链式简单选择排序课程的设计.docVIP

链式简单选择排序 1 设计题目 链式简单选择排序 2 问题描述 链式简单选择排序即以单链表为存储结构，实现简单选择排序的功能。显然，实现该程序就是先要建立一个单链表，利用单链表对数据进行存储、操作。将输入的整型数据以结点的形式存储在这个建立的单链表中。然后对单链表中的这些结点的值进行简单选择排序。 该问题中，以带有附加头结点的单链表为存储结构，排序分为从大到小排序和从小到大排序两种方式，我们可以用这两种方法分别实现进行排序，分别得到结果。 3 设计 3.1 存储结构设计 线性表的链式存储结构的特点是用一组任意的可以是不连续的存储单元存储线性表的数据元素。它包括两个域：其中存储数据元素信息的称为数据域；存储直接后继存储位置的域称为指针域。 单链表结构体的定义如下： Struct link_node //链表节点类的定义 { int data; //指针域 link_node*next; //值域，不是float *next; 关于链表中的 //指针指向问题 link_node(link_node*ptr=NULL){next=ptr;}; //初始化指针成员的构造函数 link_node(const int item,link_node*ptr=NULL) { //初始化指针成员和数据的构造函数 data=item; next=ptr; }; }; //结构体定义“;”结束 其中，值域data以整型存储了所要排序的关键字值，而指针域next以指针型存储了指向下一个结点的地址。其中两个构造函数分别用于初始化数据和指针成员。Link_node是定义的一个全局结构体变量，可以在下面的任何函数中调用。 3.2 主要算法设计 本程序中主要用到5个函数，分别是构造函数list()、输入结点数据input(int)、output()、从小到大排列函数SelectSort1()、从大到小排列函数 void SelectSort2()。list(){first=new link_node;}; //创建附加头结点，first指向该结点 输入节点数据函数： 利用后插法建立链表，算法如下 void list::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) { cerr存储分配失误endl; exit(1); } //动态分配失败 last-next=newnode; last=newnode; //last永远指向表尾 cinval; //插入到表末端 } last-next=NULL; //可有可无,表收尾 } 函数SelectSort1( )和SelectSort2( )的基本实现思想是一样的，只是一些细节有所不同。两者构成了本程序的主体部分，链式简单选择排序的基本思想是：每一趟排序（例如第i趟，i=0,1,2，…，n-2）在后面n-i个待排序的节点数据中找出最小的元素，作为有序元素排列的第i个元素。待到第n-2趟做完，待排序元素只剩一个了，就不用再选了。 SelectSort1( ) //实现从小到大排序，其实现代码见附表实验代码。 SelectSort2( ) //实现从大到小排序，其实现代码见附表实验代码。 这样，主要算法中的函数，