数据结构上机实验报告

数据结构上机实验报告

姓名学号

班级指导老师

实验1有两个整数集合采用有序单链表存储，设计尽可能高效的算法求两个集合的并集、交集和差集。并用相关数据进行测试。

【程序代码】

#include

using std::cout;

using std::cin;

using std::endl;

void main()

{

//定义两个数组

int array1[] = {7,1,2,5,4,3,5,6,3,4,5,6,7,3,2,5,6,6};

int size1 = sizeof(array1) / sizeof(array1[0]);

int array2[] = {8,2,1,3,4,5,3,2,4,5,3,2,1,3,5,4,6,9};

int size2 = sizeof(array2) / sizeof(array2[0]);;

int end = size1;

bool swap = false;//标识变量，表示两种情况中的哪一种

for(int i=0 ; i < end;)

{

swap = false;//开始假设是第一种情况

for(int j=i ; j < size2; j++)//找到与该元素存在相同的元素，将这个相同的元素交换到与该元素相同下标的位置上

{

if(array1[i] == array2[j])//第二种情况，找到了相等的元素

{

int tmp = array2[i];//对数组2进行交换

array2[i] = array2[j];

array2[j] = tmp;

swap = true;//设置标志

break;

}

}

if(swap != true)//第一种情况，没有相同元素存在时，将这个元素交换到尚未进行比较的尾部

{

int tmp = array1[i];

array1[i] = array1[--end];

array1[end] = tmp;

}

else

i++;

}

//结果就是在end表示之前的元素都找到了匹配，而end元素之后的元素都未被匹配

//先输出差集

cout<<"only in array1"<

for(i = end ; i < size1; i++)

{

cout<

}

cout<

cout<<"only in array2"<

for(i = end ; i < size2; i++)

{

cout<

}

cout<

//输出交集

cout<<"elements in array1 and array2"<

for(i = 0 ; i

{

cout<

}

cout<

//输出并集

cout<<"elements in array1 or array2"<

for(i = 0 ; i

{

cout<

}

for(i = end ; i < size1; i++)

{

cout<

}

for(i = end ; i < size2; i++)

{

cout<

}

cout<

}

【运行结果】

实验2假设以I和O字符分别表示进栈和出栈操作，栈的初态和终栈均为空，进栈和出栈的操作序列可表示为仅由I和O组成的序列。如IOIIOIOO序列是合法的，而IOOIOIIO序列是不合法的。设计一个算法判定所给的操作序列是否合法。若合法返回1；否则返回0。（假设被判定的操作序列已存入一维数组中）。并用相关数据进行测试。

【程序代码】

int Judge(char A[]) {

//判断字符数组A中的输入输出序列是否是合法序列。如是，返回true,否则返回false

i=0;

j=k=0; //i为下标，j和k分别为字母I和O的个数

while (A[i]!='\0') { //未到字符数组尾

switch(A[i]){

case 'I' ; j++; break; //入栈次数增1

case 'O' : k++;

if (k>j ) { printf ("序列非法\n") ; exit (0) ; }

}

i++; //不论A[i]是“I”或“0”，指针i均后移

} //while

if (j!=k) {

printf ("序列非法\n" );

return false;

}else{

printf ("序列合法\n");

return true;

}

}

【运行结果】

实验3假设一棵二叉树采用二叉链存储结构，其中所有结点值均不相同。设计一个算法求从根结点到值为x的结点的路径。并用相关数据进行测试。

【程序代码】

#include

#include

#include

#define MAXSIZE 100;

struct PTNode

{

char data;

int parent;

};

typedef struct{

struct PTNode nodes[100];

int r,n;

}PTree;

void CreatPTree(PTree *PT)

{

cout<<" 请输入二叉树根节点的位置r和节点数n：\n" ;

cout<<" 根节点的位置r=";

cin>>PT->r;

cout<<" 二叉树的节点数n=";

cin>>PT->n;

char d;

int p;

cout<<" //***请输入节点和双亲指针\n";

cout<<" //***格式如下：\n";

cout<<" //*** A-1"<

cout<<" //*** B0"<

cout<<" //*** C0"<

cout<<" //*** D1"<

cout<<" //*** ......"<

cout<<" 开始输入"<

for(int i=0;in;i++)

{

cin>>d>>p;

PT->nodes[i].data=d;

PT->nodes[i].parent=p;

}

cout<<" 以下就是节点数是"<n<<"的二叉树"<

for(i=0;in;i++){

cout<nodes[i].data<<" "<nodes[i].parent<

}

}

void path(PTree *PT , char e)

{

int s[20],top=-1;

for(int i=0;in;i++)

if(PT->nodes[i].data==e)

break;

while(i!=PT->r)

{

s[++top]=i;

i=PT->nodes[i].parent;

}

s[++top]=i;

cout<<"根节点到"<

for(;top>0;--top)

cout<nodes[s[top]].data<<"->";

cout<nodes[s[top]].data<<"\n";

}//path

void main(){

cout<<"**********************求二叉树根到给定节点的路径**********************"<

cout<<" *******先创建一棵二叉树，再求这棵树的一个叶子节点到根的路径*******

"<

cout<<"

***************************************************************"<

CreatPTree(PT1);

char e;

cout<<"输入要查找的结点: ";

cin>>e;

path(PT1,e);

}

【运行结果】

《数据结构》实验报告3

实验三——图 一、实验目的 1.掌握图的基本概念； 2.掌握图的存储结构及其建立算法； 3.熟练掌握图的两种遍历算法及其应用。 二、实验内容 1.对给定的图G，设计算法输出从V0出发深（广）度遍历图G的深（广）度优先搜索 序列； 2.设计算法输出给定图G的连通分量个数及边（或弧）的数目。 三、实验预习内容 在实验中要用到这几个函数：typedef struct 邻接矩阵的创建，Locate函数去查找，create函数创建图，定义两个指针firstadj,nextadj找寻临接点和下一个临接点，void dfs函数从某一点开始遍历，void dfsgraph进行图的遍历算法，然后就是main 函数。 四、上机实验 1.实验源程序。 #include #define max 80 int num1=0,num2=0; bool visited[max]; //标记数组 typedef struct //邻接矩阵 { char vexs[max]; int arcs[max][max]; int vexnum,arcnum; } graph; int locate(graph G,char v) //定位 { int i; for(i=0;i>G.vexnum>>G.arcnum; cout<<"Please iput the chars in sequence:";

数据结构上机实验报告

数据结构上机实验报告 数据结构上机实验报告 1、实验目的 本次实验旨在通过实践，加深对数据结构中各种基本数据结构 和算法的理解，并掌握其应用方法，提高编程实践能力。 2、实验内容 2.1 实验环境 2.1.1 硬件环境： - 计算机配置：操作系统，处理器，内存 - 其他硬件设备：无 2.1.2 软件环境： - 开发工具：版本 - 编程语言：版本 - 其他相关软件：无 2.2 实验任务 2.2.1 任务一、线性表的基本操作实现 - 需要实现线性表的初始化、插入、删除、查找等基本操作。

- 使用自定义的数据结构实现线性表，例如顺序表或链表。 2.2.2 任务二、栈和队列的基本操作实现 - 需要实现栈和队列的初始化、压栈、弹栈、入队、出队等基本操作。 - 使用自定义的数据结构实现栈和队列。 2.2.3 任务三、树和图的基本操作实现 - 需要实现树和图的初始化、遍历、添加节点、删除节点等基本操作。 - 使用自定义的数据结构实现树和图。 2.3 实验步骤 2.3.1 任务一实现步骤： 1、按照实验要求，设计并实现线性表的初始化函数。 2、根据实验要求，编写线性表的插入函数，可以在指定位置插入元素。 3、编写线性表的删除函数，可以删除指定位置的元素。 4、实现线性表的查找函数，可以根据元素值查找对应位置。 2.3.2 任务二实现步骤：

1、设计并实现栈的初始化函数。 2、编写栈的压栈函数，将元素添加到栈顶。 3、实现栈的弹栈函数，将栈顶元素弹出。 4、设计并实现队列的初始化函数。 5、编写队列的入队函数，将元素添加到队尾。 6、实现队列的出队函数，将队首元素出队。 2.3.3 任务三实现步骤： 1、设计并实现树的初始化函数。 2、编写树的遍历函数，可以按照先序、中序、后序等方式遍历树的节点。 3、实现树的添加节点函数，可以在指定节点下添加子节点。 4、编写树的删除节点函数，可以删除指定节点及其子节点。 5、设计并实现图的初始化函数。 6、编写图的遍历函数，可以按照广度优先或深度优先方式遍历图的节点。 7、实现图的添加节点函数，可以添加新的节点。 8、编写图的删除节点函数，可以删除指定节点及其相关边。

东北大学数据结构上机实验报告3

实验三树和图应用 一、实验目的 光纤管道铺设施工问题 问题描述 设计校园内有N个教学楼及办公楼，要铺设校园光纤网，如何设计施工方案使得工程总的造价为最省。 二、实验要求 设计校园光纤网铺设的最小生成树模拟程序。 1)采用邻接表或邻接矩阵存储结构。 2)分别采用普利姆算法和克鲁斯卡尔算法实现。 输入形式 对应的教学楼、办公楼数目n，各边权值即每栋楼之间的距离 输出形式 最小生成树，即总路程最小的路 程序功能 设计校园光纤网铺设的最小生成树模拟程序 三、设计概要 流程图 抽象数据类型的定义 class prims { private:

int n; //节点的个数 int graph_edge[99][4]; //图的边 int g; //图中边的个数 int tree_edge[99][4]; //树的边 int t; //树的边的个数 int s; //源节点 int T1[50],t1; // 第一部分 int T2[50],t2; //第二部分 public: void input(); int findset(int); void algorithm(); void output(); }; 各程序模块之间的调用关系 四、详细设计 定义prims类 private中进行对图的创建 public: void input(); int findset(int); void algorithm();

void output(); 开始界面 实现prims类中图的初始化 分别输入图中的顶点个数、图的边及其权值 算法构造 t=0;//初始化边的个数为0 t1=1; T1[1]=1; //资源节点 t2=n-1; int i; for(i=1;i<=n-1;i++) T2[i]=i+1; cout<<"\n\n*****运算开始*****\n\n\n"; while(g!=0 && t!=n-1) { int min=99; int p; int u,v,w; for(i=1;i<=g;i++) { if(findset(graph_edge[i][1])!=findset(graph_edge[i][2])) //如果u和v在不同的部分{ if(min>graph_edge[i][3]) { min=graph_edge[i][3]; u=graph_edge[i][1]; v=graph_edge[i][2]; w=graph_edge[i][3]; p=i; } } } for(int l=p;l

太原理工大学数据结构实验报告

数据结构实验报告 课程名称：数据结构 实验项目：线性表、树、图、查找、内排序实验地点：*********************** 专业班级：物联网**** 学号：********* 学生姓名：

指导教师：周杰伦 2014年*月*日 实验一线性表 目的与要求 本次实习的主要目的是为了使学生熟练掌握线性表的基本操作在顺序存储结构和链式存储结构上的实现，提高分析和解决问题的能力。要求仔细阅读并理解下列例题，上机调试并编译执行通过，并观察其结果，然后独立完成后面的实验内容，写出完整的实验报告。编写程序过程中注意养成良好的编程风格与习惯，要求程序结构清晰，程序缩进，适当注释。 实验仪器 使用的计算机联想：硬件配置cpu-i3等、软件环境win7 实验内容 问题描述：

1．设顺序表A中的数据元素递增有序，试写一程序，将x插入到顺序表的适当位置上，使该表仍然有序。 输入：插入见的顺序表，插入的数，插入后的顺序表 输出：插入前的顺序表，插入的数，插入后的顺序表 存储结构：顺序表存储数据 算法基本思想：这里采用了顺序表来存储数据，主要就是考虑插入的位置是不是在最后一个，如果不是在最后一个，那么就要移动数据了，算法很简单就不在这里的数据都看成是整型的 实验代码 #include #include void Insert(int* p,int length,int n){ int i,j; int flag=0; if(n>=p[length-1]){ p[length]=n; flag=1; } else{ for(i=length-2;i>=0;i--){ if(n>=p[i]){

太原理工数据结构实验报告完整版

实验名称：线性表 一．目的与要求 本次实习的主要目的是为了使学生熟练掌握线性表的基本操作在顺序存储结构和链式存储结构上的实现，提高分析和解决问题的能力。要求仔细阅读并理解下列例题，上机通过，并观察其结果，然后独立完成后面的实习题。 二．例题 [问题描述] 用链表形式存储一个字符串，插入、删除某个字符，最后按正序、逆序两种方式输出字符串。 [输入] 初始字符串，插入位置，插入字符，删除字符。 [输出] 已建立链表（字符串），插入字符后链表，删除字符后链表，逆转后链表。[存储结构] 采用链式存储结构 [算法的基本思想] 建立链表：当读入字符不是结束符时，给结点分配存储空间，写数据域，将新结点插到表尾；插入字符：根据读入的字符在链表中找插入位置，将新结点插入到该位置之前；删除字符：根据读入的删除字符在链表中找到被删结点后，将其从链表中删除；链表逆转：从链表的第一个结点开始对所有结点处理，将每个结点的前驱变为它的后继；打印链表：从链表的第一个结点开始，依次打印各个结点的数据域。 [参考源程序] #define NULL 0 typedef struct node{ char a; struct node *link; }node,*nodelink; void readlink(nodelink head){ nodelink p,q; char c; p=head; printf("Input a linktable(a string):"); scanf("%c",&c); if (c=='\n') printf("This string is empty。"); while(c!='\n'){ q=(nodelink)malloc(sizeof(node)); q->a=c; p->link=q; p=q; scanf("%c",&c); } p->link=NULL;

约瑟夫环数据结构实验报告

数据结构上机实验报告1 班级：1303028姓名：牛雅祺 1、需求分析 1、问题描述：约瑟夫（joseph）问题的一种描述是：编号为1、 2、…、n的n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m。从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列。将他的密码作为新的m的值，从他在顺时针方向上方的下一个人开始重新报数，如此下去，直至所有人全部出列为止。式设计一 个程序求出出列顺序。 2、本演示过程前，首先指定报数上限值，建立循环链表中不需要头结点，注意 空表与非空表的界限。 3、演示过程中输入密码为大于0的正整数，否则无法完成约瑟夫过程。 4、演示程序以用户与计算机的对话方式执行，即在计算机终端上显示“提示信息”后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据和输 出结果显示在其后。 5、程序执行的命令包括： (1)创建链表； (2)删除结点； (3)输出出列 顺序； (4)结束。 6、测试数据 m的初值为20；n=7,7个人的密码依次为：3,1,7,2,4,8,4， 首先m的值为6（正确的出列顺序为6,1,4,7,2,3,5）。 2概要分析 （1）抽象数据类型的定义： 为实现上述程序的功能，可以用整数存储用户的输入。并将用户输入的值存储于线性表中。 算法的基本思想：约瑟夫环问题中的数据是人所在的位置，而这种数据是存在“第一元素、最后元素”，并且存在“唯一的前驱和后继的”，符合线性表的特点。由于需要模拟约瑟夫环的出列问题，可以采用顺序表来实现线性表，完成出列顺序的输出。 核心算法主要分为两步： 1、确定需要删除的位置， 2、设置并删除该位置。 已知报数间隔m，我们可以把当前位置加上m获得需要删除的位置，如果获得的位置超过顺序表中实际元素的总长度，则可以通过减去数组的实际长度来修正（即模拟环状计数）。然后把顺序表中的当前指向位置设置为该位置，继而删掉该位置。 反复进行上述确定位置和删除位置的操作，直到顺序表为空。 （2）主程序的流程： 程序由三个模块组成： （1）输入模块：无提示语句，直接输入总人数n和报数次数m，中间用逗号隔开。 （2）构造链表并输入每个人信息模块： （3）主要处理出列的函数：分别在DOS下和文件中，按移除元素的顺序依

数据结构上机实验报告

数据结构实验报告 课程数据结构 _ 院系 专业班级实验地点 姓名学号 实验时间指导老师 数据结构上机实验报告1 一﹑实验名称： 实验一——链表 二﹑实验目的： 1.了解线性表的逻辑结构特性； 2.熟悉链表的基本运算在顺序存储结构上的实现，熟练掌握链式存 储结构的描述方法； 3.掌握链表的基本操作（建表、插入、删除等） 4. 掌握循环链表的概念，加深对链表的本质的理解。 5.掌握运用上机调试链表的基本方法 三﹑实验内容： （1）创建一个链表 （2）在链表中插入元素 （3）在链表中删除一个元素 （4）销毁链表

四﹑实验步骤与程序 #include #include typedef struct LNode {int data; struct LNode *next; }Lnode, *LinkList; //假设下面的链表均为带头结点。 void CreatLinkList(LinkList &L,int j) {//建立一个链表L,数据为整数，数据由键盘随机输入。 LinkList p,q; L=(LinkList )malloc(sizeof(Lnode)); L->next=NULL; q=L; cout<<"请输入一个链表："<>p->data; p->next=q->next; q->next=p; q=p; }

} int PrintLinkList(LinkList &L) {//输出链表L的数据元素 LinkList p; p=L->next; if(L->next==NULL) { cout<<"链表没有元素!"<data<<" "; p=p->next; } cout<

数据结构上机实验报告

数据结构上机实验报告 欢迎交流（760135448@https://www.wendangku.net/doc/d219169958.html,） 2015年11月20日

上机实验一 1．上机实验简介 1）实验目的 当用户输入一个合法的算术表达式后，能够返回正确的结果。能够计算的运算符包括：加、减、乘、除、括号；能够计算的操作数要求在实数范围内；对于异常表达式能给出错误提示。 2）开发工具 C++语言，Microsoft Visual C++ 6.0开发软件 3）测试数据 分别对一位数、多位数以及小数的四则运算进行检验，我选取了下面几个式子： 3+4-5*(12/6)# 100+20*(26/13)# 1.3+3.4-(5.6/1.2)# 正确计算结果应分别为-3.00、140.00与0.03，用所做程序计算并与正确结果比较。 2．算法说明 (1)概要说明：为实现上述程序功能： 1. 首先置操作数栈为空栈，表达式起始符＃为运算符栈的栈底元素； 2. 依次扫描表达式中每个字符，若是操作数则进OPND栈；若是运算符，则 和OPTR栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求 值完毕。 3. 先做一个适合个位的+-*/运算, 其次就要考虑到对n位和小数点的运算。 (2)程序主要模块 主要模块有：头文件、栈定义及栈函数、运算符判断与优先级比较函数、实现计算函数 { InitStack(&S) 操作结果：构造一个空栈S。 GetTop(S) 初始条件：栈S已存在。 操作结果：用P返回S的栈顶元素。 Push(&S，e) 初始条件：栈S已存在。 操作结果：插入元素ch为新的栈顶元素。 Pop(&S，e) 初始条件：栈S已存在。 操作结果：删除S的栈顶元素。 In(c)

《数据结构》上机实验报告—利用栈实现迷宫求解

《数据结构》上机实验报告—利用栈实现迷宫求解 实验目的： 掌握栈的基本操作和迷宫求解的算法，并能够利用栈实现迷宫求解。实验原理： 迷宫求解是一个常见的路径问题，其中最常见的方法之一是采用栈来实现。栈是一种先进后出的数据结构，适用于这种类型的问题。 实验步骤： 1.创建一个迷宫对象，并初始化迷宫地图。 2.创建一个栈对象，用于存储待探索的路径。 3.将起点入栈。 4.循环执行以下步骤，直到找到一个通向终点的路径或栈为空： a)将栈顶元素出栈，并标记为已访问。 b)检查当前位置是否为终点，若是则路径已找到，结束。 c)检查当前位置的上、下、左、右四个方向的相邻位置，若未访问过且可以通行，则将其入栈。 5.若栈为空，则迷宫中不存在通向终点的路径。 实验结果： 经过多次实验，发现利用栈实现迷宫求解的算法能够较快地找到一条通向终点的路径。在实验中，迷宫的地图可通过一个二维数组表示，其中0表示可通行的路径，1表示墙壁。实验结果显示，该算法能够正确地找

