《大话数据结构》学习记录----第三章线性表

线性表：零个或多个数据元素的有限序列

3.2线性表的定义

        是具有像线一样的性质的表。就像算盘那个柱子一样一个串一个珠子。

线性表（List）：零个或多个数据元素的有限序列。

两个特点：

        1、元素之间有序

        2、表的长度是有限的

       如果用数学语言来进行定义。可如下：

        若将线性表记为（a1,a2,a_(i-1),a_(i),a(i+1),an）,则表中a_(i-1)领先于a_(i)，a_(i)领先于a_(i+1)，称a_(i-1)是a_(i)的直接前驱元素，a_(i+1)是a_(i)的直接后继元素。当i=1,2,……，n-1时，a_(i)有且仅有一个直接后继，当i=2,3,……，n时，a_(i)有且仅有一个直接前驱。

        线性表中的元素n（n>=0）定义为线性表的长度，当n=0时称为空表。

        在非空表的每个数据元素都有一个确定的位置，如a1是第一个元素，an是最后一个元素，a_(i)，是第i个元素，称i为数据元素a_(i)在线性表中的位序。

在较复杂的线性表中，一个数据元素可以由若干个数据项组成。

3.3线性表的抽象数据类型

定义如下：

ADT 线性表（List）
Data 线性表的数据对象集合为{a1,a2,……an}，各个元素的类型均为DataType.其中。除第一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素an外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。
OperationInitList(*L):    初始化操作，建立一个空的线性表LListEmpty(L):    若线性表为空，返回true，否则返回falseClearList(*L):    清空线性表GetElem(L,i,*e):    将线性表L中的第i个元素值返回给eLocateElem(L,e):    在线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在表中序号表示成功；否则，返回0表示失败；ListInsert(*L,i,e):    在线性表L中的第i个位置插入新元素e.ListDelete(*L,i,e):    删除线性表L中第i个位置的元素，并用e返回其值ListLength(L):    返回线性表的元素个数。
endADT

        对于不同的应用，线性表的基本操作时不同的，上述操作是最基本的，对于实际问题涉及到的关于线性表更复杂的操作，完全可以用这些基本操作的组合实现。

示例：

3.4线性表的顺序存储结构

3.4.1顺序存储的定义

        线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

3.4.2顺序存储方式

        在内存中找了块地，通过占位的形式，把一定内存空间给占了，然后把相同数据类型的数据元素依次存放在这片空地上。因为线性表中的每个数据元素的类型相同，所以可以用C语言（其他语言也一样）的一维数组来实现顺序存储结构，即把第一个数据元素存在数组下标为0的位置中，接着把线性表相邻的元素存储在数组中相邻的位置。每个线性表都有自己的容量，也有自己的长度，长度≤容量。

        线性表的顺序存储的结构代码：

#define MAXSIZE 20    /*存储空间初始分配量*/
typedef int ElemType    /*ElemType 这里是将int类型作为示例 以后凡是int出现的地方用ElemType代替 */
typedef struct 
{ElemType data[MAXSIZE];/*数组存储数据元素，最大值为MAXSIZE*/int length;            /*线性表当前长度*/
}SqList;

顺序存储结构的三个属性：

存储空间的起始位置：数组data,他的存储位置就是存储空间的存储位置。

线性表的最大存储容量：数组长度MaxSize.

线性表的当前长度：length.

3.4.3数组长度与线性表长度的区别

        数组的长度是存放线性表的存储空间的长度。

        线性表的长度是指数据元素的个数。这个长度随着线性表的操作例如插入或者删除是会变化的。

        在任意时刻，线性表的长度应该小于等于数组的长度

3.4.4地址的计算方法

        C语言中的数组是从0开始下标的，于是线性表的第i个元素是要存储在数组的第i-1个位置，即数据元素的序号和存放他的数组下标之间存在对应关系。

LOC表示获得存储位置的函数：

则第i+1个元素和第i个元素有：

        LOC(a_(i+1)) = LOC(a_i) + c;//c是指每个数据元素占多少空间

所以对于第i个元素的存储位置可以由a1推算得出

        LOC(a_i) =( i - 1 ) * c  + LOC(a1)

因为有了这个计算公式，所以不管你的元素是哪一个，只要通过计算公式就可以一步得到内存地址，所以线性表的存取时间性能即时间复杂度为O（1）

