资源预览内容
第1页 / 共27页
第2页 / 共27页
第3页 / 共27页
第4页 / 共27页
第5页 / 共27页
第6页 / 共27页
第7页 / 共27页
第8页 / 共27页
第9页 / 共27页
第10页 / 共27页
亲,该文档总共27页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
习题配套第一章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-elemj+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个元素);return 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(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的结点*/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;return OK;/*Insert_LinkListab*/10顺序表void Reverse_Sq(SqList *L)/*顺序表的就地逆置*/for(i=1,j=L.len;inext;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为新表表头。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)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;while(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;return 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-next=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=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);/*释放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;
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号