出所有可行的路径，并找到最短路径。实验结果还显示，该算法对于大型迷宫来说，解决速度相对较慢。 实验总结： 通过本次实验，我掌握了利用栈实现迷宫求解的算法。栈作为一种先进后出的数据结构，非常适合解决一些路径的问题。通过实现迷宫求解算法，我深入了解了栈的基本操作，并学会运用栈来解决实际问题。此外，我还了解到迷宫求解是一个复杂度较高的问题，对于大型迷宫来说，解决时间较长。因此，在实际应用中需要权衡算法的速度和性能。 在今后的学习中，我将进一步加深对栈的理解，并掌握其他数据结构和算法。我还将学习更多的路径算法，以便更好地解决迷宫类问题。掌握这些知识将有助于我解决更加复杂的问题，并提升编程能力。

数据结构上机实验报告

数据结构上机实验报告 姓名学号 班级指导老师 实验1有两个整数集合采用有序单链表存储，设计尽可能高效的算法求两个集合的并集、交集和差集。并用相关数据进行测试。 【程序代码】 #include using std::cout; using std::cin; using std::endl; void main() { //定义两个数组 int array1[] = {7,1,2,5,4,3,5,6,3,4,5,6,7,3,2,5,6,6}; int size1 = sizeof(array1) / sizeof(array1[0]); int array2[] = {8,2,1,3,4,5,3,2,4,5,3,2,1,3,5,4,6,9}; int size2 = sizeof(array2) / sizeof(array2[0]);; int end = size1; bool swap = false;//标识变量，表示两种情况中的哪一种 for(int i=0 ; i < end;) { swap = false;//开始假设是第一种情况 for(int j=i ; j < size2; j++)//找到与该元素存在相同的元素，将这个相同的元素交换到与该元素相同下标的位置上 { if(array1[i] == array2[j])//第二种情况，找到了相等的元素