3.5顺序存储结构的插入与删除

3.5.1获得元素操作

        思想：对于线性表的顺序存储结构来说，如果我们要实现GetElem操作，即将线性表L中的第i个元素值返回，其实是非常简单的。就程序而言，只要i的数值在数组下标范围内，就是把数组第i-1下标的值返回即可。

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
/*Status是函数的类型，其值是函数结果状态代码 如OK
* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
* 操作结果：用e返回L中第i个数据元素的值
*/
Status GetElem(SqList L, int i, ElemType* e)
{if (L.length == 0 || i<1 || i>L.length)return ERROR;*e = L.data[i - 1];return OK;
}

3.5.2插入操作

        如果要实现ListInsert(*L,i,e),即在线性表中的第i个位置插入新元素e，该怎么实现呢。

实现思路：

        如果插入位置不合理，抛出异常；

        如果线性表长度大于等于数组长度，则抛出异常或动态增加容量；

        从最后一个位置开始向前遍历到第i个位置，分别将他们都往后移动一个位置；

        将要插入的元素填入位置i处

        表长+1

读者可以先自己尝试如何实现相关代码

/*初始条件：顺序线性表L已存在，1≤i≤ListLength(L),
* 操作结果：在L中第i个位置之前插入新的元素e，L的长度加一
*/
Status ListInsert(SqList* L, int i, ElemType e)
{int k;if (L->length == MAXSIZE) //顺序线性表已经满了return ERROR;if (i<1 || i>L->length + 1)//当i不在范围内时候return ERROR;if (i <= L->length){for (k = L->length - 1; k > i; k--)//将要插入位置后数据元素向后移动一位{L->data[k + 1] = L->data[k];}}L->data[k - 1] = e;//将新元素插入L->length++;return OK;
}

3.5.3删除操作

        思路：

        如果删除位置不合理，抛出异常

        取出删除元素

        从删除元素位置开始遍历到最后一个元素位置，分别将他们都向前移动一个位置；

        表长减一

/*初始条件：顺序表L已存在，1≤i≤ListLength(L),
* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减一
*/
Status ListDelete(SqList *L, int i, ElemType* e)
{int k;if (L->length == 0) //线性表为空return ERROR;if (i<1 || i>L->length) //删除位置不正确return ERROR;*e = L->data[i - 1];if (i < L->length){for (k=i ;i <L->length; k++){L->data[k - 1] = L->data[k];}}L->length--;return OK;
}

插入和删除的时间复杂度都是O（n）

存或者取的时间复杂度是O(1)

3.5.4线性表顺序存储的优缺点

优点：

        无须为表示表中元素之间的逻辑关系而增加额外的存储空间

        可以快速地存取表中任意位置的元素

缺点：

        插入和删除操作需要移动大量的元素

        当线性表长度变化较大时，难以确定存储空间的容量

        造成存储空间的“碎片”

3.6线性表的链式存储结构

3.6.1顺序存储结构不足的解决方法

        之前的线性表的顺序存储结构。是有缺点的，最大的缺点就是插入和删除时需要移动大量元素，这显然就需要消费时间。所以便有了链式存储。

3.6.2线性表链式存储结构定义

        线性表的链式存储结构特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这就意味着，这些数据元素可以存在内存未被占用的任意位置。

        

        在链式结构中，除了要存储数据元素信息外，还要存储它的后继元素的存储地址。因此为了表示每个数据元素a _i与其直接后继元素a_(i + 1)之间的逻辑关系，对数据元素a_i来说，除了存储其自身的信息之外，还需要存储一个指示其后继信息（即直接后继的存储位置）。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称为指针或链。把这俩部分信息组成的数据元素a_(i)的存储映像，称为节点（Node）。 

        n个节点链结成一个链表，即为线性表（a1,a2,a3……an）的链式存储结构，因为此链表的每个节点只包含一个指针域，所以是单链表。

        我们把链表中第一个结点的存储位置叫做头指针，有时候为了更方便的对链表操作，会在单链表的第一个结点前附设一个结点，这个节点称为头结点。头结点的数据域可以不存储任何信息，也可以存储线性表的长度等附加信息。

        最后一个节点指向空即null

 3.6.3头指针和头结点的异同

头指针：

        头指针是指链表指向第一个结点的指针，若链表有头结点1，则是指向头结点的指针

        头指针具有标识作用，所以常用头指针冠以链表的名字

        无论链表是否为空，头指针均不为空。头指针是链表的必要元素。

