数据结构——线性表（C语言实现）

写在前面：

在前面C语言的结构体学习中，我提及了链表的操作，学习数据结构我认为还是需要对C语言的数组、函数、指针、结构体有一定的了解，不然对于结构体的代码可能很难理解，特别是一些书籍上面用的还是伪代码，就很难理解。所以我建议大家可以看看我前面C语言的篇章，其实在C语言的结构体这篇博客中我已经引入了数据结构中——链表的使用，只不过相对简单，其动态链表对应的就是本章的单链表的一些内容，所以有了那篇博客，就能很好的顺应到数据结构上来。

C语言——结构体-CSDN博客

一、线性表概述

线性结构包括：线性表、栈、队列、串和数组；

线性结构的特点是：除了第一个元素没有前驱，最后一个元素没有后继以外，其余的元素的都有前驱和后继。

线性表是最常用的线性结构，由有限个特性相同的元素构成的序列称为线性表；

线性表的特点：

1、存在唯一的元素被称为“第一个”数据元素；

2、存在唯一的元素被称为“最后一个”数据元素；

3、除第一个元素外，结构中每个元素都有一个前驱；

4、除最后一个元素外，结构中每一个元素都有一个后继；

线性表按照存储方式分为：顺序存储与链式存储。

二、顺序表

线性表的顺序存储——顺序表；

线性表的链式存储——链表；

顺序表基本上就是数组，其逻辑上是相邻的元素，其物理地址也是相邻的。

2.1静态初始化

这个静态和动态如何区分呢？

在前面的C语言的结构体中，我们指出动态内存分配；

我们讲，全局变量定义在内存的静态存储区，局部变量定义在内存中的动态存储区；这个存储区称为栈区。

除此之外，内存还允许建立动态分配区域，用来存放临时的数据，这些数据需要时随时开辟，不需要时随时释放，这个区域称为堆区。

对于内存的动态分配是通过系统提供的库函数实现的，主要有malloc,calloc,free,recalloc函数。

也就是说，我们直接定义一个数组，那这个数组就是静态的，我们利用动态库函数定义一个数组，那这个数组就是动态存储的。

#include <stdio.h>
#define MAXSIZE 10
typedef struct //创建一个结构体，其成员有两个一个是data数组，用来存放数据，一个是变量length，用来存放数据长度。
{
	int data[MAXSIZE];
	int length;
}SeqList;

//静态初始化
void InitList(SeqList *L)
{
	for (int i = 0; i < MAXSIZE; i++)
	{
		L->data[i] = 0;
	}
	L->length =0;
}

int main()
{
	SeqList L;
	InitLink(&L);
	return 0;
}

运行结果：创建静态顺序表，没有什么输出；只不过先定义了一个结构体，然后将数组作为一个成员存放在里面，然后结构体里面还有一个变量，用来表示当前顺序表的长度。

后面的增删查改基本上和动态表是一样的，所以就只介绍动态顺序表的使用；

2.2动态初始化

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10
typedef struct //创建一个结构体类型
{
	int * data;//指向动态分配数组的指针
	int Max;//顺序表的最大容量
	int length;//顺序表目前的长度
}SeqList;

void InitList(SeqList * L)
{
	L->data = (int *)malloc(MAXSIZE*sizeof(int));
	L->length = 0;
	L->Max = MAXSIZE;
}

int main()
{
	SeqList L;
	InitList(&L);
}

运行结果与上面一样；我们需要注意的是，在使用动态顺序表初始化的时候，我们并没有直接定义数组，而是利用malloc函数动态的创建了一块内存地址，这个地址的大小是由规则的小空间组成，所存储的数据性质是一样的，

2.2.1增

增也可以说是插入，就是在原有的线性表基础上再插入一个元素；需要注意的是：

1、插入一次只能插入一个元素；

2、插入元素的位置要合理。即下图：

3、插入元素前，顺序表的大小要小于最大容量；

        上图表中，最大长度和位置为上面数组12345678910；数组的编号是从a[0]开始，那也就需要注意，第i个位置的元素对应的是数组的a[i-1];

        当length的长度为0，也就是空表的时候，我们只能往1的那位置插入。

        当length的长度为1，我们只能往1和2的那位置插入。往1插入23就会移到后面2的位置，1中为新插入的数据。

