数据结构报告(收藏11篇)

【#实用文# #数据结构报告(收藏11篇)#】在经济飞速发展的今天,报告的使用频率呈上升趋势，优秀的报告，有助于我们团结同事和争取领导的支持。什么样的报告算得上是高质量的？今天编辑为大家带来了一篇关于“数据结构报告”的相关文章，记得将本文保存随时查看参考！

数据结构报告【篇1】

一、需求分析1、程序所实现的功能；2、程序的输入，包含输入的数据格式和说明；3、程序的输出，程序输出的形式；4、测试数据，如果程序输入的数据量比较大，需要给出测试数据；5、合作人及其分工二、设计说明1、主要的数据结构设计说明；2、程序的主要流程图；3、程序的主要模块，要求对主要流程图中出现的模块进行说明4、程序的主要函数及其伪代码说明(不需要完整的代码)；5、合作人设计分工三、上机结果及体会1、合作人编码分工2、实际完成的情况说明（完成的功能，支持的数据类型等）；3、程序的性能分析，包括时空分析；4、上机过程中出现的问题及其解决方案；5、程序中可以改进的地方说明；6、程序中可以扩充的功能及设计实现假想；说明：1、如果程序比较大，可以将设计说明分为概要设计和详细设计两部分。概要设计主要负责程序的流程、模块、抽象数据类型设计；详细设计负责程序的数据类型定义和主要函数的说明。2、设计说明中，不需要写出代码或者模块的详细代码，只需要写出主要函数的伪代码说明。

数据结构报告【篇2】

数据结构实验报告1

一、实验目的及要求

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

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

二、实验内容

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

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

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

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

顺序栈：

Status InitStack(SqStack &S)

{

S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));

if(!S.base)

return ERROR;

=S.base;

S.stacksize=STACK_INIT_SIZE;

return OK;

}

Status DestoryStack(SqStack &S)

{

free(S.base);

return OK;

}

Status ClearStack(SqStack &S)

{

=S.base;

return OK;

}

Status StackEmpty(SqStack S)

{

if(S.base==)

return OK;

return ERROR;

}

int StackLength(SqStack S)

{

return -S.base;

}

Status GetTop(SqStack S,ElemType &e)

{

if(-S.base>=S.stacksize)

{

S.base=(ElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));

if(!S.base) return ERROR;

=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;

}

*++=e;

return OK;

}

Status Push(SqStack &S,ElemType e)

{

if(-S.base>=S.stacksize)

{

S.base=(ElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));

if(!S.base)

return ERROR;

=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;

}

*++=e;

return OK;

}

Status Pop(SqStack &S,ElemType &e)

{

if(==S.base)

return ERROR;

e=*–;

return OK;

}

Status StackTraverse(SqStack S)

