我们在平时的学习工作中,我们都需要书写报告，报告有利于上级机关对工作进行进一步的追踪与安排。报告正确写法是什么？以下内容是零思考方案网小编精心准备的“数据结构报告”，请您继续关注我们的网站我们将不断更新更多内容！
Introduction
Data structures are essential components of computer programming that define the way programs store and manage data. They enable developers to organize, manipulate, and retrieve data effectively, which is critical in making complex software systems. This report explores the main concepts, types, and applications of data structures.
Types of Data Structures
There are two main types of data structures: linear and non-linear. Linear data structures organize data in a sequence, such as arrays, linked lists, stacks, and queues. Non-linear data structures, on the other hand, organize data in a hierarchical or graph-like structure, such as trees, graphs, and heaps.
Arrays are the simplest and most commonly used linear data structures, and they store elements of the same data type in contiguous memory locations. Linked lists, on the other hand, allow dynamic memory allocation and store elements in non-contiguous nodes connected by pointers. Stacks and queues are used to implement algorithms that follow a Last-In-First-Out (LIFO) and First-In-First-Out (FIFO) approach, respectively.
Trees are non-linear data structures that organize data in a hierarchical structure and consist of nodes connected by edges. There are different types of trees, such as binary trees, AVL trees, and Red-Black trees, which have varying properties and applications. Graphs are also non-linear data structures that consist of vertices and edges and can be used to model relationships between entities. Heaps are used to store and manipulate priority queues, which prioritize elements based on their values.
Applications of Data Structures
Data structures have various applications in computer programming, such as:
1. Searching and Sorting: Many algorithms rely on data structures to search and sort data efficiently, such as binary search and quick sort algorithms.
2. Symbol Tables: Data structures such as Hash Tables and Binary Search Trees are used to implement symbol tables, which enable fast and efficient searching and retrieval of data.
3. Compiler Design: Data structures are used extensively in compiler design to parse, analyze, and optimize source code.
4. Graph Algorithms: Graphs are used to solve many real-world problems, such as routing problems, social network analysis, and recommendation systems.
5. Database Management: Data structures such as B-trees and Hash Indexes are used to organize and manage large amounts of data in databases.
Conclusion
Data structures are a fundamental component of computer programming that enable efficient and effective management of data. There are various types of data structures, including linear and non-linear structures, each with unique properties and applications. They are used extensively in many domains, such as compiler design, database management, and graph algorithms, to solve complex problems. Therefore, a thorough understanding of data structures is essential for any programmer who wants to create efficient and robust software systems.
问题描述：;四则运算表达式求值，将四则运算表达式用中缀表达式;一、需求分析：;输入输出格式：;输入格式：在字符界面上输入一个中缀表达式，回车表;请输入表达式：;输入一个中缀表达式;输出格式：如果该中缀表达式正确，那么在字符界面上;式，其中后缀表达式中两相邻操作数之间利用空格隔开;果不正确，在字符界面上输出
问题描述：
四则运算表达式求值，将四则运算表达式用中缀表达式，然后转换为后缀表达式，并计算结果。
一、 需求分析：
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
#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
{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 ();
1.下列程序段的时间复杂度为( )。
(A) O(m*n*t) (B) O(m+n+t) (C) O(m+n*t) (D) O(m*t+n)
2.设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动( )个元素。
(A) n-i (B) n+l -i (C) n-1-i (D) i
3.设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为( )。
(A) N1-1 (B) N2-1 (C) N2+N3 (D) N1+N3
4.利用直接插入排序法的思想建立一个有序线性表的时间复杂度为( )。
(A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(1og2n)
5.设指针变量p指向双向链表中结点A，指针变量s指向插入的结点X，则在结点A的后面插入结点X的操作序列为( )。
(A) p->right=s; s->left=p; p->right->left=s; s->right=p->right;
(B) s->left=p;s->right=p->right;p->right=s; p->right->left=s;
(C) p->right=s; p->right->left=s; s->left=p; s->right=p->right;
(D) s->left=p;s->right=p->right;p->right->left=s; p->right=s;
6.下列各种排序算法中平均时间复杂度为O(n2)是( )。
(A) 快速排序 (B) 堆排序 (C) 归并排序 (D) 冒泡排序
7.设输入序列1、2、3、…、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是( )。
(A) n-i (B) n-1-i (C) n+l -i (D) 不能确定
8.设散列表中有m个存储单元，散列函数H(key)= key % p，则p最好选择( )。
9.设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数为1的结点数有2个，那么度数为0的结点数有( )个。
10.设完全无向图中有n个顶点，则该完全无向图中有( )条边。
(A) n(n-1)/2 (B) n(n-1) (C) n(n+1)/2 (D) (n-1)/2
11.设顺序表的长度为n，则顺序查找的平均比较次数为( )。
(A) n (B) n/2 (C) (n+1)/2 (D) (n-1)/2
12.设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过( )次比较。
13.设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找长度为( )。
14.设有向无环图G中的有向边集合E={，，，}，则下列属于该有向图G的一种拓扑排序序列的是( )。
(A) 1，2，3，4 (B) 2，3，4，1 (C) 1，4，2，3 (D) 1，2，4，3
15.设有一组初始记录关键字序列为(34，76，45，18，26，54，92)，则由这组记录关键字生成的二叉排序树的深度为( )。
1.设指针p指向单链表中结点A，指针s指向插入的结点X，则在结点A的前面插入结点X时的操作序列为：
1) s->next=___________;2) p->next=s;3) t=p->data;
4) p->data=___________;5) s->data=t;
2.设某棵完全二叉树中有100个结点，则该二叉树中有______________个叶子结点。
3.设某顺序循环队列中有m个元素，且规定队头指针F指向队头元素的前一个位置，队尾指针R指向队尾元素的当前位置，则该循环队列中最多存储_______队列元素。
4.对一组初始关键字序列(40，50，95，20，15，70，60，45，10)进行冒泡排序，则第一趟需要进行相邻记录的比较的次数为__________，在整个排序过程中最多需要进行__________趟排序才可以完成。
5.在堆排序和快速排序中，如果从平均情况下排序的速度最快的角度来考虑应最好选择_________排序，如果从节省存储空间的.角度来考虑则最好选择________排序。
6.设一组初始记录关键字序列为(20，12，42，31，18，14，28)，则根据这些记录关键字构造的二叉排序树的平均查找长度是_______________________________。
7.设一棵二叉树的中序遍历序列为BDCA，后序遍历序列为DBAC，则这棵二叉树的前序序列为____________________。
8.设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为7、19、2、6、32、3、21、10，根据这些频率作为权值构造哈夫曼树，则这棵哈夫曼树的高度为________________。
9.设一组记录关键字序列为(80，70，33，65，24，56，48)，则用筛选法建成的初始堆为_______________________。
10. 10. 设无向图G(如右图所示)，则其最小生成树上所有边的权值之和为_________________。
3.子串“ABC”在主串“AABCABCD”中的位置为2。( )
4.若一个叶子结点是某二叉树的中序遍历序列的最后一个结点，则它必是该二叉树的先序遍历序列中的最后一个结点。( )
6.用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。( )
8.入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。( )
1.设计计算二叉树中所有结点值之和的算法。
2.设计将所有奇数移到所有偶数之前的算法。
3.设计判断单链表中元素是否是递增的算法。
二.实验目的：
1、使学生熟练掌握哈夫曼树的生成算法。
2、熟练掌握哈夫曼编码的方法。
三.问题描述：
已知n个字符在原文中出现的频率，求它们的哈夫曼编码。
1、读入n个字符，以及字符的权值，试建立一棵Huffman树。
2、根据生成的Huffman树，求每个字符的Huffman编码。并对给定的待编码字符序列进行编码，并输出。
typedef struct{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; //动态分配数组存储郝夫曼树
typedef char* *HuffmanCode;//动态分配数组存储郝夫曼编码
(2)主要的实现思路：
1.基本上没有什么太大的问题，在调用select这个函数时，想把权值最小的两个结点的序号带回HuffmanCoding，所以把那2个序号设置成了引用。
2.在编程过程中，在什么时候分配内存，什么时候初始化花的时间比较长
3.最后基本上实现后，发现结果仍然存在问题，经过分步调试，发现了特别低级的输入错误。把HT[i].weight=HT[s1].weight+HT[s2].weight;中的s2写成了i
typedef struct{
int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char* *HuffmanCode;
void Select(HuffmanTree &HT,int k,int &s1,int &s2)
{ int i;
i=1;
while(i
s1=i;
{
if(HT[i].parent==0&&HT[i].weight
{
if(HT[i].parent==0&&i!=s1)break;
}
s2=i;
{
if(HT[i].parent==0&&i!=s1&&HT[i].weight
}
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
{
int m,c,f,s1,s2,i,start;
char *cd;
if(n
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //0号单元未用，预分配m+1个单元
HuffmanTree p=HT+1;
{
p->weight=*w;
p->parent=p->rchild=p->lchild=0;
{
p->weight=p->parent=p->rchild=p->lchild=0;
{
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)); //分配求编码的工作空间
for(i=1;i
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) //从叶子到根逆向求编码
{
if(HT[f].lchild==c)cd[--start]='0';
cd[--start]='1';
}
HC[i]=(char*)malloc((n-start)*sizeof(char)); //为第i个字符编码分配空间
strcpy(HC[i],&cd[start]);//从cd复制编码到HC
HuffmanTree HT;
HuffmanCode HC;
cout
cin>>n;
w=(int*)malloc((n+1)*sizeof(int)); //记录权值，号单元未用
ch=(char*)malloc((n+1)*sizeof(char));//记录字符，号单元未用
cout
{
cout
}
数据结构报告
一、引言
数据结构是计算机科学中的一门重要课程，它研究的是数据之间的关系、组织方式以及它们在计算机中的存储和操作方法。在计算机科学与技术领域中，数据结构具有非常广泛的应用，它不仅能提高程序的运行效率，还能够解决各种实际问题。本报告将对数据结构进行介绍与论述，并深入探讨其相关主题。
二、数据结构的定义与分类
1. 数据结构的定义
数据结构是指一组数据的形式化描述，包括数据之间的关系和组织方式。它可以分为线性结构、非线性结构和文件结构三种类型。
2. 线性结构
线性结构是指数据元素之间存在一对一的关系，即每个数据元素最多只有一个直接前驱和一个直接后继。常见的线性结构有数组、链表、栈和队列等。
3. 非线性结构
非线性结构是指数据元素之间存在一对多或多对多的关系，即每个数据元素可以有多个直接前驱和直接后继。常见的非线性结构有树和图等。
4. 文件结构
文件结构是指将数据组织成文件的方式，常见的文件结构有顺序文件、索引文件和散列文件等。
三、常见数据结构及其应用
1. 数组
数组是一种线性结构，它将数据元素按顺序存储在连续的存储空间中。数组能够快速访问任意位置的元素，因此广泛应用于数据的存储和查找。
2. 链表
链表是一种线性结构，它通过指针将数据元素连接起来。链表可以动态地分配和释放存储空间，因此适用于频繁插入和删除操作的场景。
3. 栈
栈是一种特殊的线性结构，它遵循先进后出的原则。栈可以用于实现函数调用和递归等场景，还可以实现表达式求值和括号匹配等功能。
4. 队列
队列是一种特殊的线性结构，它遵循先进先出的原则。队列可以用于实现进程调度和任务管理等场景，还可以实现广度优先搜索等算法。
5. 树
树是一种非线性结构，它包含一个根节点和若干子节点，每个节点之间通过边连接。树可以用于实现文件系统、数据库索引和算法设计等领域。
6. 图
图是一种非线性结构，它包含若干个顶点和边，顶点之间可以通过边相连。图可以用于实现社交网络分析、路由算法和最短路径等问题。
四、数据结构的时间复杂度与空间复杂度
时间复杂度是衡量算法执行效率的指标，它表示算法的运行时间与问题规模的增长关系。空间复杂度是衡量算法占用空间的指标，它表示算法所需存储空间与问题规模的增长关系。在设计和分析算法时，我们需要考虑时间复杂度和空间复杂度，以便选择合适的数据结构和算法。
五、数据结构在实际问题中的应用
数据结构在实际问题中有广泛应用，例如：
1. 文件系统
文件系统通常采用树型结构，将文件和目录组织成一棵树。通过树的层次关系，可以实现文件的查找、编辑和删除等操作。
2. 数据库索引
数据库通常采用树型索引结构，通过树的层次关系，可以快速查找和检索数据库中的数据。
3. 网络路由
路由器采用图的结构来管理网络中的路由信息，通过图的遍历算法来选择最短路径和高效路由。
4. 排序算法
排序算法通常使用数组或链表来存储数据，通过比较和交换操作来实现数据的排序。
六、结论
数据结构是计算机科学中的重要课程，它研究的是数据之间的关系、组织方式以及它们在计算机中的存储和操作方法。数据结构有多种类型，包括线性结构、非线性结构和文件结构。不同的数据结构适用于不同的场景，能够提高程序的运行效率和解决实际问题。在设计和分析算法时，我们需要考虑时间复杂度和空间复杂度，以便选择合适的数据结构和算法。数据结构在实际问题中有广泛应用，包括文件系统、数据库索引、网络路由和排序算法等。通过深入学习和理解数据结构，我们能够更好地应对计算机科学与技术领域中的各种挑战和问题。
数据结构报告
一、引言
数据结构是计算机科学的核心内容之一，它是计算机算法和程序设计的基础，为我们理解和解决各类复杂问题提供了极为有力的工具。数据结构涉及诸多知识体系和理论模型，如线性表、树、图、堆、散列表等，通过对它们的深入学习和掌握，我们可以高效地解决各种实际问题。本篇报告主要针对数据结构的相关主题进行介绍和阐述，以帮助读者加深对数据结构知识的理解和掌握。
二、数据结构基础
1.常见的数据结构类型
数据结构类型主要包括线性结构和非线性结构两种，其中线性结构中又分为顺序结构和链式结构。常见的数据结构有数组、链表、栈、队列、树、图等。这些数据结构的应用涉及各种领域，如数据搜索、图像处理、人工智能等。
2.常见的数据结构操作
数据结构的基本操作包括增、删、查、改四个方面，以及一些高级操作如排序、查找、遍历、存储等。每种数据结构对应的操作有所不同，例如数组的插入操作需要移动元素，链表的插入操作则需要改变指针指向。
三、线性表
1.线性表的定义
线性表是由n个数据元素组成的有限序列，每个数据元素都有一个线性前驱和后继。线性表的元素可以是数字、字符或者其他任何类型的数据。
2.线性表的基本操作
线性表的基础操作包括插入、删除、查找、排序等。其中插入和删除操作是我们在使用线性表时最常见的操作，它们主要用来在线性表中增加或删除一个元素。线性表的查找操作广泛应用于各种场合，例如在字典中查找某个单词、在数据库中查找某条记录等。
四、树
1.树的定义
树是一种非线性的数据结构，它由n个节点组成，每个节点最多有一个父节点和多个子节点。如果一个节点没有父节点，则该节点是根节点；如果一个节点没有子节点，则该节点是叶子节点。树的每个节点都可以有自己的属性和方法，这使得树在很多领域都有着广泛的应用。
2.树的遍历
树的遍历是指对树中所有节点的访问操作，分为前序遍历、中序遍历和后序遍历三种。前序遍历是先访问根节点，然后按照从左到右的顺序访问子节点；中序遍历是按照从左到右的顺序依次访问树中每个节点；后序遍历是先访问子节点，然后访问根节点。
五、图
1.图的定义与分类
图是一种非线性的数据结构，它包含一组节点和一组边，每个边连接两个节点。图的节点包括顶点和边，顶点表示图的节点，边表示两个顶点间的关系。图可以分为有向图和无向图两种，有向图中的边是有方向的，而无向图中的边是无方向的。
2.图的遍历
图的遍历是指对图中所有节点的访问操作，分为深度优先搜索和广度优先搜索两种。深度优先搜索一般使用递归或栈的数据结构实现，它从一个初始节点开始依次访问每个节点的子节点，直到没有子节点为止。广度优先搜索一般使用队列的数据结构实现，它从一个初始节点开始向外扩展，访问每个节点的邻居节点，直到所有节点都被访问为止。
六、散列表
1.散列表的定义
散列表是一种根据关键字直接访问内存位置的数据结构。它的特点是查询操作的平均时间复杂度为O(1)，这是由于散列表使用哈希函数将关键字映射到内存地址上。散列表主要有两个操作：插入和查找。插入操作将一个新元素插入到散列表中，查找操作根据关键字查找对应的元素。
2.散列表的哈希函数
哈希函数是散列表的关键部分，它将任意长度的输入值映射到固定长度的输出值。常见的哈希函数包括除留余数法、乘法散列法、平方取中法等。选择合适的哈希函数有助于提高散列表的查找效率和容错能力。
七、堆
1.堆的定义
堆是一种基于树形结构的数据结构，它可以被看做一个完全二叉树。堆可以分为最大堆和最小堆两种，最大堆中父节点的值大于等于两个子节点的值，最小堆中父节点的值小于等于两个子节点的值。堆主要用于解决如优先队列、图形算法等方面的问题。
2.堆的操作
堆的基本操作包括插入、删除和调整。插入操作将一个元素插入到堆中，删除操作将堆顶元素弹出，调整操作是将一个不满足堆的性质的堆变成满足堆性质的堆。其中调整操作通常使用堆排序算法实现。
八、数据结构的应用
数据结构广泛应用于各个领域，如软件开发、金融、生命科学、大数据等。在软件开发方面，数据结构的应用包括算法设计、数据管理、信息检索等。在金融方面，数据结构的应用包括股票市场预测、投资决策、模型优化等。在生命科学方面，数据结构的应用包括基因组学研究、蛋白质结构预测、药物发现等。在大数据方面，数据结构的应用包括海量数据处理、数据挖掘和机器学习等。
九、总结
本篇报告主要对数据结构的相关知识进行了介绍和阐述，包括线性表、树、图、散列表、堆等主题。这些数据结构在计算机科学中有着广泛的应用，可以帮助我们处理各种复杂问题，提高效率和准确性。希望本篇报告能够帮助读者更好地理解和掌握数据结构知识，并在实际应用中取得更好的效果。
一、需求分析1、程序所实现的功能；2、程序的输入，包含输入的数据格式和说明；3、程序的输出，程序输出的形式；4、测试数据，如果程序输入的数据量比较大，需要给出测试数据；5、合作人及其分工二、设计说明1、主要的数据结构设计说明；2、程序的主要流程图；3、程序的主要模块，要求对主要流程图中出现的模块进行说明4、程序的主要函数及其伪代码说明(不需要完整的代码)；5、合作人设计分工三、上机结果及体会1、合作人编码分工2、实际完成的情况说明（完成的功能，支持的数据类型等）；3、程序的性能分析，包括时空分析；4、上机过程中出现的问题及其解决方案；5、程序中可以改进的地方说明；6、程序中可以扩充的功能及设计实现假想；说明：1、如果程序比较大，可以将设计说明分为概要设计和详细设计两部分。概要设计主要负责程序的流程、模块、抽象数据类型设计；详细设计负责程序的数据类型定义和主要函数的说明。2、设计说明中，不需要写出代码或者模块的详细代码，只需要写出主要函数的伪代码说明。
数据结构是计算机科学中非常重要的一门基础课程，它研究的是数据的存储、组织和管理方式。本文将针对数据结构这一主题展开一系列讨论，介绍数据结构的基本概念、常用算法以及实际应用场景。
一、数据结构的基本概念
1.1 数据类型
数据类型是数据结构中最基本的概念之一，它指的是数据存储的格式和类型。常见的数据类型包括整型、浮点型、字符型等。
1.2 数据结构
数据结构指的是一种数据的组织方式，它可以简单地理解为按一定规律组织数据的方法。常见的数据结构包括数组、链表、树、图等。
1.3 算法
算法是一种用于解决特定问题的过程或方法，它可以用某种语言来描述。不同的算法适用于不同的问题，比如排序、查找、计算等。
二、常用数据结构算法
2.1 排序算法
排序算法是数据结构中最基本和常见的算法之一，它可以对一系列数据进行排序，以便于后续的查找和管理。常见的排序算法有冒泡排序、快速排序、插入排序等。
2.2 查找算法
查找算法是在一组数据中搜索指定数据的过程，常见的查找算法有顺序查找、二分查找等。
2.3 哈希算法
哈希算法是一种常见的数据加密和解密算法，它通过对数据进行一定方式的计算，将其变成一个固定长度的字符串，用于保障数据的安全性。
三、数据结构在实际应用中的应用场景
3.1 图像处理
图像处理是一项对图片进行操作和优化的技术，它需要使用到很多数据结构，比如数组、链表等，用于存储和处理图片的颜色、像素等信息。
3.2 网络通信
网络通信是一个重要的应用场景，它需要使用到很多数据结构，比如树、图等用于存储和处理网络的拓扑结构、路由算法等。
3.3 数据库管理
数据库是一个存储、管理和检索数据的系统，它需要使用到很多数据结构，比如哈希表、B-Tree等，用于快速地检索数据、管理索引等。
综上所述，数据结构是计算机科学中一个非常重要的基础课程，它研究的是数据的存储、组织和管理方式。在实际应用中，数据结构有着广泛的应用场景，包括图像处理、网络通信、数据库管理等。掌握数据结构的基本概念和常用算法，对于提高算法设计和编程能力有着巨大的帮助。
设计题目：模拟计算器程序
学生姓名：谢先斌
系 别：计算机与通信工程学院
专 业：计算机科学与技术
班 级：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
# 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的干扰
}
相关推荐 更多 +
最新更新 更多 +