数据结构课程设计

湖南工学院计算机系。

课程设计。课程名称：数据结构。

题目：数据结构课程设计。

年级/专业/班：计本0703班。

学生姓名：邹明军。

学号： 310070303

指导老师：彭代文。

开题时间： 2024年06月11日。

完成时间： 2024年06月15日。

目录。一 joseph环 1

1.1 任务 1

1.2 概要设计 1

1.2.1 设计思想 1

1.2.2 算法描述 1

1.2.3 数据结构 3

1.3 详细设计 3

1.4 测试与性能分析 5

1.4.1 测试 5

1.4.2 性能分析 5

二纸牌游戏 6

2.1 任务 6

2.2 概要设计 6

2.2.1 设计思想 6

2.2.2 算法描述 6

2.2.3 数据结构 6

2.3 详细设计 7

2.4 测试与性能分析 7

2.4.1 测试 7

2.4.2 性能分析 8

三课程设计体会 8

四参考文献 8

编号是1，2，……n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。

设计一个程序来求出出列顺序。

要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。

测试数据：m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？

要求：输入数据：建立输入处理输入数据，输入m的初值，n ，输入每个人的密码，建立单循环链表。

输出形式：建立一个输出函数，将正确的输出序列。

建立单循环链表，将每个的信息储存此链表中，构成一个圈。递归调用循环删除函数，每一个人出列打印他的id号，将他的key赋给m。直到链表中只剩下一个人，打印他的id。

算法流程图如下：

利用单循环链表存储结构。

源**如下。

#include<>

typedef struct node

int number;

int key;

struct node *next;

lnode,*linklist;//定义结点结构。

linklist h;定义头结点。

initlist(int n)

int i;

int key;

linklist l;

if (n>=1)

h=h->next;//构成循环单链表。

elseprintf("the input is error")/输入错误；

joseph(int m,linklist h)

int i;

linklist l;

l==h;i=1;

while(i!=m) /依次访问结点。

printf("%3d",h->number);

m=h->key;

l->next=h->next;

free(h);/删除释放结点。

h=l->next;

if(h!=l)

joseph(m,h);/递归调用此函数。

elsemain()

int n;

int m;

int i;

clrscr();

printf("please input the first key of m:")

scanf("%d",&m);

printf("please input how many number of the joseph:")

scanf("%d",&n);

printf("please input the key from number1 to number%d:",n);

initlist(n);

printf("the order of dequeue is:")

joseph(m,h);

程序运行如下图。

算法时间复杂度。

t(n)=n+n*n/m*m

算法空间发杂度。

s(n)=n

编号为1-52张牌，正面向上，从第2张开始，以2为基数，是2的倍数的牌翻一次，直到最后一张牌；然后，从第3张开始，以3为基数，是3的倍数的牌翻一次，直到最后一张牌；然后…从第4张开始，以4为基数，是4的倍数的牌翻一次，直到最后一张牌；..再依次5的倍数的牌翻一次，6的，7的直到以52为基数的翻过，输出：这时正面向上的牌有哪些？

定义一个长度为53数组，一张牌为数组的一个元素，定义元素值“1“为纸牌正面向上，”0“为正面向下。开始所有元素的值都为1.利用两个嵌套循环进行翻牌，内循环控制翻牌，外循环控制基数。

牌被翻一次值取反，最后输出数组中值为1的元素的序号。

程序n-s图如下。

此程序只利用数组存储结构。

源**如下。

main()

int a[53];

int i,j;

for(i=1;i<=52;i++)

a[i]=1;

for(i=2;i<=52;i++)外循环控制基数增加。

for(j=2;j<=52;j++)内循环控制翻牌。

if(j%i==0)

a[j]=~a[j];/牌翻值取反。

printf("positive upward the number of licenses:")

for(i=1;i<=52;i++)

if(a[i]==1)

printf("%3d",i);/输出数组中值为1的元素的序号。

程序运行结果如下。

算法时间复杂度。

t(n)=n*n

算法空间复杂度。

s(n)为连续的53个内存单位。

通过此程序设计，使我更好的掌握了线性结构。也使我明白了程序设计是一个要先想透使用何种算法，再通过所学反复修改、测试、纠正的过程。更使我树立学好这门课程的信心。

有些问题看似复杂，只要我们弄明白其中的缘由，其实很简单。

1] 严蔚敏、吴伟民·数据结构·清华大学出版社·2024年4月第一版。

2] 谭浩强·c程序设计·清华大学出版社·2024年7月第3版。

数据结构课程设计

数据结构课程设计

数据结构课程设计

数据结构课程设计

其他用户还读了