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

《《数据结构(c语言描述)》-马秋菊-源代码和习题参考答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、习题配套第一章2．C、A、B、B、A、A、D3．D={A,B,C,E,F,G,H,I,J};R={,,,,,,,,,}ABCEFGHI题1-3图J4．顺序、链式、索引、哈希。*5．解：100n2>2nn至少要多大6.Ｏ(n)、Ｏ(n)、Ｏ(n)、Ｏ()、(5)当n>m，Ｏ(n),当m>n，Ｏ(m)7．n!2100>lgn>n1/2>n3/2>(3/2)n>2n>nlgn>nn第二章1．×、√、×、√、√2．AAD4．顺序表voidDelete_SeqListx(SeqList

2、*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)链表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;

3、}else{p=q;q=q->next;}}}O(n)5．intDelete_SeqListx(SeqList*L,inti,intk)/*删除表中删除自第i个结点开始的k个结点*/{intj;if(i<1

4、

5、k<0

6、

7、i+k-1>L->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_SeqList

8、x(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)，然而要查找终端结点则需从头指针开始

9、遍历整个链表，其时间是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*

10、/{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;i

11、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(Li