计算机软件技术基础课后题答案20xx(1)

计算机软件技术基础课后题答案20xx(1)内容摘要：

顺序表 L 中 i=0。 while((i=Llength1)amp。 amp。 (x=Ldata[i])) i++； ／／找正确的插入位置 for(k=Llength1。 k=i； k) ／／元素从后往前依次后移 Ldata[k+1]=Ldata[k]； Ldata[i]=x； ／／ x 插入到正确位置 Llength++； ) L 是一个递减有序表，试写一个算法将 x 插入其中后仍保持 L 的有序性。 答：分析：此问题的关键是在链表中找到 x 的插入位置，因此需要两个指针一前一后地依次向后移动。 void LinkListinsert(LinkedList *L， int x){／／ x 插入有序链表 L 中 q=L； p=q— next； while(p!=NULLamp。 amp。 p— datax) ／ ／找到插入的位置 {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!=NULLamp。 amp。 ji1) ／／找到第 i1 个元素 {p=p— next； j++； } if(i=0||p==NULL) printf(”插入位置不正确＼ n” )； else {q=(LinkedList*)malloc(sizeof(LinkedList))； q— data=x； 7 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(imamp。 amp。 jn) {if([i][j]) ／／ A 中当前元素较小 {Cdata[k]=[il； i++； ] else {Cdata[k]=[j]。 j++； } ／／ B 中当前元素较小 k++； } if (i==m) for(t=j； tn； t++) {Cdata[k]=[t]。 k++； } ／／ B 表长度大于 A 表 else for(t=i； tm； t++) {Cdata[k]=[t]； k++； } ／／ A 表长度大于 B 表 Clength=m+n； return C。 } (2) VOid Linkmerge(LinkedList *A， LinkedList *B， LinkedList *C) {／／有序链表 A 和 B 归并成有序链表 C pa=A— next； pb=B— next； C=A； pc=C； while(paamp。 amp。 pb) ／／ A 和 B 都不为空时 {if(pa— datapb— data) ／／ A 当前结点值较小 {qa=panext； pCnext=pa； pc=pcnext； pa=qa； } else {qb=pbnext； pcnext=pb： pc=pcnext； 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 指向第 i1 和第 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 个元素 ,并将这峰元素插入到单链表 lb中第 j个结点之前 if(i0||j0||len0) exit(0)； p=la； k=1； pre=NULL； while(pamp。 amp。 ki) ／／在 la 表中查找第 i 个结点 {pre=p； p=pnext。 k++； } if(!p) exit(0)； q=p； k=l； ／／ p 指向 la 表中第 i 个结点 while(qamp。 amp。 klen) {q=q— next； k++； } ／／查找 la 表中第 i+len1 个结点 if(!q) exit(0)； if(pre==la) la=q— next； ／／ i=1 的情况 else pre— next=q— next； ／／完成删除 ／／将从 la 中删除的结点插入到 lb 中 if(j==1) {qnext=lb； lb=p； } ／／ j=1 时 8 else { r=lb。 k=1； ／／ j1 时 while(ramp。 amp。 kj1) {r=r— next； 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) {／／删除递减有序单链表 L 中值大于 min 且小于 max 的结点 q=L； if(minmax) {printf(” minmax＼ n” )； exit(0)； } else p=L— next； ／／ q 始终指向 p 的前驱 while(p— data=max) ／／当前元素大于或等于 max，则 p、 q 依次向后移动 {q=p； p=p— next； } while((p!=NULL)amp。 amp。 (p 一 datamin)) {／／当前元素的值比 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 depose(LinkedList *A， LinkedList *B) {／／单链表 A 分解成元素序号为奇数的单链表 A 和元素序号为偶数的单链表 B p=Anext； B=(LinkedList*)malloc(sizeof(LinkedList))； r=B； while(p!=NULLamp。 amp。 pnext!=NULL) {q=p— next； ／／ q 指向偶数序号的结点 p— next=q— next； ／／将 q 从 A 表中删除 r— next=q； ／／将 q 结点链接到 B 链表的末尾 r=q； ／／ r 总是指向 B 链表的最后 — 个结点 p=p— next； ／／ p 指向原链表 A 中的奇数序号的结点 } r— next=NULL； ／／将生成 B 链表中的最后一个结点的 next 域置为空 } 9．假设以两个元素值递增有序排列的线性表 A、 B 分别表示两个集合，要求另辟空间构造一个线性表 C，其元素为两集合的交集，且表 C 中的元素值也递增有序排列。 用顺序表实现并写出 C 的算法。 答：分析：用三个变量 i、 j、 k 分别指示 A、 B、 C 三个顺序表的当前位置，若 A、 B 表中当前元素值相同，则写入 C 中，并使 i、 j、 k 值增 1；若 A 表元素值较小，则使 i 增 1；若 B 表元素值较小，则使 j 增 1，直到有一个表先结束。 SeqLiSt *intersection(SeqList A， SeqList B， SeqList *C) {／／求元素依值递增有序排列的顺序表 A、 B 的交集 C i=0； j=0； k=0； while((i=)amp。 amp。 (j=)) {if([i]==[j]) ／／找到值相同的元素 {Cdata[k]=[i]； ／／相同元素写入 C 表中 k++； i++； j++； } else if([i][j]) i++；／／ A、 B 表当前元素不等，值较小的下标增 1 else j++； } Clength=k； return C； } 9 11．假设在长度大于 1 的 单循环链表中，既无头结点也无头指针。 s 为指向链表中某个结点的指针，试编写算法删除结点 *s 的直接前驱结点。 答：分析：因为既不知道此单循环链表的头指针，也不知道其尾指针，所以找 s 的前驱就只能从 s 开始，顺次向后寻找。 void DeletePre(Linkedlist *s) {／／删除单循环链表中结点 s 的直接前驱 p=s； while(p— next— next!=s) p=p— next； ／／找到 s 的前驱的前驱 p q=p— next； ／／ q 是 p 的后继，即 s 的前驱 p— next=s； ／／将 q 删除 free(q)； } 12．计算带头结点的循环链表的结点个数。 答： int number(Linkedlist *head) {／／计算单循环链表中结点的个数 p=head— next； i=0； while(p!=head) {i++； p=pnext； } return i； } 13．已知由单链表表示的线性表中，含有三类字符的数据元素 (如：字母字符、数字字符和其他字符 )，试编写算法构造三个以循环链表表示的 线性表，使得每个表中只含有同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。 答：分析： p 指向待处理的单链表的首元结点，构造三个空的单循环链表，分别存储三类字符，其中一个表可使用原来的单链表。 q 指向 p 的下一个结点，根据 *p 的数据域的值将其插入到不同的链表上。 再把 q。