单链表的定义

typedef int ElemType; typedef struct LNode {     ElemType data;     LNode *next; } LNode, *LinkList;

此处LNode 强调一个结点，*LinkList 强调一个单链表的头指针，本例中只有头指针使用*LinkList ；

单链表的头指针和头节点

若单链表没有头节点，那么单链表的头指针则指向链表的第一个元素；若由头节点，头指针指向头节点；例如头指针为 L；如果链表为空，则有L == NULL，若有头节点，则有L->next = NULL；

注意此处的指向问题应当透彻理解指针的概念，指向理解为元素地址；此处的 L 为头指针；在没有头节点时指向第一个元素，L 就是第一个元素的地址，若没有元素，即没有第一个元素，那么L == NULL；如果有头节点，那么 L 为头节点的地址，因此L->next 即为元素的第一个结点，故当链表为空时L->next == NULL；

本例中的单链表均为带头节点的单链表；

初始化一个单链表

初始化单链表的主要目的在于建立一个头节点，并让 L 指向头节点；

L = (LinkList)malloc(sizeof(LNode)) 此处申请一个头节点的空间并返回申请到空间的地址返回，必须传入 L 的应用或者二级指针；

若直接传入 L 那么将会拷贝一份 L 指针给 L1 ，那么申请到的空间地址将返回给 L1 而不是L，如下图

因此必须传入 L 的引用或者 L 的指针；

传入 L（无效）

void ListInitite(LinkList L) {     L = (LinkList)malloc(sizeof(LNode));     L->next = NULL; }

传入引用

void ListInitite(LinkList &L) {     L = (LinkList)malloc(sizeof(LNode));     L->next = NULL; }

传入 L 的指针

void ListInitite(LinkList *L) {     *L = (LinkList)malloc(sizeof(LNode));     (*L)->next = NULL; }

创建一个单链表

头插法

即将新元素插入到链表的第一个位置

