例1说明在线性表的链式存储结构中，头指针与头结点之间的根本区别；头结点与首元结点的关系。

答：在线性表的链式存储结构中，头指针是指指向链表的指针，若链表有头指针则是链表的头结点的指针，头指针具有标识作用，故常用头指针冠以链表的名字。

头结点是为了操作的统一、方便而设立的，放在第一数据元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用作监视哨，等等），有了头结点后，对在第一数据元素结点前插入结点和删除第一结点，其操作与对其它结点的操作就统一了。

而且无论链表是否为空，头指针均不为空。

首元结点也就是第一数据元素结点，它是头结点后边的第一个结点。

例2 为什么在单循环链表中设置尾指针比设置头指针更好？答：尾指针是指指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一个带头结点的单循环链表，其尾指针是rear，则开始结点和终端结点分别为指针rear所指结点的后继结点的后继结点和指针rear所指结点（利用C语言分别描述为rear->next->next和rear，利用标准Pascal语言分别描述为rear↑.next↑.next和rear），查找时间均为O(1)。

若用头指针来表示该链表，则查找时间均为O(n)。

例3请分析含有n个结点的顺序表，在进行插入和删除操作时的时间复杂度，并对计算的结果进行分析，由此可得到线性表的适用范围的什么结论。

解：值得注意的是，插入操作是指在某个元素前面或后面插入，是针对位置的，因此可插入的位置为n+1个，而删除操作是删除线性表中某个位置上的元素，是针对元素的，因此可删除的元素为n个。

设p i为在第i个元素之前插入一个元素的概率，在等概率的条件下，其值为1/(n+1)。

在第i个元素之前插入一个元素需要移动的元素的个数为：n-i+1。

