数据结构实验报告 第一篇
一、实验目的及要求
1)掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们。
本实验训练的要点是“栈”和“队列”的观点;
二、实验内容
1) 利用栈，实现数制转换。
2) 利用栈，实现任一个表达式中的语法检查(选做)。
3) 编程实现队列在两种存储结构中的基本操作(队列的初始化、判队列空、入队列、出队列);
三、实验流程、操作步骤或核心代码、算法片段
顺序栈：
Status InitStack(SqStack &S)
(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));
if(!)
return ERROR;
_INIT_SIZE;
return OK;
Status DestoryStack(SqStack &S)
free();
return OK;
Status ClearStack(SqStack &S)
return OK;
Status StackEmpty(SqStack S)
if()
return OK;
return ERROR;
int StackLength(SqStack S)
return ;
Status GetTop(SqStack S,ElemType &e)
if(;=)
(ElemType *)realloc(,()*sizeof(ElemType));
if(!) return ERROR;
return OK;
Status Push(SqStack &S,ElemType e)
if(;=)
(ElemType *)realloc(,()*sizeof(ElemType));
if(!)
return ERROR;
return OK;
Status Pop(SqStack &S,ElemType &e)
if()
return ERROR;
e=*;
return OK;
Status StackTraverse(SqStack S)
ElemType *p;
p=(ElemType *)malloc(sizeof(ElemType));
if(!p) return ERROR;
p=;
while(p!=)上面一个...
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)
(QueuePtr)malloc(sizeof(QNode));
if (!) return ERROR;
;next = NULL;
return OK;
Status DestoryQueue(LinkQueue &Q)
while()
;next;
free();
return OK;
Status QueueEmpty(LinkQueue &Q)
if(;next==NULL)
return OK;
return ERROR;
Status QueueLength(LinkQueue Q)
int i=0;
QueuePtr p,q;
p=;
while(p->next)
i++;
p=;
q=p->next;
p=q;
return i;
Status GetHead(LinkQueue Q,ElemType &e)
QueuePtr p;
p=;next;
if(!p)
return ERROR;
e=p->data;
return e;
Status ClearQueue(LinkQueue &Q)
QueuePtr p;
while(;next )
p=;next;
free();
;next=NULL;
;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;
;next = p;
; //p->next 为空
return OK;
Status DeQueue(LinkQueue &Q,ElemType &e)
QueuePtr p;
if ( == )
return ERROR;
p = ;next;
e = p->data;
;next = p->next;
if ( == p)
= ; //只有一个元素时(不存在指向尾指针)
free (p);
return OK;
Status QueueTraverse(LinkQueue Q)
QueuePtr p,q;
if( QueueEmpty(Q)==OK)
printf(“这是一个空队列!n”);
return ERROR;
p=;next;
while(p)
q=p;
printf(“%ddata);
q=p->next;
p=q;
return OK;
循环队列：
Status InitQueue(SqQueue &Q)
(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));
if(!)
exit(OWERFLOW);
return OK;
Status EnQueue(SqQueue &Q,QElemType e)
if(()%MAXQSIZE==)
return ERROR;
[]=e;
()%MAXQSIZE;
return OK;
Status DeQueue(SqQueue &Q,QElemType &e)
if()
return ERROR;
e=[];
()%MAXQSIZE;
return OK;
int QueueLength(SqQueue Q)
return()%MAXQSIZE;
Status DestoryQueue(SqQueue &Q)
free();
return OK;
Status QueueEmpty(SqQueue Q) //判空
if( ==)
return OK;
return ERROR;
Status QueueTraverse(SqQueue Q)
if()
printf(“这是一个空队列!”);
while(!=)
printf(“%d
return OK;
数据结构实验报告 第二篇
数据结构实验报告
数据结构实验报告1
一、实验目的及要求
1)掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们。
本实验训练的要点是“栈”和“队列”的观点;
二、实验内容
1) 利用栈，实现数制转换。
2) 利用栈，实现任一个表达式中的语法检查(选做)。
3) 编程实现队列在两种存储结构中的基本操作(队列的初始化、判队列空、入队列、出队列);
三、实验流程、操作步骤或核心代码、算法片段
顺序栈：
Status InitStack(SqStack &S)
(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));
if(!)
return ERROR;
_INIT_SIZE;
return OK;
Status DestoryStack(SqStack &S)
free();
return OK;
Status ClearStack(SqStack &S)
return OK;
Status StackEmpty(SqStack S)
if()
return OK;
return ERROR;
int StackLength(SqStack S)
return ;
Status GetTop(SqStack S,ElemType &e)
if(;=)
(ElemType *)realloc(,()*sizeof(ElemType));
if(!) return ERROR;
return OK;
Status Push(SqStack &S,ElemType e)
if(;=)
(ElemType *)realloc(,()*sizeof(ElemType));
if(!)
return ERROR;
return OK;
Status Pop(SqStack &S,ElemType &e)
if()
return ERROR;
e=*;
return OK;
Status StackTraverse(SqStack S)
ElemType *p;
p=(ElemType *)malloc(sizeof(ElemType));
if(!p) return ERROR;
p=;
while(p!=)上面一个...
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)
(QueuePtr)malloc(sizeof(QNode));
if (!) return ERROR;
;next = NULL;
return OK;
Status DestoryQueue(LinkQueue &Q)
while()
;next;
free();
return OK;
Status QueueEmpty(LinkQueue &Q)
if(;next==NULL)
return OK;
return ERROR;
Status QueueLength(LinkQueue Q)
int i=0;
QueuePtr p,q;
p=;
while(p->next)
i++;
p=;
q=p->next;
p=q;
return i;
Status GetHead(LinkQueue Q,ElemType &e)
QueuePtr p;
p=;next;
if(!p)
return ERROR;
e=p->data;
return e;
Status ClearQueue(LinkQueue &Q)
QueuePtr p;
while(;next )
p=;next;
free();
;next=NULL;
;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;
;next = p;
; //p->next 为空
return OK;
Status DeQueue(LinkQueue &Q,ElemType &e)
数据结构实验报告 第三篇
北京邮电大学信息与通信工程学院
级数据结构实验报告
实验名称： 实验三哈夫曼编/解码器的实现
学生姓名：陈聪捷
日 期： 11月28日
1.实验要求
一、实验目的：
了解哈夫曼树的思想和相关概念;
二、实验内容：
利用二叉树结构实现哈夫曼编/解码器
1.初始化：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈夫曼树。
2.建立编码表：利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。
3.编码：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。
4.译码：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。
5.打印：以直观的方式打印哈夫曼树。
6.计算输入的字符串编码前和编码后的长度，并进行分析，讨论哈夫曼编码的压缩效果。
7.用户界面可以设计成“菜单”方式，能进行交互，根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码。
2. 程序分析
存储结构
二叉树
template
class BiTree
public:
BiTree; //构造函数，其前序序列由键盘输入
~BiTree(void); //析构函数
BiNode* Getroot(); //获得指向根结点的指针
protected:
BiNode *root; //指向根结点的头指针
//声明类BiTree及定义结构BiNode
Data：
二叉树是由一个根结点和两棵互不相交的左右子树构成
data:
HCode* HCodeTable;//编码表
int tSize; //编码表中的总字符数
二叉树的节点结构
template
struct BiNode //二叉树的结点结构 {
T data; //记录数据
T lchild; //左孩子
T rchild; //右孩子
T parent; //双亲
编码表的节点结构
struct HCode
char data; //编码表中的字符
char code[100]; //该字符对应的编码
待编码字符串由键盘输入，输入时用链表存储，链表节点为 struct Node
char character; //输入的字符
unsigned int count;//该字符的权值
bool used; //建立树的时候该字符是否使用过
Node* next; //保存下一个节点的地址
示意图：
关键算法分析
1.初始化函数(void HuffmanTree::Init(string Input))
算法伪代码：
1.初始化链表的头结点
2.获得输入字符串的第一个字符，并将其插入到链表尾部,n=1(n记录的是链表
中字符的个数)
3.从字符串第2个字符开始，逐个取出字符串中的字符
将当前取出的字符与链表中已经存在的字符逐个比较，如果当前取出
的字符与链表中已经存在的某个字符相同，则链表中该字符的权值加1。
如果当前取出的字符与链表中已经存在的字符都不相同，则将其加入
到链表尾部，同时n++
(tSize记录链表中字符总数，即哈夫曼树中叶子节点总数)
5.创建哈夫曼树
6.销毁链表
源代码：
void HuffmanTree::Init(string Input)
Node *front=new Node; //初始化链表的头结点
if(!front)
throw exception(“堆空间用尽”);
front->next=NULL;
front->character=NULL;
front->count=0;
Node *pfront=front;
char ch=Input[0]; //获得第一个字符
Node* New1=new Node;
if(!New1)
throw exception(“堆空间用尽”);
New1->character=ch; //将第一个字符插入链表
New1->count=1;
New1->next=pfront->next;
pfront->next=New1;
bool replace=0; //判断在已经写入链表的字符中是否有与当前读出的字符相同的字符 int n=1; //统计链表中字符个数
for(int i=1;i
ch=Input[i]; //获得第i个字符
pfront=pfront->next;
if((int)pfront->character == (int)ch) //如果在链表中有与当前字符相同的字符，
该字符权值加1
pfront->count++;
replace=1;
break;
}while(pfront->next);
if(!replace) //如果在链表中没找到与当前字符相同的字符，则将该字符作为新成 员插入链表
Node* New=new Node;
if(!New)
throw exception(“堆空间用尽”);
New->character=ch;
New->count=1;
New->next=pfront->next;
pfront->next=New;
n++;
pfront=front; //重置pfront和replace变量为默认值 replace=0;
tSize=n; //tSize记录的是编码表中字符个数
CreateHTree(front,n); //创建哈夫曼树
pfront=front;
while(pfront) //销毁整个链表
front=pfront;
pfront=pfront->next;
front;
时间复杂度：
若输入的字符串长度为n，则时间复杂度为O(n)
2.创建哈夫曼树(void HuffmanTree::CreateCodeTable(Node *p))
算法伪代码：
1. 创建一个长度为2*tSize-1的三叉链表
2. 将存储字符及其权值的链表中的字符逐个写入三叉链表的前tSize个结点
的data域，并将对应结点的孩子域和双亲域赋为空
3. 从三叉链表的第tSize个结点开始，i=tSize
从存储字符及其权值的链表中取出两个权值最小的结点x,y，记录其
下标x,y。
将下标为x和y的哈夫曼树的结点的双亲设置为第i个结点
将下标为x的结点设置为i结点的左孩子，将下标为y的结点设置为
i结点的右孩子，i结点的权值为x结点的权值加上y结点的权值，i
结点的双亲设置为空
4. 根据哈夫曼树创建编码表
源代码：
void HuffmanTree::CreateHTree(Node *p,int n)
root= new BiNode[2*n-1]; //初始化哈夫曼树
Node *front=p->next;
if(n==0)
throw exception(“没有输入字符”);
for(int i=0;i
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;
for(i=n;i<2*n-1;i++)
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;
CreateCodeTable(p); //创建编码表
时间复杂度：
在选取两个权值最小的结点的函数中要遍历链表，时间复杂度为O(n),故该函数
的时间复杂度为O(n^2)
3.创建编码表(void HuffmanTree::CreateCodeTable(Node *p))
算法伪代码：
1.初始化编码表
2.初始化一个指针，从链表的头结点开始，遍历整个链表
将链表中指针当前所指的结点包含的字符写入编码表中
得到该结点对应的哈夫曼树的叶子结点及其双亲
如果哈夫曼树只有一个叶子结点，将其字符对应编码设置为0
如果不止一个叶子结点，从当前叶子结点开始判断
如果当前叶子结点是其双亲的左孩子，则其对应的编码为0，否
则为1
child指针指向叶子结点的双亲，parent指针指向child指针的双亲，
重复的操作
将已完成的编码倒序
取得链表中的下一个字符
3.输出编码表
源代码：
void HuffmanTree::CreateCodeTable(Node *p)
HCodeTable=new HCode[tSize]; //初始化编码表
Node *front=p->next;
for(int i=0;i
HCodeTable[i].data=front->character; //将第i个字符写入编码表
int child=i; //得到第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，
否则编码为1
HCodeTable[i].code[k]='0';
else
HCodeTable[i].code[k]='1';
k++;
child=parent;
parent=root[child].parent;
HCodeTable[i].code[k]='';
Reverse(HCodeTable[i].code); //将编码逆置
front=front->next; //得到下一个字符
cout<
for(i=0;i
cout<
parent=root[parent].lchild;
else //编码为1则寻找右孩子
parent=root[parent].rchild;
i++;
if(tSize==1) //如果编码表只有一个字符，则根结点即为叶子结点 i++;
(1,HCodeTable[parent].data);//将叶子节点对应的字符追加到解码串中 }
cout<
时间复杂度：
设待解码串长度为n，则复杂度为O(n)
8. 计算哈夫曼编码的压缩比(void HuffmanTree::Calculate(string s1,string s2)) 算法伪代码：
1. 获得编码前字符串的长度，即其占用的字节数
2. 获得编码后的字符串的长度，将其除以8然后向上取整，得到其占用的字
3. 压缩比将两个相除
源代码：
void HuffmanTree::Calculate(string s1,string s2)
int cal1=();
int cal2=();
cal2=ceill((float)cal2/8); //将编码串的比特数转化为字节数 cout<
cout<
cout<
时间复杂度：
O(1)
9. 打印哈夫曼树(void HuffmanTree::PrintTree(int TreeNode,int layer) ) 算法伪代码：
1. 如果待打印结点为空，则返回
2. 递归调用函数打印当前结点的右子树
3. 根据当前结点所在的层次确定其前面要输出多少空格，先输出空格，在打
印当前结点的权值
4. 递归调用函数打印当前结点的左子树
源代码：
void HuffmanTree::PrintTree(int TreeNode,int layer)
if(TreeNode==-1) //如果待打印结点为空，则返回 return;
else
PrintTree(root[TreeNode].rchild,layer+1); //先打印该结点的右子树，layer记录
的是该结点所在的层次
for(int i=0;i
cout<
cout<
PrintTree(root[TreeNode].lchild,layer+1); //打印该结点的左子树
时间复杂度：
中序遍历哈夫曼树，复杂度为O(n)
10. 菜单函数(void HuffmanTree::Menu())
算法伪代码：
1. 逐一读取键盘缓存区中的字符，并将它们逐一追加到记录输入字符串的
string变量中，直到读到回车输入符为止
2. 删除string变量末尾的回车输入符
3.利用string变量创建哈夫曼树，初始化编码表。
4. 直观打印哈夫曼树
5. 对输入的字符串进行编码
6. 对编码后的字符串进行解码
7. 计算编码前后的压缩比并输出
源代码：
void HuffmanTree::Menu()
cout<
string Input;
char letter;
do //将字符逐个读入Input变量中
letter=();
(1,letter);
}while(letter!=' ');
(()-1,1); //去掉Input末尾的回车符
Init(Input); //根据输入的字符串创建哈夫曼树及其编码表 cout<
PrintTree(2*tSize-1-1,1); //打印哈夫曼树
cout<
string d1,d2;
cout<
Encode(Input,d1); //编码并打印编码串
cout<
Decode(d1,d2); //解码并打印解码串
cout<
Calculate(Input,d1); //计算编码前后的压缩比
其他
1.由于题目要求能输入任意长的字符串，所以本程序采用了string变量来记录输入
的字符串，并采用string类的类成员函数来完成各项任务
2.打印哈夫曼树时采用了递归函数，且采用了凹凸表的形式打印哈夫曼树。
3.为了输入空格，输入时采取逐个字符输入的方式
3. 程序运行结果
主函数流程图：
运行结果：
各函数运行正常，没有出现bug
4. 总结
经过这次实验，我了解了哈夫曼树的创建过程，了解了一种不等长编码的方法，用设断点调试的方法更加熟练，同时熟悉了STL中string类型的用法，对C++更加熟悉
数据结构实验报告 第四篇
数据结构试题答案
一、单项选择题（每题2分，共30分）
1.若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。
A) 单链表 B) 双链表 C) 单向循环链表 D) 顺序表
2.串是任意有限个（ ）。
A) 符号构成的序列 B) 符号构成的集合
C) 字符构成的序列 D) 字符构成的集合
3.设矩阵A的任一元素aij(1≤i,j≤10)满足：
aij≠0；(i≥j,1≤i,j≤10)
aij=0； (i
现将A的所有非0元素以行序为主序存放在首地址为的存储区域中，每个元素占有4个单元，则元素A[9,5]的首地址为（ ）。
A) 2340 B) 2336 C) 2164 D) 2160
4.如果以链表作为栈的存储结果，则出栈操作时（ ）。
A) 必须判别栈是否为满 B) 对栈不作任何判别
C) 必须判别栈是否为空 D) 判别栈元素的类型
5.设数组Data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针,则执行出队操作的语句为（ ）。
A) front = front+1 B) front = (front+1) % m
C) rear = (rear+1) % m D) front = (front+1) % (m+1)
6.深度为6(根的层次为1)的二叉树至多有（ ）结点。
A) 64 B) 32 C) 31 D) 63
7.将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次堆结点编号，根结点的编号为1。编号为49的结点X的双亲的编号为（ ）。
A) 24 B) 25 C) 23 D) 无法确定
8.设有一个无向图 和 ，如果 为 的生成树，则下面不正确的说法是（ ）。
A) 为 的子图 B) 为 的连通分量
C) 为 的极小连通子图且 D) 为 的一个无环子图
9.用线性探测法查找闭散列表，可能要探测多个散列地址，这些位置上的键值（ ）。
A) 一定都是同义词 B) 一定都不是同义词
C) 多相同 D) 不一定都是同义词
10.二分查找要求被查找的表是（ ）。
A) 键值有序的链接表 B) 链接表但键值不一定有序
C) 键值有序的顺序表 D) 顺序表但键值不一定有序
11.当初始序列已经按键值有序，用直接插入算法对其进行排序，需要循环的次数为（ ）。
A) B) C) D) n－1
12.堆是一个键值序列 ,对 ，满足（ ）。
A) B)
C) 且 ( ) D) 或 ( )
13.使用双向链表存储数据，其优点是可以（ ）。
A) 提高检索速度 B) 很方便地插入和删除数据
C) 节约存储空间 D) 很快回收存储空间
14.设计一个判别表达式中左右括号是否配对出现地算法，采用（ ）数据结构最佳。
A) 线性表地顺序存储结构 B) 栈
C) 队列 D) 线性表达的链式存储结构
15.设深度为k的二叉树上只有度为0和2的结点，则此类二叉树中所含的结点数至少为（ ）。
A) k + 1 B) 2k C) 2k - 1 D) 2k + 1
二、填空题（每空2分，共28分）
1.设r指向单链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是_____________________________________________r=s;r->next=NULL。
2.在单链表中，指针p所指结点为最后一个结点的条件是___________________。
3.设一个链栈的栈顶指针是ls，栈中结点格式为 ，栈空的条件为_____________。如果栈不为空，则出栈操作为p=ls;______________;free(p)。
4.已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的'结点，则该树有________个叶子结点。
5.树有三种常用的存储结构，即孩子链表法，孩子兄弟链表法和____________。
个顶点的连通图的生成树有__________条边。
7.一个有向图G中若有弧 、 和 ，则在图G的拓扑序列中，顶点 的相对位置为___________。
8.设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和归并排序方法对其进行排序(按递增顺序)，________最省时间，__________最费时间。
9.下面是将键值为x的结点插入到二叉排序树中的算法，请在划线处填上适当的内容。
Typedef struct pnode
{ int key;
struct node * left, * right;
Void search (int x; pnode t )
{ if (_____________)
{p = malloc (size);
p->key=x;p->left=NULL;
p->right=NULL;
t=p;
else
if (xkey) search (x,t->left)
else _________________
10.线性表的____________的主要优点是从表中任意结点出发都能访问到所有结点。而使用____________，可根据需要在前后两个方向上方便地进行查找。
三、应用题（每题10分，共30分）
1.在双链表中，要在指针变量P所指结点之后插入一个新结点，请按顺序写出必要的算法步骤。(设：P所指结点不是链表的首尾结点，q是与p同类型的指针变量)
2.已知待排序文件各记录的排序码顺序如下：
72 73 71 23 94 16 05 68
请列出快速排序过程中每一趟的排序结果。
四、算法题(共12分)
编写算法，实现单链表上的逆置运算(说明：即将单链表中的元素次序反转)
参考答案：
一、单项选择题（每题2分，共30分）
二、填空题（每空2分，共28分）
1. r->next=s; 2. p->next=NULL;
3. ls = = NULL; ls=ls->link。 4. 12
5. 双亲表示法 6. n-1
7. i,j,k 8. 冒泡排序，快速排序
9. t= =NULL，search（x,t->right）； 10.循环链表，双向链表
三、应用题（每题10分，共30分）
1．new(q)；
q↑.llink ← p；
q↑.rlink ← p↑.rlink；
p↑.rlink↑.llink ← q；
p↑.rlink ← q。
评分细则：按顺序每对一个给2分，全对计10分。
2．各趟结果如下：
[68 05 71 23 16] 72 [94 73]
[16 05 23] 68 [71] 72 [94 73]
[05] 16 [23] 68 [71] 72 [94 73]
05 16 [23] 68 [71] 72 [94 73]
05 16 23 68 71 72 [94 73]
05 16 23 68 71 72 [73] 94
05 16 23 68 71 72 73 94
四．算法题(共12分)
void invert（ pointer head）
{p=NULL;
while ( headNULL)
{u=head;
head=head->next;
u->next=p;
p=u;
head=p;
数据结构实验报告 第五篇
目前所在： xxx 年 龄： 20
户口所在： 汕头 国 籍： 中国
婚姻状况： 未婚 民 族： 汉族
诚信徽章： 未申请 身 高： 157 cm
人才测评： 未测评 体 重：
人才类型： 在校学生
应聘职位： 幼教/保育员， 家教， 销售主管/销售代表/客户代表
工作年限： 1 职 称：
求职类型： 兼职 可到职日期： 随时
月薪要求： 面议 希望工作地区： xxx,xxx,广州
工作经历
无 起止年月：-10 ～ -05
公司性质： 所属行业：
担任职位： 作业指导
工作描述： 辅导小学生作业，照顾小学生
广州地铁 起止年月：2023-04 ～ 2023-05
担任职位： 地铁志愿者
工作描述：
毕业院校： 广东交通职业技术学院
最高学历： 大专 获得学位: 毕业日期： -06
专 业 一： 软件技术 专 业 二：
起始年月 终止年月 学校（机构） 所学专业 获得证书 证书编号
语言能力
外语： 英语 良好 粤语水平： 一般
其它外语能力：
国语水平： 优秀
工作能力及其他专长
数据结构实验报告 第六篇
数据结构试题
一、选择题(30分)
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最好选择( )。
(A) 小于等于m的最大奇数 (B) 小于等于m的最大素数
(C) 小于等于m的最大偶数 (D) 小于等于m的最大合数
9.设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数为1的结点数有2个，那么度数为0的结点数有( )个。
(A) 4 (B) 5 (C) 6 (D) 7
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的元素需要经过( )次比较。
(A) 1 (B) 2 (C) 3 (D) 4
13.设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找长度为( )。
(A) 6 (B) 11 (C) 5 (D)
14.设有向无环图G中的有向边集合E={<1，2>，<2，3>，<3，4>，<1，4>}，则下列属于该有向图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)，则由这组记录关键字生成的二叉排序树的深度为( )。
(A) 4 (B) 5 (C) 6 (D) 7
二、填空题(30分)
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(如右图所示)，则其最小生成树上所有边的权值之和为_________________。
三、判断题(20分)
1.有向图的邻接表和逆邻接表中表结点的个数不一定相等。( )
2.对链表进行插入和删除操作时不必移动链表中结点。( )
3.子串“ABC”在主串“AABCABCD”中的位置为2。( )
4.若一个叶子结点是某二叉树的中序遍历序列的最后一个结点，则它必是该二叉树的先序遍历序列中的最后一个结点。( )
5.希尔排序算法的时间复杂度为O(n2)。( )
6.用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。( )
7.中序遍历一棵二叉排序树可以得到一个有序的序列。( )
8.入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。( )
9.顺序表查找指的是在顺序存储结构上进行查找。( )
10.堆是完全二叉树，完全二叉树不一定是堆。( )
四、算法设计题(20分)
1.设计计算二叉树中所有结点值之和的算法。
2.设计将所有奇数移到所有偶数之前的算法。
3.设计判断单链表中元素是否是递增的算法。
数据结构实验报告 第七篇
1.判断链表是否存在环型链表问题：判断一个链表是否存在环，例如下面这个链表就存在一个环：
例如N1->N2->N3->N4->N5->N2就是一个有环的链表，环的开始结点是N5这里有一个比较简单的解法，设置两个指针p1，p2。每次循环p1向前走一步，p2向前走两步。直到p2碰到NULL指针或者两个指针相等结束循环。如果两个指针相等则说明存在环。
struct link
int data;
link* next;
bool IsLoop(link* head)
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);
if(p1 == p2)
return true;
else
return false;
2,链表反转 单向链表的反转是一个经常被问到的一个面试题，也是一个非常基础的问题。比如一个链表是这样的： 1->2->3->4->5 通过反转后成为5->4->3->2->1。最容易想到的方法遍历一遍链表，利用一个辅助指针，存储遍历过程中当前指针指向的下一个元素，然后将当前节点元素的指针反转后，利用已经存储的指针往后面继续遍历。源代码如下：
struct linka {
int data;
linka* next;
void reverse(linka*& head)
if(head ==NULL)
return;
linka*pre, *cur, *ne;
pre=head;
cur=head->next;
while(cur)
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;
return p;
else
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;
while(start<=end)
mid=(start+end)/2;
if(a[i]==b[mid])
return true;
else if (a[i]
end=mid-1;
else
start=mid+1;
return false;
后来发现有一个 O(n)算法，
因为两个数组都是排好序的。所以只要一次遍历就行了。首先设两个下标，分别初始化为两个数组的起始地址，依次向前推进。推进的规则是比较两个数组中的数字，小的那个数组的下标向前推进一步，直到任何一个数组的下标到达数组末尾时，如果这时还没碰到相同的数字，说明数组中没有相同的数字。
bool findcommon2(int a[], int size1, int b[], int size2)
int i=0,j=0;
while(i
{
if(a[i]==b[j])
return true;
if(a[i]>b[j])
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 max_sub(int a[],int size)
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]
if(v>max)
max=v;
return max;
那怎样才能达到线性复杂度呢？这里运用动态规划的思想。先看一下源代码实现：
int max_sub2(int a[], int size)
int i,max=0,temp_sum=0;
for(i=0;i
temp_sum+=a[i];
if(temp_sum>max)
max=temp_sum;
else if(temp_sum<0)
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* mid(link* head)
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;
来自：
数据结构实验报告 第八篇
【简要分析】
首先可以想到的是双栈，一个作为数栈用来存放数，另一个作为符号栈用来存放运算符。遍 历算数表达式，如果是数字就入数栈，如果是符号就分情况：
1.如果当前符号栈为空，则直接入栈；
2.如果当前符号栈不为空，则进行比较。如果当前的操作符的优先级小于或等于栈中操作符，就从栈中pop出两个数，从符号栈中pop出一个符号进行运算，再将得到的结果入数栈，然后将当前的符号入符号栈；如果当前的操作符的优先级大于栈中的操作符，就直接入符号栈。
3.算术表达式扫描完了后，顺序的从数栈和符号栈中pop出相应的数和符号并运行；
4.最后在数栈中剩下的最后的数字就是表达式的结果。
数据结构实验报告 第九篇
怎么学好数据结构
首先你要知道什么是数据结构，学习数据结构的意义。这将是你学习的动力所在。计算机软件都用到了数据结构。所以，学好数据结构对于你将来从事计算机编程类的工作有十分重要的作用。
数据结构中的基本概念，你要一定清楚。平时要多看书，要在计算机上去调试程序，在调试的过程中，你才能发现自己的问题，然后及时解决。在上机调试的过程中，更要大胆尝试，注重运用。拿到一个题时，更要深入分析，尝试用不同的算法去设计。当然编程的时候，要注意格式。比如：变量一定要先定义后使用。变量的定义不要定义在中间。
算法与数据结构是紧密联系，所以你算法一定要会。如果你是学生，只需把课本上出现的搞懂就好了，比如线性表的插入，删除，查找算法，它都是固定的。你就要理解，当然你要学会画图。对于书中的内容要熟悉。
数据结构的大纲如下：线性表、栈和队列，串、数组和广义表、树与森林、图、还有就是查找和排序。简单的总结一下也就是它的逻辑结构：线性结构和非线性结构。这些基本的内容你如果搞懂了，你的数据结构也就学好了。
要严格要求自己。在学习算法的过程中，你要想它为什么要这样设计?它的优点在哪里?想着去改进算法，慢慢的的你的逻辑思维能力也就提高了。你会发现其实数据结构也就那么回事，不是很难。
有不懂得地方要及时请教老师，不要不懂装懂。不要放过任何一个细节，因为我的专业就是计算机，所以有很多都是深有体会。
注意：
一、认真安排好你的时间
首先你要清楚一周内所要做的事情，然后制定一张作息时间表。在表上填上那些非花不可的时间，如吃饭、睡觉、上课、娱乐等。安排这些时间之后，选定合适的、固定的时间用于学习，必须留出足够的时间来完成正常的阅读和课后作业。当然，学习不应该占据作息时间表上全部的空闲时间，总得给休息、业余爱好、娱乐留出一些时间，这一点对学习很重要。一张作息时间表也许不能解决你所有的问题，但是它能让你了解如何支配你这一周的时间，从而使你有充足的时间学习和娱乐。
二、学习前先预习
这就意味着在你认真投入学习之前，先把要学习的内容快速浏览一遍，了解学习的大致内容及结构，以便能及时理解和消化学习内容。当然，你要注意轻重详略，在不太重要的地方你可以花少点时间，在重要的地方，你可以稍微放慢学习进程。
三、充分利用课堂时间
学习成绩好的学生很大程度上得益于在课堂上充分利用时间，这也意味着在课后少花些功夫。课堂上要及时配合老师，做好笔记来帮助自己记住老师讲授的内容，尤其重要的是要积极地独立思考，跟得上老师的思维。
四、学习要有合理的规律
课堂上做的笔记你要在课后及时复习，不仅要复习老师在课堂上讲授的重要内容，还要复习那些你仍感模糊的认识。如果你坚持定期复习笔记和课本，并做一些相关的习题，你定能更深刻地理解这些内容，你的记忆也会保持更久。定期复习能有效地提高你的考试成绩。
五、一个安静的、舒适的学习环境
选择某个地方作你的学习之处，这一点很重要。它可以是你的单间书房或教室或图书馆，但是它必须是舒适的，安静而没有干扰。当你开始学习时，你应该全神贯注于你的功课，切忌“身在曹营心在汉”。
六、树立正确的考试观
平时测验的目的主要看你掌握功课程度如何，所以你不要弄虚作假，而应心平气和地对待它。或许，你有一两次考试成绩不尽如人意，但是这不要紧，只要学习扎实，认真对待，下一次一定会考出好成绩来。通过测验，可让你了解下一步学习更需要用功夫的地方，更有助于你把新学的知识记得牢固。
数据结构实验报告 第十篇
一.实验内容：
实现哈夫曼编码的生成算法。
二.实验目的：
1、使学生熟练掌握哈夫曼树的生成算法。
2、熟练掌握哈夫曼编码的方法。
三.问题描述：
已知n个字符在原文中出现的频率，求它们的哈夫曼编码。
1、读入n个字符，以及字符的权值，试建立一棵Huffman树。
2、根据生成的Huffman树，求每个字符的Huffman编码。并对给定的待编码字符序列进行编码，并输出。
四.问题的实现
(1)郝夫曼树的存储表示
typedef struct{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; //动态分配数组存储郝夫曼树
郝夫曼编码的存储表示
typedef char* *HuffmanCode;//动态分配数组存储郝夫曼编码
(2)主要的实现思路：
a.首先定义郝夫曼树的存储形式，这里使用了数组
b.用select遍历n个字符，找出权值最小的两个
c.构造郝夫曼树HT，并求出n个字符的郝夫曼编码HC
1.基本上没有什么太大的问题，在调用select这个函数时，想把权值最小的两个结点的序号带回HuffmanCoding，所以把那2个序号设置成了引用。
2.在编程过程中，在什么时候分配内存，什么时候初始化花的时间比较长
3.最后基本上实现后，发现结果仍然存在问题，经过分步调试，发现了特别低级的输入错误。把HT[i].weight=HT[s1].weight+HT[s2].weight;中的s2写成了i
//动态分配数组存储郝夫曼树
typedef struct{
int weight; //字符的权值
int parent,lchild,rchild;
}HTNode,*HuffmanTree;
//动态分配数组存储郝夫曼编码
typedef char* *HuffmanCode;
//选择n个(这里是k=n)节点中权值最小的两个结点
void Select(HuffmanTree &HT,int k,int &s1,int &s2)
{ int i;
i=1;
while(i<=k && HT[i].parent!=0)i++;
//下面选出权值最小的结点，用s1指向其序号
s1=i;
for(i=1;i<=k;i++)
if(HT[i].parent==0&&HT[i].weight
//下面选出权值次小的结点，用s2指向其序号
for(i=1;i<=k;i++)
if(HT[i].parent==0&&i!=s1)break;
s2=i;
for(i=1;i<=k;i++)
if(HT[i].parent==0&&i!=s1&&HT[i].weight
//构造Huffman树，求出n个字符的编码
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
int m,c,f,s1,s2,i,start;
char *cd;
if(n<=1)return;
m=2*n-1; //n个叶子n-1个结点
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //0号单元未用，预分配m+1个单元
HuffmanTree p=HT+1;
w++; //w的号单元也没有值，所以从号单元开始
for(i=1;i<=n;i++,p++,w++)
p->weight=*w;
p->parent=p->rchild=p->lchild=0;
for(;i<=m;++i,++p)
p->weight=p->parent=p->rchild=p->lchild=0;
for(i=n+1;i<=m;i++)
Select(HT,i-1,s1,s2); //选出当前权值最小的
HT[s1].parent=i;
HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
//从叶子到根逆向求每个字符的郝夫曼编码
HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); //分配n个字符编码的头指针变量
cd=(char*)malloc(n*sizeof(char)); //分配求编码的工作空间
cd[n-1]=' ';//编码结束符
for(i=1;i<=n;i++) //逐个字符求郝夫曼编码
start=n-1; //编码结束符位置
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) //从叶子到根逆向求编码
if(HT[f].lchild==c)cd[--start]='0';
else
cd[--start]='1';
HC[i]=(char*)malloc((n-start)*sizeof(char)); //为第i个字符编码分配空间
strcpy(HC[i],&cd[start]);//从cd复制编码到HC
free(cd); //释放工作空间
void main
{ int n,i;
int* w; //记录权值
char* ch; //记录字符
HuffmanTree HT;
HuffmanCode HC;
cout<
cin>>n;
w=(int*)malloc((n+1)*sizeof(int)); //记录权值，号单元未用
ch=(char*)malloc((n+1)*sizeof(char));//记录字符，号单元未用
cout<
for(i=1;i<=n;i++)
cout<
数据结构实验报告 第十一篇
实 验 报 告
课程名称：数据结构 班级：软件工程实验成绩：
1206
实验名称：打印机队列模拟学号：20234848 批阅教师签字：
程序的设计
实验编号：实验一 姓名： 实验日期：205 月 24 日
一、实验目的
对队列的理解
对STL中的queue的使用
二、实验内容与实验步骤流程图
这个任务队列的测试使用STL队列适配器。程序要求完成模拟的实现共享打印机。这个打印机使用先进先出队列。仿真是通过读取和处理事件数据文件的列表。一个有效的数据文件中的每一行包含信息打印作业和提交这份工作的时间。
具体地说,每一行中包含的信息是提交工作的时间(以秒为单位),和在页面的工作长及工作的计算机的名称。在模拟的开始,每个这些事件的每一个应该被程序所读，存储在继承工作负载队列。程序应该通过循环递增计数器或while-loop模拟时间的流逝。程序应该将计数器初始化为零,然后依次增加1秒。当模拟等于当前时间的打印作业的提交时间在工作队列的前面，一个打印作业完成。当这一切发生的时候,从工作队列取出这个事件,然后把它放在另一个队列对象。这个队列对象存储已完成的打印作业。当程序仿真其他的打印工作的时候，这些工作在队列等待。
Win8，Visual C++
四、实验过程与分析
(1)实验主要函数及存储结构
包括主函数和主要的功能
仿真类的声明
仿真类的定义
事件类的声明
- 事件类的定义
作业类的声明
作业类的定义
包括任意打印作业数的数据文件
输出
包括打印较大作业的数据文件
输出
(2)实验代码
#ifndef FIFO_H
#define FIFO_H
#include “”
class fifo:public simulator{
protected:
queue waiting;
priority_queue priority_waiting;
public:
fifo(int seconds_per_page);
void simulate(string file);
bool operator < (event evtleft,event evtright);
#endif
#include “”
#include
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((“arbitrary”)!= string::npos){
string outfile =“”;
ofstream osf(());
loadworkload(file);
osf<
for(int time =1;!()||!();time++){ while(!() && time ==
().arrival_time()){
evt= ();
osf<
();
if(!() && time >= finish_time){
totaljob ++;
evt = ();
agg_latency += time - ();
osf<
finish_time = time + ().getnumpages() * seconds_per_page;
osf<
osf<
osf<
return;
if((“bigfirst”) != string::npos){
string outfile = “”;
ofstream osf(());
loadworkload(file);
osf<
for(int time
=1;!()||!();time++){
while(!() && time ==
().arrival_time()){
evt= ();
osf<
();
if(!() && time >= finish_time){
totaljob ++;
evt = ();
agg_latency += time - ();
osf<
finish_time = time + ().getnumpages() * seconds_per_page; }
osf<
osf<
osf<
return;
cerr<
cerr<
bool operator < (event evtleft,event evtright){
return ().getnumpages() <
().getnumpages();
五、实验结果总结
经测试，功能较为完整。代码流程简图如下：
数据结构实验报告 第十二篇
【类的建立】
School类：含括学校ID，学校名称，学校参赛队伍个数,总分等字段
Team类：含括所属学校ID，队伍名称，参加项目和所得分数等字段
Event类：含括一个存储Team类对象的集合表示参加该项目的队伍以及项目
Function类：其内容涉及一个存储所有参赛项目的集合events和一个存储所有参赛学校的集合schools以及各项查询功能
【算法函数】
项目添加函数：用于添加相应的项目
学校添加函数：用于添加参赛学校
队伍添加函数：用于添加参赛队伍，该函数为主要添加函数，若在添加过程中发现不存在当前所要添加的项目或学校，则在执行结果命令行显示添加错误及原因，若学校参赛队伍达到上限，同上，学校总分计算函数：计算某学校的总分；学校总分排名的函数：按总分进行降序排序；学校的项目总分排名函数：返回一个字典集合，内含项目id和项目总分；单个项目获奖情况函数：对项目内的队伍按分数进行排名，索引为0，1，2，3；0，1，2即为前三；3则代表未获奖学校各项目获奖情况函数、
查看全文