链表由节点构成，单链表中的节点包含着数据和next指针，写成结构体的形式就是
1
2
3
4
5
| typedef int ElemType;
typedef struct _Node {
ElemType data;
struct _Node *next;
} Node;
|
初始化链表
1
2
3
4
5
6
| Node *InitList() {
Node *L = (Node *)malloc(sizeof(Node));
L->data = 0;
L->next = NULL;
return L;
}
|
插入
插入的方法分为：头插、尾插、任意插。
头插法
注意：一定是先让目标节点P的next指向后继节点，再让前驱节点的next指向P，不然后继节点的地址会被覆盖掉。
1
2
3
4
5
6
| void HeadInsert(Node *L, ElemType e) {
Node *P = (Node *)malloc(sizeof(Node));
P->data = e;
P->next = L->next;
L->next = P;
}
|
尾插法
1
2
3
4
5
6
7
8
9
10
| void *TailInsert(Node *L, ElemType e) {
Node *P = L, *Tail = (Node *)malloc(sizeof(Node));
while (P->next) {
P = P->next;
}
P->next = Tail;
Tail->data = e;
Tail->next = NULL;
}
|
任意位置插入
1
2
3
4
5
6
7
8
9
| void Insert(Node *L, int index, ElemType e) {
Node *P = L, *Q = (Node *)malloc(sizeof(Node));
for (int i = 0; i < index - 1; i++) {
P = P->next;
}
Q->next = P->next;
P->next = Q;
Q->data = e;
}
|
遍历
1
2
3
4
5
6
7
8
| void Traverse(Node *L) {
Node *P = L->next;
while (P!=NULL) {
printf("%c", P->data);
P = P->next;
}
printf("\n");
}
|
删除
1
2
3
4
5
6
7
8
9
| void Delete(Node *L, int index) {
Node *P = L;
for (int i = 0; i < index - 1; i++) {
P = P->next;
}
Node *Q = P->next;
P->next = Q->next;
free(Q);
}
|
销毁
1
2
3
4
5
6
7
8
| void Destory(Node *L) {
Node *P = L, *Q;
while (P) {
Q = P->next;
free(P);
P = Q;
}
}
|
查找
1
2
3
4
5
6
7
8
9
10
| int Find(Node *L, ElemType e) {
Node *P = L;
int index = 0;
while (P) {
P = P->next;
index++;
if (P->data == e) return index;
}
return -1;
}
|
