染雾北邮数据结构实验报告线性表 篇一
在北邮数据结构实验中，我们学习了线性表这一重要的数据结构。线性表是一种有序的数据集合，其中的数据元素之间存在一对一的关系。在本次实验中，我们通过使用数组和链表两种不同的存储方式来实现线性表，并比较它们的优缺点。
首先，我们使用数组来实现线性表。数组是一种连续存储的数据结构，可以通过下标来访问元素。在实验中，我们定义了一个固定大小的数组，然后使用指针来指向数组的头部。通过这种方式，我们可以在常数时间内访问线性表中的任意一个元素。然而，数组的大小是固定的，一旦超过了数组的容量，就需要进行扩容操作。这个过程会涉及到重新分配内存和数据的复制，导致时间复杂度为O(n)。此外，删除操作也比较麻烦，需要将后面的元素向前移动，时间复杂度也为O(n)。
接下来，我们使用链表来实现线性表。链表是一种非连续存储的数据结构，每个节点包含数据和指向下一个节点的指针。在实验中，我们使用头节点来表示线性表的头部，并且每个节点都包含一个指向下一个节点的指针。通过这种方式，我们可以在常数时间内插入和删除节点，因为只需要修改指针的指向即可。然而，链表的访问时间复杂度为O(n)，因为需要从头节点开始遍历到目标节点。此外，链表需要额外的空间来存储指针，导致空间复杂度比数组高。
通过对比两种存储方式，我们可以看出它们各有优缺点。数组适合于需要频繁访问元素的场景，而链表适合于需要频繁插入和删除元素的场景。在实际应用中，我们可以根据具体的需求选择合适的存储方式。此外，我们还可以根据实际情况，结合两种存储方式的优点，设计出更高效的数据结构，如链表数组或者跳表等。
总之，本次实验通过实现线性表，让我们更加深入地理解了数据结构的基本概念和操作。通过比较数组和链表两种不同的存储方式，我们了解到它们各自的优缺点，并且可以根据实际需求选择合适的存储方式。通过不断学习和实践，我们可以更好地应用数据结构来解决实际问题。
北邮数据结构实验报告线性表 篇二
在北邮数据结构实验中，我们学习了线性表这一重要的数据结构。线性表是一种有序的数据集合，其中的数据元素之间存在一对一的关系。在本次实验中，我们通过使用数组和链表两种不同的存储方式来实现线性表，并比较它们的优缺点。
首先，我们使用数组来实现线性表。数组是一种连续存储的数据结构，可以通过下标来访问元素。在实验中，我们定义了一个固定大小的数组，然后使用指针来指向数组的头部。通过这种方式，我们可以在常数时间内访问线性表中的任意一个元素。然而，数组的大小是固定的，一旦超过了数组的容量，就需要进行扩容操作。这个过程会涉及到重新分配内存和数据的复制，导致时间复杂度为O(n)。此外，删除操作也比较麻烦，需要将后面的元素向前移动，时间复杂度也为O(n)。
接下来，我们使用链表来实现线性表。链表是一种非连续存储的数据结构，每个节点包含数据和指向下一个节点的指针。在实验中，我们使用头节点来表示线性表的头部，并且每个节点都包含一个指向下一个节点的指针。通过这种方式，我们可以在常数时间内插入和删除节点，因为只需要修改指针的指向即可。然而，链表的访问时间复杂度为O(n)，因为需要从头节点开始遍历到目标节点。此外，链表需要额外的空间来存储指针，导致空间复杂度比数组高。
通过对比两种存储方式，我们可以看出它们各有优缺点。数组适合于需要频繁访问元素的场景，而链表适合于需要频繁插入和删除元素的场景。在实际应用中，我们可以根据具体的需求选择合适的存储方式。此外，我们还可以根据实际情况，结合两种存储方式的优点，设计出更高效的数据结构，如链表数组或者跳表等。
总之，本次实验通过实现线性表，让我们更加深入地理解了数据结构的基本概念和操作。通过比较数组和链表两种不同的存储方式，我们了解到它们各自的优缺点，并且可以根据实际需求选择合适的存储方式。通过不断学习和实践，我们可以更好地应用数据结构来解决实际问题。
北邮数据结构实验报告线性表 篇三
实验报告;课程名称：数据结构班级：软件工程实验成绩：;1206;实验名称：打印机队列模拟学号：20124848批;程序的设计;实验编号：实验一姓名：实验日期：2014年5月2;一、实验目的;对队列的理解;对STL中的queue的使用;实验仿真一个网络打印过程;二、实验内容与实验步骤流程图;这个任务队列的测试使用STL队列适配器;具体地说,每一行中包含的信息是
实 验 报 告
课程名称：数据结构 班级：软件工程实验成绩：
1206
实验名称：打印机队列模拟学号：20124848 批阅教师签字：
程序的设计
实验编号：实验一 姓名： 实验日期：2014年5 月 24 日
一、实验目的
对队列的理解
对STL中的queue的使用
实验仿真一个网络打印过程
二、实验内容与实验步骤流程图
这个任务队列的测试使用STL队列适配器。程序要求完成模拟的实现共享打印机。这个打印机使用先进先出队列。仿真是通过读取和处理事件数据文件的列表。一个有效的数据文件中的每一行包含信息打印作业和提交这份工作的时间。
具体地说,每一行中包含的信息是提交工作的时间(以秒为单位),和在页面的工作长及工作的计算机的名称。在模拟的开始,每个这些事件的每一个应该被程序所读，存储在继承工作负载队列。程序应该通过循环递增计数器或while-loop模拟时间的流逝。程序应该将计数器初始化为零,然后依次增加1秒。当模拟等于当前时间的打印作业的提交时间在工作队列的前面，一个打印作业完成。当这一切发生的时候,从工作队列取出这个事件,然后把它放在另一个队列对象。这个队列对象存储已完成的打印作业。当程序仿真其他的打印工作的时候，这些工作在队列等待。
Win8，Visual C++ 6.0
四、实验过程与分析
(1)实验主要函数及存储结构
main.cpp 包括主函数和主要的功能
simulator.h 仿真类的声明
simulator.cpp 仿真类的定义
event.h 事件类的声明
event.cpp - 事件类的定义
job.h 作业类的声明
job.cpp 作业类的定义
arbitrary.run 包括任意打印作业数的数据文件
arbitrary.out 输出 arbitrary.run
bigfirst.run 包括打印较大作业的数据文件
bigfirst.out 输出 bigfirst.run
(2)实验代码
#ifndef FIFO_H //fifo.h
#define FIFO_H
#include "simulator.h"
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 "fifo.h" //fifo.cpp
#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(file.find("arbitrary")!= string::npos){
string outfile ="arbitrary.out";
ofstream osf(outfile.c_str());
loadworkload(file);
osf<<"FIFO Simulation "<
for(int time =1;!waiting.empty()||!workload.empty();time++){ while(!workload.empty() && time ==
workload.front().arrival_time()){
evt= workload.front();
osf<<" Arriving: "<
workload.pop();
}
if(!waiting.empty() && time >= finish_time){
totaljob ++;
evt = waiting.front();
agg_latency += time - evt.arrival_time();
osf<<" Servicing: "<
finish_time = time + evt.getjob().getnumpages() * seconds_per_page;
}
}
osf<<" total job "<
osf<<" aggregate latency: "<
osf<<" mean latency : "<
return;
}
if(file.find("bigfirst") != string::npos){
string outfile = "bigfirst.out";
ofstream osf(outfile.c_str());
loadworkload(file);
osf<<"FIFO Simulation "<
for(int time
=1;!priority_waiting.empty()||!workload.empty();time++){
while(!workload.empty() &
workload.front().arrival_time()){
evt= workload.front();
osf<<" Arriving: "<
workload.pop();
}
if(!priority_waiting.empty() && time >= finish_time){
totaljob ++;
evt = priority_waiting.top();
agg_latency += time - evt.arrival_time();
osf<<" Servicing: "<
finish_time = time + evt.getjob().getnumpages() * seconds_per_page; }
}
osf<<" total job "<
osf<<" aggregate latency: "<
osf<<" mean latency : "<
return;
}
cerr<<"The program don't know what algorithm to use"<
cerr<<"You should specify the file name with arbitrary or bigfirst"<
bool operator < (event evtleft,event evtright){
return evtleft.getjob().getnumpages() <
evtright.getjob().getnumpages();
}
五、实验结果总结
经测试，功能较为完整。代码流程简图如下：
通过这次实验，我了解了有关队列方面的知识。掌握了队列的逻辑结构，抽象数据类型，队列的存储方式等。运用先进先出表，仿真了网络打印队列。这都使我对数据结构的学习有了新的认识与帮助。在实验过程中，我也遇到了许多困难，从开始时对队列运算的不熟悉，到逐渐查找资料，从而完成了实验;六、附录;-《数据结构与算法分析》以及网上资料;
逐渐查找资料，从而完成了实验。在今后的学习中，我将继续努力，加强对堆栈，队列等知识的学习，以达到精益求精。
六、附录
-《数据结构与算法分析》以及网上资料
