发布时间 : 星期六 文章最完整的数据结构1800题含答案更新完毕开始阅读
片段语句如下:
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 a[i]:=t； END; [算法讨论] 分界元素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结