大连理工大学《数据结构》作业2016-参考答案

数据结构作业参考答案作业1.线性表编程作业：1．将顺序表逆置，要求用最少的附加空间。参考答案#includestdio.h#includemalloc.h#includeprocess.h#defineLIST_INIT_SIZE100#defineLISTINCREMENT10#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2typedefintStatus;typedefintElemType;typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;//创建空顺序表StatusInitList_Sq(SqList&L){L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;returnOK;}//顺序表在第i个元素之前插入eStatussxbcr(SqList&L,inti,ElemTypee){数据结构作业参考答案ElemType*p,*q;if((i1)||(iL.length+1))return(ERROR);else{q=&(L.elem[i-1]);for(p=&(L.elem[L.length-1]);p=q;--p)*(p+1)=*p;*q=e;++L.length;return(OK);}}//顺序表显示voidxsList(SqListL){inti=L.length,k;for(k=0;ki;k++)printf(%d,L.elem[k]);printf(\n);}//顺序表逆置voidnizhi(SqList&L){inti=0,j=L.length-1;ElemTypetemp;for(;ij;i++,j--){temp=L.elem[i];L.elem[i]=L.elem[j];L.elem[j]=temp;}}main(){SqListL;charflag1='y',flag2='n';inti;ElemTypek;数据结构作业参考答案if(InitList_Sq(L)){printf(建立空顺序表成功！\n);do{printf(当前线性表长度为：%d\n,L.length);printf(请输入要插入元素的位置：);scanf(%d,&i);printf(请输入要插入的元素值：);scanf(%d,&k);if(sxbcr(L,i,k)){printf(插入成功，插入后顺序表长度为：%d\n,L.length);printf(插入后的顺序表为：);xsList(L);}elseprintf(插入失败);printf(\n继续插入元素？(y/n));fflush(stdin);scanf(%c,&flag1);}while(flag1=='y');nizhi(L);printf(顺序表逆置后为：\n);xsList(L);}}2．从键盘读入n个整数（升序），请编写算法实现：（1）CreateList()：建立带表头结点的单链表；（2）PrintList()：显示单链表，（形如：H-10-20-30-40）;（3）InsertList()：在有序单链表中插入元素x；（4）ReverseList()：单链表就地逆置；（5）DelList()：在有序单链表中删除所有值大于mink且小于maxk的元素。选作：使用文本菜单完成功能选择及执行。参考答案：#includestdio.h#includemalloc.h数据结构作业参考答案#includeprocess.h#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2typedefintStatus;typedefintElemType;typedefstructnode{ElemTypedata;structnode*link;}Lnode,*LinkList;//头插法建立单链表voidCreate_L1(LinkList&L,intn){LinkListp;inti;L=(LinkList)malloc(sizeof(Lnode));L-link=NULL;for(i=n;i0;--i){p=(LinkList)malloc(sizeof(Lnode));scanf(%d,&p-data);p-link=L-link;L-link=p;}}//尾插法建立单链表voidCreate_L2(LinkList&L,intn){LinkLists,p;inti;L=(LinkList)malloc(sizeof(Lnode));L-data=0;L-link=NULL;数据结构作业参考答案p=L;for(i=1;i=n;i++){s=(LinkList)malloc(sizeof(Lnode));scanf(%d,&s-data);s-link=NULL;p-link=s;p=s;}}//查找是否存在结点eLinkListdlbcz(LinkListL,ElemTypee){LinkListp=L-link;while(p!=NULL&&p-data!=e)p=p-link;return(p);}//在第i个元素之前插入结点eStatusListInsert_L(LinkListL,inti,ElemTypee){LinkListp=L,s;intj=0;while(p&&ji-1){p=p-link;++j;}if(!p||ji-1)returnERROR;s=(LinkList)malloc(sizeof(Lnode));s-data=e;s-link=p-link;p-link=s;returnOK;}//删除第i个结点StatusListDelete_L(LinkListL,inti,ElemType&e){LinkListp=L,q;intj=0;数据结构作业参考答案while(p-link&&ji-1){p=p-link;++j;}if(!(p-link)||ji-1)returnERROR;q=p-link;p-link=q-link;e=q-data;free(q);returnOK;}//求第i个元素值StatusGetElem_L(LinkListL,inti,ElemType&e){intj=1;LinkListp=L-link;while(p&&ji){p=p-link;j++;}if(!p||ji)returnERROR;e=p-data;returnOK;}//显示单链表中元素voidxsList(LinkListL){LinkListp=L-link;while(p){printf(%d,p-data);p=p-link;}}//删除大于mink且小于maxk的元素voidDelList(LinkList&L,ElemTypemink,ElemTypemaxk){LinkListp=L,q;while(p-link&&p-link-datamink)p=p-link;数据结构作业参考答案q=p;while(q&&q-datamaxk)q=q-link;p-link=q;}//就地升序排序voidsh_sort(LinkList&L){LinkListp=L-link,pre=L,q=L-link-link,u;p-link=NULL;while(q){p=L-link;pre=L;while(p&&p-dataq-data){pre=p;p=p-link;}u=q-link;pre-link=q;q-link=p;q=u;}}//就地逆置voidnizhi(LinkList&L){LinkListp=L-link,q=L-link-link,u;p-link=NULL;while(q){u=q-link;q-link=L-link;L-link=q;q=u;}}数据结构作业参考答案//有序表插入voidyxcharu(LinkList&L,ElemTypee){LinkListpre,p,s;pre=L;p=L-link;while(p&&p-datae){pre=p;p=p-link;}s=(LinkList)malloc(sizeof(Lnode));s-data=e;s-link=p;pre-link=s;}main(){LinkListL;intn,i,mink,maxk;ElemTypee;charchoice='0';while(choice!='q'){printf(\n****************\n);printf(1.建立单链表);printf(2.取元素值);printf(3.查找\n);printf(4.插入);printf(5.删除);printf(6.显示\n);printf(7.删除大于mink且小于maxk的元素值);printf(8.就地升序排序\n);printf(9.就地逆置);printf(a.有序表插入);printf(q.退出\n);printf(\n请选择操作：);fflush(stdin);scanf(%c,&choice);数据结构作业参考答案switch(choice){case'1':printf(请输入单链表中结点个数：);scanf(%d,&n);Create_L2(L,n);break;case'2':printf(请输入元素位序：);scanf(%d,&i);GetElem_L(L,i,e);printf(元素值为：%d\n,e);break;case'3':printf(请输入要查找的元素：);scanf(%d,&e);if(dlbcz(L,e))printf(查找成功！);elseprintf(查找失败。);break;case'4':printf(请输入插入位置：);scanf(%d,&i);printf(请输入要插入的元素：);scanf(%d,&e);if(ListInsert_L(L,i,e))printf(插入成功！单链表为：);elseprintf(插入失败。);break;case'5':printf(请输入删除位置：);scanf(%d,&i);if(ListDelete_L(L,i,e))printf(删除成功！);elseprintf(删除失败。\n);break;case'6':printf(\n单链表为：);xsList(L);break;case'7':printf(请输入mink和maxk:);scanf(%d,%d,&mink,&maxk);DelList(L,mink,maxk);数据结构作业参考答案break;case'8':sh_sort(L);break;case'9':nizhi(L);break;case'a':printf(请输入在有序表中插入的元素值:);scanf(%d,&e);yxcharu(L,e);break;}}}作业2.栈、队列、数组非编程作业：1．若进栈序列为ABCD，请写出全部可能的出栈序列和不可能的出栈序列。参考答案：可能的出栈序列：(14种)dcbacdbabacdcbdaadcbcbadbdcaacdbbcdaacbdbcadabdcbadcabcd不可能的出栈序列：(10种)dbcadbacdabcdacbdcabcabdcdabbdaccadbadbc2．简要说明循环队列如何判断队满和队空？参考答案：当牺牲一