{ int tmp = array2[i];//对数组2进行交换 array2[i] = array2[j]; array2[j] = tmp; swap = true;//设置标志 break; } } if(swap != true)//第一种情况，没有相同元素存在时，将这个元素交换到尚未进行比较的尾部 { int tmp = array1[i]; array1[i] = array1[--end]; array1[end] = tmp; } else i++; } //结果就是在end表示之前的元素都找到了匹配，而end元素之后的元素都未被匹配 //先输出差集 cout<<"only in array1"<

数据结构实验报告总结

数据结构实验报告总结 引言 数据结构是计算机领域中的重要概念之一，涉及到如何存储和组织数据，以便更高效地进行操作和处理。在本次实验中，我们学习了不同的数据结构以及它们的实际应用。通过实践和测试，我们对数据结构的原理和实现方式有了更深入的了解。 实验一：数组和链表 在实验一中，我们研究了数组和链表两种常见的数据结构。数组是一种连续存储的结构，其中的元素在内存中是连续存放的。这使得数组具有随机访问元素的能力，但在插入和删除元素时效率较低。而链表则以节点的形式存储元素，节点之间通过指针链接。链表的插入和删除操作效率较高，但随机访问元素的效率较低。 通过实验测试，我们发现在大部分情况下，数组在查找元素方面的性能更好，而链表在插入和删除元素方面的性能较佳。这与数据结构的特性是一致的。因此，在实际应用中，我们需要综合

考虑数据的访问模式和需求，选择合适的数据结构来提高程序的效率。 实验二：栈和队列 栈和队列是两种基于线性结构的特殊数据结构。栈采用“先进后出”的原则，只能在栈顶进行插入和删除操作。队列则采用“先进先出”的原则，只能在队列的一端插入新元素，并在另一端删除元素。 在实验二中，我们实现了栈和队列的操作，并测试了它们在不同情境下的效果。我们发现，栈在后缀表达式的计算和函数调用中具有重要作用，而队列则在广度优先搜索等算法中发挥着重要的作用。 实验三：树 树是一种非线性的数据结构，它由节点和边组成。节点之间的关系以层次结构进行组织，并形成了树的形状。树的基本概念包括根节点、叶节点和子节点等。

在实验三中，我们研究了树的各种操作和遍历方法。特别是二叉树和二叉搜索树，在实际应用中有着广泛的应用。例如，二叉搜索树可以用于搜索和排序，并且具有较高的效率。 实验四：图 图是一种非常复杂的数据结构，它由节点和边组成。图的节点可以互相连接，并形成复杂的网络结构。图的表达方式多样，例如邻接矩阵和邻接表。图的遍历算法有深度优先搜索和广度优先搜索等。 在实验四中，我们通过实践和测试，掌握了图的基本操作和遍历算法。特别是深度优先搜索，在最短路径问题和拓扑排序中有重要应用。 结论 通过本次实验，我们深入学习了数据结构的原理和实现方式。不同的数据结构有不同的特性和应用场景，我们需要根据具体情

数据结构实验报告

数据结构实验报告 实验一数据结构实验报告 一、实验目的 本实验的目的是通过实践，对数据结构的基本概念和基本操作进行理 解与掌握。通过实验，加深对线性表及其实现方式的认识，并能够编程实 现线性表相应的各种操作。 二、实验内容 1.线性表的顺序存储结构的实现 在本实验中，我们采用顺序存储结构实现线性表。通过编写程序，实 现线性表的初始化、插入、删除、查找等基本操作。具体实现流程如下： a)初始化线性表：申请一定大小的内存空间，用于存储线性表的数据 元素。 b)插入操作：在线性表的任意位置插入一个新元素。若插入位置无效，返回错误提示。 c)删除操作：在线性表中删除指定位置的元素。若删除位置无效，返 回错误提示。 d)查找操作：查找线性表中指定元素的位置。若找到，返回元素所在 位置的序号；若找不到，返回错误提示。 2.线性表的链式存储结构的实现 在本实验中，我们采用链式存储结构实现线性表。通过编写程序，实 现链表的初始化、插入、删除、查找等基本操作。具体实现流程如下：

