带头结点的单链表

第二章 线性表（linear list) 线性表的定义及运算1 线性表的顺序存储结构（顺序表） 线性表的链式存储结构（链表） 2.1 线性表的定义及运算2.1.1. 线性表的定义是由n(n>=0)个数据元素（结点）a 1 ,a 2 ,a 3 , ……a n 组成的有限序列。其中：n为数据元素的个数，也称为表的 长度。2当n=0 时，称为 空表。非空的线性表(n>0) 记作：（ a 1 ,a 2 ,a 3 , ……a n ）※ ※※※ [ 线性表的特性]（1）线性表中的所有数据元素的数据类型是一致的。（2）数据元素性表中的位置只取决于它的序号。（3）结点间的逻辑关系是线性的。（ （1 ）有且仅有一个开始结点a 1 ( 无直接前趋)；（；（2 ）有且仅有一个终端结点a n ( 无直接后继)；（；（3 ）其余的结点a i 都有且仅有一个直接前趋都有且仅有一个直接前趋a i-1 和一个直接后继a i+1 。（ （4 ）a i 是属于某个数据对象的元素 ， 它可以是 一 个2.1.2 线性表（a 1 ,a 2 ,a 3 , ……a n ）的逻辑特征3（ （4 ）a i 是属于某个数据对象的元素 ， 它可以是 个数字 、一个 字母 或一个 记录 。

例 例1 ．26个英文字母组成的字母表（个英文字母组成的字母表（A ，B ，C 、… 、Z）例）例2 ．某学院从2006 年到2011年各种型号的计算机拥有量的变化情况。（年各种型号的计算机拥有量的变化情况。（36 ，87 ，102 ，150 ，192 ，240） ）例 例3 、学生健康情况登记表姓 名 学 号 性 别 年龄 健康情况王小林 100631 男 18 健康陈 红 100632 女 20 一般4陈 红 女 般刘建平 100633 男 21 健康张立立 100634 男 17 神经衰弱…….. …….. ……. ……. …….数据的运算是定义在逻辑结构上的，而具体的实现则在存储结构上进行。（1）存取（2）插入（3）删除 基本运算2.1.3. 线性表的运算5（3）删除（4）查找（5）合并（6）分解（7）排序（8）求线性表的长度基本运算   2.2 线性表的顺序存储结构（顺序表）2.2.1. 顺序表的定义：用一组连续的存储单元（地址连续）依次存放线性表的各个数据元素6存放线性表的各个数据元素。

将一个线性表存储到计算机中，可以采取许多不同的方式，最简单的是顺序存储方式即把线性表的结点按逻辑次序依次存放在一组连续的存储单元里，结点在计算机内的存放位置完全由结点性表中的顺序号决定，用这种方法存储的线性表称为顺序表。由于聚集索引规定数据在表中的物理存储顺序，因此一个表只能包含一个聚集索引。为了体现功能的正常性，至少要编制遍历数据的函数.数据的逻辑结构设计和运算定义需要实现线性表的以下功能:1、创建单链表 2、删除链表中的某个结点 3、输出单链表(遍历) 4、释放结点所占空间5、查找第i个结点 6、插入一个结点 7、求链表的长度三. 数据的存储结构设计和算法设计(1).数据结构线性表的线性结构觉决定了它的性质：数据元素之间是一种线性关系，数据元素一个接一个的排列，除了最后一个数据，其他的数据面临的下一个数据有且仅有一个。