所以插入元素的位置要合理——i>1 以及 i<=length + 1;插入位置不能为0，没有0这个位置，插入位置不能大于长度+1，不然就不连续，长度+1的位置就会空出来。

此外，插入位置之前，lengh的长度要小于最大容量，因为插入后length+1最多只能和最大容量一样大，要不然就会溢出。

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10
typedef struct //创建一个结构体
{
	int * data;//指向动态分配数组的指针
	int Max;//顺序表的最大容量
	int length;//顺序表目前的长度
}SeqList;

void InitList(SeqList * L)
{
	L->data = (int *)malloc(MAXSIZE*sizeof(int));
	L->length = 0;
	L->Max = MAXSIZE;
}

int InsertList(SeqList * L, int i,int e)
{
	if (i<1 || i> L->length + 1)
	{
		printf("插入位置不合法\n");
		return 0;
	}
	if (L->length >= L->Max)
	{
		printf("当前存储空间已满\n");
	}
	for (int j = L->length; j >= i; j--)
	{
		L->data[j] = L->data[j - 1];

	}
	L->data[i - 1] = e;
	L->length++;
	return 1;
}
void PrintfList(SeqList  L)
{
	for (int i = 1; i <= L.length; i++)
	{

		printf("%d->", L.data[i - 1]);
	}
	printf("NULL\n");

}

int main()
{
	SeqList L;
	InitList(&L);
	PrintfList(L);
	InsertList(&L, 1, 1);//在第一个位置插入数据1；
	PrintfList(L);
	InsertList(&L, 1, 2);//在第一个位置插入数据2；
	PrintfList(L);
	InsertList(&L, 2, 3);//在第二个位置插入数据3；
	PrintfList(L);
	InsertList(&L, 4, 4);//在第四个位置插入数据4；
	PrintfList(L);
	InsertList(&L, 6, 1);//在第六个位置插入数据1；
	PrintfList(L);

}

2.2.2删

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10
typedef struct //创建一个结构体
{
	int * data;//指向动态分配数组的指针
	int Max;//顺序表的最大容量
	int length;//顺序表目前的长度
}SeqList;

void InitList(SeqList * L)
{
	L->data = (int *)malloc(MAXSIZE*sizeof(int));
	L->length = 0;
	L->Max = MAXSIZE;
}

int InsertList(SeqList * L, int i,int e)
{
	if (i<1 || i> L->length + 1)
	{
		printf("插入位置不合法\n");
		return 0;
	}
	if (L->length >= L->Max)
	{
		printf("当前存储空间已满\n");
	}
	for (int j = L->length; j >= i; j--)
	{
		L->data[j] = L->data[j - 1];

	}
	L->data[i - 1] = e;
	L->length++;
	return 1;
}

int DeleteLink(SeqList * L, int i)
{
	if (i<1 || i> L->length + 1)
	{
		printf("删除位置不合法\n");
		return 0;
	}
	if (L->length <= 0)
	{
		printf("当前存储空间为0\n");
	}
	int e = L->data[i - 1];

	for (int j = i; j < L->length; j++)
	{
		L->data[j-1] = L->data[j];
	}
	L->length--;
	return e;


}


void PrintfList(SeqList  L)
{
	for (int i = 1; i <= L.length; i++)
	{

		printf("%d->", L.data[i - 1]);
	}
	printf("NULL\n");

}

int main()
{
	int e;
	SeqList L;
	InitList(&L);
	InsertList(&L, 1, 1);
	InsertList(&L, 1, 2);
	InsertList(&L, 2, 3);
	InsertList(&L, 4, 4);
	PrintfList(L);
    e=DeleteLink(&L, 2);
	printf("删除的元素的值为：%d\n", e);
	PrintfList(L);
}

运行结果：

2.2.3查

查找分为按位查找与按值查找，按位查找直接利用L->data[i-1]就可以把第i位的值查找出来，没有多大意义，我们重点来说一下按位查找；

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10
typedef struct //创建一个结构体
{
	int * data;//指向动态分配数组的指针
	int Max;//顺序表的最大容量
	int length;//顺序表目前的长度
}SeqList;

void InitList(SeqList * L)
{
	L->data = (int *)malloc(MAXSIZE*sizeof(int));
	L->length = 0;
	L->Max = MAXSIZE;
}