头结点：

        头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义（也可存放链表的长度）

        有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其他节点的操作就统一了

        头结点不一定是链表的必须要素

3.6.4线性表链式存储结构的代码描述

注意这里只是将链表中的每个节点进行了描述

/*线性表的单链表存储结构*/
typedef struct Node
{ElemType data;struct Node* next;
}Node;
typedef struct Node* LinkList;/*定义LinkList*/

         上述代码：首先定义了每个节点应该具有什么，一个是数据域，一个是指向下一个的指针域

然后就定义了头指针为LinkList,表示我们定义了这样一个链表。

3.7单链表的读取

        算法思路：

        1、申明一个结点p指向链表的第一个结点，初始化j从1开始；

        2、当j<i时，就遍历链表。让p的指针往后移动，让p的指针向后移动，不断地指向下一个结点，j累加1；

        3、若到链表结尾p为空，就说明第i个元素不存在；

        4、否则查找成功，返回节点p的数据

实现代码：

/*初始条件：顺序线性表L已存在 1≤i≤ListLength(L)*/
/*操作结果：用e返回L中第i个数据元素的值*/
Status GetElem_LinkList(LinkList L, int i, ElemType* e)
{int j;LinkList p;     /*申明一个结点p*/p = L->next;    /*让p指向链表L的第一个结点1*/j = 1;          /*j为计数器*/while (p && j < i)   /*p不为空或者计数器j还没有等于i时，循环 */{p = p->next;    /*让p指向下一个结点*/++j;}if (!p || j > i)    /*第i个元素不存在*/return ERROR;   /*取第i个元素的数据*/*e = p->data;return OK;
}

注意：最坏情况时间复杂度为O（n），核心思想：工作指针后移

3.8单链表的插入和删除

3.8.1单链表的插入

        单链表第i个数据插入结点的算法思路：

1.  声明一结点p指向链表的第一个结点，初始化j从1开始
2.  当j<i时，就遍历链表，让p的指针往后移动，不断指向下一个结点，j累加1；
3. 若到链表末尾p为空，则说明第i个元素不存在
4. 否则查找成功，在系统中生成一个空节点s
5. 将数据元素e赋值给s->data；
6. 单链表的标准插入语句s-next = p->next;p-next=s;
7. 返回成功

实现代码：

/*初始条件：顺序线性表L已存在 1≤i≤ListLength(L)*/
/*操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1*/
Status ListInsert_LinkList(LinkList* L, int i, ElemType e)
{int j = 1;LinkList p, s;p = *L;while (p && j < i)  //寻找第i个节点{p->next;++j;}if (!p || j > i)    //第i个节点不存在return ERROR;s = (LinkList)malloc(sizeof(Node));/*生成新的节点*/s->data = e;            s->next = p->next;              //将p的后继节点赋值给s的后继p->next = s;                    //将s赋值给p的后继return OK;
}

3.8.2单链表的删除

        算法思路：

1. 申明一个结点p指向链表的第一个结点，初始化从j=1开始
2. 当j<i时，就遍历链表，让p的指针往后移动，不断指向下一个结点，j累加1
3. 若到链表结点末尾p为空，则说明第i个元素不存在
4. 否则查找成功，将欲删除的节点p->next赋值给暂存节点q
5. 利用单链表的标准删除语句，p->next=q-next;
6. 将q节点中的数据赋值给e,作为返回 返回的是删除的节点的数据 可以视情况保留
7. 释放q节点 
8. 返回成功  

/*初始条件：顺序线性表L已存在 1≤i≤ListLength(L)*/
/*操作结果：删除L中的第i个元素，并用e返回其值，L的长度减一*/
Status Listdelete_LinkList(LinkList* L, int i, ElemType* e)
{int j = 1;LinkList p, q;p = *L;while (p->next && j < i)//遍历寻找第i个元素 注意这里 实际上j=i时，此时的p节点是第i节点的前一个节点{p = p->next;++j;}if (!(p->next) || j > i)//第i个元素不存在return ERROR;q = p->next;p->next = q->next;  //将q的后继赋值给p的后继*e = q->data;       //将q节点中的数据赋值给efree(q);            //让系统回收此节点，释放内存return OK;
}

对于插入数据越频繁的操作，单链表的效率优势就越是明显。

