数据结构课程设计报告.docx

1、数据结构课程设计报告数据结构课程设计 题目一：约瑟夫环题目二：可变长顺序表设计班 级： 软件1303姓 名： 学 期：2014-2015学年第二学期题目一：约瑟夫环问题描述：编号为1，2，n的n个人按顺时针方向围坐一圈，每人持一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 基本要求 利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。基本要求：1. 用不带头结点单

2、循环链表方法设计；2. 键盘输入总人数、初始报数上限值m及个人密码；3. 按照出列顺序输各人的编号。测试数据：m的初始值为7,n为5，各人密码依次为1，3，5，7，9。正确出列顺序应为2，5，4，1，34. 算法思想：是用不带头结点单循环链表存储每个人的密码，链表长度为n，由用户键入m,n,key完成出列计算。模块划分：main函数完成全部内容数据结构：单循环链表源程序：#includestdio.h#includemalloc.h struct node int no; int code; node *next;int main() int m,n,i,j; node *p,*q,*firs

3、t; printf(* * * * * * * * * * * * *约瑟夫环* * * * * * * * * * * * *nn); printf(请输入m的初始值 m:); scanf(%d,&m); printf(n请输入人数 n:); scanf(%d,&n); printf(n); for(i=1;inext=q; p=q; printf(第%d个人的key为: ,i); scanf(%d,&p-code); p-no=i; p-next=first; p=first; printf(nn* * * * * * * * * * * * *出列* * * * * * * * * *

4、* * *nn); for (j=1;j=n;j+) for(i=1;inext); m=p-code; printf(%d ,p-no); p-no=p-next-no; p-code=p-next-code; q=p-next; p-next=p-next-next; free(q); printf(nn完毕n); return 0;测试情况：题目二：可变长顺序表设计问题描述：编写一个函数，实现用键盘输入顺序表的元素进行建立顺序表的操作。然后依次调用初始化、求数据元素个数，插入、删除和取数据元素并输出新的顺序表。 基本要求：（1）使用动态数组结构。（2）顺序表的操作包括：初始化、求数据元素

5、个数、插入、删除、取数据元素，编写每个操作的函数。（3）设计一个测试主函数。测试数据：以随机输入的元素为原始数据算法思想：可变长顺序表的设计，主要是利用动态数组结构的设计方法。动态数组是指用动态内存分配方法定义的数组，他中的元素的个数是在用户申请动态数组空间时才确定的。此外，用键盘输入顺序表的元素，进行建立顺序表。依次调用初始化、求数据元素个数，插入、删除和取数据元素并输出新的顺序表。模块划分：Main.c文件。Main.c文件包括以下函数：初始化，求数据元素个数，插入，删除，取数据元素。void Initiate(SeqList *s,int max) 函数：其功能是用于顺序表的初始化。in

6、t ListLength(SeqList *L) 函数：其功能是用于求顺序表的数据元素个数。int Insert(SeqList *s) 函数：其功能是用于顺序表的插入。int Delete(SeqList *s) 函数：其功能是用于顺序表的删除。int getdata(SeqList *s) 函数：其功能是用于函数的获取元素void main（）函数：主函数。其功能建立顺序表并调用以上函数实现问题要求。数据结构：1.顺序表结构体定义：typedef struct int *str; int Length; SeqList; 2.动态数组动态申请空间：s-str=(int *)malloc(s

7、izeof(int)*max);源程序：#include #include #include typedef struct int *str; int Length; SeqList; void main() void Initiate(SeqList *s,int max);/函数声明 int ListLength(SeqList *s); int Insert(SeqList *s); int Delete(SeqList *s); int Getdata(SeqList *s); void Print(SeqList *s,int); SeqList L; int x,max; prin

8、tf( +可变长顺序表设计+n); printf(n 请输入创建顺序表的长度:); scanf(%d,&max); printf( 请输入创建的顺序表的值:); Initiate(&L,max); printf(n); printf( +n); printf( + 功能选项 +n); printf( + 1.数据元素个数 2.数据元素插入 +n); printf( + 3.数据元素删除 4.取数据元素 +n); printf( + 0.退出 +n); printf( +n); way: printf(n 输入序号选择程序功能:); scanf(%d,&x); if(x=1) printf( 数

9、据元素个数是：%dn,ListLength(&L); goto way; if(x=2) Insert(&L); goto way; if(x=3) Delete(&L); goto way; if(x=4) Getdata(&L); goto way; if(x=0) printf(nn 谢谢使用!nn); void Initiate(SeqList *s,int max)/初始化顺序表 int i,x; s-str=(int *)malloc(sizeof(int)*max);/动态申请空间 s-Length=max; for(i=0; istri=x; int ListLength(Se

10、qList *L) /元素个数 return L-Length; int Insert(SeqList *s) /插入 int i,j,x; printf( 请输入要插入的位置及数据: ); scanf(%d %d,&j,&x); if(js-Length+1) printf( 参数不合法!n); return 0; else realloc(s-str,(s-Length+1)*sizeof(int);/新结点申请空间 for(i=s-Length-1;i=j-1;i-) s-stri+1=s-stri; s-strj-1=x; s-Length+; printf( 新的顺序表是：); fo

11、r(i=0;iLength;i+) printf(%d ,s-stri); printf(n); return 1; void Print(SeqList *s,int max) /顺序表 int i; for(i=0;istri); int Delete(SeqList *s) /删除 int i,j,x; printf( 请输入要删除数据的位置：); scanf(%d,&j); if(js-Length) printf( 参数不合法!n); return 0; x=s-strj-1; for(i=j;iLength;i+) s-stri-1=s-stri; s-Length-; print

12、f( 删除的数据为:%dn,x); printf( 新的顺序表为: ); for(i=0;iLength;i+) printf(%d ,s-stri); printf(n); return 1; int Getdata(SeqList *s) /取数据元素 int j,x; printf( 请输入要获取元素的位置:); scanf(%d,&j); if(js-Length) printf( 参数不合法!n); return 0; else x=s-strj-1; printf( 获取的元素为: %dn,x); return 1; 测试情况：个人总结：在这次课程设计中，我收获了很多单从课本上不能学到的知识，以及经验，这对我对数据结构这门课程的认识与理解有很大的帮助。