前言：
为避免在使用线性表顺序存储结构的时，需插入和删除需大量移动元素的弊端。
本节讨论线性表的另外一种表示方法---链式存储结构：
由于它不要求逻辑上相邻的元素在物理位置上相邻，因此它对元素的插入和删除没有顺序结构所具有的弊端，但是也失去了顺序表随机存取的优点。
目录：
1.线性表的链式表示和实现
1.1线性链表
单链表（指针型线性链表）
静态链表
1.2循环链表
1.3双向链表
正文：
1.线性表的链式表示和实现
1.1线性链表
线性链表的特点：
是用一组任意的存储单元存储线性表的数据元素（存储单元可以连续，也可以不连续）。因此，为表示 数据元素 ai 和其直接后继元素 a(i+1)之间逻辑关系，对ai来说，除存储其本身的信息外，还需存储一个指向其直接后继的信息（即直接后继的存储位置）。这两部分信息组成数据元素ai的存储映像，称为结点。它包括两个域：其中存储数据元素信息的域称为数据域，存储后继元素位置的域称为指针域。
指针域中存储的信息称作指针或链。n个结点链结成一个链表，即为线性表
（a1, a2, ...., an）
的链式存储结构。又由于此链表的每个节点中只包含一个指针域，故又称线性链表或单链表。
链表的机构描述：
整个链表的存取必须从头指针开始进行，头指针指示链表中的第一个结点的存储位置。同时，由于最后一个数据元素没有直接后继，则线性链表中最后一个结点的指针为 “空” （NULL）,如下图所示：
单链表可以由头指针唯一确定，在Ｃ语言中可用 “结构指针” 来描述。
线性表的单链表存储结构：
typedef struct LNode{
ElemType data;
struct LNode *next；
}LNode, *LinkList;
假设L是LinkList型的变量，则L为单链表的头指针，它指向表中的第一个结点。若L为空（L=NULL），则所表示的单链表为“空”，表长度为 0；
有时候，我们在第一个结点前面，附加一个结点，称之为头结点。头结点的数据域可以不存储信息，也可存储链表长度等信息，头结点的指针域存储指向第一个结点的之指针。如下图：a中 头结点指向第一个结点， b中头结点的指针域为NULL
在单链表结点的创建和删除的时候，我们会用到C语言中的两个标准函数 malloc 和free。
假设 P 和 q 是LinkList 型的变量，则执行 p=(LinkList)malloc(sizeof(LNode))的作用是由系统生成一个LNode型的结点，同时将该结点的起始位置复制给指针变量 p ；反之，执行 free(q) 的作用是由系统回收一个LNode型的结点，回收后的空间可以备作再次生成结点时用。
每个单链表占用的空间都不需要预先分配，而是应需求通过 malloc 即时生成。
代码实现：
#include<stdio.h>
#include<stdlib.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2//Status是函数的类型，其值是函数结果状态码typedef int Status;typedef int ElemType;typedef struct LNode{ ElemType data; //单链表中结点的数据域 struct LNode *next; //结点的指针域}LNode,*LinkList;//为单链表L,创建n个元素void CreateList_L(LinkList L,int n){ //初始化头结点 L=(LinkList)malloc(sizeof(LNode)); //生成头结点 L->next=NULL; for(int i=0;i<n;i++){ LNode *q=(LinkList)malloc(sizeof(LNode)); //创建新结点 scanf("%d",&q->data); //输入元素 q->next=L->next; //插入到表头 L->next=q; } }//在单链表中，取得第i个位置的值必须从头开始找起，因为每个结点元素的位置信息只能通过其直接前继结点确定//获取L 中第i个元素的值，并用 e 返回。Status GetElem_L(LinkList &L,int i,ElemType &e){ //此处L为带有头结点的单链表 LNode * q; q=L->next; //p指向第一个结点 int j=1; while(q&&j<i){ //移动指针的错误写法：q++; 因为在链式存储结构中存储地址不一定是连续的 q=q->next; j++; } if(j!=i) return ERROR; e=q->data; return OK;}//时间复杂度为 O（n）//插入元素，在L中第i个位置之前插入数据 eStatus ListInsert_L(LinkList &L,int i,ElemType e){ //1.找到指向 第 i-1 处元素的指针 LNode * q; q=L; // q指向头结点 int j=0; while(q&&j<(i-1)){ q=q->next; //后移结点 j++; } //正确j的可能值：0，(i-1), if(!q||i<1) //1.q为NULL(i大于表长+1) 2.i不能小于1 return ERROR; LNode * s; s=(LinkList)malloc(sizeof(LNode)); //生成新节点 s->data=e; //新结点数据域inti s->next=q->next; q->next=s; //插入新结点 return OK;}//时间复杂度为 O（n）//删除元素，在L中删除位置为i的元素，并用将返回值存储在e中。Status ListDelete_L(LinkList &L,int i,ElemType &e){ //1.找到指向 第 i-1 处元素的指针 LNode * q; q=L; // q指向头结点 int j=0; while(q&&j<(i-1)){ q=q->next; //后移指针 j++; } if(!(q->next)||i<1) //1.q->next不能为NULL(i位置不存在) 2.i不能小于1 return ERROR; e=q->next->data; //将被删除的值保存在e中 LNode * tem=q->next; //保存 将被删除元素的坐在位置 q->next=q->next->next; //删除元素 free(tem); //释放被删除元素占用的内存空间 return OK;}//时间复杂度为 O（n）//合并两个非递减的单链表，使得合并后的单链表仍为非递减Status MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){ LNode *qa=La->next; //指向La 表的第一个元素 LNode *qb=Lb->next; //指向Lb 表的第一个元素 LNode *qc=Lc; while(qa&&qb){ //如果都没有达到单链表的末尾 if(qa->data<=qb->data){ qc->next=qa; qa=qa->next; }else{ qc->next=qb; //增加Lc表的数据元素 qb=qb->next; //Lb指针后移 } qc=qc->next; //qc指向Lc的最后一个元素 } //Lc的最后一个元素直接指向没有比较完的链表 if(qa) qc->next=qa; if(qb) qc->next=qb; //释放头结点 free(La); free(Lb); return OK;}//链表进行合并时，不需要新建表的结点空间，而是将La 和Lb 中结点按新的关系连接起来void printAllValues(LinkList &L){ if(!L->next) printf("%s\n","此表为空但链表"); LNode *q; q=L; while(q->next){ q=q->next; //指针后移 printf("地址：%p",q); printf("值：%d\n",q->data); }}//时间复杂度为 O（n）void main(int argc, char *argv[]){ LNode *L; L=(LinkList)malloc(sizeof(LNode)); //生成头结点 L->next=NULL; printf("%s\n","执行插入操作..."); ListInsert_L(L,1,9); ListInsert_L(L,1,7); ListInsert_L(L,1,4); ListInsert_L(L,1,2); printAllValues(L); ElemType e; GetElem_L(L,2,e); printf("获取第2个元素为：%d\n",e); printf("%s\n","执行删除操作..."); if(ListDelete_L(L,3,e)==1) printf("%s\n","删除成功"); printAllValues(L); printf("删除的元素为：%d\n",e); LNode *La; La=(LinkList)malloc(sizeof(LNode)); //生成头结点 La->next=NULL; printf("%s\n","插入La..."); ListInsert_L(La,1,9); ListInsert_L(La,1,7); ListInsert_L(La,1,4); ListInsert_L(La,1,2); printAllValues(La); LNode *Lb; Lb=(LinkList)malloc(sizeof(LNode)); //生成头结点 Lb->next=NULL; printf("%s\n","插入Lb..."); ListInsert_L(Lb,1,11); ListInsert_L(Lb,1,9); ListInsert_L(Lb,1,5); ListInsert_L(Lb,1,1); printAllValues(Lb); LNode *Lc; Lc=(LinkList)malloc(sizeof(LNode)); //生成头结点 Lc->next=NULL; MergeList_L(La,Lb,Lc); printf("%s\n","合并后的Lc..."); printAllValues(Lc); }
运行结果：
