单链表：用链式存储的方式实现线性表，每个结点除了存放数据元素外，还要存储指向下个节点的指针
单链表的特点：
- 不要求大片连续空间，改变容量方便
- 不可随机存取，要耗费一定空间存放指针
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
| #include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
typedef struct LNode{ //LNode:结点
int data; //数据域：每个结点存放一个数据元素
struct LNode *next; //指针域：指针指向下一个结点
}LNode,*LinkList; //typedef struct LNode *LinkList; 要表示一个单链表时，只需声明一个头指针L，指向单链表的第一个结点
//初始化一个空的链表(不带头结点)
//bool InitList(LinkList *L){
// (*L)=NULL; //空表，暂时还没有任何结点，防止脏数据
// return true;
//}
//判断单链表是否为空(不带头结点)
//bool Empty(LinkList *L){
// if((*L) == NULL){
// return true;
// }
// else{
// return false;
// }
//}
//这里LNode *和LinkList是等价的，LinkList强调这是一个单链表，LNode *强调这是一个结点
//LNode * GetElem(LinkList L,int i){
// int j=1;
// LNode *p=L->next;
// if(i == 0){
// return L;
// }
// if(i<1){
// return NULL;
// }
// while(p != NULL && j<i){
// p=p->next;
// j++;
// }
// return p;
//}
//初始化一个单链表(带头结点)
bool InitList(LinkList *L){
(*L)=(LNode *)malloc(sizeof(LNode)); //分配一个头结点,并使得头指针*L指向这个头结点
if((*L) == NULL){ //内存不足，分配失败
return false;
}
(*L)->data=0; //头结点不存储数据
(*L)->next=NULL; //头结点之后暂时还没有结点
return true;
}
//判断单链表是否为空(带头结点)
bool Empty(LinkList *L){
if((*L)->next == NULL){
return true;
}
else{
return false;
}
}
int main(){
LinkList L; //等价于LNode *L; 声明一个指向单链表的第一个结点的指针，注意此处并没有创建一个结点
InitList(&L); //初始化一个空表
//...后续代码
}
|
不带头结点写代码更麻烦，带头结点写代码更方便
