数据结构课程设计报告

一、课程设计概述：

本次数据结构课程设计共完成两个题：快速排序、josephu 问题。

使用语言：c

编译环境：visual c++ 6.0

二、课程设计题目一。

实验内容]快速排序。

问题描述]输入有限个数据，按照从小到大的顺序进行快速排序。

需求分析]要求及提示：

1、对用上述算法进行快速排序，写出运行结果。

2、写出用上述算法进行的第一趟快速排序后的结果。

3. 界面美观。

详细设计]程序清单：

#include<>

#define max 100

int r[max];

void quicksortl(int r[ ]int s,int t)

while((r[0]>=r[i])&i i++;if(i

r[i]=r[0];

if(s quicksortl(r,s,i-1);

if(t>i+1)

quicksortl(r,i+1,t);

void main( )

int i,n;

printf("请输入待排序元素的个数（少于100个）:

scanf("%d",&n);

if(n>=100)

quicksortl(r,1,n);

printf("排序结束后为：")

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

printf("%1d ",r[i]);

调试分析]本程序主要的操作对象是记录数据，然后对数据进行排序处理，最后输出处理后的数。

据。怎么进行排序是一个重点也是难点，是此程序出现问题的主要原因之一：

问题一：现象：当输入的数据个数大于规定的最大数时，程序仍在继续运行。

原因：该程序中缺少一个排错片段。导致输入数据个数大于定义最大值时，不会产生中断，继续向下面的排序函数运行。

解决方法是对数据输出时，添加一个if语句，当输出的数据大于100时，提醒用户重新输入正确数据。

问题二：现象：排序时只进行第一次排序，余下的数未参与到排序中，直接输出到排序后的队列。

原因：在编写主要函数排序函数时，未采用循环语句或有非法终止的条件。导致进行第一次排序后，条过了后面的数据，直接进行了输出函数。

解决方法是将该函数分成两种情况来分析，即r【0】与r【j】的关系。

运行结果及分析]

1. 对用上述算法进行快速排序，写出运行结果。

运行结果如下：

2. 写出用上述算法进行的第一趟快速排序后的结果。

运行结果如下

3. 若出现输出大于100，则输出如下：

参考文献】1].《c程序设计》第二版，谭浩强著。北京：清华大学出版社，2024年。

2].《数据结构》严蔚敏、吴伟民。北京：清华大学出版社，2024年。

课程设计题目二：

实验内容】=

josephu 问题。

问题描述=】

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

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

实现提示】用一个不带头结点的循环链表来处理josephu 问题：先构成一个有n个结点的单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。

测试数据】m的初值为20；n=7，7各人的密码依次为：3，1，7，2，4，8，4。

详细设计]程序清单：

#include<>

#include <>

struct mannode

int number;

struct mannode *next

int password;

void main()

int m;

int numman;

struct mannode *head;

void deletenode(int mannumber,int number,struct mannode *head);

struct mannode *createlist(int numofman);

printf("请输入参加的人数 n

scanf("%d",&numman);

head=createlist(numman);

printf("请输入刚开始报数上限数 m

scanf("%d",&m);

deletenode(numman,m,head);

getchar();

free(head);

struct mannode *createlist (int numofman)

struct mannode *head,*mannodeptr1,*mannodeptr2;

head=null;

int num=1;

mannodeptr2=(struct mannode *)malloc(sizeof(struct mannode

printf("请输入用户所持有的密码。

scanf("%d",&mannodeptr2->password);

mannodeptr2->number=num;

head=mannodeptr2;

while(num!=numofman)

nummannodeptr1=(struct mannode *)malloc(sizeof(struct mannode

printf("请输入用户所持有的密码。

scanf("%d",&mannodeptr1->password

mannodeptr1->number =num

mannodeptr2->next =mannodeptr1

mannodeptr2=mannodeptr1;

mannodeptr2->next =head;

printf("输入结束！");

return head;

void deletenode(int mannumber,int number,struct mannode *head)

int num=1;

struct mannode *mannodeptr1;

struct mannode *mannodeptr2;

mannodeptr1=mannodeptr2=head;

while(mannumber>0)

while(num!=number

mannodeptr2=mannodeptr1

mannodeptr1=mannodeptr1->next

number

number=mannodeptr1->password;

printf("出列人的编号：%d",mannodeptr1->number) ;

mannodeptr2->next =mannodeptr1->next

mannodeptr1=mannodeptr1->next ;

mannumber--;

printf("运行结束！！！n");

调试分析]本程序用一个不带头结点的循环链表来处理该问题，先构成一个有n个结点的单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。

运行结果及分析]

m的初值为20；n=7，7各人的密码依次为：3，1，7，2，4，8，4 时，运行结果如下：

数据结构课程设计报告

数据结构课程设计报告

数据结构课程设计报告

数据结构课程设计报告

其他用户还读了