数据结构上机报告

数据结构上机报告

课程：有向图中求各顶点之间的最短路径

算法设计：

现设一个矩阵F，用来记录路径长度。初始时，顶点Vi到顶点Vj的最短路径长度F[i][j]=weight[i][j],即弧上的权值。若不存在,则F[][]=∞（程序中用1000表示）。此时，把矩阵F记做F0。F0考虑到了有弧相连直接到达的路径，但这个长度不是最短长度，所以要进行探索。

① 让路径经过V0（第一个顶点），并比较路径（Vi,Vj）和路径（Vi,V0,Vj）的长度，去较短的作为最短路径长度。其中，路径（Vi,V0,Vj）的长度等于路径（Vi,V0）和（V0,Vj）长度之和，即F[i][j]=F[i][0]+F[0][j]。把此时得到的矩阵F记做F1，F1考虑到了各项点间除直接到达的路径外，其他经过V0的路径，只取其中最短的作为最短路径长度。

② 在F1的基础上让路径经过第二个顶点V1，依照?的方法求得最短路径长度，得到F2。

③ 以此类推，经过n次试探，将n个顶点都考虑到路径之中，此时求得最短路径长度。

例：有向图如下：

求任意两个顶点之间的最短路径长度

程序运行如下：

程序代码：

#include using namespace std;

#def

1． 已知长度为n的线性表L采用顺序存储结构，编写一个时间复杂度为O(n)，空间复杂度

为O(1)的算法，该算法删除线性表中所有值为item的数据元素。

2． 用顺序表A和B表示的两个线性表，元素的个数分别为m和n，若表中数据都是由小

到大顺序排列的，且这(m+n)个数据中没有相重的。设计一个算法将些两个线性表合并成一个，仍是数据由小到大排列的线性表，存储到另一个顺序表C中。

3． 已知线性表{a0,a1,……,an-1}按顺序存储，且每个元素都是不相等的整数。设计把所有

的奇数移到所有的偶数前边的算法（要求时间最少，辅助空间最少）。 4． 输入一组整型元素序列，建立单链表。

5． 写出在带头结点的单向链表l中删除第i个结点的算法。

6． 编写算法,将带头结点的单链表拆分成一个奇数链表和一个偶数链表。

7． 设C={a1,b1,a2,b2,……,an,bn}为一线性表，采用带头结点的Hc单链表存放，编写一个

就地算法，将其拆分成两个线性表，使得：A={a1,a2,…..,an} C={b1,b2,….,bn} 8． 编写出判断带头结点的双向循环链表L是否对称相等的算法。 9． 设计一算法，将一带头结点的数据域依次为a1,a2,…,an(n>=3)的单

吉林大学

数据结构实验报告

班级： 姓名： 学号：

姓名 实验项目 实验性质 学号 第一次上机 □演示性实验□验证性实验 ?操作性实验□综合性实验 实验地点 计算机楼A108 机器编号 2017年11月24日 时 指导教师 江丽 实验时间 分 一、实验目的及要求 题目1： 线性表、堆栈、队列相关算法的实验验证 [实验目的] 验证单链表及其上的基本操作。 [实验内容及要求] 1、 定义单链表类、链式栈类、顺序队列类。 2、 实验验证如下算法的正确性、各种功能及指标： 1）单链表插入操作：分别在当前结点后、表头、表尾插入值为x的结点； 2）单链表删除操作：分别删除表头结点、表尾结点和当前结点的后继结点； 3）查找操作：查找值为x的元素在单链表中出现的位置（是链表中的第几个元素）； 4）压栈和弹栈操作； 5）出队和入队操作（顺序存储） 3、 为便于观察程序的运行结果，设计的输出函数能在输出设备上以图形或表格或其它直观的形式输出计算结果。例如可将链表输出成如下形式： [1]?[2] ?[3] ?[4] ?[5] 4、 测试程序时，对所有输入变量取遍各种有代表性的值。 5、 为了增强程序的可读性，程序中要有适当的注释。 题目2（选做题）

数据结构上机答案

1.1顺序线性表的基本操作 #include #include #define OK 1 #define ERROR 0

#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 #define ElemType int

typedef struct { int *elem,length,listsize; }SqList;

int InitList_Sq(SqList &L) { L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); L.length=0; L.listsize=LIST_INIT_SIZE; return OK; }

