目录

一 单链表的基本概念

1.单链表的定义

2.区分两个概念

3.单链表的特点

二 单链表的表示

三 单链表的基本操作

1.单链表的初始化

2.单链表的创建

头插法

 尾插法

 3.单链表的插入

按位序插入

指定节点的后插操作

指定节点的前插操作

 4.单链表的删除

按位序删除

指定节点的删除

指定节点后的删除

 5.单链表的查找

按位查找

按值查找

 6.求表长

本文是我在复习 计算机基础--数据结构 的一些学习笔记，希望通过这样的方式，在掌握知识的同时，将我学到的东西分享给更多的人，能给他们带来帮助，我就很开心了。

若有志同道合之人，可以加入我，一起学习计算机知识，一起记录自己的所学。

若本文有错误或不足之处，请各位大佬批评指正，不吝赐教，我定当认真反思改进，谢谢！

希望各位前进的路上不迷茫，都有光明的未来。

一 单链表的基本概念

1.单链表的定义

线性表的链接表示又称单链表，它是通过一组任意的存储单元来存储线性表中的数据元素。为表示每个元素与其后继元素之间额逻辑关系，每个元素除了需要存储自身的信息外，还要存放一个指示其后继的指针。

单链表的每个节点包括两个域：数据域--存放元素本身的信息；指针域--存放其后继节点的存储位置。由于最后一个元素没有后继，它的指针不指向任何节点，称为空指针。指向链表中的第一个节点的指针称为该链表的头指针。

2.区分两个概念

头节点：为了方便操作，在单链表第一个节点之前附加一个节点，称为头节点。头节点通常不存储信息，它的指针指向单链表的第一各节点。

头指针：指向单链表中第一个节点的指针称为该链表的头指针

3.单链表的特点

优点：不要求大片连续空间，改变容量容易。

缺点：不可随机存取，要耗费一定空间存放指针。 

二 单链表的表示

typedef int ElemType;struct LinkNode {     //单链表节点类型 ElemType data;    //数据域 struct LNode* next;      //指针域 };typedef struct LinkNode PNode;//节点typedef struct LinkNode* LinkList;   //单链表类型

三 单链表的基本操作

为了操作方便，本文的所有操作均在带头节点的情况下讨论

1.单链表的初始化

LinkList InitLinkList(void){LinkList llist = (LinkList)malloc(sizeof(struct LinkNode));  //申请表头节点内存空间if (llist == NULL)//表头节点内存空间申请失败{return NULL;}llist->next = NULL;     //表头姐节点内存空间申请成功，表头节点的指针指向空return llist;}

2.单链表的创建

头插法

LinkList HeadInsertList(LinkList llist) //逆向建立单链表{PNode* s;int x;llist = (LinkList)malloc(sizeof(PNode));  //创建头节点llist->next = NULL;  //初始化空链表scanf("%d", &x);     //输入节点值while (x != 99999)   //输入99999表示结束{s = (PNode*)malloc(sizeof(PNode));    //创建新节点s->data = x;     s->next = llist->next;llist->next = s; //将新节点插入表中，llist为头节点scanf("%d", &x);}return llist;}

 尾插法

LinkList TailInsertList(LinkList llist)//正向建立单链表{ int x; //设ElemType为整型llist = (PNode*)malloc(sizeof(PNode));    //建立头节点PNode* s;     PNode* r;     //r为表尾指针scanf("%d", &x);     //输入节点的值while (x != 99999)   //输入99999表示结束，结束标志可自由选择{s = (PNode*)malloc(sizeof(PNode));s->data = x;r->next = s;     //在r节点后插入新的元素xr = s;    //r指向新的表尾节点scanf("%d", &x);}r->next = NULL;     //尾节点指针置空return llist;}

 3.单链表的插入

按位序插入

在表llist的第i个位置上插入指定元素e，可以把头节点看作第"0"个节点

bool InsertLinkList(LinkList* llist, int i, ElemType e){if (i < 1)    //位序不合法，报错      {return false;}int j = 0;    //当前p指向的是第几个节点，指向头节点，头节点是第0个节点PNode* p = llist;    //指针p指向当前扫描到的节点while (p != NULL && j next;j++;}if (p == NULL)      //i值不合法，报错{return false;}PNode* s = (PNode*)malloc(sizeof(PNode));   //申请新的节点内存空间if (s == NULL)//新节点内存申请失败{return false;}s->data = e;s->next = p->next;p->next = s;  //将s链接到p之后return true;}

指定节点的后插操作

在p节点之后插入元素e

bool InsertLinkListPost(LinkList llist, PNode* p, ElemType e){if (p == NULL)      //p节点不合法，报错{return false;}PNode* s = (PNode*)malloc(sizeof(PNode));  //申请新节点内存空间if (s == NULL)//新节点内存申请失败{return false;}s->data = e;s->next = p->next;p->next = s; //新节点s链接到p之后return true;}

指定节点的前插操作

在p节点之前插入元素e

法一

bool InsertLinkListPre(LinkList llist, PNode* p, ElemType e){if (p == NULL)      //p节点不合法，报错{return false;}PNode* s = (PNode*)malloc(sizeof(PNode));    //申请新节点的内存空间if (s == NULL)      //新节点内存申请失败{return false;}s->next = p->next;  p->next = s; //新节点链接到p后面s->data = p->data;  //将p中的元素复制到s中p->data = e; //用e覆盖p中的元素return true;}

法二

//在单链表中求p所指节点的前驱节点PNode LocatePreLinkNode(LinkList llist, PNode p){if (llist == NULL){return NULL;}PNode* q = llist;while (q != NULL && q->next != p)  //节点不为空且下一节点不为p{q = q->next;     //找p的前驱节点}return q;}bool InsertLinkListPost(LinkList llist, PNode* p, ElemType e){PNode* pre = LocatePreLinkNode(llist, p);if (pre == NULL)//pre为空，报错{return false;}PNode* s = (PNode*)malloc(sizeof(PNode));if (s == NULL) //新节点申请失败，报错{return false;}s->data = e;s->next = pre->next;  //将新节点连接到pre节点后面pre->next = s;return true;}