《数据结构（c语言描述）马秋菊源代码和习题参考答案》由会员分享，可在线阅读，更多相关《数据结构（c语言描述）马秋菊源代码和习题参考答案（27页珍藏版）》请在金锄头文库上搜索。
1、习题配套第一章2C、A、B、B、A、A、D3D=A,B,C,E,F,G,H,I,J;R=,ABCEFGHI题1-3图 J4顺序、链式、索引、哈希。*5解：100n22nn至少要多大6.(n)、(n)、(n)、()、(5)当nm，(n),当mn，(m)7n!2100lgnn1/2n3/2(3/2)n2nnlgnnn第二章1、2AAD4顺序表void Delete_SeqListx(SeqList *L,ElemType x)/*删除表中值为x元素*/inti,j;for(i=1;ilength;i+)if(L-elemi=x)for(j=i;jlength-1;j+)L-elemj=L-elem
2、j+1;L-length-;/*向上移动*/O(n2)链表void del_link(LinkList H，int x)/*删除数据域为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;elsep=q;q=q-next;O(n)5int Delete_SeqListx(SeqList *L,int i,int k)/*删除表中删除自第i个结点开始的k个结点*/intj;if(i1|kL-length)/*检查空表及删除位置的合法性*/printf(不存在第i个元素);r
3、eturn ERROR;for(j=i;jlength-k;j+)L-elemj=L-elemj+k; /*向上移动*/L-length-=k;Return OK;/*删除成功*/O(n)6void Delete_SeqListx(SeqList *L,ElemType x)/*将表中值为x元素换成y*/inti,j;for(i=1;ilength;i+)if(L-elem=x)L-elemi=y;/* */O(n)7写一算法在循环单链表上实现线性表的CList_length(L)运算。int link_length(LinkList H)LNode *p;int i=0;p=H;while(
4、p-next!=H)i+;p=p-next;return i;O(n)8在用头指针表示的单循环链表中，查找开始结点a1的时间是O(1)，然而要查找终端结点则需从头指针开始遍历整个链表，其时间是O(n)。但在很多实际问题中，表的操作常常是在表的首、尾位置上进行，如果改用尾指针rear来表示单循环链表，则查找开始结点a1和终端结点an都很方便，它们的存储位置分别是rear-next-next和rear，显然，查找时间都是O(1)。9.int Insert_LinkListab(LinkList H, ElemType a,ElemType b)/*在单链表中值为a的结点前插入一个值为b的结点*/L
5、Node*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；return OK;/*Insert_LinkListab*/10顺序表void Reverse_Sq(SqList *L)/*顺序表的就地逆置*/for(i=1，j=L.len;inext;q=p-next;s=q-n
6、ext;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为新表表头。11void merge1(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)
7、t=q-next;q-next=s;/*如A非空,将A的元素插入*/p=s;q=t;/*while*/*merge1*/12Status Delete_Pre(CiLNode s)/*删除单循环链表中结点p的直接前驱*/q=p;while(q-next-next!=p)q=q-next;/*找到p的前驱的前驱*/s=q-next;q-next=p;free(s);return OK;/*Delete_Pre*/13Status Insert_SqList(SeqList &L，int x)if(L-length+1m-1)return ERROR;L-length+;i=L-length;wh
8、ile(L-elemix&i0;)L-elemi+1=L-elemi;i-;L-elemi+1=x;return OK;/*Insert_SqList14intInsert_Linkx(LinkList H,ElemType x)/*在值递增单链表中插入一个值为x的结点，仍递增*/LNode*q=H,*s;*p=H-next;while(p!=NULL&p-datanext&q-next-datanext;/*查找a结点*/s=(LinkList)malloc(sizeof(LNode);/*申请、填装结点*/s-data=x;s-next=q-next;/*新结点插入*/q-next=s；r
9、eturn OK;/*Insert_Linkx*/15源程序代码：（在TubroC2.0测试通过）#include#includestructnodeintnumber;/*人的序号*/intcipher;/*密码*/structnode*next;/*指向下一个节点的指针*/;structnode*CreatList(intnum)/*建立循环链表*/inti;structnode*ptr1,*head;if(ptr1=(structnode*)malloc(sizeof(structnode)=NULL)perror(malloc);returnptr1;head=ptr1;ptr1-ne
10、xt=head;for(i=1;inext=(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;inumber=i;head-cipher=rand();head=head-next;m=rand();/*m取随机数*/i=
11、0;/*因为我没办法删除head指向的节点，只会删除head的下一节点，所以只能从0数起。*/while(head-next!=head)/*当剩下最后一个人时，退出循环*/if(i=m)ptr=head-next;/*ptr记录数到m的那个人的位置*/printf(number:%dn,ptr-number);printf(cipher:%dn,ptr-cipher);m=ptr-cipher;/*让m等于数到m的人的密码*/head-next=ptr-next;/*让ptr从链表中脱节，将前后两个节点连接起来*/head=hea/d-next;/*head移向后一个节点*/free(ptr
12、);/*释放ptr指向的内存*/i=0;/*将i重新置为0，从0再开始数*/elsehead=head-next;i+;printf(number:%dn,head-number);printf(cipher:%dn,head-cipher);free(head);/*让最后一个人也出列*/16void SqList_Intersect(SqList A,SqList B,SqList &C)/*求元素递增排列的线性表A和B的元素的交集并存入C中*/i=1;j=1;k=0;while(A.elemi&B.elemj)if(A.elemiB.elemj)j+;if(A.elemi=B.elemj)C.elem+k=A.elemi;/当发现了一个在A,B中都存在的元素,/就添加到C中i+;j+;/*while*/*SqList_Intersect*/17Status DuLNode_Pre(DuLinkList*H)/*完成双向循环链表结点的pre域*/p=H;while(q-next!=H)p-next-pre=p;p=p-next;return OK;
