发布时间 : 星期五 文章数据结构考研复习题--第二章--线性表（带答案）更新完毕开始阅读51301d7bddccda38376baf2b
]∥结束奇数链结点
s:=r;∥s指向新的待排序结点。 ]∥结束“WHILE(s<>NIL)DO” ENDP；∥结束整个算法。 [算法讨论]由于算法要求“不得使用NEW过程申请空间，也没明确指出链表具有头结点，所以上述算法复杂些，它可能需要在第一个结点前插入新结点，即链表的头指针会发生变化。如有头结点，算法不必单独处理在第一个结点前插入结点情况，算法会规范统一，下面的（1）是处理带头结点的例子。算法中偶数链上结点是靠数据整除2等于0（DATA DIV 2=0）判断的。
类似本题的其它题解答如下：
（1）[题目分析]本题基本类似于上面第7题，不同之处有二。一是带头结点，二是分解后的两个链表，一个是数据值小于0，另一个是数据值大于0。由于没明确要求用类PASCAL书写算法，故用C书写如下。
void DisCreat1(LinkedList A)
∥A是带头结点的单链表，链表中结点的数据类型为整型。本算法将A分解成两个单链表B和C，B中结点的数据小于零，C中结点的数据大于零。 {B=A;
C=(LinkedList )malloc(sizeof(LNode));∥为C申请结点空间。 C->next=null ∥C初始化为空表。 p=A->next; ∥p为工作指针。 B->next=null; ∥B表初始化。 while(p!=null)
{r=p->next; ∥暂存p的后继。
if (p->data<0)∥小于0的放入B表。
{p->next=B->next; B->next=p; }∥将小于0的结点链入B表。 else {p->next=C->next; C->next=p; } p=r;∥p指向新的待处理结点。 }
}∥算法结束。
[算法讨论]因为本题并未要求链表中结点的数据值有序，所以算法中采取最简单方式：将新结点前插到头结点后面（即第一元素之前）。 （2） 本题同上面第7题，除个别叙述不同外，本质上完全相同，故不再另作解答。
（3）[题目分析]本题中的链表有头结点，分解成表A和表B，均带头结点。分解后的A表含有原表中序号为奇数的元素，B表含有原A表中序号为偶数的元素。由于要求分解后两表中元素结点的相对顺序不变，故采用在链表尾插入比较方便，这使用一指向表尾的指针即可方便实现。
void DisCreat3(LinkedList A)
∥A是带头结点的单链表，本算法将其分解成两个带头结点的单链表，A表中含原表中序号为奇数
∥的结点，B表中含原表中序号为偶数的结点。链表中结点的相对顺序同原链表。 {i=0;∥i记链表中结点的序号。
B=(LinkedList)malloc(sizeof(LNode);∥创建B表表头。 B->next=null; ∥B表的初始化。
LinkedList ra,rb;∥ra和rb将分别指向将创建的A表和B表的尾结点。
ra=A;rb=B;
p=A->next; ∥p为链表工作指针，指向待分解的结点。 A->next=null; ∥置空新的A表 while(p!=null)
{r=p->next; ∥暂存p的后继。 i++;
if(i%2==0) ∥处理原序号为偶数的链表结点。
{p->next=rb->next;∥在B表尾插入新结点； rb->next=p; rb=p;∥rb指向新的尾结点； }
else∥处理原序号为奇数的结点。
{p->next=ra->next; ra->next=p; ra=p; }
p=r; ∥将p恢复为指向新的待处理结点。 }∥算法结束
8．[题目分析]题目要求重排n个元素且以顺序存储结构存储的线性表，使得所有值为负数的元素移到正数元素的前面。这可采用快速排序的思想来实现，只是提出暂存的第一个元素（枢轴）并不作为以后的比较标准，比较的标准是元素是否为负数。 int Rearrange（SeqList a; int n)
∥a是具有n个元素的线性表，以顺序存储结构存储，线性表的元素是整数。本算法重
排线性表a，
∥使所有值为负数的元素移到所有值为正数的数的前面。 {i=0; j=n-1; ∥ i,j为工作指针（下标），初始指向线性表a的第1个和第n个元
素。
t=a[0]; ∥暂存枢轴元素。 while(i {while(i while(i a[i]=t; ∥将原第一元素放到最终位置。 } [算法讨论] 本算法时间复杂度为O（n）。算法只是按题目要求把正负数分开，如要求统计负数和大于等于零的个数，则最后以t来定。如t为负数，则0至i共i+1个负数，n-1-i个正数（包括零）。另外，题目并未提及零的问题，笔者将零放到正数一边。对此问题的扩充是若元素包含正数、负数和零，并要求按负数、零、正数的顺序重排线性表，统计负数、零、正数的个数。请读者利用上面解题思想自行解答。 类似本题的选了5 个题，其解答如下： （1）与上面第8题不同的是，这里要求以an为参考元素，将线性表分成左右两部分。左半部分的元素都小于等于an，右半部分的元素都大于an，an位于分界位置上。其算法主要片段语句如下: i=1;j=n; t=a[n]; ∥暂存参考元素。 while(i {while(i while(i a[i]=t; ∥参考元素置于分界位置。 (2) [题目分析]本题要求将线性表A分成B和C两个表，表B和表C不另占空间，而是利用表A的空间，其算法与第8题相同。这里仅把表B和表C另设空间的算法解答如下： void Rearrange2(int A[],B[],C[]) ∥线性表A有n个整型元素，顺序存储。本算法将A拆成B和C 两个表，B中存放 大于 ∥等于零的元素，C中存放小于零的元素。 {i=0; ∥i，j，k是工作指针，分别指向A、B和C表的当前元素。 j=k=-1; ∥j，k初始化为-1。 while(i {if(A[i]<0) C[++k]=A[i++]; ∥将小于零的元素放入C表。 else B[++j]=A[i++]; ∥将大于零的元素放入B表。 [算法讨论]本题用一维数组存储线性表，结果线性表B和C中分别有j+1和k+1个元素。若采用教材中的线性表，则元素的表示作相应改变，例如A.elem[i]，而最后B和C表应置上表的长度，如B.length=j和C.length=k。 (3) 本题与第8题本质上相同，第8题要求分开正数和负数，这里要求分开奇数和偶数，判别方式是a[i]%2==0，满足时为偶数，反之为奇数。 (4) 本题与第8题相同，只是叙述不同。 (5) 本题与第8题基本相同，不同之处在于这里的分界元素是整数19（链表中并不要 求一定有19）。本题要求用标准pascal描述算法，如下所示。 TYPE arr=ARRAY[1..1000] OF integer； VAR a：arr； PROCEDURE Rearrange5（VAR a：arr）； ∥a是n（设n=1000）个整数组成的线性表，用一维数组存储。本算法将n个元素 中所有大于等于19的整数放在所有小于19的整数之后。 VAR i,j,t：integer； BEGIN i:=1；j:=n；t:=a[1] ；∥i,j指示顺序表的首尾元素的下标，t暂存分界元素 WHILE（i WHILE （i IF（i IF（i [算法讨论] 分界元素t放入a[i]，而不论它的值如何。算法中只用了一个t中间变量，符合空间复杂度O(1)的要求。算法也满足时间复杂度O(n)的要求。 9．[题目分析] 本题要求在单链表中删除最小值结点。单链表中删除结点，为使结点删除后不出现“断链”，应知道被删结点的前驱。而“最小值结点”是在遍历整个链表后才能知道。所以算法应首先遍历链表，求得最小值结点及其前驱。遍历结束后再执行删除操作。 LinkedList Delete（LinkedList L） ∥L是带头结点的单链表，本算法删除其最小值结点。 {p=L->next； ∥p为工作指针。指向待处理的结点。假定链表非空。 pre=L； ∥pre指向最小值结点的前驱。 q=p； ∥q指向最小值结点，初始假定第一元素结点是最小值结点。 while（p->next!=null） {if（p->next->data pre->next=q->next；∥从链表上删除最小值结点 free（q）； ∥释放最小值结点空间 }∥结束算法delete。 [算法讨论] 算法中函数头是按本教材类C描述语言书写的。原题中void delete（linklist &L），是按C++的“引用”来写的，目的是实现变量的“传址”，克服了C语言函数传递只是“值传递”的缺点。 10．[题目分析] 本题要求将链表中数据域值最小的结点移到链表的最前面。首先要查找最小值结点。将其移到链表最前面，实质上是将该结点从链表上摘下（不是删除并回收空间），再插入到链表的最前面。 LinkedList delinsert（LinkedList list） ∥list是非空线性链表，链结点结构是（data，link），data是数据域，link是链域。 ∥本算法将链表中数据域值最小的那个结点移到链表的最前面。 {p=list->link；∥p是链表的工作指针 pre=list； ∥pre指向链表中数据域最小值结点的前驱。 q=p； ∥q指向数据域最小值结点，初始假定是第一结点 while （p->link!=null） {if（p->link->data if (q!=list->link) ∥若最小值是第一元素结点，则不需再操作 {pre->link=q->link； ∥将最小值结点从链表上摘下； q->link= list->link；∥将q结点插到链表最前面。 list->link=q； } }∥算法结束 [算法讨论] 算法中假定list带有头结点，否则，插入操作变为q->link=list；list=q。 11．[题目分析] 知道双向循环链表中的一个结点，与前驱交换涉及到四个结点（p结点，前驱结点，前驱的前驱结点，后继结点）六条链。 void Exchange（LinkedList p） ∥p是双向循环链表中的一个结点，本算法将p所指结点与其前驱结点交换。 {q=p->llink；