数据结构joseph环精选.doc

Joseph环 课程设计目的 ⑴ 通过独立解决某个课程设计问题，在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。 ⑵ 深刻理解、牢固掌握数据结构和算法设计技术， 提高分析和解决实际问题的能力。 ⑶ 在程序设计方法以及上机操作等基本技能和科学作风方面进行比较系统和严格的训练。 设计方案论证 2.1 设计思路 首先,定义两个结构体,将个人的信息写入其中内容包括个人的顺序号(Num),个人的密码m (随机输入的值)及指针. 第二,再将每个人的信息存储于一个单向循环链表内. 第三,根据题目要求编写程序,开始随机把一个数赋给m,开始报数(查找)则将顺序号为m的人的编号提出列,并将其的密码(随机输入的)赋给m. 最后,m有了新值,再从出列的人的下一个位置开始重复上面第三步,直到所有人的顺序号都被调出,结束程序。 2.2设计方法： 2.2.1 结构设计 利用单向循环链表存储结构模拟此过程,按照出列的顺序输出各个人的编号。输入数据：建立输入函数处理输入数据,输入m值和n值，存放在由DATA结构体为存储元素的顺序存储结构里。再建立单向循环链表，节点结构为NODE结构体，将所有信息存在链表里。输出形式：建立一个输出函数,将正确的输出序列。 2.3算法设计 2.3.1 线性表的单链表存储结构 typedef struct node {int num; //成员编号 int m; //每个成员的唯一编码 struct node *next; }NODE,*LINK; 2.3.2 线性表的动态分配顺数存储结构 typedef struct data //输入函数中数据存储节点结构 {int num; int m; } DATA; 2.3.3 数据输入函数 DATA InputData（） 输入函数采用线性表的顺序存储结构，线性表的顺序存储结构是一种随机存取的存储结构。特点是存储空间连续，用一组地址连续的存储单元依次存储线性表的数据元素。并且逻辑位置相邻的两个元素其物理位置也相邻。每一个数据元素的存储位置都和线性表的起始位置相差一个和数据元素在线性表中的位序成正比的常数，由此，只要确定了存储线性表的起始位置，线性表中的任一数据元素都可以随机存取。由于高级程序设计语言中的数组类型也有随机存取的特性，因此，通常都用数组来描述数据结构中的顺序存储结构。线性表的顺序存储结构需要预先分配存储空间。 输入函数算法设计如下： DATA *InputData (int *n) //数据输入函数，n 是节点的个数 {DATA *d, *p, *s; //d用来存放数组空间的首地址 int i; printf(How many people there are?\n); printf(Please Input length:); scanf(%d,n); // 输入节点数 d=(DATA *)malloc(*n*sizeof(DATA)); //申请内存空间函数malloc返回首地址存放在DATA类型的d变量里 p=d; for(i=1;i=*n;i++) //动态输入各节点信息 {printf(Number%d ---- input m: ( m means the secret of them! ) ：,i); scanf(%d,p-m); p-num=i; p++; } return(d); //返回内存空间的首地址 } 输入函数流程图如下： 图1 输入函数流程图 2.3.4 单向循环链表的建立 LINK CreateLinklist ( DATA *d, int n ) 单向循环链表是一种链式存储结构，它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环，由此，从表中任意结点出发均可找到表中其他结点。单向循环链表的构造类似于单向链表的构造，但是不同的是最后一个元素的指针指向的是首元素。 循环链表的操作和线性链表基本一致，差别仅在于算法中的循环条件不是p或p-next是否为空，而是他们是否指向头指针，但有的时候，若在循环链表中设置尾指针而不设头指针，即带尾指针的单向循环链表，可使某些程序简化。 单链表和顺序存储结构不同，它是一种动态结构，整个可用存储空间可为多个链表共同享用，每个链表占用的空间不需预先分配划定，而可由系统应需求直接生成，因此，建立线性表线性存储结构的过程就是一个动态生成链表的过程。 在单链表中任何两个元素的存储位置之间没有固定的联系。但每个元素的存储位置都包含在其直接前驱节点的信息之中。假设p是指向线