数据结构实验报告 实验五（精选8篇）

数据结构实验报告 实验五 篇1

实现哈夫曼编码的生成算法。

二.实验目的：

1、使学生熟练掌握哈夫曼树的生成算法。

2、熟练掌握哈夫曼编码的方法。

三.问题描述：

已知n个字符在原文中出现的频率，求它们的哈夫曼编码。

1、读入n个字符，以及字符的权值，试建立一棵Huffman树。

2、根据生成的Huffman树，求每个字符的Huffman编码。并对给定的待编码字符序列进行编码，并输出。

四.问题的实现

(1)郝夫曼树的存储表示

typedef struct{

unsigned int weight;

unsigned int parent，lchild，rchild;

}HTNode，*HuffmanTree; //动态分配数组存储郝夫曼树

郝夫曼编码的存储表示

typedef char* *HuffmanCode;//动态分配数组存储郝夫曼编码

(2)主要的实现思路：

a.首先定义郝夫曼树的存储形式，这里使用了数组

b.用select()遍历n个字符，找出权值最小的两个

c.构造郝夫曼树HT，并求出n个字符的郝夫曼编码HC

总结

1.基本上没有什么太大的问题，在调用select()这个函数时，想把权值最小的两个结点的序号带回HuffmanCoding()，所以把那2个序号设置成了引用。

2.在编程过程中，在什么时候分配内存，什么时候初始化花的时间比较长

3.最后基本上实现后，发现结果仍然存在问题，经过分步调试，发现了特别低级的输入错误。把HT[i].weight=HT[s1].weight+HT[s2].weight;中的s2写成了i

附：

//动态分配数组存储郝夫曼树

typedef struct{

int weight; //字符的权值

int parent，lchild，rchild;

}HTNode，*HuffmanTree;

//动态分配数组存储郝夫曼编码

typedef char* *HuffmanCode;

//选择n个(这里是k=n)节点中权值最小的两个结点

void Select(HuffmanTree &HT，int k，int &s1，int &s2)

