数据结构实训报告样本

（数据结构实训报告）

一、实训目的. 1

二、实训题目. 2

三、实训步骤. 2

四、实训内容. 3

五、实训心得. 19

六、参考文献. 19

一、实训目的

通过实训，对所学数据结构和程序设计的基本知识和基本理论有更进一步的了解和认识，将理论和实际相结合，能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来。主要是培养学生综合利用C语言进行程序设计的能力和创新能力以及综合解决问题的能力。运用算法分析与程序设计的一般方法进行实际项目的开发。本次实训尽量选取与实际结合紧密或学生比较感兴趣的项目，本次实训学生需要具备熟练的程序设计基础、数据结构和计算机应用基础知识，具备程序编写、调试的基本能力，具有一定的文字表达和报告撰写能力，具备办公软件使用能力。

通过实训，考查语言基本概述掌握是否牢固，并考查与后续课程较为密切的结构体，链表，文件的运用熟练程度，加强对基本概念的理解和复习，最重要的是了解基本软件的设计步骤，还有对软件调试的掌握。能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。

二、实训题目

（一）单项题目

1、二叉树遍历

【问题描述】建立二叉树，实现二叉树的先序遍历、中序、后序和层序遍历（用递归或非递归的方法都可以）。

【要求】编写菜单程序。能够输入二叉树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立二叉树存储结构的输入函数、输出先序遍历序列的函数；输出中序遍历序列的函数；输出后序遍历序列的函数；输出层序遍历序列的函数。

（二）综合题目

1、图书管理系统

【问题描述】建立一个图书信息文件，包括书号（num）、书名（bookname）、作者（name）、出版社（publish）、价格（price）等。

【要求】建立一个图书信息文件，包括书号（num）、书名（bookname）、作者（name）、出版社（publish）、价格（price）等。

三、实训步骤

1、问题分析

正确理解问题，分析问题究竟“做什么”，分析问题已知的信息及其作用，分析在解决中对信息处理的规则、要求、限制条件，分析问题解决后应该输出什么样的结果（输出形式、格式、内容）。并分析得出判定结果是否正确的标准。

2、设计分析

得出解决问题的思路、主要流程、采用的数据结构类型的说明、主要算法的思想。

3、设计方案

采用的数据结构类型的定义、主要算法的描述及说明。

4、详细设计

根据问题要求和已得到的算法编写程序。

5、调试程序

发现程序中存在的语法错误和一些逻辑错误，并修改，使程序能够运行。

6、运行程序

选择若干具有代表性的输入数据（包括合理数据和不合理数据），进行测试，尽量使程序的各语句和分支都被检查到，以便发现程序中的错误和漏洞，以便改进算法和程序。

7、使用说明

包括程序源代码、算法（程序）流程图、开发过程中各阶段的有关记录、算法的正确性证明、程序的测试结果、对输入输出要求及格式的详细描述。

四、实训内容

（一）个人题目

1、二叉树遍历

【问题描述】建立二叉树，实现二叉树的先序遍历、中序、后序和层序遍历（用递归或非递归的方法都可以）。

【设计分析】1、总体设计(基本概念)

树的概念

树（Tree）是n（n>=0）个结点的有限集。在任意一棵非空树中：

1) 有且仅有一个特定的称为根的结点；

2) 当n>1时，其余结点可分为m（m>0）个互不相交的有限集T1，T2......Tm，其中每一个集合又是一棵树，并且称为根的子树（SubTree）。

【例】如图1所示：

图1

图1是有8个结点的树，其中A是根，其余结点分成2个互不相交的子集：T1={B，D}，T2={C，E，F，G，H}；T1和T2都是根A的子树，且本身也是一棵树。

【设计方案】1．创建二叉树（可从键盘输入各结点的值）

2．按某种方式对二叉树进行遍历

3．树型结构是一种非常重要的非线性结构。树在客观世界是广泛存在的，在计算

机领域里也得到了广泛的应用。在编译程序里，也可用树来表示源程序的语法结构，在数据库系统中，数形结构也是信息的重要组织形式。

4．节点的有限集合（N大于等于0）。在一棵非空数里：（1）、有且仅有

一个特定的根节点；（2）、当N大于1时，其余结点可分为M（M大于0）个互不相交的子集，其中每一个集合又是一棵树，并且称为根的子树。树的定义是以递归形式给出的。

5．二叉树是另一种树形结构。它的特点是每个结点最多有两棵子树，并且，二叉

树的子树有左右之分，其次序不能颠倒。

从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：

（1）访问结点本身(N)，

（2）遍历该结点的左子树(L)，

（3）遍历该结点的右子树(R)。

以上三种操作有六种执行次序：

　NLR、LNR、LRN、NRL、RNL、RLN。

【详细设计】本程序源代码如下：

/*源程序*/

