双向链表排序实验报告

1、本文格式为word版，下载可任意编辑双向链表排序实验报告 陈祎智 试验报告2 1. 问题描述: 双向链表的排序。 要求： 输入一个双向链表，显示些双向链表并对此双向链表排序 2.课题分析(结构图): 3.数据结构的设计: typedef struct node int info; struct node *llink,*rlink; node; 双向链表的排序 双向链表存储结构 快速排序定义 输入数据结点 4.流程图 5源程序： #includeiostream.h #includestdlib.h #include stdio.h 开头 创建链表 初始化链表 从中间分成两部 排序链表 插入

2、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

3、=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-righ

4、t=null; return(head); linky s head,linky one,linky two)/*任意交换两个结点*/ linky temp; if(one-lift=nulltwo-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-righ

5、t; 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-li

6、ft=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=t

7、wo-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;

8、 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!=

9、null;i=i-right)/*用选择法的思想对这些结点排序*/ max=i-data; for(j=i-right;j!=null;j=j-right) if(j-datamax) 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;

10、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 语言学问有了更进一步的了解。但是学问是学无止境的，我信任，这次的课程设计对我以后在计算机编程这方面有很好的指导意义，让我通过这次实践了解到计算机