int InsertList(SeqList * L, int i,int e)
{
	if (i<1 || i> L->length + 1)
	{
		printf("插入位置不合法\n");
		return 0;
	}
	if (L->length >= L->Max)
	{
		printf("当前存储空间已满\n");
	}
	for (int j = L->length; j >= i; j--)
	{
		L->data[j] = L->data[j - 1];

	}
	L->data[i - 1] = e;
	L->length++;
	return 1;
}

int DeleteLink(SeqList * L, int i)
{
	if (i<1 || i> L->length + 1)
	{
		printf("删除位置不合法\n");
		return 0;
	}
	if (L->length <= 0)
	{
		printf("当前存储空间为0\n");
	}
	int e = L->data[i - 1];

	for (int j = i; j < L->length; j++)
	{
		L->data[j-1] = L->data[j];
	}
	L->length--;
	return e;


}

int ReserchList(SeqList  L, int e)
{
	for (int i = 0; i < L.length; i++)
	{
		if (e = L.data[i])
		{
			return i + 1;
		}
	}
	printf("查找失败，没有该元素的值；\n");
	return 0;
}

void PrintfList(SeqList  L)
{
	for (int i = 1; i <= L.length; i++)
	{

		printf("%d->", L.data[i - 1]);
	}
	printf("NULL\n");

}

int main()
{
	int e;
	SeqList L;
	InitList(&L);
	InsertList(&L, 1, 1);
	InsertList(&L, 1, 2);
	InsertList(&L, 2, 3);
	InsertList(&L, 4, 4);
	PrintfList(L);
	e = ReserchList(L, 2);
	printf("查找后，该值的位置为%d\n", e);

}

2.2.4扩容

扩容是只针对动态内存的，扩容的步骤：

1、生成指向原来顺序表的存储空间的指针；
2、为顺序表开辟新的一块更大的空间
3、数据转移；
4、修改顺序表的最大长度；
5、用free释放掉原有的空间。

int IncreatSize(SeqList * L, int len)
{
   int * p = L->data;

   L->data = (int*)malloc((L->Max + len)*sizeof(int));

   for (int i = 0; i < L->length; i++)
   {
       L->data[i] = p[i];
   }
   L->Max += len;
   free(p);
   return 0;
}

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10
typedef struct //创建一个结构体
{
	int * data;//指向动态分配数组的指针
	int Max;//顺序表的最大容量
	int length;//顺序表目前的长度
}SeqList;

void InitList(SeqList * L)
{
	L->data = (int *)malloc(MAXSIZE*sizeof(int));
	L->length = 0;
	L->Max = MAXSIZE;
}

int InsertList(SeqList * L, int i,int e)
{
	if (i<1 || i> L->length + 1)
	{
		printf("插入位置不合法\n");
		return 0;
	}
	if (L->length >= L->Max)
	{
		printf("当前存储空间已满\n");
	}
	for (int j = L->length; j >= i; j--)
	{
		L->data[j] = L->data[j - 1];

	}
	L->data[i - 1] = e;
	L->length++;
	return 1;
}

int DeleteLink(SeqList * L, int i)
{
	if (i<1 || i> L->length + 1)
	{
		printf("删除位置不合法\n");
		return 0;
	}
	if (L->length <= 0)
	{
		printf("当前存储空间为0\n");
	}
	int e = L->data[i - 1];

	for (int j = i; j < L->length; j++)
	{
		L->data[j-1] = L->data[j];
	}
	L->length--;
	return e;


}

int ReserchList(SeqList  L, int e)
{
	for (int i = 0; i < L.length; i++)
	{
		if (e = L.data[i])
		{
			return i + 1;
		}
	}
	printf("查找失败，没有该元素的值；\n");
	return 0;
}

void PrintfList(SeqList  L)
{
	for (int i = 1; i <= L.length; i++)
	{

		printf("%d->", L.data[i - 1]);
	}
	printf("NULL\n");

}

//扩容：
/*
1、生成指向原来顺序表的存储空间的指针；
2、为顺序表开辟新的一块更大的空间
3、数据转移；
4、修改顺序表的最大长度；
5、用free释放掉原有的空间。
*/
int IncreatSize(SeqList * L, int len)
{
	int * p = L->data;

	L->data = (int*)malloc((L->Max + len)*sizeof(int));

	for (int i = 0; i < L->length; i++)
	{
		L->data[i] = p[i];
	}
	L->Max += len;
	free(p);
	return 0;
}

三、单链表