{ int i;

i=1;

while(i<=k && HT[i].parent!=0)i++;

//下面选出权值最小的结点，用s1指向其序号

s1=i;

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

{

if(HT[i].parent==0&&HT[i].weight

}

//下面选出权值次小的结点，用s2指向其序号

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

{

if(HT[i].parent==0&&i!=s1)break;

}

s2=i;

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

{

if(HT[i].parent==0&&i!=s1&&HT[i].weight

}

}

//构造Huffman树，求出n个字符的编码

void HuffmanCoding(HuffmanTree &HT，HuffmanCode &HC，int *w，int n)

{

int m，c，f，s1，s2，i，start;

char *cd;

if(n<=1)return;

m=2*n-1; //n个叶子n-1个结点

HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //0号单元未用，预分配m+1个单元

HuffmanTree p=HT+1;

w++; //w的号单元也没有值，所以从号单元开始

for(i=1;i<=n;i++，p++，w++)

{

p->weight=*w;

p->parent=p->rchild=p->lchild=0;

}

for(;i<=m;++i，++p)

{

p->weight=p->parent=p->rchild=p->lchild=0;

}

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

{

Select(HT，i-1，s1，s2); //选出当前权值最小的

HT[s1].parent=i;

HT[s2].parent=i;

HT[i].lchild=s1;

HT[i].rchild=s2;

HT[i].weight=HT[s1].weight+HT[s2].weight;

}

//从叶子到根逆向求每个字符的郝夫曼编码

HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); //分配n个字符编码的头指针变量

cd=(char*)malloc(n*sizeof(char)); //分配求编码的工作空间

cd[n-1]="";//编码结束符

for(i=1;i<=n;i++) //逐个字符求郝夫曼编码

{

start=n-1; //编码结束符位置

for(c=i，f=HT[i].parent;f!=0;c=f，f=HT[f].parent) //从叶子到根逆向求编码

{

if(HT[f].lchild==c)cd[--start]="0";

else

cd[--start]="1";

}

HC[i]=(char*)malloc((n-start)*sizeof(char)); //为第i个字符编码分配空间

strcpy(HC[i]，&cd[start]);//从cd复制编码到HC

}

free(cd); //释放工作空间

}

void main()

{ int n，i;

int* w; //记录权值

char* ch; //记录字符

HuffmanTree HT;

HuffmanCode HC;

cout<<"请输入待编码的字符个数n=";

cin>>n;

w=(int*)malloc((n+1)*sizeof(int)); //记录权值，号单元未用

ch=(char*)malloc((n+1)*sizeof(char));//记录字符，号单元未用

cout<<"依次输入待编码的字符data及其权值weight"<

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

{

cout<<"data["<

}

数据结构实验报告 实验五 篇2

问题描述：

四则运算表达式求值，将四则运算表达式用中缀表达式，然后转换为后缀表达式，并计算结果。

一、 需求分析：

1、本程序是利用二叉树后序遍历来实现表达式的转换，同时可以使用实验三的结果来求解后缀表达式的值。

2、输入输出格式：

输入格式：在字符界面上输入一个中缀表达式，回车表示结束。

请输入表达式：

输入一个中缀表达式

输出格式：如果该中缀表达式正确，那么在字符界面上输出其后缀表达

式，其中后缀表达式中两相邻操作数之间利用空格隔开;如

果不正确，在字符界面上输出表达式错误提示。

逆波兰表达式为：

3、测试用例

输入：21+23*(12-6)

输出：21 23 12 6 -*+ 输出逆波兰表达式 运算结果为：输出运算后的结果

二、概要设计 ：

抽象数据类型

二叉树类BiTree

算法的基本思想

根据题目要求，利用栈计算，和二叉树存储，来计算表达式

该算法的基本思想是：

先利用栈进行计算，然后用二叉树进行存储，和实验三算法一样来计算逆波兰表达式的值

程序的流程

程序由三个模块组成：

(1) 输入模块：输入一个运算式

(2) 计算模块：利用栈进行表达式的计算，二叉树来存储。 (3 ) 输出模块：屏幕上显示出后缀表达式和运算结果。

三、详细设计

物理数据类型

程序含有两个类，其中栈不再赘述，另一个类为二叉树class BiTree包含私有成员struct BiTreeNode，根节点BiTreeNode *T;索引index; int number_of_point 优先级比较函数 compare(char a，char b);生成树的函数void InorderCreate(BiTreeNode *&T，char str[30][10]，int start，int end);判断数字函数bool IsNumber(char a);求值函数double Operate(BiTreeNode *T);还有显示后缀表达式的函数void display(BiTreeNode *T) ;而公有成员函数则是对私有函数的重载，为方便使用，因为函数中普遍使用了递归的算法。

算法的时空分析

此算法利用栈和二叉树来实现，故次算法的的时间复杂度为(N)。

输入和输出的格式

输入格式：请输入表达式：

输入一个中缀表达式 //回车

输出格式：逆波兰表达式为：

输出逆波兰表达式

运算结果为：输出运算后的结果

四、调试分析

略。

五、测试结果

本实验的测试结果截图如下：

六、用户使用说明(可选)

1、本程序的运行环境为windows 操作系统，执行文件为 biaodashi.exe 2 、运行程序时

提示输入表达式

本程序可以将中缀表达式转换为后缀表达式后在计算出运算式的结果。 提示：请输入表达式：

输出

提示：逆波兰表达式为：

运算结果：

七、实验心得(可选)

本次实验过程比较复杂，由于书上的知识掌握的还不是很牢靠，所以现在实验做起来有点儿吃力。本实验主要是通过与同学的讨论和课后查阅资料来完成的，虽然有些地方还不是很懂，但基本上能完成此次实验的内容。而且通过本次实验，加深了对二叉树算法的了解。

附录(实验代码)：

#include

#include

#include

#include

#include

#include

#define STACK_INIT_SIZE 100

#define DATA_SIZE 10

#define STACKINCREMENT 10

#define OK 1

#define TRUE 1

#define FALSE 0

#define ERROR 0

#define OVERFLOW -2

using namespace std;

typedef float SElemtype;

typedef int Status;

typedef char * TElemType;

typedef struct BiTNode {

TElemType data;

int len; //data字符串中字符的个数

struct BiTNode * lchild， * rchild;

}BiTNode， *BiTree;

typedef struct

{

SElemtype *base;

SElemtype *top;

int stacksize;

} SqStack;

Status IsDigital(char ch)

{ if(ch>="0"&&ch<="9")

{return 1; //是数字字母

}

return 0; //不是数字字母

}

int CrtNode(stack &PTR， char *c)

{

BiTNode * T;

int i=0;

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

T->data = (char *)malloc(DATA_SIZE*sizeof(char));

while(IsDigital(c[i]))

{T->data [i] = c[i];

i++; }

T->len = i;

T->lchild = T->rchild = NULL;

PTR.push (T);

return i;

}

void CrtSubTree(stack &PTR， char c)

{BiTNode * T;

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

T->data = (char *)malloc(DATA_SIZE*sizeof(char));

T->data [0] = c;

T->len = 1;

T->rchild = PTR.top(); //先右子树，否则运算次序反了

PTR.pop ();

T->lchild = PTR.top();

PTR.pop ();

PTR.push (T);

}

char symbol[5][5]={{">"， ">"， "<"， "<"， ">"}， //符号优先级

{">"， ">"， "<"， "<"， ">"}，

{">"， ">"， ">"， ">"， ">"}，

{">"， ">"， ">"， ">"， ">"}，

{"<"， "<"， "<"， "<"， "="}};

int sym2num(char s) //返回符号对应优先级矩阵位置 { switch(s)

{

case "+": return 0; break;

case "-": return 1; break;

case "*": return 2; break;

case "/": return 3; break;

case "#": return 4; break;

}

}

char Precede(char a， char b) //返回符号优先级

{return(symbol[sym2num(a)][sym2num(b)]);}

void CrtExptree(BiTree &T， char exp[])

{ //根据字符串exp的内容构建表达式树T

stack PTR;//存放表达式树中的节点指针

stack OPTR;//存放操作符

char op;

int i=0;

OPTR.push ("#");

op = OPTR.top();

while( !((exp[i]=="#") && (OPTR.top()=="#")) ) //与

{

if (IsDigital(exp[i]))

{//建立叶子节点并入栈 PTR

i+=CrtNode(PTR， &exp[i]);

}

else if (exp[i] == " ")

i++;

else{

switch (exp[i])

{

case "(": {

OPTR.push (exp[i]);

i++;

break;}

case ")": {

op = OPTR.top (); OPTR.pop ();

while(op!="("){

CrtSubTree(PTR， op);

op = OPTR.top (); OPTR.pop ();

}//end while

数据结构实验报告 实验五 篇3

学生姓名：谢先斌

系 别：计算机与通信工程学院

专 业：计算机科学与技术

班 级：1班

学 号：541007010144

指导教师：卢冰 李晔

年 6 月 21 日

郑州轻工业学院

课 程 设 计 任 务 书

题目 模拟计算器程序

专业、班级 计算机科学与技术10-01班 学号 541007010144 姓名 谢先斌

主要内容：

设计一个模拟计算器的程序，要求能对包含加、减、乘、除、括号运算符及SQR和ABS函数的任意整型表达式进行求解。

基本要求：

要检查有关运算的条件，并对错误的条件产生报警。

主要参考资料：

[1] 严蔚敏 吴伟民 编著《数据结构(C语言版)》 清华大学出版社 第44页 3.1 栈、第52页3.2.5表达式求值

完 成 期 限： xxxx年6月21日

指导教师签名：

课程负责人签名：

xxxx年 6月 21 日

一、 设计题目

模拟计算器的程序

设计一个模拟计算器的程序，要求能对包含加、减、乘、除、括号运算符及SQR和ABS函数的任意整型表达式进行求解。

设计要求：要检查有关运算的条件，并对错误的条件产生报警。

二、 算法设计的思想

本程序设计主要是应用了栈，利用栈的“先进后出”原理，建立了两个栈，分别为运算符栈pOStack和运算数栈pDStack。算法的基本思想(参考课本p53页)是：

(1) 首先置操作数栈为pDStack空栈，表达式起始符为“=”，位运算符栈的栈底元素;

(2) 依次读入表达式中的每个字符，若是操作数则进入pDStack栈，若是运算符则和pOStack栈的栈定运算符比较优先权后作相应操作，直到整个表达式求值完毕(即pOStack栈的栈定元素和当前读入的字符均为“=” )。

三、 算法的流程图

本程序的流程如下附图1所示：

附图1 程序流程图

四、 算法设计分析

首先创建了两个栈：

typedef struct OPStack //定义运算符栈

{

char opStack[MAX_OPERATOR_NUM];

int top;

}OPStack， *pOPStack;

typedef struct DATAStack //定义运算数栈

{

double stack[MAX_DATA_NUM];

int top;

}DATAStack， *pDATAStack;

来分别存放运算符和运算数。在两个结构体中均有一个top数据域，当top=-1时，表示该站为空栈。

定义一个Evaluateexpression_r()函数来完成函数运算的主要功能：读入表达式，并计算结果。以下是对该函数的分析：

当一次运算开始时，分别调用InitpOPStack(pOPStack &pOStack)函数和InitpDATAStack(pDATAStack &pDStack)函数分别对运算符栈和运算数栈进行初始化。调用PushOPStack(pOStack， "=")函数来完成运算符栈栈低元素的设置。

通过PushOPStack(pOPStack &pOStack， char ch)函数、

PopOPStack(pOPStack &pOStack， char &ch)函数、

PushDATAStack(pDATAStack &pDStack， double d)函数和PopDATAStack(pDATAStack &pDStack， double &d)函数来分别完成运算符和运输数的进出栈操作。getToppOPStack(pOPStack &pOStack)函数和getToppDATAStack(pDATAStack &pDStack) 函数主要是进行得到栈定元素的作用，特别是在对运算符栈优先级的比较中十分重要，其中还会调用IsOP(char &ch) 函数来区分读入的是运算符还是运算数。

ChangeChar(char &c)函数当每次读入一个字符是都会调用一次，主要的作用就是完成不用区分A、S的大小的功能。

Precede(char op1， char op2)函数主要是通过一个二维字符串数组来存放9种运算符的优先级比较的结果，每当读到一个运算符后就进行与运算符栈顶元素比较，通过返回的“<、>、=”结果来进行下一步的操作："<"表示栈顶元素优先级低，运算符进栈;"="表示脱括号并接受下一个字符;">"表示运算符和运算数各退栈一次并调用Operate(double a， char theta， double b)函数(主要是对出栈的运算符和运算数进行计算)，最后将运算结果压入运算数栈pDStack。

当操作结束时运算数栈的栈顶元素就是计算结果，分别调用ClearpOPStack(pOStack)函数清空运算符栈、ClearpDATAStack(pDStack)函数清空运算数栈以待下一次继续进行相关操作。

print_user()函数和exit_E()函数开始和结束时个调用一次，分别完成欢迎界面和退出界面的布置。main()是本程序的主函数，主要通过while语句和switch语句来完成本程序的运行，当输入Y(y)时调用Evaluateexpression_r()函数完成计算，当输入N(n)时，调用exit_E()函数退出本程序的运行。

本程序还考虑到各种异常的处理，如运算时除数为0、被开方数为0等情况的出现，最终的处理是直接退出程序的运行。

五、 运行结果分析

1. 程序开始界面，如附图2：

附图2 开始界面

2.如下附图3，附图4分别是选择进入和退出程序界面：

附图3(在以下界面输入计算式即可运行出计算结果如附图5)

附图4 退出界面

附图5 运行界面

2. 对异常的处理

a) 对异常1除数为0，如输入“1+2/0=”程序将直接退出，如附图6：

附图6 异常1除数为0

b) 对异常2被开方数为负数，如输入“3+S(-9)=”程序将直接退出，如附图7：

附图7 异常2被开方数为负数

3.以下是对各种简单运算的运行结果，如附图8：

附图8 简单运算

3. 综合运算：如式子“1/2+A(7-8)-S(9*8)=”运行结果如附图9

附图9 综合运算

六、 收获及体会

本程序以C语言的栈的相关知识为基础，通过控制两个栈(运算数栈和运算符栈)的进出的栈操作，来实现对包含加、减、乘、除、括号运算符及SQRT和ABS函数的任意整型表达式的求解运算。

从程序的编写来看，感觉这次自己真的学到了好多，特别是对程序的开发流程。从最初的选定程序，到最终的程序运行成功，让我感到如果是仅仅掌握课本上的知识是远远不能够很好的应用到实际的编程中去的。在这个过程中还需要我们更多的去考虑到实际条件的种种限制和约束。

我在写本程序的过程中也遇到了很多的问题，当然本程序的核心问题就是对两个栈的压出栈操作，需要做优先级判断，并要考虑什么时候进栈，什么时候出栈等操作。我采用了课本上第52-54页讲的通过一个二维字符串数组来控制比较“+-*、()AS=”共9个运算符的优先级控制。对异常，如除数为0、被开方数小于0等异常也进行了精心的处理。对操作过程中要用到的Y、N、A、S等字符也进行了改进，最终本程序可以不区分大小写就完成相关操作。

总之，经过本次专业课程设计，让我掌握了开发应用软件的基本流程，运用所学编程技能的基本技巧，也让我初步了解了软件设计的基本方法，提高进行工程设计的基本技能及分析、解决实际问题的能力，为以后毕业设计和工程实践等打下良好的基础。相信通过这次的课程设计，我对所学的《数据结构(C语言版)》和各种编程语言都有了一个全新的认识。我也会积极吸取本次课程设计的经验，继续研究数据结构和所学的各种编程语言。

七、 源代码

# include

# include

# include

# include

# define MAX_OPERATOR_NUM 100 //运算符栈数组长度

# define MAX_DATA_NUM 100 //运算数栈数组长度

typedef struct OPStack //定义运算符栈

{

char opStack[MAX_OPERATOR_NUM];

int top;

}OPStack， *pOPStack;

typedef struct DATAStack //定义运算数栈

{

double stack[MAX_DATA_NUM];

int top;

}DATAStack， *pDATAStack;

void InitpOPStack(pOPStack &pOStack) //初始化运算符栈

{

if( !(pOStack = (pOPStack)malloc(sizeof(OPStack)))) //为运算符栈分配空间

{

printf("分配内存空间失败! ");

exit(-1);

}

pOStack->top = -1;

}

void InitpDATAStack(pDATAStack &pDStack) //初始化运算数栈

{

if( !(pDStack = (pDATAStack)malloc(sizeof(DATAStack)))) //为运算数栈分配空间

{

printf("分配内存空间失败! ");

exit(-1);

}

pDStack->top = -1;

}

void PushOPStack(pOPStack &pOStack， char ch) //运算符进栈

{

pOStack->opStack[++(pOStack->top)] = ch;

}

void PopOPStack(pOPStack &pOStack， char &ch) //运算符出栈

{

ch = pOStack->opStack[pOStack->top];

pOStack->top--;

}

void PushDATAStack(pDATAStack &pDStack， double d) //运算数进栈

{

++(pDStack->top);

pDStack->stack[pDStack->top] = d;

}

void PopDATAStack(pDATAStack &pDStack， double &d) //运算数出栈

{

d = pDStack->stack[pDStack->top];

pDStack->top--;

}

void ClearpOPStack(pOPStack &pOStack) //清空运算符栈

{

pOStack->top = -1;

}

void ClearpDATAStack(pDATAStack &pDStack) //清空运算数栈

{

pDStack->top = -1;

}

char GetToppOPStack(pOPStack &pOStack) //获取运算符栈顶元素

{

return pOStack->opStack[pOStack->top];

}

double GetToppDATAStack(pDATAStack &pDStack) //获取运算数栈顶元素

{

return pDStack->stack[pDStack->top];

}

bool IsOP(char &ch) //区分 运算符 和 运算数 的函数，是运算符时返回true，否则返回false

{ //判断是否为符号

if ( (ch == "+") || (ch == "-") || (ch == "*") || (ch == "/") || (ch == "=") || (ch == "A") || (ch == "S") || (ch == "a") || (ch == "s") || (ch == "(") || (ch == ")") )

return true;

else

return false;

}

char Precede(char op1， char op2) //参考《数据结构》(C语言版)第53页 3.2.5表达式求值 表 3.1

{

char tab[9][10]; //定义字符串的二维数组来存放运算符优先级的关系

strcpy( tab[0]， ">><<<><<>" );

strcpy( tab[1]， ">><<<><<>" );

strcpy( tab[2]， ">>>><><<>" );

strcpy( tab[3]， ">>>><><<>" );

strcpy( tab[4]， "<<<<<=<

strcpy( tab[5]， ">>>>E>>>>" );

strcpy( tab[6]， ">>>><>>>>" );

strcpy( tab[7]， ">>>><>>>>" );

strcpy( tab[8]， "<<<<

printf(" | ***欢迎您的下次使用!谢谢!!!*** | "); //退出使用

printf(" |~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~| ");

}

double Operate(double a， char theta， double b) //对出栈的运算符和运算数进行计算

{

double s;

switch(theta)

{

case "+":

s = a + b;

break;

case "-":

s = a - b;

break;

case "*":

s = a * b;

break;

case "/":

if ( b != 0 ) //判断除数是否为0，若为0，退出程序

{

s = a/b;

break;

}

else

{

printf(" #### 除数为0，非法运算。程序终止! #### ");

exit_E(); //打印结束菜单

exit(-1);

}

case "A":

s = fabs(b); //调用FABS()函数

break;

case "S":

if( b >= 0) //判断被开方数是否为0，若为0，退出程序

{

s = sqrt(b); //调用SQRT()函数

break;

}

else

{

printf(" #### 求负数的平方根是非法运算。程序终止! #### ");

exit_E(); //打印结束菜单

exit(-1);

}

}

return s;

}

char ChangeChar(char &c) //通过ChangeChar函数来把a、s的小写字母改为大写的

{

if( c == "a" )

c = "A";

else if( c == "s" )

c = "S";

return c;

}

//参考《数据结构》(C语言版)第53页 3.2.5表达式求值算法3.4 Evaluateexpression_r()函数

void Evaluateexpression_r() //计算函数：读入表达式，并计算结果

{

pOPStack pOStack; //声明运算符栈

pDATAStack pDStack; //声明运算数栈

double result; //存运算的结果

char x， theta， c; //c存放读取的字符，x、theta存放运算符栈的栈顶元素

int flag， data; //标识符，用来读入连续的数字

double s;

double getd; //存放GetTop***的结果

double a， b， cc; //a，b存放数据栈出栈的栈顶元素， c存放运算结果

flag = 0; //初始化标识符，用来判断字符串中的连续数字

data = 0; //

InitpOPStack(pOStack); //初始化运算符栈

InitpDATAStack(pDStack); //初始化运算数栈

PushOPStack(pOStack， "="); //在运算符栈底放入"="

printf(" &请输入表达式以"="结束：");

c = get); //读入字符

ChangeChar(c); //通过调用函数来实现把小写的a、s改为大写的A、S

while( c != "=" || GetToppOPStack(pOStack) != "=")

{

if( !IsOP(c) ) //不是运算符进栈

{

s = c - "0"; //把字符转化为数字

if ( flag == 1 )

{

PopDATAStack(pDStack， getd);

s = getd*10 + s;

}

PushDATAStack(pDStack， s);

flag = 1;

c = get);

ChangeChar(c);

}

else

{

flag = 0;

switch( Precede(GetToppOPStack(pOStack)， c) ) //输入元素和运算符栈顶元素比较

{

case "<": //栈顶元素优先级低

PushOPStack(pOStack， c);

c = get);

ChangeChar(c);

break;

case "=": //托括号并接受下一个字符

PopOPStack(pOStack， x);

c = get);

ChangeChar(c);

break;

case ">": //退栈并将运算结果进栈

PopOPStack(pOStack， theta);

PopDATAStack(pDStack， b);

PopDATAStack(pDStack， a);

cc = Operate(a， theta， b);

PushDATAStack(pDStack， cc);

break;

}//switch

}//else

}//while

result = GetToppDATAStack(pDStack); //运算结束时，运算数栈的栈底元素就是计算结果

ClearpOPStack(pOStack); //清空运算符栈

ClearpDATAStack(pDStack); //清空运算数栈

printf(" ->计算结果为：%.2f "， result); //输出运算结果

return ;

}

void print_user() //欢迎界面

{

printf(" 欢迎使用C语言版模拟计算器 ");

printf("************************************************************************ ");

printf(" |~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~| ");

printf(" | 模拟计算器使用说明 | ");

printf(" | 作者：谢先斌 | ");

printf(" | 本程序包括对"+"、"-"、"*"、"/"、"()"的运算 | ");

printf(" | 本程序中ABS()算用A()替代、SQRT()运算用S()代替 | ");

printf(" | 本程序中的一切字母均不区分大小写 | ");

printf(" 正确的表达式如：1+A(7-8)+S(9*8)= ");

printf(" | 输入"="表示表达式输入结束!! | ");

printf(" | 欢迎使用!!!-->--> | ");

printf(" |~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~| ");

printf("************************************************************************ ");

}

int main() //主函数

{

char in;

bool b; //标识符，用来标识是否结束程序

b = true; //初始化，不结束

print_user(); //打印欢迎界面

printf(" *请确认使用计算器Y/N:");

while(1)

{

scanf("%c"， &in); //确认是否继续操作

get); //吃掉会车，避免干扰

switch(in)

{

case "Y":

case "y":

{

Evaluateexpression_r(); //进入计算函数：读入表达式，并计算结果

break;

}

case "N":

case "n":

{

exit_E();

b = false;

break;

}

//default:

// printf(" **输入错误，请重新输入Y/N:");

// break;

}

if(b==false) //如果 b==false ，退出整个程序

break;

printf(" *您确定要继续使用计算机Y/N:");

get); //用getchar吃掉回车，避免对后续输入中in的干扰

}

return 0;

}

