DataStruct in c(一)linked list

链表

数组和链表都属于线性表结构。对于大部分有变成经验的人来说数组可能再熟悉不过了,大部分工作用都数组可以用数组完成。但使用数组时需要对表大小进行估计并指定长度(对于c应该是这样的,不包括C99的变长数组)。通常那一准确估计表的大小造成空间的浪费等问题。

链表与数组不同的是链表是一种链式存储结构。而数组在内存中是顺序存储的。如图

链表结构体有两个部分,分别是存放元素的值和指向下一节点的指针,可以用使用c中的结构体来表示。

1
2
3
4
5
6
typedef struct Node *Position;

struct Node{ //每一节点中 element 代表存放的内容,next 指针指向下一节点
ElementType element;
Position next;
};

其次,在对线性表的进行 插入,删除,打印等操作时,选择数组或链表的时间复杂度也是不同的。由于数组的顺序存储,在插入或删除元素时需要对数组内的元素整体进行移动,但由于数组可以直接通过下标进行索引,所以读取非常方便。而链表的链式存储决定了链表在插入和删除元素时比数组要更方便,但读取时则需要线性时间。

数组 链表
读取 O(1) O(N)
插入 O(N) O(1)
删除 O(N) O(1)

C中链表的实现

  • List.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
#include <stdlib.h>

typedef struct Node *Position;
typedef Position List;
typedef int ElementType;

struct Node{
ElementType element;
Position next;
};

List makeEmpty ();
List createL ();
Position find (List L, ElementType E);
void insert (List L, ElementType pre, ElementType e);
Position findPre (List L, ElementType E);
void del (List L, ElementType E);
void printL (List L);
void destoryL (List L);
  • List.c
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
#include "List.h"

int main ()
{
List L = createL();
printL(L);
return 0;
}

//init header
List makeEmpty ()
{
List L = (List) malloc( sizeof(struct Node) );

// 检查内存分配是否失败
if(L == NULL){
printf("can\'t allocate region");
exit(1);
}

L->next = NULL;
return L;
}

// init List
List createL ()
{
List L = makeEmpty();
Position tail = L;

printf("input some integer into List in turn: (q to quit) \n");

while(1){ //尾插法,可以保证依序插入链表
Position P = (Position) malloc ( sizeof(struct Node) );

if(scanf("%d", &(P->element)) == 0)
break;

P->next = NULL;
tail->next = P;
tail = P;
}

return L;
}

//查找 List 中的某一元素,返回该处的 Position
//未找到时返回 NULL
Position find (List L, ElementType E)
{
Position P = L->next;

while(P->element != E)
if(P->next == NULL)
return NULL;
else
P = P->next;

return P;
}

//insert函数, 将 e 插入 pre 之后
void insert (List L, ElementType pre, ElementType e)
{
Position PtrToPre = find(L, pre);

if(PtrToPre == NULL){
printf("can\'t find pre\n"); return;
}

Position TmpPtr = (Position) malloc ( sizeof(struct Node) );
TmpPtr->element = e;
TmpPtr->next = PtrToPre->next;
PtrToPre->next = TmpPtr;
}

//与 find() 方法同理,返回的是前置元素的 Position,配合 del() 函数
//未找到返回 NULL
Position findPre (List L, ElementType E)
{
Position P = L->next;

while(P->next->element != E)
if(P->next->next == NULL)
return NULL;
else
P = P->next;

return P;
}

//del 函数删除 值为e的元素
void del (List L, ElementType E)
{
Position PtrToPre = findPre(L, E);

if(PtrToPre == NULL){
printf("can\'t find pre\n"); return;
}

Position TmpN = PtrToPre->next;
PtrToPre->next = PtrToPre->next->next;
free(TmpN);
}

void printL (List L)
{
Position P = L->next;

while(P != NULL){
printf("%d->", P->element);
P = P->next;
}
printf("\n");
}

关于链表实现时的一些问题

在实现链表时,个人感觉最难的一部分便是 createL() 方法的实现。网上很多代码依然是先让用户输入表的长度 length 再用 for 循环 length 次来读入数据。但可以根据 scanf() 函数的返回值来判断元素读取是否成功,进而实现读入不确定的数目,再通过任意的英文字符如 q 来跳出 while 循环。

其次是 createL() 方法中可以使用 头插法尾插法 来将元素依次插入链表中。尾插法即将元素按照顺序一次插入尾部,该方法需要一个辅助变量(tail), 该变量需要永远指向 List 的尾部来记录位置,可以保证链表的顺序与用户输入的顺序是一致的。与此同时还有一种初始化方法即是 头插法 。头插法只是将每一个新元素 P 的 next 指向表头,然后再将 L->next 指向新的 P。即可实现将新的元素插入到表头的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
List createL ()
{
List L = makeEmpty();
Position tail = L;

printf("input some integer into List in turn: (q to quit) \n");

while(1){ //头插法,插入顺序为输入的倒序
Position P = (Position) malloc ( sizeof(struct Node) );

if(scanf("%d", &(P->element)) == 0)
break;

P->next = L->next;
L->next = P;
}
return L;
}

二者实际运行的区别。