3.1概述

链表：逻辑上相邻的数据元素，其物理地址不一定相邻；用一组任意的存储单元存储线性表的元素（这组存储单元可以是连续的，也可以是不连续的。）因此，为了表示每个数据元素与前后元素的关系，对于某个元素来说，存储的不仅是本身的信息，还需要指定下一个元素的信息；

这种由两部分组成的数据元素的存储，称为结点；它包括两个域：

存储数据元素信息的区域称为数据域；

存储后继元素位置的区域称为指针域；

由于线性表的链式存储，每个节点中只包含一个指针域，故称为线性链表或者单链表；

一般情况下，为了处理方便，在单链表的第一个节点之前附设一个节点，称之为头结点。如图红色框中的结点；

首元结点：指链表中存储第一个数据元素的结点，上图中，数据区域为1的结点。

头结点：是在首元结点之前附设的一个节点，其指针域指向首元结点，头结点的数据域不存储任何信息，也可以存储一些附加信息。例如：如果当数据域的元素为整数型时，头结点的数据域可存放该线性表的长度。

头指针：指向链表的第一个结点的指针，若链表设有头结点，则头指针所指结点为头结点，如果不设头结点，头指针指向首元结点。

3.2单链表

3.2.1初始化

在初始化之前我们先创建链表所需要的结点——即定义结构体类型：

typedef struct Node//定义一个结构体，并用typedef进行替换，即struct Node——Node；
{
	int data;			//数据域，本次采用整形；
	struct Node * next;//指针域，指针类型为结构体指针；
}Node;

初始化单链表：

生成一个新的节点，用头指针指向头结点。头结点的指针域置空；

Node * InitList() //定义一个初始化函数，其返回值为结构体指针，即将构建的链表首地址返回；
{
	Node * head;//定义一个头指针；
	head= (Node *)malloc(sizeof(Node));//创建一个节点，并让头指针指向该节点，该节点也就是头结点；
	head->data = 0;//头结点的数据域为0；
	head->next = NULL;//头结点的指针域为空；
	return head;//返回头结点的地址
}

3.2.2插入

前插法：

前插法是将新的结点逐个插入链表的头部（头结点的后面），每次申请一个新的节点，将其进行插入。

void HeadInsert(Node * L,int data)//定义一个前插函数，函数的参数分别为，链表的地址，以及新插入的元素值；
{
	Node * node = (Node *) malloc(sizeof(Node));//构建一个新的结点，然后返回其地址；
	node->data = data;//将传入的数据存放在新节点的数据域；
	node->next = L->next;//将原来的头结点的指针域的值，存放在新节点的指针域中；
	L->next = node;//将新节点的地址存放在头指针的指针域；
	L->data++;//头结点的数值域的数值加1，表示链表增加一个长度；
}

后插法：

后插法是通过将新节点逐个插入到链表的尾部，同前插法相同，每次申请一个新结点，将数值进行存放，不同的是，为了使新结点能够插入到末尾，需要增加一个尾指针，尾指针指向链表的尾结点；

void TailInsert(Node * L, int data)//定义一个后插函数，函数的参数分别为，链表的地址，以及新插入的元素值；
{
	Node * node=L;//定义一个指针，类型为结构体指针；
	int i ;
	for (i = 0; i < L->data; i++)//将指针指向尾结点；
	{
		node = node->next;
	}
	Node * n = (Node *) malloc(sizeof(Node));//创建一个新的结点，将创建的结点的地址先放在n中；
	node->next = n;//将新结点的地址存放在尾结点的指针域；
	n->data = data;//将新元素的数据存放在新结点的数据域；
	n->next = NULL;//新结点重新作为尾结点，其指针域为空；
	L->data++;//头结点的数值域数值加1；表示链表的长度+1；
}

3.2.3删除

删除指定位置的结点，首先应该找到该位置的前驱结点，在单链表删除之前应将前驱结点的指针域的地址改为其后继结点的地址。

