数据结构实验报告示例.doc

数据结构实验报告：编制一个Joseph约瑟夫环示例程序

◎实验题目:给定（也可自己定相关内容）

◎实验目的：给定（也可自己定相关内容）

◎实验内容：给定（也可自己定相关内容）

一、?需求分析

陈述程序设计的任务，强调程序要解决的问题是什么？?明确规定：输入的形式和输入值的范围；输出的形式；程序所能达到的功能；测试数据

1.输入的形式和输入值的范围

???本程序中，输入报数上限值m和人数上限l，密码，均限定为正整数，输入的形式为一个以“回车符”为结束标志的正整数。

2.输出的形式

???从屏幕显示出列顺序。

3.程序功能

???提供用户从键盘输入，Joseph约瑟夫环的必要数据，并显示出列顺序。

4.测试数据

（1）

输入

20

7

3172484

输出

6???1???4???7???2???3???5

二、概要设计

说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次（调用）关系。

以单向循环链表实现该结构。

1.抽象数据类型的定义为：

ADTLNode

{

???数据对象：D={ai|ai∈CharSet，i=1，2，…，n，n≥0}

???数据关系：R1={ai-1，ai|ai∈D，I=2，…，n}

基本操作：

???InitList(L)

???????操作结果：构造一个最大长度ms,内容为空的有序表L。

???ClearList(L)

???????初始条件：线性表L已经存在。

???????操作结果：将L重置为空表。

???EmptyList(L)

???????初始条件：线性表L已经存在。

???????操作结果：若L为空表返回TRUE，否则返回FALSE。

???ListLength(L)

???????????初始条件：线性表L已经存在。

???????操作结果：返回L中数据元素个数。

???GetElem(L,pos,e)

???????初始条件：线性表L已经存在，1≤i≤ListLength(L)。

???????操作结果：用e返回L中第i个数据元素的值。

???LocateElem(L,e)

???????初始条件：线性表L已经存在。

???????操作结果：返回L中第1个与e相同的元素的位序。若不存在返回0。

???ListInsert(L,i,e)

???????初始条件：线性表L已经存在。

???????操作结果：在L中的第i个元素的位置之前插入新元素e,L的长度加1。

ListDelete(L,pos,e)

???????初始条件：线性表L已经存在，1≤i≤ListLength(L)。

???????操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。

???ListTraverse(L)

???????初始条件：线性表L已经存在。

???????操作结果：依次对L的每个数据元素进行访问。

}ADTSqList

本程序包含以下模块：

（1）主程序模块：

voidmain()

{

???初始化；

???输入数据；

???执行功能；

显示结果；

}

（2）各功能模块——实现单循环链表表的各项功能。

各模块的调用关系：

主程序

??↓

各功能模块

三、详细设计

?实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和其他模块也都需要写出伪码算法；画出函数的调用关系。

设计思路：写出存储结构，主要算法的基本思想。?

设计表示：每个操作及模块的伪码算法。列出每个过程或函数所调用和被调用的过程或函数，也可以通过调用关系（层次）图表达。?

实现注释：各项功能的实现程度、在完成基本要求的基础上还实现了什么功能。?

#includestdio.h

#includestdlib.h

#includestring.h

#defineTRUE1

#defineFALSE0

#defineOK1

#defineERROR0

#defineINFEASIBLE-1

#defineOVERFLOW-2

typedefintStatus;

typedefintElemType;

/*定义类型*/

typedefstructLNode

{

???ElemTypedata;

???structLNode*next;

}LNode,*LinkList;

/*1初始化，置表头指针为空*/

voidInitList(LinkListHL)

{

???HL=(LinkList)malloc(sizeof(LNode));

???HL-next=HL;

}

/