数据结构实验报告 实验五 篇4

1．顺序表的建立、插入、删除。

2．带头结点的单链表的建立（用尾插法）、插入、删除。

二、提交到个人10M硬盘空间的内容及截止时间

1．分别建立二个文件夹，取名为顺序表和单链表。

2．在这二个文件夹中，分别存放上述二个实验的相关文件。每个文件夹中应有三个文件(.C文件、.OBJ文件和.EXE文件)。

3.截止时间：12月28日（18周周日）晚上关机时为止，届时服务器将关闭。

三、实验报告要求及上交时间（用A4纸打印）

1．格式：

《计算机软件技术基础》上机实验报告

用户名se×××× 学号 姓名 学院

① 实验名称：

② 实验目的：

③ 算法描述（可用文字描述，也可用流程图）：

④ 源代码：（.C的文件）

⑤ 用户屏幕（即程序运行时出现在机器上的画面）：

2．对C文件的要求：

程序应具有以下特点：A 可读性：有注释。

B 交互性：有输入提示。

C 结构化程序设计风格：分层缩进、隔行书写。

3.上交时间：12月26日下午1点-6点，工程设计中心三楼教学组。请注意：过时不候哟！

数据结构实验报告 实验五 篇5

一、实验目的及要求

1)掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们。

本实验训练的要点是“栈”和“队列”的观点;