a)初始化线性表：创建一个头节点，并初始化链表为空。 b)插入操作：在链表的任意位置插入一个新节点。若插入位置无效，返回错误提示。 c)删除操作：删除链表中指定位置的节点。若删除位置无效，返回错误提示。 d)查找操作：查找链表中指定元素的位置。若找到，返回元素所在位置的序号；若找不到，返回错误提示。 三、实验过程与结果分析 1.线性表的顺序存储结构实现 a)实现过程： 首先，定义一个结构体，用于存储线性表的相关信息，包括线性表的总长度、当前长度和数据元素的数组。 然后，编写初始化函数，通过动态分配内存空间，为线性表的数据元素数组分配一定大小的内存空间。 接着，实现插入操作。在插入操作中，判断插入位置是否有效，若无效，则返回错误提示；若有效，则将插入位置以后的所有元素向后移动一位，空出插入位置，将新元素插入到指定位置上。 同样地，实现删除操作。判断删除位置是否有效，若无效，则返回错误提示；若有效，则将删除位置以后的所有元素向前移动一位，覆盖掉删除位置上的元素。

数据结构实验报告及心得体会

2011~2012第一学期数据结构实验报告 班级：信管一班 学号：201051018 姓名：史孟晨

实验报告题目及要求 一、实验题目 设某班级有M（6）名学生，本学期共开设N（3）门课程，要求实现并修改如下程序（算法）。 1. 输入学生的学号、姓名和 N 门课程的成绩（输入提示和输出显示使用汉字系统）， 输出实验结果。（15分） 2. 计算每个学生本学期 N 门课程的总分，输出总分和N门课程成绩排在前 3 名学 生的学号、姓名和成绩。 3. 按学生总分和 N 门课程成绩关键字升序排列名次，总分相同者同名次。 二、实验要求 1．修改算法。将奇偶排序算法升序改为降序。（15分） 2．用选择排序、冒泡排序、插入排序分别替换奇偶排序算法,并将升序算法修改为降序算法；。（45分）） 3．编译、链接以上算法，按要求写出实验报告（25）。 4. 修改后算法的所有语句必须加下划线，没做修改语句保持按原样不动。 5．用A4纸打印输出实验报告。 三、实验报告说明 实验数据可自定义，每种排序算法数据要求均不重复。 (1) 实验题目：《N门课程学生成绩名次排序算法实现》； (2) 实验目的：掌握各种排序算法的基本思想、实验方法和验证算法的准确性； (3) 实验要求：对算法进行上机编译、链接、运行； (4) 实验环境（Windows XP-sp3,Visual c++)； (5) 实验算法（给出四种排序算法修改后的全部清单）； (6) 实验结果（四种排序算法模拟运行后的实验结果）； (7) 实验体会（文字说明本实验成功或不足之处）。