int  DeleteList(Node * L, int data)//定义一个删除函数，函数的参数分别为，链表的地址，以及删除的元素值；
{
	Node * p1 = L;//定义一个指针，类型为结构体指针，准备用来表指向前驱结点；
	Node * p2 = L->next;//定义一个指针，类型为结构体指针，准备用来表指向删除的结点；
	while (p2)//逐个判断其数值是否与链表中的一直，直到每一个对比完。
	{
		if (p2->data == data)//判断是不是要删除的元素
		{						//如果是
			p1->next = p2->next;//将该节点的指针域的值放在前驱结点的指针域中；
			free(p2);//释放该节点的空间
			L->data--;//链表的长度减1；
			return 1;//删除成功，返回1；
		}					//如果不是
		p1 = p2;			//依次向后移到下一个结点；
		p2 = p2->next;
	}
	return 0;//没有要删除的元素，返回0；
}

2.3.4打印

void PrintList(Node * L)//定义一个打印函数，函数的参数为，链表的地址
{
	Node * node = L->next;//定义一个指针，类型为结构体指针,用来进行数据的移动；
	while (node)//当该结点的指针域为空时，表示打印结束；
	{
		printf("%d ", node->data);//打印结点的数据
		node = node->next;//指向下一个结点；
	}
	printf("\n");
}

2.3.5案例

创建一个新链表，利用前插插入5个数，利用后插插入5个数，打印出来链表，然后删除其中一些结点，再打印出来；

#include <stdio.h>
#include <stdlib.h>


//定义链表结构体节点

typedef struct Node//定义一个结构体，并用typedef进行替换，即struct Node——Node；
{
	int data;			//数据域，本次采用整形；
	struct Node * next;//指针域，指针类型为结构体指针；
}Node;

//初始化链表

Node * InitList() //定义一个初始化函数，其返回值为结构体指针，即将构建的链表首地址返回；
{
	Node * head;//定义一个头指针；
	head= (Node *)malloc(sizeof(Node));//创建一个节点，并让头指针指向该节点，该节点也就是头结点；
	head->data = 0;//头结点的数据域为0；
	head->next = NULL;//头结点的指针域为空；
	return head;//返回头结点的地址
}

//链表头插：
void HeadInsert(Node * L,int data)//定义一个前插函数，函数的参数分别为，链表的地址，以及新插入的元素值；
{
	Node * node = (Node *) malloc(sizeof(Node));//构建一个新的结点，然后返回其地址；
	node->data = data;//将传入的数据存放在新节点的数据域；
	node->next = L->next;//将原来的头结点的指针域的值，存放在新节点的指针域中；
	L->next = node;//将新节点的地址存放在头指针的指针域；
	L->data++;//头结点的数值域的数值加1，表示链表增加一个长度；
}

//链表尾插;
void TailInsert(Node * L, int data)//定义一个后插函数，函数的参数分别为，链表的地址，以及新插入的元素值；
{
	Node * node=L;//定义一个指针，类型为结构体指针；
	int i ;
	for (i = 0; i < L->data; i++)//将指针指向尾结点；
	{
		node = node->next;
	}
	Node * n = (Node *) malloc(sizeof(Node));//创建一个新的结点，将创建的结点的地址先放在n中；
	node->next = n;//将新结点的地址存放在尾结点的指针域；
	n->data = data;//将新元素的数据存放在新结点的数据域；
	n->next = NULL;//新结点重新作为尾结点，其指针域为空；
	L->data++;//头结点的数值域数值加1；表示链表的长度+1；
}

//链表删除

int  DeleteList(Node * L, int data)//定义一个删除函数，函数的参数分别为，链表的地址，以及删除的元素值；
{
	Node * p1 = L;//定义一个指针，类型为结构体指针，准备用来表指向前驱结点；
	Node * p2 = L->next;//定义一个指针，类型为结构体指针，准备用来表指向删除的结点；
	while (p2)//逐个判断其数值是否与链表中的一直，直到每一个对比完。
	{
		if (p2->data == data)//判断是不是要删除的元素
		{						//如果是
			p1->next = p2->next;//将该节点的指针域的值放在前驱结点的指针域中；
			free(p2);//释放该节点的空间
			L->data--;//链表的长度减1；
			return 1;//删除成功，返回1；
		}					//如果不是
		p1 = p2;			//依次向后移到下一个结点；
		p2 = p2->next;
	}
	return 0;//没有要删除的元素，返回0；
}

//链表打印

void PrintList(Node * L)//定义一个打印函数，函数的参数为，链表的地址
{
	Node * node = L->next;//定义一个指针，类型为结构体指针,用来进行数据的移动；
	while (node)//当该结点的指针域为空时，表示打印结束；
	{
		printf("%d ", node->data);//打印结点的数据
		node = node->next;//指向下一个结点；
	}
	printf("\n");
}

