数据结构实验报告实验5.docx
本科实验报告
课程名称： 数据结构
实验项目： 排序
实验地点： 迎西校区逸夫楼302
专业班级：软件1109学号：2022004872
学生姓名： 栗永春
指导教师： 牛之贤
排序
一、实验目的和要求
目的与要求
二、实验内容和原理
简述题目要解决的问题是什么，并说明输入和输出数据的形式。
简述存储结构和算法的基本思想。
三、主要仪器设备
使用的计算机：硬件配置、软件环境
I、操作方法与实验步骤
列出调试通过的源程序。
习题1：
/*********************************************************************
* 1.设计一个用链表表示的直接选择排序算法，并用程序实现。 *
★算法说明：已知待排序初始序列用单链表存贮，头指针head指向第一个结点★
*,从这个待排序列中找出最小结点，插入head之后，用r来指示。r以前为已*
?排序序列，r以后为未排序序列。再从未排序序列中找出最小结点插入r的后*
★面，让r指向这个结点。反复执行这个过程，直到排好序。 *
#includestdio.h
#includemalloc.h
〃结点
typedefstructno
intx;
structno*next;
}Node,*Node_;
〃函数声明
Node_Structure。;//构建序列链表
voidShow(Node_head);//打印链表
voidSort(Node_head);//排序算法
voidMyfree(Node_head);//空间释放算法
voidmain()
(
Nodehead;
head.next=Structure();
if(head.next==NULL)(
printf(构建序列表失败列)return;
}
Show(head.next);
Sort(head);
Show(head.next);
Myfree(head.next);
)
〃用于构造一个序列链表，返回其第一个元素的指针Node_Structure()
{
intx;
scanf(n%dn,x);
if(x!=O)(
Node_q=(Node_)malloc(sizeof(Node));
q-x=x;
q-next=Structure();
returnq;
}
returnNULL;
〃释放申请的空间
voidMyfree(Node_head)
Node_p;
while(head!=NULL)(
p=head;
head=head-next;
free(p);
)
}
〃打印序列链表中的数据
voidShow(Node_head)(
while(head!=NULL)
(
printf(％4d”，head-x);
head=head-next;
}printf(,\nH);
}
〃排序算法
voidSort(Node_head){
Node_r=head,p;
Node_ident;〃用来记录中间量
Node_identl;〃用来记录中间量的前一个结点
while(r-next!=NULL)(
ident=r-next;
identl=r;
for(p=ident;p-next!=NULL;p=p-next)(
if((p-next-x)(ident-x))(
identl=p;
ident=p-next;
})
identl-next=ident-next;
ident-next=r-next;
r-next=ident;
r=r-next;
习题2：
/★★★**★★★★★★★★***★★★*★★★★★★★★***★★******★★★★***★★★***★★★★★★***★★★******★2.对N个关键字取整数的记录进行整序，以使所有关键字为非负数的记录排在*?关键字为负数的记录之前，要求使用至少的附加空间，且算法的时间复杂度**为0(N)o *
I*:*********************************************************************/
includestdio.h
#defineMAX100
voidmain()(
inta[MAX];
inti,j,n;
printf(请输入记录的总个数。\rT);
scanf(,,%d,,Jn);
printf(“请输入各记录(仅输入关键字)\n)for(i=1;i=n;i++)(
scanf(n%dH,a[i]);)
a[0]=a[1]