三、实验源程序（算法） Score.c #include "stdio.h" #include "string.h" #define M 6 #define N 3 struct student { char name[10]; int number; int score[N+1]; /*score[N]为总分,score[0]-score[2]为学科成绩*/ }stu[M]; void changesort(struct student a[],int n,int j) {int flag=1,i; struct student temp; while(flag) { flag=0; for(i=1;ia[i+1].score[j]) { temp=a[i]; a[i]=a[i+1]; a[i+1]=temp; flag=1; } for(i=0;ia[i+1].score[j]) { temp=a[i]; a[i]=a[i+1]; a[i+1]=temp; flag=1;

东北大学数据结构实验报告

实 验 报 告 一、实验目(de) （1） 掌握线性表(de)基本操作（插入、删除、查找）以及线性表合并等运算在顺序存储结构、链式存储结构上(de)实现.重点掌握链式存储结构实现(de)各种操作. （2） 掌握线性表(de)链式存储结构(de)应用. 二、实验内容与实验步骤 （1）实验内容： 实现约瑟夫环,约瑟夫环（Joseph ）问题(de)一种描述是：编号为1、2、3……n(de)n 个人按照顺时针方向围坐一圈,每人持有一个密码（正整数）.一开始任选一个正整数作为报数(de)上限值m,从第一个人开始按照顺时针(de)方向自1开始顺序报数,报到m 时停止报数.报m(de)人出列,将他(de)密码作为新(de)m 值,从他(de)顺时针方向上(de)下一个人开始重新从1报数,如此下去,直至所有人全部出列为止.设计一个程序求出出列顺序. 课程名称：数据结构 班级： 实验成绩： 实验名称：顺序表和链表(de)应用 学号： 批阅教师签字： 实验编号：实验一 姓名： 实验日期：2017-11-25 指导教师： 组号： 实验时间：18:30~22:30

