081103_链表的C语言实现之单链表的实现

c语⾔实现--带头结点单链表操作可能是顺序表研究的细致了⼀点，单链表操作⼀下⼦就实现了。

这⾥先实现带头结点的单链表操作。

⼤概有以下知识点.1;结点：结点就是单链表中研究的数据元素，结点中存储数据的部分称为数据域，存储直接后继地址的部分称为指针域。

2;结点⽰意图：3;头指针：头指针始终指向链表第⼀个元素，当有头结点时头结点就是链表第⼀个元素。

头指针具有标识左右，故头指针命名为链表的名字，这⾥为linklist。

头指针是⼀定存在的。

4;头结点：引⼊头结点的⽬的是，将链表⾸元结点的插⼊和删除操作与其他结点的插⼊和删除操作统⼀起来。

（即头指针地址不在发⽣变化）5;单链表结点结构体表⽰：1struct LNode2 {3int data; //姑且认为其数据为整型4struct LNode * next;5 };67 typedef struct LNode * linklist6;单链表的操作集合，头⽂件 defs.h1 #ifndef _DEFS_H_2#define _DEFS_H_34 #include<stdio.h>5 #include<stdlib.h>6 #include<malloc.h>78struct LNode //单链表结点的定义9 {10int data;11struct LNode * next;12 }13 typedef struct LNode * linklist1415//操作集合16void InitList(linklist *L); //申请头结点，头指针地址改变17void DestroyList(linklist *L); //须释放头结点，头指针地址改变18void ClearList(linklist L); //保留头结点，头指针地址不变19void ListEmpty(linklist L);20int ListLength(linklist L);21int GetElem(linklist L, int i, int *e);22int LocateElem(linklist L, int e);23int PriorElem(linklist L, int cur_e, int *pri_e);24int NextElem(linklist L, int cur_e, int *nex_e);25int ListInsert(linklist L, int i, int e); //插⼊不改变头指针的值26int ListDelete(linklist L, int i, int *e); //删除操作也不改变头指针的值27void TravelList(linklist L);28#endif7;InitList操作实现1 #include"defs.h"23void InitList(linklist *L) //接受头指针的地址值4 {5 *L = (linklist)malloc(sizeof(struct LNode)); //*L表⽰头指针67if (*L == NULL)8 {9 printf("分配结点失败。

单链表的基本操作《》⼀节我们学习了如何使⽤存储数据元素，以及如何使⽤ C 语⾔创建链表。

本节将详细介绍对链表的⼀些基本操作，包括对链表中数据的添加、删除、查找（遍历）和更改。

注意，以下对链表的操作实现均建⽴在已创建好链表的基础上，创建链表的代码如下所⽰：1. //声明节点结构2. typedef struct Link{3. int elem;//存储整形元素4. struct Link *next;//指向直接后继元素的指针5. }link;6. //创建链表的函数7. link * initLink(){8. link * p=(link*)malloc(sizeof(link));//创建⼀个头结点9. link * temp=p;//声明⼀个指针指向头结点，⽤于遍历链表10. //⽣成链表11. for (int i=1; i<5; i++) {12. //创建节点并初始化13. link *a=(link*)malloc(sizeof(link));14. a->elem=i;15. a->next=NULL;16. //建⽴新节点与直接前驱节点的逻辑关系17. temp->next=a;18. temp=temp->next;19. }20. return p;21. }从实现代码中可以看到，该链表是⼀个具有头节点的链表。

由于头节点本⾝不⽤于存储数据，因此在实现对链表中数据的"增删查改"时要引起注意。

链表插⼊元素同⼀样，向链表中增添元素，根据添加位置不同，可分为以下 3 种情况：插⼊到链表的头部（头节点之后），作为⾸元节点；插⼊到链表中间的某个位置；插⼊到链表的最末端，作为链表中最后⼀个数据元素；虽然新元素的插⼊位置不固定，但是链表插⼊元素的思想是固定的，只需做以下两步操作，即可将新元素插⼊到指定的位置：1. 将新结点的 next 指针指向插⼊位置后的结点；2. 将插⼊位置前结点的 next 指针指向插⼊结点；例如，我们在链表{1,2,3,4}的基础上分别实现在头部、中间部位、尾部插⼊新元素 5，其实现过程如图 1 所⽰：图 1 链表中插⼊元素的 3 种情况⽰意图从图中可以看出，虽然新元素的插⼊位置不同，但实现插⼊操作的⽅法是⼀致的，都是先执⾏步骤 1 ，再执⾏步骤 2。

C语⾔单链表实现⽅法详解本⽂实例讲述了C语⾔单链表实现⽅法。

分享给⼤家供⼤家参考，具体如下：slist.h#ifndef __SLIST_H__#define __SLIST_H__#include<cstdio>#include<malloc.h>#include<assert.h>typedef int ElemType;typedef struct Node { //定义单链表中的结点信息ElemType data; //结点的数据域struct Node *next; //结点的指针域}Node,*PNode;typedef struct List { //定义单链表的链表信息PNode first; //first指向单链表中的第⼀个结点PNode last; //last指向单链表中的最后⼀个结点size_t size; //记录单链表中的结点个数}List;void InitList(List *list);//初始化单链表void push_back(List *list, ElemType x);//在单链表的末尾插⼊元素void push_front(List *list, ElemType x);//在单链表的头部插⼊元素void show_list(List *list);//打印单链表void pop_back(List *list);//删除单链表的最后⼀个元素void pop_front(List *list);//删除单链表的第⼀个元素void insert_val(List *list, ElemType val);//将数据元素插⼊到单链表中（要求此时单链表中的数据元素顺序排列）Node* find(List *list, ElemType x);//查找单链表中数据值为x的结点int length(List *list);//求单链表的长度void delete_val(List *list, ElemType x);//按值删除单链表中的某个数据元素void sort(List *list);//对单链表进⾏排序void reverse(List *list);//逆置单链表void clear(List *list);//清除单链表void destroy(List *list);//摧毁单链表#endif //__SLIST_H__slist.cpp#include"slist.h"void InitList(List *list) {list->first = list->last = (Node*)malloc(sizeof(Node)); //头结点assert(list->first != NULL);list->first->next = NULL;list->size = 0;}void push_back(List *list, ElemType x) {//step 1：创建⼀个新的结点Node *s = (Node*)malloc(sizeof(Node));assert(s != NULL);s->data = x;s->next = NULL;//step 2：将新结点插⼊单链表的表尾list->last->next = s;list->last = s;//step 3：更新单链表的长度list->size++;}void push_front(List *list, ElemType x) {//step 1：创建⼀个新的结点Node *s = (Node*)malloc(sizeof(Node));assert(s != NULL);s->data = x;s->next = NULL;//step 2：将新结点插⼊单链表的表头s->next = list->first->next;list->first->next = s;//step 3：判断插⼊的结点是否是单链表的第⼀个结点，若是更新链表的尾指针if (list->size == 0)list->last = s;//step 4：更新单链表的长度list->size++;}void show_list(List *list) {//step 1：指针p指向单链表的第⼀个结点Node *p = list->first->next;//step 2：循环打印结点的信息while (p != NULL) {printf("%d->", p->data);p = p->next;}printf("Nul.\n");}void pop_back(List *list) {//step 1：判断单链表是否为空if (list->size == 0) return;//step 2：定义指针p使其指向⽬标结点的前⼀个结点Node *p = list->first;//从头结点开始while (p->next != list->last)p = p->next;//step 3：删除⽬标结点free(list->last);list->last = p;list->last->next = NULL;//step 4：更新单链表的长度list->size--;}void pop_front(List *list) {//step 1：判断单链表是否为空if (list->size == 0) return;//step 2：定义指针p使其指向⽬标结点的前⼀个结点Node *p = list->first->next;//step 3：删除⽬标结点list->first->next = p->next;free(p);//step 4：判断删除的结点是否是单链表的最后⼀个结点，若是则更新单链表的尾指针 if (list->size == 1)list->last = list->first;//step 4：更新单链表的长度list->size--;}void insert_val(List *list, ElemType x) {//step 1：创建⼀个新的结点Node *s = (Node*)malloc(sizeof(Node));assert(s != NULL);s->data = x;s->next = NULL;//step 2：定义指针p使其指向待插⼊位置的前⼀个结点Node *p = list->first;//从头结点开始while (p->next != NULL && p->next->data < s->data)p = p->next;//step 3：判断结点的待插⼊位置是否是表尾，若是则更新单链表的尾指针if (p->next == NULL)list->last = s;//step 4：插⼊结点s->next = p->next;p->next = s;//step 5：更新单链表长度list->size++;}Node* find(List *list, ElemType x) {//step 1：指针p指向单链表的第⼀个结点Node *p = list->first->next;//step 2：按照循环顺序查找链表结点while (p != NULL && p->data != x)p = p->next;return p;}int length(List *list) {return list->size;}void delete_val(List *list, ElemType x) {//step 1：判断单链表是否为空if (list->size == 0) return;//step 2：确定结点在单链表中的位置，并判断其是否存在于单链表中Node *p = find(list, x);if (p == NULL) {printf("要删除的数据不存在！\n");return;}//step 3：判断结点位置是否是表尾if (p == list->last)//是表尾pop_back(list);else {//不是表尾Node *q = p->next;p->data = q->data;p->next = q->next;free(q);list->size--;}}void sort(List *list) {//step 1：判断单链表中的结点数是否为0或1if (list->size == 0 || list->size == 1) return;//step 2：将单链表中第⼀个结点之后的链表部分截出，⽅便重新按顺序插⼊链表之中Node *s = list->first->next; // 指针s指向单链表的第⼀个节点Node *p = s->next;//q指向s后⾯的结点list->last = s;//单链表的尾指针指向单链表的第⼀个结点list->last->next = NULL;//截断链表//step 3：将截出的链表中的结点根据其数据域⼤⼩重新插⼊到原来链表中while (p != NULL) {s = p;p = p->next;Node *q = list->first;while (q->next != NULL && q->next->data < s->data)q = q->next;if (q->next == NULL)//判断q此时指向的是否是单链表的最后⼀个结点，若是则更新链表的尾指针list->last = s;//将结点重新插⼊链表s->next = q->next;q->next = s;}}void reverse(List *list) {//step 1：判断单链表中的结点数是否为0或1if (list->size == 0 || list->size == 1) return;//step 2：将单链表中第⼀个结点之后的链表部分截出，然后将截出的链表中的结点按头插法重新插⼊到原链表中 Node *p = list->first->next;Node *q = p->next;list->last = p;list->last->next = NULL;while (q != NULL) {p = q;q = q->next;p->next = list->first->next;list->first->next = p;}}void clear(List *list) {//step 1：判断单链表是否为空if (list->size == 0) return;//step 2：释放单链表中的每⼀个结点Node *p = list->first->next;while (p != NULL) {list->first->next = p->next;free(p);p = list->first->next;}//step 3：头指针和尾指针重新都指向头结点list->last = list->first;//step 4：更新链表长度list->size = 0;}void destroy(List *list) {//step 1：清空单链表clear(list);//step 2：释放头结点free(list->first);//step 3：头指针和尾指针都赋值为空list->first = list->last = NULL;}main.cpp#include"slist.h"void main() {List mylist;InitList(&mylist);ElemType item;Node *p = NULL;int select = 1;while (select) {printf("*******************************************\n"); printf("*[1] push_back [2] push_front *\n");printf("*[3] show_list [4] pop_back *\n");printf("*[5] pop_front [6] insert_val *\n");printf("*[7] find [8] length *\n");printf("*[9] delete_val [10] sort *\n");printf("*[11] reverse [12] clear *\n");printf("*[13*] destroy [0] quit_system *\n"); printf("*******************************************\n"); printf("请选择：>>");scanf("%d", &select);if (select == 0) break;switch (select) {case 1:printf("请输⼊要插⼊的数据（-1结束）:>");while (scanf("%d", &item), item != -1) {push_back(&mylist, item);}break;case 2:printf("请输⼊要插⼊的数据（-1结束）:>");while (scanf("%d", &item), item != -1) {push_front(&mylist, item);}break;case 3:show_list(&mylist);break;case 4:pop_back(&mylist);break;case 5:pop_front(&mylist);break;case 6:printf("请输⼊要插⼊的数据:>");scanf("%d", &item);insert_val(&mylist, item);break;case 7:printf("请输⼊要查找的数据:>");scanf("%d", &item);p = find(&mylist, item);if (p == NULL)printf("要查找的数据在单链表中不存在！\n"); break;case 8:printf("单链表的长度为%d\n", length(&mylist)); break;case 9:printf("请输⼊要删除的值:>");scanf("%d", &item);delete_val(&mylist, item);break;case 10:sort(&mylist);break;case 11:reverse(&mylist);break;case 12:clear(&mylist);break;//case 13://destroy(&mylist);//break;default:printf("选择错误,请重新选择！\n");break;}}destroy(&mylist); //程序结束，摧毁链表}附：单链表优化版本slist.h#ifndef __SLIST_H__#define __SLIST_H__#include<cstdio>#include<malloc.h>#include<assert.h>typedef int ElemType;typedef struct Node { //定义单链表中的结点信息ElemType data; //结点的数据域struct Node *next; //结点的指针域}Node,*PNode;typedef struct List { //定义单链表的链表信息PNode first; //first指向单链表中的第⼀个结点PNode last; //last指向单链表中的最后⼀个结点size_t size; //记录单链表中的结点个数}List;void InitList(List *list);//初始化单链表void push_back(List *list, ElemType x);//在单链表的末尾插⼊元素void push_front(List *list, ElemType x);//在单链表的头部插⼊元素void show_list(List *list);//打印单链表void pop_back(List *list);//删除单链表的最后⼀个元素void pop_front(List *list);//删除单链表的第⼀个元素void insert_val(List *list, ElemType val);//将数据元素插⼊到单链表中（要求此时单链表中的数据元素顺序排列）Node* find(List *list, ElemType x);//查找单链表中数据值为x的结点int length(List *list);//求单链表的长度void delete_val(List *list, ElemType x);//按值删除单链表中的某个数据元素void sort(List *list);//对单链表进⾏排序void reverse(List *list);//逆置单链表void clear(List *list);//清除单链表void destroy(List *list);//摧毁单链表//代码优化Node* CreateNode(ElemType x); //创建⼀个单链表结点Node* begin(List *list); //返回单链表的第⼀个结点Node* end(List *list); //返回单链表中最后⼀个结点的下⼀个结点void insert(List *list, Node *pos, ElemType x); //在单链表的特定位置（pos）插⼊新的结点#endif //__SLIST_H__slist.cpp#include"slist.h"void InitList(List *list) {list->first = list->last = (Node*)malloc(sizeof(Node)); //头结点assert(list->first != NULL);list->first->next = NULL;list->size = 0;}//push_back的优化void push_back(List *list, ElemType x) {insert(list, end(list), x);}//push_front的优化void push_front(List *list, ElemType x) {insert(list, begin(list), x);}void show_list(List *list) {//step 1：指针p指向单链表的第⼀个结点Node *p = list->first->next;//step 2：循环打印结点的信息while (p != NULL) {printf("%d->", p->data);p = p->next;}printf("Nul.\n");}void pop_back(List *list) {//step 1：判断单链表是否为空if (list->size == 0) return;//step 2：定义指针p使其指向⽬标结点的前⼀个结点Node *p = list->first;//从头结点开始while (p->next != list->last)p = p->next;//step 3：删除⽬标结点free(list->last);list->last = p;list->last->next = NULL;//step 4：更新单链表的长度list->size--;}void pop_front(List *list) {//step 1：判断单链表是否为空if (list->size == 0) return;//step 2：定义指针p使其指向⽬标结点的前⼀个结点Node *p = list->first->next;//step 3：删除⽬标结点list->first->next = p->next;free(p);//step 4：判断删除的结点是否是单链表的最后⼀个结点，若是则更新单链表的尾指针 if (list->size == 1)list->last = list->first;//step 4：更新单链表的长度list->size--;}//insert_val的优化void insert_val(List *list, ElemType x) {//step 1：创建⼀个新的结点Node *s = CreateNode(x);//step 2：定义指针p使其指向待插⼊位置的前⼀个结点Node *p = list->first;//从头结点开始while (p->next != NULL && p->next->data < s->data)p = p->next;//step 3：判断结点的待插⼊位置是否是表尾，若是则更新单链表的尾指针if (p->next == NULL)list->last = s;//step 4：插⼊结点s->next = p->next;p->next = s;//step 5：更新单链表长度list->size++;}Node* find(List *list, ElemType x) {//step 1：指针p指向单链表的第⼀个结点Node *p = list->first->next;//step 2：按照循环顺序查找链表结点while (p != NULL && p->data != x)p = p->next;return p;}int length(List *list) {return list->size;}void delete_val(List *list, ElemType x) {//step 1：判断单链表是否为空if (list->size == 0) return;//step 2：确定结点在单链表中的位置，并判断其是否存在于单链表中Node *p = find(list, x);if (p == NULL) {printf("要删除的数据不存在！\n");return;}//step 3：判断结点位置是否是表尾if (p == list->last)//是表尾pop_back(list);else {//不是表尾Node *q = p->next;p->data = q->data;p->next = q->next;free(q);list->size--;}}void sort(List *list) {//step 1：判断单链表中的结点数是否为0或1if (list->size == 0 || list->size == 1) return;//step 2：将单链表中第⼀个结点之后的链表部分截出，⽅便重新按顺序插⼊链表之中Node *s = list->first->next; // 指针s指向单链表的第⼀个节点Node *p = s->next;//q指向s后⾯的结点list->last = s;//单链表的尾指针指向单链表的第⼀个结点list->last->next = NULL;//截断链表//step 3：将截出的链表中的结点根据其数据域⼤⼩重新插⼊到原来链表中while (p != NULL) {s = p;p = p->next;Node *q = list->first;while (q->next != NULL && q->next->data < s->data)q = q->next;if (q->next == NULL)//判断q此时指向的是否是单链表的最后⼀个结点，若是则更新链表的尾指针list->last = s;//将结点重新插⼊链表s->next = q->next;q->next = s;}}void reverse(List *list) {//step 1：判断单链表中的结点数是否为0或1if (list->size == 0 || list->size == 1) return;//step 2：将单链表中第⼀个结点之后的链表部分截出，然后将截出的链表中的结点按头插法重新插⼊到原链表中 Node *p = list->first->next;Node *q = p->next;list->last = p;list->last->next = NULL;while (q != NULL) {p = q;q = q->next;p->next = list->first->next;list->first->next = p;}}void clear(List *list) {//step 1：判断单链表是否为空if (list->size == 0) return;//step 2：释放单链表中的每⼀个结点Node *p = list->first->next;while (p != NULL) {list->first->next = p->next;free(p);p = list->first->next;}//step 3：头指针和尾指针重新都指向头结点list->last = list->first;//step 4：更新链表长度list->size = 0;}void destroy(List *list) {//step 1：清空单链表clear(list);//step 2：释放头结点free(list->first);//step 3：头指针和尾指针都赋值为空list->first = list->last = NULL;}//优化Node* CreateNode(ElemType x) {Node *s = (Node*)malloc(sizeof(Node));assert(s != NULL);s->data = x;s->next = NULL;return s;}Node* begin(List *list) {return list->first->next;}Node* end(List *list) {return list->last->next;}void insert(List *list, Node *pos, ElemType x) {//step 1：创建⼀个新的结点Node *s = CreateNode(x);//step 2：确定带插⼊位置Node *p = list->first;while (p->next != pos)p = p->next;//step 3：插⼊结点s->next = p->next;p->next = s;//step 4：判断结点是否插⼊到链表的表尾，若是则更新单链表的表尾指针 if (pos == NULL)list->last = s;//step 5：更新单链表长度list->size++;}main.cpp#include"slist.h"void main() {List mylist;InitList(&mylist);ElemType item;Node *p = NULL;int select = 1;while (select) {printf("*******************************************\n");printf("*[1] push_back [2] push_front *\n");printf("*[3] show_list [4] pop_back *\n");printf("*[5] pop_front [6] insert_val *\n");printf("*[7] find [8] length *\n");printf("*[9] delete_val [10] sort *\n");printf("*[11] reverse [12] clear *\n");printf("*[13*] destroy [0] quit_system *\n");printf("*******************************************\n");printf("请选择：>>");scanf("%d", &select);if (select == 0) break;switch (select) {case 1:printf("请输⼊要插⼊的数据（-1结束）:>");while (scanf("%d", &item), item != -1) {push_back(&mylist, item);}break;case 2:printf("请输⼊要插⼊的数据（-1结束）:>");while (scanf("%d", &item), item != -1) {push_front(&mylist, item);}break;case 3:show_list(&mylist);break;case 4:pop_back(&mylist);break;case 5:pop_front(&mylist);break;case 6:printf("请输⼊要插⼊的数据:>");scanf("%d", &item);insert_val(&mylist, item);break;case 7:printf("请输⼊要查找的数据:>");scanf("%d", &item);p = find(&mylist, item);if (p == NULL)printf("要查找的数据在单链表中不存在！\n");break;case 8:printf("单链表的长度为%d\n", length(&mylist));break;case 9:printf("请输⼊要删除的值:>");scanf("%d", &item);delete_val(&mylist, item);break;case 10:sort(&mylist);break;case 11:reverse(&mylist);break;case 12:clear(&mylist);break;//case 13://destroy(&mylist);//break;default:printf("选择错误,请重新选择！\n");break;}}destroy(&mylist); //程序结束，摧毁链表}希望本⽂所述对⼤家C语⾔程序设计有所帮助。

单链表（c语⾔实现）贼详细直接上代码吧#include<stdio.h>#include<malloc.h>/*单链表特点：它是⼀种动态的储存结构，链表中每个节点占⽤的储存空间不是预先分配的，⽽是运⾏时系统根据需求⽣成的*/typedef struct lnode{int data;struct lnode *next;}lnode,*linklist;//结点定义/*关于头指针的⼀点说明：linklist L;外⾯⽤头指针来标识⼀个单链表，如单链表L,单链表H等，是指链表的第⼀个节点的地址被记录在指针变量L，H中，头指针为NULL时，表⽰⼀个空的单链表，需要进⼀步指出的是：上⾯定义的lnode是节点的类型，linklist是指向lnode节点的指针的类型，为了增强程序的可读性，通常将标识⼀个链表的头指针说明为linklist类型的变量*/linklist creat_linklist_insert_head_nohead(){linklist l=NULL;//定义头指针变量llnode *s;//新建⼀个节点int flag=-1;//输⼊停⽌标志位printf("输⼊整型数据，数据以空格隔开，输⼊数据为-1的时候表⽰输⼊截⽌\n");while(1){int x;scanf("%d",&x);if(x==flag)break;s=(lnode*)malloc(sizeof(lnode));//对s节点申请储存空间s->data=x;//赋值s->next=l;//s节点的next指向头指针l=s;//头指针指向新建⽴的s节点，因为这是在单链表的头部插⼊数据}return l;}//创建⼀个单链表，通过在头部插⼊数据，不含空的头节点//-------------------------------------------------------------------------------------------------------------///*在单链表的表头插⼊，只要x！=flag，就是⼀直申请s结点，从⽽可以⼀直在表头插⼊，其中l=s是最重要的，因为这是将s插⼊到l的表头，因为是在头部插⼊，所以只要⼀个头指针就可以，若是在单链表的尾部插⼊，那么就需要尾部指针关于此函数使⽤的⼀点说明：我们输⼊数据 1 2 3 4 5的时候，输出的是 5 4 3 2 1，因为我们是在头部插⼊数据的*///-------------------------------------------------------------------------------------------------------------//linklist creat_linklist_insert_end_yeshead(){linklist l=NULL,r=NULL;//定义头指针变量和尾指针变量lnode *s;//定义新建节点int flag=-1;//输⼊结束标志位printf("输⼊整型数据，数据以空格隔开，输⼊数据为-1的时候表⽰输⼊截⽌\n");while(1){int x;scanf("%d",&x);if(x==flag)//输⼊数据等于输⼊结束标志位则跳出循环break;s=(lnode*)malloc(sizeof(lnode));//申请内存空间s->data=x;//赋值if(l==NULL)//单链表为空l=s;//则将头指针指向新建节点elser->next=s;//不空的话则将尾指针的next指向s，因为如果不空的话，尾指针指向的肯定是⼀个数据节点，尾指针的next指向s是为了将两个数据节点连接起来r=s;//尾指针移动到新插⼊的节点上}if(r!=NULL)//有数据r->next=NULL;//尾指针的next指向空，说明尾指针后⾯没有数据了，⽬的的为了保证单链表尾指针逻辑的合理性return l;}//建⽴单链表且在链表尾部插⼊数据,含空的头节点//-----------------------------------------------------------------------------------------------------------------------///*在单链表的尾部插⼊，只要没有输⼊结束的标志，就⼀直申请s结点，然后把x赋给s结点的data域，l=s是为了第⼀个结点的结点的处理，因为在此之前l是⼀个空表，然后因为不断有新的结点⽣成，所以就是不断把新的s结点赋给r的next，这样就不断有s结点加⼊到了单链表中间，然后最重要的是每次新的结点加⼊到单链表中后要把r尾指针向后⾯移动，就是⽂中的r=s；关于此函数的⼀点说明：输⼊数据 1 2 3 4 5，输出还是 1 2 3 4 5，⽽不是 5 4 3 2 1，因为我们插⼊数据是在链表尾部插⼊的*///-----------------------------------------------------------------------------------------------------------------------//int length_linklist_yeshead(linklist l){linklist p=l;int j=1;while(p->next){j++;p=p->next;}return j;}//求单链表的表长，针对含有空的头节点的单链表int length_linklist_nohead(linklist l){lnode *p=l;int j=0;while(p){j++;p=p->next;}return j;}//求链表的表长，针对不含空的头节点的单链表lnode *get_linklist(linklist l,int i){lnode *p=l;int j=0;while(p!=NULL&&j<i){p=p->next;j++;}if(j==i)return p;elsereturn NULL;}//单链表的查找第i个元素结点，*p=l就是使p指针指向l链表；lnode *locate_linklist(linklist l,int x){lnode *p=l->next;//l为头节点while(p!=NULL&&p->data!=x)p=p->next;return p;}//单链表查找值为x的结点，找到后返回指向这个结点的指针；以后时刻要记得l为头指针，因为定义了头指针⽐没有定义头指针要⽅便许多；int insert_linklist(linklist l,int i,int x){lnode *p,*s;p=get_linklist(l,i-1);//找到第i-1个结点if(p==NULL){printf("i错误");return0;}elses=(lnode*)malloc(sizeof(lnode));s->data=x;s->next=p->next;p->next=s;return1;}//单链表的第i个结点后⾯的插⼊，重要的是申请，封装s结点，int del_linklist(linklist l,int i){i--;linklist p,s;p=get_linklist(l,i-1);if(p==NULL){printf("该i-1节点不存在");return -1;}else if(p->next==NULL){printf("第i个结点不存在");return0;}else{s=p->next;p->next=s->next;free(s);return1;}}//单链表中删除第i个结点，那么就先要找到i个结点的前驱，也就是第i-1个结点，同理单链表中的插⼊也要知道其前驱结点，所以单链表中的头节点的重要性就可想⽽知了void printf_linklist(lnode *plisthead){lnode *ptemp=plisthead;while(ptemp){printf("%d\t",ptemp->data);ptemp=ptemp->next;}printf("\n");}//链表打印函数int main(){/*linklist l=creat_linklist_insert_end_yeshead();printf("%d\n",length_linklist_yeshead(l));insert_linklist(l,2,100);//第⼆个结点的后⾯插⼊100printf_linklist(l);del_linklist(l,4);//删除第四个结点printf_linklist(l);*//*linklist l=creat_linklist_insert_head_nohead();printf("%d\n",length_linklist_nohead(l));insert_linklist(l,2,100);printf_linklist(l);del_linklist(l,4);printf_linklist(l);*/return0;}。

单链表（C语⾔实现）链表结构：SList.h//--------------------------------------------------------------------------/***功能：应⽤C语⾔实现单链表的各项操作****** 1：建⽴节点** 2：打印单链表** 3：尾插** 4：尾删** 5：头插** 6：头删** 7：清空整个链表** 8：获取链表长度** 9：查找数据** 10：在某位置后插⼊数据** 11：删除某位置的数据** 12：删除⼀个⽆头单链表的⾮尾节点** 13：在⽆头单链表的⼀个⾮头节点前插⼊⼀个节点** 14：查找中间节点** 15：查找倒数第k个节点(要求只能遍历⼀次)** 16：倒着打印单链表** 17：逆置单链表** 18：合并两个有序链表（合并后依然有序）** 19：冒泡排序****** By ：Lynn-Zhang***///---------------------------------------------------------------------------#pragma oncetypedef int DataType;typedef struct SListNode{DataType data; // 数据struct SListNode* next; //指向下⼀个节点的指针}SListNode;// 如果要修改链表就必须加引⽤SListNode* _BuyNode(DataType x); //建⽴节点void PrintSlist(SListNode* pHead); //打印单链表void PushBack(SListNode* & pHead, DataType x); //尾插(这⾥⽤了引⽤，指明是list的别名，调⽤时传参，不⽤传地址)(引⽤在.c⽂件中不可⽤) //void PushBack(SListNode** pHead, DataType x); // 这⾥的第⼀个参数指向链表第⼀个节点的指针的地址（调⽤时传参，传的是地址）void PopBack(SListNode* & pHead); //尾删void PushFront(SListNode* & pHead, DataType x); //头插void PopFront(SListNode* & pHead); //头删void DestoryList(SListNode*& pHead); //清空整个链表int GetSize(SListNode* pHead); //获取链表长度SListNode* Find(SListNode* pHead, DataType x); //查找数据void Insert(SListNode* pos, DataType x); //在某位置后插⼊数据void Erase(SListNode*& pHead, SListNode* pos); //删除某位置的数据void DelNonTailNode(SListNode* pos); //删除⼀个⽆头单链表的⾮尾节点void InsertFrontNode(SListNode* pos, DataType x); // 在⽆头单链表的⼀个⾮头节点前插⼊⼀个节点SListNode* FindMidNode(SListNode* pHead); //查找中间节点SListNode* FindKNode(SListNode* pHead, int k); //查找倒数第k个节点(要求只能遍历⼀次)void PrintTailToHead(SListNode* pHead); //倒着打印单链表（递归）//SListNode* Reverse_(SListNode* pHead); //逆置单链表（需要接收返回值），原链表会被改void Reverse(SListNode*& pHead); // 将原链表逆置SListNode* Merge(SListNode* pHead1, SListNode* pHead2); //合并两个有序链表（合并后依然有序）（递归）void Sort(SListNode* pHead); //冒泡排序SList.cpp#include"SList.h"#include <stdio.h>#include<assert.h>#include <malloc.h>SListNode* _BuyNode(DataType x) //建⽴节点{SListNode* tmp = (SListNode*)malloc(sizeof(SListNode)); tmp->data = x;tmp->next = NULL;return tmp;}void PrintSlist(SListNode* pHead) // 打印单链表{SListNode* cur = pHead;while (cur){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");}//void PushBack(SListNode** ppHead, DataType x) //尾插//{// assert(ppHead);//// 1.空//// 2.不为空// if(*ppHead == NULL)// {// *ppHead = _BuyNode(x);// }// else// {//// 找尾// SListNode* tail = *ppHead;// while(tail->next != NULL)// {// tail = tail->next;// }//// tail->next = _BuyNode(x);// }//}void PushBack(SListNode* & pHead, DataType x) //尾插{// 1.空// 2.不为空if (pHead == NULL){pHead = _BuyNode(x);}else{// 找尾SListNode* tail = pHead;while (tail->next != NULL){tail = tail->next;}tail->next = _BuyNode(x);}}void PopBack(SListNode* & pHead) // 尾删{//// 1.空// 2.⼀个节点// 3.多个节点//if (pHead == NULL){return;}else if (pHead->next == NULL){free(pHead);pHead = NULL;}else{SListNode* tail = pHead;SListNode* prev = NULL;while (tail->next){prev = tail;tail = tail->next;}free(tail);prev->next = NULL;}}void PushFront(SListNode* & pHead, DataType x) //头插{// 1.空// 2.不空if (pHead == NULL){pHead = _BuyNode(x);}else{SListNode* tmp = _BuyNode(x);tmp->next = pHead;pHead = tmp;}}void PopFront(SListNode*& pHead) //头删{//// 1.空// 2.⼀个节点// 3.⼀个以上的节点//if (pHead == NULL){return;}else if (pHead->next == NULL){free(pHead);pHead = NULL;}else{SListNode* tmp = pHead;pHead = pHead->next;free(tmp);}}void DestoryList(SListNode*& pHead) //清空整个链表{SListNode* cur = pHead;while (cur){SListNode* tmp = cur;cur = cur->next;free(tmp);}pHead = NULL;}int GetSize(SListNode* pHead) //获取链表长度{assert(pHead);SListNode* cur = pHead;int count = 0;while (cur){count++;cur = cur->next;}return count;}SListNode* Find(SListNode* pHead, DataType x) //查找节点{SListNode* cur = pHead;while (cur){if (cur->data == x)return cur;}cur = cur->next;}return NULL;}void Insert(SListNode* pos, DataType x) // 某位置后插⼊节点{assert(pos);SListNode* tmp = _BuyNode(x);tmp->next = pos->next;pos->next = tmp;}void Erase(SListNode*& pHead, SListNode* pos) //删除某位置的节点{assert(pos);assert(pHead);//pos为头结点if (pHead == pos){pHead = pHead->next;free(pos);return;}////SListNode* prev = pHead;while (prev){if (prev->next == pos){prev->next = pos->next;free(pos);break;}prev = prev->next;}}void DelNonTailNode(SListNode* pos) //// 删除⼀个⽆头单链表的⾮尾节点{assert(pos);assert(pos->next);SListNode* del = pos->next;SListNode* dnext = del->next;pos->data = del->data;pos->next = dnext;free(del);}void InsertFrontNode(SListNode* pos, DataType x) // 在⽆头单链表的⼀个⾮头节点前插⼊⼀个节点{assert(pos);SListNode* tmp = _BuyNode(pos->data);tmp->next = pos->next;pos->next = tmp;pos->data = x;}void Sort(SListNode* pHead) //冒泡排序{assert(pHead);int size = GetSize(pHead);for (int i = 0; i < size - 1; i++){SListNode* left = pHead;SListNode* right = pHead->next;for (int j = 0; j < size - i - 1; j++){if (left->data>right->data){int tmp = left->data;left->data = right->data;right->data = tmp;}right = right->next;left = left->next;}}SListNode* FindMidNode(SListNode* pHead) //查找中间节点{SListNode* fast = pHead;SListNode* slow = pHead;while (fast&&fast->next){slow = slow->next;fast = fast->next->next;}return slow;}SListNode* FindKNode(SListNode* pHead, int k) //查找倒数第k个节点{SListNode* fast = pHead;SListNode* slow = pHead;while (fast && k--){fast = fast->next;}if (k > 0){return NULL;}while (fast){slow = slow->next;fast = fast->next;}return slow;}void PrintTailToHead(SListNode* pHead) //倒着打印单链表（递归）{if (pHead){PrintTailToHead(pHead->next);printf("%d ", pHead->data);}}//SListNode* Reverse_(SListNode* pHead) //逆置单链表（需要接收返回值）原链表会被改//{// SListNode* cur = pHead;// SListNode* newHead = NULL;// while (cur)// {// SListNode* tmp = cur;// cur = cur->next;// tmp->next = newHead;// newHead = tmp;// }// return newHead;//}void Reverse(SListNode*& pHead) //逆置单链表（⽆需返回值）{SListNode* cur = pHead;SListNode* newHead = NULL;while (cur){SListNode* tmp = cur;cur = cur->next;tmp->next = newHead;newHead = tmp;}pHead = newHead;//return newHead;}SListNode* Merge(SListNode* pHead1, SListNode* pHead2) //合并两个有序链表（合并后依然有序）递归{if (pHead1 == NULL)return pHead2;else if (pHead2 == NULL)return pHead1;SListNode* pMergedHead = NULL;if (pHead1->data < pHead2->data){pMergedHead = pHead1;pMergedHead->next = Merge(pHead1->next, pHead2); }else{pMergedHead = pHead2;pMergedHead->next = Merge(pHead1, pHead2->next); }return pMergedHead;}Test.cpp#include "SList.h"#include<stdlib.h>//测试⽤例void Test1(){// 尾插打印尾删头插头删清空链表SListNode* list = NULL;PushBack(list, 1);PushBack(list, 2);PushBack(list, 3);PushBack(list, 4);PrintSlist(list);PopBack(list);PrintSlist(list);PushFront(list,0);PrintSlist(list);PopFront(list);PrintSlist(list);DestoryList(list);PrintSlist(list);}void Test2(){// 查找节点在某位置插⼊节点删除某位置节点SListNode* list = NULL;PushBack(list, 1);PushBack(list, 2);PushBack(list, 3);PushBack(list, 4);PrintSlist(list);SListNode* pos = Find(list, 2);Insert(pos, 0);PrintSlist(list);Erase(list, Find(list, 0));PrintSlist(list);}void Test3(){SListNode* list = NULL;PushBack(list, 1);PushBack(list, 2);PushBack(list, 3);PushBack(list, 4);PushBack(list, 5);PushBack(list, 6);PrintSlist(list);// 删除⼀个⽆头单链表的⾮尾节点/*SListNode* pos = Find(list, 2);DelNonTailNode(pos);PrintSlist(list);*/// 在⽆头单链表的⼀个⾮头节点前插⼊⼀个节点/*SListNode* pos = Find(list, 2);InsertFrontNode(pos, 0);PrintSlist(list);*///查找中间节点//PrintSlist(FindMidNode(list));//查找倒数第k个节点//SListNode* ret = FindKNode(list, 2);//PrintSlist(ret);//倒着打印单链表（递归）//PrintTailToHead(list);//逆置单链表//SListNode* ret = Reverse(list);//PrintSlist(ret);//PrintSlist(Reverse_(list));//PrintSlist(list);}void Test4(){ //合并两个有序链表（合并后依然有序） SListNode* list = NULL;PushBack(list, 4);PushBack(list, 2);PushBack(list, 1);PushBack(list, 4);PrintSlist(list);Sort(list);PrintSlist(list);/*SListNode* list1 = NULL;PushBack(list1, 2);PushBack(list1, 3);PushBack(list1, 3);PushBack(list1, 0);PrintSlist(list);Sort(list1);PrintSlist(list1);SListNode* ret = Merge(list, list1);PrintSlist(ret);PrintSlist(list);PrintSlist(list1);*/}int main(){//Test1();//Test2();//Test3();Test4();system("pause");return0;}。

单链表基本操作的实现单链表是一种常见的数据结构，它由多个节点组合而成，每个节点包含一个数据元素和一个指向下一个节点的指针。

通过指针，我们可以方便地在单链表中进行插入、删除和遍历等操作。

以下是关于单链表基本操作的实现。

1. 单链表的创建单链表的创建需要定义一个空的头结点，它的作用是方便在链表的头部进行添加和删除节点操作。

一个空的头节点可以在链表初始化的过程中进行创建。

```typedef struct Node{int data;struct Node *next;}Node;Node *createList(){Node *head = (Node*)malloc(sizeof(Node)); //创建空的头节点head->next = NULL;return head; //返回头节点的地址}```2. 单链表的插入单链表的插入可以分为在链表头部插入、在链表尾部插入和在链表中间插入三种情况。

a. 在链表头部插入节点：```void insertAtHead(Node *head, int data){Node *node = (Node*)malloc(sizeof(Node));node->data = data;node->next = head->next;head->next = node;}```b. 在链表尾部插入节点：```void insertAtTail(Node *head, int data){Node *node = (Node*)malloc(sizeof(Node));node->data = data;node->next = NULL;Node *p = head;while(p->next != NULL){p = p->next;}p->next = node;}```c. 在链表中间插入节点：```void insertAtMid(Node *head, int data, int pos){ Node *node = (Node*)malloc(sizeof(Node)); node->data = data;node->next = NULL;Node *p = head;int count = 0;while(p->next != NULL && count < pos-1){ p = p->next;count++;}if(count == pos-1){node->next = p->next;p->next = node;}else{printf("插入位置错误!");}}```3. 单链表的删除单链表的删除可以分为在链表头部删除、在链表尾部删除和在链表中间删除三种情况。

C语⾔实现单向链表及其各种排序（含快排，选择，插⼊，冒泡） #include<stdio.h>#include<malloc.h>#define LEN sizeof(struct Student)struct Student //结构体声明{long num;int score;struct Student* next;};int n;struct Student* creat() //创建单向链表{struct Student *head=NULL, *p_before, *p_later;p_before = p_later = (struct Student*) malloc(LEN);scanf_s("%ld%d", &p_before->num, &p_before->score);while (p_before->num!=0){n++;if (n == 1) head = p_before;else p_later->next = p_before;p_later = p_before;p_before = (struct Student*) malloc(LEN);scanf_s("%ld%d", &p_before->num, &p_before->score);}p_later->next = NULL;free(p_before);return head;}struct Student* sort(struct Student* list) //冒泡排序，当初写的是内容交换⽽不是指针交换，我知道这不是好的做法，但⽇⼦⼀久，当下没时间和热情改了，⼤家原谅，{ //等有时间了⼀定改struct Student *p, *q;int temp1,i;long temp2;for (p = list, i =1; i < n;i++,p=p->next)for (q = p->next;q!= NULL;q=q->next)if (p->score < q->score){temp1 = p->score;p->score = q->score;q->score = temp1;temp2 = p->num;p->num = q->num;q->num = temp2;}return list;}struct Student* sort1(struct Student* h) //插⼊排序（下边这堆注释是当初写完代码后⼜分析时加的，这⾥必须承认，我参考了⽹上的⼀些代码。

CC++实现单向循环链表（尾指针，带头尾节点） C语⾔实现单向循环链表，主要功能为空链表创建，链表初始化（头插法，尾插法），链表元素读取，按位置插⼊，（有序链表）按值插⼊，按位置删除，按值删除，清空链表，销毁链表。

单向循环链表和单向链表的区别：（1）单向链表为头指针，循环链表为尾指针，头指针指向头结点，尾指针指向终端结点；（2）为统⼀⽅便操作，单向链表设置头结点，单向循环链表设置头结点和尾结点；（3）设置尾结点后，尾指针指向尾结点，插⼊，删除等操作不⽤移动尾指针。

关键思路：创建头结点和尾结点。

1 #include <stdio.h>2 #include <stdlib.h>34 typedef struct Node{5int data;6struct Node *next;7 }Node;89//空循环链表创建10//创建头结点和尾结点11//链表尾指针指向尾结点，尾结点指向头结点，头结点指向尾结点12void iniCList(Node **CListTail){13 *CListTail = (Node *)malloc(sizeof(Node));14 Node *CListHead = (Node *)malloc(sizeof(Node));15if (NULL == *CListTail || NULL == CListHead){16 exit(0);17 }1819 (*CListTail)->next = CListHead;20 CListHead->next = *CListTail;21 }2223//循环链表初始化(头插法)24void iniCListHead(Node **CListTail, int n){25//创建头尾结点26 *CListTail = (Node *)malloc(sizeof(Node));27 Node *CListHead = (Node *)malloc(sizeof(Node));28if (NULL == *CListTail || NULL == CListHead){29 exit(0);30 }3132 (*CListTail)->next = CListHead;33 CListHead->next = *CListTail;3435int i = 0;36while (i < n){3738 Node *tmpNode = (Node *)malloc(sizeof(Node));39if (NULL == tmpNode){40 exit(0);41 }42 tmpNode->data = i;43 tmpNode->next = CListHead->next;44 CListHead->next = tmpNode;45 ++i;46 }47 }4849//循环链表初始化(尾插法)50void iniCListTail(Node **CListTail, int n){51//创建头尾结点52 *CListTail = (Node *)malloc(sizeof(Node));53 Node *CListHead = (Node *)malloc(sizeof(Node));54if (NULL == *CListTail || NULL == CListHead){55 exit(0);56 }5758 (*CListTail)->next = CListHead;59 CListHead->next = *CListTail;6061 Node *pCurrent = CListHead;6263int i = 0;64while (i < n){65 Node *tmpNode = (Node *)malloc(sizeof(Node));66if (NULL == tmpNode){67 exit(0);68 }69 tmpNode->data = i;70 tmpNode->next = *CListTail;71 pCurrent->next = tmpNode;72 pCurrent = tmpNode;7374 ++i;75 }76 }7778//循环链表按位置插⼊79void insertCListPos(Node *CList, int pos, int val){ 8081 Node *pCurrent = CList->next; //指向头结点82int i = 1;83while (pCurrent != CList && i < pos){84 pCurrent = pCurrent->next;85 ++i;86 }8788 Node *tmpNode = (Node *)malloc(sizeof(Node)); 89if (NULL == tmpNode){90 exit(0);91 }92 tmpNode->data = val;93 tmpNode->next = pCurrent->next;94 pCurrent->next = tmpNode;9596 }9798//有序循环链表，按值插⼊99void insertCListValue(Node *CList, int val){100 Node *pCur = CList->next->next;101 Node *pPer = CList->next;102103while (pCur != CList && pCur->data < val){ 104 pPer = pCur;105 pCur = pCur->next;106 }107108 Node *tmpNode = (Node *)malloc(sizeof(Node)); 109if (NULL == tmpNode){110 exit(0);111 }112 tmpNode->data = val;113 tmpNode->next = pPer->next;114 pPer->next = tmpNode;115 }116117//循环链表，按位置删除118void deleteCListPos(Node *CList, int pos){119 Node *pCur = CList->next;120121int i = 1;122while (pCur != CList && i < pos){123 pCur = pCur->next;124 ++i;125 }126127 Node *tmpNode = pCur->next;128 pCur->next = tmpNode->next;129free(tmpNode);130 }131132//循环链表，按值删除133//删除空链表为出问题134void deleteCListValue(Node *CList, int val){135 Node *pCur = CList->next->next;136 Node *pPer = CList->next;137138while (pCur != CList && pCur->data != val){ 139 pPer = pCur;140 pCur = pCur->next;141 }142if (pCur == CList)143return;144else{145 pPer->next = pCur->next;146free(pCur);147 }148 }149150//循环链表，清空链表151void claerCList(Node *CList){152 Node *p = CList->next->next;153 Node *q = NULL;154155while (p != CList){ //到达表尾156 q = p->next;157free(p);158 p = q;159 }160161 CList->next = CList; //将头结点指向尾结点162 }163164//循环链表，销毁链表165void destoryCList(Node **CList){166 Node *p = (*CList)->next;167 Node *q = NULL;168169while (p != (*CList)->next){ //到达表头170 q = p->next;171free(p);172 p = q;173 }174175 *CList = NULL;176 }177178//获取元素179void getCList(Node *CList, int pos, int *val){180 Node *pCur = CList->next->next;181int i = 1;182while (pCur != CList && i < pos){183 pCur = pCur->next;184 ++i;185 }186187 *val = pCur->data;188 }189//遍历输出元素190void printCList(Node *CList){191 Node * tmpNode = CList->next->next;192while (tmpNode != CList){ //到达表尾193 printf("%d\n", tmpNode->data);194 tmpNode = tmpNode->next;195 }196 }197198199int main(){200 Node *CList = NULL;201//iniCListHead(&CList, 8);202//iniCList(&CList);203 iniCListTail(&CList, 8);204205//insertCListPos(CList, 1, 2);206//insertCListPos(CList, 2, 4);207//insertCListPos(CList, 3, 6);208//209//insertCListValue(CList, 1);210//211//deleteCListPos(CList, 3);212//213//deleteCListValue(CList, 6);214215//claerCList(CList);216217int a = 0;218 getCList(CList, 2, &a);219 printf("%d\n", a);220221 printCList(CList);222223 printf("%d\n", CList);224 destoryCList(&CList);225 printf("%d\n", CList);226227 system("pause");228return0;229 }C语⾔完整代码 通过C++实现C语⾔的链表，主要区别：（1）struct可以不通过typedef，直接使⽤Node；（2）将malloc和free更换为new和delete1 #include <stdio.h>2 #include <stdlib.h>34struct Node{5int data;6struct Node *next;7 };89//空循环链表创建10//创建头结点和尾结点11//链表尾指针指向尾结点，尾结点指向头结点，头结点指向尾结点 12void iniCList(Node **CListTail){13 *CListTail = new Node;14 Node *CListHead = new Node;1516 (*CListTail)->next = CListHead;17 CListHead->next = *CListTail;18 }1920//循环链表初始化(头插法)21void iniCListHead(Node **CListTail, int n){22//创建头尾结点23 *CListTail = new Node;24 Node *CListHead = new Node;2526 (*CListTail)->next = CListHead;27 CListHead->next = *CListTail;2829int i = 0;30while (i < n){31 Node *tmpNode = new Node;3233 tmpNode->data = i;34 tmpNode->next = CListHead->next;35 CListHead->next = tmpNode;36 ++i;37 }38 }3940//循环链表初始化(尾插法)41void iniCListTail(Node **CListTail, int n){42//创建头尾结点43 *CListTail = new Node;44 Node *CListHead = new Node;4546 (*CListTail)->next = CListHead;47 CListHead->next = *CListTail;4849 Node *pCurrent = CListHead;5051int i = 0;52while (i < n){53 Node *tmpNode = new Node;5455 tmpNode->data = i;56 tmpNode->next = *CListTail;57 pCurrent->next = tmpNode;58 pCurrent = tmpNode;5960 ++i;61 }62 }6364//循环链表按位置插⼊65void insertCListPos(Node *CList, int pos, int val){6667 Node *pCurrent = CList->next; //指向头结点68int i = 1;69while (pCurrent != CList && i < pos){70 pCurrent = pCurrent->next;71 ++i;72 }7374 Node *tmpNode = new Node;7576 tmpNode->data = val;77 tmpNode->next = pCurrent->next;78 pCurrent->next = tmpNode;7980 }8182//有序循环链表，按值插⼊83void insertCListValue(Node *CList, int val){84 Node *pCur = CList->next->next;85 Node *pPer = CList->next;8687while (pCur != CList && pCur->data < val){88 pPer = pCur;89 pCur = pCur->next;90 }9192 Node *tmpNode = new Node;9394 tmpNode->data = val;95 tmpNode->next = pPer->next;96 pPer->next = tmpNode;97 }9899//循环链表，按位置删除100void deleteCListPos(Node *CList, int pos){ 101 Node *pCur = CList->next;102103int i = 1;104while (pCur != CList && i < pos){105 pCur = pCur->next;106 ++i;107 }108109 Node *tmpNode = pCur->next;110 pCur->next = tmpNode->next;111delete tmpNode;112 }113114//循环链表，按值删除115//删除空链表为出问题116void deleteCListValue(Node *CList, int val){ 117 Node *pCur = CList->next->next;118 Node *pPer = CList->next;119120while (pCur != CList && pCur->data != val){ 121 pPer = pCur;122 pCur = pCur->next;123 }124if (pCur == CList)125return;126else{127 pPer->next = pCur->next;128delete pCur;129 }130 }131132//循环链表，清空链表133void claerCList(Node *CList){134 Node *p = CList->next->next;135 Node *q = NULL;136137while (p != CList){ //到达表尾138 q = p->next;139delete p;140 p = q;141 }142143 CList->next = CList; //将头结点指向尾结点144 }145146//循环链表，销毁链表147void destoryCList(Node **CList){148 Node *p = (*CList)->next;149 Node *q = NULL;150151while (p != (*CList)->next){ //到达表头152 q = p->next;153delete p;154 p = q;155 }156157 *CList = NULL;158 }159160//获取元素161void getCList(Node *CList, int pos, int *val){ 162 Node *pCur = CList->next->next;163int i = 1;164while (pCur != CList && i < pos){165 pCur = pCur->next;166 ++i;167 }168169 *val = pCur->data;170 }171//遍历输出元素172void printCList(Node *CList){173 Node * tmpNode = CList->next->next;174while (tmpNode != CList){ //到达表尾175 printf("%d\n", tmpNode->data);176 tmpNode = tmpNode->next;177 }178 }179180181int main(){182 Node *CList = NULL;183//iniCListHead(&CList, 8);184//iniCList(&CList);185 iniCListTail(&CList, 8);186187//insertCListPos(CList, 1, 2);188//insertCListPos(CList, 2, 4);189//insertCListPos(CList, 3, 6);190//191//insertCListValue(CList, 1);192//193//deleteCListPos(CList, 3);194//195//deleteCListValue(CList, 6);196197//claerCList(CList);198199int a = 0;200 getCList(CList, 2, &a);201 printf("%d\n", a);202203 printCList(CList);204205 printf("%d\n", CList);206 destoryCList(&CList);207 printf("%d\n", CList);208209 system("pause");210return0;211 }C++完整代码单向循环链表 注意：（1）单向循环链表销毁时，需要将头结点和尾结点删除；（2）单向循环链表插⼊，删除，遍历，清空链表时，条件从头结点或第⼀节点始，判断指针是否达到尾结点；（3）清空链表时，最后将头结点指向尾结点；（4）销毁链表时，条件从头结点始，判断条件为指针是否到达头结点，最后将指针置空。

#include 〈stdio.h>＃include <malloc。

h>＃include 〈stdlib.h>/＊数据结构C语言版线性表的单链表存储结构表示和实现P28—31编译环境：Dev-C++ 4。

9。

9。

2日期：2011年2月10日＊/typedef int ElemType;// 线性表的单链表存储结构typedef struct LNode{ElemType data; //数据域struct LNode *next；//指针域}LNode, ＊LinkList；// typedef struct LNode *LinkList；// 另一种定义LinkList的方法// 构造一个空的线性表Lint InitList（LinkList ＊L){/＊产生头结点L，并使L指向此头结点,头节点的数据域为空，不放数据的。

void ＊malloc(size_t)这里对返回值进行强制类型转换了,返回值是指向空类型的指针类型.＊/（＊L）= (LinkList）malloc（sizeof（struct LNode) ）;if( ！(＊L）)exit（0）；// 存储分配失败(＊L)-〉next = NULL；// 指针域为空return 1；}// 销毁线性表L,将包括头结点在内的所有元素释放其存储空间。

int DestroyList（LinkList ＊L）｛LinkList q;// 由于单链表的每一个元素是单独分配的，所以要一个一个的进行释放while（＊L )｛q = (*L)—〉next;free（＊L ）；//释放*L = q;}return 1；｝/*将L重置为空表,即将链表中除头结点外的所有元素释放其存储空间，但是将头结点指针域置空，这和销毁有区别哦。

不改变L，所以不需要用指针。

*/int ClearList( LinkList L )｛LinkList p，q；p = L—〉next；// p指向第一个结点while( p ) // 没到表尾则继续循环｛q = p—>next;free( p )；//释放空间p = q；}L—>next = NULL; // 头结点指针域为空,链表成了一个空表return 1;}// 若L为空表（根据头结点L—〉next来判断，为空则是空表)，则返回1，// 否则返回0.int ListEmpty(LinkList L）{if（L—>next ) // 非空return 0;elsereturn 1；｝// 返回L中数据元素个数。

链表的C语言实现分类:计算机学习2006.12.29 09:06 作者：ybxycy | 评论：0 | 阅读：652数组作为存放同类数据的集合，给我们在程序设计时带来很多的方便，增加了灵活性。

但数组也同样存在一些弊病。

如数组的大小在定义时要事先规定，不能在程序中进行调整，这样一来，在程序设计中针对不同问题有时需要3 0个大小的数组，有时需要5 0个数组的大小，难于统一。

我们只能够根据可能的最大需求来定义数组，常常会造成一定存储空间的浪费。

我们希望构造动态的数组，随时可以调整数组的大小，以满足不同问题的需要。

链表就是我们需要的动态数组。

它是在程序的执行过程中根据需要有数据存储就向系统要求申请存储空间，决不构成对存储区的浪费。

链表是一种复杂的数据结构，其数据之间的相互关系使链表分成三种：单链表、循环链表、双向链表，下面将逐一介绍。

7.4.1 单链表图7 - 3是单链表的结构。

单链表有一个头节点h e a d，指向链表在内存的首地址。

链表中的每一个节点的数据类型为结构体类型，节点有两个成员：整型成员（实际需要保存的数据）和指向下一个结构体类型节点的指针即下一个节点的地址（事实上，此单链表是用于存放整型数据的动态数组）。

链表按此结构对各节点的访问需从链表的头找起，后续节点的地址由当前节点给出。

无论在表中访问那一个节点，都需要从链表的头开始，顺序向后查找。

链表的尾节点由于无后续节点，其指针域为空，写作为N U L L。

图7 - 3还给出这样一层含义，链表中的各节点在内存的存储地址不是连续的，其各节点的地址是在需要时向系统申请分配的，系统根据内存的当前情况，既可以连续分配地址，也可以跳跃式分配地址。

看一下链表节点的数据结构定义：struct node{int num;struct node *p;} ;在链表节点的定义中，除一个整型的成员外，成员p是指向与节点类型完全相同的指针。

在链表节点的数据结构中，非常特殊的一点就是结构体内的指针域的数据类型使用了未定义成功的数据类型。

线性表之单链表C++实现 线性表之单链表⼀、头⽂件：LinkedList.h1//单链表是⽤⼀组任意的存储单元存放线性表的元素，这组单元可以是连续的也可以是不连续的，甚⾄可以是零散分布在内存中的任意位置。

2//单链表头⽂件3 #include<iostream>4using namespace std;5//定义单链表结点-结构体类型6 template<class DataType>7struct Node8 {9 //数据域，存放该结点的数据10 DataType data;11 //指针域，指向下⼀个结点12 Node<DataType> *next;13 };1415 template<class DataType>16class LinkedList{17public:18 //单链表⽆参构造器19 LinkedList();20 //单链表有参构造器21 LinkedList(DataType array[], int n);22 LinkedList(int n, DataType array[]);23 //单链表析构函数24 ~LinkedList();25 //获取单链表的长度26 int GetLength();27 //查找单链表指定元素的序号28 int GetLocal(DataType x);29 //获取单链表指序号的元素30 DataType GetElement(int index);31 //单链表中在指定位置插⼊指定的元素32 void Insert(int index, DataType x);33 //在单链表中删除指定位置的元素34 DataType Delete(int index);35 //按序号输出单链表中的元素36 void PrintLinkedList();3738private :39 //声明单链表的头指针40 Node<DataType> *first;41 };4243//实现单链表的⽆参构造函数44 template<class DataType>45 LinkedList<DataType>::LinkedList()46 {47 first = new Node<DataType>;48 first->next = NULL;49 }5051//头插法建⽴单链表52 template<class DataType>53 LinkedList<DataType>::LinkedList(int n,DataType array[])54 {55 //初始化⼀个空链表56 first = new Node<DataType>;57 first->next = NULL;58 for (int i = 0; i < n; i++)59 {60 //为每⼀个数组元素都申请新结点61 Node<DataType> *s = new Node<DataType>;62 //数组元素赋值给结点数据域63 s->data = array[i];64 //将结点插⼊到头结点之前65 s->next = first->next;66 first->next = s;6768 }69 }7071//尾插法建⽴单链表72 template<class DataType>73 LinkedList<DataType>::LinkedList(DataType array[], int n)74 {75 //⽣成头结点76 first = new Node<DataType>;77 //定义尾结点78 Node<DataType> *r = first;79 for (int i = 0; i < n; i++)80 {81 //为每⼀个数组元素申请⼀个结点82 Node<DataType> *s = new Node<DataType>;83 //把数组元素赋值给结点的数据域84 s->data = array[i];85 //将每⼀个结点追加到终端结点之后86 r->next = s;87 r = s;88 }89 //尾结点尾NULL90 r->next = NULL;91 }9293//实现单链表的析构函数94 template<class DataType>95 LinkedList<DataType>::~LinkedList()96 {97 //声明⼯作指针98 Node<DataType> *q;99 while (first != NULL)100 {101 //暂存被释放的结点102 q = first;103 //让头指针指向要释放结点的下⼀个结点104 first = first->next;105 delete q;106 }107 }108109//实现单链表插⼊:在指定的位置插⼊指定的元素110 template<class DataType>111void LinkedList<DataType>::Insert(int index, DataType x)112 {113 //定义⼯作指针114 Node<DataType> *p = first->next;115 //定义计数器，初始值为0116 int count = 0;117 while (p != NULL &&count < index - 1)118 {119 //⼯作指针后移120 p = p->next;121 count ++;122 }123 //找到 index-1 的位置124 if (p == NULL)125 {126 throw"插⼊的位置有误";127 }128 else129 {130 //申请⼀个新结点131 Node<DataType> *s;132 s= new Node<DataType>;133 //其数据域为 x134 s->data = x;135 //在新结点的指针域存放⼯作指针p的指针域136 s->next = p->next;137 //将结点s插⼊到p结点之后138 p->next = s;139 }140 }141142//实现单链表的按值查找，返回指定元素在单链表中的序号（如不存在，则返回0）143 template<class DataType>144int LinkedList<DataType>::GetLocal(DataType x)145 {146 //定义⼯作指针147 Node<DataType> *p = first->next;148 //定义计数器，初始值是1149 int count = 1;150 //查找序号所对应的位置151 while (p != NULL)152 {153 if (p->data == x)154 {155 return count;156 }157 //⼯作指针后移158 p = p->next;159 //计数器加1160 count++;161 }162 //如果找不到该元素，则返回0163 return0;164 }165166//实现单链表按位查找，返回指定位置的元素167 template<class DataType>168 DataType LinkedList<DataType>::GetElement(int index)169 {170 //定义⼯作指针171 Node<DataType> *p = first->next;172 //定义计数器，初始值是1173 int count = 1;174 //查找序号所对应的位置175 while (p != NULL&&count < index)176 {177 //⼯作指针后移178 p = p->next;179 //计数器加1180 count++;181 }182 //如果找到单链表的末尾，还找不到指定的位置，则抛出异常183 if (p == NULL)184 {185 throw"查找的位置有误";186 }187 else188 {189 //当找到合适的位置时，返回该位置上的元素190 return p->data;191 }192193 }194195//实现获取单链表的长度196 template<class DataType>197int LinkedList<DataType>::GetLength()198 {199 //定义计数器，⽤来计算单链表的长度200 int count = 0;201 //定义⼯作指针202 Node<DataType> *p = first->next;203 while (p != NULL)204 {205 p = p->next;206 count++;207 }208 return count;209210 }211212//实现单链表的按序号输出元素213 template<class DataType>214void LinkedList<DataType>::PrintLinkedList()215 {216 //声明⼯作指针217 Node<DataType> *p;218 //初始化⼯作指针219 p = first->next;220 while(p != NULL)221 {222 cout << p->data << "";223 //⼯作指针向后移动224 p = p->next;225 }226 cout << endl;227 }228229//实现单链表的删除230 template<class DataType>231 DataType LinkedList<DataType>::Delete(int index)232 {233 Node<DataType> *p = first->next;234 int count = 0;235 //查找第 index-1 位置结点236 while (p != NULL&&count < index - 1)237 {238 p = p->next;239 count++;240 }241 //如果能找到242 if (p == NULL || p->next == NULL)243 {244 throw"删除的位置有误";245 }246 else247 {248 Node<DataType> *q = p->next;249 DataType x = q->data;250 p->next = q->next;251 delete q;252 return x;253 }254 }⼆、测试线性表之单链表的源⽂件：TestLinkedList.cpp1 #include<iostream>2 #include "LinkedList.h"3using namespace std;4void show()5 {6 cout << "---------------------------------------" << endl;7 }8int main()9 {10 int array[] = { 1, 3, 5, 2, 7, 6, 9, 8, 10, 4};11 //声明单链表12 LinkedList<int> linkedList = LinkedList<int>(10,array);13 cout << "输出单链表：" << endl;14 linkedList.PrintLinkedList();15 show();16 cout << "单链表的长度:" << linkedList.GetLength() << endl;17 cout << "单链表中第5个元素是：" << linkedList.GetElement(5) << endl; 18 cout << "单链表中元素5的位置是：" << linkedList.GetLocal(5) << endl; 19 show();20 cout << "在单链表的第5个位置上插⼊元素22" << endl;21 linkedList.Insert(5, 22);22 cout << "输出单链表：" << endl;23 linkedList.PrintLinkedList();24 cout << "单链表的长度:" << linkedList.GetLength() << endl;25 show();26 cout << "删除第5位置的元素" << endl;27 linkedList.Delete(5);28 cout << "输出单链表：" << endl;29 linkedList.PrintLinkedList();30 cout << "单链表的长度:" << linkedList.GetLength() << endl;31 show();32 return0;33 }三、运⾏⽰例结果。

c语言单链表的实现
摘要：
一、单链表的概念与特点
1.单链表的定义
2.单链表的特点
二、单链表的实现
1.定义链表节点结构体
2.创建链表
3.插入节点
4.删除节点
5.查找节点
6.遍历链表
7.链表长度
三、单链表的应用
1.数据排序
2.栈与队列的实现
四、总结
正文：
一、单链表的概念与特点
单链表是一种线性数据结构，它由若干个节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。

单链表的特点是插入和删除操作非常方
便，但查找和排序操作的效率较低。

1.单链表的定义
单链表是一种数据结构，它由一个节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。

2.单链表的特点
单链表的特点如下：
（1）插入和删除操作非常方便；
（2）查找和排序操作的效率较低；
（3）内存空间利用率高；
（4）适合动态数据结构。

二、单链表的实现
为了实现单链表，首先需要定义一个链表节点结构体，然后实现创建、插入、删除、查找和遍历等操作。

数据结构之链表篇（单链表，循环链表，双向链表）C语⾔版1.链表 链表是线性表的⼀种，由⼀系列节点（结点）组成，每个节点包含⼀个数据域和⼀个指向下⼀个节点的指针域。

链表结构可以克服数组需要预先知道数据⼤⼩的缺点，⽽且插⼊和删除元素很⽅便，但是失去数组随机读取的优点。

链表有很多种不同类型：单向链表，双向链表和循环链表。

在链表中第⼀个节点叫头节点(如果有头节点）头节点不存放有效信息，是为了⽅便链表的删除和插⼊操作，第⼀个有效节点叫⾸节点，最后⼀个节点叫尾节点。

2.单链表的操作 链表的操作⼀般有创建链表，插⼊节点，删除节点，遍历链表。

插⼊节点的⽅法有头插法和尾插法，头插法是在头部插⼊，尾插法是在尾部插⼊。

下⾯以⼀个带头节点，采⽤尾插法的链表说明链表的各种操作。

1 #include<stdio.h>2 #include<stdlib.h>3//单链表456//节点结构体7 typedef struct node8 {9int value;//数据域10struct node*next;//指针域11 }Node;1213 Node*createList();//创建链表并且返回头节点指针14void deleteNode(Node*head);//删除节点15void insertNode(Node*head);//插⼊节点16void travelList(Node*head);//遍历链表1718int main()19 {20 Node*head=createList();21 travelList(head);22 insertNode(head);23 travelList(head);24 deleteNode(head);25 travelList(head);26return0;27 }28//创建链表，返回头节点指针29 Node*createList()30 {31//采⽤尾插法32 Node*head;//头节点33 Node*tail;//尾节点34 Node*temp=NULL;35int i,value,size;36 head=(Node*)malloc(sizeof(Node));//头节点37 head->value=0;38 head->next=NULL;39 tail=head;40 printf("输⼊节点个数: ");41 scanf("%d",&size);42 printf("输⼊各个节点的值: ");4344for(i=0;i<size;i++)45 {46 scanf("%d",&value);47 temp=(Node*)malloc(sizeof(Node));48 temp->value=value;49 tail->next=temp;//让尾节点的指针域指向新创建的节点50 tail=temp;//尾节点改为新创建的节点51 tail->next=NULL;//让尾节点的指针域为空52 }53return head;54 }55//遍历链表56void travelList(Node*head)57 {58while(head->next!=NULL)59 {60 printf("%d\n",head->next->value);61 head=head->next;62 }63 }64//插⼊节点65void insertNode(Node*head)66 {67int value;68int position;69int pos=0;70 Node*pre=NULL;//⽤来保存要插⼊节点的前⼀个节点71 Node*newNode;72 printf("输⼊要插⼊节点的值: ");73 scanf("%d",&value);74 printf("要插⼊的位置: ");75 scanf("%d",&position);76while(head!=NULL)77 {78 pos++;79 pre=head;80 head=head->next;81if(pos==position)82 {83 newNode=(Node*)malloc(sizeof(Node));84 newNode->value=value;85 newNode->next=pre->next;86 pre->next=newNode;87 }88 }89 }90//删除节点91void deleteNode(Node*head)92 {93int value;94 Node*pre=head;95 Node*current=head->next;96 printf("输⼊要删除节点的值: ");97 scanf("%d",&value);98while(current!=NULL)99 {100if(current->value==value)101 {102 pre->next=current->next;103free(current);//释放空间104break;105 }106 pre=current;107 current=current->next;108 }109 }3.循环链表 循环链表就是让尾节点的指针域不再是NULL,⽽是指向头节点从⽽形成⼀个环。

单链表的实现及其基本操作结点的引⼊链表是⼀种链式存储结构，链式存储结构的特点是⽤⼀组任意的存储单元存储数据元素。

为了能正确表⽰数据元素之间的线性关系，需引⼊结点概念。

⼀个结点表⽰链表中的⼀个数据元素，节点中除了储存数据元素的信息，还必须存放指向下⼀个节点的的指针（单、双链表的最后⼀个节点除外，它们存储的是⼀个空指针NULL）结点的结构如下图所⽰：代码如下：1 typedef struct node{2int data;3struct node* pNext;4 }Node, *PNode;View Code注：这⾥假设结点中储存的是整型 (int) 的数据单链表由多个结点依次连接⽽成，我们不难想象出它结构：我们注意到：在第⼀个结点的前⾯多了⼀个头结点，这是为了处理空表的⽅便⽽引⼊的，它的指针指向链表的第⼀个结点，⽽它的data域不存放任何信息。

单链表的基本操作1.创建链表1 PNode createList()2 {3int len, value;45 PNode pHead = (PNode)(malloc(sizeof(Node)));6 PNode pTail = pHead;7 pTail->pNext = NULL;89 printf("请输⼊你要的节点个数：");10 scanf("%d", &len);11for(int i=1;i<=len;i++){12 printf("请输⼊第%d个节点的值：", i);13 scanf("%d", &value);1415 PNode pNew = (PNode)malloc(sizeof(Node));16 pNew->data = value;17 pTail->pNext = pNew;18 pTail = pNew;19 pTail->pNext = NULL;20 }2122return pHead;23 }View Code2.遍历链表void traverse(PNode pHead){printf("遍历结果为:\n");PNode pTra = pHead;while(pTra->pNext != NULL){printf("%d ", pTra->pNext->data);pTra = pTra->pNext;}printf("\n");}View Code3.判断链表是否为空1bool isEmpty(PNode pHead)2 {3if(pHead->pNext==NULL)4return true;5else6return false;7 }View Code4.链表长度1int length(PNode pHead)2 {3int len = 0;4while(pHead->pNext!=NULL){5 pHead = pHead->pNext;6 len++;7 }8return len;910 }View Code5.插⼊结点1bool insert(PNode pHead, int pos, int val)2 {3if(pos<1 || pos>length(pHead)){4return false;5 }else{6 PNode pInsert = pHead;7for(int i=1;i<pos;i++){8 pInsert = pInsert->pNext;9 }1011 PNode pNew = (PNode)malloc(sizeof(Node));12 pNew->data = val;13 pNew->pNext = pInsert->pNext;14 pInsert->pNext = pNew;1516return true;17 }1819 }View Code6.删除结点1bool del(PNode pHead, int pos)2 {3if(pos<1 || pos>length(pHead)){4return false;5 }else{6 PNode pDel = pHead;7for(int i=1;i<pos;i++){8 pDel = pDel->pNext;9 }1011if(pos==length(pHead)){12free(pDel->pNext);13 pDel->pNext = NULL;14 }else{15 PNode pNext = pDel->pNext->pNext;16free(pDel->pNext);17 pDel->pNext = pNext;18 }1920return true;2122 }232425 }View Code7.查找节点（1）按元素值查找1 PNode locate(PNode pHead, int value)2 {3 PNode p = pHead->pNext;4while(p&&p->data!=value){ //NULL 是 05 p = p->pNext;6 }7return p;8 }View Code（2）按序号查找1 PNode get(PNode pHead, int k)2 {3 PNode p = pHead;4for(int i=1;i<=k;i++){5 p = p->pNext;6 }7return p;89 }View Code完整代码1 #include<stdio.h>2 #include<stdlib.h>3 typedef struct node{4int data;5struct node* pNext;6 }Node, *PNode;78 PNode createList();9void traverse(PNode pHead);10bool isEmpty(PNode pHead);11int length(PNode pHead);12bool insert(PNode pHead, int pos, int val);13bool del(PNode pHead, int pos);14 PNode get(PNode pHead, int k); //按序号查找15 PNode locate(PNode pHead, int value);//按值查找 1617int main(void)18 {19//test2021return0;22 }2324 PNode createList()25 {26int len, value;2728 PNode pHead = (PNode)(malloc(sizeof(Node)));29 PNode pTail = pHead;30 pTail->pNext = NULL;3132 printf("请输⼊你要的节点个数：");33 scanf("%d", &len);34for(int i=1;i<=len;i++){35 printf("请输⼊第%d个节点的值：", i);36 scanf("%d", &value);3738 PNode pNew = (PNode)malloc(sizeof(Node));39 pNew->data = value;40 pTail->pNext = pNew;41 pTail = pNew;42 pTail->pNext = NULL;43 }4445return pHead;46 }474849void traverse(PNode pHead)50 {51 printf("遍历结果为:\n");52 PNode pTra = pHead;53while(pTra->pNext != NULL)54 {55 printf("%d ", pTra->pNext->data);56 pTra = pTra->pNext;57 }58 printf("\n");59 }6061bool isEmpty(PNode pHead)62 {63if(pHead->pNext==NULL)64return true;65else66return false;67 }6869int length(PNode pHead)70 {71int len = 0;72while(pHead->pNext!=NULL){73 pHead = pHead->pNext;74 len++;75 }76return len;7778 }7980bool insert(PNode pHead, int pos, int val)81 {82if(pos<1 || pos>length(pHead)){83return false;84 }else{85 PNode pInsert = pHead;86for(int i=1;i<pos;i++){87 pInsert = pInsert->pNext;88 }8990 PNode pNew = (PNode)malloc(sizeof(Node));91 pNew->data = val;92 pNew->pNext = pInsert->pNext;93 pInsert->pNext = pNew;9495return true;96 }9798 }99100bool del(PNode pHead, int pos)101 {102if(pos<1 || pos>length(pHead)){103return false;104 }else{105 PNode pDel = pHead;106for(int i=1;i<pos;i++){107 pDel = pDel->pNext;108 }109110if(pos==length(pHead)){111free(pDel->pNext);112 pDel->pNext = NULL;113 }else{114 PNode pNext = pDel->pNext->pNext;115free(pDel->pNext);116 pDel->pNext = pNext;117 }118119return true;120121 }122123124 }125126 PNode get(PNode pHead, int k)127 {128 PNode p = pHead;129for(int i=1;i<=k;i++){130 p = p->pNext;131 }132return p;133134 }135 PNode locate(PNode pHead, int value)136 {137 PNode p = pHead->pNext;138while(p&&p->data!=value){ //NULL 是 0 139 p = p->pNext;140 }141return p;142 }View Code。

C++编程语⾔实现单链表详情⽬录⼀、单链表简单介绍⼆、下⾯我们先实现单链表的初始化。

三、实现单链表的插⼊与删除数据⼀、单链表简单介绍⾸先，我们再回顾⼀下线性表的两种存储⽅式——顺序存储与链式存储上图左边为顺序存储，右边为链式存储之前我们利⽤数组来实现顺序表，对于顺序表的优点缺点，总结来说就是，查找⽅便，增删复杂。

线性表之顺序存储的优缺点⽽链表特点可以说恰恰相反，增删⽅便，查找复杂。

今天实现的是链表中最简单的⼀种——单链表（每个结点中只含有⼀个指针域）对于链表我们只知道它每个结点的存储的物理地址是不连续的，但逻辑上还是符合线性表“⼀对⼀”的特点。

因此，我们就需要⽤“线”（指针）把这些不连续的结点按顺序连接起来。

链表的结点在内存中存储不连续通过指针把每个结点按顺序连起来到这⾥我们可以发现，要想表⽰链表中的结点，光存储结点的数据是不够的，还得有指针。

因此，单链表的结点结构如下：数据域存储数据，指针域存储指针//================线性表的单链表存储结构=================typedef struct LNode {ElemType data;//数据域struct LNode *next;//指针域}LNode;注意：因为指针是指向每个结点的，也就是指向struct LNode这个⾃定义的结构体类型，所以指针的类型就是struct LNode*。

⼆、下⾯我们先实现单链表的初始化。

单链表的初始化其实就是创建⼏个结点，然后⽤指针把他们连接起来。

先创建⼀个头指针，实际上就是创建⼀个头结点，然后头指针指向头结点就OKLNode* CreateList_L(int n) {//顺位序输⼊n个元素的值，建⽴带表头结点的单链线性表LLNode *p = (LNode*)malloc(sizeof(LNode));//创建头结点（p也就是头指针）LNode *temp = p;//声明⼀个指针指向头结点,⽤于遍历链表(不是头指针，因为它只是暂时指向头结点) //⽣成链表for (int i = n; i > 0; --i){LNode *node = (LNode *)malloc(sizeof(LNode));//创建结点if (node){//分配地址成功scanf_s("%c", &(node->data));node->next = NULL;//建⽴新结点与直接前驱结点的逻辑关系temp->next = node;temp = temp->next;}else {//如果分配地址失败，则返回错误信息printf("结点创建失败！\n");}}return p;}三、实现单链表的插⼊与删除数据单链表插数据情况观察可知，我们要实现插⼊操作，需要的操作是⼀样的。

链表之循环单链表（⽤C语⾔描述）上回说到建⽴链表的三种形式，分别是头插法，尾插法，和尾插法MAX下⾯讲⼀下循环单链表循环单链表，字⾯意思，就是单链表循环了起来，尾节点在输⼊结束后不会指向NULL，⽽是指向了头节点head 酱紫，链表就循环了起来下⾯是代码实现#include <stdio.h>#include <stdlib.h>typedef char datatype;typedef struct node{datatype data;struct node *next;int length;}linkList;linkList *CREAT(linkList *L){L->length = 0;linkList *head,*r,*s;head = (linkList *)malloc(sizeof(linkList));r = head;char ch;ch = getchar();while(ch!='$'){s = (linkList *)malloc(sizeof(linkList));L->length++;s->data = ch;r->next = s;r = s;s->next = head;// char a = getchar();// 如果使⽤上⾯这⼀句，在输⼊data的时候可以在两个字符间输⼊空格ch = getchar();};return r;}void PUT(linkList *L,linkList *r){int i = 0;linkList *pt;pt = r;pt = pt->next->next;while(i<L->length)//如果你想测试⼀下⾃⼰写的代码会不会循环起来，可以给length+2以上，看看会不会输出//因为在CREAT（）的时候，我是⽤的是尾插法MAX ，就是在整个链表的前⾯加上⼀个空的节点，所以输出不会显⽰这个节点的内容 {printf("%c ",pt->data);pt = pt->next;i++;};printf("\n");}int main(void){linkList L;PUT(&L,CREAT(&L));return 0;}//这个代码的算法实现都是⽐较简单易懂的，如果不是很清楚链表是怎样构建的话，可以康⼀康我的上⼀篇blog//希望能对初学数据结构的同学们有⼀点帮助。

单链表的表⽰和实现-数据结构原⽂地址：基本概念链式存储结构，不要求逻辑上相邻的元素在物理上也相邻，没有顺序存储结构所具有的的弱点（在作插⼊或删除操作是，需移动⼤量元素），但同时也失去了顺序表可随机存取的优点。

单链表的结点由数据域和指针域构成，多个结点链结成⼀个链表。

代码实现# include <stdio.h># include <stdlib.h># define OK 1# define ERROR -1# define OVERFLOW -2typedef int ElemType;typedef int Status;typedef struct Lnode {ElemType data;struct Lnode * next;} Lnode, * LinkList;Status GetElem_L(LinkList L, int i, ElemType & e);Status ListInsert_L(LinkList & L, int i, ElemType e);Status ListDelete_L(LinkList & L, int i, ElemType & e);void CreateList_L(LinkList & L, int n);void MergeList_L(LinkList & La, LinkList & Lb, LinkList & Lc);Status ShowList_L(LinkList L);int main(void){//测试函数LinkList L;CreateList_L(L, 8);ShowList_L(L); //print createListInsert_L(L, 3, 3);ShowList_L(L); //print insertElemType e;ListDelete_L(L, 4, e);printf("delete e = %d\n", e); //print e deleteShowList_L(L); //print deleteGetElem_L(L, 5, e);printf("getelem e = %d\n", e); //print getelemLinkList Lb;CreateList_L(Lb, 5);ShowList_L(Lb); //print LbLinkList Lc;MergeList_L(L, Lb, Lc);ShowList_L(Lc); //print Lcreturn 0;}Status GetElem_L(LinkList L, int i, ElemType & e){//算法2.8//L为带头结点的单链表的头指针Lnode * p = L->next;int j = 1;for(j = 1; p && j < i; j++) {p = p->next;}if(!p) {return ERROR;}e = p->data;return OK;}Status ListInsert_L(LinkList & L, int i, ElemType e){//算法2.9//在带头结点的单链线性表L中第i个位置之前插⼊元素eLnode * p = L->next;int j = 1;Lnode * s = (Lnode * ) malloc(sizeof(Lnode));s->data = e;for(j =1; p && j < i - 1; j++) {p = p->next;}if(!p) {return ERROR;}s->next = p->next;p->next = s;return OK;}Status ListDelete_L(LinkList & L, int i, ElemType & e){//算法2.10Lnode * p = L->next;int j = 1;for(j = 1; p && j < i - 1; j++) {p = p->next;}if(!p) {return ERROR;}Lnode * q;q = p->next;e = q->data;p->next = q->next;free(q);return OK;}void CreateList_L(LinkList & L, int n){//算法2.11//逆位序输⼊n个元素的值，建⽴带表头结点的单链线性表L L = (LinkList) malloc(sizeof(Lnode));L->next = NULL;for(int i = 0; i < n; i++) {Lnode * p = (Lnode * ) malloc(sizeof(Lnode));scanf("%d", & p->data);p->next = L->next;L->next = p;}}void MergeList_L(LinkList & La, LinkList & Lb, LinkList & Lc) {//算法2.12//归并⾮递减排列的La和Lb到Lc//⽤La的头结点作为Lc的头结点//本算法具有副作⽤Lnode * pa = La->next;Lnode * pb = Lb->next;Lc = La;Lnode * pc = Lc;while(pa && pb) {if(pa->data <= pb->data) {pc->next = pa;pc = pc->next;pa = pa->next;} else {pc->next = pb;pc = pc->next;pb = pb->next;}}pc = (pa ? pa : pb);free(Lb);}Status ShowList_L(LinkList L){Lnode * p = L->next;Lnode * p = L->next;if(!p) {return ERROR;}while(p) {printf("%d ", p->data);p = p->next;}putchar('\n');return OK;}算法分析GetElem_L()、ListInsert_L()、ListDelete_L()的时间复杂度均为O(n)。