线性表的表示与实现-------链式结构
链表：顺序查找，插入删除操作效率高。
单链表
用一组地址任意的存储单元存放线性表中的数据元素。在物理上不一定相邻。
结点(表示数据元素或数据元素的映象)=元素(数据元素的映象) + 指针(指示后继元素存储位置)
以“结点的序列”表示线性表 称作链表
线性表的地址（线性表的头指针）是以线性表中第一个数据元素的存储地址
单链表的描述定义
- Typedef struct LNode {
- ElemType data; // 数据域
- struct Lnode *next; // 指针域
- } LNode, *LinkList;
- LNode为结点 LinkList为指向链表的指针
- LinkList L； // L 为单链表的头指针，是一个地址
要注意的是：以上定义了一个单链表，是一个地址，逻辑上的地址，而不是物理上的空间。
线性表的基本操作在链表中的实现（初始化、插入、删除、取元素、重置、创建）
注意：在单链表中通常会有一个头指针L，这个L所指的结点并不是第一个结点，头结点为21，P是一个指针，用来指向结点地址的指针。
初始化
- Status InitList(LinkList &L){
- L=(LinkList)malloc(sizeof(LNode)); //分配一个结点的空间
- L->next=NULL; //将头指针指向的下一个结点（首元结点也是第一个结点）设为空
- return OK;
- }
取元素
- Status GetElem_L(LinkList L, int i, ElemType &e) {
- // L是带头结点的链表的头指针，以 e 返回第 i 个元素
- p= L->next; j = 1; // p指向第一个结点，j为计数器,L->next为下一个结点
- while (p && j<i) {
- pp = p->next; ++j; // 顺指针向后查找，直到 p 指向第 i 个元素
- } // 或 p 为空
- if ( !p || j>i )
- return ERROR; // 第 i 个元素不存在
- e = p->data; // 取得第 i 个元素
- return OK;
- } // GetElem_L
插入
在链表中插入结点只需要修改指针，不需要移动大量元素，因为链表是一个指向。如上图：将ai-1的后继指针指向e.
- Status ListInsert_L(LinkList L, int i, ElemType e) {
- // L 为带头结点的单链表的头指针，本算法
- // 在链表中第i 个结点之前插入新的元素 e
- p = L; j = 0;
- while (p && j < i-1) {
- pp = p->next; ++j; // 寻找第 i-1 个结点
- }
- if (!p || j > i-1)
- return ERROR; // i 大于表长或者小于1
- s = (LinkList) malloc ( sizeof (LNode)); // 生成新结点
- s->data = e; s->next=NULL; //让s指向结点e
- s->next = p->next; p->next = s; // 插入，过程如下图。
- return OK;
- } // LinstInsert_L
删除
找到线性表中第i-1个结点，修改其指向后继的指针。
- Status ListDelete_L(LinkList L, int i, ElemType &e) {
- // 删除以 L 为头指针(带头结点)的单链表中第 i 个结点
- p = L; j = 0;
- while (p->next && j < i-1) {
- pp = p->next; ++j; // 寻找第 i 个结点，并令 p 指向其前趋
- }
- if (!(p->next) || j > i-1)
- return ERROR; // 删除位置不合理
- q = p->next; p->next = q->next; // 删除并释放结点，过程如下图
- e = q->data; free(q);
- return OK;
- } // ListDelete_L
重置（将表置空）
- void ClearList(&L) {
- // 将单链表重新置为一个空表
- while (L->next) {
- p=L->next; L->next=p->next;
- free（p）;
- }
- } // ClearList
创建
创建链表实际上就是一个插入的过程。过程如下：采用逆位序插入，然后建立头结点
- void CreateList_L(LinkList &L, int n) {
- // 逆序输入 n 个数据元素，建立带头结点的单链表
- L = (LinkList) malloc (sizeof (LNode));
- L->next = NULL; // 先建立一个带头结点的单链表
- for (i = n; i > 0; --i) {
- p = (LinkList) malloc (sizeof (LNode));
- scanf(&p->data); // 输入元素值
- p->next = L->next; L->next = p; // 插入
- }
- } // CreateList_L
- 算法的时间复杂度为:O(Listlength(L))
循环链表
最后一个结点的指针域的指针又指回头结点（第一个结点）的链表，整个链表形成一个环
注意：判断时应该是后继是否为头结点，比如取元素长度时，单链表为结点后继是否为NULL，但是循环链表的判断是结点的后继是否为头结点。
与单链表操作比较：
1.Initlist（） 初始化时，头结点的next不为NULL，而是指向自身。
2.求表长：while中的条件改为 p！=L；
3.插入、删除操作的基本语句无变化
操作基本一致，通常遇到的循环条件不是判断指针p或p->next 是否为NULL,而是判断它们是否等于头结点
双向链表
定义
- typedef struct DuLNode
- {
- ElemType data; // 数据域
- struct DuLNode *prior; // 指向前驱的指针域
- struct DuLNode *next; // 指向后继的指针域
- } DuLNode, *DuLinkList;
双向循环链表
双向循环链表的基本操作：
其中查询和单链表相同。
初始化
- Status Init_Dul(DulinkList &L){
- if(!L) return ERROR;
- L->next=L;
- L->prior=L;
- Return OK;
- }//Init_Dul
插入
不论P指向哪个结点，都要按照1234的顺序来就不会有错误
- Status ListInsert_Dul(DuLinkList &L,int i, ElemType e){
- P=L-->next; j=1;
- while(p&&j<i){
- pp=p-->next; j++;
- }
- if(!p||j>i) return ERROR;
- if(!(s=(DuLinkList)malloc(sizeof(DuLNode))) return ERROR;)
- S-->data=e;
- S-->pprior=p ; S-->next= P-->next ; P-->next=S; S-->next-->prior=S ;
- return OK;
- }//
删除
删除中间结点
- p-->next=p-->next-->next;
- p-->next-->pprior=p; 注意：现在的p-->next已经是最后一个结点了，因为上一步