数据结构报告精选。
数据结构报告【篇1】
首先你要知道什么是数据结构,学习数据结构的意义。这将是你学习的动力所在。计算机软件都用到了数据结构。所以,学好数据结构对于你将来从事计算机编程类的工作有十分重要的作用。
数据结构中的基本概念,你要一定清楚。平时要多看书,要在计算机上去调试程序,在调试的过程中,你才能发现自己的问题,然后及时解决。在上机调试的过程中,更要大胆尝试,注重运用。拿到一个题时,更要深入分析,尝试用不同的算法去设计。当然编程的时候,要注意格式。比如:变量一定要先定义后使用。变量的定义不要定义在中间。
算法与数据结构是紧密联系,所以你算法一定要会。如果你是学生,只需把课本上出现的搞懂就好了,比如线性表的插入,删除,查找算法,它都是固定的。你就要理解,当然你要学会画图。对于书中的内容要熟悉。
数据结构的大纲如下:线性表、栈和队列,串、数组和广义表、树与森林、图、还有就是查找和排序。简单的总结一下也就是它的逻辑结构:线性结构和非线性结构。这些基本的内容你如果搞懂了,你的数据结构也就学好了。
要严格要求自己。在学习算法的过程中,你要想它为什么要这样设计?它的优点在哪里?想着去改进算法,慢慢的的你的逻辑思维能力也就提高了。你会发现其实数据结构也就那么回事,不是很难。
有不懂得地方要及时请教老师,不要不懂装懂。不要放过任何一个细节,因为我的专业就是计算机,所以有很多都是深有体会。
首先你要清楚一周内所要做的事情,然后制定一张作息时间表。在表上填上那些非花不可的时间,如吃饭、睡觉、上课、娱乐等。安排这些时间之后,选定合适的、固定的时间用于学习,必须留出足够的时间来完成正常的阅读和课后作业。当然,学习不应该占据作息时间表上全部的空闲时间,总得给休息、业余爱好、娱乐留出一些时间,这一点对学习很重要。一张作息时间表也许不能解决你所有的问题,但是它能让你了解如何支配你这一周的时间,从而使你有充足的时间学习和娱乐。
这就意味着在你认真投入学习之前,先把要学习的内容快速浏览一遍,了解学习的大致内容及结构,以便能及时理解和消化学习内容。当然,你要注意轻重详略,在不太重要的地方你可以花少点时间,在重要的地方,你可以稍微放慢学习进程。
学习成绩好的学生很大程度上得益于在课堂上充分利用时间,这也意味着在课后少花些功夫。课堂上要及时配合老师,做好笔记来帮助自己记住老师讲授的内容,尤其重要的是要积极地独立思考,跟得上老师的思维。
课堂上做的笔记你要在课后及时复习,不仅要复习老师在课堂上讲授的重要内容,还要复习那些你仍感模糊的认识。如果你坚持定期复习笔记和课本,并做一些相关的习题,你定能更深刻地理解这些内容,你的记忆也会保持更久。定期复习能有效地提高你的考试成绩。
选择某个地方作你的学习之处,这一点很重要。它可以是你的单间书房或教室或图书馆,但是它必须是舒适的,安静而没有干扰。当你开始学习时,你应该全神贯注于你的功课,切忌“身在曹营心在汉”。
平时测验的目的主要看你掌握功课程度如何,所以你不要弄虚作假,而应心平气和地对待它。或许,你有一两次考试成绩不尽如人意,但是这不要紧,只要学习扎实,认真对待,下一次一定会考出好成绩来。通过测验,可让你了解下一步学习更需要用功夫的地方,更有助于你把新学的知识记得牢固。
数据结构报告【篇2】
数据结构(C语言版)实验报告;专业:计算机科学与技术、软件工程;学号:____201240703061_____;班级:_________软件二班________;姓名:________朱海霞__________;指导教师:___刘遵仁_____________;青岛大学信息工程学院;2013年10月;实验1;实验题目:顺序存储结构线性表的插入和删除;实验目
数据结构(C语言版) 实验报告
专业:计算机科学与技术、软件工程
学号:____201240703061___________________
班级:_________软件二班______________
姓名:________朱海霞______________
指导教师:___刘遵仁________________
青岛大学信息工程学院
2013年10月
实验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(iL.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(iL.length)return ERROR;
p=&(L.elem[i-1]);
e=*p;
q=L.elem+L.length-1;
for(++p;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
ListInsert_Sq(L,i,a[i-1]);
for(i=0;i
printf(" %d",L.elem[i]);
printf(" ");//插入9个数
ListInsert_Sq(L,3,24);
for(i=0;i
printf(" %d",L.elem[i]);
printf(" ");//插入一个数
int e;
ListDelete_Sq(L,2, e);
for(i=0;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
实验题目:单链表的插入和删除
实验目的:
了解和掌握线性表的逻辑结构和链式存储结构,掌握单链表的基本算法及相关的时间性能分析。
实验要求:
建立一个数据域定义为字符类型的单链表,在链表中不允许有重复的字符;根据输入的字符,先找到相应的结点,后删除之。
实验主要步骤:
理解给出的示例程序。
4、调试程序,并设计输入数据(如:A,C,E,F,H,J,Q,M),测试程序的如下功能:不允许重复字符的插入;根据输入的字符,找到相应的结点并删除。
5、修改程序:
(1) 增加插入结点的功能。
(“后插”法。
程序代码:
#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
p=L->next;
while(p!=NULL){
printf("%c ",p->data); p=p->next;
}//插入八个字符printf(" ;实验结果:;ACEFHJQU;ABCEFHJQU;ABEFHJQU;心得体会:;单链表是通过扫描指针P进行单链表的`操作;头指针唯;实验掌握栈的顺序存储结构和链式存储结构,以便在实;掌握栈的基本运算,如:入栈与出栈
}
}//插入八个字符 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.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
int StackEmpty(SqStack S)
{ // 若栈S为空栈,则返回TRUE,否则返回FALSE
if(==S.base)
return TRUE;
else
return FALSE;
}
int Push(SqStack &S, int e)
{ // 插入元素e为新的栈顶元素
if(-S.base>=S.stacksize) // 栈满,追加存储空间
{
S.base=(int *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int)); if(!S.base)
exit(OVERFLOW); // 存储分配失败
=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*()++=e;
return OK;
}
int Pop(SqStack &S,int &e)
{ // 若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR if(==S.base)
return ERROR;
e=*--;
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
实验题目:二叉树操作设计和实现
实验目的:
掌握二叉树的定义、性质及存储方式,各种遍历算法。
实验要求:
采用二叉树链表作为存储结构,完成二叉树的建立,先序、中序和后序以及按层次遍历的操作,求所有叶子及结点总数的操作。
实验主要步骤:
理解程序。
中序和后序以及按层次遍历序列,求所有叶子及结点总数。
程序代码:
实验结果:
心得体会:
实验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
实验题目:排序
实验目的:
掌握各种排序方法的基本思想、排序过程、算法实现,能进行时间和空间性能的分析,根据实际问题的特点和要求选择合适的排序方法。
实验要求:
实现直接排序、冒泡、直接选择、快速、堆、归并排序算法。比较各种算法的运行速度。
实验主要步骤:
程序代码
数据结构报告【篇3】
数据结构报告
一、引言
数据结构是计算机科学的核心内容之一,它是计算机算法和程序设计的基础,为我们理解和解决各类复杂问题提供了极为有力的工具。数据结构涉及诸多知识体系和理论模型,如线性表、树、图、堆、散列表等,通过对它们的深入学习和掌握,我们可以高效地解决各种实际问题。本篇报告主要针对数据结构的相关主题进行介绍和阐述,以帮助读者加深对数据结构知识的理解和掌握。
二、数据结构基础
1.常见的数据结构类型
数据结构类型主要包括线性结构和非线性结构两种,其中线性结构中又分为顺序结构和链式结构。常见的数据结构有数组、链表、栈、队列、树、图等。这些数据结构的应用涉及各种领域,如数据搜索、图像处理、人工智能等。
2.常见的数据结构操作
数据结构的基本操作包括增、删、查、改四个方面,以及一些高级操作如排序、查找、遍历、存储等。每种数据结构对应的操作有所不同,例如数组的插入操作需要移动元素,链表的插入操作则需要改变指针指向。
三、线性表
1.线性表的定义
线性表是由n个数据元素组成的有限序列,每个数据元素都有一个线性前驱和后继。线性表的元素可以是数字、字符或者其他任何类型的数据。
2.线性表的基本操作
线性表的基础操作包括插入、删除、查找、排序等。其中插入和删除操作是我们在使用线性表时最常见的操作,它们主要用来在线性表中增加或删除一个元素。线性表的查找操作广泛应用于各种场合,例如在字典中查找某个单词、在数据库中查找某条记录等。
四、树
1.树的定义
树是一种非线性的数据结构,它由n个节点组成,每个节点最多有一个父节点和多个子节点。如果一个节点没有父节点,则该节点是根节点;如果一个节点没有子节点,则该节点是叶子节点。树的每个节点都可以有自己的属性和方法,这使得树在很多领域都有着广泛的应用。
2.树的遍历
树的遍历是指对树中所有节点的访问操作,分为前序遍历、中序遍历和后序遍历三种。前序遍历是先访问根节点,然后按照从左到右的顺序访问子节点;中序遍历是按照从左到右的顺序依次访问树中每个节点;后序遍历是先访问子节点,然后访问根节点。
五、图
1.图的定义与分类
图是一种非线性的数据结构,它包含一组节点和一组边,每个边连接两个节点。图的节点包括顶点和边,顶点表示图的节点,边表示两个顶点间的关系。图可以分为有向图和无向图两种,有向图中的边是有方向的,而无向图中的边是无方向的。
2.图的遍历
图的遍历是指对图中所有节点的访问操作,分为深度优先搜索和广度优先搜索两种。深度优先搜索一般使用递归或栈的数据结构实现,它从一个初始节点开始依次访问每个节点的子节点,直到没有子节点为止。广度优先搜索一般使用队列的数据结构实现,它从一个初始节点开始向外扩展,访问每个节点的邻居节点,直到所有节点都被访问为止。
六、散列表
1.散列表的定义
散列表是一种根据关键字直接访问内存位置的数据结构。它的特点是查询操作的平均时间复杂度为O(1),这是由于散列表使用哈希函数将关键字映射到内存地址上。散列表主要有两个操作:插入和查找。插入操作将一个新元素插入到散列表中,查找操作根据关键字查找对应的元素。
2.散列表的哈希函数
哈希函数是散列表的关键部分,它将任意长度的输入值映射到固定长度的输出值。常见的哈希函数包括除留余数法、乘法散列法、平方取中法等。选择合适的哈希函数有助于提高散列表的查找效率和容错能力。
七、堆
1.堆的定义
堆是一种基于树形结构的数据结构,它可以被看做一个完全二叉树。堆可以分为最大堆和最小堆两种,最大堆中父节点的值大于等于两个子节点的值,最小堆中父节点的值小于等于两个子节点的值。堆主要用于解决如优先队列、图形算法等方面的问题。
2.堆的操作
堆的基本操作包括插入、删除和调整。插入操作将一个元素插入到堆中,删除操作将堆顶元素弹出,调整操作是将一个不满足堆的性质的堆变成满足堆性质的堆。其中调整操作通常使用堆排序算法实现。
八、数据结构的应用
数据结构广泛应用于各个领域,如软件开发、金融、生命科学、大数据等。在软件开发方面,数据结构的应用包括算法设计、数据管理、信息检索等。在金融方面,数据结构的应用包括股票市场预测、投资决策、模型优化等。在生命科学方面,数据结构的应用包括基因组学研究、蛋白质结构预测、药物发现等。在大数据方面,数据结构的应用包括海量数据处理、数据挖掘和机器学习等。
九、总结
本篇报告主要对数据结构的相关知识进行了介绍和阐述,包括线性表、树、图、散列表、堆等主题。这些数据结构在计算机科学中有着广泛的应用,可以帮助我们处理各种复杂问题,提高效率和准确性。希望本篇报告能够帮助读者更好地理解和掌握数据结构知识,并在实际应用中取得更好的效果。
数据结构报告【篇4】
数据结构实验报告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
}
数据结构报告【篇5】
数据结构
数据结构是计算机科学中的一个基础概念,用于描述数据之间的组织方式和关系。在计算机程序中,数据结构常用来存储和操作数据,可大大提高程序的效率和可靠性。本文将介绍数据结构的基本概念、常用算法和应用实例。
一、基本概念
1.数据类型
数据类型指数据的属性和操作集合。在计算机程序中,常用的数据类型包括整数、浮点数、字符串等。
2.数据结构
数据结构是一组数据的组织方式和关系。常见的数据结构包括数组、链表、栈、队列、树和图等。
3.算法
算法是解决问题的方法或步骤。在计算机程序中,常用的算法包括查找、排序、递归等。
二、常用算法
1.查找
在数据集合中查找指定的元素。常用的查找算法包括顺序查找、二分查找和哈希查找。
2.排序
对数据集合进行排序。常用的排序算法包括冒泡排序、插入排序、选择排序、快速排序和归并排序。
3.递归
通过递归调用自身来解决问题的方法。常见的递归应用包括树的遍历和图的遍历。
4.动态规划
将大问题分解为小问题,并找到最优解的方法。常见的应用包括背包问题和最长公共子序列问题。
三、应用实例
1.数据存储
数据结构被广泛应用于数据存储中。常见的应用包括数据库、文件系统和内存管理。
2.搜索引擎
搜索引擎是一种利用数据结构进行信息检索的工具。搜索引擎使用索引存储文本数据,并使用算法对索引进行搜索和排序。
3.图形图像处理
数据结构可用于处理图形和图像数据。常见的应用包括图像压缩和人脸识别。
四、总结
数据结构是计算机科学中的一个基础概念,其应用广泛,能够提高程序的效率和可靠性。本文介绍了数据结构的基本概念、常用算法和应用实例,希望能够为读者提供一个基本的了解和思路。
数据结构报告【篇6】
设计题目:模拟计算器程序
学生姓名:谢先斌
系 别:计算机与通信工程学院
专 业:计算机科学与技术
班 级: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的干扰
}
数据结构报告【篇7】
一、需求分析1、程序所实现的功能;2、程序的输入,包含输入的数据格式和说明;3、程序的输出,程序输出的形式;4、测试数据,如果程序输入的数据量比较大,需要给出测试数据;5、合作人及其分工二、设计说明1、主要的数据结构设计说明;2、程序的主要流程图;3、程序的主要模块,要求对主要流程图中出现的模块进行说明4、程序的主要函数及其伪代码说明(不需要完整的代码);5、合作人设计分工三、上机结果及体会1、合作人编码分工2、实际完成的情况说明(完成的功能,支持的数据类型等);3、程序的性能分析,包括时空分析;4、上机过程中出现的问题及其解决方案;5、程序中可以改进的地方说明;6、程序中可以扩充的功能及设计实现假想;说明:1、如果程序比较大,可以将设计说明分为概要设计和详细设计两部分。概要设计主要负责程序的流程、模块、抽象数据类型设计;详细设计负责程序的数据类型定义和主要函数的说明。2、设计说明中,不需要写出代码或者模块的详细代码,只需要写出主要函数的伪代码说明。
数据结构报告【篇8】
实验报告;课程名称:数据结构班级:软件工程实验成绩:;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
osf
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
osf
osf
return;
}
cerr
cerr
bool operator
return evtleft.getjob().getnumpages()
evtright.getjob().getnumpages();
经测试,功能较为完整。代码流程简图如下:
通过这次实验,我了解了有关队列方面的知识。掌握了队列的逻辑结构,抽象数据类型,队列的存储方式等。运用先进先出表,仿真了网络打印队列。这都使我对数据结构的学习有了新的认识与帮助。在实验过程中,我也遇到了许多困难,从开始时对队列运算的不熟悉,到逐渐查找资料,从而完成了实验;六、附录;-《数据结构与算法分析》以及网上资料;
逐渐查找资料,从而完成了实验。在今后的学习中,我将继续努力,加强对堆栈,队列等知识的学习,以达到精益求精。
数据结构报告【篇9】
数据结构报告
1. 引言
数据结构是计算机科学中的重要基础知识,它研究数据的组织和存储方式,以及对这些数据进行操作和处理的算法。在现代计算机应用中,更加高级的数据结构和算法往往可以提高程序的效率和性能。本报告将介绍数据结构的基本概念、常用的数据结构和其应用场景。
2. 数据结构的基本概念
2.1 数据和数据存储
数据是计算机科学中的基本概念,它可以是数字、文字、图像、声音等一切可以被处理和存储的信息。数据的存储方式有多种,包括顺序存储、链式存储、散列存储等。不同的存储方式有不同的优缺点,根据实际需求选择合适的存储方式非常重要。
2.2 记忆和处理数据的方法
计算机通常使用内存来存储和处理数据。在计算机内存中,数据的存储方式又可以分为顺序存储和链式存储。顺序存储适用于数据的长度固定且顺序不经常变化的场景,而链式存储则适用于数据的长度不定且经常需要插入、删除操作的场景。
3. 常用的数据结构
3.1 顺序表
顺序表是最基本的数据结构之一,它将数据元素顺序地存放在连续的存储单元中。顺序表支持随机访问,即可以通过下标直接访问到对应位置的数据元素,但插入和删除操作需要移动大量的数据元素,效率较低。
3.2 链表
链表是另一种常用的数据结构,它通过指针将数据元素连接起来。链表支持插入和删除操作的效率很高,但随机访问需要从头节点开始遍历,效率较低。
3.3 栈
栈是一种具有后进先出(LIFO)特性的数据结构,它可以用数组或链表实现。栈常用于表达式求值、函数调用和递归等场景。
3.4 队列
队列是一种具有先进先出(FIFO)特性的数据结构,它可以用数组或链表实现。队列常用于实现缓冲区、任务调度和广度优先搜索等场景。
3.5 树
树是一种非线性的数据结构,它由节点和连接节点的边组成。树具有层次关系,每个节点可以有多个子节点。树常用于表示文件系统、数据库索引和组织结构等场景。
3.6 图
图是一种更为复杂的数据结构,它由节点和连接节点的边组成。图可以用邻接矩阵或邻接表来表示,常用于表示网络、地图和社交关系等场景。
4. 数据结构的应用场景
4.1 排序算法
排序算法是数据结构的一项重要应用,它可以将一组无序的数据元素按照某个规则进行排序。常用的排序算法有冒泡排序、插入排序、选择排序、归并排序、快速排序等。
4.2 查找算法
查找算法是数据结构的另一个重要应用,它可以在一组数据中查找指定的元素。常用的查找算法有顺序查找、二分查找、哈希查找等。
4.3 图算法
图算法是数据结构的高级应用,它可以解决一些复杂的图相关问题,如最短路径、最小生成树、拓扑排序等。常用的图算法有深度优先搜索、广度优先搜索、Dijkstra算法、Prim算法等。
5. 结论
数据结构是计算机科学中的基础知识,它研究数据的组织和存储方式,以及对这些数据进行操作和处理的算法。本报告介绍了数据结构的基本概念、常用的数据结构和其应用场景。了解和掌握不同的数据结构可以提高程序的效率和性能,帮助我们更好地解决实际问题。
数据结构报告【篇10】
一、需求分析
1、 程序所实现的功能;
2、 程序的输入,包含输入的数据格式和说明;
3、 程序的输出,程序输出的形式;
4、 测试数据,如果程序输入的数据量比较大,需要给出测试数据;
5、 合作人及其分工
二、设计说明
1、 主要的数据结构设计说明;
2、 程序的主要流程图;
3、 程序的主要模块,要求对主要流程图中出现的模块进行说明
4、 程序的'主要函数及其伪代码说明 (不需要完整的代码) ;
5、 合作人设计分工
三、上机结果及体会
1、 合作人编码分工
2、 实际完成的情况说明(完成的功能,支持的数据类型等);
3、 程序的性能分析,包括时空分析;
4、 上机过程中出现的问题及其解决方案;
5、 程序中可以改进的地方说明;
6、 程序中可以扩充的功能及设计实现假想;
说明:
模块、抽象数据类型设计;详细设计负责程序的数据类型定义和主要函数的说明。
2、 设计说明中,不需要写出代码或者模块的详细代码,只需要写出主要函数的伪代码说明。