void List_HeadInsert(LinkList &L) {     for(int i = 1; i <= 10; i++) { //将 1 ~ 10 按头插法插入单链表         LNode* p = (LNode*)malloc(sizeof(LNode));         p->data = i;         p->next = L->next;         L->next = p;     }     //按照头插法的插入方式结果为倒序     Show_List(L); }

测试本段代码

#include<iostream> #include<cstdlib> using namespace std;   typedef int ElemType; typedef struct LNode {     ElemType data;     struct LNode *next; } LNode, *LinkList;  void ListInitite(LinkList &L) {     L = (LinkList)malloc(sizeof(LNode));     L->next = NULL; }  void Show_List(LinkList L) {     LNode* p = L->next;     while (p)     {         printf("%d ", p->data);         p = p->next;     } }  void List_HeadInsert(LinkList &L) {     for(int i = 1; i <= 10; i++) { //将 1 ~ 10 按头插法插入单链表         LNode* p = (LNode*)malloc(sizeof(LNode));         p->data = i;         p->next = L->next;         L->next = p;     }     //按照头插法的插入方式结果为倒序     Show_List(L); }  int main() {     LinkList L;     ListInitite(L);     List_HeadInsert(L);     return 0; }

运行结果

10 9 8 7 6 5 4 3 2 1

尾插法

即新的元素放在链表尾

使用尾插法，需要定义一个尾指针 r，尾指针始终指向链表的最后一个元素；刚开始为空链表，尾指针指向头节点，即和 L 相等，此后每插入一个新的结点，新的结点成为新的尾结点，r 指向此结点；

void List_TailInsert(LinkList &L) {     LNode* r = L;     for(int i = 1; i <= 10; i++) {         LNode* p = (LNode*)malloc(sizeof(LNode));         p->data = i;         p->next = r->next;         r->next = p;         r = p;     } }

测试：

#include<iostream> #include<cstdlib> using namespace std;  typedef int ElemType; typedef struct LNode {     ElemType data;     struct LNode *next; } LNode, *LinkList;  void ListInitite(LinkList &L) {     L = (LinkList)malloc(sizeof(LNode));     L->next = NULL; }  void Show_List(LinkList L) {     LNode* p = L->next;     while (p)     {         printf("%d ", p->data);         p = p->next;     } }  void List_HeadInsert(LinkList &L) {     for(int i = 1; i <= 10; i++) { //将 1 ~ 10 按头插法插入单链表         LNode* p = (LNode*)malloc(sizeof(LNode));         p->data = i;         p->next = L->next;         L->next = p;     }     //按照头插法的插入方式结果为倒序     Show_List(L); }  void List_TailInsert(LinkList &L) {     LNode* r = L;     for(int i = 1; i <= 10; i++) {         LNode* p = (LNode*)malloc(sizeof(LNode));         p->data = i;         p->next = r->next;         r->next = p;         r = p;     } }  int main() {     LinkList L;     ListInitite(L);     List_TailInsert(L);     //按尾插法插入为顺序      Show_List(L);     return 0; }

测试结果：

1 2 3 4 5 6 7 8 9 10

返回链表的长度

int Length(LinkList L) {     LNode* p = L;     int length = 0;     while (p->next) {         length++;         p = p->next;     }     return length; }

链表的查询

按序号查找结点的值

即查找第 i 个结点的值，最终返回此结点

LNode* GetElem(LinkList L, int i) {     if(i == 0) {         return L;     }     if(i < 1 || i > Length(L)) {   //若超出链表范围         return NULL;     }     LNode* p = L;     int now = 0;     while(p && now < i) {         p = p->next;         now++;     }     return p; }

测试：

#include<iostream> #include<cstdlib> using namespace std;  typedef int ElemType; typedef struct LNode {     ElemType data;     struct LNode *next; } LNode, *LinkList;  void ListInitite(LinkList &L) {     L = (LinkList)malloc(sizeof(LNode));     L->next = NULL; }  void Show_List(LinkList L) {     LNode* p = L->next;     while (p)     {         printf("%d ", p->data);         p = p->next;     } }  void List_TailInsert(LinkList &L) {     LNode* r = L;     for(int i = 1; i <= 10; i++) {         LNode* p = (LNode*)malloc(sizeof(LNode));         p->data = i;         p->next = r->next;         r->next = p;         r = p;     } }  int Length(LinkList L) {     LNode* p = L;     int length = 0;     while (p->next) {         length++;         p = p->next;     }     return length; }   LNode* GetElem(LinkList L, int i) {     if(i == 0) {         return L;     }     if(i < 1 || i > Length(L)) {   //若超出链表范围         return NULL;     }     LNode* p = L;     int now = 0;     while(p && now < i) {         p = p->next;         now++;     }     return p; }   int main() {     LinkList L;     ListInitite(L);     List_TailInsert(L);     LNode* ip = GetElem(L, 5);     Show_List(L);     if(ip) {         printf("\n%d", ip->data);     }     return 0; }

测试结果：

1 2 3 4 5 6 7 8 9 10 5

按值查找结点

LNode* LocateElem(LinkList L, ElemType e) {     LNode* p = L->next;     while(p && p->data != e) {         p = p->next;     }     return p; }

插入结点

在链表的第 i 个位置插入元素 e

插入新的元素后共有 len + 1 个元素，插入位置也必须在 [1, len + 1]，因此插入位置必须在这个范围内；首先获得第 i - 1 个结点，然后进行操作；

bool ListInsert(LinkList &L, int i, ElemType e) {     if(i < 1 || i > Length(L) + 1) {         printf("插入位置错误\n");         return false;     }     LNode *pre, *s;     s->data = e;     pre = GetElem(L, i - 1);     s->next = pre->next;     pre->next = s;     return true; }

测试代码：

#include<iostream> #include<cstdlib> using namespace std;  typedef int ElemType; typedef struct LNode { 	ElemType data; 	struct LNode *next; } LNode, *LinkList;  void ListInitite(LinkList &L) { 	L = (LinkList)malloc(sizeof(LNode)); 	L->next = NULL; }  void Show_List(LinkList L) { 	LNode* p = L->next; 	while (p) { 		printf("%d ", p->data); 		p = p->next; 	} }  void List_HeadInsert(LinkList &L) { 	for(int i = 1; i <= 10; i++) { //将 1 ~ 10 按头插法插入单链表 		LNode* p = (LNode*)malloc(sizeof(LNode)); 		p->data = i; 		p->next = L->next; 		L->next = p; 	} }   int Length(LinkList L) { 	LNode* p = L->next; 	int length = 0; 	while(p) { 		length++; 		p = p->next; 	} 	return length; }   LNode* GetElem(LinkList L, int i) { 	if(i == 0) { 		return L; 	} 	if(i < 1 || i > Length(L)) {   //若超出链表范围 		return NULL; 	} 	LNode* p = L; 	int now = 0; 	while(p && now < i) { 		p = p->next; 		now++; 	} 	return p; }   bool ListInsert(LinkList &L, int i, ElemType e) {     if(i < 1 || i > Length(L) + 1) {         printf("插入位置错误\n");         return false;     }     LNode *pre = GetElem(L, i - 1);     LNode *s = (LNode*)malloc(sizeof(LNode));     s->data = e;     s->next = pre->next;     pre->next = s;     return true; }  int main() { 	LinkList L; 	ListInitite(L); 	List_HeadInsert(L); 	ListInsert(L, 5, 100); 	Show_List(L); 	return 0; }

测试结果：

10 9 8 7 100 6 5 4 3 2 1

前插和后插

前插即在一个已知结点的前面插入新的结点，后插即在一个已知结点的后面插入新的结点；

上面的插入函数即在结点的后面插入新的结点，首先需要得到第 i - 1 个结点，然后再此结点后面插入新的结点，即为后插；

前插操作也是类似，在某个结点的前面插入结点，首先获取到此结点的前一个结点，然后在前一个结点后面插入新的结点；但这种插入方式必须首先获取到已知结点的前一个结点，查找过程必须遍历当前结点之前的所有元素才能找到前一个结点；时间复杂度为 O(n)，采用另一种方式可以巧妙的将复杂度降低到 O(1)；方法为在已知结点的后面插入新的结点，然后交换新节点与已知结点的值，就实现了相同的目的；

void FrontInsert(LNode* node, ElemType e) {     LNode *s = (LNode*)malloc(sizeof(LNode));     s->data = e;     s->next = node->next;     node->next = s;     ElemType temp = node->data;     node->data = s->data;     s->data = temp; }

2~5 行操作为将新的结点插入到已知结点的后面，6~8 行操作为交换两个结点内的值；

测试：

#include<iostream> #include<cstdlib> using namespace std;  typedef int ElemType; typedef struct LNode {     ElemType data;     struct LNode *next; } LNode, *LinkList;  void ListInitite(LinkList &L) {     L = (LinkList)malloc(sizeof(LNode));     L->next = NULL; }  void Show_List(LinkList L) {     LNode* p = L->next;     while (p)     {         printf("%d ", p->data);         p = p->next;     } }  void List_HeadInsert(LinkList &L) {     for(int i = 1; i <= 10; i++) { //将 1 ~ 10 按头插法插入单链表         LNode* p = (LNode*)malloc(sizeof(LNode));         p->data = i;         p->next = L->next;         L->next = p;     } }   int Length(LinkList L) {     LNode* p = L->next;     int length = 0;     while(p) {         length++;         p = p->next;     }     return length; }   LNode* GetElem(LinkList L, int i) {     if(i == 0) {         return L;     }     if(i < 1 || i > Length(L)) {   //若超出链表范围         return NULL;     }     LNode *p = L;     int now = 0;     while(p && now < i) {         p = p->next;         now++;     }     return p; }   void FrontInsert(LNode* &node, ElemType e) {     LNode *s = (LNode*)malloc(sizeof(LNode));     s->data = e;     s->next = node->next;     node->next = s;     ElemType temp = node->data;     node->data = s->data;     s->data = temp; }   int main() {     LinkList L;     ListInitite(L);     List_HeadInsert(L);     Show_List(L);     LNode *node = GetElem(L, 5);     FrontInsert(node, 50);     printf("\n");     Show_List(L);     return 0; }

测试结果：

10 9 8 7 6 5 4 3 2 1 10 9 8 7 50 6 5 4 3 2 1

删除结点操作

删除链表位置为 i 的结点，并将删除的结点存放在 node 中

bool ListDelete(LinkList &L, int i, LNode* &node) {     if(i < 1 || i > Length(L)) {         printf("删除位置错误");         return false;     }     LNode *p = GetElem(L, i - 1);     LNode *q = p->next;     p->next = q->next;     node = q;     free(q);     return true; }

上述代码有错，free(void* p) 函数的作用是回收 动态分配给 p 的空间，不论有多少指针指向 p 所指向的空间，因此将对于node = q，在free(q) 以后 node 所指向的空间也被回收了，因此此处最好不返回结点，返回结点中的值；修正后的代码如下：

bool ListDelete(LinkList &L, int i, ElemType &del) {     if(i < 1 || i > Length(L)) {         printf("删除位置错误");         return false;     }     LNode *p = GetElem(L, i - 1);     LNode *q = p->next;     p->next = q->next;     del = q->data;     free(q);     return true; }

测试：

#include<iostream> #include<cstdlib> using namespace std;  typedef int ElemType; typedef struct LNode {     ElemType data;     struct LNode *next; } LNode, *LinkList;  void ListInitite(LinkList &L) {     L = (LinkList)malloc(sizeof(LNode));     L->next = NULL; }  void Show_List(LinkList L) {     LNode* p = L->next;     while (p)     {         printf("%d ", p->data);         p = p->next;     } }  void List_TailInsert(LinkList &L) {     LNode* r = L;     for(int i = 1; i <= 10; i++) {         LNode* p = (LNode*)malloc(sizeof(LNode));         p->data = i;         p->next = r->next;         r->next = p;         r = p;     } }  int Length(LinkList L) {     LNode* p = L->next;     int length = 0;     while(p) {         length++;         p = p->next;     }     return length; }   LNode* GetElem(LinkList L, int i) {     if(i == 0) {         return L;     }     if(i < 1 || i > Length(L)) {   //若超出链表范围         return NULL;     }     LNode *p = L;     int now = 0;     while(p && now < i) {         p = p->next;         now++;     }     return p; }   bool ListDelete(LinkList &L, int i, ElemType &del) {     if(i < 1 || i > Length(L)) {         printf("删除位置错误");         return false;     }     LNode *p = GetElem(L, i - 1);     LNode *q = p->next;     p->next = q->next;     del = q->data;     free(q);     return true; }  int main() {     LinkList L;     ListInitite(L);     List_TailInsert(L);     Show_List(L);     ElemType del;     ListDelete(L, 7, del);     printf("\n");     Show_List(L);     printf("\n删除的元素为：%d", del);     return 0; }

结果：

1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 8 9 10 删除的元素为：7

此处删除的实现依然为后删，即找到将要删除结点的前一个结点进行删除；即给定一个已知结点需要对其进行删除，首先应该找到其前驱节点才能进行删除；和前插法类似，也有减少其复杂度的方法，即首先交换待删除结点后其后继节点的值，然后删除其后继节点；实现方式和前插法类似：

void Del(LinkList &L, LNode* &p) {     LNode* q = p->next;     ElemType temp = q->data;     q->data = p->data;     p->data = temp;     p->next = q->next;     free(q); }

当然此时对于极端情况，即要删除的元素为最后一个元素时不适用；

测试：

#include<iostream> #include<cstdlib> using namespace std;  typedef int ElemType; typedef struct LNode {     ElemType data;     struct LNode *next; } LNode, *LinkList;  void ListInitite(LinkList &L) {     L = (LinkList)malloc(sizeof(LNode));     L->next = NULL; }  void Show_List(LinkList L) {     LNode* p = L->next;     while (p)     {         printf("%d ", p->data);         p = p->next;     } }  void List_TailInsert(LinkList &L) {     LNode* r = L;     for(int i = 1; i <= 10; i++) {         LNode* p = (LNode*)malloc(sizeof(LNode));         p->data = i;         p->next = r->next;         r->next = p;         r = p;     } }  int Length(LinkList L) {     LNode* p = L->next;     int length = 0;     while(p) {         length++;         p = p->next;     }     return length; }   LNode* GetElem(LinkList L, int i) {     if(i == 0) {         return L;     }     if(i < 1 || i > Length(L)) {   //若超出链表范围         return NULL;     }     LNode *p = L;     int now = 0;     while(p && now < i) {         p = p->next;         now++;     }     return p; }    void Del(LinkList &L, LNode* &p) {     LNode* q = p->next;     ElemType temp = q->data;     q->data = p->data;     p->data = temp;     p->next = q->next;     free(q); }  int main() {     LinkList L;     ListInitite(L);     List_TailInsert(L);     Show_List(L); 	LNode *p = GetElem(L, 4); 	Del(L, p); 	printf("\n"); 	Show_List(L);     return 0; }

结果：

1 2 3 4 5 6 7 8 9 10 1 2 3 5 6 7 8 9 10

单链表的销毁

void Destory(LinkList &L) {     LNode* p = L;     LNode* q = L;     while (q)     {         p = q;         q = q->next;         free(p);     }    free(L);      L=NULL; }