搜索
《数据结构》――程序填空1《数据结构》――程序填空2019年10月1.一个带头结点的单链表如下：head为头指针，每个结点按data字段值递增顺序链接，r指向一个新结点，下面是将r所指的新结点插入链表中的算法，插入后结点仍按data字段值递增顺序链接。typedefstructnode{intdata;structnode*link;}node,*ptr;voidinsert(ptr&head,ptrr){pred=head;q=head-link;while((q)&&(q-data=r-data)){pred=q;q=q-link;}r-link=q;pre-link=r;}2.求单链表的长度typedefstructlnode{elemtpdata;structlnode*next;}lnode,*linkisttp;intlength(linkisttpL){p=L-next;len=0;while(p){len++;p=p-next;}returnlen;}3.假设head1指向带有头结点的单链表，现将该单链表复制一个。typedefstructlnode{elemtpdata;structlnode*next;}lnode,*linkisttp;voidcopy(pointerhead1,&head2){head2=(pointer)malloc(sizeof(pnode));//建立一个头结点q=head2;p=head1;while(p!=NULL)//复制一个新结点{s=(pointer)malloc(sizeof(pnode));s-data=p-data;^headdatalink《数据结构》――程序填空2q-next=s;p=p-next;q=q-next;}q-next=NULL;//置最后一个结点的next域}4.把两个递增的单链表LA，LB合并成一个递减的单链表LC。题中链表都不带表头结点。＃includestdio.hstructnodetype{intdata;structnodetype*link;}node;structnodetype*la,*lb,*lc;voidmerge(){structnodetype*p;lc=NULL;while(la!=NULL)&&(lb!=NULL){if(la-datalb-data){p=la;la=la-link;p-link=lc;lc=p;}else{p=lb;lb=lb-link;p-link=lc;lc=p;}}if(la==NULL)la=lb;while(la!=NULL){p=la;la=la-link;p-link=lc;lc=p;}}5.有两个向量A（有m个元素）和B（有n个元素），其元素均以从小到大的升序排列，编写一个过程将它们合并成一个向量C，使得C的元素也按升序排列。typedefvector=datatype[n0];voidlink(vectorA,B,&C;intm,n){i=1;j=1;k=1;while(i=m&&j=n)if(A[i]B[j]){C[k]=A[i];i++;k++;}else{C[k]=B[j];j=j+1;k=k+1;}if(j==n)for(;i=m;++i)《数据结构》――程序填空3{C[k]=A[i];k=k+1;}if(i==m)for(l=j;l=n;l++){C[k]=B[l];k++;}}6.本算法的功能是：向顺序存储的有序表L中插入一个新元素x，使表中数据仍按升序排列。typedefstructsqlisttp{Elemtpelem[maxlen]；intlast;}sqlisttp;voidsample(sqlisttp&L,Elemtpx){if(L.last==maxlen)exit(‘OVERFLOW’);i=0;while(L.elem[i]=x)&&(iL.last)i++;for(j=L.last-1;j=i;j--)L.elem[j+1]=L.elem[j];L.elem[i]=x;L.last++;}7.假设向量中的元素按值非递减有序排列，现删除向量中多余的值相同的元素。voiddel(inta[],intn){i=0;while(in–1)if(a[i]!=a[i+1])i++;else{for(j=(i+2);jn;j++)A[j-1]=A[j];n=n-1;}}8.本算法的功能是：在一个带表头结点的线性表中（结点的数据值无序排列），删除所有多余值相等的结点。typedefstructnodetp{intdata;structnodetp*next;}nodetp,*Link;voidexam(Link&h){q=h-next;while(q-next)《数据结构》――程序填空4{pre=q;p=q-next;do{while(p-data!=q-data){pre=p;p=p-next;}if(p){pre-next=p-next;free(p);p=pre-next;}}while(p);q=q-next;}9.已知线性表中的元素按值递增有序排列，并拥带头结点的单链表L表示，现删除其中重复的多余元素并释放所占空间typedefstructlnode{elemtpdata;structlnode*next;}lnode,*linklist;voiddessame(linklist&L){p=L-next;while(p){q=p-next;while(q&&p-data==q-data){p-next=q-next;free(q);q=p-next;}p=p-next;}}10.假设有两个已排序的单链表a，b，现将它们合并成一个链表c，且不改变其有序性。typedefstructpnode{datatypedata;structpnode*next;}pnode,*pointer;voidmerg(pointera,b,&c){h=(pointer)malloc(sizeof(pnode));h-next=NULL;r=h;p=a-next;q=b-next;while(p!=NULL)&&(q!=NULL)if(p-data=q-data){r-next=p;p=p-next;r=r-next;}else{r-next=q;《数据结构》――程序填空5r=r-next;q=q-next;};if(q!=NULL)(orP=NULL)r-next=q;if(p)r-next=p;c=h;}11.假设循环单链表如下图，下列程序将所有箭头方向取反（类型说明同上）heada1a2…antypedefstructpnode{datatypedata;structpnode*next;}pnode,*pointer;voidds53(pointerhead){p=head;q=p-next;while(p!=q){r=q;while(r-next!=p)r=r-next;p-next=r;p=p-next;}q-next=head或p-next=head;}12.本算法的功能是将带头结点的单链表L中的结点前后次序颠倒一下（不包括头结点）。#defineMAXSIZE10typedefstructLnode{floatdata;structLnode*link;}Lnode,*LinkList;voidconverse(LinkList&L){LinkListp,q,r,s;p=NULL;q=L-link;while(q){r=q-link;q-link=p;p=q;q=r;}L-link=p;}13.把一个头指针为heada的单链表插入到头指针为headb的单链表的第i个元素之前。typedefstructpnode{datatypedata;《数据结构》――程序填空6structpnode*next;}pnode,*pointer;voidinsert(pointerheada,pointerheadb,inti){pb=headb-next;j=1;while(pb&&ji-1){pb=pb-next;j++;}if(!pb)returnERROR;pa=heada-next;while(pa-next)pa=pa-next;pa-next=pb-next;pb-next=heada-next;free(heada);}14.删除带头结点的双向循环链表L的第i个元素（1≤i≤表长）voidListDelete(DuLinkList&L,inti,ElemType&e){if(!(p=GetElemP(L,i)))return0;//确定L中第i个元素的指针pe=p-data;p-prior-next=p-next;p-next-prior=p-prior;free(p)return;}15.给定栈的顺序存储表示：#definemaxsize100typedefstruct{intdata[maxsize];inttop;}stack;intInit(stack&s)//顺序栈初始化（构造空栈）{s.top=0;return1;}intpush(stack&s,intx)//数据元素进栈{if(s.top==maxsize){printf(‘OVERFLOW’);return0;}s.top=s.top+1;s.data[s.top-1]=x;return1;}16.对于循环队列，函数init为队列初始化，函数en为进队操作#defineMAXSIZE10typedefstruct{int*a;intf,r;《数据结构》――程序填空7}Queue;statusinit(Queue&p){if((q=(int*)malloc(MAXSIZE*sizeof(int)))p.a=q;p.f=p.r=0;return(OK);}statusen(Queue&p,intd){if((p.r+1)%MAXSIZE==p.f){printf(“QueueFULL!\n”);return(ERROR);}p.a[p.r]=d;p.r=(p.r+1)%MAXSIZE;returnOK;}17.假设以一个一维向量data[0..maxsize-1]存放一个循环队列中的元素，同时设变量rear和len分别指示循环队列中队尾元素的位置和内含元素的个数。试设计出相应的入队和出队的算法。typedefstructSeque{QelemTypedata[maxsize];intrear,len;}Seque;voidenqueue(Seque*sq,QelemTypex)//入队算法{if(sq-len==maxsize)printf(“OVERFLOW\n”);else{sq-rear=(sq-rear+1)%maxsize;sq-data[sq-rear]=x;sq-len=sq-len+1;}}QelemTypedequeue(Seque*sq)//出队算法{if(sq-len==0)printf(“underflow\n”);else{front=sq-rear+1–sq-len;if(front0)front=front+maxsize;sq-len--;}return(sq-data[front]);}18.返回二叉树t的后序序列的第一个结点的指针typedefstructbnode{Elemtypedata;structbnode*lchild,rchild;}bnode,*btree;voidpost(btreet,btree&p){p=t;if(t!=NULL)while((p-lchild!=NULL)||(p-rchild!=NULL))