单链表（不带头结点）

90 阅读 0 评论 60 点赞

我是靠谱客的博主鲤鱼早晨，最近开发中收集的这篇文章主要介绍单链表（不带头结点），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

初稿：2017-11-18 23:50:40

单链表的结点：数据域，指针域（存储下一结点的地址）

包含函数：初始化，销毁，清空，尾插法和头插法批量录入数据，统计结点的个数，追加结点，删除结点，正序和逆序打印链表。

知识点：

（1）一个结构体内部不能含有结构体本身类型的结点，但可以含有本类型的指针。

（2）易错点：删除，插入的操作可能会影响首结点的地址，要单独处理，不注意代码运行会全是bug！

（3）逆序打印采用的递归，可着重看一下。

（4）批量录入数据有两种方法：头插法，链表的顺序和输入顺序正好相反。尾插法则正好相同。

（5）删除结点采用O（1）方法，分4种情况

首结点&&最后一个结点：*L = null
首结点&&不是最后一个结点：先保存下一结点的地址，用下一结点覆盖本应删除的目的结点，删除事先保存的结点
不是首结点&&最后一个结点：无法删除，必须采用伴随扫描指针的方式，获知前驱指针，才能删除
不是首结点&&不是最后一个结点：采用情况2的方法

（6）伴随指针查找value的代码（两个紧邻指针一起扫描单链表，一般删除结点时使用）

//至少含有一个元素，即不为空

p = frist; q = NULL;
while (p != NULL && p->data != value)
{
//在此通过p可以操作所有的元素

q = p;/*这两个语句是不可分割的，是一个整体，相当于原语*/
p = p->next;/*在这个整体前后，q一定指向p的前驱*/
//在此p：2 to last；q：1 to last - 1

}
/*出循环后，q仍旧指向p的前驱，只要p不指向空*/
/*适用于查找value，并进行牵扯到其前驱的操作*/
注意第一个结点就是value的情况！，出循环后前驱指针是null


1 #include"头文件.h"

2 /*头插法，逆序

3 尾插法，正序*/

4 typedef struct node {

5
int data;

6
struct node *next;

7 }Node,*LinkList;

8 /*初始化单链表*/

9 void InitList(LinkList *L) {
 10
*L = null;
 11 }
 12 /*销毁单链表*/
 13 void DestroyList(LinkList *L) {
 14
if (*L == null)
 15
return;
 16 
LinkList p;
 17
while (*L != null) {
 18
p = (*L)->next;//临时保存下一结点的地址
 19
free(*L);
 20
*L = p;
 21 
}
 22 }
 23 /*清空单链表*/
 24 void ClearList(LinkList *L) {
 25 
DestroyList(L);
 26 }
 27 /*批量录入数据：头插法*/
 28 void HeadCreate(LinkList *L) {
 29
int elem; Node *p;
 30
while (scanf_s("%d", &elem), elem != -1) {
 31
if (*L == null) {
 32
*L = (LinkList)malloc(sizeof(Node));
 33
if (*L == null) exit(-1);
 34
(*L)->data = elem;
 35
(*L)->next = null;
 36 
}
 37
else {
 38
p = (LinkList)malloc(sizeof(Node));
 39
if (!p) exit(-1);
 40
p->data = elem;
 41
p->next = (*L)->next;
 42
(*L)->next = p;
 43 
}
 44 
}
 45 }
 46 /*批量录入数据：尾插法*/
 47 void TailCreate(LinkList *L) {
 48
int elem; Node *tail = null,*p;
 49
while (scanf_s("%d", &elem), elem != -1) {
 50
if (*L == null) {
 51
*L = (LinkList)malloc(sizeof(Node));
 52
if (*L == null) exit(-1);
 53
(*L)->data = elem;
 54
(*L)->next = null;
 55
tail = *L;
 56 
}
 57
else {
 58
p = (LinkList)malloc(sizeof(Node));
 59
if (!p) exit(-1);
 60
p->data = elem;
 61
p->next = null;
 62
tail->next = p;
 63
tail = p;
 64 
}
 65 
}
 66 }
 67 /*统计结点的个数*/
 68 int TotalNum(LinkList *L) {
 69
int count = 0;//计数器
 70
LinkList p = *L;
 71
for (; p; p = p->next)
 72
++count;
 73
return count;
 74 }
 75 /*在表尾追加元素value*/
 76 void AddToTail(LinkList *L,int value) {
 77
Node *p = null,*q = null;
 78
if (*L == null) {
 79
*L = (LinkList)malloc(sizeof(Node));
 80
if (*L == null) exit(-1);
 81
(*L)->data = value;
 82
(*L)->next = null;
 83 
}
 84
else {
 85
for (p = *L; p->next != null; p = p->next)
 86 
;
 87
q = (LinkList)malloc(sizeof(Node));
 88
if (!q) exit(-1);
 89
q->data = value;
 90
q->next = p->next;
 91
p->next = q;
 92 
}
 93 }
 94 /*删除第一个值是value结点*/
 95 void Remove(LinkList *L,int value) {
 96
if (*L == null)
 97
return;
 98
Node *p = *L,*q;
 99
while (p && p->data != value) {
100
p = p->next;
101 
}
102
if (!p) {
103
printf("没有该元素！n"); return;
104 
}
105
if (p == *L) {
106
if (p->next == null) {
107
*L = null;
108
free(p);
109 
}
110
else {
111
p = (*L)->next;
112
(*L)->data = (*L)->next->data;
113
(*L)->next = (*L)->next->next;
114
free(p);
115 
}
116 
}
117
else {
118
if (p->next != null) {
119
p->data = p->next->data;
120
q = p->next;
121
p->next = q->next;
122
free(q);
123 
}
124
else {
125
printf("无法删除，请采用伴随扫描指针的方法删除。n");
126
return;
127 
}
128 
}
129
130 }
131 /*打印单链表*/
132 void Print(LinkList *L) {
133
if (*L == null)
134
return;
135
Node *p = *L;
136
for (; p; p = p->next) {
137
printf("%d ", p->data);
138 
}
139
printf("n");
140 }
141 /*递归逆序打印单链表*/
142 void FromTailPrint(LinkList *L) {
143
if (*L == null)
144
return;
145
FromTailPrint(&(*L)->next);
146
printf("%d ", (*L)->data);
147 }
148 int main() {
149 
LinkList L;
150
InitList(&L);
151
TailCreate(&L);
152 
fflush(stdin);
153
printf("打印单链表n");
154
Print(&L);
155
printf("单链表结点的个数是：%dn", TotalNum(&L));
156
printf("删除9n");
157
Remove(&L, 9);
158
printf("打印单链表n");
159
Print(&L);
160
printf("追加10n");
161
AddToTail(&L, 10);
162
printf("逆序打印单链表n");
163
FromTailPrint(&L);
164
system("pause");
165
return 0;
166 }