数据结构课程设计报告

数据结构。

课程设计报告书。

课程设计的名称：

一、生死者游戏。

1. 问题描述：有n个旅客同乘一条船，因为严重超载，加上风高浪大，危险万分；因此船长告诉乘客，只有将全船一半的旅客投入大海，其余人才能幸免遇难．无奈，大家只得同意这种办法，并议定n个人围坐一圈，从1,2,3…到n进行编号。

由第一个人数起，依次报数，数到第m人，将它扔进大海中，然后再从他的下一个人数起，数到第m人，再将他扔进大海，如此循环进行，直到剩下一半人为止，问哪几个人是将被扔进大海的人。

2. 基本要求：

利用单向循环链表存储结构模拟此过程，输出生者的编号。

3. 算法思想：

该问题是由古罗马著名史学家josephus提出的问题演变而来，所以通常称之为josephus问题。

josephus问题的解决需要采用循环链表，先构造一个有n个结点的不带头结点的单循环链表，再给出报数上限值m(假设m>1).

在链表的首结点开始从1计数，计到m-1时，将下一个结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，数到m-1，再将其下一个结点从单循环链表删除，直到剩下一半结点为止。

4. 模块划分：

建立一个由头指针head指示的有n个结点的约瑟夫单循环链表initring。

生者与死者的选择：

p指向链表第一个结点，初始化i为1；

while (i<=n/2) /删除一半的结点。

输出所有生者的编号。

5. 数据结构：

程序包含以下函数：

linklist initring(int n,linklist r)：初始化一个约瑟夫环。

linklist deletedeath(int n,int k,linklist r)：寻找被扔入大海的人。

void output(linklist r)：输出所有生存者函数。

6. 源程序：

#include <>

typedef struct node

int num;

struct node *next;

node,*linklist;

linklist initring(int n,linklist r)

node *q,*p;

int i;

r=q=(node*)malloc(sizeof(node));

for(i=1;i

p->num=n;

p->next=r;

return r;

linklist deletedeath(int n,int k,linklist r)

int i,j;

node *p,*q;

p=r;for(i=1;i<=n/2;i++)删除一半结点。

//forreturn p;

*输入所有生存者函数*/

void output(linklist r)

node *p;

p=r;do

while(p!=r);

void main()

linklist r;

int n,m;

printf("总人数n,报数上限m(之间用，分隔):"

scanf("%d,%d",&n,&m);

r=initring(n,r);

output(r);

printf("被抛入大海的人有：")

r=deletedeath(n,m,r);

printf("生存下来的人有：")

output(r);

printf("");

7. 测试情况：

截图。二、二叉树的基本操作的实现。

1. 问题描述：在主程序中编写一个简单的菜单，将有关二叉树的操作整合在一起，包括递归算法和非递归算法。

2. 基本要求：建立一棵二叉树的存储结构、遍历一棵二叉树、统计二叉树叶子结点的个数、求二叉树的深度。

3. 算法思想：

建立一棵二叉树的存储结构；二叉树常用的存储结构为二叉链表形式，二叉链表由一个数据项data和两个指针项lchild、rchild组成。data用于存放结点的值，lchild/rchild 分别指向该结点的左右子树。

遍历一棵二叉树：

先序遍历：若二叉树为空树，则空操作；否则，1）访问根结点；

2）先序遍历左子树；

3）先序遍历右子树。

中序遍历：若二叉树为空树，则空操作；否则，1）中序遍历左子树；

2）访问根结点；

3）中序遍历右子树。

后序遍历：若二叉树为空树，则空操作；否则，1）后序遍历左子树；

2）后序遍历右子树；

3）访问根结点。

统计二叉树叶子结点的个数：先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。

由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增1。

求二叉树的深度：从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：

求得左、右子树深度的最大值，然后加 1 。

4. 模块划分：

先序遍历构造二叉树。

层次遍历输出二叉树。

先序、中序、后序遍历二叉树。

叶子结点统计。

二叉树的深度。

5.数据结构：

程序包含以下函数：

bitree createbitree(bitree t)/*先序遍历二叉树*/

void levelorder(bitree t)/*层次遍历输出*/

status preordertr**erse(bitree t,status(*visit)(telemtype))先序遍历二叉树。

status inordertr**erse(bitree t,status(*visit)(telemtype))中序遍历二叉树。

status postordertr**erse(bitree t,status(*visit)(telemtype))后序遍历二叉树。

int leafcount(bitree bt)//else

return t;

//createbitree

*层次遍历输出*/

void levelorder(bitree t)

bitree queue[max],b;

/*用一维数组表示队列，front和rear分别表示队守和队尾指针*/

int front,rear;

front=rear=0;

if(t)/*若数非空*/

//if/*levelorder*/

status printelement(telemtype e)

printf("%2c",e);

return ok;

status preordertr**erse(bitree t,status(*visit)(telemtype))

int i,j,k;

if(t==null)

return ok;

else//else

status inordertr**erse(bitree t,status(*visit)(telemtype))

else return ok;

//inordert**erse

status postordertr**erse(bitree t,status(*visit)(telemtype))

数据结构课程设计报告

数据结构课程设计报告

数据结构课程设计报告

数据结构课程设计报告

其他用户还读了