内容发布更新时间 : 2024/5/15 2:30:04星期一 下面是文章的全部内容请认真阅读。
Status DeleteAndInsertSub(LinkList &la,LinkList &lb,int i,int j,int len)緘頰垒嚙缨輥榮。 { }
2、17 试写一算法，在无头结点得动态单链表上实现线性表操作Insert(L,i,b)，并与在带头结点得动态单链表上实现相同操作得算法进行比较。鸦饼掙歡东窑赎。 2、18试写一算法，实现线性表操作Delete(L,i)，并与在带头结点得动态单链表上实现相同操作得算法进行比较。埚孫蔺詿騰語頂。 LinkList p,q,s,prev=NULL; int k=1;
if(i<0||j<0||len<0) return INFEASIBLE; // 在la表中查找第i个结点 p=la;
while(p&&k if(!p)return INFEASIBLE; // 在la表中查找第i+len-1个结点 q=p; k=1; while(q&&k if(!q)return INFEASIBLE; // 完成删除，注意，i=1得情况需要特殊处理 if(!prev) la=q->next; else prev->next=q->next; // 将从la中删除得结点插入到lb中 if(j=1){ } else{ } return OK; s=lb; } if(!s)return INFEASIBLE; q->next=s->next; s->next=p; //完成插入 k=1; while(s&&k s=s->next; k++; q->next=lb; lb=p; q=p->next; k++; prev=p; p=p->next; k++; 2、19 已知线性表中得元素以值递增有序排列，并以单链表作存储结构。试写一高效得算法，删除表中所有值大于mink且小于maxk得元素（若表中存在这样得元素），同时释放被删结点空间，并分析您得算法得时间复杂度（注意，mink与maxk就是给定得两个参变量，它们得值可以与表中得元素相同，也可以不同）。 笃噜镉馋販緇濑。 解： Status ListDelete_L(LinkList &L,ElemType mink,ElemType maxk)达横筚構饷毁賡。 { } 2、20 同2、19题条件，试写一高效得算法，删除表中所有值相同得多余元素（使得操作后得线性表中所有元素得值均不相同），同时释放被删结点空间，并分析您得算法得时间复杂度。诎膚楨櫞袞樁镤。 解： void ListDelete_LSameNode(LinkList &L) { LinkList p,q,prev; p=L; prev=p; p=p->next; while(p){ prev=p; p=p->next; if(p&&p->data==prev->data){ } prev->next=p->next; q=p; p=p->next; free(q); LinkList p,q,prev=NULL; if(mink>maxk)return ERROR; p=L; prev=p; p=p->next; while(p&&p->data return OK; if(p->data<=mink){ } else{ } prev->next=p->next; q=p; p=p->next; free(q); prev=p; p=p->next; } } 2、21 试写一算法，实现顺序表得就地逆置，即利用原表得存储空间将线性表 ?a1,?,an?逆置为 ?an,?,a1?。 解： // 顺序表得逆置 Status ListOppose_Sq(SqList &L) { } 2、22 试写一算法，对单链表实现就地逆置。 解： // 带头结点得单链表得逆置 Status ListOppose_L(LinkList &L) { } 2、23 设线性表 LinkList p,q; p=L; p=p->next; L->next=NULL; while(p){ } return OK; q=p; p=p->next; q->next=L->next; L->next=q; int i; ElemType x; for(i=0;i return OK; x=L、elem[i]; L、elem[i]=L、elem[L、length-1-i]; L、elem[L、length-1-i]=x; A??a1,a2,?,am?，B??b1,b2,?,bn?，试写一个按下列规则合并A，B为线性表C??a1,b1,?,am,bm,bm?1,?,bn? C??a1,b1,?,an,bn,an?1,?,am? C得算法，即使得 当m?n时； 当m?n时。 线性表A，B与C均以单链表作存储结构，且C表利用A表与B表中得结点空间构成。注意：单链表得长度 值m与n均未显式存储。儉紆獸蠼邓劊颅。 解： // 将合并后得结果放在C表中，并删除B表 Status ListMerge_L(LinkList &A,LinkList &B,LinkList &C)聽祯搶杩阔髅锉。 { } 2、24 假设有两个按元素值递增有序排列得线性表A与B，均以单链表作存储结构，请编写算法将A表与B表归并成一个按元素值递减有序（即非递增有序，允许表中含有值相同得元素）排列得线性表C，并要求利用原表（即A表与B表）得结点空间构造C表。埚傴厅婵閩頎杩。 解： // 将合并逆置后得结果放在C表中，并删除B表 Status ListMergeOppose_L(LinkList &A,LinkList &B,LinkList &C)电秽颗鐙誄談糞。 { LinkList pa,pb,qa,qb; pa=A; pb=B; qa=pa; qb=pb; // 保存pa得前驱指针 // 保存pb得前驱指针 LinkList pa,pb,qa,qb; pa=A->next; pb=B->next; C=A; while(pa&&pb){ } if(!pa)qb->next=pb; pb=B; free(pb); return OK; qa=pa; qb=pb; pa=pa->next; pb=pb->next; qb->next=qa->next; qa->next=qb; pa=pa->next; pb=pb->next; A->next=NULL; C=A; while(pa&&pb){ if(pa->data qa=pa; pa=pa->next; qa->next=A->next; //将当前最小结点插入A表表头 A->next=qa; } } } qb=pb; pb=pb->next; qb->next=A->next; //将当前最小结点插入A表表头 A->next=qb; while(pa){ } while(pb){ } pb=B; free(pb); return OK; qb=pb; pb=pb->next; qb->next=A->next; A->next=qb; qa=pa; pa=pa->next; qa->next=A->next; A->next=qa; 2、25 假设以两个元素依值递增有序排列得线性表A与B分别表示两个集合（即同一表中得元素值各不相同），现要求另辟空间构成一个线性表C，其元素为A与B中元素得交集，且表C中得元素有依值递增有序排列。试对顺序表编写求C得算法。镗萦廣导篳黌邺。 解： // 将A、B求交后得结果放在C表中 Status ListCross_Sq(SqList &A,SqList &B,SqList &C) { } 2、26 要求同2、25题。试对单链表编写求C得算法。 解： int i=0,j=0,k=0; while(i return OK; if(A、elem[i] if(A、elem[i]>B、elem[j]) else{ } ListInsert_Sq(C,k,A、elem[i]); i++; k++; j++; i++;