数据结构课程设计报告含菜单

1/1数据结构课程设计报告含菜单

算法与数据结构课程设计

报告

系（院）：计算机科学学院

专业班级：计科11005

姓名：张林峰

学号：202303784

指导老师：詹泽梅

设计时间：2023.6.11-2023.6.18

设计地点：12教机房

名目

一、课程设计目的(2)

二、设计任务及要求(2)

三、需求分析(2)

四、总体设计错误!未定义书签。

五、具体设计与实现[含代码和实现界面]..8

六、课程设计小结(15)

一．设计目的

1．能依据实际问题的详细状况，结合数据结构课程中的基本理论和基本算法，分析并正确确定数据的规律结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。

2．提高程序设计和调试力量。同学通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，快速找出程序代码中的错误并且修改。

3．初步把握软件开发过程中问题分析、系统设计、程序编码、测试等基本方法和技能。

4．训练用系统的观点和软件开发一般规范进行软件开发，培育软件工所应具备的科学的工作方法和作风。

5．培育依据选题需要选择学习书籍，查阅文献资料的自学力量。二．设计任务及要求

依据《算法与数据结构》课程的结构体系，设计一个基于DOS菜单的应用程序。要利用多级菜单实现各种功能。比如，主界面是大项，主要是学过的各章的名字诸如线性表、栈与队列、串与数组及广义表等，子菜单这些章中的节或者子节。要求全部子菜单退出到他的父菜单。编程实现时，要用到C++的面对对象的功能。

三．需求分析

菜单运用极其广泛，应用于各行各业。菜单运用起来极其便利。随着社会的进展，社会的行业消失多样化，也就需要各式

各样的菜单。这就需要设计人员非常精细的设计。

进一步了解《算法与数据结构》课程的学问结构体系，绘制整个课程的学问结构规律示意图，类似于：

依据算法与数据及结构的课程支配，可以设计如上所示的菜单。在主菜单里可以有“线性表”、“栈和队列”、“串、数组、广义表”、“树”、“图”、“查找”、“排序”。然后要在线性表里创建一个子菜单实现“创建链表”、“插入元素”、“删除元素”、“查找元素”的功能。并且可以退出这个子菜单回到上一级菜单。栈和队列创建一个子菜单，包含进制转换和括号匹配的功能。进制转换里又

分为十进制转八进制、十进制转二进制。串、数组、广义表里可以创建子菜单包含矩阵乘法、矩阵转置的功能。树里创建子菜单，有树的创建、先序遍历、中序遍历、后序遍历、树的高度、叶子数这几个选项。这些子菜单都能退出回到上一级菜单。四．总体设计

设计菜单类

依据实际使用，我们知道菜单类的主要功能就是显示菜单项与响应用户选项。所以我们可以这样设计一个菜单基类：

classCMenuBase

{

public:

CMenuBase(void);

~CMenuBase(void);

virtualvoidShowMenu=0;

virtualvoidEvent(intEvenID)=0;

protected:

CMenuBase*m_pParent;

};

依据所绘制的学问结构图，设计DOS菜单。例如

在此基础上，全部菜单类都继承这个类，以此来实现“显示”与“响应大事”的多态性。例如，主菜单类的设计为：

classCMainMenu:publicCMenuBase

{

public:

CMainMenu(void);

~CMainMenu(void);

virtualvoidShowMenu;

virtualvoidEvent(intEvenID);

};

和基类基本没有区分。其实现可以为