二、实验内容

1) 利用栈，实现数制转换。

2) 利用栈，实现任一个表达式中的语法检查(选做)。

3) 编程实现队列在两种存储结构中的基本操作(队列的初始化、判队列空、入队列、出队列);

三、实验流程、操作步骤或核心代码、算法片段

顺序栈：

status initstack(sqstack &s)

{

s.base=(elemtype*)malloc(stack_init_size*sizeof(elemtype));

if(!s.base)

return error;

s.top=s.base;

s.stacksize=stack_init_size;

return ok;

}

status destorystack(sqstack &s)

{

free(s.base);

return ok;

}

status clearstack(sqstack &s)

{

s.top=s.base;

return ok;

}

status stackempty(sqstack s)

{

if(s.base==s.top)

return ok;

return error;

}

int stacklength(sqstack s)

{

return s.top-s.base;

}

status gettop(sqstack s，elemtype &e)

{

if(s.top-s.base>;=s.stacksize)

{

s.base=(elemtype *)realloc(s.base，(s.stacksize+stackincrement)*sizeof(elemtype));

if(!s.base) return error;

s.top=s.base+s.stacksize;

s.stacksize+=stackincrement;

}

*s.top++=e;

return ok;

}

status push(sqstack &s，elemtype e)

{

if(s.top-s.base>;=s.stacksize)

{

s.base=(elemtype *)realloc(s.base，(s.stacksize+stackincrement)*sizeof(elemtype));

if(!s.base)

return error;

s.top=s.base+s.stacksize;

s.stacksize+=stackincrement;

}

*s.top++=e;

return ok;

}

status pop(sqstack &s，elemtype &e)

{

if(s.top==s.base)

return error;

e=*--s.top;

return ok;

}

status stacktraverse(sqstack s)

{

elemtype *p;

p=(elemtype *)malloc(sizeof(elemtype));

if(!p) return error;

p=s.top;

while(p!=s.base)//s.top上面一个...

{

p--;

printf("%d "，*p);

}

return ok;

}

status compare(sqstack &s)

{

int flag，ture=ok，false=error;

elemtype e，x;

initstack(s);

flag=ok;

printf("请输入要进栈或出栈的元素：");

while((x= getchar)!="#"&&flag)

{

switch (x)

{

case "(":

case "[":

case "{":

if(push(s，x)==ok)

printf("括号匹配成功!nn");

break;

case ")":

if(pop(s，e)==error || e!="(")

{

printf("没有满足条件n");

flag=false;

}

break;

case "]":

if ( pop(s，e)==error || e!="[")

flag=false;

break;

case "}":

if ( pop(s，e)==error || e!="{")

flag=false;

break;

}

}

if (flag && x=="#" && stackempty(s))

return ok;

else

return error;

}

链队列：

status initqueue(linkqueue &q)

{

q.front =q.rear=

(queueptr)malloc(sizeof(qnode));

if (!q.front) return error;

q.front->;next = null;

return ok;

}

status destoryqueue(linkqueue &q)

{

while(q.front)

{

q.rear=q.front->;next;

free(q.front);

q.front=q.rear;

}

return ok;

}

status queueempty(linkqueue &q)

{

if(q.front->;next==null)

return ok;

return error;

}

status queuelength(linkqueue q)

{

int i=0;

queueptr p，q;

p=q.front;

while(p->;next)

{

i++;

p=q.front;

q=p->;next;

p=q;

}

return i;

}

status gethead(linkqueue q，elemtype &e)

{

queueptr p;

p=q.front->;next;

if(!p)

return error;

e=p->;data;

return e;

}

status clearqueue(linkqueue &q)

{

queueptr p;

while(q.front->;next )

{

p=q.front->;next;

free(q.front);

q.front=p;

}

q.front->;next=null;

q.rear->;next=null;

return ok;

}

status enqueue(linkqueue &q，elemtype e)