{

ElemType *p;

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

if(!p) return ERROR;

p=;

while(p!=S.base)//上面一个…

{

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("%ddata);

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.front++;

}

return OK;

}

数据结构实验报告2

一.实验内容：

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

二.实验目的：

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

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

s1=i;

for(i=1;i

{

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

}

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

for(i=1;i

{

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

}

s2=i;

for(i=1;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

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

{

p->weight=*w;

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

}

for(;i

{

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

}

for(i=n+1;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

{

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

cin>>n;

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

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

cout

for(i=1;i

{

cout

}

数据结构报告【篇3】

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

专业班级姓名学号

实验项目

实验一二叉树的应用

实验目的

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

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

访问和处理二叉树的运算。

实验内容

题目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）家谱输出函数：用括号表示法输出家谱

输出形式为：父和母（子，子）

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：如果不为空，则输出当前结点信息，

是否为空，如不为空则输出“和配偶信息。

”；

是否为空

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

7程序结束

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

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

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

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

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

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

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

。

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

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

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

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

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

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

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

实验测试结果及结果分析

（一）测试结果

（二）结果分析

数据结构报告【篇4】

实验报告;课程名称：数据结构班级：软件工程实验成绩：;1206;实验名称：打印机队列模拟学号：4848批;程序的设计;实验编号：实验一姓名：实验日期：5月2;一、实验目的;对队列的理解;对STL中的queue的使用;实验仿真一个网络打印过程;二、实验内容与实验步骤流程图;这个任务队列的测试使用STL队列适配器;具体地说,每一行中包含的信息是

这个任务队列的测试使用STL队列适配器。程序要求完成模拟的实现共享打印机。这个打印机使用先进先出队列。仿真是通过读取和处理事件数据文件的列表。一个有效的数据文件中的每一行包含信息打印作业和提交这份工作的时间。

具体地说,每一行中包含的信息是提交工作的时间(以秒为单位),和在页面的工作长及工作的计算机的名称。在模拟的开始,每个这些事件的每一个应该被程序所读，存储在继承工作负载队列。程序应该通过循环递增计数器或while-loop模拟时间的流逝。程序应该将计数器初始化为零,然后依次增加1秒。当模拟等于当前时间的打印作业的提交时间在工作队列的前面，一个打印作业完成。当这一切发生的时候,从工作队列取出这个事件,然后把它放在另一个队列对象。这个队列对象存储已完成的打印作业。当程序仿真其他的打印工作的时候，这些工作在队列等待。

#include “simulator.h”

protected:

queue waiting;

priority_queue priority_waiting;

public:

fifo(int seconds_per_page);

void simulate(string file);

};

bool operator

using namespace std;

fifo::fifo(int seconds_per_page):simulator(seconds_per_page){ }

void fifo::simulate(string file){

int finish_time = 0;

float agg_latency = 0;

int totaljob =0;

event evt;

if(file.find(“arbitrary”)!= string::npos){

string outfile =“arbitrary.out”;

ofstream osf(outfile.c_str());

loadworkload(file);

osf

for(int time =1;!waiting.empty()||!workload.empty();time++){ while(!workload.empty() && time ==

workload.front().arrival_time()){

evt= workload.front();

osf

workload.pop();

}

if(!waiting.empty() && time >= finish_time){

totaljob ++;

evt = waiting.front();

agg_latency += time - evt.arrival_time();

osf

finish_time = time + evt.getjob().getnumpages() * seconds_per_page;

}

osf

return;

}

if(file.find(“bigfirst”) != string::npos){

string outfile = “bigfirst.out”;

ofstream osf(outfile.c_str());

loadworkload(file);

=1;!priority_waiting.empty()||!workload.empty();time++){

while(!workload.empty() && time ==

workload.front().arrival_time()){

evt= workload.front();

osf

workload.pop();

}

if(!priority_waiting.empty() && time >= finish_time){

totaljob ++;

evt = priority_();

agg_latency += time - evt.arrival_time();

osf

finish_time = time + evt.getjob().getnumpages() * seconds_per_page; }

}

osf

return;

}

cerr

bool operator

return evtleft.getjob().getnumpages()

evtright.getjob().getnumpages();

经测试，功能较为完整。代码流程简图如下：

通过这次实验，我了解了有关队列方面的知识。掌握了队列的逻辑结构，抽象数据类型，队列的存储方式等。运用先进先出表，仿真了网络打印队列。这都使我对数据结构的学习有了新的认识与帮助。在实验过程中，我也遇到了许多困难，从开始时对队列运算的不熟悉，到逐渐查找资料，从而完成了实验;六、附录;-《数据结构与算法分析》以及网上资料;

逐渐查找资料，从而完成了实验。在今后的学习中，我将继续努力，加强对堆栈，队列等知识的学习，以达到精益求精。

数据结构报告【篇5】

设计题目：模拟计算器程序

学生姓名：谢先斌

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

专业：计算机科学与技术

班级：1班

学号：541007010144

指导教师：卢冰李晔

2012 年 6 月 21 日

郑州轻工业学院

课程设计任务书

题目模拟计算器程序

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

主要内容：

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

基本要求：

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

主要参考资料：

[第52页3.2.5表达式求值

完成期限： 2012年6月21日

指导教师签名：

课程负责人签名：

2012年 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 op>、=”结果来进行下一步的操作：''表示运算符和运算数各退栈一次并调用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函数的任意整型表达式的求解运算。

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

我在写本程序的过程中也遇到了很多的问题，当然本程序的.核心问题就是对两个栈的压出栈操作，需要做优先级判断，并要考虑什么时候进栈，什么时候出栈等操作。我采用了课本上第()AS=”共被开方数小于N、A、S等字符也进行了改进，最终本程序可以不区分大小写就完成相关操作。

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

七、源代码

# 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的干扰

}

数据结构报告【篇6】

数据结构报告

引言

数据结构是计算机科学中的一个重要概念，它是指数据元素之间的关系以及这些关系在计算机中的存储方式。数据结构的选择和设计直接影响到程序的运行效率和空间利用率。本报告将详细介绍数据结构的相关知识、应用及优化方法。

一、数据结构的概念和分类

数据结构是对计算机中数据的组织、存储和管理的方法的研究。它按照数据元素之间的关系可分为线性结构、非线性结构和文件结构。线性结构中的数据元素是一对一的关系，如数组、链表；非线性结构中的数据元素是一对多的关系，如树、图；文件结构是对数据进行存储和访问的方法，如顺序文件、索引文件。

二、常见数据结构的应用

1. 数组(Array)：数组是一种线性结构，它可以存储多个相同类型的元素。在计算机科学中，数组被广泛应用于存储和访问数据，如矩阵运算、图像处理等。

2. 链表(Linked List)：链表是一种线性结构，它通过指针将数据元素连接在一起。链表可以动态地调整大小，因此在需要频繁插入和删除元素的情况下，链表是一种常用的数据结构。

3. 栈(Stack)：栈是一种具有特定操作限制的线性结构，它遵循先进后出（LIFO）的原则。栈常用于程序的内存分配、表达式求值等场景。

4. 队列(Queue)：队列是一种具有特定操作限制的线性结构，它遵循先进先出（FIFO）的原则。队列常用于实现任务调度、消息传递等场景。

5. 树(Tree)：树是一种非线性结构，它由节点和边组成。树状结构的应用非常广泛，如文件系统、数据库索引等。

6. 图(Graph)：图是一种非线性结构，它由节点和边组成。图的应用涉及到网络、社交关系分析等领域。

三、数据结构的优化方法

1. 算法优化：选择合适的算法可以明显提高程序的执行效率。比如，在查找一个有序数组中的元素时，使用二分查找算法可以将时间复杂度降低为O(logN)，而不是简单的线性查找算法的O(N)。

2. 空间优化：合理利用存储空间是数据结构优化的一个重要方面。比如，对于稀疏矩阵，可以采用压缩存储的方式，只保存非零元素，从而减少内存消耗。

3. 缓存优化：利用计算机中的缓存机制可以提高程序的访问速度。比如，将最常用的数据放在缓存中，减少从内存读取数据的时间。

4. 并行优化：利用并行计算的特性可以加快程序的执行速度。比如，将大规模的计算任务分解为多个子任务，分配给多个处理器同时执行。

结论

数据结构是计算机科学中非常重要的一门学科，它对程序的性能和空间利用率有着直接影响。在实际的软件开发中，根据具体的需求选择合适的数据结构和优化方法可以提高程序的效率和用户体验。因此，深入理解数据结构的概念和分类，并学会应用优化方法，对于开发高效的软件应用至关重要。

数据结构报告【篇7】

问题描述：;四则运算表达式求值，将四则运算表达式用中缀表达式;一、需求分析：;输入输出格式：;输入格式：在字符界面上输入一个中缀表达式，回车表;请输入表达式：;输入一个中缀表达式;输出格式：如果该中缀表达式正确，那么在字符界面上;式，其中后缀表达式中两相邻操作数之间利用空格隔开;果不正确，在字符界面上输出

问题描述：

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

一、需求分析：

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)。

输入和输出的格式

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

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

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

输出逆波兰表达式

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

四、调试分析

略。

五、测试结果

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

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

运行程序时

提示输入表达式

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

输出

提示：逆波兰表达式为：

运算结果：

七、实验心得(可选)

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

附录(实验代码)：

#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

{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.pop ();

T->lchild = ();

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 = ();

while( !((exp[i]=='#') && (()=='#')) ) //与

{

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.pop ();

while(op!='('){

CrtSubTree(PTR, op);

op = (); OPTR.pop ();

数据结构报告【篇8】

数据结构报告

一、引言

数据结构是计算机科学中一门重要的基础学科，研究的是数据元素之间的关系以及数据元素的存储和操作方式。在计算机科学领域中应用广泛，如算法设计与分析、数据库系统、编译器、操作系统等都离不开数据结构。本报告旨在介绍数据结构的概念、特点和应用领域，以及在数据结构设计中常用的数据结构类型。

二、数据结构概述

数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。它不仅仅关注数据的存储方式，更关注数据的逻辑结构和操作方式。常见的数据结构有数组、链表、栈、队列、树和图等。数据结构的特点包括抽象性、逻辑性、物理性和动态性。数据结构的设计需要根据具体问题的特点选择合适的数据结构类型，以达到提高算法效率的目的。

三、数据结构的应用领域

1. 算法设计与分析：数据结构是算法的基础。合理选择数据结构类型，可以提高算法的效率和可读性。常用的数据结构类型有栈、队列、树和图等。

2. 数据库系统：数据结构在数据库系统中起着重要的作用。例如，关系型数据库使用B树和哈希表来组织和索引数据，提高数据的访问效率。

3. 编译器：编译器在代码的分析、优化和生成过程中需要使用数据结构来表示中间代码和符号表等。例如，语法分析阶段使用树状结构来表示源代码的语法结构。

4. 操作系统：操作系统中需要使用数据结构来管理进程、文件和内存等资源。例如，操作系统使用链表来管理进程的调度顺序。

五、常用的数据结构类型

1. 数组：数组是一种线性表数据结构，它的特点是连续存储的固定大小的元素。数组的元素可以通过下标来访问，具有随机访问的优势。但数组的插入和删除操作效率较低。

2. 链表：链表是一种通过指针将一组零散的内存块串联起来的数据结构。链表的元素可以动态增删，具有插入和删除的优势。但链表的访问时间复杂度较高。

3. 栈和队列：栈和队列是两种特殊的线性表数据结构。栈是一种后进先出（LIFO）的数据结构，只允许在栈顶进行插入和删除操作；队列是一种先进先出（FIFO）的数据结构，允许在队尾进行插入操作，在队头进行删除操作。

4. 树：树是一种非线性表数据结构，由节点和边组成。树的特点是层次性、唯一性和无环性。常见的树结构有二叉树、平衡二叉树和哈夫曼树等。

5. 图：图是一种非线性表数据结构，由节点和边组成。图的特点是多对多的关系。常见的图结构有有向图和无向图等。

六、结论

数据结构是计算机科学中一门重要的学科，研究的是数据元素之间的关系以及数据元素的存储和操作方式。数据结构的应用广泛，如算法设计与分析、数据库系统、编译器、操作系统等。合理选择数据结构类型，可以提高算法效率和系统性能。常见的数据结构类型有数组、链表、栈、队列、树和图等。在实际应用中，根据具体问题的特点选择合适的数据结构类型是关键。

数据结构报告【篇9】

数据结构报告

一、引言

数据结构是计算机科学中一个重要的概念，它研究的是数据组织、存储和管理的方式。在计算机程序设计与算法分析过程中，选择适合的数据结构并进行有效的数据组织可以提高程序的运行效率，并且计算机科学中许多重要的应用都依赖于数据结构的设计和实现。

本报告将介绍数据结构的基本概念、常用的数据结构以及它们的应用等内容，以便读者更好地理解和应用数据结构。

二、数据结构的基本概念

1. 数据结构的定义

数据结构是计算机科学领域研究各种数据的组织方式、存储结构和操作方法的学科。数据结构通过定义一种数据存储形式，并在该存储形式上定义一些操作，以实现对数据的管理和处理。

2. 数据结构的分类

数据结构可以分为线性结构和非线性结构两大类。线性结构包括线性表、栈和队列等，而非线性结构包括树和图等。

三、常用的数据结构

1. 线性表

线性表是最简单、最常用的数据结构之一，它包含一组有序的元素集合，元素之间存在前驱和后继关系。线性表的常用实现方式有数组和链表。线性表的应用非常广泛，例如数组用于存储多个相同类型的数据，链表用于实现链式存储结构。

2. 栈

栈是一种特殊的线性表，它的特点是元素的插入和删除操作只能在表的一端进行。栈的应用也非常广泛，例如用于实现递归算法、表达式求值等。

3. 队列

队列也是一种特殊的线性表，与栈不同的是，队列的插入操作在一端进行，删除操作在另一端进行。队列一般采用先进先出（FIFO）的原则，常用于模拟排队系统、任务调度等。

4. 树

树是一种非线性结构，它由节点（顶点）和连接节点的边组成。树的特点是一个节点可以有多个子节点，但每个节点只能有一个父节点。树的应用非常广泛，例如用于实现文件系统、数据库索引等。

5. 图

图是一种非线性结构，它由节点和连接节点的边组成，不同于树的是图中的节点之间可以有多个连接。图的应用也非常广泛，例如用于实现社交网络、网络拓扑分析等。

四、数据结构的应用

1. 数据库系统

数据库系统是当今计算机科学中应用最广泛的应用之一，它基于数据结构来组织和管理大量的数据，并支持各种复杂的查询和操作。数据库系统中常用的数据结构包括哈希表、B树、B+树等。

2. 算法和程序设计

在算法和程序设计过程中，选择合适的数据结构对程序的性能影响非常大。例如，如果需要对一个有序列表进行查找操作，使用二分查找树比使用线性表更高效。

3. 图像处理

图像处理涉及到大量的像素数据，为了高效地处理图像，需要选择和设计合适的数据结构。例如，用二维数组来表示图像的像素矩阵，用链表来表示图像的轮廓等。

五、总结

数据结构作为计算机科学中的重要概念，对于程序设计和算法分析具有重要意义。通过本报告的介绍，读者对数据结构的基本概念、常用的数据结构以及它们的应用有了更深入的了解。同时，了解数据结构的定义和分类，以及不同数据结构的特点和应用场景，对于选择和设计合适的数据结构有了一定的指导意义。

希望本报告对读者有所帮助，使他们在实际工作和学习中更好地应用和理解数据结构的知识。

数据结构报告【篇10】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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