数据结构上机试题

数据结构上机试题一、顺序表的操作（1）插入元素操作：将新元素x插入到顺序表a中第i个位置。（2）删除元素操作：删除顺序表a中第i个元素。#includestdio.h#includestdlib.h#defineLIST_INIT_SIZE10#defineLISTINCREMENT10typedefintElemType;typedefintstatus;#defineOK1#defineOVERFLOW-1#defineERROR0ElemType*newbase,*p,*q;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;}statusListInsert_Sq(SqList&L,inti,ElemTypee){if(i1||iL.length+1)returnERROR;if(L.length=L.listsize){newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;}q=&(L.elem[i-1]);for(p=&(L.elem[L.length-1]);p=q;--p)*(p+1)=*p;*q=e;++L.length;returnOK;}statusListDelete_Sq(SqList&L,inti,ElemType&e){if((i1)||(iL.length))returnERROR;p=&(L.elem[i-1]);e=*p;q=L.elem+L.length-1;for(++p;p=q;++p)*(p-1)=*p;--L.length;returnOK;}voidmain(){inti,a,b,c;SqListL;InitList_Sq(L);printf(请输入要插入的数字：);scanf(%d,&a);printf(请输入插入数的位置：);scanf(%d,&b);for(i=1;i=10;i++)ListInsert_Sq(L,i,i);ListInsert_Sq(L,b,a);printf(表的长度为：%d\n,L.length);for(i=1;i=L.length;i++)printf(%6d,L.elem[i-1]);printf(\n请输入要删除数的位置：);ElemTypee;scanf(%d,&i);ListDelete_Sq(L,i,e);printf(表的长度：%d\n,L.length);for(i=1;i=L.length;i++)printf(%6d,L.elem[i-1]);getchar();getchar();}二、单链表的操作（1）创建一个带头结点的单链表；（2）插入元素操作：将新元素x插入到单链表中第i个元素之后；（3）删除元素操作：删除单链表中值为x的元素；#includestdio.h#includestdlib.h#defineLIST_INIT_SIZE10#defineLISTINCREMENT10typedefintElemType;typedefintstatus;#defineOK1#defineOVERFLOW-1#defineERROR0typedefstructLNode{ElemTypedata;structLNode*next;intlength;}LNode,*LinkList;LinkListp,q;statusInitLinkedList(LinkList&L){L=(LNode*)malloc(sizeof(LNode));if(!L)exit(OVERFLOW);L-next=NULL;L-length=0;returnOK;}statusGetElem_L(LinkListL,inti,ElemType&e){p=L-next;intj=1;while(p!=NULL&&ji){p=p-next;++j;}if(!p||ji)returnERROR;e=p-data;returnOK;}statusListInsert_L(LinkList&L,inti,ElemTypee){p=L;intj=0;while(p&&ji-1){p=p-next;++j;}if(!p||ji-1)returnERROR;q=(LinkList)malloc(sizeof(LNode));q-data=e;q-next=p-next;p-next=q;++(L-length);returnOK;}statusListdelete_L(LinkList&L,inti,ElemType&e){p=L;intj=0;while(p-next&&ji-1){p=p-next;++j;}if(!(p-next)||ji-1)returnERROR;q=p-next;p-next=q-next;e=p-data;free(q);--(L-length);returnOK;}voidmain(){inti,n,a,b;LinkListL;InitLinkedList(L);printf(请输入要插入的数字：);scanf(%d,&a);printf(请输入要插入数的位置：);scanf(%d,&b);for(i=1;i=10;i++)ListInsert_L(L,i,i);ListInsert_L(L,b,a);printf(表的长度为：%d\n,L-length);p=L-next;while(p!=NULL){printf(%6d,p-data);p=p-next;}printf(\n请输入要删除数的位置：);ElemTypee;scanf(%d,&i);Listdelete_L(L,i,e);printf(表的长度：%d\n,L-length);p=L-next;while(p!=NULL){printf(%6d,p-data);p=p-next;}getchar();getchar();}三、在顺序栈上实现将非负十进制数转换成二进制数。#includestdio.h#includestdlib.h#defineMAX30typedefstruct{intsize;int*base,*top;}SqStack;intInitStack(SqStack&s){s.base=(int*)malloc(MAX*sizeof(int));if(!s.base)return0;s.top=s.base;s.size=MAX;return1;}intPush(SqStack&s,inte){if(s.top-s.bases.size){s.base=(int*)realloc(s.base,(s.size+10)*sizeof(int));if(!s.base)return0;s.top=s.base+s.size;s.size+=10;}*s.top++=e;return1;}intPop(SqStack&s,int&e){if(s.base==s.top)return0;e=*--s.top;return1;}voidmain(){intnum,k;SqStackl;InitStack(l);while(1){printf(请输入欲转换的十进制数！);scanf(%d,&num);while((num/2)!=0||(num)!=1){Push(l,num%2);num=num/2;}Push(l,num%2);printf(转化结果为：);while(Pop(l,k))printf(%d,k);printf(\n);}}四、在顺序表中采用顺序查找算法和折半查找算法寻找关键字X在顺序表中的位置。#includestdio.h#includestdlib.h#defineLIST_INIT_SIZE10#defineERROR0#defineOK1#defineOVERFLOW-1#defineTYPEinttypedefstruct{TYPE*elem;intlength;intlistsize;}SqList;intInitList(SqList*L){inti;L-elem=(TYPE*)malloc(LIST_INIT_SIZE*sizeof(TYPE));if(!L-elem)exit(OVERFLOW);L-length=10;L-listsize=LIST_INIT_SIZE;for(i=0;iL-length;i++){L-elem[i]=i*i;}returnOK;}intSequanceSearch(SqList&l,intn,TYPEc){inti=1;intposition;while(in){if(l.elem[i-1]==c){position=i;break;}elseposition=-1;i++;}if(position=n)returnposition;elsereturnERROR;}intBinSearch(SqList&l,TYPEc){intlow=0,mid,high=l.length;while(low=high){mid=(low+high)/2;if(c==l.elem[mid])returnmid;else{if(cl.elem[mid])high=mid-1;elselow=mid+1;}}returnERROR;}intdisplay(SqList*L){inti;for(i=0;iL-length;i++){printf(%d,L-elem[i]);printf();}returnOK;}intmain(){SqListL;TYPEe;inti;InitList(&L);printf(初始化顺序表为：);display(&L);while(1){printf(\n顺序查找查什么？\n);scanf(%d,&e);i=SequanceSearch(L,LIST_INIT_SIZE,e);if(i==ERROR)printf(顺序表没有该元素！！！\n);elseprintf(所查元素所在位置为：%d\n,i);printf(\n折半查找查什么？\n);scanf(%d,&e);i=BinSearch(L,e);if(i==ERROR)printf(顺序表没有该元素！！！\n);elseprintf(所查元素所在位置为：%d\n,i+1);}returnOK;}五、将无序数列使用直接插入排序算法和快速排序算法将其排成递增有序数列。#includeiostream.h#includestdlib.h#defineMAX100//将无序数列使用直接插入排序算法和快速排序算法将其排成递增有序数列typedefstruct{intdata[MAX];intlength;}sqlist;voidinit(sqlist&a)//线性表初始化{a.length=0;}voidinsert(sqlist&a,inti,intx)//插入元素,构造无序数列{intj;if(i0||ia.length+1||a.length==100);else{for(j=a.length+1;ji;j--)a.data[j]=a.data[j-1];a.dat