int Load_Sq(SqList &L) { int i; if(L.length==0) printf(\ else { printf(\ for(i=0;i

int ListInsert_Sq(SqList &L,int i,int e) { if(i<1||i>L.length+1) return ERROR; ElemType *newbase,

数据结构上机答案

1.1顺序线性表的基本操作 #include #include #define OK 1 #define ERROR 0

#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 #define ElemType int

typedef struct { int *elem,length,listsize; }SqList;

int InitList_Sq(SqList &L) { L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); L.length=0; L.listsize=LIST_INIT_SIZE; return OK; }

int Load_Sq(SqList &L) { int i; if(L.length==0) printf(\ else { printf(\ for(i=0;i

int ListInsert_Sq(SqList &L,int i,int e) { if(i<1||i>L.length+1) return ERROR; ElemType *newbase,

上机实验报告

课程名称： 数据结构A 实验题目： 二叉树操作 专业班级： 计算机1501 学 号： 3150602020 姓名： 经普杰 完成日期： 2016.11.1 成 绩：

实验内容、目的和要求

（一） 实验内容

二叉树的建立和遍历。

（二） 实验目的

1. 进一步掌握指针变量的使用。

2. 掌握二叉树的结构特征以及各种存储结构的特点及使用范围。 3. 掌握用指针类型描述、访问和处理二叉树的运算。

4. 掌握栈或队列的使用。

（三） 实验要求

本实验要求实现以下功能：

1. 按前序次序建立一棵二叉树，以‘＃’表示空。 2. 中序、后序遍历该二叉树，输出遍历序列。

3. 求出该二叉树的深度并输出，或求出该二叉树的叶子数目并输出。

4. 试以栈为辅助存储结构实现二叉树的前序非递归算法或以队列为辅

助存储结构实现二叉树的层次遍历算法。

程序中使用的数据结构及符号说明

主要使用了

While循环语句 for循环语句

北京科技大学 计算机与通信工程学院

实验名称：

学生姓名：

专 业：

班 级：

学 号：

指导教师：

实验成绩：

实验地点：

实验时间：

实 验 报 告

数据结构上机实验

计算机科学与技术

________________________________

2015 年__ __6 ___月

一、实验目的与实验要求

1 实验目的

（1）加深对常用数据结构和算法设计基本思路、思考方法及其适用场合的理解，并能运用于解决实际问题；

（2）能根据特定问题需求，分析建立计算模型（包括逻辑结构和物理结构）、设计算法和程序，并在设计中综合考虑多种因素，对结果的有效性进行分析；

（3）训练分析问题、解决问题的能力以及自主学习与程序设计实践能力；

（4）形成将非数值型问题抽象为计算模型到算法设计、程序实现、结果有效性分析的能力。

2 实验要求

（1）由于在有限的实验课内学时难以较好完成所有实验内容，因此要求在实验课前自主完成部分实验或实验的部分内容；

（2）对于每个实验都要针对问题进行分析，设计出有效的数据结构、算法和程序，对实现结果的正确性进行测试，给

《数据结构》上机实验题目 （共8次，每次上机4小时）

第一阶段（线性部分）

《数据结构》第1上机题 （线性表练习） 1．编程实现书P19 ADT List 基本操作12个：

（1） 用顺序存储结构实现； （2）用链式存储结构实现； 2．编程实现顺序表和单链表的就地逆置（习题集P18 2.21 2.22）。

《数据结构》第2上机题 （线性表练习）

1．分别用顺序结构和单链表结构编程实现下列功能：假设以两个元素依值递增有序排列的线性表A和B 分别表示两个集合，现要求在A的空间上构成一个新线性表C，其元素为A和B元素的交集，且表C中的元素也是依值递增有序排列（习题集P18 2.25 2.26）；

2．设有一个双向循环链表，每个结点中除有pre，data和next三个域外，还增设了一个访问频度域freq。在链表被起作用前，频度域freq的值均初始化为零，而当对链表进行一次LOCATE(L,x)的操作之后，被访问的结点（即元素值等于x的节点）中的频度域freq的值便增1，同时调整链表中结点之间的次序，使其按访问频度非递增的顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编程实现之（习题集P19 2.38）。

《数据结构》 第3

成都信息工程学院计算机系

课程实验报告

实验课程： 数据结构

实验项目： 文本编辑器的实现 指导教师： 李莉丽 学生姓名: 陈德怀 学生学号： 2009053035 班 级： 数媒一班 实验地点： 实验时间： 20 10 年 月 日 点~ 点 实验成绩： 评阅老师：

一【上机实验目的】

要求功能与界面模拟WINDOWS记事本，支持鼠标，因为记事本功能较多，可以根据自己的能力模拟出部分功能，文本编辑这部分功能必须实现，主要利用串的知识。

二【实验环境】

PC机每人1台

三【上机实验内容】

要求功能与界面模拟WINDOWS记事本，支持鼠标，因为记事本功能较多，可以根据自己的能力模拟出部分功能，文本编辑这部分功能必须实现，主要利用串的知识。

四【上机调试程序流程图】（注：可打印）

在此程序中，主要包含了添加、插入、删除、复制、剪切、粘贴、还有文件操作。

五【上机调试中出现的错误信息、错误原因及解决办法】

1、 开始的时候当我输入字符的时候，总是输不进去，经过检查才知道，我忘了把字符输出

到屏幕上。 2、 在删除的时候，当一行删除完的时候，光标并不会上移到上一行。然后我通过判断当这

光标处的坐标减一后

成都信息工程学院计算机系

课程实验报告

实验课程： 数据结构

实验项目： 文本编辑器的实现 指导教师： 李莉丽 学生姓名: 陈德怀 学生学号： 2009053035 班 级： 数媒一班 实验地点： 实验时间： 20 10 年 月 日 点~ 点 实验成绩： 评阅老师：

一【上机实验目的】

要求功能与界面模拟WINDOWS记事本，支持鼠标，因为记事本功能较多，可以根据自己的能力模拟出部分功能，文本编辑这部分功能必须实现，主要利用串的知识。

二【实验环境】

PC机每人1台

三【上机实验内容】

要求功能与界面模拟WINDOWS记事本，支持鼠标，因为记事本功能较多，可以根据自己的能力模拟出部分功能，文本编辑这部分功能必须实现，主要利用串的知识。

四【上机调试程序流程图】（注：可打印）

在此程序中，主要包含了添加、插入、删除、复制、剪切、粘贴、还有文件操作。

五【上机调试中出现的错误信息、错误原因及解决办法】

1、 开始的时候当我输入字符的时候，总是输不进去，经过检查才知道，我忘了把字符输出

到屏幕上。 2、 在删除的时候，当一行删除完的时候，光标并不会上移到上一行。然后我通过判断当这

光标处的坐标减一后