参考书：王道考研数据结构

（此贴为博主学习408的笔记，因博主也是学习者，个人总结如有错误欢迎指正。如有侵权请告知，马上删除致歉）​​

单链表定义

单链表是线性表的链式存储，通过一组任意的存储单元来存储线性表的数据元素。每个结点包含数据域和指针域。单链表只有一个指向后继结点的next后继指针。

单链表可以解决顺序表需要大量连续的存储单元的缺点，其离散的分布在存储空间内，逻辑上连续，物理上不连续。因为是非随机存取的特性，所以在查找某一个结点的时候，需要从头遍历，依次查找。

#include <stdio.h>#include <stdlib.h>/**********************************************制作人：祝星。项目名称：数据结构-单链表的基本操作（C语言实现）完成时间：11月4日完成内容：单链表的创建，修改，增加，删除，销毁。更新时间：7月20日更新内容：头插法优化，销毁功能优化（基于新王道知识点）具体内容，头插法，尾插法，按位查找，按位删除，指定结点后插，指定位序后插，指定位序前插，指定结点前插，求表长，遍历输出，销毁单链表运行环境：win10程序环境：VC++文件语言：C语言文件类型：.cpp注：1.VC++的.cpp环境，&为取地址。2.LNode *等价于LinkList，前者强调这是结点，后者强调这是链表，合适的地方使用合适的名字，代码可读性更高。***********************************************//*定义有头结点单链表的结点结构*/typedef struct node{int data; //每个结点存放的数据类型struct node *next;//结点存放的指针域指向下一个结点}LNode, *LinkList;//前者强调这是结点，后者强调这是链表/************************函数名：尾插法创建单链表参数：L返回值：创建好的表*************************/LinkList T_InitList(LinkList &L){int x; //初始化输入的值L = (LinkList)malloc(sizeof(LNode));//动态申请头结点LNode *s,*r = L;//初始化两个结点指针指向头结点L->next=NULL;//头指针指向NULL，防止脏数据printf("输入（9999结束）");scanf("%d",&x);//输入插入的值，输入9999结束while(x!=9999){s = (LNode*)malloc(sizeof(LNode));//动态申请一个存放插入值的结点s->data=x;//将输入的值赋值给新申请结点r->next=s;//将指向头结点的r的next指针指向sr=s;//将r的指针指向sprintf("输入（9999结束）");scanf("%d",&x);}r->next=NULL;//r的next指针指向NULLreturn L;//返回创建好的表}/************************函数名：头插法创建单链表参数：L返回值：创建好的表*************************/LinkList H_InitList(LinkList &L){int x;//初始化输入的值L = (LinkList)malloc(sizeof(LNode));//动态申请头结点LNode *s;//初始化一个指针指向头结点L->next=NULL;//头指针指向NULL，防止脏数据printf("输入（9999结束）");scanf("%d",&x);//输入插入的值，输入9999结束while(x!=9999){s = (LNode*)malloc(sizeof(LNode));//动态申请一个存放插入值的结点s->data=x;//将输入的值赋值给新申请结点s->next=L->next;//s的next指针指向头指针指向的NULLL->next=s;//头结点的NEXT指针指向sprintf("输入（9999结束）");scanf("%d",&x);}return L;//返回创建好的表}/*******************************函数名：按位查找参数：L,i返回值：返回结点指针值*******************************/LNode *GetElem(LinkList L,int i){int j=1;//因为有头结点，所以从1开始遍历if(i<0){//判断查找的位置是否合法printf("数值非法");}LNode *p = L->next;//初始化结点指针while(p!=NULL&&j<i){p=p->next;j++;}return p;}/*******************************函数名：按位删除结点参数：L,i返回值：返回结点指针值*******************************/LinkList DeleteNode(LinkList &L,int i){LNode *p;p=GetElem(L,i-1);//调用按位查找函数if(p==NULL){//找到待删除第i个元素的前驱结点return false; //如果此前去结点为空或者前驱结点的下一个结点为空} //就是说该i位置为NULL，不能被删除，没有值能被删除if(p->next==NULL){return false;}LNode *q=p->next;//初始化q指向前驱结点p的下一个，就是第i位置元素p->next=q->next;//p指向q的下一个结点free(q);//删除qreturn L;}/*指定结点的后插*/LinkList InsertNextNode(LinkList &L,LNode *p,int e){if(p==NULL)return false;LNode *s = (LNode*)malloc(sizeof(LNode));//申请不到内存空间则返回falseif(s==NULL)return false;s->data=e;s->next=p->next;p->next=s;return L;}/*指位序后插入*/LinkList InsertNNode(LinkList &L,int i,int e){if(i<1)return false;LNode *s;int j=0;s=L;while(s!=NULL&&j<i){s=s->next;j++;}if(s==NULL)return false;return InsertNextNode(L,s,e);}/*指定结点的前插*/LinkList InsertPriorNode(LinkList &L,LNode *p,int e){if(p==NULL)return false;LNode *s = (LNode*)malloc(sizeof(LNode));if(s==NULL)return false;s->data=e;s->next=p->next;p->next=s;return L;}/*指位序前插入*/LinkList InsertPNode(LinkList &L,int i,int e){LNode *p = GetElem(L,i-1);return InsertPriorNode(L,p,e);}/*按值查找*/int LocateElem(LinkList L,int e){int i=1;LNode *p = L->next;while(p!=NULL&&p->data!=e){p=p->next;i++;}return i;}/*求表长*/int Length(LinkList L){int len=0;LNode *p=L;while (p->next!=NULL){p=p->next;len++;}return len;}/*遍历输出*/void Show(LinkList L){printf("当前单链表的所有元素：【head】->");LNode *p;p =L->next;while(p!=NULL){printf("[%d]->",p->data);p=p->next;}printf("NULL");printf("\n");printf("当前表长为%d\n",Length(L));printf("-----------------------------------------------------------\n");}void DestroyList(LinkList &L){LNode *p ,*q;p= L->next;q=p;while(p!=NULL){q=p->next;free(p);p = q;}L->next = NULL;printf("\n销毁成功\n");}/*主函数*/int main(){LinkList l;l = T_InitList(l);Show(l);DeleteNode(l,3);printf("删除第三个位置的元素后：");Show(l);printf("在第二个位置后插入99：");InsertNNode(l,2,99);Show(l);printf("在第4个位置前插入101：");InsertPNode(l,4,101);Show(l);printf("101元素的位置是%d \n",LocateElem(l,101));DestroyList(l);Show(l);return 0;}