《数据结构(C语言描述)》-马秋菊-源代码和习题参考答案

习题配套第一章2．C、A、B、B、A、A、D3．D={A,B,C,E,F,G,H,I,J};R={A,B,A,C,A,E,B,F,B,G,E,H,E,I,E,J,H,I,I,J}4．顺序、链式、索引、哈希。*5．解：100n22nn至少要多大6.Ｏ(n)、Ｏ(n)、Ｏ(n)、Ｏ(n)、(5)当nm，Ｏ(n),当mn，Ｏ(m)7．n!2100lgnn1/2n3/2(3/2)n2nnlgnnn第二章1．×、√、×、√、√2．AAD4．顺序表voidDelete_SeqListx(SeqList*L,ElemTypex)/*删除表中值为x元素*/{inti,j;for(i=1;i=L-length;i++){if(L-elem[i]==x){for(j=i;j=L-length-1;j++)L-elem[j]=L-elem[j+1];L-length--;}/*向上移动*/}O(n2)ABCEFGHI题1-3图J链表voiddel_link(LinkListH，intx)/*删除数据域为x的结点*/{LNode*p，*q;p=H;q=H-next;while(q!=NULL){if(q-data==x){p-next=q-next;free(q);q=p-next;}else{p=q;q=q-next;}}}O(n)5．intDelete_SeqListx(SeqList*L,inti,intk)/*删除表中删除自第i个结点开始的k个结点*/{intj;if(i1||k0||i+k-1L-length)/*检查空表及删除位置的合法性*/{printf(＂不存在第i个元素＂);returnERROR;}for(j=i;j=L-length-k;j++)L-elem[j]=L-elem[j+k];/*向上移动*/L-length-=k;ReturnOK;/*删除成功*/}O(n)6．voidDelete_SeqListx(SeqList*L,ElemTypex)/*将表中值为x元素换成y*/{inti,j;for(i=1;i=L-length;i++){if(L-elem[]==x){L-elem[i]=y;}/**/}O(n)7．写一算法在循环单链表上实现线性表的CList_length(L)运算。intlink_length(LinkListH){LNode*p;inti=0;p=H;while(p-next!=H){i++;p=p-next;}returni;}O(n)8．在用头指针表示的单循环链表中，查找开始结点a1的时间是O(1)，然而要查找终端结点则需从头指针开始遍历整个链表，其时间是O(n)。但在很多实际问题中，表的操作常常是在表的首、尾位置上进行，如果改用尾指针rear来表示单循环链表，则查找开始结点a1和终端结点an都很方便，它们的存储位置分别是rear-next-next和rear，显然，查找时间都是O(1)。9.intInsert_LinkListab(LinkListH,ElemTypea,ElemTypeb)/*在单链表中值为a的结点前插入一个值为b的结点*/{LNode*q=H,*s;*p=H-next;while(p!=NULL&&p-data!=a)/*q-next&&q-next-data!=a*/{q=p;p=p-next;}/*查找a结点*/s=(LinkList)malloc(sizeof(LNode));/*申请、填装结点*/s-data=b;s-next=q-next;/*新结点插入在第i-1个结点的后面*/q-next=s；returnOK;}/*Insert_LinkListab*/10．顺序表voidReverse_Sq(SqList*L)/*顺序表的就地逆置*/{for(i=1，j=L.len;ij;i++){t=L.elem[i];L.elem[i]=L.elem[L.len-i+1];L.elem[L.len-i+1]=t;}}/*Reverse_Sq*/单链表voidReverse_L(LinkList*H)/*为简化算法，假设表长大于2*/{p=H-next;q=p-next;s=q-next;p-next=NULL;while(s-next){q-next=p;p=q;q=s;s=s-next;/*把H的元素逐个插入新表表头*/}q-next=p;s-next=q;H-next=s;}/*Reverse_L*/分析：本算法的思想是，逐个地把L的当前元素q插入新的链表头部，p为新表表头。11．voidmerge1(LinkList&A,LinkList&B,LinkList&C)/*把链表A和B合并为C,A和B的元素间隔排列,且使用原存储空间*/{p=A-next;q=B-next;C=A;while(p&&q){s=p-next;p-next=q;/*将B的元素插入*/if(s){t=q-next;q-next=s;/*如A非空,将A的元素插入*/}p=s;q=t;}/*while*/}/*merge1*/12．StatusDelete_Pre(CiLNodes)/*删除单循环链表中结点p的直接前驱*/{q=p;while(q-next-next!=p)q=q-next;/*找到p的前驱的前驱*/s=q-next;q-next=p;free(s);returnOK;}/*Delete_Pre*/13．StatusInsert_SqList(SeqList&L，intx){if(L-length+1m-1)returnERROR;L-length++;i=L-length;while(L-elem[i]x&&i0;){L-elem[i+1]=L-elem[i];i--;}L-elem[i+1]=x;returnOK;}/*Insert_SqList14．intInsert_Linkx(LinkListH,ElemTypex)/*在值递增单链表中插入一个值为x的结点，仍递增*/{LNode*q=H,*s;*p=H-next;while(p!=NULL&&p-datax)/*q-next&&q-next-datax*/{q=p;p=p-next;}/*查找a结点*/s=(LinkList)malloc(sizeof(LNode));/*申请、填装结点*/s-data=x;s-next=q-next;/*新结点插入*/q-next=s；returnOK;}/*Insert_Linkx*/15．源程序代码：（在TubroC2.0测试通过）#includestdlib.h#includealloc.hstructnode{intnumber;/*人的序号*/intcipher;/*密码*/structnode*next;/*指向下一个节点的指针*/};structnode*CreatList(intnum)/*建立循环链表*/{inti;structnode*ptr1,*head;if((ptr1=(structnode*)malloc(sizeof(structnode)))==NULL){perror(malloc);returnptr1;}head=ptr1;ptr1-next=head;for(i=1;inum;i++){if((ptr1-next=(structnode*)malloc(sizeof(structnode)))==NULL){perror(malloc);ptr1-next=head;returnhead;}ptr1=ptr1-next;ptr1-next=head;}returnhead;}main(){inti,n=30,m;/*人数n为30个*/structnode*head,*ptr;randomize();head=CreatList(n);for(i=1;i=30;i++){head-number=i;head-cipher=rand();head=head-next;}m=rand();/*m取随机数*/i=0;/*因为我没办法删除head指向的节点，只会删除head的下一节点，所以只能从0数起。*/while(head-next!=head)/*当剩下最后一个人时，退出循环*/{if(i==m){ptr=head-next;/*ptr记录数到m的那个人的位置*/printf(number:%d\n,ptr-number);printf(cipher:%d\n,ptr-cipher);m=ptr-cipher;/*让m等于数到m的人的密码*/head-next=ptr-next;/*让ptr从链表中脱节，将前后两个节点连接起来*/head=hea/d-next;/*head移向后一个节点*/free(ptr);/*释放ptr指向的内存*/i=0;/*将i重新置为0，从0再开始数*/}else{head=head-next;i++;}}printf(number:%d\n,head-number);printf(cipher:%d\n,head-cipher);free(head);/*让最后一个人也出列*/}16．voidSqList_Intersect(SqListA,SqListB,SqList&C)/*求元素递增排列的线性表A和B的元素的交集并存入C中*/{i=1;j=1;k=0;while(A.elem[i]&&B.elem[j]){if(A.elem[i]B.elem[j])i++;if(A.elem[i]B.elem[j])j++;if(A.elem[i]==B.elem[j]){C.elem[++k]=A.elem[i];//当发现了一个在A,B中都存在的元素,//就添加到C中i++;j++;}}/*while*/}/*SqList_Intersect*/17．StatusDuLNode_Pre(DuLinkList*H)/*完成双向循环链表结点的pre域*/{p=H;while(q-next!=H){p-next-pre=p;p=p-next;}returnOK;}/*DuLNode_Pre*/第三章栈与队列1．假定有编号A、B、C的3辆列车顺序开进一个栈式结构的站台，请写出每一种开出站台的列车编号顺序(注：每一列车开出栈开出站台后，不允许再进栈)。2．指出下述程序段的功能是什么？voidDemo1(SeqStack*S){inti;arra[16];n=16；initStack(&S);for(i=0,in;i++)push(S,arra[i]);while(!StackEmpty(S))arra[i]=pop(S);}3．写出带表头链栈取栈顶元素和置栈空的算法。4．假设一个算术表达式中包含圆括号、方括号和花括号，编写一个判别表达式中括号是否配对的算法。5．写出计算表达式5+3*（4/6-7）时操作数和算符栈的变化情况。6．对于给定的十进制正整数，输出对应的八进制正整数。(1)写出递归算法。(2)写出非递归算法。7．已知n为大于等于零的整数，试写出计算下列递归函数f(n)的递归和非递归算法。8．回文是指正读和反读均相同的字符序列，如”abba”和”abdba”均是回文，而”ashgash”不是回文。试写一个算法判断读入的一个以‘@’为结束符的字符序列是否为回文。(提示：将一半字符入栈)。9．一个双向栈S是在同一向量空间内实现的两个栈，它们的栈底分别设在向量空间的两端。设计初始化InitStack(S,i)、入栈push(S,i,x)和出栈pop(S,i)等算法，其中i为0或1，用以指示栈号。10．对于一个具有m个单元的循环队