第二章 答案.docx
- 文档编号:8923003
- 上传时间:2023-05-16
- 格式:DOCX
- 页数:24
- 大小:20.77KB
第二章 答案.docx
《第二章 答案.docx》由会员分享,可在线阅读,更多相关《第二章 答案.docx(24页珍藏版)》请在冰点文库上搜索。
第二章答案
一、选择题
1-5CBABA6-10CACCC11-15ACBCC
16-20ABBDD21-25DCADC26-30BBDDA
31C
二、判断题
1-5FFFFF6-10FFTFT11-15TTFFF16F
三综合应用题
1、
(1)
EmemtypeDelete(Elemtypea[],int&Length)
{
Elemtypetag=0;
Elemtypemin;
if(Length==0)
returnERROR;
for(inti=1;i { if(a[tag]>a[i]) tag=i; } min=a[tag]; a[tag]=a[Length-1]; Length--; returnmin; } (2) StatusListDelete_Sq(SqList*LA,inti,ElemType*e) { /*在顺序线性表L中删除第i个元素,并用e返回其值 //i的合法值为1≤i≤Listlength_Sq(L)*/ ElemType*q,*p;intn=0;/*定义局部变量*/ if((i<1)||(i>(*LA).length))returnERROR;/*i值不合法*/ p=&((*LA).elem[i-1]);/*p为被删除元素的位置*/ *e=*p;/*被删除元素的值赋给e*/ q=(*LA).elem+(*LA).length-1;/*表尾元素的位置*/ for(++p;p<=q;++p){*(p-1)=*p;++n;}/*被删除元素之后的元素左移*/ printf("n=%d\n",n); --(*LA).length;/*表长减1*/ returnOK; } (3) StatusListInsert_Sq(SqList*LA,inti,ElemTypee) {/*在顺序线性表L中第i个位置之前插入新的元素e, //i的合法值为1≤i≤Listlength_Sq(L)+1*/ ElemType*newbase,*q,*p;intn=0;/*定义局部变量*/ if(i<1||i>(*LA).length+1)returnERROR;/*值不合法*/ if((*LA).length>=(*LA).listsize){/*当前空间已满,增加分配*/ newbase=(ElemType*)realloc((*LA).elem,((*LA).listsize+LISTINCREMENT)*sizeof(ElemType)); if(! newbase)exit(OVERFLOW);/*存储分配失败*/ (*LA).elem=newbase;/*新基址*/ (*LA).listsize+=LISTINCREMENT;}/*增加存储容量*/ q=&((*LA).elem[i-1]);/*q为插入位置*/ for(p=&((*LA).elem[(*LA).length-1]);p>=q;--p){*(p+1)=*p;++n;}/*插入位置及之后的元素右移*/ printf("n=%d\n",n); *q=e;/*插入e*/ ++(*LA).length; returnOK; } 4、 voiddel_x(Sqlist&L,Elemtypex) { intk=0; for(i=0;i if(L.data[i]! =x) { L.data[k]=L.data[i]; k++; } L.length=k; } (5) boolDel_s_t(sqList&L,Elemtypes,Elemtypet) { inti,k=0; if(L.length==0||s>=t) returnfalse; for(i=0;i { if(L.data[i]>=s&&L.data[i]<=t) k++; else L.data[i-k]=L.data[i]; } L.length-=k; returntrue; } (6) boolDel_s_t(sqList&L,Elemtypes,Elemtypet) { inti,j; if(L.length==0||s>=t) returnfalse; for(i=0;i if(i>=L.length) returnfalse; for(j=i;j for(;j L.data[i]=L.data[j] L.length=i; returntrue; } (7) boolMerge(SqListA,SqListb,SqList&c) { if(A.length+B.length>C.maxSize) returnfalse; inti=0,j=0,k=0; while(i { if(A.data[i]<=B.data[j]) C.data[k++]=A.data[i++]; else C.data[k++]=B.data[j++]; } while(i C.data[k++]=A.data[i++]; while(j C.data[k++]=B.data[j++]; C.length=k; returntrue; } (8) boolDelete_Same(SqList&L) { if(L.length==0) returnfalse; inti,j; for(i=0,j=1;j if(L.data[i] L.data[++i]=L.data[j]; L.length=i+1; } 2、 LinkedListinvert(LinkedListL){ p=L->next;∥p为工作指针。 L->next=null;∥第一结点成为尾结点。 while(p! =null){ r=p->next; p->next=L;∥将p结点插到L结点前面。 L=p;∥L指向新的链表“第一”元素结点。 p=r; } returnL; } 3、 LinkListreverse(LinkList&L)//带头结点单链表的就地逆置 { p=L->next; L->next=null; while(p! =NULL) { r=p->next; p->next=L->next; L->next=p; p=r; } returnL; } 4、 voidMiniValue(LinkedListla){ ∥la是数据域为正整数且无序的单链表,本算法查找最小值结点且打印。 ∥若最小值结点的数值是奇数,则与后继结点值交换;否则,就删除其直接后继结点。 p=la->next;∥设la是头结点的头指针,p为工作指针。 pre=p;∥pre指向最小值结点,初始假定首元结点值最小。 while(p->next! =null){∥p->next是待比较的当前结点。 if(p->next->data pre=p->next; p=p->next;∥后移指针 } printf(“最小值=%d\n”,pre->data); if(pre->data%2! =0)∥处理奇数 if(pre->next! =null){∥若该结点没有后继,则不必交换 t=pre->data; pre->data=pre->next->data; pre->next->data=t; }∥交换完毕 else∥处理偶数情况 if(pre->next! =null){∥若最小值结点是最后一个结点,则无后继 u=pre->next; pre->next=u->next; free(u); }∥释放后继结点空间 } 5、 解法如下: 假定链表结点类型如下; structnode { intdata; node*next; }; voidsort(node*head) { node*p=head->next; while(p) { node*q=p->next; while(q) { if(q->data { head->data=p->data; p->data=q->data; q->data=head->data; } q=q->next; } p=p->next; } } 6、 LinkedListUnion(LinkedListla,LinkedListlb){ ∥la,lb分别是带头结点的两个单链表的头指针,链表中的元素值按递增序排列,本算法将两链表合并成一个按元素值递减次序排列的单链表。 pa=la->next; pb=lb->next;∥pa,pb分别是链表la和lb的工作指针 la->next=null;∥la作结果链表的头指针,先将结果链表初始化为空。 while(pa! =null&&pb! =null)∥当两链表均不为空时作 if(pa->data<=pb->data){ r=pa->next;∥将pa的后继结点暂存于r。 pa->next=la->next;∥将pa结点链于结果表中,同时逆置。 la->next=pa; pa=r;∥恢复pa为当前待比较结点。 } else{ r=pb->next;∥将pb的后继结点暂存于r。 pb->next=la->next;∥将pb结点链于结果表中,同时逆置。 la->next=pb; pb=r;∥恢复pb为当前待比较结点。 } while(pa! =null){∥将la表的剩余部分链入结果表,并逆置。 r=pa->next; pa->next=la->next; la->next=pa; pa=r; } while(pb! =null){ r=pb->next; pb->next=la->next; la->next=pb; pb=r; } returnla; } 7、 voidDel_Same(LinkList&L) { LNode*p=L->next,*q; while(p->next! =null) { q=p->next; if(p->data==q->data) { p->next=q->next; free(q); } else p=p->next; } } 8、 LinkedListDelete(LinkedListL) ∥L是带头结点的单链表,本算法删除其最小值结点。 {p=L->next;∥p为工作指针。 指向待处理的结点。 假定链表非空。 pre=L;∥pre指向最小值结点的前驱。 q=p;∥q指向最小值结点,初始假定第一元素结点是最小值结点。 while(p->next! =null) {if(p->next->data p=p->next;∥指针后移。 } pre->next=q->next;∥从链表上删除最小值结点 free(q);∥释放最小值结点空间 }∥结束算法delete。 9、 voidFun(Node**heada,Node**headb,inti,intj,intlen) { Node*p,*q,*r; p=*heada; q=*heada; intn=1; while(n++ p=p->next; q=p->next; n=0; while(n++ q=q->next; r=p->next; p->next=q->next; q->next=NULL; n=1; p=*headb; while(n++ p=p->next; q->next=p->next; p->next=r; } 10、 LinkedListdelinsert(LinkedListlist) { p=list->link; pre=list; q=p; while(p->link! =null) { if(p->link->data { pre=p;q=p->link; } if(q! =list->link) { pre->link=q->link; q->link=list->link; list->link=q; } } } 11、 LinkedListUnion(LinkedListha,hb) //线性表A和B代表两个集合,以链式存储结构存储,元素递增有序。 ha和hb分别是其链表的头指针。 本算法求A和B的并集 //AuB,仍用线性表表示,结果链表元素也是递增有序 {pa=ha->next;pb=hb->next;//设工作指针pa和pb pc=ha;//pb为结果链表当前结点的前驱指针 while(pa&&pb) if(pa->data {pc->next=pa;pc=pa;pa=pa->next;} elseif(pa->data>pb->data) { pc->next=pb;pc=pb;pb=pb->next; } else//处理pa->data=pb->data {pc->next=pa;pc=pa;pa=pa->next;u=pb;pb=pb->next;free(u);} if(pa) pc->next=pa;//若ha表未空,则链入结果表。 elsepc->next=pb;//若hb表未空,则链入结果表 free(hb);//释放hb头结点 return(ha); } 12、 LinkedListUnion(LinkedListla,LinkedListlb){ pa=la->next; pb=lb->next;∥设工作指针pa和pb; pc=la;∥结果表中当前合并结点的前驱的指针。 while(pa&&pb){ if(pa->data==pb->data){∥交集并入结果表中。 pc->next=pa; pc=pa; pa=pa->next; u=pb; pb=pb->next; free(u); } elseif(pa->data u=pa; pa=pa->next; free(u); } else{ u=pb; pb=pb->next; free(u); } } while(pa){ u=pa; pa=pa->next; free(u);∥释放结点空间 } while(pb){ u=pb; pb=pb->next; free(u);∥释放结点空间 } pc->next=null;∥置链表尾标记。 free(lb);∥注: 本算法中也可对B表不作释放空间的处理 returnla; } 13、 算法的基本设计思想: 对两个链表进行归并,但当A的一个元素,不是B中的一个元素时,才将其加入到新链表C中。 算法的代码: NODE*difference(NODE*A,NODE*B){ NODE*C,*last; C=last=(NODE*)malloc(sizeof(NODE)); while(A! =null&&B! =null){∥两均未空时循环 if(A->element last=append(last,A->element); A=A->link; } elseif(A->element==B->element){∥两表中相等元素不作结果元素 A=A->link; B=B->link; } else B=B->link;∥向后移动B表指针 } while(A! =null){ last=append(last,A->element); A=A->link; } last->link=null;∥置链表尾 last=C; C=C->link; free(last); returnC; } 14、 LinkedListLinkListInsertSort(LinkedListla){ ∥la是带头结点的单链表,其数据域是正整数。 本算法利用直接插入原则将链表整理成递增的有序链表。 if(la->next! =null){∥链表不为空表。 p=la->next->next;∥p指向第一结点的后继。 la->next->next=null;∥直接插入原则认为第一元素有序,从第二元素起依次插入。 while(p! =null){ r=p->next;∥暂存p的后继。 q=la; while(q->next! =null&&q->next->data q=q->next; p->next=q->next;∥将p结点链入链表。 q->next=p; p=r; } } returnla; } 15、 LinkedListDisCreat(LinkedListA) ∥A是带头结点的单链表,链表中结点的数据类型为整型。 本算法将A分解成两个单链表B和C,B中结点的数据小于零,C中结点的数据大于零。 处理之后,B表的头指针即为A表头指针,只需返回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指向新的待处理结点。 } returnC; } 16、 LinkedListDisCreat(LinkedListA){ ∥A是带头结点的单链表,本算法将其分解成两个带头结点的单链表,A表中含原表中序号 ∥为奇数的结点,B表中含原表中序号为偶数的结点。 链表中结点的相对顺序同原链表。 i=0;∥i记链表中结点的序号。 B=(LinkedList)malloc(sizeof(LNode);∥创建B表表头。 B->next=null;∥B表的初始化。 LinkedListra,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=null;∥在B表尾插入新结点; rb->next=p; rb=p;∥rb指向新的尾结点; } else{∥处理原序号为奇数的结点。 p->next=ra->next; ra->next=p; ra=p; } p=r;∥将p恢复为指向新的待处理结点。 } returnB; } 17、 intPattern(LinkedListA,LinkedListB){ ∥A和B分别是数据域为整数的单链表,本算法判断B是否是A的子序列。 如是,返回1;∥否则,返回0表示不是。 p=A;∥p为A链表的工作指针,本题假定A和B均无头结点。 pre=p;∥pre记住每趟比较中A链表的开始结点。 q=B;∥q是B链表的工作指针。 while(p&&q) if(p->data==q->data){ p=p->next; q=q->next; } else{ pre=pre->next; p=pre;∥A链表新的开始比较结点。 q=B; }∥q从B链表第一结点开始。 if(q==null) return1;∥B是A的子序列。 else return0;∥B不是A的子序列。 } 18、 voidRearrange(SeqLista;intn){ ∥a是具有n个元素的线性表,以顺序存储结构存储,线性表的元素是整数。 本算法重排线 ∥性表a,使所有值为负数的元素移到所有值为正数的数的前面。 i=0;j=n-1;∥i,j为工作指针(下标),初始指向线性表a的第1个和第n个元素。 t=a[0];∥暂存枢轴元素。 while(i while(i j--;∥若当前元素为大于等于零,则指针前移。 if(i a[i]=a[j]; i++; } while(i i++; if(i a[j--]=a[i];∥正数后移。 } a[i]=t;∥将原第一元素放到最终位置。 此枢纽是为了减少交换次数,正负皆可。 } 19、 voidderivative(ha){ q=ha; pa=ha->next; while(pa! =null){∥遍历到链表结束 if(pa->exp==0){∥若指数为0,即本项为常数项 q->next=pa->next;∥删常数项 free(pa); pa=q; } else{ pa->coef=(pa->coef)*(pa->exp); pa->exp--;∥指数项减1 q=pa; }∥前驱后移,或q->next pa=pa->next;∥取下一元素 }} 20、 voidAdjust(DLinkListL){
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第二章 答案 第二