int main()
{
	Node * L= InitList();
	HeadInsert(L, 1);
	HeadInsert(L, 2);
	HeadInsert(L, 3);
	HeadInsert(L, 4);
	HeadInsert(L, 5);
	TailInsert(L, 6);
	TailInsert(L, 7);
	TailInsert(L, 8);
	TailInsert(L, 9);
	TailInsert(L, 10);
	PrintList(L);

	int ret =DeleteList(L, 1);
	if (ret == 1)
	{
		printf("sucess delete\n");
	}
	else
	{
		printf("fail delete\n");
	}
		PrintList(L);
		return 0;
}

运行结果：

3.3单循环链表

循环链表是另一种形式的链式存储结构，其特点是表中的追后一个节点的指针域指向头结点，整个链表形成一个环，由此，链表的任何一个节点出发均可以找到表中的其他节点。

单循环链表的操作和单链表基本一致，差别进在于：当链表遍历时，判别当前指针P是指向表尾结点的终止条件不同。

单链表：判别条件为P!=NULL;或者P->next!=NULL;

单循环链表：判别条件为P!=L;或者P->next!=L;

案例：

#include <stdio.h>
#include <stdlib.h>

#define  True  1
#define  False 0

typedef struct Node
{	
	int data;
	struct Node * next;
}Node;

Node * Init_Link()
{
	Node* head = (Node *)malloc(sizeof(Node));
	head->data = 0;
	head->next = head;
	return head;
}

void HeadInsert(Node * L, int data)
{
	Node * n = (Node *)malloc(sizeof(Node));
	n->data = data;
	n->next = L->next;
	L->next = n;
	L->data++;
}
void TailInsert(Node * L, int data)
{
	Node * n = (Node *)malloc(sizeof(Node));
	Node * b = L->next;
	while (b->next!= L)
	{
		b = b->next;
	}
	b->next = n;
	n->data = data;
	n->next = L;
	L->data++;
}

void PrintLink(Node * L)
{
	Node * L1 = L->next;
	while (L1 != L)
	{
		printf("%d->", L1->data);
		L1 = L1->next;
	}
	printf("NULL\n");
}

int DeleteLink(Node * L, int data)
{
	Node * n1 = L;
	Node * n2 = L->next;
	while (n2 != L)
	{
		if (n2->data == data)
		{
			n1->next = n2->next;
			free(n2);
			L->data--;
			return True;
		}
		n1 = n2;
		n2 = n2->next;
	}
	return False; 
}

int main()
{
	Node* node = Init_Link();
	HeadInsert(node, 1);
	HeadInsert(node, 2);
	HeadInsert(node, 3);
	HeadInsert(node, 4);
	HeadInsert(node, 5);
	TailInsert(node, 6);
	TailInsert(node, 7);
	TailInsert(node, 8);
	TailInsert(node, 9);
	TailInsert(node, 10);
	PrintLink(node);
	DeleteLink(node, 5);
	DeleteLink(node, 6);
	PrintLink(node);
	return 0;
}

运行结果：

四、双向链表

4.1双向链表

以上讨论的链式存储结构的节点只有一个指示直接后继的指针域，也就是说从某个节点出发只能顺指针向后进行查找。若要寻查结点的直接前驱，则必须要从表头指针出发。

为了克服单链表这种单向性的缺点，可以利用双向链表。

顾名思义，双向链表的节点由两个指针域，一个指向直接后继，一个指向直接前驱。结点的结构如下图所示：

#include <stdio.h>
#include <stdlib.h>

#define True 1
#define False 2

typedef struct Node
{
	int data;
	struct Node * pre;
	struct Node * next;
}Node;

Node * InitLink()
{
	Node * head = (Node*)malloc(sizeof(Node));
	head->data = 0 ;
	head->next = NULL;
	head->pre = NULL; 
}

void HeadInsert(Node * L, int data)
{
	Node * n = (Node *)malloc(sizeof(Node));
	n->data = data;
	if (L->next == NULL)
	{
		n->pre = L;
		n->next = L->next;
		L->next = n;
	}
	else
	{
		n->next = L->next;
		n->pre = L;
		L->next->pre = n;
		L->next = n;
	}
	L->data++;
}