（2）抽象数据类型和设计(de)函数描述,说明解决设想. 首先定义一个链表,用其中(de)data项存储每个人(de)编号,用password项存储每个人所持有(de)密码,并且声明一个指针.之后使用CreatList_CL函数来创建一个循环链表,在其中(de)data和password中存入编号和密码,最后使最后一个节点(de)net指向L,使其能够形成循环队列.定义了函数Display来显示链表当中(de)内容,以确定存储(de)数据没有错误.定义了函数Delete_L来实现约瑟夫环中依次删除(de)功能,依次比较,如果某个人所持(de)密码和m值相等,则删除这个结点,并且输出此时该结点(de)编号和密码,实现出列(de)功能. （3）简短明确地写出实验所采用(de)存储结构,并加以说明. 该实验我主要采用(de)是线性表(de)链式存储结构,首先定义了链表(de)结构,其中包括data项和password项,分别存储每个人(de)编号和所持密码,还声明了指向下一个结点(de)指针,该指针可以连接各个结点,并且将最后一个结点(de)指针指向第一个结点使之成为一个循环链表. 三、实验环境 操作系统：Windows 7 调试软件名称：Visio Studio2017 上机地点：信息楼B405 四、实验过程与分析 （1）主要(de)函数或操作内部(de)主要算法,分析这个算法(de)时、空复杂度,并说明设计(de)巧妙之处.

