双向链表排序实验报告
陈祎智
实验报告<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 程序设计却有很好的帮助。
在设计中我遇到了很多编程方面的难点，在老师的辛勤指导和同学们的热心帮助下，我慢慢的找到了解决问题的方法。在老师的指导下我学到很多实用的知识，在此表示感谢！感谢老师和同学们的帮助和支持。
上一篇：乡镇卫生院调研报告例文x
下一篇：乡镇意识形态工作自查报告