编写报告能让我们对自己未来的工作有更透彻的理解,随着人们自身素质提升。我们通常会使用到报告,撰写报告需要注意哪些内容呢?出国留学网的编辑认真整理了大量信息推出了这篇数据结构报告,本文供你参考,希望能帮到你!
数据结构报告【篇1】
一、实验目的及要求
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("括号匹配成功!\n\n");
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)
数据结构报告【篇2】
一、实验目的:
了解哈夫曼树的思想和相关概念;
1.初始化:能够对输入的任意长度的字符串s进行统计,统计每个字符的频度,并建立哈夫曼树。
2.建立编码表:利用已经建好的哈夫曼树进行编码,并将每个字符的编码输出。
3.编码:根据编码表对输入的字符串进行编码,并将编码后的字符串输出。
4.译码:利用已经建好的哈夫曼树对编码后的字符串进行译码,并输出译码结果。
6.计算输入的字符串编码前和编码后的长度,并进行分析,讨论哈夫曼编码的压缩效果。
7.用户界面可以设计成“菜单”方式,能进行交互,根据输入的字符串中每个字符出现的次数统计频度,对没有出现的字符一律不用编码。
Data:
哈夫曼树类的数据域,继承节点类型为int的二叉树 class HuffmanTree:public BiTreedata:
struct BiNode //二叉树的结点结构 {
};
待编码字符串由键盘输入,输入时用链表存储,链表节点为 struct Node
1.初始化函数(void HuffmanTree::Init(string Input))
2.获得输入字符串的第一个字符,并将其插入到链表尾部,n=1(n记录的是链表
3.1 将当前取出的字符与链表中已经存在的字符逐个比较,如果当前取出
的字符与链表中已经存在的某个字符相同,则链表中该字符的权值加1。
3.2 如果当前取出的字符与链表中已经存在的字符都不相同,则将其加入
到链表尾部,同时n++
4.tSize=n(tSize记录链表中字符总数,即哈夫曼树中叶子节点总数)
源代码:
{
Node *front=new Node; //初始化链表的头结点
throw exception(“堆空间用尽”);
front->next=NULL;
front->character=NULL;
front->count=0;
Node *pfront=front;
Node* New1=new Node;
throw exception(“堆空间用尽”);
New1->character=ch; //将第一个字符插入链表
New1->count=1;
New1->next=pfront->next;
pfront->next=New1;
bool replace=0; //判断在已经写入链表的字符中是否有与当前读出的字符相同的字符 int n=1; //统计链表中字符个数
{
pfront=pfront->next;
if((int)pfront->character == (int)ch) //如果在链表中有与当前字符相同的字符,
{
pfront->count++;
replace=1;
break;
}
}while(pfront->next);
if(!replace) //如果在链表中没找到与当前字符相同的字符,则将该字符作为新成 员插入链表
{
Node* New=new Node;
throw exception(“堆空间用尽”);
New->character=ch;
New->count=1;
New->next=pfront->next;
pfront->next=New;
n++;
}
pfront=front; //重置pfront和replace变量为默认值 replace=0;
}
pfront=front;
{
front=pfront;
pfront=pfront->next;
front;
}
时间复杂度:
2.创建哈夫曼树(void HuffmanTree::CreateCodeTable(Node *p))
算法伪代码:
2. 将存储字符及其权值的链表中的字符逐个写入三叉链表的前tSize个结点
3.1 从存储字符及其权值的链表中取出两个权值最小的结点x,y,记录其
下标x,y。
3.3 将下标为x的结点设置为i结点的左孩子,将下标为y的结点设置为
源代码:
void HuffmanTree::CreateHTree(Node *p,int n)
{
root= new BiNode[2*n-1]; //初始化哈夫曼树
Node *front=p->next;
throw exception(“没有输入字符”);
root[i].data=front->count;
root[i].lchild=-1;
root[i].rchild=-1;
root[i].parent=-1;
front=front->next;
}
front=p;
int New1,New2;
{
SelectMin(New1,New2,0,i); //从0~i中选出两个权值最小的结点
root[New1].parent=root[New2].parent=i; //用两个权值最小的结点生成新结点,
root[i].data=root[New1].data+root[New2].data;//新结点的权值为其孩子的权值的和 root[i].lchild=New1;
root[i].rchild=New2;
root[i].parent=-1;
}
}
时间复杂度:
在选取两个权值最小的结点的函数中要遍历链表,时间复杂度为O(n),故该函数
3.创建编码表(void HuffmanTree::CreateCodeTable(Node *p))
2.4.1 如果当前叶子结点是其双亲的左孩子,则其对应的编码为0,否
2.4.2 child指针指向叶子结点的双亲,parent指针指向child指针的双亲,
源代码:
void HuffmanTree::CreateCodeTable(Node *p)
{
HCodeTable=new HCode[tSize]; //初始化编码表
Node *front=p->next;
{
HCodeTable[i].data=front->character; //将第i个字符写入编码表
int parent=root[i].parent; //得到第i个字符对应的叶子节点的双亲
int k=0;
if(tSize==1) //如果文本中只有一种字符,它的编码为0
{
HCodeTable[i].code[k]='0';
k++;
}
while(parent!=-1) //从第i个字符对应的叶子节点开始,寻找它到根结点的路径
{
if(child==root[parent].lchild) //如果当前结点为双亲的左孩子,则编码为0,
HCodeTable[i].code[k]='0';
HCodeTable[i].code[k]='1';
k++;
child=parent;
parent=root[child].parent;
}
HCodeTable[i].code[k]='';
Reverse(HCodeTable[i].code); //将编码逆置
}
{
cout
parent=root[parent].lchild;
parent=root[parent].rchild;
i++;
}
if(tSize==1) //如果编码表只有一个字符,则根结点即为叶子结点 i++;
d.append(1,HCodeTable[parent].data);//将叶子节点对应的字符追加到解码串中 }
cout
}
时间复杂度:
8. 计算哈夫曼编码的压缩比(void HuffmanTree::Calculate(string s1,string s2)) 算法伪代码:
2. 获得编码后的字符串的长度,将其除以8然后向上取整,得到其占用的字
源代码:
void HuffmanTree::Calculate(string s1,string s2)
{
int cal1=s1.length();
int cal2=s2.length();
cal2=ceill((float)cal2/8); //将编码串的比特数转化为字节数 cout
cout
cout
9. 打印哈夫曼树(void HuffmanTree::PrintTree(int TreeNode,int layer) ) 算法伪代码:
3. 根据当前结点所在的层次确定其前面要输出多少空格,先输出空格,在打
源代码:
void HuffmanTree::PrintTree(int TreeNode,int layer)
{
if(TreeNode==-1) //如果待打印结点为空,则返回 return;
{
PrintTree(root[TreeNode].rchild,layer+1); //先打印该结点的右子树,layer记录
cout
cout
PrintTree(root[TreeNode].lchild,layer+1); //打印该结点的左子树
}
}
10. 菜单函数(void HuffmanTree::Menu())
算法伪代码:
1. 逐一读取键盘缓存区中的字符,并将它们逐一追加到记录输入字符串的
3.利用string变量创建哈夫曼树,初始化编码表。
cout
string Input;
char letter;
{
letter=cin.get();
Input.append(1,letter);
}while(letter!=' ');
Input.erase(Input.length()-1,1); //去掉Input末尾的回车符
Init(Input); //根据输入的字符串创建哈夫曼树及其编码表 cout
PrintTree(2*tSize-1-1,1); //打印哈夫曼树
cout
string d1,d2;
cout
cout
cout
Calculate(Input,d1); //计算编码前后的压缩比
1.由于题目要求能输入任意长的字符串,所以本程序采用了string变量来记录输入
2.打印哈夫曼树时采用了递归函数,且采用了凹凸表的形式打印哈夫曼树。
主函数流程图:
经过这次实验,我了解了哈夫曼树的创建过程,了解了一种不等长编码的方法,用设断点调试的方法更加熟练,同时熟悉了STL中string类型的用法,对C++更加熟悉
数据结构报告【篇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
}
数据结构报告【篇4】
首先你要知道什么是数据结构,学习数据结构的意义。这将是你学习的动力所在。计算机软件都用到了数据结构。所以,学好数据结构对于你将来从事计算机编程类的工作有十分重要的作用。
数据结构中的基本概念,你要一定清楚。平时要多看书,要在计算机上去调试程序,在调试的过程中,你才能发现自己的问题,然后及时解决。在上机调试的过程中,更要大胆尝试,注重运用。拿到一个题时,更要深入分析,尝试用不同的算法去设计。当然编程的时候,要注意格式。比如:变量一定要先定义后使用。变量的定义不要定义在中间。
算法与数据结构是紧密联系,所以你算法一定要会。如果你是学生,只需把课本上出现的搞懂就好了,比如线性表的插入,删除,查找算法,它都是固定的。你就要理解,当然你要学会画图。对于书中的内容要熟悉。
数据结构的大纲如下:线性表、栈和队列,串、数组和广义表、树与森林、图、还有就是查找和排序。简单的总结一下也就是它的逻辑结构:线性结构和非线性结构。这些基本的内容你如果搞懂了,你的数据结构也就学好了。
要严格要求自己。在学习算法的过程中,你要想它为什么要这样设计?它的优点在哪里?想着去改进算法,慢慢的的你的逻辑思维能力也就提高了。你会发现其实数据结构也就那么回事,不是很难。
有不懂得地方要及时请教老师,不要不懂装懂。不要放过任何一个细节,因为我的专业就是计算机,所以有很多都是深有体会。
首先你要清楚一周内所要做的事情,然后制定一张作息时间表。在表上填上那些非花不可的时间,如吃饭、睡觉、上课、娱乐等。安排这些时间之后,选定合适的、固定的时间用于学习,必须留出足够的时间来完成正常的阅读和课后作业。当然,学习不应该占据作息时间表上全部的空闲时间,总得给休息、业余爱好、娱乐留出一些时间,这一点对学习很重要。一张作息时间表也许不能解决你所有的问题,但是它能让你了解如何支配你这一周的时间,从而使你有充足的时间学习和娱乐。
这就意味着在你认真投入学习之前,先把要学习的内容快速浏览一遍,了解学习的大致内容及结构,以便能及时理解和消化学习内容。当然,你要注意轻重详略,在不太重要的地方你可以花少点时间,在重要的地方,你可以稍微放慢学习进程。
学习成绩好的学生很大程度上得益于在课堂上充分利用时间,这也意味着在课后少花些功夫。课堂上要及时配合老师,做好笔记来帮助自己记住老师讲授的内容,尤其重要的是要积极地独立思考,跟得上老师的思维。
课堂上做的笔记你要在课后及时复习,不仅要复习老师在课堂上讲授的重要内容,还要复习那些你仍感模糊的认识。如果你坚持定期复习笔记和课本,并做一些相关的习题,你定能更深刻地理解这些内容,你的记忆也会保持更久。定期复习能有效地提高你的考试成绩。
选择某个地方作你的学习之处,这一点很重要。它可以是你的单间书房或教室或图书馆,但是它必须是舒适的,安静而没有干扰。当你开始学习时,你应该全神贯注于你的功课,切忌“身在曹营心在汉”。
平时测验的目的主要看你掌握功课程度如何,所以你不要弄虚作假,而应心平气和地对待它。或许,你有一两次考试成绩不尽如人意,但是这不要紧,只要学习扎实,认真对待,下一次一定会考出好成绩来。通过测验,可让你了解下一步学习更需要用功夫的地方,更有助于你把新学的知识记得牢固。
数据结构报告【篇5】
一、需求分析1、程序所实现的功能;2、程序的输入,包含输入的数据格式和说明;3、程序的输出,程序输出的形式;4、测试数据,如果程序输入的数据量比较大,需要给出测试数据;5、合作人及其分工二、设计说明1、主要的数据结构设计说明;2、程序的主要流程图;3、程序的主要模块,要求对主要流程图中出现的模块进行说明4、程序的主要函数及其伪代码说明(不需要完整的代码);5、合作人设计分工三、上机结果及体会1、合作人编码分工2、实际完成的情况说明(完成的功能,支持的数据类型等);3、程序的性能分析,包括时空分析;4、上机过程中出现的问题及其解决方案;5、程序中可以改进的地方说明;6、程序中可以扩充的功能及设计实现假想;说明:1、如果程序比较大,可以将设计说明分为概要设计和详细设计两部分。概要设计主要负责程序的流程、模块、抽象数据类型设计;详细设计负责程序的数据类型定义和主要函数的说明。2、设计说明中,不需要写出代码或者模块的详细代码,只需要写出主要函数的伪代码说明。
数据结构报告【篇6】
1)掌握栈和队列这两种特殊的线性表,熟悉它们的特性,在实际问题背景下灵活运用它们。
本实验训练的要点是“栈”和“队列”的观点;
1) 利用栈,实现数制转换。
2) 利用栈,实现任一个表达式中的语法检查(选做)。
3) 编程实现队列在两种存储结构中的基本操作(队列的初始化、判队列空、入队列、出队列);
顺序栈:
Status InitStack(SqStack &S)
{
S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));
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;
}
return OK;
return ERROR;
}
{
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));
return ERROR;
=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*++=e;
return OK;
}
Status Pop(SqStack &S,ElemType &e)
return ERROR;
e=*--;
return OK;
}
{
ElemType *p;
p=(ElemType *)malloc(sizeof(ElemType));
if(!p) return ERROR;
p=;
while(p!=S.base)//上面一个...
{
p--;
printf(“%d ”,*p);
}
return OK;
}
{
int flag,TURE=OK,FALSE=ERROR;
ElemType e,x;
InitStack(S);
flag=OK;
while((x= getchar)!='#'&&flag)
case '{':
printf(“括号匹配成功!nn”);
break;
printf(“没有满足条件n”);
flag=FALSE;
}
break;
break;
break;
}
}
if (flag && x=='#' && StackEmpty(S))
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)
{
Q.rear=Q.front->next;
free(Q.front);
Q.front=Q.rear;
}
return OK;
}
Status QueueEmpty(LinkQueue &Q)
{
return OK;
return ERROR;
}
{
int i=0;
QueuePtr p,q;
p=Q.front;
{
i++;
p=Q.front;
q=p->next;
p=q;
}
return i;
}
Status GetHead(LinkQueue Q,ElemType &e)
{
QueuePtr p;
p=Q.front->next;
return ERROR;
e=p->data;
return e;
}
Status ClearQueue(LinkQueue &Q)
{
QueuePtr p;
{
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));
return ERROR;
p->data=e;
p->next=NULL;
Q.rear->next = p;
return OK;
}
Status DeQueue(LinkQueue &Q,ElemType &e)
{
QueuePtr p;
return ERROR;
p = Q.front->next;
e = p->data;
Q.front->next = p->next;
Q.rear = Q.front; //只有一个元素时(不存在指向尾指针)
free (p);
return OK;
}
Status QueueTraverse(LinkQueue Q)
{
QueuePtr p,q;
{
printf(“这是一个空队列!n”);
return ERROR;
}
p=Q.front->next;
{
q=p;
printf(“%ddata);
q=p->next;
p=q;
}
return OK;
}
循环队列:
Status InitQueue(SqQueue &Q)
{
Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));
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)
return ERROR;
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAXQSIZE;
return OK;
}
{
return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}
Status DestoryQueue(SqQueue &Q)
{
free(Q.base);
return OK;
}
Status QueueEmpty(SqQueue Q) //判空
return OK;
return ERROR;
}
printf(“这是一个空队列!”);
Q.front++;
}
return OK;
}
数据结构报告【篇7】
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,同时取其右结点
数据结构报告【篇8】
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.设计判断单链表中元素是否是递增的算法。
数据结构报告【篇9】
1.判断链表是否存在环型链表问题:判断一个链表是否存在环,例如下面这个链表就存在一个环:
例如N1->N2->N3->N4->N5->N2就是一个有环的链表,环的开始结点是N5这里有一个比较简单的解法,设置两个指针p1,p2。每次循环p1向前走一步,p2向前走两步。直到p2碰到NULL指针或者两个指针相等结束循环。如果两个指针相等则说明存在环。
{
int data;
link* next;
};
{
link* p1=head, *p2 = head;
if (head ==NULL || head->next ==NULL)
{
return false;
}
do{
p1= p1->next;
p2 = p2->next->next;
} while(p2 && p2->next && p1!=p2);
return false;
}
2,链表反转 单向链表的反转是一个经常被问到的一个面试题,也是一个非常基础的问题。比如一个链表是这样的: 1->2->3->4->5 通过反转后成为5->4->3->2->1。最容易想到的方法遍历一遍链表,利用一个辅助指针,存储遍历过程中当前指针指向的下一个元素,然后将当前节点元素的指针反转后,利用已经存储的指针往后面继续遍历。源代码如下:
struct linka {
int data;
linka* next;
};
return;
linka*pre, *cur, *ne;
pre=head;
cur=head->next;
{
ne = cur->next;
cur->next = pre;
pre = cur;
cur = ne;
}
head->next = NULL;
head = pre;
}
还有一种利用递归的方法。这种方法的基本思想是在反转当前节点之前先调用递归函数反转后续节点。源代码如下。不过这个方法有一个缺点,就是在反转后的最后一个结点会形成一个环,所以必须将函数的返回的节点的next域置为NULL。因为要改变head指针,所以我用了引用。算法的源代码如下:
linka* reverse(linka* p,linka*& head)
{
if(p == NULL || p->next == NULL)
{
head=p;
{
linka* tmp = reverse(p->next,head);
tmp->next = p;
return p;
}
}
3,判断两个数组中是否存在相同的数字 给定两个排好序的数组,怎样高效得判断这两个数组中存在相同的数字?
这个问题首先想到的是一个O(nlogn)的算法。就是任意挑选一个数组,遍历这个数组的所有元素,遍历过程中,在另一个数组中对第一个数组中的每个元素进行binary search。用C++实现代码如下:
bool findcommon(int a[],int size1,int b[],int size2)
{
int i;
for(i=0;i
{
int start=0,end=size2-1,mid;
{
mid=(start+end)/2;
return true;
else if (a[i]
start=mid+1;
}
}
return false;
}
后来发现有一个 O(n)算法,
因为两个数组都是排好序的。所以只要一次遍历就行了。首先设两个下标,分别初始化为两个数组的起始地址,依次向前推进。推进的规则是比较两个数组中的数字,小的那个数组的下标向前推进一步,直到任何一个数组的下标到达数组末尾时,如果这时还没碰到相同的数字,说明数组中没有相同的数字。
bool findcommon2(int a[], int size1, int b[], int size2)
{
int i=0,j=0;
while(ireturn true;j++;if(a[i]i++;}return false;}4,最大子序列 问题:给定一整数序列A1, A2,... An (可能有负数),求A1~An的一个子序列Ai~Aj,使得Ai到Aj的和最大例如:整数序列-2, 11, -4, 13, -5, 2, -5, -3, 12, -9的最大子序列的和为21。对于这个问题,最简单也是最容易想到的那就是穷举所有子序列的方法。利用三重循环,依次求出所有子序列的和然后取最大的那个。当然算法复杂度会达到O(n^3)。显然这种方法不是最优的,下面给出一个算法复杂度为O(n)的线性算法实现,算法的来源于Programming Pearls一书。 在给出线性算法之前,先来看一个对穷举算法进行优化的算法,它的算法复杂度为O(n^2)。其实这个算法只是对对穷举算法稍微做了一些修改:其实子序列的和我们并不需要每次都重新计算一遍。假设Sum(i, j)是A[i] ... A[j]的和,那么Sum(i, j+1) = Sum(i, j) + A[j+1]。利用这一个递推,我们就可以得到下面这个算法:{int i,j,v,max=a[0];for(i=0;i{v=0;for(j=i;j{v=v+a[j];//Sum(i, j+1) = Sum(i, j) + A[j+1]max=v;}}return max;}那怎样才能达到线性复杂度呢?这里运用动态规划的思想。先看一下源代码实现:{int i,max=0,temp_sum=0;for(i=0;i{temp_sum+=a[i];max=temp_sum;temp_sum=0;}return max;}在这一遍扫描数组当中,从左到右记录当前子序列的和temp_sum,若这个和不断增加,那么最大子序列的和max也不断增加(不断更新max)。如果往前扫描中遇到负数,那么当前子序列的和将会减小。此时temp_sum 将会小于max,当然max也就不更新。如果temp_sum降到0时,说明前面已经扫描的那一段就可以抛弃了,这时将temp_sum置为0。然后,temp_sum将从后面开始将这个子段进行分析,若有比当前max大的子段,继续更新max。这样一趟扫描结果也就出来了。5, 找出单向链表的中间结点 这道题和解判断链表是否存在环,我用的是非常类似的方法,只不过结束循环的条件和函数返回值不一样罢了。设置两个指针p1,p2。每次循环p1向前走一步,p2向前走两步。当p2到达链表的末尾时,p1指向的时链表的中间。{link* p1,*p2;p1=p2=head;if(head==NULL || head->next==NULL)return head;do {p1=p1->next;p2=p2->next->next;} while(p2 && p2->next);return p1;}来自:akalius.blog/163319
数据结构报告【篇10】
实验报告;课程名称:数据结构班级:软件工程实验成绩:;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();
经测试,功能较为完整。代码流程简图如下:
通过这次实验,我了解了有关队列方面的知识。掌握了队列的逻辑结构,抽象数据类型,队列的存储方式等。运用先进先出表,仿真了网络打印队列。这都使我对数据结构的学习有了新的认识与帮助。在实验过程中,我也遇到了许多困难,从开始时对队列运算的不熟悉,到逐渐查找资料,从而完成了实验;六、附录;-《数据结构与算法分析》以及网上资料;
逐渐查找资料,从而完成了实验。在今后的学习中,我将继续努力,加强对堆栈,队列等知识的学习,以达到精益求精。