{

queueptr p;

p=(queueptr)malloc(sizeof (qnode));

if(!p)

return error;

p->;data=e;

p->;next=null;

q.rear->;next = p;

q.rear=p; //p->;next 为空

return ok;

}

status dequeue(linkqueue &q，elemtype &e)

{

queueptr p;

if (q.front == q.rear)

return error;

p = q.front->;next;

e = p->;data;

q.front->;next = p->;next;

if (q.rear == p)

q.rear = q.front; //只有一个元素时(不存在指向尾指针)

free (p);

return ok;

}

status queuetraverse(linkqueue q)

{

queueptr p，q;

if( queueempty(q)==ok)

{

printf("这是一个空队列!n");

return error;

}

p=q.front->;next;

while(p)

{

q=p;

printf("%d<-n"，q->;data);

q=p->;next;

p=q;

}

return ok;

}

循环队列：

status initqueue(sqqueue &q)

{

q.base=(qelemtype*)malloc(maxqsize*sizeof(qelemtype));

if(!q.base)

exit(owerflow);

q.front=q.rear=0;

return ok;

}

status enqueue(sqqueue &q，qelemtype e)

{

if((q.rear+1)%maxqsize==q.front)

return error;

q.base[q.rear]=e;

q.rear=(q.rear+1)%maxqsize;

return ok;

}

status dequeue(sqqueue &q，qelemtype &e)

{

if(q.front==q.rear)

return error;

e=q.base[q.front];

q.front=(q.front+1)%maxqsize;

return ok;

}

int queuelength(sqqueue q)

{

return(q.rear-q.front+maxqsize)%maxqsize;

}

status destoryqueue(sqqueue &q)

{

free(q.base);

return ok;

}

status queueempty(sqqueue q) //判空

{

if(q.front ==q.rear)

return ok;

return error;

}

status queuetraverse(sqqueue q)

{

if(q.front==q.rear)

printf("这是一个空队列!");

while(q.front%maxqsize!=q.rear)

{

printf("%d<- "，q.base[q.front]);

q.front++;

}

return ok;

}

数据结构实验报告 实验五 篇6

数据结构(C语言版) 实验报告

专业：计算机科学与技术、软件工程

学号:____40703061___________________

班级:_________软件二班______________

姓名:________朱海霞______________

指导教师:___刘遵仁________________

青岛大学信息工程学院

xxxx年10月

实验1

实验题目：顺序存储结构线性表的插入和删除

实验目的：

了解和掌握线性表的逻辑结构和顺序存储结构，掌握线性表的基本算法及相关的时间性能分析。

实验要求：

建立一个数据域定义为整数类型的线性表，在表中允许有重复的数据;根据输入的数据，先找到相应的存储单元，后删除之。

实验主要步骤：

1、分析、理解给出的示例程序。

2、调试程序，并设计输入一组数据(3，-5，6，8，2，-5，4，7，-9)，测试程序的如下功能：根据输入的数据，找到相应的存储单元并删除，显示表中所有的数据。

程序代码:

#include

#include

#define OK 1

#define ERROR 0

#define OVERFLOW -2

#define LIST_INIT_SIZE 100

#define LISTINCREMENT 10

typedef struct{

int* elem;

int length;

int listsize;

}Sqlist;

int InitList_Sq(Sqlist &L){

L.elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int));

if(!L.elem) return -1;

L.length=0;

L.listsize=LIST_INIT_SIZE;

return OK;

}

int ListInsert_Sq(Sqlist&L，int i，int e){

if(i<1||i>L.length+1) return ERROR;

if(L.length==L.listsize){

int *newbase;

newbase=(int*)realloc(L.elem，(L.listsize+LISTINCREMENT)*sizeof(int));

if(!newbase) return -1;

L.elem=newbase;

L.listsize+=LISTINCREMENT;

}

int *p，*q;

q=&(L.elem[i-1]);

for(p=&(L.elem[L.length-1]);p>=q;--p)

*(p+1)=*p;

*q=e;

++L.length;

return OK;

}

int ListDelete_Sq(Sqlist &L，int i，int e){

int *p，*q;

if(i<1||i>L.length)return ERROR;

p=&(L.elem[i-1]);

e=*p;

q=L.elem+L.length-1;

for(++p;p<=q;++p)

*(p-1)=*p;

--L.length;

return OK;

}

int main(){

Sqlist L;

InitList_Sq(L);//初始化

int i，a[]={3，-5，6，8，2，-5，4，7，-9};

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

ListInsert_Sq(L，i，a[i-1]);

for(i=0;i<9;i++)

printf(" %d"，L.elem[i]);

printf(" ");//插入9个数

ListInsert_Sq(L，3，24);

for(i=0;i<10;i++)

printf(" %d"，L.elem[i]);

printf(" ");//插入一个数

int e;

ListDelete_Sq(L，2， e);

for(i=0;i<9;i++)

printf(" %d"，L.elem[i]);//删除一个数

printf(" ");

return 0;

}

实验结果：

3，-5，6，8，2，-5，4，7，-9

3，-5，24，6，8，2，-5，4，7，-9

3，24，6，8，2，-5，4，7，-9

心得体会：

顺序存储结构是一种随机存取结构，存取任何元素的时间是一个常数，速度快;结构简单，逻辑上相邻的元素在物理上也相邻;不使用指针，节省存储空间;但是插入和删除元素需要移动大量元素，消耗大量时间;需要一个连续的存储空间;插入元素可能发生溢出;自由区中的存储空间不能被其他数据共享 实验2

实验题目：单链表的插入和删除

实验目的：

了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。

实验要求：

建立一个数据域定义为字符类型的单链表，在链表中不允许有重复的字符;根据输入的字符，先找到相应的结点，后删除之。

实验主要步骤：

3、分析、理解给出的示例程序。

4、调试程序，并设计输入数据(如：A，C，E，F，H，J，Q，M)，测试程序的如下功能：不允许重复字符的插入;根据输入的字符，找到相应的结点并删除。

5、修改程序：

(1) 增加插入结点的功能。

(2) 建立链表的方法有“前插”、“后插”法。

程序代码:

#include

#include

#define NULL 0

#define OK 1

#define ERROR 0

typedef struct LNode{

int data;

struct LNode *next;

}LNode，*LinkList;

int InitList_L(LinkList &L){

L=(LinkList)malloc(sizeof(LNode)); L->next=NULL;

return OK;

}

int ListInsert_L(LinkList &L，int i，int e){ LinkList p，s;

int j;

p=L;j=0;

while(p&&j

p=p->next;++j;

}

if(!p||j>i-1)

return ERROR;

s=(LinkList)malloc(sizeof(LNode)); s->data=e;

s->next=p->next;

p->next=s;

return OK;

}

int ListDelete_L(LinkList&L，int i，int &e){ LinkList p，q;

int j;

p=L;j=0;

while(p->next&&j

p=p->next;++j;

}

if(!(p->next)||j

return ERROR;

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

return OK;

}

int main(){

LinkList L，p;

char a[8]={"A"，"C"，"E"，"F"，"H"，"J"，"Q"，"U"}; int i，j;

InitList_L(L);

for(i=1，j=0;i<=8，j<8;i++，j++) ListInsert_L(L，i，a[j]);

p=L->next;

while(p!=NULL){

printf("%c "，p->data); p=p->next;

}//插入八个字符printf(" ;实验结果：;ACEFHJQU;ABCEFHJQU;ABEFHJQU;心得体会：;单链表是通过扫描指针P进行单链表的操作;头指针唯;实验3;实验题目：栈操作设计和实现;实验目的：;1、掌握栈的顺序存储结构和链式存储结构，以便在实;2、掌握栈的特点，即后进先出和先进先出的原则;3、掌握栈的基本运算，如：入栈与出栈

}

}//插入八个字符 printf(" "); i=2; int e; ListInsert_L(L，i，"B"); p=L->next; while(p!=NULL){ printf("%c "，p->data); p=p->next; }//插入一个字符 printf(" "); i=3; ListDelete_L(L，i，e); p=L->next; while(p!=NULL){ printf("%c "，p->data); p=p->next; } printf(" "); return 0;