3.9单链表的整表创建

        单链表整表创建的算法思路：

1. 声明一节点p和计数器变量i
2. 初始化一空链表L
3. 让L的头结点的指针指向NULL,即建立一个带头结点的单链表
4. 循环：

                生成一个新节点，赋值给p，即建立一个带头结点的单链表

                随机生成一数字赋值给p的数据域p->data;

                将p插入到头结点与前一新节点之间

头插法：

/*随机产生n个元素的值，建立带表头结点的单链线性表L（头插法）*/
void CreateListHead(LinkList* L, int n)
{LinkList p;int i;srand(time(0)); //初始化随机数种子*L = (LinkList)malloc(sizeof(Node));(*L)->next = NULL;  //先建立一个带头结点的单链表for (i = 0; i < n; i++){p = (LinkList)malloc(sizeof(Node)); //生成新的节点p->data = rand() % 100 + 1; //随机生成100以内的数字p->next = (*L)->next;   (*L)->next = p; //插入到表头}
}

还有一种方式就是先来后到的顺序，进行尾插法。

实现代码如下：

/*随机产生n个元素的值，建立带表头结点的单链线性表L（尾插法）*/
void CreateListTail(LinkList* L, int n)
{LinkList p, r;srand(time(0));//初始化随机数种子*L = (LinkList)malloc(sizeof(Node));//为整个线性表r = *L;     //r为指向尾部的节点for (int i = 0; i < n; i++){p = (Node*)malloc(sizeof(Node));//产生新的节点p->data = rand() % 100 + 1; //随机生成100以内的数字r->next = p;    //将表尾终端节点的指针指向新的节点r = p;          //将当前的新节点定义为表尾终端节点}r->next = NULL;     //表示当前链表结束
}

 

         循环结束后，表明当前r就已经是最后一个节点了，所以将他的下一个设置为NULL，是为了后面继续装元素，以便以后遍历的时候可以确认他是尾部。

3.10单链表的整表删除

        删除算法思路：

1. 声明节点p和q
2. 将第一个节点赋值给p
3. 循环

                将下一个节点赋值给q

                释放p;

                将q赋值给p

实现代码：

/*初始条件：顺序线性表L已存在，操作结果：将L重置为空表*/
Status ClearList(LinkList* L)
{LinkList p, q;p = (*L)->next;// p指向第一个结点while (p)       //一直跑哇跑 直到结尾{q = p->next;free(p);p = q;}(*L)->next = NULL;  //头结点置空return OK;
}

        这个q指针是否一定要存在呢，回答是 是的！因为你每个节点除了指针域 还有数据域，free（）操作是对整个节点进行删除和释放内存的工作，那么就会找不到后面的节点了，那这些节点会自己释放吗？不可能的，直接造成内存危机。所以不能只让自己解脱，还得留下下一个兄弟的信息，大家一起解脱。

3.11单链表结构与顺序存储结构的优缺点

小结：

        若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构若需要频繁插入和删除时，宜采用单链表结构。

        当线性表中的元素个数变化较大或者根本不知道有多大的时候，最好用单链表结构，这样可以不需要考虑存储空间的大小问题。而如果事先知道线性表的大致长度，使用顺序存储结构就比较舒服。

        在实际使用时，应综合考虑二者的优缺利弊。

3.12静态链表

        在C语言中可以使用指针来操作内存中的地址和数据，那么那些没有指针的语言该怎么办呢。于是有人就提到了用数组来代替指针。

        首先，让每一个数组位置存两个数据域，data和cur。即数组的每个下标都对应着一个data和cur。

数据域data：用来存放数据元素，是我们通常要处理的数据元素。

而游标cur：相当于单链表中的next指针，存放该元素的后继元素的下标

        这种用数组描述的链表叫做静态链表，这种描述方式也可以叫做游标实现法。

实现代码如下：线性表的静态链表存储结构

/*线性表的静态链表存储结构*/
#define MAXSIZE_STACTIC 1000    /* 假设链表的最大长度1000*/
typedef struct
{ElemType data;int cur; /*游标（Cursor），为0的时表示无指向*/
}Component,StaticLinkList[MAXSIZE_STACTIC];

一些特殊处理：

        数组的第一个和最后一个位置作为特殊元素处理，不存数据。

        备用链表：未被使用的数组元素。

数组的第一个元素：即下标为0的cur就存放备用链表的第一个结点的下标

