【数据结构】线性表知识大全_数据结构线性表知识点总结

1、线性表的定义

线性表是具有相同数据类型的 n（n>=0）个数据元素的有限序列，其中 n 为表长，当 n=0 时线性表是一个空表。若用 L 命名线性表，其一般表示为：

      L = (a1,a2,...,ai,ai+1,...,an)
1

式中，a1 是唯一的“第一个”数据元素，又称表头元素；an 是唯一的“最后一个”数据元素，又称表尾元素。除第一个元素外，每个元素有且只有一个直接前驱。除最后一个元素外，每个元素有且只有一个直接后继。

线性表具有如下特点：

• 表中元素的个数有限
• 表中元素具有逻辑上的顺序性，表中元素有其先后次序
• 表中元素都是数据元素，每个元素都是单个元素
• 表中元素的数据类型都相同，每个元素占用相同大小的存储空间
• 表中元素具有抽象性，只讨论元素间的逻辑关系，不考虑元素表示的内容

注意：线性表是一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是指存储结构，两者属于不同层次的概念，不要将其混淆。

2、线性表顺序存储表示

2.1 顺序表的定义

线性表的顺序存储又称顺序表。是用一组地址连续的存储单元依次存储线性表中的数据元素，使得逻辑上相邻的两个元素在物理位置上也相邻。顺序表中元素的逻辑顺序与其物理顺序相同。

注意：线性表中元素的次序是从 1 开始的，数组中元素的下标是从 0 开始的

线性表的顺序存储类型描述如下：

#define MaxSize 50  //定义线性表的最大长度
typedef struct{
    ElemType date[MaxSize];  //顺序表的元素，ElemType为元素类型
    int length;  //顺序表的当前长度
}SqList;  //顺序表的类型长度
1
2
3
4
5

一维数组可以是静态分配，也可以是动态分配。在静态分配时，由于数组的大小和空间事先已经固定，一旦空间占满，再加入数据便会产生溢出，进而导致程序奔溃。

动态分配时，存储数组的空间是在程序执行过程中通过动态存储分配语句分配的，一旦数据空间占满，就会另外开辟一块更大的存储空间，用以替换原来的存储空间，从而达到扩充存储数据空间的目的，不需要一次性划分所有空间。

动态分配顺序表存储空间类型描述如下：

#define InitSize 100 //表长度的初始定义
typedef struct{
   ElemType *data;  //指示动态分配数据的指针
   int MaxSize,length;  //数组的最大容量和当前个数
   } SqlList; //动态分配数组顺序表的类型定义
1
2
3
4
5

C 的初始动态分配语句为：

L.data = (ElemType *)malloc(sizeof(ElemType)*InitSize);
1

注意：动态分配并不是链式存储，它也属于顺序存储结构，物理结构没有变化，依然是随机存取方式，只是分配的空间大小可以在运行时决定。

顺序表具有的特点如下所示：

• 随机访问，即通过首地址和元素序号可在时间 O(1) 内找到指定的元素
• 存储密度高，每个节点只存储数据元素
• 逻辑上相邻的两个元素在物理上也相邻，插入和删除数据时需要移动大量元素

2.2 顺序表的基本操作

（1）插入操作：指定位置插入数据元素

• 最好情况：在表尾插入（即 i=n+1），元素后移语句不执行，时间复杂度为 O(1) 。
• 最坏情况：在表头插入（即 i=1），元素后移语句将执行 n 次，时间复杂度为 O(n) 。
• 平均情况：假设 pi（pi = 1/(n+1)）是在第 i 个位置上插入一个节点的概率，则在长度为 n 的线性表中插入一个结点时，所需要移动的平均次数为：ave(平均次数) = (1/(n+1)*(n(n+1)))/2 = n/2 。
• 线性表插入算法的平均时间复杂度为 O(n) 。

（2）删除操作：指定位置删除数据元素

