数据结构实验报告实验5.docx

本科实验报告课程名称：数据结构实验项目：排序实验地点：迎西校区逸夫楼302专业班级：软件1109学号：2022004872学生姓名：栗永春指导教师：牛之贤排序一、实验目的和要求目的与要求二、实验内容和原理简述题目要解决的问题是什么，并说明输入和输出数据的形式。简述存储结构和算法的基本思想。三、主要仪器设备使用的计算机：硬件配置、软件环境I、操作方法与实验步骤列出调试通过的源程序。习题1：/*1.设计一个用链表表示的直接选择排序算法，并用程序实现。*算法说明：已知待排序初始序列用单链表存贮，头指针head指向第一个结点* ,从这个待排序列中找出最小结点，插入head之后，用r来指示。r以前为已*排序序列，r以后为未排序序列。再从未排序序列中找出最小结点插入r的后*面，让r指向这个结点。反复执行这个过程，直到排好序。*#include <stdio.h>#include <malloc.h>结点typedef struct noint x;struct no *next;Node, *Node_;函数声明Node_ Structure。;/构建序列链表void Show(Node_ head);/打印链表void Sort(Node_ head);/排序算法void Myfree(Node_ head);/空间释放算法void main()(Node head;head.next = Structure();if(head.next = NULL) (printf("构建序列表失败列) return ;Show(head.next);Sort(&head);Show(head.next);Myfree(head.next);)用于构造一个序列链表，返回其第一个元素的指针 Node_Structure()int x;scanf(n%dn, &x);if(x!=O) (Node_q=(Node_)malloc(sizeof(Node);q->x = x;q->next = Structure();return q;return NULL;释放申请的空间void Myfree(Node_ head)Node_ p;while(head != NULL) (p = head;head = head->next;free(p);)打印序列链表中的数据void Show(Node_ head) (while(head != NULL)(printf("4d”，head->x);head = head->next; printf(,'nH);排序算法void Sort(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*:* /include <stdio.h>#define MAX 100void main() (int aMAX;int i, j, n;printf("请输入记录的总个数。rT);scanf(,%d,J &n);printf(“请输入各记录(仅输入关键字)n) for(i=1; i <= n; i+) (scanf(n%dH, &ai); )a0 = a1;® ； j=n;while(ivj) 利用快速排序的思想改写 (while(i<j&&aj>=0) -j;ai = aU;while(i<j&&ai<=0) +i; aj = ai; )ai = a0;for(i=1;iv=n;i+) 打印输出 (printf(H%4d", ai); printf(,'nn);五、实验数据记录和处理列出上面程序对应的运行结果。5 4 3 2 1 05432112345请按任意键继续.区输入记录的总个数。f青输入各记录（仅输入关键字）2 3 -3 -2 TT -2 3132请按任意键继续. . .六、实验结果与分析分析程序的优缺点、时空性能七、讨论、心得改进思想，写出心得体味注：填写内容用5号，宋体，单倍行距