实验结果：

A C E F H J Q U

A B C E F H J Q U

A B E F H J Q U

心得体会：

单链表是通过扫描指针P进行单链表的操作;头指针唯一标识点链表的存在;插入和删除元素快捷，方便。

实验3

实验题目：栈操作设计和实现

实验目的：

1、掌握栈的顺序存储结构和链式存储结构，以便在实际中灵活应用。

2、掌握栈的特点，即后进先出和先进先出的原则。

3、掌握栈的基本运算，如：入栈与出栈等运算在顺序存储结构和链式存储结构上的实现。

实验要求：

回文判断：对于一个从键盘输入的字符串，判断其是否为回文。回文即正反序相同。如

“abba”是回文，而“abab”不是回文。

实验主要步骤

(1)数据从键盘读入;

(2)输出要判断的字符串;

(3)利用栈的基本操作对给定的字符串判断其是否是回文，若是则输出“Yes”，否则输出“No”。

程序代码:

#include

#include

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define OVERFLOW -2

#define N 100

#define STACK_INIT_SIZE 100

#define STACKINCREMENT 10

typedef struct{

int *base; // 在栈构造之前和销毁之后，base的值为NULL int *top; // 栈顶指针

int stacksize; // 当前已分配的存储空间，以元素为单位

} SqStack;

int InitStack(SqStack &S)

{ // 构造一个空栈S

if(!(S.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int))))

exit(OVERFLOW); // 存储分配失败

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

return OK;

}

int StackEmpty(SqStack S)

{ // 若栈S为空栈，则返回TRUE，否则返回FALSE

if(S.top==S.base)

return TRUE;

else

return FALSE;

}

int Push(SqStack &S， int e)

{ // 插入元素e为新的栈顶元素

if(S.top-S.base>=S.stacksize) // 栈满，追加存储空间

{

S.base=(int *)realloc(S.base，(S.stacksize+STACKINCREMENT)*sizeof(int)); if(!S.base)

exit(OVERFLOW); // 存储分配失败

S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;

}

*(S.top)++=e;

return OK;

}

int Pop(SqStack &S，int &e)

{ // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK;否则返回ERROR if(S.top==S.base)

return ERROR;

e=*--S.top;

return OK;

}

int main(){

SqStack s;

int i，e，j，k=1;

char ch[N] = {0}，*p，b[N] = {0};

if(InitStack(s)) // 初始化栈成功

{

printf("请输入表达式: ");

gets(ch);

p=ch;

while(*p) // 没到串尾

Push(s，*p++);

for(i=0;i

if(!StackEmpty(s)) {// 栈不空

Pop(s，e); // 弹出栈顶元素

b[i]=e;

}

}

for(i=0;i

if(ch[i]!=b[i])

k=0;

}

if(k==0)

printf("NO!");

else

printf("输出:")

printf("YES!");

}

return 0;

}

实验结果：

请输入表达式：

abcba

输出：YES!

心得体会：栈是仅能在表尾惊醒插入和删除操作的线性表，具有先进后出的性质，这个固有性质使栈成为程序设计中的有用工具。

实验4

实验题目：二叉树操作设计和实现

实验目的：

掌握二叉树的定义、性质及存储方式，各种遍历算法。

实验要求：

采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。

实验主要步骤：

1、分析、理解程序。

2、调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点(空指针)，如ABD###CE##F##，建立二叉树，求出先序、中序和后序以及按层次遍历序列，求所有叶子及结点总数。

程序代码:

实验结果：

心得体会：

实验5

实验题目：图的遍历操作

实验目的：

掌握有向图和无向图的概念;掌握邻接矩阵和邻接链表建立图的存储结构;掌握DFS及BFS对图的遍历操作;了解图结构在人工智能、工程等领域的广泛应用。

实验要求：

采用邻接矩阵和邻接链表作为图的存储结构，完成有向图和无向图的DFS和BFS操作。

实验主要步骤：

设计一个有向图和一个无向图，任选一种存储结构，完成有向图和无向图的DFS(深度优先遍历)和BFS(广度优先遍历)的操作。

1. 邻接矩阵作为存储结构

#include"stdio.h"

#include"stdlib.h"

#define MaxVertexNum 100 //定义最大顶点数

typedef struct{

char vexs[MaxVertexNum]; //顶点表

int edges[MaxVertexNum][MaxVertexNum]; //邻接矩阵，可看作边表 int n，e; //图中的顶点数n和边数e

}MGraph; //用邻接矩阵表示的图的类型

//=========建立邻接矩阵=======

void CreatMGraph(MGraph *G)