• 最好情况：删除表尾元素（即 i = n），无需移动元素，时间复杂度为 O(1) 。
• 最坏情况：删除表头元素（即 i = 1），需移动除第一个元素外的所有元素，时间复杂度为 O(n) 。
• 平均情况：假设 pi（pi = 1/(n+1)）是删除第 i 个位置上结点的概率，则在长度为 n 的线性表中删除一个结点时，所需要移动的平均次数为：ave(平均次数) = (1/n*(n(n-1)))/2 = (n-1)/2 。
• 线性表删除算法的平均时间复杂度为 O(n) 。

（3）按值查找（顺序查找）

• 最好情况：查找的元素就在表头，仅需比较一次，时间复杂度为 O(1) 。
• 最坏情况：查找的元素在表尾（或不存在）时，需要比较 n 次，时间复杂度为 O(n) 。
• 平均情况：假设 pi（pi=1/n）是查找的元素在第 i（1<=i<=L.length）个位置上的概率，则在长度为 n 的线性表中查找值为 e 的元素所需比较的平均次数为：ave(平均次数) = (1/n*((n(n+1))/2)/2 = （n+1)/2
• 线性表按值查找算法的平均时间复杂度为 O(n）。

下面通过代码简单介绍顺序表的初始化、插入指定位置操作、删除指定位置操作以及查询操作，示例代码如下：

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

#define OK 1;
#define ERROR 0;

#define LIST_INIT_SIZE 100 
#define LISTINCREMENT 10 

typedef int Status;
typedef int ElemType;

typedef struct
{
	ElemType *elem;
	int length;
	int listsize;
}SqList;

Status initList(SqList &L)
{
	L.elem=(ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
	if(!L.elem)
	{
		exit(0);
	}
	L.length=0;
	L.listsize=LISTINCREMENT;
	return OK;
}

Status createList(SqList &L,int n)
{
    ElemType *newbase;
    int i;
    if(n<0)
    {
        return ERROR;
    }
    if(n>L.listsize)
    {
        newbase = (ElemType*)realloc(L.elem,(L.listsize + n)*sizeof(ElemType));
        if(!newbase) 
		{
			exit(0);
		}
        L.elem = newbase;
        L.listsize += n;
    }
    L.length = n;
    for(i=0;i<n;i++)
    {
        scanf("%d",&(L.elem[i]));
    }
    return OK;
}
Status showList(SqList &L)
{
	int i;
	if(L.length<=0)
	{
		return ERROR;
	}
    for(i=0;i<L.length;i++)
	{
		printf("%d\t",L.elem[i]);
	}
	printf("\n");
	return OK;
}

Status destroyList(SqList &L)
{
	if(L.elem)
	{
		free(L.elem);
	}
	return OK;
}

Status deleteList(SqList &L,int i,ElemType &e)
{
	ElemType *p,*q;
	if((i<1)||(i>L.length))
	{
		return ERROR;
	}
	p=&(L.elem[i-1]);
	e=*p;
    q=L.elem+L.length-1;
	for(++p;p<=q;++p)
		*(p-1)=*p;
	--L.length;
	return OK;
}

Status insertList(SqList &L,int i,ElemType e)
{
	ElemType *p,*q,*newbase;
	if((i<1)||(i>L.length+1))
	{
		return ERROR;
	}
	if(L.length>=L.listsize)
	{
		newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
		if(!newbase)
		{
			exit(0);
		}
		L.elem=newbase;
		L.listsize+=LISTINCREMENT;
	}
	q=&(L.elem[i-1]);
	for(p=&(L.elem[L.length-1]);p>=q;--p)
		*(p+1)=*p;
	*q=e;
	++L.length;
	return OK;
}
int main()
{
	SqList L;
	printf("申请顺序表当前长度以及存储空间初始分配量:\n");
	initList(L);
	printf("%d\t%d\n",L.length,L.listsize);
	printf("顺序表中输入五个数据:\n");
	createList(L,5);
	printf("输出顺序表中全部元素:\n");
	showList(L);
	printf("顺序表中删除三号位置上的数据:\n");
	int e;
	deleteList(L,3,e);
	showList(L);
	printf("被删除的元素e:\ne=%d\n",e);
	printf("顺序表二号位置插入一个数据10:\n");
	insertList(L,2,10);
	showList(L);
	printf("初始化顺序表:\n");
	destroyList(L);
	printf("\n");
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143

运行结果图如下所示：

示例代码：结构体数组创建学生成绩信息及其指针操作代码如下所示：

#include<stdio.h>
#include<string.h>
#define max 3
struct student
{
	char name[5];
	char sex[5];
	int age;
	char classes[10];
	int chinese;
	int math;
};
struct student stu[max];
void input()
{
	printf("输入学生的相关信息:\n");
    for(int i=0;i<max;i++)
	{
		printf("输入第%d个学生的相关信息\n",i+1);
		printf("学生姓名:\t");
		scanf("%s",&stu[i].name);
		printf("学生性别:\t");
		scanf("%s",&stu[i].sex);
		printf("学生年龄:\t");
		scanf("%d",&stu[i].age);
		printf("学生班级:\t");
		scanf("%s",&stu[i].classes);
		printf("语文成绩:\t");
		scanf("%d",&stu[i].chinese);
		printf("数学成绩:\t");
		scanf("%d",&stu[i].math);
	}
}
void show()
{
	printf("\n\n输出学生的相关信息:\n");
	printf("姓名\t性别\t年龄\t班级\t语文\t数学\n");
	for(int i=0;i<max;i++)
	{
		printf("%s\t%s\t%d\t%s\t%d\t%d\n",stu[i].name,stu[i].sex,stu[i].age,stu[i].classes,stu[i].chinese,stu[i].math);
	}
}
void find()
{
	char name[5];
	char *p;
	p=name;
	printf("\n\n输入你要查询的学生姓名:\t");
	scanf("%s",p);
	for(int i=0;i<max;i++)
	{
		if(strcmp(p,stu[i].name)==0)
		{
		    printf("姓名\t性别\t年龄\t班级\t语文\t数学\n");
            printf("%s\t%s\t%d\t%s\t%d\t%d\n",stu[i].name,stu[i].sex,stu[i].age,stu[i].classes,stu[i].chinese,stu[i].math);
			break;
		}
			
		else
		{
			printf("没有你要查询的学生信息!\n");
			break;
		}
	}
}
int main()
{	
	input();
	show();
	find();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

运行结果如下图所示：

3、线性表的链式表示

3.1 单链表的定义

线性表的链式存储又称单链表，是指通过一组任意的存储单元来存储线性表中的数据元素。

单链表在创建过程中，除了要存放自身的信息外，还需要存放一个指向其后继的指针。单链表结果示意图如下所示：

其中， data 为单链表的数据域，存放数据元素；next 为指针域，指向其后继结点的指针。

单链表的结点类型描述如下：

typedef struct LNode{  //定义单链表结点类型
   ElemType data;  //数据域
   struct LNode *next;  //指针域
}LNode,*LinkList;
1
2
3
4

单链表可以解决顺序表需要大量存储单元的缺点，但单链表附加指针域，也存在浪费存储空间的缺点。单链表的存储空间离散地分布在存储空间中，单链表是非随机存取地存储结构。在使用单链表查找数据元素时，不能直接找到某个特定地结点，需要从表头开始遍历，依次比较查找。

为了操作上地遍历，在单链表的第一个结点之前附加一个结点，称为头结点。头结点的数据域可以不设任何信息，也可以用来记录表长等信息。头结点结构示意图如下：

头指针和头结点的区分：不管带不带头结点，头指针始终指向链表的第一个结点，而头结点是带头结点的链表的第一个结点，结点内通常不存储信息。
引入头结点后，可以带来两个优点：

• 由于第一个数据结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作和在表的其他位置上的操作一致，无需进行特殊处理。
• 无论链表是否为空，其头指针都指向头结点的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就得到统一。

3.2 单链表的基本操作

（1）头插法创建单链表

• 从一个空表开始，生成新结点，并将读取到的数据存储到新结点的数据域中，然后将新结点插入到当前链表的表头，即头结点之后。头插法操作示意图如下所示：
  
• 头插法建立单链表时，读入数据的顺序与生成的链表中的元素的顺序是相反的。每个结点的插入时间为 O(1)，设单链表长为 n，则总时间复杂度为 O(n)。
• 头插法建立单链表的示例代码如下：

void HeadCreatList(List *L) //头插法建立链表
{
List *s; //不用像尾插法一样生成一个终端节点。
L->next = NULL;
for (int i = 0; i < 10; i++) {
        s = (struct List*) malloc(sizeof(struct List));//s指向新申请的节点
        s->data = i;//用新节点的数据域来接受i
        s->next = L->next; //将L指向的地址赋值给S;//头插法与尾插法的不同之处主要在此，
        //s所指的新节点的指针域next指向L中的开始节点
        L->next = s; //头指针的指针域next指向s节点，使得s成为开始节点。
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

（2）尾插法创建单链表

• 该方法将新节点插入到当前链表的表尾中，为此必须增加一个尾指针 r，使其始终指向当前链表的尾结点。该方法生成的链表中的结点的次序和输入数据的顺序一致。尾插法创建单链表示意图如下图所示：
  
• 附设了一个指向表尾结点的指针，故时间复杂度和头插法的相同。
• 尾插法建立单链表的示例代码如下：

void TailCreatList(List *L) //尾插法建立链表
{
List *s, *r;//s用来指向新生成的节点。r始终指向L的终端节点。
r = L; //r指向了头节点，此时的头节点是终端节点。
for (int i = 0; i < 10; i++) {
        s = (struct List*) malloc(sizeof(struct List));//s指向新申请的节点
        s->data = i; //用新节点的数据域来接受i
        r->next = s; //用r来接纳新节点
        r = s; //r指向终端节点
    }
    r->next = NULL; //元素已经全部装入链表L中
    //L的终端节点指针域为NULL，L建立完成
}
1
2
3
4
5
6
7
8
9
10
11
12
13

单链表的创建以及基本操作（以头插法为例）：

#include<stdio.h>
#include<stdlib.h>
#define OK 1;
#define ERROR 0;
typedef int Status;
typedef int ElemType;
typedef struct LNode
{
	ElemType data;
	struct LNode *next;
}*LinkList;

void createList(LinkList &L,int n)
{
	int i;
	LinkList p;
	L=(struct LNode *)malloc(sizeof(LNode));
	L->next=NULL;
	for(i=1;i<=n;i++)
	{
		p=(struct LNode *)malloc(sizeof(LNode));
		scanf("%d",&p->data);
		p->next=L->next;
		L->next=p;
	}
}
void showList(LinkList &L)
{
	LinkList p=L->next;
If(p==NULL)
{ 
    printf(“单链表为空!”);
    return ERROR;
}
	while(p!=NULL)
	{
		printf("%d\t",p->data);
		p=p->next;
	}
	printf("\n");
}
Status insertList(LinkList &L,int i,ElemType e)
{
	int j=0;
	LinkList p,q;
	p=L;
	while(p&&j<i-1)
	{
		p=p->next;
		++j;
	}
	if(!p||j>i-1)
	{
		return ERROR;
	}
	q=(struct LNode *)malloc(sizeof(LNode));
    q->data=e;
	q->next=p->next;
	p->next=q;
	return OK;
}
Status deleteList(LinkList &L,int i,ElemType &e)
{
	int j=0;
	LinkList p,q;
    p=L;
	while(p->next&&j<i-1)
	{
		p=p->next;
		++j;
	}
	if(!p->next&&j>i-1)
	{
		return ERROR;
	}
	q=p->next;
	p->next=q->next;
	e=q->data;
    free(q);
	return OK;
}
void destoryList(LinkList &L)
{
	LinkList p;
	p=L;
	p->next=NULL;
	while(p==NULL)
	{
		p=L->next;
		free(p);
		L->next=p;
	}
}

int main()
{
	LinkList L;
	printf("创建链表输入五个数据:\n");
	createList(L,5);
	printf("输出链表中的全部数据:\n");
	showList(L);
	printf("插入数据进入链表中的三号位置:\n");
	insertList(L,3,10);
	showList(L);
	int e;
	printf("链表中删除四号位置的数据:\n");
	deleteList(L,4,e);
	showList(L);
	printf("被删除的数据e=%d\n\n",e);
	printf("初始化线性链表:\n");
	destoryList(L);
	printf("\n初始化后的线性链表:\n");
	showList(L);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

运行结果如下图所示：

3.3 双链表的定义

单链表结点中只有一个指向其后继的指针，使得单链表只能从头结点依次顺序地向后遍历。要访问某个结点地前驱结点（插入、删除操作）时，只能从头开始遍历，访问后继结点时地时间复杂度为 O(1)，访问前驱结点的时间复杂度为 O(n)。

为了克服单链表上的缺陷，引入了双链表，双链表结点中有两个指针 prior 和 next，分别为指向其前驱结点和后继结点，双链表示意图如下所示：

双链表中结点类型的描述如下：

typedef struct DNode{  //定义双链表结点类型
   ElemType data; //数据域
   struct DNode *prior,*next;  //前驱和后继指针
   }DNode,*DLinklist;
1
2
3
4

3.4 双链表的基本操作

（1）双链表的插入操作

• 在双链表中 p 所指的结点之后插入结点 *s，其指针的变化过程如下图所示：
  
• 插入操作的代码片段如下所示：

 1.  s->next = p->next;  //将结点 *s 插入到结点 *p 之后
 2.  p->next->prior = s;
 3.  s->prior = p;
 4.  p->next = s
1
2
3
4

注意：语句顺序虽然不唯一，但也不是任意的，第1和2两步必须在第4步之前，否则 *p 的后继结点的指针就会丢掉，导致插入失败。

（2）双链表的删除操作

• 删除双链表中结点 *p 的后继结点 *q，其指针的变化过程如下图所示：
  
• 删除操作的代码片段如下所示：

   p->next = q->next; //步骤 1
   q->next->prior = p; //步骤2
   free(q); //释放结点空间
1
2
3

双链表的基本操作源代码如下图所示：

#include<stdio.h>
#include<stdlib.h>
#define OK 1;
#define ERROR 0;
typedef int Status;
typedef int ElemType;
typedef struct DuLNode
{
	ElemType data;
	struct DuLNode *next;
	struct DuLNode *prior;
}*DuLinkList;

Status initList(DuLinkList &L)
{
	L=(struct DuLNode*)malloc(sizeof(DuLNode));
	if(!L)
	{
		printf("双向链表空间创建失败!\n");
		exit(0);
	}
	L->next=NULL;
	L->prior=NULL;
	return OK;
}

Status createList(DuLinkList &L,int n)
{
	int  i;
	DuLinkList p,q;
	p=L;
	printf("双向链表中输入五个数据:\n");
	for(i=1;i<=n;i++)
	{
		q=(struct DuLNode *)malloc(sizeof(DuLNode));
		if(!q)
		{
         	printf("双向链表空间创建失败!\n");
		    exit(0);
		}
		scanf("%d",&q->data);
		q->next=NULL;
		q->prior=p;
		p->next=q;
		p=q;
	}
	return OK;
}
Status  showList(DuLinkList &L)
{
	DuLinkList p=L->next;
	while(p!=NULL)
	{
		printf("%d\t",p->data);
		p=p->next;
	}
	printf("\n");
	return OK;
}

Status deleteList(DuLinkList &L,int i,ElemType &e)
{
	int j=1;
	DuLinkList p;
    p=L;
	while(p&&j<=i)
	{
		p=p->next;
		++j;
	}
	if(!p&&j>i)
	{
		return ERROR;
	}
	printf("删除三号位置上的数据后的链表数据:\n");
	e=p->data;
	p->prior->next=p->next;
	p->next->prior=p->prior;
    free(p);
	return OK;
}

Status insertList(DuLinkList &L,int i,ElemType e)
{
	int j=1;
	DuLinkList p=L,s;
	while(p&&j<i)
	{
		p=p->next;
		++j;
	}
	if(!p&&j>i)
	{
		return ERROR;
	}
    printf("双向链表四号位置插入数据100:\n");
	if(!(s=(struct DuLNode *)malloc(sizeof(DuLNode))))
		return ERROR;
    s->data=e;
	s->prior=p->prior;
	p->prior->next=s;
	s->next=p;
	p->prior=s;
	return OK;
}
Status destory(DuLinkList &L)
{
	DuLinkList p=L;
	p->next=NULL;
	p->prior=NULL;
	while(p==NULL)
	{
		p=L->next;
		free(p);
		L->next=p;
	}
	return OK;
}
int main()
{
	DuLinkList L;
	int e;
	initList(L);
	createList(L,5);
	printf("输出双向链表中的全部数据:\n");
	showList(L);
	deleteList(L,3,e);
	showList(L);
	printf("删除的数据e=%d\n",e);
	insertList(L,4,100);
    showList(L);
	destory(L);
	showList(L);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135

运行结果如下图所示：

3.5 循环链表

（1）循环单链表

• 循环单链表和单链表的区别在于，表中最后一个结点的指针不是 null，而改为指向头结点，从而整个链表形成一个环，循环单链表示意图如下所示：
  
• 在循环单链表中，表尾结点 *r 的 next 域指向 L，故表中没有指针域为 null 的结点，因此，循环单链表的判空条件不是头结点的指针为空，而是它是否等于头指针。
• 在单链表中只能从表头结点开始往后顺序遍历整个链表，而循环单链表可以从表中的任意一个结点开始遍历整个链表。

（2）循环双链表

• 在循环单链表的基础之上，循环双链表中，头结点的 prior 指针还指向尾结点。循环双链表示意图如下所示：
  
• 在循环双链表 L 中，某结点 *p 为尾结点时，p->next==L；当循环双链表为空时，其头结点的 prior 域和 next 域都等于 L。

以循环单链表为例，其代码如下所示：

#include<stdio.h>
#include<stdlib.h>
#define OK 1;
#define ERROR 0;
typedef int Status;
typedef int ElemType;
typedef struct LNode
{
	ElemType data;
	struct LNode *next;
}*LinkList;

Status InputList(LinkList &L,int n)
{
	int i;
	LinkList p,q;
	L=(struct LNode *)malloc(sizeof(LNode));
	q=L;
    q->next=q;
	printf("输入五个数据进入循环链表中:\n");
	for(i=1;i<=n;i++)
	{
		p=(struct LNode *)malloc(sizeof(LNode));
		scanf("%d",&p->data);
		p->next=q->next;
		q->next=p;
	}	
	return OK;
}

Status printList(LinkList &L)
{	
	LinkList p=L->next;
	while(p!=L)
	{
	    printf("%d\t",p->data);
	    p=p->next;
	}
    printf("\n");
	return OK;
}

Status InsertList(LinkList &L,int i,ElemType e)
{
	int j=0;
	LinkList p,q;
	p=L;
	while(p&&j<i-1)
	{
		p=p->next;
		++j;
	}
	if(!p||j>i-1)
	{
		return ERROR;
	}
	printf("在循环链表的四号位置插入数据10:\n");
	q=(struct LNode *)malloc(sizeof(LNode));
    q->data=e;
	q->next=p->next;
	p->next=q;
	return OK;
}
Status deleteList(LinkList &L,int i,ElemType &e)
{
	int j=0;
	LinkList p,q;
    p=L;
	while(p->next&&j<i-1)
	{
		p=p->next;
		++j;
	}
	if(!p->next&&j>i-1)
	{
		return ERROR;
	}
	printf("删除循环链表二号位置的元素:\n");
	q=p->next;
	p->next=q->next;
	e=q->data;
    free(q);
	return OK;
}
Status destoryList(LinkList &L)
{
	LinkList p;
	p=L;
	p->next=NULL;
	while(p==NULL)
	{
		p=L->next;
		free(p);
		L->next=p;
	}
	return OK;
}
int main()
{
	int e;
	LinkList L;
	InputList(L,5);
    printf("输出循环链表中的全部数据:\n");
	printList(L);
	InsertList(L,4,10);
	printList(L);
	deleteList(L,2,e);
	printList(L);
	printf("被删除的元素e=%d\n",e);
	destoryList(L);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

运行结果如下图所示：