void TailInsert(Node * L,int data)
{
	Node * n = (Node *)malloc(sizeof(Node));
	n->data = data;
	Node * n1=L;
	while (n1->next )
	{
		n1 = n1->next;
	}
	n->pre = n1;
	n->next = n1->next;
	n1->next = n;
	L->data++;
}
int DeleteLink(Node * L, int data)
{
	Node * n = L;
	while (n)
	{
		if (n->data == data)
		{
			n->pre->next = n->next;
			if (n->next)
			{
				n->next->pre = n->pre;
			}
				free(n);
				L->data--;
				return True;
		}
		n = n->next;
	}
	return False;

}
 void PrintLint(Node * L)
{
	Node * n = L->next;
	while (n)
	{
		printf("%d->", n->data);
		n = n->next;
	}
	printf("NULL\n");
 }
 int main()
 {
	 Node *L = InitLink();
	 HeadInsert(L, 1);
	 HeadInsert(L, 2);
	 HeadInsert(L, 3);
	 HeadInsert(L, 4);
	 HeadInsert(L, 5);
	 TailInsert(L, 6);
	 TailInsert(L, 7);
	 TailInsert(L, 8);
	 TailInsert(L, 9);
	 TailInsert(L, 10);
	 PrintLint(L);
	 DeleteLink(L, 5);
	 DeleteLink(L, 6);
	 DeleteLink(L, 10);
	 PrintLint(L);
	 return 0;
 }

运行结果：

4.2双循环链表

循环链表是另一种形式的链式存储结构，其特点是表中的追后一个节点的指针域指向头结点，整个链表形成一个环，由此，链表的任何一个节点出发均可以找到表中的其他节点。

双向循环链表的是结合双链表和循环链表的特点，其基本的算法与前文相似，需要注意的是插入和删除时有很大的不用，在双链表种需要需改多个指针。

#include <stdio.h>
#include <stdlib.h>

#define True 1
#define False 0

typedef struct Node
{
	int data;
	struct Node * pre;
	struct Node * next;
}Node;

Node * InitLink()
{
	Node * head = (Node*)malloc(sizeof(Node));
	head->data = 0;
	head->next =head;
	head->pre = head;
	return head;
}

void HeadInter(Node* L, int data)
{
	Node* node = (Node*)malloc(sizeof(Node));
	node->data = data;
	node->next = L->next;
	node->pre = L;
	L->next->pre = node;
	L->next = node;
	L->data++;
}
void TailInter(Node * L, int data)
{
	
	Node * node = L;
	while (node->next != L)
	{	
		node = node->next;
	}
	Node * n = (Node *)malloc(sizeof(Node));
	n->data = data;
	n->pre = node;
	n->next = L;
	L->pre = n;
	node->next = n;
	L->data++;
}
int DeleteLink(Node* L, int data)
{
	Node * node = L->next;
	while (node!= L)
	{
		if (node->data == data)
		{
			node->pre->next = node->next;
			node->next->pre = node->pre;
			free(node);
			L->data--;
			return True;
		}
		  node = node->next;
	}
	return False;	
}

void PrintLink(Node *L)
{
	Node* node = L->next;
	while (node!=L)
	{
		printf("%d->", node->data);
		node = node->next;
	}
	printf("NULL\n");
}

int main()
{
	Node * L = InitLink();
	HeadInter(L, 1);
	HeadInter(L, 2);
	HeadInter(L, 3);
	HeadInter(L, 4);
	HeadInter(L, 5);
	TailInter(L, 6);
	TailInter(L, 7);
	TailInter(L, 8);
	TailInter(L, 9);
	TailInter(L, 10);
	PrintLink(L);
	DeleteLink(L,7);
	DeleteLink(L,6);
	DeleteLink(L,5);
	DeleteLink(L,1);
	PrintLink(L);
	return 0;
}

运行结果：

需要注意的时，在指针进行交换的时候，一定需要注意顺序；例如：

在头插法中:

void HeadInter(Node* L, int data)
{
   Node* node = (Node*)malloc(sizeof(Node));
   node->data = data;
   node->next = L->next;
   node->pre = L;
   L->next->pre = node;
   L->next = node;
   L->data++;
}

        如果上述两个代码的顺序发生错误，就会在删除头插数据时出现错误，因为其连接发生错误。

        当增加指针时，一定注意，先修改新插的节点，再修改后继节点，最后再修改前驱节点。不然就会发生错误。