《数据结构》实验1实验报告

南京工程学院实验报告 <班级>_<学号>_<实验X>.RAR文件形式交付指导老师。 一、实验目的 1.熟悉上机环境，进一步掌握语言的结构特点。 2.掌握线性表的顺序存储结构的定义及实现。 3.掌握线性表的链式存储结构——单链表的定义及实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容 1.顺序线性表的建立、插入及删除。 2.链式线性表的建立、插入及删除。 三、实验步骤 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插入元素68。 3.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。 四、程序主要语句及作用 程序1的主要代码(附简要注释) public struct sequenlist { public const int MAXSIZE=1024; /*最大值为1024*/ public elemtype[] vec; public int len; /* 顺序表的长度 */ public sequenlist( int n) { vec=new elemtype[MAXSIZE ]; len = n; } }; class Program { static void Main(string[] args) { sequenlist list1 = new sequenlist(5); for (int i = 0; i < 5; i++) { list1.vec[i] = i; } for (int i = 0; i < 5; i++)

数据结构实验报告--1

理工大学 数据结构与算法 实验报告 实验题目：线性表顺序存储试验实验时间： 实验地点：

班级： 学号： 姓名： 一、实验目的与要求 1、掌握用Visual C++6.0上机调试顺序表的基本方法 2、掌握顺序表的基本操作，插入、删除、查找等算法的实现 [基本要求] 要求生成顺序表时，可以键盘上读取元素，用顺序存储结构实现存储。二、实验意义与原理 当我们要在顺序表的第i个位置上插入一个元素时，必须先将顺序表中第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。若是欲删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置。 三、算法分析 （1）以下为函数运行结果状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 （2）线性表的动态分配顺序存储结构 #define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量 #define LISTINCREMENT 10 //线性表存储空间分配增量 typedef int Status; //函数类型，其值为为函数结果状态代码

typedef int ElemType; //假设数据元素为整型 typedef struct { ElemType *elem; //存储空间基址 int length; //当前长度 int listsize; //当前分配的存储容量 }Sqlist; （2）构造函数 //函数名：InitList() //参数：SqList L //初始条件：无 //功能：构造一个空线性表 Status InitList(Sqlist L) { L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(L.elem==NULL) exit(OVERFLOW); else { L.length=0; L.listsize=LISTINCREMENT; return OK; } } （3）插入函数 //函数名：ListInsert() //参数：SqList L,int i,ElemType e //初始条件：线性表L已存在，1<=i<=ListLength(L)+1 //功能：在线性表中第i个数据元素之前插入数据元素e Status ListInsert(Sqlist L,int i,ElemType e) { int *q=&(L.elem[i-1]); ElemType *newbase,*p; if(i<1||i>(L.length+1)) return ERROR; if(L.length>=L.listsize) { newbase=(ElemType*)realloc(L.elem,L.listsize+LISTINCREMENT*sizeof(ElemType)); if(newbase==NULL) exit(OVERFLOW); L.elem=newbase;