1、1 链式简单选择排序 1 1 设计题目设计题目 链式简单选择排序 2 2 问题描述问题描述 链式简单选择排序即以单链表为存储结构，实现简单选择排序的功能。 显然， 实现该程序就是先要建立一个单链表， 利用单链表对数据进行存储、 操作。 将输入的整型数据以结点的形式存储在这个建立的单链表中。 然后对单链表中的 这些结点的值进行简单选择排序。 该问题中，以带有附加头结点的单链表为存储结构，排序分为从大到小 排序和从小到大排序两种方式，我们可以用这两种方法分别实现进行排序，分别 得到结果。 3 3 设计设计 3 3.1 .1 存储结构设计存储结构设计 线性表的链式存储结构的特点是用一组任意的可以是不
2、连续的存储单元存 储线性表的数据元素。它包括两个域：其中存储数据元素信息的称为数据域； 存储直接后继存储位置的域称为指针域。 单链表结构体的定义如下： Struct link_node /链表节点类的定义 int data; /指针域 link_node*next; /值域，不是float *next; 关于链表中的 /指针指向问题 link_node(link_node*ptr=NULL)next=ptr; /初始化指针成员的构造函数 link_node(const int next=ptr; ; ; /结构体定义“;”结束 其中，值域data以整型存储了所要排序的关键字值，而指针域next
3、以指针型 存储了指向下一个结点的地址。 其中两个构造函数分别用于初始化数据和指针成 员。Link_node是定义的一个全局结构体变量，可以在下面的任何函数中调用。 3.2 3.2 主要算法设计主要算法设计 本程序中主要用到5个函数，分别是构造函数list()、输入结点数据input(int)、 输出数据函数output()、从小到大排列函数SelectSort1()、从大到小排列函数 void SelectSort2()。 构造函数： list()first=new link_node; /创建附加头结点，first指向该结点 输入节点数据函数： 利用后插法建立链表，算法如下 void lis
4、t:input(int endTag) /其中DendTag link_node *newnode,*last; int val; make_empty(); /清空链表 cinval; last=first; while (val!=endTag) /last指向表尾 newnode=new link_node(val); if(newnode=NULL) 3 cerrval; /插入到表末端 last-next=NULL; /可有可无,表收尾 函数SelectSort1( )和SelectSort2( )的基本实现思想是一样的， 只是一些细节有 所不同。两者构成了本程序的主体部分，链式简单
5、选择排序的基本思想是：每一 趟排序（例如第i趟，i=0,1,2，n-2）在后面n-i个待排序的节点数据中找出 最小的元素，作为有序元素排列的第i个元素。待到第n-2趟做完，待排序元素只 剩一个了，就不用再选了。 SelectSort1( ) /实现从小到大 排序，其实现代码见附表实验代码。 SelectSort2( ) /实现从大到小排序，其实现代码见附表实验代码。 这样，主要算法中的函数，只需在主函数中调用即可实现。 3.3 3.3 测试用例设计测试用例设计 任意输入几个数据，以0为终止符，例如输入972845 ，634873，127498， 928134， 518487， 215398，
6、对其进行从大到小的排序， 排序后结果应为972845 ， 928134，634873，518487，215398，127498。 再输入若干整数，例如输入98375 ， 69828， 76837， 10738， 63874， 90897， 对其进行从大到小的排序， 排序后结果应为10738， 63874， 69828， 76837， 90897， 98375 。 4 4 调试报告调试报告 本实验需要采用支持标准 Microsoft Visual C+ 2010 Express 编译器， 并采用最基础的 Win32 控制台程序。 4 在调试程序时，出现错误提示如下： （1） 1- 已启动生成：项目: 链式简单选择排序-初级版, 配置: Debug Win32 - 1 链排序.cpp 1c:usersadmini