voidCMainMenu::ShowMenu{

coutShowMenu;

通过构造函数，将当前菜单对象作为子菜单的父菜单，以后退出子菜单时，子菜单将将显示权让给其父菜单：

#defineEXIT_SUBMENUtmp=m_pParent;\

deletepBase;\

pBase=tmp;\

pBase->ShowMenu;

这样设计，无论有多少级菜单，其编程风格都是一样的，只需管理当前的菜单交接，而无需知道它是从哪儿来的。

还定义了线性表、栈和队列、数组串和广义表、树等模板类。

线性表的类如下：

classCListMenu:publicCMenuBase

{

public:

CListMenu(CMenuBase*);

~CListMenu(void);

virtualvoidShowMenu;

virtualvoidEvent(intEvenID);

protected:

voidCreateList_L(intn);

StatusListInsert_L(inti,ElemTypee);

StatusListOut_L;

StatusListDelete_L(inti,ElemType

StatusGetElem_L(inti,ElemType

LinkListL;};

栈和队列的类如下

classCStackMenu:publicCMenuBase

{

charname[20];

public:

CStackMenu(CMenuBase*);

~CStackMenu(void){}

virtualvoidShowMenu;

virtualvoidEvent(intEvenID);

protected:

StatusInitStack;

StatusPush(SElemTypee);

StatusPop(SElemType

voidKuohao;SqStackS;};

进制转换的类定义如下

classCJinzhiMenu:publicCMenuBase

{

charname[20];

public:

CJinzhiMenu(CMenuBase*);

~CJinzhiMenu(void){}

virtualvoidShowMenu;

virtualvoidEvent(intEvenID);

protected:

voidconversion_8;

voidconversion_2;

StatusInitStack;

StatusPush(JElemTypex);

StatusPop(JElemType

JSqStacks;

};

数组的类定义如下：

classCShuzuMenu:publicCMenuBase

{

charname[200];

public:

CShuzuMenu(CMenuBase*);

~CShuzuMenu(void){}

virtualvoidShowMenu;

virtualvoidEvent(intEvenID);

protected:

StatusCreat_2(RLSMatrix

StatusPutout_2(RLSMatrix

StatusMultSMatrix(RLSMatrix

StatusFastTransposeSMatrix(TSMatrix

voidzhuanzhi;

voidChengfa;

};

树的类定义如下：

classCShuMenu:publicCMenuBase

{

charname[20];

public:

CShuMenu(CMenuBase*);

~CShuMenu(void){}

virtualvoidShowMenu;

virtualvoidEvent(intEvenID);

protected:

StatussVisit(TElemTypee);

StatussCreateBiTree(BiTree

StatussxianOrderTraverse(BiTreeT1);

StatussZhongOrderTraverse(BiTreeT1);

StatussHouOrderTraverse(BiTreeT1);

intDepth(BiTreeT1);

intcountleaf(BiTreeT1);

BiTreeT;

};

每一级的菜单函数都可以依据以上类的模板来写。便利且不简单遗漏出错。

五．具体设计与实现

线性表菜单显示如下：

线性链表菜单的设计则可能为

其实现则类似于

CListMenu::CListMenu(CMenuBase*parent){

m_pParent=parent;

}

voidCListMenu::ShowMenu{

cout>n;

list.CreateList_L(n);

cout>i;cout>e;

list.ListInsert_L(i,e);

cout>i;

list.ListDelete_L(i,e);

cout>i;

list.GetElem_L(i,e);system("pause");

break;

default:

InvalidateAction;

break;}

}

线性链表各功能详细实现代码如下：

创建链表：

voidCListMenu::CreateList_L(intn){

inti;

LinkListp;

L=(LinkList)malloc(sizeof(LNode));

L->next=NULL;

for(i=n;i>0;i--){

p=(LinkList)malloc(sizeof(LNode));

cin>>p->data;

p->next=L->next;L->next=p;}

}

界面如下：

查找元素：

StatusCListMenu::GetElem_L(inti,ElemType

LinkListp;

p=L->next;j=1;

while(p

j++;}

if(!p||j>i)returnERROR;

e=p->data;

couti)return0;

s=(LinkList)malloc(sizeof(LNode));

s->data=e;s->next=p->next;p->next=s;

return1;

}

删除元素：

StatusCListMenu::ListDelete_L(inti,ElemType

intj;

p=L;j=0;

while(p->nextj++;}

if(!(p->next)||j>i-1)return0;

q=p->next;p->next=q->next;e=q->data;free(q);

return1;

}

扫瞄全部元素：

StatusCListMenu::ListOut_L{

LinkListp;

p=L->next;

while(p)

{

coutnext;

}

return0;

}

栈和队列菜单显示界面如下：

栈和队列的菜单设计如下：

其菜单函数为：

voidCStackMenu::ShowMenu{

system("cls");//清屏

cout*pList;

voidmain

{

MAIN_EXIT=false;

pBase=newCMainMenu;

pBase->ShowMenu;

intEventID=0;

charCammandLine[255]={0};

while(MAIN_EXIT==false){

cin>>CammandLine;

if(strlen(CammandLine)==0){

coutEvent(EventID);

}

if(p