排序系统

《排序系统》由会员分享，可在线阅读，更多相关《排序系统（8页珍藏版）》请在装配图网上搜索。

1、课程设计任务书20112012学年第1学期 电子与信息工程 系 专业 班级课程设计名称： 数据结构课程设计 设计题目： 排序系统 完成期限：自 2012 年 1 月 2 日至 2012 年 1 月 6 日共 1 周设计依据、要求及主要内容（可另加附页）：一、设计目的熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。二、设计要求 （1）重视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务；（2）按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者与被抄袭者皆以零分计入本课程设计成绩。凡发现实验报告或源程序雷同，涉及的全部人员皆以零分计入本课程

2、设计成绩；（3）学生在接受设计任务后，首先要按设计任务书的要求编写设计进程表；（4）认真编写课程设计报告。三、设计内容设编号为1，2，3，n的n(n0)个人按顺时针方向围坐一圈，每个人持有一个正整数密码。开始时任选一个正整数做为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m是停止报数，报m的人出列，将他的密码作为新的m值，从他的下一个人开始重新从1报数。如此下去，直到所有人全部出列为止。令n最大值取30。要求设计一个程序模拟此过程，求出出列编号序列。初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数。四、参考文献1王红梅数据结构清华大学出版社2王红梅数据结构学习辅导与实验

3、指导清华大学出版社3严蔚敏，吴伟民数据结构（C语言版）清华大学出版社目录一、需求分析3二、总体设计3三、详细设计5四、调试与测试5五、关键源程序清单和执行结果5六、参考资料8一、需求分析本系统为实现排序功能，输入所要排序的人数，要求人数大于等于1小于等于30人并为其排号，系统运用循环链表将输入的n个人顺时针排成环。每人手里又一张密码牌，密码拍亦要求大于等于1，记录为m的值，首先，一圈人顺时针报数。利用指针将m指向与其相同的报数号，记录该人的报数号和密码值并将其作为作为新的m值，该人出链，指针指向下一人，重复执行以上操作直至链表为空，记录出链顺序号。 二、总体设计程序设计组成框图流程图（见右图）

4、三、详细设计定义结构体people，并定义number，key为整型。struct people声明结构体类型people,定义类link，声明两个成员函数create和show。定义人数n与密码m值。class link链表类,此类包含多个people类,并控制输入输出。link()定义构造成员函数，函数名与类名相同。m=0;n=0;head=NULL;利用构造函数对对象中的数据成员赋初值。void create()声明环的成员函数。void show()声明运算并输出的成员函数。Create函数用来建立相应的输入输出功能和建立循环链表。其中，链表的定义借助两个临时指针p1,p2。p1=ne

5、w people，利用for循环（利于一个int型数据存放结点编号，进而实现循环），通过临时指针的首尾相接，建立循环链表，输出链表数据。考虑到链表为空的情况，添加if语句，避免出现编译错误。person *p1,*p2定义2个临时指针。p1=new people新实例化一个人的对象。p1-number=i给这个人编个号。如果当前链表为空,头结点指向第一个人。否则,p2永远指向尾结点,新建的结点都接到p2之后。p2-next=head;/把链表连成一个循环链表(就是一个环)Show函数执行排序功能，设int型函数count，初值为1，通过循环语句找到第m个人，利用三个临时指针，p1.p2和p，将

6、p1指向m个人，p2指向他的前一人，p2-next指向p1-next，实现第m人的出链，将p1指针后移一位,p指针指向该结点，即第m人，删除该结点。此外要将m值赋给p1-key，m值更新，下一次循环开始，直至链表结点全部出链。用count定位到第m个人,循环后,p1指向这个人,p2指向这个人的上一个人。coutnumber输入当前人的编号。m=p1-key把当前人的密码作为指向下一个人所要经过的人数。p=p1p指向当前这个人。p2-next=p1-next把这个人前面的人和后面的人连接。p1=p1-next下次从这个人的下一个人开始数。delete p从链表中删除这个人。主函数调用create

7、函数和show函数四、调试与测试刚开始研究这个题目时，觉得应该用循环链表写，可是对指针这方面，我并不是很擅长，出了很多错。都是指向的问题。后来经过看书调试，终于把指针这方面的都写对了。五、关键源程序清单和执行结果#includeusing namespace std;struct people/声明结构体类型people int number;/number为编号 int key;/key为密码 people *next;class link/链表类,此类包含多个people类private: int n;/存放人数 int m;/存放初始密码people *head;/链表的头结点publi

8、c:link()/定义构造成员函数，函数名与类名相同m=0;n=0;head=NULL;void create();/声明环的成员函数void show();/声明运算并输出的成员函数;void link:create()/定义成员函数createcoutn;while(n30)/人数取值范围在1到30人之间cout人数错误，请重新输入：n;coutm;while(m1) coutm值输入错误，请重新输入：m;people *p1,*p2;/定义2个临时指针for(int i=1;inumber=i;/给这个人编个号cout请输入第 ip1-key;while(p1-key1) cout密码输

9、入错误，请重新第i个人的密码：p1-key; if(i=1)/如果当前链表为空,头结点指向第一个人head=p1;p2=p1;else/否则,p2永远指向尾结点,新建的结点都接到p2之后p2-next=p1;p2=p1;p2-next=head;/把链表连成一个循环链表(就是一个环)void link:show()/定义类link中的函数showpeople *p1,*p2,*p;p1=head;cout*编号序列结果*endl;/有n个人,所以执行n次循环for(int i=1;i=n;i+)int count=1;/用count定位到第m个人,循环后,p1指向这个人,p2指向这个人的上一个

10、人while(count+next;coutnumber;/输入当前人的编号coutkey;/把当前人的密码作为指向下一个人所要经过的人数p=p1;/p指向当前这个人p2-next=p1-next;/把这个人前面的人和后面的人连接p1=p1-next;/下次从这个人的下一个人开始数delete p;/从链表中删除这个人int main()link l;/定义对象ll.create();/调用l的create函数l.show();/调用l的show函数return 0;六、参考资料1王红梅数据结构清华大学出版社2王红梅数据结构学习辅导与实验指导清华大学出版社3严蔚敏，吴伟民数据结构（C语言版）清华大学出版社7