数据结构经典例题

《数据结构经典例题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构经典例题1.设计一个算法将L拆分成两个带头节点的单链表L1和L2。voidsplit(LinkList*&L,LinkList*&L1,LinkList*&L2){LinkList*p=L->next,*q,*r1;//p指向第1个数据节点L1=L;//L1利用原来L的头节点r1=L1;//r1始终指向L1的尾节点L2=(LinkList*)malloc(sizeof(LinkList));//创建L2的头节点L2->next=NULL;//置L2的指针域为NULLwhile(p!=NULL){r1->next=p;//采用尾插法将*p(data值为ai)插入L1中r1=p;p=p-

2、>next;//p移向下一个节点(data值为bi)q=p->next;//由于头插法修改p的next域,故用q保存*p的后继节点p->next=L2->next;//采用头插法将*p插入L2中L2->next=p;p=q;//p重新指向ai+1的节点}r1->next=NULL;//尾节点next置空}2.查找链表中倒数第k个位置上的节点（k为正整数）。若查找成功，算法输出该节点的data域的值，并返回1；否则，只返回0。typedefstructLNode{　intdata;　structLNode*link;}*LinkList;intSearchk(LinkListlist,intk

3、){LinkListp,q;intcount=0;p=q=list->link;while(p!=NULL){if(countlink;p=p->link;}if(countdata);return(1);}}1.假定采用带头节点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。设str1和str2分别指向两个单词所在单链表的头节点请设计一个时间上尽可能高效的算法，找出由str1和str2所指向两个链表共同后缀的起始位置。typedefstructNode{　cha

4、rdata;　structNode*next;}SNODE;SNODE*Findlist(SNODE*str1,SNODE*str2){intm,n;SNODE*p,*q;m=Listlen(str1);//求单链表str1的长度mn=Listlen(str2);//求单链表str2的长度nfor(p=str1;m>n;m--)//若m大，则str1后移m-n+1个节点p=p->next;for(q=str2;mnext;while(p->next!=NULL&&p->next!=q->next){p=p->next;//p、

5、q两步后移找第一个指针值相等的节点q=q->next;}returnp->next;}intListlen(SNODE*head)//求单链表的长度{intlen=0;while(head->next!=NUL){len++;head=head->next;}returnlen;}4.设计一个算法，删除一个单链表L中元素值最大的节点。voiddelmaxnode(LinkList*&L){LinkList*p=L->next,*pre=L,*maxp=p,*maxpre=pre;while(p!=NULL)//用p扫描整个单链表,pre始终指向其前驱节点{if(maxp->datad

6、ata)//若找到一个更大的节点{maxp=p;//更改maxpmaxpre=pre;//更改maxpre}pre=p;//p、pre同步后移一个节点p=p->next;}maxpre->next=maxp->next;//删除*maxp节点free(maxp);//释放*maxp节点}5.有一个带头节点的单链表L（至少有一个数据节点），设计一个算法使其元素递增有序排列。voidsort(LinkList*&L){LinkList*p,*pre,*q;p=L->next->next;//p指向L的第2个数据节点L->next->next=NULL;//构造只含一个数据节点的有序表while(

7、p!=NULL){q=p->next;//q保存*p节点后继节点的指针pre=L;//从有序表开头进行比较,pre指向插入*p的前驱节点while(pre->next!=NULL&&pre->next->datadata)pre=pre->next;//在有序表中找插入*p的前驱节点*prep->next=pre->next;//将*pre之后插入*ppre->next=p;p=q;//扫描原单链表余