本文介绍一下线性表的链式存储结构，以及相关的算法实现，主要是记录并且梳理一下自己实现的算法。本文的参考书目是严蔚敏的《数据结构（C语言版）》。注意这本书在算法实现中用了C++中的引用，而没有用C语言中的指针，所以文件命名后缀为.cpp。
顺序表的优缺点线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻，因此可以随机存取表中任一元素，他的存储位置可用一个简单的公式来表示。但是这个特点也成为了顺序存储结构的缺点：在作插入或者删除操作时，需要移动大量的元素。但是使用单链表就可以完美避免这个问题，单链表可以保持元素的逻辑顺序不变，但是每个元素的实际位置是随机的。
单链表的介绍单链表的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此对于数据元素
，不仅要存储其本身的信息，还需要储存其直接后继的信息，这两部分信息组成数据
的存储映像，称为结点（Node）。结点包括两个域：存储元素自身信息的域称为数据域；存储直接后继元素位置的域称为指针域。n个结点组成一个链表，即为线性表的链式存储结构。由于这种链表的每个结点只包含一个指针域，所以又称为单链表。
举例介绍下表为线性表
的线性链表的存储结构。链表从头指针开始，头指针指向链表的第一个数据元素。也可以不创建没有头指针的链表，但是和有头指针的链表相比在插入和删除元素等操作中更加复杂，因此本文默认使用带有头指针的链表。最后一个元素没有直接后继，所以指针指向为空(NULL)。
存储地址数据域指针域12FBAGNULL35CED头结点(head)23单链表的元素之间的关系如下图所示，但是和线性表不同的是每个元素的实际位置是随机的，不连续的。
单链表下面开始用代码实现单链表
单链表的结构体本文将链表的元素定义为int型变量，结构体就是由数据域和指针域组成。
//结果状态定义#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2//元素数据类型定义typedefintStatus;typedefintElemType;//-----线性表的单链表存储结构-----typedefstructLNode{ElemTypedata;//元素域structLNode*next;//指针域}LNode,*LinkList;单链表的初始化
空的单链表就只有一个头结点，并且头结点的指向NULL
StatusInitList_L(LinkListL){L=(LinkList)malloc(sizeof(LNode));if(!L)returnERROR;L-next=NULL;returnOK;}单链表的元素获取
元素获取很简单，就是设置一个计数器j控制指针p移动的次数，最终使指针p指向第i个元素的地址。
StatusGetElem_L(LinkListL,inti,ElemTypee){//L为带头结点的单链表的头指针//当第i个元素存在时，其值赋给e并返回OK，否则返回ERRORLinkListp=L-next;//p指向第一个结点intj=1;//j为计数器while(pji){//直到p指向第i个元素或p指向NULL结束循环p=p-next;j++;}if(!p
ji)//第i个元素不存在returnERROR;e=p-data;//获取第i个元素returnOK;}单链表的插入
单链表插入元素的主要思想是，先找到要插入位置i的前一个位置i-1的元素，p指向第i-1个元素。然后创建要插入的结点s，将s插入结点i和结点i-1之间。
元素插入的过程如下图，p-next原来是指向元素F的地址，现在我们要插入结点s，就先让s指向元素F,即：s-next=p-next，然后让p指向结点s，即p-next=s。
元素的插入这里有个要注意的地方，不能先让p指向结点s，再让s指向元素F，因为如果先执行p-next=s，再执行s-next=p-next，很显然相当于s的后继是s自己，并没有指向原来p的后继。所以插入操作顺序绝对不能错！
StatusListInsert_L(LinkListL,inti,ElemTypee){//在带头结点的单链线性表L中的第i个位置之前插入元素eLinkListp=L;//p指向头结点intj=0;//j为计数器while(pji-1){//直到p指向第i-1个元素和p指向NULL时结束循环p=p-next;j++;}if(!p
ji-1)//i大于1或者大于表长加1returnERROR;LinkLists=(LinkList)malloc(sizeof(LNode));//生成新结点s-data=e;//插入结点s-next=p-next;p-next=s;returnOK;}单链表的删除
单链表的删除也是先找到要插入位置i的前一个位置i-1的元素，p指向第i-1个元素。然后让q指向第i个位置元素，即：q=p-next。
元素删除操作如下图，要删除元素C，我们只需要将p的指向元素C的后继元素D，即：p-next=q-next（也可以写成p-next=p-next-next）,然后直接释放q指向的元素C的内存,即：free(q)。此时删除操作就完成了！
元素的删除StatusListDelete_L(LinkListL,inti,ElemTypee){//在带头结点的单链表L中，删除第i个元素，并由e返回其值LinkListp=L;intj=0;while(p-nextji-1){//寻找第i个结点，并令p指向其前驱p=p-next;j++;}if(!(p-next)
ji)returnERROR;LinkListq=p-next;//删除结点并且释放结点内存p-next=q-next;e=q-data;free(q);returnOK;}单链表的创建
再看完插入操作后再来看链表的创建就会很简单，其实就是在执行插入操作，其中的思想是一样的。链表的创建有正序和逆序两种顺序。
我们先介绍逆序创建，也就是头插法。我们先建立一个带有头结点的单链表L，然后创建要插入的结点p，然后每次将p插入到头结点之后，这样就得到了逆序的链表。
头插法voidCreatListHead_L(LinkListL,intn){//逆位序输入n个元素的值，建立带头结点的单链表LLinkListp;L=(LinkList)malloc(sizeof(LNode));L-next=NULL;//先建立一个带有头结点的单链表printf("pleaseenter:");for(inti=0;in;i++){p=(LinkList)malloc(sizeof(LNode));//生成新结点scanf("%d",p-data);//输入元素值p-next=L-next;L-next=p;//插入元素到表头后}}
正序创建（尾插法）就是每次都将要插入的元素插入链表的尾部，这样就得到了正序的链表。创建主要的操作和头插法一样，只是插入的位置不同，如图
尾插法voidCreatListTail_L(LinkListL,intn){//顺位序输入n个元素的值，建立带表头结点的单链表L，和逆序类似LinkListp,r;L=(LinkList)malloc(sizeof(LNode));L-next=NULL;//先建立一个带有头结点的单链表r=L;printf("pleaseenter:");for(inti=0;in;i++){p=(LinkList)malloc(sizeof(LNode));//生成新结点scanf("%d",p-data);//输入元素值r-next=p;r=p;//插入元素到表头后}r-next=NULL;//表尾结点指向NULL}打印链表
打印链表其实就是利用指针遍历输出整个链表，指针为空时循环停止，遍历结束
voidListPrint_L(LinkListL){LinkListp;p=L-next;while(p){printf("%d",p-data);p=p-next;}printf("\n");}合并两个链表
合并两个元素按值非递减排列的单链表La和Lb为一个链表Lc。主要思想就是分别按顺序遍历La和Lb，然后比较遍历的元素的大小，较小的元素放入Lc，然后指针后移，直到某一个链表为空时结束，最后再将链表剩余未比较的元素放入Lc中。主要过程如下图
合并操作voidMergeList_L(LinkListLa,LinkListLb,LinkListLc){//已知单链表La和Lb的元素按值非递减排列。//归并La和Lb得到新的单链表Lc，Lc的元素按值非递减排列。LinkListpa=La-next;LinkListpb=Lb-next;LinkListpc=La;Lc=La;//La的头结点作为Lc的头结点while(papb){//比较元素大小按顺序插入Lcif(pa-data=pb-data){pc-next=pa;pc=pa;pa=pa-next;}else{pc-next=pb;pc=pb;pb=pb-next;}}pc-next=pa?pa:pb;//插入剩余段free(Lb);//释放Lb的头结点}算法测试
intmain(void){LinkListL;ElemTypee1,e2;InitList_L(L);//初始化链表LCreatListTail_L(L,10);//尾插法创建长度为10的链表ListPrint_L(L);//打印链表ListInsert_L(L,3,33);//在第3个位置插入元素33ListPrint_L(L);//打印链表ListInsert_L(L,12,11);//在链表尾部(12个位置)插入元素11ListPrint_L(L);//打印链表ListDelete_L(L,4,e1);//删除链表第4个元素，用e1获取元素的值printf("e1=%d\n",e1);ListPrint_L(L);//打印链表ListDelete_L(L,11,e2);//删除链表第11个元素(最后一个元素)，用e2获取元素的值printf("e2=%d\n",e2);ListPrint_L(L);//打印链表//Merge_L()函数测试LinkListLa,Lb,Lc;InitList_L(La);InitList_L(Lb);InitList_L(Lc);CreatListTail_L(La,5);//尾插法创建长度为5的Laprintf("La=");ListPrint_L(La);//打印LaCreatListTail_L(Lb,5);//尾插法创建长度为5的Lbprintf("Lb=");ListPrint_L(Lb);//打印LbMergeList_L(La,Lb,Lc);//合并操作printf("Lc=");ListPrint_L(Lc);//打印Lcreturn0;}运行结果
pleaseenter:35678910123567891e1=312567891e2=11125678910pleaseenter:La=pleaseenter:Lb=Lc=总结
以上几个算法体现了链表的核心思想，尤其是插入和删除。还有一些长度获取，清空链表，销毁链表等算法没有介绍，这些算法不是很复杂，可以自己尝试添加。下篇文章介绍双向链表。
预览时标签不可点收录于话题#个上一篇下一篇