2.2.4 顺序表的几种基本运算（ （1 ）插入运算在第i（1<=i<=n)个元素之前插入一个新的数据元素x。使：长度为n的线性表变为长度为n+1的线性表（a 1 a 2 a i 1 a i a ）10（a 1 ,a 2 ,…,a i-1 ,a i ,…,a n ）（a 1 ,a 2 ,…,a i-1 ,x,a i ,…,a n ） 插入算法的思想：1. 若i=n+1,则将x插入到表尾；2. 若表长度n<0或插入位置不适当，则输出错误信息，并返回-1；3. 当1<=i<=n时，则从表尾开始到i个依次向后移动 个位置（共需移动 i 1个11次向后移动一个位置（共需移动n-i+1个数据元素。带头结点的单链表4. 最后将x存入v[i]中，表长n增1插入成功，函数返回值为0。插入算法描述int insertlist(v,pn,i,x)int v[],x,*pn,i;/*--pn指向表长n的地址。--*/{ int j;if (*pn<0){printf(“表长错误\n");for (j=*pn;j>=i;j--)v[j+1]=v[j];v[i]=x;(*pn)++;printf("success\n");return(0);12{printf( 表长错误\n );return(-1);}if (i<1||i>*pn+1){printf(“插入位置i不适当\n");return(-1);}return(0);}※ 算法调用：k=insertlist(v,&n,i,x)插入算法分析：上述算法for循环语句的执行次数为n-i+1;若i=1,需移动全部n个结点（最坏：O(n)）若i=n+1（在表尾插入）,无需用移动结点，直接插入即可。

（最好O(1)）移动结点的平均次数：13移动结点的平均次数： 按等概率考虑：可能的插入位置为i=1,2,……n,n+1共n+1个，则p i =1/(n+1)所以14 顺序表插入算法平均约需移动一半结点。 （ （2 ）删除算法将线性表的第i（1<=i<=n)个结点删除，使：长度为n的线性表变为长度为n-1的线性表。（a 1 ,a 2 ,…,a i-1 ,a i ,a i+1 ,…,a n ）15（a 1 ,a 2 ,…,a i-1 ,a i+1 ,…,a n ） 删除算法的思想：1. 若i=n,只需删除终端结点，不用移动结点；2. 若表长度n<=0或删除位置不适当，则输出错误信息，并返回-1；163. 当1<=i<n时，则将表中结点a i+1 ,a i+2 ,…,a n 依次向前移动一个位置（共需移动n-i个数据元素。4. 最后将表长n减1，删除成功，函数返回值为0。删除算法描述Void deleteList(Sqlist*L，int i){int j;if(i<1 || i>L.length){ printf(“Position error”);17return ERROR;}for(j=i+1;j<=L.length;j++)L.data[j-1]=L.data[j];L.length--;}[注：] Sqlist类型定义见教材22页 删除算法分析：上述算法for循环语句的执行次数为n-i;若i=1,最坏：O(n)若i=n,无需用移动结点，直接删除即可。

（最好O(1)）移动结点的平均次数18移动结点的平均次数： 按等概率考虑：可能的删除位置为i=1,2,……n共n个，则p i =1/n所以19 顺序表删除算法平均约需移动一半结点。 [小结：] 顺序表插入、删除算法平均约需移动一半结点，当n很大时，算法的效率较低。优点：（1）无须为表示结点间的逻辑关系而增加额外的存储空间。（2）可以方便地随机存储表中的任一结点。 顺序表的优、缺点20缺点：（1）插入和删除平均须移动一半结点。（2）存储分配只能预先进行（静态）过大 浪费过小 溢出  2.3 线性表的链式存储结构（链表）2.3.1 基本知识 链表：用一组 任意的存储单元（可以是无序的，即可零散地分布在内存中的任何位置上）存放线性表的数据元素。的存储单元（可以是无序的，即可零散地分布在内存中的任何位置上）存放线性表的数据元素。21 链表的特点：链表中结点的逻辑次序和物理次序不一定相同。即：逻辑上相邻未必在物理上相邻。结点之间的相对位置由链表中的指针域指示，而结点在存储器中的存储位置是随意的。链表中结点的逻辑次序和物理次序不一定相同。即：逻辑上相邻未必在物理上相邻。

一个单链表结点，其结构类型分为两部分：1、数据域：用来存储本身数据2、链域或称为指针域：用来存储下一个结点地址或者说指向其直接后继的指针。这只需要修改输出链表的尾结点中的指针域，令其指向箱子链表的头，然后修改输出链表的尾指针，令其指向箱子链表的尾即可。为了正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其直接后继结点的地址（或位置），称为指针或链，这两部分组成了链表中的结点结构。