数组的最后一个元素：自身的cur则存放第一个有数值的元素的下标，相当于单链表中头结点作用。

/*将一维数组space中各分量链成一备用链表*/
/*space[0].cur为头指针，"0"表示空指针*/
Status InitList(StaticLinkList space)
{for (int i = 0; i < MAXSIZE_STACTIC - 1; i++){space[i].cur = i + 1;}space[MAXSIZE_STACTIC - 1].cur = 0;/*目前空链表为空。最后一个元素cur为0*/return OK;
}

3.12.1静态链表的插入操作

        目标：实现静态模拟动态链表结构的存储空间的分配，需要时申请，无用时释放。

        在动态链表中：结点的申请和释放分别借用malloc()和free()两个函数实现。

        在静态链表中：操作的是数组，不存在动态链表中的节点申请和释放问题，所以我们得自己实现这两个函数。才能进行插入和删除。

        为了辨明数组中哪些分量未被使用，解决的办法是将所有未被使用过的及被删除的分量用游标链成一个备用的链表，每当进行插入时，便可以从备用链表上取得第一个结点作为待插入的新节点。

实现的Malloc函数

/*若备用空间链表非空，则返回分配的节点下标，否则返回0*/
int Malloc_SLL(StaticLinkList space)
{int i = space[0].cur;/*当前数组的第一个元素的cur存的值*//*就是要返回的第一个备用空闲的下标*/if (space[0].cur)space[0].cur = space[i].cur;/*由于要拿出当前的第一个备用分量所以要把他的下一个分量用来做备用*/return i;
}

代码解释：

1、第一步返回目前知道的下一个空闲位置的下标（因为你的第一个数组的cur始终存着第一个备用链表的下标）

2、如果不是最后一个元素，那么取出下一个作为新的备用节点

3、返回取出的节点使用

静态链表的插入代码实现：

/*在L中第i个元素之前插入新的数据元素e */
Status ListInsert_Static(StaticLinkList L, int i, ElemType e)
{int j, k, l;k = MAXSIZE_STACTIC - 1;/*注意k首先是最后一个元素的下标*/if (i<1 || i>ListLength(L) + 1)return ERROR;j = Malloc_SLL(L);  //获得空闲分量的下标if (j){L[j].data = e;//将数据赋值给此分量的datafor (l = 1; l <= i - 1; l++)//找到第i个元素之前的位置k = L[k].cur;L[j].cur = L[k].cur;//把第i个元素之前的cur赋值给新元素的curL[k].cur = j;//把新元素的下标赋值给第i个元素之前的元素的curreturn OK;}return ERROR;
}

看这张图，我们要将丙元素插入到乙和丁之间，那么按照代码来看的话。执行流程是这样的：

1. 先获取到第一个有数值元素的位置（通过最后一个位置来获得）即：k=MAXSIZE_STACTIC - 1;在这里我们获得了最后一个元素的下标，根据前面的定义，最后一个数组位置的下标存放着指向第一个有数值元素的cur，所以先得到这个k。
2. 判断插入位置是否合理，if条件就是拿来判断插入位置的合法性。
3. 合法的的话，就获取到第一个空闲位置，前面说了第一个数组位置的cur存放着第一个备用链表的空闲分量的下标于是j = Malloc_SLL(L);
4. 当然我们要先保障有空闲位置才能继续下面的操作，于是乎有了个if(j)
5. 这个时候j就是我们获取到的数组中空闲位置，于是我们将插入的元素赋值给这个空位，因为这是个空位，所以不用担心有数值覆盖的问题。
6. 接下来该怎么办呢，因为我们是想将新元素插入到乙和丁之间，也就是3号位置，所以我们要得到第3个位置也就是i在哪里，于是进行一个for循环：①l = 1，k = L[k = 999].cur=1（因为此时第一个有元素的位置是1），此时l++；②l + 2，k=L[k=1].cur=2，l++；③l=3>i-1=2故循环结束，那么此时k = 2就是我们要插入位置的前一个元素，对吧
7. 那么此时，请你想想，下一步该怎么做呢，是先把前一个元素的游标直接指向新插入的元素还是先将新插入的元素的游标指向前一个元素的游标呢。当然是后者，假设你直接就将前一个元素的游标指向了新插入的元素，那怎么能够将新插入的这个元素指向原先的下一个元素呢，不可能的，因为你直接丢失对下一个元素的索引。所以我们必须先将插入元素的游标指向原先元素的游标，然后再将原先元素的游标指向新插入元素，这样才能保障新插入元素是在他们之间，而不是断掉了与后面的沟通，所以L[j].cur = L[k].cur；L[k],cur = j;

