双向链表的排序实验报告

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

2、uct Link *right;linkx,*linky;linky Init();/*建立双向链表*/void PrLink(linky p);/*输出双向链表*/linky Sort(linky head);/*对双向链表排序*/linky Swap(linky 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; hea

3、d=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 Swap(linky head,linky one,linky two)/*任意交换两个结点*/

4、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;/*尾结点成为头结点*

5、/ 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-

6、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=on

7、e; 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-lif

8、t=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;

9、j=j-right) if(j-datadata; t=j; if(max!=i-data)/*假如没有找到比i小的结点*/ head=Swap(head,i,t);/*因为最终返回的是头结点,而头结点又有可能变化,所以每次头结点返回*/ 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语言知识有了更进一步的了解。但是知识是学无止境的，我相信，这次的课程设计对我以后在计算机编程这方面有很好的指导意义，让我通过