双向链表的排序实验报告

《双向链表的排序实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、陈祎智11004530实验报告<2>1.问题描述:双向链表的排序。要求：输入一个双向链表，显示些双向链表并对此双向链表排序2.课题分析(结构图):双向链表的排序双向链表存储结构快速排序定义输入数据结点3.数据结构的设计:typedefstructnode{intinfo;structnode*llink,*rlink;}NODE;4.流程图开始创建链表初始化链表从中间分成两部排序链表插入10个值输出排序链表终止5．源程序：#include#include#includetypedefstructLink/*双向链表结构体*/{i

2、ntdata;structLink*lift;structLink*right;}linkx,*linky;linkyInit();/*建立双向链表*/voidPrLink(linkyp);/*输出双向链表*/linkySort(linkyhead);/*对双向链表排序*/linkySwap(linkyhead,linkyone,linkytwo);/*任意交换双向链表两个结点的地址*/voidmain(void){linkyhead;head=Init();head=Sort(head);PrLink(head);}linky(Init())/*建立链表*/{linkyp,q,head;

3、intn=0;head=p=q=(linky)malloc(sizeof(linkx));printf("排序前的链表:");scanf("%d",&p->data);/*输入数据*/head->lift=NULL;n++;while(n!=10)/*一直输入到规定的数字个数停止*/{q=p;p=(linky)malloc(sizeof(linkx));scanf("%d",&p->data);/*输入数据*/q->right=p;p->lift=q;n++;}p->right=NULL;return(head);}linkySwap(linkyhead,linkyone,linkytwo

4、)/*任意交换两个结点*/{linkytemp;if(one->lift==NULL&&two->right==NULL)/*首和尾巴的交换*/{if(one->right==two)/*只有两个结点的情况下*/{two->right=one;two->lift=NULL;one->lift=two;one->right=NULL;head=two;}else/*有间隔的首尾交换*/{one->right->lift=two;two->lift->right=one;two->right=one->right;one->lift=two->lift;two->lift=one->right

5、=NULL;head=two;/*尾结点成为头结点*/}}elseif(two->right==NULL)/*尾和任意一个交换*/{if(one->right==two)/*交换最后两个结点*/{one->lift->right=two;two->lift=one->lift;two->right=one;one->lift=two;one->right=NULL;}else/*和前面其他结点交换*/{temp=two->lift;temp->right=one;one->lift->right=two;one->right->lift=two;two->lift=one->lift;tw

6、o->right=one->right;one->lift=temp;one->right=NULL;}}elseif(one->lift==NULL)/*头和任意一个交换*/{if(one->right==two)/*交换头两个结点*/{two->right->lift=one;one->right=two->right;one->lift=two;two->right=one;two->lift=NULL;head=two;}else/*头结点和后面其他结点交换*/{temp=one->right;temp->lift=two;one->lift=two->lift;one->righ

7、t=two->right;two->lift->right=one;two->right->lift=one;two->right=temp;two->lift=NULL;head=two;/*交换的结点成为头结点*/}}else/*当中的任意两个交换*/{if(one->right==two)/*交换连在一起的两个结点*/{temp=one->lift;one->lift->right=two;one->right->