3.12.2静态链表的删除操作

      前面删除元素时，原来是需要释放节点的函数free(),现在我们也要自己实现它：

代码如下：

/*将下标为k的空闲节点回收到备用链表*/
void Free_SSL(StaticLinkList space, int k)
{space[k].cur = space[0].cur;//把第一个元素cur赋值给要删除的分量curspace[0].cur = k;//把要删除的分量下标赋值给第一个元素的cur
}

代码解释：

        你看你的数组中的第0个位置是不是指向的下一个第一个可以使用的备用链表的下标，那么现在呢。你想，我是不是要删除第k个节点，是不是也就意味着我数组的第0个位置的游标指向这个k，如果我直接就将k给赋值给了space[0]，那么后面哪里有空位，我是不是就晓球不得了，所以在这里，我们得先将我目前第0个位置指向的空位赋值给第k个位置的游标，这样在我将k赋值给自己之后，我是不是就能找到后面的空位。也就是我先将第0个元素指向的空位，先让k来指，这样第0个元素坐过去之后，是不是就能保持相安无事。就像李世民玄武门之变一样，自己顶了太子的位置，然后后面才能当皇帝。

        好的，回归主线任务，接下来我们就要去删除在L中删除元素了：

代码如下：

/*删除在L中的第i个数据元素e*/
Status ListDelete(StaticLinkList L, int i)
{int j, k;if (i<1 || i>ListLength(L))return ERROR;k = MAXSIZE_STACTIC - 1;//获取到最后一个位置的下标，然后为了获取第一个数值元素的位置for (j = 1; j <= i-1; j++)k = L[k].cur;//移动到第i-1个位置 此时k的位置就是第i-1 不执行的话就是还是在最后，即第一个位置是有元素的j = L[k].cur;//获取到要删除的元素的下标了L[k].cur = L[j].cur;//将第i-1个元素的游标指向删除元素的游标，即跳过删除元素不就是删除了这个元素Free_SSL(L, j);//释放删除元素的空间return OK;
}

3.12.3静态链表的优缺点

3.13循环链表

        对于单链表，你的每个节点只存储了向后的指针，到了尾指针就傻眼了，回不到前面了，就只能一条道走到黑。那怎么能回到过去呢，当然是听一万遍《反方向的钟》啦，哈哈哈，开玩笑的。所以出现了循环链表，你将自己的尾节点的指针指向头结点是不是就能回去了哈。

        将单链表中终端节点的指针端由空指针改为指向头结点，就使得整个单链表形成了一个环，这种头尾相接的单链表称为单循环链表，简称循环链表。

        

3.14双向链表 

        试想你知道你的下级，但是你永远不知道你的上级，那从何开启加薪啊！所以为了获取到上级的消息，科学家们还发明了双向链表.即：双向链表是在单链表的每个节点中，在设置一个指向其前驱结点的指针域。所以在双向链表中的节点都有两个指针域，一个 指向直接后继，一个指向直接前驱。

代码示例：

/*线性表的双向链表存储结构*/
typedef struct DulNode
{ElemType data;struct DuLNode  *prior;//直接前驱指针struct DuLNode  *next;//直接后继指针
}DulNode,*DuLinkList;

插入操作：

一共四步：

1.  先将待插入的节点的后继节点指向前一个节点的后继节点
2.  再将待插入结点的前去节点指向前一个节点
3. 修改前一个节点的后继节点为插入节点
4. 修改后一个结点的前驱结点为插入节点

删除操作：

总结：

1. 先将待删除节点的前驱节点的后继指向待删除节点的后继
2. 再将待删除节点的后继节点的前驱指向待删除节点的前驱

3.15总结

附本文所有代码：