※ 开始结点头指针为空。※ 开始结点---（无前趋）用头指针指向之。※ 尾结点（无前趋）用头指针指向之。※ 尾结点--- （无后继），最后一个结点，其指针域为空，用^ 或null表示。※ 表中其它结点表示。※ 表中其它结点--- 由其前趋的指针域指向之。※ ※ 头结点--- 在链表的第 一 个结点之前附设 一 个结点 ， 称为头24※ ※ 头结点--- 在链表的第 个结点之前附设 个结点 ， 称为头结点。头结点的数据域可以不存任何信息，也可存储如长度等附加信息。结点。头结点的数据域可以不存任何信息，也可存储如长度等附加信息。a 2a n^ a 1Head头结点Typedef int datatype;typedef structure node/*结点类型定义*/{ datatype data;/*数据域*/struct node *next; }JD; /*next为指针域，指向该结点的后继*/ 单链表的描述：25指向该结点的后继 /JD *head,*p;/*指针类型说明*/指针p 与指向的结点关系:Datanextp结点 (*p) 指针p与指向的结点关系：p结点 (*p)说明：p 指向链表中某一结点的指针Datanext26p---指向链表中某一结点的指针。

尾插法的说核心思想，就是始终有一个指针指向链表的尾结点，然后在尾结点之后插入新开辟的结点，对于尾插法的代码为什么这样写，不解释，自己思考，仿照头插法分析一样，自己理解。这只需要修改输出链表的尾结点中的指针域，令其指向箱子链表的头，然后修改输出链表的尾指针，令其指向箱子链表的尾即可。注意，创建循环链表时必须使其尾结点的后继指针指向表头结点，尤其是在尾结点后插入新结点时。

尾插法的说核心思想，就是始终有一个指针指向链表的尾结点，然后在尾结点之后插入新开辟的结点，对于尾插法的代码为什么这样写，不解释，自己思考，仿照头插法分析一样，自己理解。这只需要修改输出链表的尾结点中的指针域，令其指向箱子链表的头，然后修改输出链表的尾指针，令其指向箱子链表的尾即可。（注意：在使用这个函数获得尾结点指针时，必须在每次插入结点元素后重新获得，因为链表尾部结点是会随着结点的插入而发生变化）。

这只需要修改输出链表的尾结点中的指针域，令其指向箱子链表的头，然后修改输出链表的尾指针，令其指向箱子链表的尾即可。尾插法的说核心思想，就是始终有一个指针指向链表的尾结点，然后在尾结点之后插入新开辟的结点，对于尾插法的代码为什么这样写，不解释，自己思考，仿照头插法分析一样，自己理解。双链表有两个指针域，一个指针指向左边结点，一个指针指向右边结点，用头指针表示开始结点，用尾指针表示结尾结点。

例：多项式p1为：18x17+9x8+4x2+3x多项式p2为：12x12+7x8+4x3多项式运算p1+p2的结果为：18x17+12x12+16x8+4x3+4x2+3x从上述的链表创建算法可以创建出两个对应的链表先利用两个指针，pa和pb，分别指向两个多项式的结点。静态链表的尾插入类似，首先从备用链表头拿出一个元素，把备用链表的头标记指向备用链表的第2个元素的数组下标，因为要作为链表的最后一个元素，因此把这个元素的cur设为空，接着把真是链表的为指针指向这个数组元素cur设为这个被拿出来的元素的下标，接着把为指针标记的值设为这个元素的数组下标，这样就完成了链表的尾插入。定义函数node *del(node *h, int i)，用于删除单链表h中第i个结点，定义两个指针*p，*q，用指针p来从第一个结点开始查找需要删除的结点，指针q是指针p的前驱，查找过程中，不断移动指针p，q，直至找到需要删除的结点，如果*p为空指针，则表示链表中没有需要删除的结点，最后返回头指针。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-96930-1.html