线性表

87 阅读 0 评论 58 点赞

我是靠谱客的博主苹果大象，这篇文章主要介绍线性表，现在分享给大家，希望可以做个参考。

线性表(List):零个或多个数据元素的有限序列。

线性表的抽象定义:

线性表的顺序存储结构:用一段地址连续的存储单元依次存储线性表的数据元素。

复制代码

#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int Status;
/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;
/* ElemType类型根据实际情况而定，这里假设为int */
Status visit(ElemType c)
{
printf("%d ",c);
return OK;
}
typedef struct
{
ElemType data[MAXSIZE];
/* 数组，存储数据元素 */
int length;
/* 线性表当前长度 */
}SqList;
/* 初始化顺序线性表 */
Status InitList(SqList *L)
{
L->length=0;
return OK;
}
/* 初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */
Status ListEmpty(SqList L)
{
if(L.length==0)
return TRUE;
else
return FALSE;
}
/* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
Status ClearList(SqList *L)
{
L->length=0;
return OK;
}
/* 初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数 */
int ListLength(SqList L)
{
return L.length;
}
/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：用e返回L中第i个数据元素的值,注意i是指位置，第1个位置的数组是从0开始 */
Status GetElem(SqList L,int i,ElemType *e)
{
if(L.length==0 || i<1 || i>L.length)
return ERROR;
*e=L.data[i-1];
return OK;
}
/* 初始条件：顺序线性表L已存在 */
/* 操作结果：返回L中第1个与e满足关系的数据元素的位序。 */
/* 若这样的数据元素不存在，则返回值为0 */
int LocateElem(SqList L,ElemType e)
{
int i;
if (L.length==0)
return 0;
for(i=0;i<L.length;i++)
{
if (L.data[i]==e)
break;
}
if(i>=L.length)
return 0;
return i+1;
}
/* 初始条件：顺序线性表L已存在,1≤i≤ListLength(L)， */
/* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */
Status ListInsert(SqList *L,int i,ElemType e)
{
int k;
if (L->length==MAXSIZE)
/* 顺序线性表已经满 */
return ERROR;
if (i<1 || i>L->length+1)/* 当i比第一位置小或者比最后一位置后一位置还要大时 */
return ERROR;
if (i<=L->length)
/* 若插入数据位置不在表尾 */
{
for(k=L->length-1;k>=i-1;k--)
/* 将要插入位置之后的数据元素向后移动一位 */
L->data[k+1]=L->data[k];
}
L->data[i-1]=e;
/* 将新元素插入 */
L->length++;
return OK;
}
/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */
Status ListDelete(SqList *L,int i,ElemType *e)
{
int k;
if (L->length==0)
/* 线性表为空 */
return ERROR;
if (i<1 || i>L->length)
/* 删除位置不正确 */
return ERROR;
*e=L->data[i-1];
if (i<L->length)
/* 如果删除不是最后位置 */
{
for(k=i;k<L->length;k++)/* 将删除位置后继元素前移 */
L->data[k-1]=L->data[k];
}
L->length--;
return OK;
}
/* 初始条件：顺序线性表L已存在 */
/* 操作结果：依次对L的每个数据元素输出 */
Status ListTraverse(SqList L)
{
int i;
for(i=0;i<L.length;i++)
visit(L.data[i]);
printf("n");
return OK;
}
void unionL(SqList *La,SqList Lb)
{
int La_len,Lb_len,i;
ElemType e;
La_len=ListLength(*La);
Lb_len=ListLength(Lb);
for (i=1;i<=Lb_len;i++)
{
GetElem(Lb,i,&e);
if (!LocateElem(*La,e))
ListInsert(La,++La_len,e);
}
}
int main()
{
SqList L;
ElemType e;
Status i;
int j,k;
i=InitList(&L);
printf("初始化L后：L.length=%dn",L.length);
for(j=1;j<=5;j++)
i=ListInsert(&L,1,j);
printf("在L的表头依次插入1～5后：L.data=");
ListTraverse(L);
printf("L.length=%d n",L.length);
i=ListEmpty(L);
printf("L是否空：i=%d(1:是 0:否)n",i);
i=ClearList(&L);
printf("清空L后：L.length=%dn",L.length);
i=ListEmpty(L);
printf("L是否空：i=%d(1:是 0:否)n",i);
for(j=1;j<=10;j++)
ListInsert(&L,j,j);
printf("在L的表尾依次插入1～10后：L.data=");
ListTraverse(L);
printf("L.length=%d n",L.length);
ListInsert(&L,1,0);
printf("在L的表头插入0后：L.data=");
ListTraverse(L);
printf("L.length=%d n",L.length);
GetElem(L,5,&e);
printf("第5个元素的值为：%dn",e);
for(j=3;j<=4;j++)
{
k=LocateElem(L,j);
if(k)
printf("第%d个元素的值为%dn",k,j);
else
printf("没有值为%d的元素n",j);
}
k=ListLength(L); /* k为表长 */
for(j=k+1;j>=k;j--)
{
i=ListDelete(&L,j,&e); /* 删除第j个数据 */
if(i==ERROR)
printf("删除第%d个数据失败n",j);
else
printf("删除第%d个的元素值为：%dn",j,e);
}
printf("依次输出L的元素：");
ListTraverse(L);
j=5;
ListDelete(&L,j,&e); /* 删除第5个数据 */
printf("删除第%d个的元素值为：%dn",j,e);
printf("依次输出L的元素：");
ListTraverse(L);
//构造一个有10个数的Lb
SqList Lb;
i=InitList(&Lb);
for(j=6;j<=15;j++)
i=ListInsert(&Lb,1,j);
unionL(&L,Lb);
printf("依次输出合并了Lb的L的元素：");
ListTraverse(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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int Status;
/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;
/* ElemType类型根据实际情况而定，这里假设为int */
Status visit(ElemType c)
{
printf("%d ",c);
return OK;
}
typedef struct
{
ElemType data[MAXSIZE];
/* 数组，存储数据元素 */
int length;
/* 线性表当前长度 */
}SqList;
/* 初始化顺序线性表 */
Status InitList(SqList *L)
{
L->length=0;
return OK;
}
/* 初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */
Status ListEmpty(SqList L)
{
if(L.length==0)
return TRUE;
else
return FALSE;
}
/* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
Status ClearList(SqList *L)
{
L->length=0;
return OK;
}
/* 初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数 */
int ListLength(SqList L)
{
return L.length;
}
/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：用e返回L中第i个数据元素的值,注意i是指位置，第1个位置的数组是从0开始 */
Status GetElem(SqList L,int i,ElemType *e)
{
if(L.length==0 || i<1 || i>L.length)
return ERROR;
*e=L.data[i-1];
return OK;
}
/* 初始条件：顺序线性表L已存在 */
/* 操作结果：返回L中第1个与e满足关系的数据元素的位序。 */
/* 若这样的数据元素不存在，则返回值为0 */
int LocateElem(SqList L,ElemType e)
{
int i;
if (L.length==0)
return 0;
for(i=0;i<L.length;i++)
{
if (L.data[i]==e)
break;
}
if(i>=L.length)
return 0;
return i+1;
}
/* 初始条件：顺序线性表L已存在,1≤i≤ListLength(L)， */
/* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */
Status ListInsert(SqList *L,int i,ElemType e)
{
int k;
if (L->length==MAXSIZE)
/* 顺序线性表已经满 */
return ERROR;
if (i<1 || i>L->length+1)/* 当i比第一位置小或者比最后一位置后一位置还要大时 */
return ERROR;
if (i<=L->length)
/* 若插入数据位置不在表尾 */
{
for(k=L->length-1;k>=i-1;k--)
/* 将要插入位置之后的数据元素向后移动一位 */
L->data[k+1]=L->data[k];
}
L->data[i-1]=e;
/* 将新元素插入 */
L->length++;
return OK;
}
/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */
Status ListDelete(SqList *L,int i,ElemType *e)
{
int k;
if (L->length==0)
/* 线性表为空 */
return ERROR;
if (i<1 || i>L->length)
/* 删除位置不正确 */
return ERROR;
*e=L->data[i-1];
if (i<L->length)
/* 如果删除不是最后位置 */
{
for(k=i;k<L->length;k++)/* 将删除位置后继元素前移 */
L->data[k-1]=L->data[k];
}
L->length--;
return OK;
}
/* 初始条件：顺序线性表L已存在 */
/* 操作结果：依次对L的每个数据元素输出 */
Status ListTraverse(SqList L)
{
int i;
for(i=0;i<L.length;i++)
visit(L.data[i]);
printf("n");
return OK;
}
void unionL(SqList *La,SqList Lb)
{
int La_len,Lb_len,i;
ElemType e;
La_len=ListLength(*La);
Lb_len=ListLength(Lb);
for (i=1;i<=Lb_len;i++)
{
GetElem(Lb,i,&e);
if (!LocateElem(*La,e))
ListInsert(La,++La_len,e);
}
}
int main()
{
SqList L;
ElemType e;
Status i;
int j,k;
i=InitList(&L);
printf("初始化L后：L.length=%dn",L.length);
for(j=1;j<=5;j++)
i=ListInsert(&L,1,j);
printf("在L的表头依次插入1～5后：L.data=");
ListTraverse(L);
printf("L.length=%d n",L.length);
i=ListEmpty(L);
printf("L是否空：i=%d(1:是 0:否)n",i);
i=ClearList(&L);
printf("清空L后：L.length=%dn",L.length);
i=ListEmpty(L);
printf("L是否空：i=%d(1:是 0:否)n",i);
for(j=1;j<=10;j++)
ListInsert(&L,j,j);
printf("在L的表尾依次插入1～10后：L.data=");
ListTraverse(L);
printf("L.length=%d n",L.length);
ListInsert(&L,1,0);
printf("在L的表头插入0后：L.data=");
ListTraverse(L);
printf("L.length=%d n",L.length);
GetElem(L,5,&e);
printf("第5个元素的值为：%dn",e);
for(j=3;j<=4;j++)
{
k=LocateElem(L,j);
if(k)
printf("第%d个元素的值为%dn",k,j);
else
printf("没有值为%d的元素n",j);
}
k=ListLength(L); /* k为表长 */
for(j=k+1;j>=k;j--)
{
i=ListDelete(&L,j,&e); /* 删除第j个数据 */
if(i==ERROR)
printf("删除第%d个数据失败n",j);
else
printf("删除第%d个的元素值为：%dn",j,e);
}
printf("依次输出L的元素：");
ListTraverse(L);
j=5;
ListDelete(&L,j,&e); /* 删除第5个数据 */
printf("删除第%d个的元素值为：%dn",j,e);
printf("依次输出L的元素：");
ListTraverse(L);
//构造一个有10个数的Lb
SqList Lb;
i=InitList(&Lb);
for(j=6;j<=15;j++)
i=ListInsert(&Lb,1,j);
unionL(&L,Lb);
printf("依次输出合并了Lb的L的元素：");
ListTraverse(L);
return 0;
}

线性表的链式存储结构:用一组任意的存储单元存储线性表的元素(存储数据和索引)

复制代码

#include "stdio.h"
#include "string.h"
#include "ctype.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */
Status visit(ElemType c)
{
printf("%d ",c);
return OK;
}
typedef struct Node
{
ElemType data;
struct Node *next;
}Node;
typedef struct Node *LinkList; /* 定义LinkList */
/* 初始化顺序线性表 */
Status InitList(LinkList *L)
{
*L=(LinkList)malloc(sizeof(Node)); /* 产生头结点,并使L指向此头结点 */
if(!(*L)) /* 存储分配失败 */
return ERROR;
(*L)->next=NULL; /* 指针域为空 */
return OK;
}
/* 初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */
Status ListEmpty(LinkList L)
{
if(L->next)
return FALSE;
else
return TRUE;
}
/* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
Status ClearList(LinkList *L)
{
LinkList p,q;
p=(*L)->next;
/*
p指向第一个结点 */
while(p)
/*
没到表尾 */
{
q=p->next;
free(p);
p=q;
}
(*L)->next=NULL;
/* 头结点指针域为空 */
return OK;
}
/* 初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数 */
int ListLength(LinkList L)
{
int i=0;
LinkList p=L->next; /* p指向第一个结点 */
while(p)
{
i++;
p=p->next;
}
return i;
}
/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：用e返回L中第i个数据元素的值 */
Status GetElem(LinkList L,int i,ElemType *e)
{
int j;
LinkList p;
/* 声明一结点p */
p = L->next;
/* 让p指向链表L的第一个结点 */
j = 1;
/*
j为计数器 */
while (p && j<i)
/* p不为空或者计数器j还没有等于i时，循环继续 */
{
p = p->next;
/* 让p指向下一个结点 */
++j;
}
if ( !p || j>i )
return ERROR;
/*
第i个元素不存在 */
*e = p->data;
/*
取第i个元素的数据 */
return OK;
}
/* 初始条件：顺序线性表L已存在 */
/* 操作结果：返回L中第1个与e满足关系的数据元素的位序。 */
/* 若这样的数据元素不存在，则返回值为0 */
int LocateElem(LinkList L,ElemType e)
{
int i=0;
LinkList p=L->next;
while(p)
{
i++;
if(p->data==e) /* 找到这样的数据元素 */
return i;
p=p->next;
}
return 0;
}
/* 初始条件：顺序线性表L已存在,1≤i≤ListLength(L)， */
/* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */
Status ListInsert(LinkList *L,int i,ElemType e)
{
int j;
LinkList p,s;
p = *L;
j = 1;
while (p && j < i)
/* 寻找第i个结点 */
{
p = p->next;
++j;
}
if (!p || j > i)
return ERROR;
/* 第i个元素不存在 */
s = (LinkList)malloc(sizeof(Node));
/*
生成新结点(C语言标准函数) */
s->data = e;
s->next = p->next;
/* 将p的后继结点赋值给s的后继
*/
p->next = s;
/* 将s赋值给p的后继 */
return OK;
}
/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */
Status ListDelete(LinkList *L,int i,ElemType *e)
{
int j;
LinkList p,q;
p = *L;
j = 1;
while (p->next && j < i)	/* 遍历寻找第i个元素 */
{
p = p->next;
++j;
}
if (!(p->next) || j > i)
return ERROR;
/* 第i个元素不存在 */
q = p->next;
p->next = q->next;
/* 将q的后继赋值给p的后继 */
*e = q->data;
/* 将q结点中的数据给e */
free(q);
/* 让系统回收此结点，释放内存 */
return OK;
}
/* 初始条件：顺序线性表L已存在 */
/* 操作结果：依次对L的每个数据元素输出 */
Status ListTraverse(LinkList L)
{
LinkList p=L->next;
while(p)
{
visit(p->data);
p=p->next;
}
printf("n");
return OK;
}
/*
随机产生n个元素的值，建立带表头结点的单链线性表L（头插法） */
void CreateListHead(LinkList *L, int n)
{
LinkList p;
int i;
srand(time(0));
/* 初始化随机数种子 */
*L = (LinkList)malloc(sizeof(Node));
(*L)->next = NULL;
/*
先建立一个带头结点的单链表 */
for (i=0; i<n; i++)
{
p = (LinkList)malloc(sizeof(Node)); /*
生成新结点 */
p->data = rand()%100+1;
/*
随机生成100以内的数字 */
p->next = (*L)->next;
(*L)->next = p;
/*
插入到表头 */
}
}
/*
随机产生n个元素的值，建立带表头结点的单链线性表L（尾插法） */
void CreateListTail(LinkList *L, int n)
{
LinkList p,r;
int i;
srand(time(0));
/* 初始化随机数种子 */
*L = (LinkList)malloc(sizeof(Node)); /* L为整个线性表 */
r=*L;
/* r为指向尾部的结点 */
for (i=0; i<n; i++)
{
p = (Node *)malloc(sizeof(Node)); /*
生成新结点 */
p->data = rand()%100+1;
/*
随机生成100以内的数字 */
r->next=p;
/* 将表尾终端结点的指针指向新结点 */
r = p;
/* 将当前的新结点定义为表尾终端结点 */
}
r->next = NULL;
/* 表示当前链表结束 */
}
int main()
{
LinkList L;
ElemType e;
Status i;
int j,k;
i=InitList(&L);
printf("初始化L后：ListLength(L)=%dn",ListLength(L));
for(j=1;j<=5;j++)
i=ListInsert(&L,1,j);
printf("在L的表头依次插入1～5后：L.data=");
ListTraverse(L);
printf("ListLength(L)=%d n",ListLength(L));
i=ListEmpty(L);
printf("L是否空：i=%d(1:是 0:否)n",i);
i=ClearList(&L);
printf("清空L后：ListLength(L)=%dn",ListLength(L));
i=ListEmpty(L);
printf("L是否空：i=%d(1:是 0:否)n",i);
for(j=1;j<=10;j++)
ListInsert(&L,j,j);
printf("在L的表尾依次插入1～10后：L.data=");
ListTraverse(L);
printf("ListLength(L)=%d n",ListLength(L));
ListInsert(&L,1,0);
printf("在L的表头插入0后：L.data=");
ListTraverse(L);
printf("ListLength(L)=%d n",ListLength(L));
GetElem(L,5,&e);
printf("第5个元素的值为：%dn",e);
for(j=3;j<=4;j++)
{
k=LocateElem(L,j);
if(k)
printf("第%d个元素的值为%dn",k,j);
else
printf("没有值为%d的元素n",j);
}
k=ListLength(L); /* k为表长 */
for(j=k+1;j>=k;j--)
{
i=ListDelete(&L,j,&e); /* 删除第j个数据 */
if(i==ERROR)
printf("删除第%d个数据失败n",j);
else
printf("删除第%d个的元素值为：%dn",j,e);
}
printf("依次输出L的元素：");
ListTraverse(L);
j=5;
ListDelete(&L,j,&e); /* 删除第5个数据 */
printf("删除第%d个的元素值为：%dn",j,e);
printf("依次输出L的元素：");
ListTraverse(L);
i=ClearList(&L);
printf("n清空L后：ListLength(L)=%dn",ListLength(L));
CreateListHead(&L,20);
printf("整体创建L的元素(头插法)：");
ListTraverse(L);
i=ClearList(&L);
printf("n删除L后：ListLength(L)=%dn",ListLength(L));
CreateListTail(&L,20);
printf("整体创建L的元素(尾插法)：");
ListTraverse(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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
#include "stdio.h"
#include "string.h"
#include "ctype.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */
Status visit(ElemType c)
{
printf("%d ",c);
return OK;
}
typedef struct Node
{
ElemType data;
struct Node *next;
}Node;
typedef struct Node *LinkList; /* 定义LinkList */
/* 初始化顺序线性表 */
Status InitList(LinkList *L)
{
*L=(LinkList)malloc(sizeof(Node)); /* 产生头结点,并使L指向此头结点 */
if(!(*L)) /* 存储分配失败 */
return ERROR;
(*L)->next=NULL; /* 指针域为空 */
return OK;
}
/* 初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */
Status ListEmpty(LinkList L)
{
if(L->next)
return FALSE;
else
return TRUE;
}
/* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
Status ClearList(LinkList *L)
{
LinkList p,q;
p=(*L)->next;
/*
p指向第一个结点 */
while(p)
/*
没到表尾 */
{
q=p->next;
free(p);
p=q;
}
(*L)->next=NULL;
/* 头结点指针域为空 */
return OK;
}
/* 初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数 */
int ListLength(LinkList L)
{
int i=0;
LinkList p=L->next; /* p指向第一个结点 */
while(p)
{
i++;
p=p->next;
}
return i;
}
/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：用e返回L中第i个数据元素的值 */
Status GetElem(LinkList L,int i,ElemType *e)
{
int j;
LinkList p;
/* 声明一结点p */
p = L->next;
/* 让p指向链表L的第一个结点 */
j = 1;
/*
j为计数器 */
while (p && j<i)
/* p不为空或者计数器j还没有等于i时，循环继续 */
{
p = p->next;
/* 让p指向下一个结点 */
++j;
}
if ( !p || j>i )
return ERROR;
/*
第i个元素不存在 */
*e = p->data;
/*
取第i个元素的数据 */
return OK;
}
/* 初始条件：顺序线性表L已存在 */
/* 操作结果：返回L中第1个与e满足关系的数据元素的位序。 */
/* 若这样的数据元素不存在，则返回值为0 */
int LocateElem(LinkList L,ElemType e)
{
int i=0;
LinkList p=L->next;
while(p)
{
i++;
if(p->data==e) /* 找到这样的数据元素 */
return i;
p=p->next;
}
return 0;
}
/* 初始条件：顺序线性表L已存在,1≤i≤ListLength(L)， */
/* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */
Status ListInsert(LinkList *L,int i,ElemType e)
{
int j;
LinkList p,s;
p = *L;
j = 1;
while (p && j < i)
/* 寻找第i个结点 */
{
p = p->next;
++j;
}
if (!p || j > i)
return ERROR;
/* 第i个元素不存在 */
s = (LinkList)malloc(sizeof(Node));
/*
生成新结点(C语言标准函数) */
s->data = e;
s->next = p->next;
/* 将p的后继结点赋值给s的后继
*/
p->next = s;
/* 将s赋值给p的后继 */
return OK;
}
/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */
Status ListDelete(LinkList *L,int i,ElemType *e)
{
int j;
LinkList p,q;
p = *L;
j = 1;
while (p->next && j < i)	/* 遍历寻找第i个元素 */
{
p = p->next;
++j;
}
if (!(p->next) || j > i)
return ERROR;
/* 第i个元素不存在 */
q = p->next;
p->next = q->next;
/* 将q的后继赋值给p的后继 */
*e = q->data;
/* 将q结点中的数据给e */
free(q);
/* 让系统回收此结点，释放内存 */
return OK;
}
/* 初始条件：顺序线性表L已存在 */
/* 操作结果：依次对L的每个数据元素输出 */
Status ListTraverse(LinkList L)
{
LinkList p=L->next;
while(p)
{
visit(p->data);
p=p->next;
}
printf("n");
return OK;
}
/*
随机产生n个元素的值，建立带表头结点的单链线性表L（头插法） */
void CreateListHead(LinkList *L, int n)
{
LinkList p;
int i;
srand(time(0));
/* 初始化随机数种子 */
*L = (LinkList)malloc(sizeof(Node));
(*L)->next = NULL;
/*
先建立一个带头结点的单链表 */
for (i=0; i<n; i++)
{
p = (LinkList)malloc(sizeof(Node)); /*
生成新结点 */
p->data = rand()%100+1;
/*
随机生成100以内的数字 */
p->next = (*L)->next;
(*L)->next = p;
/*
插入到表头 */
}
}
/*
随机产生n个元素的值，建立带表头结点的单链线性表L（尾插法） */
void CreateListTail(LinkList *L, int n)
{
LinkList p,r;
int i;
srand(time(0));
/* 初始化随机数种子 */
*L = (LinkList)malloc(sizeof(Node)); /* L为整个线性表 */
r=*L;
/* r为指向尾部的结点 */
for (i=0; i<n; i++)
{
p = (Node *)malloc(sizeof(Node)); /*
生成新结点 */
p->data = rand()%100+1;
/*
随机生成100以内的数字 */
r->next=p;
/* 将表尾终端结点的指针指向新结点 */
r = p;
/* 将当前的新结点定义为表尾终端结点 */
}
r->next = NULL;
/* 表示当前链表结束 */
}
int main()
{
LinkList L;
ElemType e;
Status i;
int j,k;
i=InitList(&L);
printf("初始化L后：ListLength(L)=%dn",ListLength(L));
for(j=1;j<=5;j++)
i=ListInsert(&L,1,j);
printf("在L的表头依次插入1～5后：L.data=");
ListTraverse(L);
printf("ListLength(L)=%d n",ListLength(L));
i=ListEmpty(L);
printf("L是否空：i=%d(1:是 0:否)n",i);
i=ClearList(&L);
printf("清空L后：ListLength(L)=%dn",ListLength(L));
i=ListEmpty(L);
printf("L是否空：i=%d(1:是 0:否)n",i);
for(j=1;j<=10;j++)
ListInsert(&L,j,j);
printf("在L的表尾依次插入1～10后：L.data=");
ListTraverse(L);
printf("ListLength(L)=%d n",ListLength(L));
ListInsert(&L,1,0);
printf("在L的表头插入0后：L.data=");
ListTraverse(L);
printf("ListLength(L)=%d n",ListLength(L));
GetElem(L,5,&e);
printf("第5个元素的值为：%dn",e);
for(j=3;j<=4;j++)
{
k=LocateElem(L,j);
if(k)
printf("第%d个元素的值为%dn",k,j);
else
printf("没有值为%d的元素n",j);
}
k=ListLength(L); /* k为表长 */
for(j=k+1;j>=k;j--)
{
i=ListDelete(&L,j,&e); /* 删除第j个数据 */
if(i==ERROR)
printf("删除第%d个数据失败n",j);
else
printf("删除第%d个的元素值为：%dn",j,e);
}
printf("依次输出L的元素：");
ListTraverse(L);
j=5;
ListDelete(&L,j,&e); /* 删除第5个数据 */
printf("删除第%d个的元素值为：%dn",j,e);
printf("依次输出L的元素：");
ListTraverse(L);
i=ClearList(&L);
printf("n清空L后：ListLength(L)=%dn",ListLength(L));
CreateListHead(&L,20);
printf("整体创建L的元素(头插法)：");
ListTraverse(L);
i=ClearList(&L);
printf("n删除L后：ListLength(L)=%dn",ListLength(L));
CreateListTail(&L,20);
printf("整体创建L的元素(尾插法)：");
ListTraverse(L);
return 0;
}

(1)单链表

(2)静态链表:用数组描述的链表

复制代码

#include "string.h"
#include "ctype.h"
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 1000 /* 存储空间初始分配量 */
typedef int Status;
/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef char ElemType;
/* ElemType类型根据实际情况而定，这里假设为char */
Status visit(ElemType c)
{
printf("%c ",c);
return OK;
}
/* 线性表的静态链表存储结构 */
typedef struct
{
ElemType data;
int cur;
/* 游标(Cursor) ，为0时表示无指向 */
} Component,StaticLinkList[MAXSIZE];
/* 将一维数组space中各分量链成一个备用链表，space[0].cur为头指针，"0"表示空指针 */
Status InitList(StaticLinkList space)
{
int i;
for (i=0; i<MAXSIZE-1; i++)
space[i].cur = i+1;
space[MAXSIZE-1].cur = 0; /* 目前静态链表为空，最后一个元素的cur为0 */
return OK;
}
/* 若备用空间链表非空，则返回分配的结点下标，否则返回0 */
int Malloc_SSL(StaticLinkList space)
{
int i = space[0].cur;
/* 当前数组第一个元素的cur存的值 */
/* 就是要返回的第一个备用空闲的下标 */
if (space[0]. cur)
space[0]. cur = space[i].cur;
/* 由于要拿出一个分量来使用了， */
/* 所以我们就得把它的下一个 */
/* 分量用来做备用 */
return i;
}
/*
将下标为k的空闲结点回收到备用链表 */
void Free_SSL(StaticLinkList space, int k)
{
space[k].cur = space[0].cur;
/* 把第一个元素的cur值赋给要删除的分量cur */
space[0].cur = k;
/* 把要删除的分量下标赋值给第一个元素的cur */
}
/* 初始条件：静态链表L已存在。操作结果：返回L中数据元素个数 */
int ListLength(StaticLinkList L)
{
int j=0;
int i=L[MAXSIZE-1].cur;
while(i)
{
i=L[i].cur;
j++;
}
return j;
}
/*
在L中第i个元素之前插入新的数据元素e
*/
Status ListInsert(StaticLinkList L, int i, ElemType e)
{
int j, k, l;
k = MAXSIZE - 1;
/* 注意k首先是最后一个元素的下标 */
if (i < 1 || i > ListLength(L) + 1)
return ERROR;
j = Malloc_SSL(L);
/* 获得空闲分量的下标 */
if (j)
{
L[j].data = e;
/* 将数据赋值给此分量的data */
for(l = 1; l <= i - 1; l++)
/* 找到第i个元素之前的位置 */
k = L[k].cur;
L[j].cur = L[k].cur;
/* 把第i个元素之前的cur赋值给新元素的cur */
L[k].cur = j;
/* 把新元素的下标赋值给第i个元素之前元素的ur */
return OK;
}
return ERROR;
}
/*
删除在L中第i个数据元素
*/
Status ListDelete(StaticLinkList L, int i)
{
int j, k;
if (i < 1 || i > ListLength(L))
return ERROR;
k = MAXSIZE - 1;
for (j = 1; j <= i - 1; j++)
k = L[k].cur;
j = L[k].cur;
L[k].cur = L[j].cur;
Free_SSL(L, j);
return OK;
}
Status ListTraverse(StaticLinkList L)
{
int j=0;
int i=L[MAXSIZE-1].cur;
while(i)
{
visit(L[i].data);
i=L[i].cur;
j++;
}
return j;
printf("n");
return OK;
}
int main()
{
StaticLinkList L;
Status i;
i=InitList(L);
printf("初始化L后：L.length=%dn",ListLength(L));
i=ListInsert(L,1,'F');
i=ListInsert(L,1,'E');
i=ListInsert(L,1,'D');
i=ListInsert(L,1,'B');
i=ListInsert(L,1,'A');
printf("n在L的表头依次插入FEDBA后：nL.data=");
ListTraverse(L);
i=ListInsert(L,3,'C');
printf("n在L的“B”与“D”之间插入“C”后：nL.data=");
ListTraverse(L);
i=ListDelete(L,1);
printf("n在L的删除“A”后：nL.data=");
ListTraverse(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
144
145
146
147
148
149
150
151
#include "string.h"
#include "ctype.h"
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 1000 /* 存储空间初始分配量 */
typedef int Status;
/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef char ElemType;
/* ElemType类型根据实际情况而定，这里假设为char */
Status visit(ElemType c)
{
printf("%c ",c);
return OK;
}
/* 线性表的静态链表存储结构 */
typedef struct
{
ElemType data;
int cur;
/* 游标(Cursor) ，为0时表示无指向 */
} Component,StaticLinkList[MAXSIZE];
/* 将一维数组space中各分量链成一个备用链表，space[0].cur为头指针，"0"表示空指针 */
Status InitList(StaticLinkList space)
{
int i;
for (i=0; i<MAXSIZE-1; i++)
space[i].cur = i+1;
space[MAXSIZE-1].cur = 0; /* 目前静态链表为空，最后一个元素的cur为0 */
return OK;
}
/* 若备用空间链表非空，则返回分配的结点下标，否则返回0 */
int Malloc_SSL(StaticLinkList space)
{
int i = space[0].cur;
/* 当前数组第一个元素的cur存的值 */
/* 就是要返回的第一个备用空闲的下标 */
if (space[0]. cur)
space[0]. cur = space[i].cur;
/* 由于要拿出一个分量来使用了， */
/* 所以我们就得把它的下一个 */
/* 分量用来做备用 */
return i;
}
/*
将下标为k的空闲结点回收到备用链表 */
void Free_SSL(StaticLinkList space, int k)
{
space[k].cur = space[0].cur;
/* 把第一个元素的cur值赋给要删除的分量cur */
space[0].cur = k;
/* 把要删除的分量下标赋值给第一个元素的cur */
}
/* 初始条件：静态链表L已存在。操作结果：返回L中数据元素个数 */
int ListLength(StaticLinkList L)
{
int j=0;
int i=L[MAXSIZE-1].cur;
while(i)
{
i=L[i].cur;
j++;
}
return j;
}
/*
在L中第i个元素之前插入新的数据元素e
*/
Status ListInsert(StaticLinkList L, int i, ElemType e)
{
int j, k, l;
k = MAXSIZE - 1;
/* 注意k首先是最后一个元素的下标 */
if (i < 1 || i > ListLength(L) + 1)
return ERROR;
j = Malloc_SSL(L);
/* 获得空闲分量的下标 */
if (j)
{
L[j].data = e;
/* 将数据赋值给此分量的data */
for(l = 1; l <= i - 1; l++)
/* 找到第i个元素之前的位置 */
k = L[k].cur;
L[j].cur = L[k].cur;
/* 把第i个元素之前的cur赋值给新元素的cur */
L[k].cur = j;
/* 把新元素的下标赋值给第i个元素之前元素的ur */
return OK;
}
return ERROR;
}
/*
删除在L中第i个数据元素
*/
Status ListDelete(StaticLinkList L, int i)
{
int j, k;
if (i < 1 || i > ListLength(L))
return ERROR;
k = MAXSIZE - 1;
for (j = 1; j <= i - 1; j++)
k = L[k].cur;
j = L[k].cur;
L[k].cur = L[j].cur;
Free_SSL(L, j);
return OK;
}
Status ListTraverse(StaticLinkList L)
{
int j=0;
int i=L[MAXSIZE-1].cur;
while(i)
{
visit(L[i].data);
i=L[i].cur;
j++;
}
return j;
printf("n");
return OK;
}
int main()
{
StaticLinkList L;
Status i;
i=InitList(L);
printf("初始化L后：L.length=%dn",ListLength(L));
i=ListInsert(L,1,'F');
i=ListInsert(L,1,'E');
i=ListInsert(L,1,'D');
i=ListInsert(L,1,'B');
i=ListInsert(L,1,'A');
printf("n在L的表头依次插入FEDBA后：nL.data=");
ListTraverse(L);
i=ListInsert(L,3,'C');
printf("n在L的“B”与“D”之间插入“C”后：nL.data=");
ListTraverse(L);
i=ListDelete(L,1);
printf("n在L的删除“A”后：nL.data=");
ListTraverse(L);
printf("n");
return 0;
}