#include<stdio.h>
#include<stdlib.h>
#include <time.h>//线性表的顺序存储
#define MAXSIZE 20    /*存储空间初始分配量*/
typedef int ElemType;   /*ElemType 这里是将int类型作为示例 以后凡是int出现的地方用ElemType代替 */
typedef struct
{ElemType data[MAXSIZE];/*数组存储数据元素，最大值为MAXSIZE*/int length;            /*线性表当前长度*/
}SqList;#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
/*Status是函数的类型，其值是函数结果状态代码 如OK
* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
* 操作结果：用e返回L中第i个数据元素的值
*/
//获取线性表中的某一个值
Status GetElem(SqList L, int i, ElemType* e)
{if (L.length == 0 || i<1 || i>L.length)return ERROR;*e = L.data[i - 1];return OK;
}
/*初始条件：顺序线性表L已存在，1≤i≤ListLength(L),
* 操作结果：在L中第i个位置之前插入新的元素e，L的长度加一
*/
Status ListInsert(SqList* L, int i, ElemType e)
{int k;if (L->length == MAXSIZE) //顺序线性表已经满了return ERROR;if (i<1 || i>L->length + 1)//当i不在范围内时候return ERROR;if (i <= L->length){for (k = L->length - 1; k > i; k--)//将要插入位置后数据元素向后移动一位{L->data[k + 1] = L->data[k];}}L->data[k - 1] = e;//将新元素插入L->length++;return OK;
}
/*初始条件：顺序表L已存在，1≤i≤ListLength(L),
* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减一
*/
Status ListDelete(SqList *L, int i, ElemType* e)
{int k;if (L->length == 0) //线性表为空return ERROR;if (i<1 || i>L->length) //删除位置不正确return ERROR;*e = L->data[i - 1];if (i < L->length){for (k=i ;i <L->length; k++){L->data[k - 1] = L->data[k];}}L->length--;return OK;
}/*线性表的单链表存储结构*/
typedef struct Node
{ElemType data;struct Node* next;
}Node;
typedef struct Node* LinkList;/*定义LinkList*//*初始条件：顺序线性表L已存在 1≤i≤ListLength(L)*/
/*操作结果：用e返回L中第i个数据元素的值*/
Status GetElem_LinkList(LinkList L, int i, ElemType* e)
{int j;LinkList p;     /*申明一个结点p*/p = L->next;    /*让p指向链表L的第一个结点1*/j = 1;          /*j为计数器*/while (p && j < i)   /*p不为空或者计数器j还没有等于i时，循环 */{p = p->next;    /*让p指向下一个结点*/++j;}if (!p || j > i)    /*第i个元素不存在*/return ERROR;   /*取第i个元素的数据*/*e = p->data;return OK;
}
/*初始条件：顺序线性表L已存在 1≤i≤ListLength(L)*/
/*操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1*/
Status ListInsert_LinkList(LinkList* L, int i, ElemType e)
{int j = 1;LinkList p, s;p = *L;while (p && j < i)  //寻找第i个节点{p->next;++j;}if (!p || j > i)    //第i个节点不存在return ERROR;s = (LinkList)malloc(sizeof(Node));/*生成新的节点*/s->data = e;            s->next = p->next;              //将p的后继节点赋值给s的后继p->next = s;                    //将s赋值给p的后继return OK;
}
/*初始条件：顺序线性表L已存在 1≤i≤ListLength(L)*/
/*操作结果：删除L中的第i个元素，并用e返回其值，L的长度减一*/
Status Listdelete_LinkList(LinkList* L, int i, ElemType* e)
{int j = 1;LinkList p, q;p = *L;while (p->next && j < i)//遍历寻找第i个元素 注意这里 实际上j=i时，此时的p节点是第i节点的前一个节点{p = p->next;++j;}if (!(p->next) || j > i)//第i个元素不存在return ERROR;q = p->next;p->next = q->next;  //将q的后继赋值给p的后继*e = q->data;       //将q节点中的数据赋值给efree(q);            //让系统回收此节点，释放内存return OK;
}
/*随机产生n个元素的值，建立带表头结点的单链线性表L（头插法）*/
void CreateListHead(LinkList* L, int n)
{LinkList p;int i;srand(time(0)); //初始化随机数种子*L = (LinkList)malloc(sizeof(Node));(*L)->next = NULL;  //先建立一个带头结点的单链表for (i = 0; i < n; i++){p = (LinkList)malloc(sizeof(Node)); //生成新的节点p->data = rand() % 100 + 1; //随机生成100以内的数字p->next = (*L)->next;   (*L)->next = p; //插入到表头}
}
/*随机产生n个元素的值，建立带表头结点的单链线性表L（尾插法）*/
void CreateListTail(LinkList* L, int n)
{LinkList p, r;srand(time(0));//初始化随机数种子*L = (LinkList)malloc(sizeof(Node));//为整个线性表r = *L;     //r为指向尾部的节点for (int i = 0; i < n; i++){p = (Node*)malloc(sizeof(Node));//产生新的节点p->data = rand() % 100 + 1; //随机生成100以内的数字r->next = p;    //将表尾终端节点的指针指向新的节点r = p;          //将当前的新节点定义为表尾终端节点}r->next = NULL;     //表示当前链表结束
}
/*初始条件：顺序线性表L已存在，操作结果：将L重置为空表*/
Status ClearList(LinkList* L)
{LinkList p, q;p = (*L)->next;// p指向第一个结点while (p)       //一直跑哇跑 直到结尾{q = p->next;free(p);p = q;}(*L)->next = NULL;  //头结点置空return OK;
}/*线性表的静态链表存储结构*/
#define MAXSIZE_STACTIC 1000    /* 假设链表的最大长度1000*/
typedef struct
{ElemType data;int cur; /*游标（Cursor），为0的时表示无指向*/
}Component,StaticLinkList[MAXSIZE_STACTIC];/*将一维数组space中各分量链成一备用链表*/
/*space[0].cur为头指针，"0"表示空指针*/
Status InitList(StaticLinkList space)
{for (int i = 0; i < MAXSIZE_STACTIC - 1; i++){space[i].cur = i + 1;}space[MAXSIZE_STACTIC - 1].cur = 0;/*目前空链表为空。最后一个元素cur为0*/return OK;
}
/*若备用空间链表非空，则返回分配的节点下标，否则返回0*/
int Malloc_SLL(StaticLinkList space)
{int i = space[0].cur;/*当前数组的第一个元素的cur存的值*//*就是要返回的第一个备用空闲的下标*/if (space[0].cur)space[0].cur = space[i].cur;/*由于要拿出当前的第一个备用分量所以要把他的下一个分量用来做备用*/return i;
}/*初始条件：静态链表已存在。操作结果：返回L中数据元素的个数*/
int ListLength(StaticLinkList L)
{int j = 0;int i = L[MAXSIZE_STACTIC - 1].cur;//指向头结点while (i){i = L[i].cur;//获取下一个不为NULL的空闲节点j++;}return j;
}/*在L中第i个元素之前插入新的数据元素e */
Status ListInsert_Static(StaticLinkList L, int i, ElemType e)
{int j, k, l;k = MAXSIZE_STACTIC - 1;/*注意k首先是最后一个元素的下标*/if (i<1 || i>ListLength(L) + 1)return ERROR;j = Malloc_SLL(L);  //获得空闲分量的下标if (j){L[j].data = e;//将数据赋值给此分量的datafor (l = 1; l <= i - 1; l++)//找到第i个元素之前的位置k = L[k].cur;L[j].cur = L[k].cur;//把第i个元素之前的cur赋值给新元素的curL[k].cur = j;//把新元素的下标赋值给第i个元素之前的元素的curreturn OK;}return ERROR;
}
/*将下标为k的空闲节点回收到备用链表*/
void Free_SSL(StaticLinkList space, int k)
{space[k].cur = space[0].cur;//把第一个元素cur赋值给要删除的分量curspace[0].cur = k;//把要删除的分量下标赋值给第一个元素的cur
}/*删除在L中的第i个数据元素e*/
Status ListDelete(StaticLinkList L, int i)
{int j, k;if (i<1 || i>ListLength(L))return ERROR;k = MAXSIZE_STACTIC - 1;//获取到最后一个位置的下标，然后为了获取第一个数值元素的位置for (j = 1; j <= i-1; j++)k = L[k].cur;//移动到第i-1个位置 此时k的位置就是第i-1 不执行的话就是还是在最后，即第一个位置是有元素的j = L[k].cur;//获取到要删除的元素的下标了L[k].cur = L[j].cur;//将第i-1个元素的游标指向删除元素的游标，即跳过删除元素不就是删除了这个元素Free_SSL(L, j);//释放删除元素的空间return OK;
}/*线性表的双向链表存储结构*/
typedef struct DulNode
{ElemType data;struct DuLNode  *prior;//直接前驱指针struct DuLNode  *next;//直接后继指针
}DulNode,*DuLinkList;