《数据结构—用C语言描述》习题答案

习题解答(唐策善版)(其他版本在上面)第一章绪论（参考答案）1.3(1)O(n)(2)(2)O(n)(3)(3)O(n)(4)(4)O(n1/2)(5)(5)执行程序段的过程中，x,y值变化如下：循环次数xy0（初始）91100192100293100………………9100100101011001191991292100………………2010199219198………………3010198319197到y=0时，要执行10*100次，可记为O（10*y）=O（n）1.52100,(2/3)n,log2n,n1/2,n3/2,(3/2)n,nlog2n,2n,n!,nn第二章线性表(参考答案)在以下习题解答中，假定使用如下类型定义：（1）顺序存储结构：#defineMAXSIZE1024typedefintdataType;//实际上，ElemType可以是任意类型typedefstruct{datatypedata[MAXSIZE];intlast;//last表示终端结点在向量中的位置}sequenlist;（2）链式存储结构（单链表）typedefstructnode{dataTypedata;structnode*next；}linklist;（3）链式存储结构（双链表）typedefstructnode{datatypedata;structnode*prior,*next；}dlinklist;（4）静态链表typedefstruct{ElemTypedata;intnext;}node;nodesa[MAXSIZE];2.1头指针：指向链表的指针。因为对链表的所有操均需从头指针开始，即头指针具有标识链表的作用，所以链表的名字往往用头指针来标识。如：链表的头指针是la，往往简称为“链表la”。头结点：为了链表操作统一，在链表第一元素结点（称为首元结点，或首结点）之前增加的一个结点，该结点称为头结点，其数据域不无实际意义（当然，也可以存储链表长度，这只是副产品），其指针域指向头结点。这样在插入和删除中头结点不变。开始结点：即上面所讲第一个元素的结点。2.2只设尾指针的单循环链表，从尾指针出发能访问链表上的任何结点。2·3voidinsert(ElemTypeA[],intelenum,ElemTypex)//向量A目前有elenum个元素，且递增有序，本算法将x插入到向量A中，并保持向量的递增有序。{inti=0,j;while(ielenum&&A[i]=x)i++;//查找插入位置for(j=elenum-1;j=i;j--)A[j+1]=A[j];//向后移动元素A[i]=x;//插入元素}//算法结束2·4voidrightrotate(ElemTypeA[],intn,k)//以向量作存储结构，本算法将向量中的n个元素循环右移k位，且只用一个辅助空间。{intnum=0;//计数，最终应等于nintstart=0;//记录开始位置（下标）while(numn){temp=A[start];//暂存起点元素值，temp与向量中元素类型相同empty=start;//保存空位置下标next=(start-K+n)%n;//计算下一右移元素的下标while(next!=start){A[empty]=A[next];//右移num++;//右移元素数加1empty=next;next=(next-K+n)%n;//计算新右移元素的下标}A[empty]=temp;//把一轮右移中最后一个元素放到合适位置num++;start++;//起点增1，若numn则开始下一轮右移。}}//算法结束算法二算法思想：先将左面n-k个元素逆置，接着将右面k个元素逆置，最后再将这n个元素逆置。voidrightrotate(ElemTypeA[],intn,k)//以向量作存储结构，本算法将向量中的n个元素循环右移k位，且只用一个辅助空间。{ElemTypetemp;for(i=0;i(n-k)/2;i++)//左面n-k个元素逆置{temp=A[i];A[i]=A[n-k-1-i];A[n-k-1-i]=temp;}for(i=1;i=k;i++)//右面k个元素逆置{temp=A[n-k-i];A[n-k-i]=A[n-i];A[n-i]=temp;}for(i=0;in/2;i++)//全部n个元素逆置{temp=A[i];A[i]=A[n-1-i];A[n-1-i]=temp;}}//算法结束2·5voidinsert(linklist*L,ElemTypex)//带头结点的单链表L递增有序，本算法将x插入到链表中，并保持链表的递增有序。{linklist*p=L-next,*pre=L，*s;//p为工作指针，指向当前元素，pre为前驱指针，指向当前元素的前驱s=(linklist*)malloc(sizeof(linklist));//申请空间，不判断溢出s-data=x;while(p&&p-data=x){pre=p;p=p-next;}//查找插入位置pre-next=s;s-next=p;//插入元素}//算法结束2·6voidinvert(linklist*L)//本算法将带头结点的单链表L逆置。//算法思想是先将头结点从表上摘下，然后从第一个元素结点开始，依次前插入以L为头结点的链表中。{linklist*p=L-next,*s;//p为工作指针，指向当前元素，s为p的后继指针L-next=null;//头结点摘下，指针域置空。算法中头指针L始终不变while(p){s=p-next;//保留后继结点的指针p-next=L-next;//逆置L-next=p;p=s;//将p指向下个待逆置结点}}//算法结束2·7(1)intlength1(linklist*L)//本算法计算带头结点的单链表L的长度{linklist*p=L-next;inti=0;//p为工作指针，指向当前元素，i表示链表的长度while(p){i++;p=p-next;}return(i);}//算法结束(2)intlength1(nodesa[MAXSIZE])//本算法计算静态链表s中元素的个数。{intp=sa[0].next,i=0;//p为工作指针，指向当前元素，i表示元素的个数，静态链指针等于-1时链表结束while(p！=-1){i++;p=sa[p].next;}return(i);}//算法结束2·8voidunion_invert(linklist*A,*B,*C)//A和B是两个带头结点的递增有序的单链表，本算法将两表合并成//一个带头结点的递减有序单链表C，利用原表空间。{linklist*pa=A-next,*pb=B-next,*C=A,*r;//pa,pb为工作指针，分别指向A表和B表的当前元素，r为当前逆置//元素的后继指针,使逆置元素的表避免断开。//算法思想是边合并边逆置，使递增有序的单链表合并为递减有序的单链表。C-next=null;//头结点摘下，指针域置空。算法中头指针C始终不变while(pa&&pb)//两表均不空时作if(pa-data=pb-data)//将A表中元素合并且逆置{r=pa-next;//保留后继结点的指针pa-next=C-next;//逆置C-next=pa;pa=r;//恢复待逆置结点的指针}else//将B表中元素合并且逆置{r=pb-next;//保留后继结点的指针pb-next=C-next;//逆置C-next=pb;pb=r;//恢复待逆置结点的指针}//以下while(pa)和while(pb)语句，只执行一个while(pa)//将A表中剩余元素逆置{r=pa-next;//保留后继结点的指针pa-next=C-next;//逆置C-next=pa;pa=r;//恢复待逆置结点的指针}while(pb)//将B表中剩余元素逆置{r=pb-next;//保留后继结点的指针pb-next=C-next;//逆置C-next=pb;pb=r;//恢复待逆置结点的指针}free(B);//释放B表头结点}//算法结束2·9voiddeleteprior(linklist*L)//长度大于1的单循环链表，既无头结点，也无头指针，本算法删除*s的前驱结点{linklist*p=s-next,*pre=s;//p为工作指针，指向当前元素，//pre为前驱指针，指向当前元素*p的前驱while(p-next!=s){pre=p;p=p-next;}//查找*s的前驱pre-next=s;free(p);//删除元素}//算法结束2·10voidone_to_three(linklist*A,*B,*C)//A是带头结点的的单链表，其数据元素是字符字母、字符、数字字符、其他字符。本算法//将A表分成//三个带头结点的循环单链表A、B和C，分别含有字母、数字和其它符号的同一类字符，利用原表空间。{linklist*p=A-next,r;//p为工作指针，指向A表的当前元素，r为当前元素的后继指针,使表避免断开。//算法思想是取出当前元素，根据是字母、数字或其它符号，分别插入相应表中。B=(linklist*)malloc(sizeof(linklist));//申请空间，不判断溢出B-next=null;//准备循环链表的头结点C=(linklist*)malloc(sizeof(linklist));//申请空间，不判断溢出C-next=null;//准备循环链表的头结点while(p){r=p-next;//用以记住后继结点if(p-data=’a’&&p-data=’z’||p-data=’A’&&p-data=’Z’){p-next=A-next;A-next=p;}//将字母字符插入A表elseif(p-data=’0’&&p-data=’9’){p-next=B-next;B-next=p;}//将数字字符插入B表else{p-next=C-next;C-next=p;}//将其它符号插入C表p=r;//恢复后继结点的指针}//while}//算法结束2·11voidlocate(dlinklist*L)//L是带头结点的按访问频度递减的双向链表，本算法先查找数据x,//查找成功时结点的访问频度域增1，最后将该结点按频度递减插入链表中适当位置。{linklist*p=L-next,*q;//p为工作指针，指向L表的当前元素，q为p的前驱，用于查找插入位置。while(p&&p-data!=x)p=p-next;//查找值为x的结点。if(!p)return(“不存在值为x的结点”);else{p-freq++;//令元素值为x的结点的freq域加1。p-next-prir=p-prior;//将p结点从链表上摘下。p-prior-next=p-next;q=p-prior;//以下查找p结点的插入位置while(q!=L&&q-freqp-freq)q=q-prior;p-next=q-next;q-next-prior=p;//将p结点插入p-prior=q;q-next=p；}}//算法结束第三章栈和队列(参考答案)//从数据结构角度看，栈和队列是操作受限的线性结构，其顺序存储结构//和链式存储结构的定义与线性表相同，请参考教材，这里不再重复。3.112342134321412432143324113242314342113422341432114322431设入栈序列元素数为n，则可能的出栈序列数为C2nn=(1/n+1)*