题 目: 链式简单选择排序
初始条件：
理论：学习了《数据结构》课程，掌握了基本的数据结构和常用的算法；
实践：计算机技术系实验室提供计算机及软件开发环境。
要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）
1、系统应具备的功能：
（1）用户自己输入数据的个数和数据；
（2）建立链表；
（3）基于链表的排序算法实现。
2、数据结构设计；
3、主要算法设计；
4、编程及上机实现；
5、撰写课程设计报告，包括：
（1）设计题目；
（2）摘要和关键字；
（3）正文，包括引言、需求分析、数据结构设计、算法设计、程序实现及测试、结果分析、设计体会等；
（4）结束语；
（5）参考文献。
时间安排： 2007年7月2日－7日 （第18周）
7月2日 查阅资料
7月4日-5日 编程并上机调试
7月6日 撰写报告
7月7日 验收程序，提交设计报告书。
指导教师签名： 2007年7月2日
系主任（或责任教师）签名： 2007年7月2日
链式简单选择排序
摘要：单链表为存储结构，并在这个基础上实现简单选择排序。一趟简单选择排序的操作为：通过n-1次关键字之间的比较，从n-i+1个记录中选出最小的记录并将这个记录并入一个新的链表中，在原链表中将这个结点删除。
关键字：单链表，简单选择排序，结点，记录
0. 引言
《数据结构》是计算机科学与技术、软件工程及相关学科的专业基础课，也是软件设计的技术基础。《数据结构》课程的教学要求之一是训练学生进行复杂的程序设计的技能和培养良好程序设计的风格，其重要程度决不亚于理论知识的传授，因此课程设计环节是一个至关重要的环节，是训练学生从事工程科技的基本能力，是培养创新意识和创新能力的极为重要的环节。基本要求如下：
(1) 熟练掌握基本的数据结构；
(2) 熟练掌握各种算法；
(3) 运用高级语言编写质量高、风格好的应用程序。
因此在这个课程设计中我选择的是链式简单选择排序。这个实验的实验要求是利用单链表作为记录（数据）的存储结构，并且在记录好用户输入了数据之后对这组数据进行输出，然后对其进行排序，并且输出排序好的数据。
1.需求分析
（1）在这个实验中的数据的存储结构要求是用单链表，不是用数组，也不是循环链表也不是循环链表。
（2）这组数据的大小（即这组数据的个数）是由用户输入的。
（3）用户输入完数据之后，程序能自动的将这些数据（记录）用单链表存储起来。
（4）用户输入完数据之后，程序要输出这些数据，以便用户查看自己是否输入错误。
（5）对用户输入的数据要自动进行排序操作。
（6）排序完了之后，程序可以自动的输出排序好的数据。
2.数据结构设计
在这个程序中用的存储结构是单链表，对于单链线性表的声明和定义如下：
#define datatype int
typedef struct Lnode
{ datatype data;//结点的数据域
struct Lnode *next;//结点的指针域
} key,*keylist;
其中的“datatype”为整型,其中的“*next”为指针类型，“*keylist”也是指针类型
3.算法设计
3.1 对于使用的算法的简单的描述
在这个课程设计中，我要做的是用单链表做存储结构，将记录的数据惊醒简单选择排序，在简单选择排序的过程中不需要最小值到底是多少，而需要知道的是它在原链表中的位置i，和其前驱结点的位置。
在这个实验中需要求出位置i，这个函数中，由于在单链表中必需将每个值都比较一次，所以需要用一个变量记下最小值所在的位置就。
另外还需要找到最小值的前驱，这个就只是需要在原链表中，将指向结点的指针向后移动i-1个位置就行了。
在这个课程设计中还需要注意的是函数之间参数的传递，虽然在下面的函数中没有用return语句来返回值，但是由于在C语言中，不能由“&”（在C ++中可以使用）来返回值。所以对于那些算法应当进行适当的改正。否则将不能达到所需要的功能。
3.2 删除结点算法
Status listDelete_b(keylist &L,int i,datatype &e)
{ //在带头结点的单链线性表L中，删除第i个元素，并由e返回其值
P<-L;j<-0;
while(p->next&&j<i-1)//寻找第i个结点，并令p指向其前驱
{ p=p->next;
j++;
}
if(!(p->next)||j>i-1)
return ERROR;// 删除位置不合理
q=p->next; // 删除并释放结点
p->next=q->next;
e=q->data;
free(q);
return OK;
}
3.3 加入结点
Status ListInsert_L(keylist &L, int i , datatype e)
{// 在带头结点的单链线性表L中第i个位置之前插入元素e
p=L;
j=0;
while(p不为空或j小于i-1) //寻找第i-1个结点
{ p=p->next;
++j;
}
if(p为空或j大于i-1)
return ERROR; //i小于1或大于表长
s->data=e;
s->next=p->next;
p->next=s;
return OK;
}
3.4 简单选择排序算法
void simplesort(keylist L, keylist &q )
{ //将带头结点的单链线性表L中的数据进行简单选择排序，并且将排序好的结果用
//带头结点q的单链表返回
q->next=Null;
r=q;
while(p不为空)
{
i=findmin(L);//在现有的元素中找到最小值在现在的链表中的位置i
p=premin(L,i);//找到最小值结点的前驱结点
if(p为空)
reurn ERROR;
u=p->next; // 将最小值从单链表L中删除结点，并入新链表q中。
p->next=u->next;
u->next=r->next;
r->next=u;
r=u;
}
}
3.5查找最小值算法
int findmin(keylist L)
{//在带头结点的单链表L中找关键字最小的元素的位置，并返回其位置
int k=0, i=0;
datatype min=30000;
keylist p;
p=L;
while(p不为空)//查找关键字最小的元素在单链表中的位置
{ k++;
if(p的值小于min)
{ min=p->data;
i=k;
}
p=p->next;
}
return i;
}
3.6创建单链表算法
void creatlink(keylist &L,int n)
{//建立一个带有头结点L的，有n个结点的单链表
L->next=Null;
r=L;
for(i=1;i<=n;i++)
{ 输入q的值;//输入结点数据
q->next=r->next;//将结点并入单链表L中
r->next=q;
r=q;
}
}
3.7有关技术讨论
在这个题目中使用的技术有：创建一个单链线性表，在单链表中找最小值的位置，在单链表中找最小值所在结点的前驱结点的地址，以及在单链表中插入和删除结点。以下分别对它们进行说明。
3.7.1 创建一个单链线性表：
首先，分配头结点；
然后，每次都产生一个新的结点，并对这个新结点赋值；
最后，将这个结点放在单链表的表尾。
3.7.2 在单链表中找最小值的位置：
首先，在这个函数先定义一个datatype型的变量min，并将这个变量赋为最大值，并且用一个变量i来记录最小值的位置，用变量k来进行计数（用来存放当前结点是在原链表中的第几个结点）；
再次，用min和当前结点的关键字进行比较，如果当前结点的关键字比较小，就将min的值赋为当前结点的关键字，并且将k的值赋给i。一直重复这个步骤，知道最后一个结点，这样就能够找到单链表中的最小值了；
最后，返回这个最小值所在的位置。
3.7.3 在单链表中找到最小值所在结点的前驱结点：
首先，在这个程序中用一个keylist类型的变量“p”来记录结点的地址；
再次，将指针“p”从都结点的位置向后移动i-1个位置，就能得到最小值所在结点前驱结点的位置；
最后，返回这个位置。
3.7.4 在单链表中插入一个结点
在这个课程设计中需要插入的位置始终是在表尾，所以用一个指针始终录表尾所在的位置就可以了。每次都只需要在表尾插入一个结点，再修改尾的位置即可。
3.7.5 在单链表中删除一个结点
首先，利用前面已经叙述的算法，找到最小值所在结点的前驱结点的位置，并下来；
其次，使用一个新的keylist类型的指针，并且是它指向最小值所在的结点的地址；
最后，让前驱结点的后继指向最小值所在结点的后继，这样就将这个含有最小值的结点从原链表中删除了。这样做的原因是因为这个最小值所在的结点在从原链表中删除后并没有释放其空间，而是将它并入了新链表的表尾，所以这个结点是仍然存在的。只是它在排序后的链表中去了。
4. 程序实现
4.1 程序中函数的声明
int selectminkey(key *head)；/*在单链表中找到最小值的位置*/
keylist premin(key *h,int j)；/*找到最小值所在结点的前驱结点*/
keylist createkeys(int n)；/*创建有n个结点的带头结点的单链表*/
4.2 主要算法代码实现
4.2.1 查找最小值算法程序
int selectminkey(key *head)/*在单链表中找到最小值的位置*/
{ int m;/*用来记录最小值的位置*/
int k=0;/*k用来记下当前结点在原链表中是第几个结点*/
keylist po,min;/*用来记录最小值*/
min=(keylist)malloc(sizeof(key));
po=(keylist)malloc(sizeof(key));
po=head->next;
min->data=30000;
if(po==null) return 0;
m=1;
while(po!=null)
{ k=k+1;
if(po->data<min->data)
{ min->data=po->data;
m=k;
}
po=po->next;
}
return m;/*返回最小值的位置*/
}
4.2.2 找最小值结点前驱结点算法程序
keylist premin(key *h,int j)/*找到最小值所在结点的前驱结点*/
{ int i;
keylist qo;/*记录前驱结点*/
qo=(keylist)malloc(sizeof(key));
qo=h;
for(i=1;i<j;i++)
{ qo=qo->next;
}
return qo;/*返回前驱结点*/
}
4.2.3 创建单链表算法程序
keylist createkeys(int n)/*创建有n个结点的带头结点的单链表*/
{ keylist head,rear,po;/*定义头结点，尾结点，和中间结点*/
int i;
head=(keylist)malloc(sizeof(key));
rear=(keylist)malloc(sizeof(key));
head->next=null;
rear=head;
for(i=1;i<=n;i++)
{ printf("Please input the data %d\n",i);
po=(keylist)malloc(sizeof(key));/*生成新结点*/
scanf("%d",&(po->data));/*输入新结点的数据*/
po->next=rear->next;/*将新结点并入链表*/
rear->next=po;
rear=po;
}
return head;
}
4.2.4 删除结点和加入结点算法程序
main()
{ int i,j,n;
keylist h,p,q,ho,r;
printf("\n Please input the number of the datas\n");
scanf("%d",&n);
h=(keylist)malloc(sizeof(key));
r=(keylist)malloc(sizeof(key));
p=(keylist)malloc(sizeof(key));
q=(keylist)malloc(sizeof(key));
ho=(keylist)malloc(sizeof(key));
ho->next=null;
r=ho;
h=createkeys(n);/*调用创建单链表的函数，并得到其头结点*/
p=h->next;
printf("\n the primary datas is: ");
for(i=1;i<=n;i++)
{ printf("%d ",p->data);
p=p->next;
}
for(i=1;i<=n;i++)/*简单选择排序*/
{ j=selectminkey(h);/*调用函数找到最小值的位置*/
q=premin(h,j);/*调用函数找到最小值所在结点的前驱结点的地址*/
p=q->next;
q->next=p->next;
p->next=r->next;
r->next=p;
r=p;
}
printf("\n the datas after sorting is: ");
r=ho->next;
while(r!=null)/*输出排序后的数据*/
{ printf("%d ",r->data);
r=r->next;
}
}
4.3 运行结果
4.3.1 计算机输出提示及用户输入数据个数
4.3.2 计算机提示及用户输入20个数据
结果分析：这个实验的实验结果完全正确。这个程序采用的是简单选择排序
结果分析：它的特点是每一趟在n-i+1（i=1,2,……,n）个记录中选取关键字最小的记录作为有序序列中第i个记录。在这个程序中还是采用的链式存储结构。这种排序最简单，很容易被读者理解。运行的时间复杂度为O(n)。这种排序对于n（数据的个数）较小时是很使用的。它的缺点是当n很大的时候很耗时间，效率不高。
5.设计体会
在整个课程设计的过程中，使我懂得了如何分析一个较复杂的问题，并且针对这个实际的问题选择适当的算法来解决我的问题，并且针对这个问题，怎样对所选择的算法进行适当的该经，以求这个算法能为我所用。最重要的是通过这个课程设计的实际问题使我懂得了怎样在程序中设计我的参数的正确传递。
也是我体会到了单链表的定义，在单链表中进行查找，插入，删除等很多的操作。在这整个设计中使我对于单链表的一些操作有了更进一步的认识，并熟练的掌握了它。
在这个课程设计中通过编程是我懂得了在计算机上怎样表示这些算法，怎样正确的使用这些算法。也使我懂得了如何对一个程序进行调试，如何在不改变程序功能的前提下对程序进行一些简单的改进。也让我懂得了在把写好的程序输入计算机的时候要仔细，要不会出现很多小错误，那些错误本来是可以减少到几乎为零的。
6.结束语
这次课程设计，我用单链表为存储结构，利用了单链表的插入、删除结点，以及创建单链表等算法实现了让用户自己输入数据的个数和数据，然后建立单链表，再将这些数据进行简单选择排序并输出结果。
参考文献
[1] 严蔚敏,吴伟民.《数据结构》,清华大学出版社,2001年1月.
[2] 张颖江,胡燕.《C语言程序设计》,科学出版社,1998年7月.
[3] 谭浩强.《C程序设计》,清华大学出版社,1999年12月.
