双向链表排序实验报告

　陈祎智

　 实验报告<2> 1. 问题描述: 双向链表的排序。

　要求：

　输入一个双向链表，显示些双向链表并对此双向链表排序

　2.课题分析(结构图):

　 3.数据结构的设计: typedef struct node { int info;

　 struct node *llink,*rlink;

　}NODE; 双向链表的排序 双向链表存储结构 快速排序定义 输入数据结点

　4.流程图

　5．源程序：

　#include<iostream.h> #include<stdlib.h> #include <stdio.h> 开始 创建链表 初始化链表 从中间分成两部 排序链表 插入 10 个值 输出排序链表 终止

　typedef struct Link/*双向链表结构体*/ {

　int data;

　struct Link *lift;

　struct Link *right; }linkx,*linky; linky Init();/*建立双向链表*/ void PrLink(linky p);/*输出双向链表*/ linky Sort(linky head);/*对双向链表排序*/ linky S head,linky one,linky two);/*任意交换双向链表两个结点的地址*/ void main(void) {

　linky head;

　head=Init();

　head=Sort(head);

　PrLink(head); } linky (Init())/*建立链表*/ {

　linky p,q,head;

　int n=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); } linky S head,linky one,linky two)/*任意交换两个结点*/ {linky temp;

　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=NULL;

　 head=two;/*尾结点成为头结点*/

　 }

　}

　else if(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;

　two->right=one->right;

　one->lift=temp;

　one->right=NULL;

　}

　 }

　else if(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->right=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->lift=two;

　 one->lift=two;

　 one->right=two->right;

　 two->right->lift=one;

　 two->right=one;

　 two->lift=temp;

　 }

　 else/*交换隔开的两个结点*/

　 {

　 one->lift->right=two;

　 one->right->lift=two;

　 one->lift=two->lift;

　 temp=one->right;

　 one->right=two->right;

　 two->lift->right=one;

　 two->right->lift=one;

　 two->right=temp;

　 two->lift=one->lift;

　 }

　 }

　return(head); } linky Sort(linky head)/*对链表排序*/ {

　linky i,j,t,p;

　int max;

　p=head;

　for(i=p;i->right!=NULL;i=i->right)/*用选择法的思想对这些结点排序*/

　 {

　max=i->data;

　for(j=i->right;j!=NULL;j=j->right)

　 if(j->data<max)

　 {

　 max=j->data;

　 t=j;

　 }

　if(max!=i->data)/*假如没有找到比 i 小的结点*/

　{

　head=S);/*因为最终返回的是头结点,而头结点又有可能变化,所以每次头结点返回*/

　i=t;

　 }

　 }

　return(head); } void PrLink(linky p)/*输出链表*/ {

　linky q;

　printf("排序后: ");

　do

　{

　 q=p;

　 printf("%d ",p->data);

　 p=p->right;

　 free(q);/*释放输出结点*/

　}

　while(p!=NULL);

　}

　6．调试记录：

　 第一次输入 136 134 158 123 197 124 156 170 103 101 实现排序

　 第二次调试 输入 12367 15842 12564 13729 49875 1546 15423 15794 54612 1543

　 ７．软件说明

　程序调试运行成功后，排序前随机输入十个不同的数值，快速排序后将由小到大输出这十个数值的排序。如上图说明

　. 8. 设计总结

　一周的上机实践课程结束了，我们也按要求完成了实践内容，这次上机实践，使我巩固了所学的计算机知识，对 C 语言知识有了更进一步的了解。但是知识是学无止境的，我相信，这次的课程设计对我以后在计算机编程这方面有很好的指导意义，让我通过这次实践了解到计算机编程的冰山一角。我此次设计的双向链表的排序程序虽然比较典型，对我们认识数据结构和 C 程序设计却有很好的帮助。

　在设计中我遇到了很多编程方面的难点，在老师的辛勤指导和同学们的热心帮助下，我慢慢的找到了解决问题的方法。在老师的指导下我学到很多实用的知识，在此表示感谢！感谢老师和同学们的帮助和支持。

推荐访问： 双向 排序 链表