所以，在长度为n的线性表中插入一个元素所需要移动的元素次数的数学期望值（平均次数）为：E in=∑+=+ -11)1 (niiinp=n/2同理，设q i为删除第i个元素的概率，在等概率的条件下，其值为1/n。

删除第i 个元素需要移动的元素的个数为：n-i。

所以，在长度为n的线性表中删除一个元素所需要移动的元素次数的数学期望值（平均次数）为：E del=∑=-niiinq1)(=(n-1)/2由于这两个操作的时间主要消耗在数据元素的移动上，所以插入算法和删除算法的时间复杂度均为：O(n)。

从上述分析可知，在顺序存储结构下，在线性表上插入或删除一个元素时需要平均移动线性表长度一半的元素个数，因此当n的值较大时，在顺序结构下，不宜对它频繁进行插入和删除操作。

附注：分析给定算法的复杂度，是一种常见的题目。

例4请给出线性表的顺序存储和链式存储结构选择的原则。

答：在实际应用中，主要根据具体问题的要求和性质，再结合顺序存储结构和链式存储结构的特点来决定，通常从以下几个方面考虑：(1)存储空间。

顺序存储结构要求事先分配其存储空间（即静态分配），所以难以估计存储空间的大小，估计过大会浪费存储空间，估计过小会造成存储空间的溢出。

链式存储结构的存储空间是动态分配的，只要机器中有空闲空间，就不会造成存储空间的溢出。

另外，还可以从存储密度的角度考虑，存储密度定义为：存储密度=结点数据本身占用的存储量/结点结构占用的存储量一般来说，存储密度越大，存储空间的利用率就越高。

显然，顺序存储结构的存储密度为1，而链式存储结构的存储密度小于1。

(2)运算时间。

顺序存储结构是已知的随机存储结构，便于元素的随机存储，即表中每个元素都可以在O(1)时间复杂度下迅速存取。

而链式存储结构中为了访问一个结点必须从头指针开始顺序查找，时间复杂度为O(n),故对于只进行查找操作而很少进行插入和删除操作的情况，采用顺序存储是比较合适的。

但是，在顺序存储结构上进行元素的插入和删除操作时，则需要大量元素的移动，尤其是线性表较长的情况。

在这种情况下，采用链式存储结构较好，因为在这种存储结构上进行插入和删除操作时，不需要元素的移动而效率较高。

(3)程序设计语言。

在不支持指针的概念和指针类型的程序设计语言中，可以采用静态链表（即利用游标实现）的方法来模拟动态存储结构。

对于问题规模不大的问题，采用静态链表来实现更加方便。

例5假设一个单循环链表，其结点含有三个域pre、data和next，其中data为数据域；pre为指针域，它的值为空指针；next为指针域，它指向后继结点。

请设计一个算法，将此表改成双向循环链表。

解：算法的基本思想是根据已知的单链表，一边复制数据，一边产生双向链表，最后首尾相连。

假设指针head指向链表的头结点。

算法描述如下：A1.//处理头结点[ A1.1. 令指针p指向指针head所指结点的后继结点；A1.2. p.pre←head；A1.3. q←p；A1.4. p←p.next； //指针p指向其所指结点的后继结点]A2.循环：当指针p≠head时，重复执行//修改结点的指针域pre，指针p所指向的结点为需要修改的结点，指针q所指向的结点为其前一结点[ A2.1. p.pre←q；A2.2. q←p； //将指针q指向指针p所指向的结点A2.3. p←p.next；]A3. //处理头结点的pre域head.pre←q；A4.算法结束.附注：本题给出了一种带头结点的双向循环链表的表示和构造方法。

以下例题线性表的遍历及其应用线性表的遍历是一种非常重要的基本运算，线性表的其它许多运算是基于该运算的。

下面举例介绍。

(1)求线性表的长度例7编写一个递归算法，计算并输出单链表的长度。

解：假设单链表不带头结点，结点结构有数据域data和指针域next，则其长度递归定义为：当单链表为空时，其长度为0，否则其长度为：1+除第一个结点外剩余的单链表的长度。

假设list为单链表的头指针，算法描述如下：listlen(p)[ 若 p为空指针，则len←0；否则len←1+listlen(p.next); //p.next是p所指向的结点的下一结点的地址返回len；]prnlen(p)[ x←listlen(p); 输出x；](2)判断线性表是否递增例8假设p是指向一个单链表的头指针，请写一个判断该线性表是否递增的算法。

解：若线性表是递增的，则输出“线性表是递增的”；否则输出“线性表不是递增的”。

算法描述如下：A1.//准备[ A1.1.flag←1；A1.2.令指针q指向指针p所指结点的后继结点；]A2．循环：当 flag为真且链表不结束时，重复执行[ 如果q.data>p.data，则[ p←q; //将p指针指向指针q所指的结点q←q.next; //指针q向下移动，指向其后继结点]否则 flag←0；]A3．如果 flag=1，则输出“线性表是递增的”;否则输出“线性表不是递增的”；A4. 算法结束.(3)线性表的输出基于顺序结构的线性表的输出比较简单，这里就不再赘述了。

下面介绍基于单链表存储结构的线性表的输出。

例9假设la是带头结点的单链表的头指针，试写一个逆序输出线性表的各结点的算法。

解：本题可先将单链表中的数据元素存放到一个数组中，然后逆序输出数组中的元素。

算法描述如下：A1.//准备[ i←0；令指针p指向链表的第一个结点；]A2. 循环：当p≠空指针时，重复执行[ A[i]←p.data； i←i+1； p←p.next；]A3．循环：j以-1为步长，从i-1到0，重复执行 [ 输出A[j]；]A4．算法结束.例10给定一个带表头结点的单链表，设head为头指针，结点的数据域为data，其为整型数据元素，next为指针域，试写一个算法完成按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间。

要求:不允许使用数组作辅助空间。

解：基本思想是不停的查找单链表中的最小元素，找到后就删除当前结点，直到单链表为空时为止。

这里设变量min存放每一趟的最小值。

令指针s和r分别指向最小值结点及其前驱结点,以便在找到具有最小值的结点后进行删除。

算法描述如下：A1．循环:当head.next≠空指针时，重复执行[ A1.1. 令指针 p指向指针head所指结点的后继结点；A1.2. min←p.data；A1.3. s←p; //令指针s指向指针p所指向的结点A1.4. r←head; //令指针r指向指针head所指向的结点A1.5.//查找具有最小数据元素的结点循环：当p≠空指针时，重复执行[ 如果p.data<min，则[ min←p.data； r←q； s←p；]q←p；p←p.next； //指针p后移一个位置]A1.6. //删除最小数据元素的结点[ A1.6.1. r.next←s.next；A1.6.2. 输出s.data；A1.6.3. 释放指针s所指结点；]]A2．释放头结点；A3．算法结束.3．线性表中结点的插入、删除及其应用线性表的基本运算中，结点的插入与删除是最重要的两种运算，许多算法设计与其有关。

(1)线性表中结点的插入与删除例11已知长度为n的线性表A采用顺序存储结构，请写一个时间复杂度为0(n)、空间复杂度为0(1)的算法，该算法删除线性表中所有值为item的数据元素（O(1)表示算法的辅助空间为常量）。

解：在顺序存储的线性表上删除元素，通常要涉及到一系列元素的移动（若删除第i 个元素，则第i+1至第n个元素要依次前移）。

本题要求删除线性表中所有值为item的数据元素，并未要求元素间的相对位置不变。

因此可以考虑设头尾两个指针（i=1，j=n），从两端向中间移动，凡遇到值为item的数据元素时，直接将右端元素左移至值为item 的数据元素位置。

算法描述如下：A1.//准备[ i←0； j←n-1；]A2.循环：当i<j时，重复执行[ A2.1.循环：当i<j且p[i]≠item时，重复执行i←i+1；A2.2.如果i<j，则[ 循环：当i<j且 p[j]=item时，重复执行j←j-1；]A2.3.如果i<j,则 [ p[i]←p[j]； i←i+1； j←j-1；]]A3. 算法结束.例12已知一个双向循环链表，从第二个结点至表尾递增有序。

试编写一个算法将第一个结点删除并插入表中适当位置，使整个链表递增有序。

设此链表没有头结点。

解：双向循环链表自第二个结点至表尾递增有序，要求将第一结点插入到链表中，使整个链表递增有序。

由于已给条件，故应先将第一结点从链表上摘下来，再将其插入到链表中的相应位置上。

由于是双向链表，不必象单链表那样必须知道要插入结点的前驱结点。

双向循环链表的结点结构定义为：(pre,data,next)。