《计算机软件技术基础》课后题答案 - 图文(4)

for(k=L->length-1;k>=i；k--) ／／元素从后往前依次后移 L->data[k+1]=L->data[k]；

L->data[i]=x； ／／x插入到正确位置 L->length++； )

3.设单链表L是一个递减有序表，试写一个算法将x插入其中后仍保持L的有序性。

答：分析：此问题的关键是在链表中找到x的插入位置，因此需要两个指针一前一后地依次向后移动。

void LinkListinsert(LinkedList *L，int x){／／x插入有序链表L中 q=L；p=q—>next；

while(p!=NULL&&p—>data>x) ／／找到插入的位置 {q=p；p=p—>next； }

s=(LinkedList*)malloc(sizeof(LinkedList))； ／／生成新结点 S—>data=x； S—>next=p； q—>next=s； }

4. 试写出在不带头结点的单链表的第i个元素之前插入一个元素的算法。 答：分析：对不带头结点的链表操作时，要注意对第一个结点和其他结点操作的不同。

void LinkedListlnsert(LinkedList *L，int x，int i) {／／不带头结点的单链表的第i个元素之前插入一个元素 p=L：j=1;

while(p!=NULL&&jnext；j++；}

if(i<=0||p==NULL) printf(”插入位置不正确＼n”)；

16

else {q=(LinkedList*)malloc(sizeof(LinkedList))；q—>data=x； if(i==1) {q—>next=L；L=q；} ／／在第一个元素之前插入 else{q—>next=p—>next；p—>next=q；} ／／在其他位置插入 } }

5．设A、B是两个线性表，其表中元素递增有序，长度分别为m和n。试写一算法分别以顺序存储和链式存储将A和B归并成一个仍按元素值递增有序的线性表C。

答：(1)分析：用三个变量i、j、k分别指示A、B、C三个顺序表的当前位置，将A、B表中较小的元素写入C中，直到有一个表先结束。最后将没结束的表的剩余元素写入C表中。

SeqList *Seqmerge(SeqList A，SeqList B，SeqList *C){／／有序顺序表A和B归并成有序顺序表C

i=0；j=0；k=0； ／／i，i，k分别为顺序表A，B，C的下标 while(i

{if(A.data[i]data[k]=A.data[il；i++； ]

else {C->data[k]=B.data[j];j++；} ／／B中当前元素较小 k++； }

if (i==m) for(t=j；tdata[k]=B.data[t];k++；} ／／B表长度大于A表

else for(t=i；tdata[k]=A.data[t]；k++；} ／／A表长度大于B表

C->length=m+n； return C;} (2)

17

VOid Linkmerge(LinkedList *A，LinkedList *B，LinkedList *C) {／／有序链表A和B归并成有序链表C pa=A—>next；pb=B—>next；C=A；pc=C； while(pa&&pb) ／／A和B都不为空时

{if(pa—>datadata) ／／A当前结点值较小

{qa=pa->next； pC->next=pa； pc=pc->next； pa=qa；}

else {qb=pb->next；pc->next=pb：pc=pc->next；pb=qb；} ／／B当前结点值较小 }

if(pa)pc—>next=pa； ／／A没有结束，将A表剩余元素链接到C表 if(pb)pc—>next=pb； ／／B没有结束，将B表剩余元素链接到C表 free(B)； ／／释放B表的头结点 }

本算法需要遍历两个线性表，因此时间复杂度为O(m+n)。

6．设指针la和lb分别指向两个不带头结点的单链表的首结点，设计从表la中删除第i个元素起共len个元素，并将这些元素插入到lb中第j个结点之前的算法。

答：分析：先在la中找到第i个结点，分别用两个指针pre和p指向第i-1和第i个结点，然后用指针q从第i个结点起向后走len个元素，使q指向此位置。然后在lb中找到第j个结点，将p所指向的la表中的第i个及q所指向的最后一个共len个结点插入到lb中。

void Deletelnsert(LinkedList *la，LinkedList *lb，int i，int j, int len)

{／／删除不带头结点的单链表la中第i个元素起共len个元素,并将这峰元素

18

插入到单链表lb中第j个结点之前 if(i<0||j<0||len<0) exit(0)； p=la；k=1；pre=NULL；

while(p&&knext; k++； } if(!p) exit(0)；

q=p；k=l； ／／p指向la表中第i个结点

while(q&&knext； k++；} ／／查找la表中第i+len-1个结点

if(!q) exit(0)；

if(pre==la) la=q—>next； ／／i=1的情况 else pre—>next=q—>next； ／／完成删除 ／／将从la中删除的结点插入到lb中

if(j==1) {q->next=lb； lb=p； } ／／j=1时 else { r=lb; k=1； ／／j>1时

while(r&&knext； k++；} ／／查找Lb表中第i—1个元素

if(!r) exit(0)；

q—>next=r—>next；r—>next=p； ／／完成插入 } }

7．单链表L是一个递减有序表，试写一高效算法，删除表中值大于min且小于max的结点(若表中有这样的结点)，同时释放被删结点空间，这里min和max是两个给定的参数。

答：LinkedList delete(LinkedList *L，int min，int max)

19

{／／删除递减有序单链表L中值大于min且小于max的结点 q=L；

if(min>max) {printf(”min>max＼n”)；exit(0)；} else p=L—>next； ／／q始终指向p的前驱

while(p—>data>=max) ／／当前元素大于或等于max，则p、q依次向后移动

{q=p；p=p—>next；}

while((p!=NULL)&&(p一>data>min))

{／／当前元素的值比min大同时比max小，删除p指向的结点 q—>next=p—>next， free(p)；p=q—>next； } return L； }．

8．编写一个算法将一个头结点指针为pa的单链表A分解成两个单链表A和B，其头结点指针分别为pa和pb，使得A链表中含有原链表A中序号为奇数的元素，而B链表中含有原链表A中序号为偶数的元素，且保持原来的相对顺序。 答：分析：用两个工作指针p和q分别指示序号为奇数和序号为偶数的结点，将q所指向的结点从A表删除，并链接到B表。 void decompose(LinkedList *A，LinkedList *B)

{／／单链表A分解成元素序号为奇数的单链表A和元素序号为偶数的单链表B p=A->next； B=(LinkedList*)malloc(sizeof(LinkedList))； r=B；

while(p!=NULL&&p->next!=NULL)

{q=p—>next； ／／q指向偶数序号的结点 p—>next=q—>next； ／／将q从A表中删除 r—>next=q； ／／将q结点链接到B链表的末尾

20