/* Note:Your choice is C IDE */

#include "stdio.h"

#include <iostream>

#include <stdio.h>

#include <stdlib.h>

#define Max 20

typedef char DataType;

#define MaxStackSize 50

using namespace std;

typedef struct Node

{ DataType data;

struct Node *leftChild;

struct Node *rightChild;

}BiTreeNode;

typedef BiTreeNode* DataType2;

typedef struct

{ DataType2 stack[MaxStackSize];

int top;

} SeqStack;

typedef struct

{ DataType2 quene[MaxStackSize];

int front;

int rear;

}Quene;

void StackInitiate(SeqStack *S)

{ S->top = 0; }

int StackNotEmpty(SeqStack S)

{ if (S.top <= 0) return 0;

else return 1;

}

int StackPush(SeqStack *S, DataType2 x)

{ if (S->top >= MaxStackSize)

{ printf("堆栈已满无法插入! \n");

return 0;

}

else

{ S->stack[S->top] = x;

S->top ++;

return 1;

}

int StackPop(SeqStack *S, DataType2 *d)

{ if (S->top <= 0)

{ printf("堆栈已空无数据元素出栈! \n");

return 0;

}

else

{ S->top --;

*d = S->stack[S->top];

return 1;

}

int StackTop(SeqStack S, DataType2 *d)

{ if (S.top <= 0)

{ printf("堆栈已空! \n");

return 0;

}

else

{ *d = S.stack[S.top - 1];

return 1;

}

typedef struct node{

char data;

struct node *lchild;

struct node *rchild;

}BTNode;

typedef BTNode *BTree;

int NodeNum,leaf;

BTree CreatBTree(void)

{BTree T;

char ch;

if((ch=getchar())=='*')

return(NULL);

else{

T=(BTNode *)malloc(sizeof(BTNode));

T->data=ch;

T->lchild=CreatBTree();

T->rchild=CreatBTree();

return(T);

}

void Preorder(BTree T)

{ if(T){

printf("%c",T->data);

Preorder(T->lchild);

Preorder(T->rchild);

}

void Inorder(BTree T)

{ if(T)

{

Inorder(T->lchild);

printf("%c",T->data);

Inorder(T->rchild);

}

void Postorder(BTree T)

{ if(T)

{

Postorder(T->lchild);

Postorder(T->rchild);

printf("%c",T->data);

}

int TreeDepth(BTree T)

{ int hl,hr,max;

if(T)

{

hl=TreeDepth(T->lchild);

hr=TreeDepth(T->rchild);

max=hl>hr?hl:hr;

NodeNum=NodeNum+1;

if(hl==0&&hr==0)

leaf=leaf+1;

return(max+1);

}

else return(0);

}

void Levelorder(BTree T)

{ int front=0,rear=1;

BTNode *cq[Max],*p;

cq[1]=T;

while(front!=rear)

{

front=(front+1)%NodeNum;

p=cq[front];

printf("%c",p->data);

if(p->lchild!=NULL)

{

rear=(rear+1)%NodeNum;

cq[front]=p->lchild;

cq[rear]=p->lchild;

}

if(p->rchild!=NULL)

{

rear=(rear+1)%NodeNum;

cq[front]=p->rchild;

cq[rear]=p->rchild;

}

void main()

{

BTree root;

int i,depth;

printf("\n");

printf("创建二叉树，请输入完全二叉树的先序序列，用*代表虚结点:");

root=CreatBTree();//返回根结点

do{

printf("\t1:先序遍历\n");

printf("\t2:中序遍历\n");

printf("\t3:后序遍历\n");

printf("\t4:深度、结点数、叶子数\n");

printf("\t5:层次遍历\n");

printf("备注：选择层次遍历之前，需要先选择4，求出该树的结点数。");

printf("\t0:Exit\n");

scanf("%d",&i);//输入菜单序号

switch(i)

{

case 1:printf("先序遍历结果为:");

Preorder(root);

break;

case 2:printf("中序遍历结果为:");

Inorder(root);

break;

case 3:printf("后序遍历结果为:");

Postorder(root);

break;

case 4:depth=TreeDepth(root);

printf("深度=%d 结点数=%d",depth,NodeNum);

printf("叶子数=%d",leaf);

break;

case 5:printf("层次遍历为:");

Levelorder(root);

break;

default:exit(1);

}

printf("\n");

}

while(i!=0);

}

【使用说明】本程序在turboc 2.0环境下运行，迷宫大小为20×20，需要修改迷宫大小时，可以修改程序中N值的大小。迷宫图由系统自动随机生成，每次生成的迷宫图是不同的。按enter健显示最终搜索结果。按Q健退出程序。

【运行调试】

图（1）二叉树遍历主界面

图（2）

（二）综合题目

1、图书管理系统

【问题描述】建立一个图书信息文件，包括书号（num）、书名（bookname）、作者（name）、出版社（publish）、价格（price）等。

【要求】编写菜单程序，功能包括：建立图书信息、插入记录，删除记录、修改记录、按照书号或书名查询记录、显示记录、根据图书价格进行排序。定义图书信息结构体名称为book。书号（num）、书名（bookname）、作者（name）、出版社（publish）均为字符型数组。价格（price）为单精度型数据。

【设计分析】系统目标分析

每个学校都有图书馆，最初由于图书数量和种类较少，人工手动管理比较方便和灵活。随着社会的发展，图书的数量和种类越来越多，人工手动管理会降低工作的效率，希望建立一个图书馆图书信息管理系统，是为了解决了人工手动管理图书信息在实践的问题，从而达到系统化、规范化、标准化的水平。该系统的建立不但给管理者带来了方便，也节省了工作时间从而提高了工作效率。
在构造系统时，首先从需求出发构造数据库表，然后再由数据库表结合需求划分系统功能模块。这样，就把一个大的系统分解成了几个小系统。这里把系统的层次划分为了三个部分：一个自由态：即面向任何用户的界面，提供登录功能，以便不同身份的用户登录子系统；一个是一般用户态：即图书有服务子系统；还有一个是管理员界面：提供图书的管理和维护功能。对于不同子系统之间的功换，采用了登录功能和用户注销功能。系统划分了子系统后，下一步的工作是继续划分子系统的小模块。先考虑在进入子系统时应该做什么，进入系统之后又应该做什么，提供那些服务等。例如，对于图书信息服务子系统，在用户进入时首先得调用相关数据库表，找出用户的图书借阅情况；进入系统后，子系统得提供图书查询、图书借阅和还书功能。另外，针对本系统的特殊情况，同时也考虑系统的可移植性，在系统中增加了数据库路径的维护部分。最后，考虑到系统的安全性，还在系统中特别增加了“加密界面”的功能。

【设计方案】本数据库管理系统主要由图书检索、图书管理、数据维护、图书统计、打印输出、系统维护六大模块组成, 如图1 所示。各模块功能如下：

1、主控模块主控模块的功能是控制各个分支模块,它是实现各模块功能的总控制台

2、图书检索模块是图书管理系统的重要模块之一,是读者快速查询图书的途径本模块的功能是按书名、书号、作者、出版社、图书分类查询

数据维护模块是由图书管理员控制的模块,它由增加、修改和删除读者,增加、修改删除图书,浏览修改读者、浏览修改图书等程序组成。在软件设计时考虑到读者编号、书名、书号是唯一的,因此,在修改读者或图书中,读者记录或图书记录一经登记“读者编号”和“姓名”便不能修改,在删除读者或图书时只要读者有借出图书未还或库存图书原有数量与现有库存量不符便不能删除。　

5、数据统计模块由读者统计、图书统计、借出图书分类统计、到期未归还图书读者统计几部分组成

我们小组的信息系统开发课程设计题目是：图书管理系统开发。系统开发的总的设计目标是实现图书管理的系统化、规范化和自动化，实现对图书资料的集中统一的管理。

本系统主要实现对图书馆信息的管理，主要功能为管理有关读者，书籍，借阅和管理者的信息等。本系统结构分为读者信息管理模块，书籍信息管理模块，借阅信息管理模块，管理者信息管理模块。读者信息管理部分有两方面的功能，可以浏览读者的信息，可以对读者信息进行维护。书籍信息管理可以浏览书籍的信息，可以对书籍信息进行维护。借阅信息管理可以显示当前数据库中书籍借阅情况，可以对借阅信息进行维护。管理者信息管理可以显示数据库中管理者的情况，可以对管理者信息进行维护。可见，本系统并不复杂，主要解决的问题是利用关键字对数据库进行查询。

【详细设计】本程序源代码如下：

/*源程序*/

/* Note:Your choice is C IDE */

#include<stdio.h>

#include<math.h>

#include<string.h>

#include<stdlib.h>

struct books_list

{

char author[20]; /*作者名*/

char bookname[20]; /*书名*/

char publisher[20]; /*出版单位*/

char pbtime[15]; /*出版时间*/

char loginnum[10]; /*登陆号*/

float price; /*价格*/

char classfy[10]; /*分类号*/

struct books_list * next; /*链表的指针域*/

};

struct books_list * Create_Books_Doc(); /*新建链表*/

void InsertDoc(struct books_list * head); /*插入*/

void DeleteDoc(struct books_list * head , int num);/*删除*/

void Print_Book_Doc(struct books_list * head);/*浏览*/

void search_book(struct books_list * head); /*查询*/

void info_change(struct books_list * head);/*修改*/

void save(struct books_list * head);/*保存数据至文件*/

/*浏览操作*/

void Print_Book_Doc(struct books_list * head)

{

struct books_list * p;

if(head==NULL || head->next==NULL) /*判断数据库是否为空*/

{

printf("\n ━━━━ 没有图书记录! ━━━━\n\n");

return;

}

p=head;

printf("┏━━━┳━━━┳━━━┳━━━┳━━━━┳━━━┳━━━┓\n");

printf("┃登录号┃书名 ┃ 作者 ┃出版单位┃出版时间┃分类号┃价格┃\n");

printf("┣━━━╋━━━╋━━━╋━━━╋━━━━╋━━━╋━━━┫\n");

/*指针从头节点开始移动，遍历至尾结点，依次输出图书信息*/

while(p->next!= NULL)

{

p=p->next;

printf("┃%-6.6s┃%-10.10s┃%-10.10s┃%-10.10s┃%-12.12s┃%-6.6s┃%.2f ┃\n",p->loginnum,p->bookname,p->author,p->publisher,p->pbtime,p->classfy,p->price); /*循环输出表格*/

}

printf("┗━━━┻━━━┻━━━┻━━━┻━━━━┻━━━┻━━━┛\n");

printf("\n");

}

/*删除操作*/

void DeleteDoc(struct books_list * head)

{

struct books_list *s,*p; /*s为中间变量，p为遍历时使用的指针*/

char temp[20];

int panduan; /*此变量用于判断是否找到了书目*/

panduan=0;

p=s=head;

printf(" [请输入您要删除的书名]:");

scanf("%s",temp);

/*遍历到尾结点*/

while(p!= NULL)

{

if(strcmp(p->bookname,temp)==0)

{

panduan++;

break;

}

p=p->next;

}

if(panduan==1)

{

for(;s->next!=p;) /*找到所需删除卡号结点的上一个结点*/

{

s=s->next;

}

s->next=p->next; /*将后一节点地址赋值给前一节点的指针域*/

free(p);

printf("\n ━━━━ 删除成功! ━━━━\n");

}

else /*未找到相应书目*/

{

printf(" 您输入的书目不存在，请确认后输入!\n");

}

return;

}

int main(void)

{

struct books_list * head;

char choice;

head=NULL;

for(;;) /*实现反复输入选择*/

{

printf(" ┏━━━━━━━━━━━━━━━━━━━┏━┓\n");

printf(" ┃ ┃ socat 图书管理系统 ┃ ┃\n");

printf(" ┃ ┗━━━━━━━━━━━━━━━━━━━┛ ┃\n");

printf(" ┃ ●[1]图书信息录入 ┃\n");

printf(" ┃ ┃\n");

printf(" ┃ ●[2]图书信息浏览 ┃\n");

printf(" ┃ ┃\n");

printf(" ┃ ●[3]图书信息查询 ┃\n");

printf(" ┃ ┃\n");

printf(" ┃ ●[4]图书信息修改 ┃\n");

printf(" ┃ ┃\n");

printf(" ┃ ●[5]图书信息删除 ┃\n");

printf(" ┃ ┃\n");

printf(" ┃ ●[6]退出系统 ┃\n");

printf(" ┗━━━━━━━━━━━━━━━━━━━━━━━┛\n");

printf(" 请选择:");

fflush(stdin);

scanf("%c",&choice);

if(choice=='1')

{

if(head==NULL)

{

head=Create_Books_Doc();

}

InsertDoc(head);

}

else if(choice=='2')

{

Print_Book_Doc(head);

}

else if(choice=='3')

{

search_book(head);

}

else if(choice=='4')

{

info_change(head);

}

else if(choice=='5')

{

struct books_list *s,*p; /*s为中间变量，p为遍历时使用的指针*/

char temp[20];

int panduan; /*此变量用于判断是否找到了书目*/

panduan=0;

p=s=head;

printf(" [请输入您要删除的书名]:");

scanf("%s",temp);

/*遍历到尾结点*/

while(p!= NULL)

{

if(strcmp(p->bookname,temp)==0)

{

panduan++;

break;

}

p=p->next;

}

if(panduan==1)

{

for(;s->next!=p;) /*找到所需删除卡号结点的上一个结点*/

{

s=s->next;

}

s->next=p->next; /*将后一节点地址赋值给前一节点的指针域*/

free(p);

printf("\n ━━━━ 删除成功! ━━━━\n");

}

else /*未找到相应书目*/

{

printf(" 您输入的书目不存在，请确认后输入!\n");

}

return;

}

else if(choice=='6')

{

printf("\n");

printf(" ━━━━━━━━ 感谢使用图书管理系统 ━━━━━━━━\n");

break;

}

else

{

printf(" ━━━━ 输入错误，请重新输入！━━━━");

break;

}

【运行调试】

图（3）图书管理系统主界面

图（4）图书信息浏览

五、实训心得

六、参考文献

相关推荐