{

int i，j，k;

char a;

printf("Input VertexNum(n) and EdgesNum(e): ");

scanf("%d，%d"，&G->n，&G->e); //输入顶点数和边数

scanf("%c"，&a);

printf("Input Vertex string:");

for(i=0;in;i++)

{

scanf("%c"，&a);

G->vexs[i]=a; //读入顶点信息，建立顶点表

}

for(i=0;in;i++)

for(j=0;jn;j++)

G->edges[i][j]=0; //初始化邻接矩阵

printf("Input edges，Creat Adjacency Matrix ");

for(k=0;ke;k++) { //读入e条边，建立邻接矩阵

scanf("%d%d"，&i，&j); //输入边(Vi，Vj)的顶点序号

G->edges[i][j]=1;;G->edges[j][i]=1;//若为;//=========定义标志向量，为全局变量=;typedefenum{FALSE，TRUE}B;Booleanvisited[MaxVertex;//========DFS：深度优先遍历的递归算;voidDFSM(MGraph*G，inti);{//以Vi为出发点

G->edges[i][j]=1;

G->edges[j][i]=1; //若为无向图，矩阵为对称矩阵;若建立有向图，去掉该条语句 }

}

//=========定义标志向量，为全局变量=======

typedef enum{FALSE，TRUE} Boolean;

Boolean visited[MaxVertexNum];

//========DFS：深度优先遍历的递归算法======

void DFSM(MGraph *G，int i)

{ //以Vi为出发点对邻接矩阵表示的图G进行DFS搜索，邻接矩阵是0，1矩阵

给出你的编码

//===========BFS：广度优先遍历=======

void BFS(MGraph *G，int k)

{ //以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索

给出你的编码

//==========主程序main =====

void main()

{

int i;

MGraph *G;

G=(MGraph *)malloc(sizeof(MGraph)); //为图G申请内存空间

CreatMGraph(G); //建立邻接矩阵

printf("Print Graph DFS: ");

DFS(G); //深度优先遍历

printf(" ");

printf("Print Graph BFS: ");

BFS(G，3); //以序号为3的顶点开始广度优先遍历

printf(" ");

}

2. 邻接链表作为存储结构

#include"stdio.h"

#include"stdlib.h"

#define MaxVertexNum 50 //定义最大顶点数

typedef struct node{ //边表结点

int adjvex; //邻接点域

struct node *next; //链域

}EdgeNode;

typedef struct vnode{ //顶点表结点

char vertex; //顶点域

EdgeNode *firstedge; //边表头指针

}VertexNode;

typedef VertexNode AdjList[MaxVertexNum]; //AdjList是邻接表类型 typedef struct {

AdjList adjlist; //邻接表

int n，e; //图中当前顶点数和边数

} ALGraph; //图类型

//=========建立图的邻接表=======

void CreatALGraph(ALGraph *G)

{

int i，j，k;

char a;

EdgeNode *s; //定义边表结点

printf("Input VertexNum(n) and EdgesNum(e): ");

scanf("%d，%d"，&G->n，&G->e); //读入顶点数和边数

scanf("%c"，&a);

printf("Input Vertex string:");

for(i=0;in;i++) //建立边表

{

scanf("%c"，&a);

G->adjlist[i].vertex=a; //读入顶点信息

G->adjlist[i].firstedge=NULL; //边表置为空表

}

printf("Input edges，Creat Adjacency List ");

for(k=0;ke;k++) { //建立边表

scanf("%d%d"，&i，&j); //读入边(Vi，Vj)的顶点对序号

s=(EdgeNode *)malloc(sizeof(EdgeNode)); //生成边表结点

s->adjvex=j; //邻接点序号为j

s->next=G->adjlist[i].firstedge;

G->adjlist[i].firstedge=s; //将新结点*S插入顶点Vi的边表头部

s=(EdgeNode *)malloc(sizeof(EdgeNode));

s->adjvex=i; //邻接点序号为i

s->next=G->adjlist[j].firstedge;

G->adjlist[j].firstedge=s; //将新结点*S插入顶点Vj的边表头部

}

}

//=========定义标志向量，为全局变量=======

typedef enum{FALSE，TRUE} Boolean;

Boolean visited[MaxVertexNum];

//========DFS：深度优先遍历的递归算法======

void DFSM(ALGraph *G，int i)

{ //以Vi为出发点对邻接链表表示的图G进行DFS搜索

给出你的编码

//==========BFS：广度优先遍历=========

void BFS(ALGraph *G，int k)

{ //以Vk为源点对用邻接链表表示的图G进行广度优先搜索

给出你的编码

//==========主函数===========

void main()

{

int i;

ALGraph *G;

G=(ALGraph *)malloc(sizeof(ALGraph));

CreatALGraph(G);

printf("Print Graph DFS: ");

DFS(G);

printf(" ");

printf("Print Graph BFS: ");

BFS(G，3);

printf(" ");

}

实验结果：

1. 邻接矩阵作为存储结构

2. 邻接链表作为存储结构

心得体会：

实验6

实验题目：二分查找算法的实现

实验目的：

掌握二分查找法的工作原理及应用过程，利用其工作原理完成实验题目中的内容。

实验要求：

编写程序构造一个有序表L，从键盘接收一个关键字key，用二分查找法在L中查找key，若找到则提示查找成功并输出key所在的位置，否则提示没有找到信息。

实验主要步骤：

1. 建立的初始查找表可以是无序的，如测试的数据为{3，7，11，15，17，21，35，42，50｝或者{11，21，7，3，15，50，42，35，17｝。

2. 给出算法的递归和非递归代码;

3. 如何利用二分查找算法在一个有序表中插入一个元素x，并保持表的有序性?

程序代码

实验结果：

心得体会：

实验7

实验题目：排序

实验目的：

掌握各种排序方法的基本思想、排序过程、算法实现，能进行时间和空间性能的分析，根据实际问题的特点和要求选择合适的排序方法。

实验要求：

实现直接排序、冒泡、直接选择、快速、堆、归并排序算法。比较各种算法的运行速度。

实验主要步骤：

程序代码

实验结果：

心得体会：

数据结构实验报告 实验五 篇7

实习报告的开头应给出题目、班级、姓名、学号和完成日期，并包括以下七个内容：

1.需求分析

以无歧义的陈述说明程序设计的任务，强调的是程序要做什么?明确规定：

(1)输入的形式和输入值的范围;

(2)输出的形式;

(3)程序所能达到的功能;

(4)测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。

2.概要设计

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

3.详细设计

实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法;对主程序和其他模块也都需要写出伪码算法(伪码算法达到的详细程度建议为：按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序);画出函数的调用关系图。

4.调试分析

内容包括：

(1)调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析;

(2)算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)和改进设想;

(3)经验和体会等。

5.用户使用说明

说明如何使用你编写的程序，详细列出每一步的操作步骤。

6.测试结果

列出你的测试结果，包括输入和输出。这里的测试数据应该完整和严格，最好多于需求分析中所列。

7.附录

带注释的源程序。如果提交源程序软盘，可以只列出程序文件名的清单。

值得注意的是，实习报告的各种文档资料，如：上述中的前三部分要在程序开发的过程中逐渐充实形成，而不是最后补写(当然也可以应该最后用实验报告纸誊清或打印)。

数据结构实验报告;实验名称：实验一线性表实现一个多项式;学生姓名：黄锦雨;班级：211109;班内序号：20;学号：210263;日期：xxxx年10月31日;实验目的：;1.熟悉C++语言的基本编程方法，掌握集成编译环;2.学习指针、模板类、异常处理的使用;3.掌握线性表的操作的实现方法;4.学习使用线性表解决实际问题的能力;实验内容：;

数据结构实验报告

实验名称： 实验一线性表实现一个多项式

学生姓名： 黄锦雨

班 级：211109

班内序号： 20

学 号： 210263

日 期： xxxx年10月31日

实验目的：

1.熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法

2.学习指针、模板类、异常处理的使用

3.掌握线性表的操作的实现方法

4.学习使用线性表解决实际问题的能力

实验内容：

利用线性表实现一个一元多项式Polynomial

f(x) = a0 + a1x + a2x2 + a3x3 + … + anxn

要求：

1. 能够实现一元多项式的输入和输出

2. 能够进行一元多项式相加

3. 能够进行一元多项式相减

4. 能够计算一元多项式在x处的值

5. 能够计算一元多项式的导数(选作)

6. 能够进行一元多项式相乘(选作) 7. 编写测试main()函数测试线性表的正确性

2. 程序分析

由于多项式是线性结构，故选择线性表来实现，在这个程序中我采用的是单链表结构，每个结点代表一个项，多项式的每一项可以用其系数和指数唯一的表示。如果采用顺序存储，那么对于结点的插入和删除的操作会比较麻烦，而且顺序表的结点个数固定，对于可能发生的情况无法很好的处理，而采用链表就会简单许多，还能自由控制链表的长度。

两个多项式要进行多次的计算，为了保护原始的数据，方便进行以后的计算，故选择把结果存储在一个新建的链表里。

2.1本程序完成的主要功能：

1. 输入和输出：需要输入的信息有多项式的项数，用来向系统动态申请内存;多项式

各项的系数和指数，用来构造每个结点，形成链表。输出即是将多项式的内容

向屏幕输出。

2. 多项式相加与相减：多项式的加减要指数相同即是同类项才能实现，所以在运算时

要注意判断指数出现的各种不同的情况，分别写出计算方法。将每项运算得到

的结果都插入到新的链表中，形成结果多项式。

3. 多项式的求导运算：多项式的求导根据数学知识，就是将每项的系数乘以指数，将

指数减1即可，将每项得到的结果插入到结果多项式的链表中。

4. 多项式在某点的值：由用户输入x的值，然后求出每项的值相加即可。

2.2存储结构

单链表: 其定义的结点包括三部分：系数、指数以及下一个结点的地址

2.3关键算法分析

[内容要求]

关键算法：

1.一元多项式求和算法:

[1]初始化工作指针p和q，以及p节点前驱节点指针p_prior

[2]若p和q都不为空，则循环以下操作:

[2.1]若p->data.expdata.exp，则p_prior=p;p=p->nenx;

[2.2]否则，若p->data.exp>q->data.exp，则:

[2.2.1]将q结点加入到A链表p结点之前

[2.2.2]q指向B链表的下一个结点

[2.3]否则:p->data.coef=p->data.coef+q->data.coef;

[2.3.1]若p->data.coef为0，则删除结点p

[2.3.2]p指向下一个结点

[2.3.3]删除q结点

[2.3.4]q指向下一个结点

[3]若p为空并且q不为空，则将q结点及其后所有结点追加到A链表的最后端

[4]将B链表 制成空链表

2.一元多项式求导

[1]初始化工作指针p及p_prior

[2]若p不为空，循环以操作

[2.1]若p->data.exp=0;p_prior->next=p->next; p; p=p_prior;

[2.2]否则 p->data.coef*=p->data.exp; p->data.exp--;

3.一元多项式求在X处的值

[1]初始化工作指针p，定义会参数a

[2]若p不为空，循环以下操作

a+=p->data.coef*pow(x，p->data.exp);

p=p->next;

4.输出多项式

[1]获取头结点;

[2]循环n-1次(n为多项式的项数)

[2.1]将指针的指向后移;

[2.2]依照多项式的各种情况，设置输出方式

[2.2.1] 系数为1且指数不为1和0，输出x^expn+;

[2.2.2] 系数不为0且指数为0，输出(coef)+;

[2.2.3] 系数不为0且指数为1，输出(coef)x+;

代码详细分析：

求和算法详细分析:

1.若p->data.expdata.exp

(1)q结点不变

(2)p结点向下移

(1)p_prior=p;

(2)p=p->next;

2.若p->data.exp>q->data.exp执行一下主要操作步骤

(1) p_prior->next=q;

(2)p_prior=q;

(3)q=q->next;

(4)p_prior->next=p;

示意图

:

3.若p->data.exp==q->data.exp执行以下操作步骤:

(a)若合并系数为零，则删除p结点，主要步骤:

(1)p_prior->next=p->next;

(2) p;

(3)p=p_prior->next;

(4)Node*temp=q;

(5)q=q->next;

(6) temp;

示意图

:

(b)合并系数不为零，将其从新赋予p结点，主要步骤:

(1)p_prior=p;

(2)p=p_prior->next;

(3)Node*temp=q;

(4)q=q->next;

(5) temp;

示意图:

5. 若p为空且q不为空的情况

p_prior->next=q;

示意图:

3、计算关键算法的时间，空间复杂度

时间复杂度(1)一元多项式的构建(2)求和(3)减法(4)求导 时间复杂度都为O(n)

空间复杂度为:S(1)

2.3 其他

[内容要求]说明:为了防止word版本不一样而可能带来的图形错乱，示意图，流程图都用截图

3. 程序运行结果

测试主函数流程：流程图如图所示

4.总结;[正文格式要求]见1实验要求中的格式要求;1.这次实现一元多项式的运算运用了模版类，单链表;版类的的继承，在掌握模版类及链表的同时又复习了上;2.这次试验另一比较大的工程是一元多项式加法的算;点打出来又截图完成的，真的是一个比较大工程!;3.这次一元多项式实验问题让我的收获很大，对链表;的更加准确，在调试代码，检验的时候，曾遇到很大的;4.通过本次

4. 总结

[正文格式要求] 见1实验要求中的格式要求

1. 这次实现一元多项式的运算运用了模版类，单链表模版类，一元多项式模版类是单链表模

版类的的继承，在掌握模版类及链表的同时又复习了上学期的相应内容.

2. 这次试验另一比较大的工程是一元多项式加法的算法示意图，以上截图全是我自己一点

点打出来又截图完成的，真的是一个比较大工程!

3.这次一元多项式实验问题让我的收获很大，对链表的构建更加熟练，对链表的向前推进把握

的更加准确，在调试代码，检验的时候，曾遇到很大的阻碍，主要是内存问题，通过自己一步步调试，解决了问题，自己也收获了很多。

4.通过本次实验，我发现自己分析问题不是很全面，容易忽略一些细节，以后分析问题时要仔细考虑认真分析，避免细节上的错误。

数据结构实验报告 实验五 篇8

《数据结构与算法》实验报告

专业 班级 姓名 学号

实验项目

实验一 二叉树的应用

实验目的

1、进一步掌握指针变量的含义及应用。

2、掌握二叉树的结构特征，以及各种存储结构的特点及使用范围。

3、掌握用指针类型描述、访问和处理二叉树的运算。

实验内容

题目1:编写一个程序，采用一棵二叉树表示一个家谱关系。要求程序具有如下功能：

（1）用括号表示法输出家谱二叉树，

（2）查找某人的所有儿子，

（3）查找某人的所有祖先。

算法设计分析

（一）数据结构的定义

为了能够用二叉树表示配偶、子女、兄弟三种关系，特采用以下存储关系，则能在二叉树上实现家谱的各项运算。

二叉树型存储结构定义为：

typedef struct SNODE

{char name[MAX]; //人名

struct SNODE *left;//指向配偶结点

struct SNODE *right; //指向兄弟或子女结点

}FNODE;

（二）总体设计

实验由主函数、家谱建立函数、家谱输出函数、儿子查找函数、祖先查找函数、结点定位函数、选择界面函数七个函数共同组成。其功能描述如下：

（1）主函数：统筹调用各个函数以实现相应功能

void main()

（2）家谱建立函数：与用户交互建立家族成员对应关系

void InitialFamily(FNODE *&head) //家谱建立函数

（3）家谱输出函数：用括号表示法输出家谱

输出形式为：父和母（子1和子妻1（孙1），子2和子妻2（孙2））

void PrintFamily(FNODE *head) //家谱输出函数

（4）儿子查找函数：在家谱中查找到某人所有的子女并输出，同时也能辨别出其是否为家族成员与是否有子女

void FindSon(FNODE *b，char p[]) //儿子查找函数

（5）祖先查找函数：在家谱中查找到某人所有的祖先并输出，同时也能辨别出其是否为家族中成员。

int FindAncestor(FNODE *head，char son[ ]) //祖先查找函数

（6）结点定位函数：在家谱中找到用户输入人名所对应的结点。

FNODE *findnode(FNODE *b，char p[]) //结点定位函数

（7）选择界面函数：为便于编写程序，将用户选择部分独立为此函数。

void PRINT(int &n)

（三）各函数的详细设计：

void InitialFamily(FNODE *&head) //家谱建立函数

1：首先建立当前人的"信息，将其左右结点置为空，

2：然后让用户确定其是否有配偶，如果没有配偶，则当前程序结束，

3：如果有则建立其配偶信息，并将配偶结点赋给当前人的左结点；

4：再让用户确定其是否有子女，如果有则递归调用家谱建立函数建立子女结点，并将其赋给配偶结点的下一个右结点。

5：如无，则程序结束

void PrintFamily(FNODE *head) //家谱输出函数

1：首先判断当前结点是否为空，如果为空则结束程序；

2：如果不为空，则输出当前结点信息，

3：然后判断其左结点（配偶结点）是否为空，如不为空则输出“和配偶信息。

4：再判断配偶结点的右结点是否为空，如不为空则递归调用输出其子女信息，最后输出“）”；

5：当配偶结点为空时，则判断其右结点（兄弟结点）是否为空

6：如果不为空，则输出“，”，并递归调用输出兄弟信息

7程序结束

FNODE *findnode(FNODE *b，char p[]) //结点定位函数

1：当前结点是否为空，为空则返回空；

2：如果和查找信息相同，则返回当前结点；

3：如不然，则先后递归访问其左结点，再不是则递归访问右结点

void FindSon(FNODE *b，char p[]) //儿子查找函数

1：在家谱中定位到要查找的结点，如无则输出“查找不到此人”

2：判断其配偶结点与子女结点是否为空，为空则输出“无子女”

3：不为空则输出其配偶结点的所有右结点（子女结点）。

int FindAncestor(FNODE *head，char son[ ]) //祖先查找函数

1：先在家谱中定位到要查找的结点，如为空输出“不存在此人”，程序结束

2：先将父母结点入栈，当栈为空时程序结束，

3：栈不为空时，判断栈顶元素是否已访问过，

4：访问过，再判断是否为查找结点，如是则输出栈中保存的其祖先结点，并滤过其兄弟结点不输出；不是查找结点，则退栈一个元素

5：未访问过，则取当前栈顶元素，置访问标志——1，同时取其右结点

6：栈不为空或当前所取结点不为空时，转到2；

实验测试结果及结果分析

（一）测试结果

（二）结果分析

（略）

实验总结

（略）