北理工数据结构实验报告4

北京理工大学汇编第四次（分支和循环程序设计实验）报告汇编第四次（分支和循环程序设计实验）报告一、实验要求和目的1．熟悉汇编语言程序设计结构；2．熟悉汇编语言分支程序基本指令的使用方法；3．掌握利用汇编语言实现单分支、双分支、多分支的程序设计方法；4．了解汇编语言循环程序设计的基本流程；5．熟悉汇编语言循环基本指令的使用方法；6．掌握利用汇编语言的循环指令完成循环程序设计方法。

二、软硬件环境1、硬件环境：计算机系统 windows；2、软件环境：装有MASM、DEBUG、LINK、等应用程序。

三、实验涉及的主要知识在实际应用中，经常根据一些条件来选择一条分支执行。

汇编语言的条件判断主要是通过状态寄存器中的状态位、无符号数相减或有符号相减产生的结果来进行。

1．无条件转移指令JMP无条件转移指令JMP是使程序无条件转移至目标处，又分为段内转移、段间转移。

2．条件转移指令JXX条件转移指令可分为三大类：1）．简单条件转移指令。

根据单个标志位的状态判断转移条件。

下表表示条件转移指令标志位的状态：2）．无符号数条件转移指令。

假设在条件转移指令前使用比较指令，比较两个无符号数A，B，指令进行的的操作是A-B，其转移指令如下：3）带符号数条件转移指令。

在汇编程序设计中，要熟练使用循环指令和跳转指令等来实现循环，理解循环体结构中的初始化部分、循环体、结束部分，并且要结合前面分支结构相关的知识点，加深对循环结构的理解和掌握。

循环结构的组成及其设计方法的知识要点有：1、循环程序的基本结构通常由3部分组成1) 初始化部分建立循环初始值,为循环做准备,如设置地址指针,(BX/SI/DI/BP),初始化循环控制变量或计数器(CX),数据寄存器(AX/DX)初值等.2) 循环体循环体是循环程序的主体,是程序中重复执行的程序段.它是由循环工作部分、修改部分、和循环控制部分。

①循环工作部分：完成程序功能的主要程序段，用于解决程序的实际任务；②修改部分：对循环参数进行修改，并为下一次循环做准备；③循环控制部分：判断循环结束条件是否满足。

数据结构实验报告——实验4学号：：得分：______________一、实验目的1、复习线性表的逻辑结构、存储结构及基本操作；2、掌握顺序表和（带头结点）单链表；3、了解有序表。

二、实验容1、（必做题）假设有序表中数据元素类型是整型，请采用顺序表或（带头结点）单链表实现：（1）OrderInsert(&L, e, int (*compare)(a, b))//根据有序判定函数compare，在有序表L的适当位置插入元素e；（2）OrderInput(&L, int (*compare)(a, b))//根据有序判定函数compare，并利用有序插入函数OrderInsert，构造有序表L；（3） OrderMerge(&La, &Lb, &Lc, int (*compare)())//根据有序判定函数compare，将两个有序表La和Lb归并为一个有序表Lc。

2、（必做题）请实现：（1）升幂多项式的构造，升幂多项式是指多项式的各项按指数升序有序，约定系数不能等于0，指数不能小于0；（2）两个升幂多项式的相加。

三、算法描述（采用自然语言描述）1.创建带头节点的链表，输入两个有序表数据La Lb归并两个有序表得有序表Lc输出三个有序表输入需插入数据e将e插入有序表Lc输出插入e后的Lc2.创建链表按指数升序输入多项式得序数和指数输出多项式按指数升序输入第二个多项式得序数和指数两个多项式相加输出第二个多项式和两个多项式得和四、详细设计（画出程序流程图）1.2.五、程序代码（给出必要注释）1.#include<stdio.h>#include<malloc.h>typedef struct LNode{int date;struct LNode *next;} LNode,*Link;typedef struct LinkList{Link head;//头结点int lenth;//链表中数据元素的个数} LinkList;int compare (LinkList *L,int e)//有序判定函数 compare {int Lc=0;Link p;p=L->head;p=p->next;while(p!=NULL){if(e>p->date){p=p->next;Lc++;}elsereturn Lc;}return Lc;}void OrderInsert (LinkList *L,int e,int (*compare)())//根据有序判定函数compare，在有序表L 的适当位置插入元素e；{Link temp,p,q;int Lc,i;temp=(Link)malloc(sizeof(LNode));temp->date=e;p=q=L->head;p=p->next;Lc=(*compare)(L,e);if(Lc==L->lenth){while(q->next!=NULL){q=q->next;}q->next=temp;temp->next=NULL;}else{for(i=0; i<Lc; i++){p=p->next;q=q->next;}q->next=temp;temp->next=p;}++L->lenth;}void OrderMerge (LinkList *La,LinkList *Lb,int (*compare)())//根据有序判定函数 compare ,将两个有序表 La 和 Lb 归并为一个有序表{int i,Lc=0;Link temp,p,q;q=La->head->next;while(q!=NULL){p=Lb->head;temp=(Link)malloc(sizeof(LNode));temp->date=q->date;Lc=(*compare)(Lb,q->date);if(Lc==Lb->lenth){while(p->next!=NULL){p=p->next;}p->next=temp;temp->next=NULL;}else{for(i=0; i<Lc; i++){p=p->next;}temp->next=p->next;p->next=temp;}q=q->next;++Lb->lenth;}}LinkList *Initialize (LinkList *NewList){int i;Link temp;NewList=(LinkList *)malloc((2+1)*sizeof(LinkList));for(i=0; i<2+1; i++){temp=(Link)malloc(sizeof(LNode));temp->date=0;temp->next=NULL;(NewList+i)->head=temp;(NewList+i)->lenth=0;}return NewList;}void Insert (LinkList *NewList){int a,i;char c;printf("在第1个表中插入数据,输入“ N ”再对下个表插入数据 \n");for(i=0; i<2; i++){while(1){scanf("%d",&a);c=getchar();if(c=='N'){if(i<2-2)printf("在第 %d个表中插入数据,输入“ N ”再对下个表插入数据 \n",i+2); else if(i==2-2)printf("在第 %d个表中插入数据,输入“ N ”结束。

数据结构实验报告引言：本实验旨在通过对数据结构的学习和实践，加深对数据结构的理解和运用能力。

在本实验中，我们将探索各种数据结构的特点、优势和适用场景，并通过实验验证它们的效果和性能。

本报告将详细介绍实验的目的、实验设计和实验结果，以及对结果的分析和总结。

一、实验目的：本实验的主要目的是帮助学生理解和掌握以下内容：1. 数据结构的基本概念和分类；2. 各种数据结构的特点、优势和适用场景；3. 数据结构的实现方式和算法；4. 数据结构的性能分析和优化。

二、实验设计：1. 实验环境：本次实验使用的编程语言为C++，开发环境为Visual Studio。

2. 实验内容：本次实验包括以下几个部分：（1）线性表的实现和应用；（2）栈和队列的实现和应用；（3）树和图的实现和应用；（4）排序和查找算法的实现和应用。

3. 实验步骤：（1）根据实验要求，选择合适的数据结构进行实现；（2）编写相应的代码，并进行调试；（3）运行程序，测试数据结构的功能和性能；（4）根据实验结果进行分析和总结。

三、实验结果：1. 线性表的实现和应用：在本次实验中，我们实现了顺序表和链表两种线性表结构，并对它们进行了性能测试。

通过测试，我们发现顺序表适用于频繁进行查找操作的场景，而链表适用于频繁进行插入和删除操作的场景。

2. 栈和队列的实现和应用：我们实现了栈和队列两种数据结构，并进行了相应的性能测试。

通过测试，我们发现栈适用于需要实现后进先出（LIFO）的场景，而队列适用于需要实现先进先出（FIFO）的场景。

3. 树和图的实现和应用：我们实现了二叉树和图两种数据结构，并进行了相应的性能测试。

通过测试，我们发现二叉树适用于需要进行快速查找和排序的场景，而图适用于需要表示复杂关系和网络结构的场景。

4. 排序和查找算法的实现和应用：我们实现了常见的排序和查找算法，并进行了相应的性能测试。

通过测试，我们发现快速排序和二分查找算法在大规模数据处理中具有较高的效率和性能。

《数据结构与算法统计》实验报告学院：班级：学号：姓名：一、实验目的⑴熟悉VC++6.0环境，学习使用C++实现栈的存储结构；⑵通过编程、上机调试，进一步理解栈的基本概念；⑶锻炼动手编程，独立思考的能力。

二、实验内容实现简单计算器的功能,请按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。

要求支持运算符：+、-、*、/、%、（）和=：①从键盘输入一个完整的表达式，以回车作为表达式输入结束的标志；②输入表达式中的数值均为大于等于零的整数，如果中间计算过程中出现小数也只取整进行计算。

例如，输入：4+2*5= 输出：14输入：(4+2)*(2-10)= 输出：-48三、程序设计1、概要设计为实现上述功能，应使用两个栈，分别寄存操作数和运算符。

为此需要栈的抽象数据结构。

⑴栈的抽象数据类型定义如下：ADT Stack{数据对象：D = { ai | ai ∈ElemSet, i=1,…,n，n≥0 }数据关系：R1 = { <ai-1, ai> | ai-1,ai ∈D, i=2, …,n }基本操作：InitStack1(SqStack1 &S)操作结果：创建一个空栈S，以存储运算符InitStack2(SqStack2 &S)操作结果：创建一个空栈S，以存储操作数Push1(SqStack1 &S,char e)初始条件：栈S已存在操作结果：插入运算符e作为新的栈顶元素Push2(SqStack2 &S,int e)初始条件：栈S已存在操作结果：插入操作数e作为新的栈顶元素Precede(char d,char c)初始条件：d，c为运算符操作结果：若d优先级大于c,返回>；若d优先级小于c,返回<；若d优先级等于c,返回=；GetTop1(SqStack1 &S)初始条件：栈S已存在且非空操作结果：用e返回寄存运算符栈S的栈顶元素GetTop2(SqStack2 &S)初始条件：栈S已存在且非空操作结果：用e返回寄存操作数栈S的栈顶元素Pop1(SqStack1 &S,char &e)初始条件：栈S已存在且非空操作结果：删除寄存运算符栈S的栈顶元素Pop2(SqStack2 &S,int &e)初始条件：栈S已存在且非空操作结果：删除寄存操作数栈S的栈顶元素Operate(int a,char theta,int b)初始条件：a，b为整数，theta为运算符操作结果：返回a与b运算的结果EvaluateExpression()初始条件：输入合法的表达式操作结果：返回表达式的值}ADT Stack⑵主程序流程调用EvaluateExpression()函数计算表达式的值，输出在屏幕上。

数据结构实验报告一、实验目的数据结构是计算机科学中非常重要的一门课程，通过本次实验，旨在加深对常见数据结构（如链表、栈、队列、树、图等）的理解和应用，提高编程能力和解决实际问题的能力。

二、实验环境本次实验使用的编程语言为C+＋，开发工具为Visual Studio 2019。

操作系统为 Windows 10。

三、实验内容1、链表的实现与操作创建一个单向链表，并实现插入、删除和遍历节点的功能。

对链表进行排序，如冒泡排序或插入排序。

2、栈和队列的应用用栈实现表达式求值，能够处理加、减、乘、除和括号。

利用队列实现银行排队系统的模拟，包括顾客的到达、服务和离开。

3、二叉树的遍历与操作构建一棵二叉树，并实现前序、中序和后序遍历。

进行二叉树的插入、删除节点操作。

4、图的表示与遍历用邻接矩阵和邻接表两种方式表示图。

实现图的深度优先遍历和广度优先遍历。

四、实验步骤及结果1、链表的实现与操作首先，定义了链表节点的结构体：｀｀｀cppstruct ListNode ｛int data;ListNode next;ListNode(int x) ： data(x)， next(NULL) ｛｝｝；｀｀｀插入节点的函数：｀｀｀cppvoid insertNode(ListNode& head, int val) ｛ListNode newNode ＝ new ListNode(val)；head ＝ newNode;｝ else ｛ListNode curr ＝ head;while （curr>next!＝ NULL) ｛curr ＝ curr>next;｝curr>next ＝ newNode;｝｝｀｀｀删除节点的函数：｀｀｀cppvoid deleteNode(ListNode& head, int val) ｛if （head ＝＝ NULL) ｛return;｝ListNode temp ＝ head;head ＝ head>next;delete temp;return;｝ListNode curr ＝ head;while （curr>next!＝ NULL ＆＆ curr>next>data!＝ val) ｛curr ＝ curr>next;｝if （curr>next!＝ NULL) ｛ListNode temp ＝ curr>next;curr>next ＝ curr>next>next;delete temp;｝｝｀｀｀遍历链表的函数：｀｀｀cppvoid traverseList(ListNode head) ｛ListNode curr ＝ head;while （curr!＝ NULL) ｛std:：cout ＜＜ curr>data ＜＜＂＂；curr ＝ curr>next;｝std:：cout ＜＜ std:：endl;｝｀｀｀对链表进行冒泡排序的函数：｀｀｀cppvoid bubbleSortList(ListNode& head) ｛if （head ＝＝ NULL ｜｜ head>next ＝＝ NULL) ｛return;｝bool swapped;ListNode ptr1;ListNode lptr ＝ NULL;do ｛swapped ＝ false;ptr1 ＝ head;while （ptr1-＞next!＝ lptr) ｛if （ptr1-＞data ＞ ptr1-＞next>data) ｛int temp ＝ ptr1-＞data;ptr1-＞data ＝ ptr1-＞next>data;ptr1-＞next>data ＝ temp;swapped ＝ true;｝ptr1 ＝ ptr1-＞next;｝lptr ＝ ptr1;｝ while （swapped)；｝｀｀｀测试结果：创建了一个包含 5、3、8、1、4 的链表，经过排序后，输出为 1 3 4 5 8 。

数据结构实验报告一、实验目的本实验旨在通过对数据结构的学习和实践，掌握基本的数据结构概念、原理及其应用，培养学生的问题分析与解决能力，提升编程实践能力。

二、实验背景数据结构是计算机科学中的重要基础，它研究数据的存储方式和组织形式，以及数据之间的关系和操作方法。

在软件开发过程中，合理选用和使用数据结构，能够提高算法效率，优化内存利用，提升软件系统的性能和稳定性。

三、实验内容本次实验主要涉及以下几个方面的内容：1.线性表的基本操作：包括线性表的创建、插入、删除、查找、修改等操作。

通过编程实现不同线性表的操作，掌握它们的原理和实现方法。

2.栈和队列的应用：栈和队列是常用的数据结构，通过实现栈和队列的基本操作，学会如何解决实际问题。

例如，利用栈实现括号匹配，利用队列实现银行排队等。

3.递归和回溯算法：递归和回溯是解决很多求解问题的常用方法。

通过编程实现递归和回溯算法，理解它们的思想和应用场景。

4.树和二叉树的遍历：学习树和二叉树的遍历方法，包括前序、中序和后序遍历。

通过编程实现这些遍历算法，加深对树结构的理解。

5.图的基本算法：学习图的基本存储结构和算法，包括图的遍历、最短路径、最小生成树等。

通过编程实现这些算法，掌握图的基本操作和应用。

四、实验过程1.具体实验内容安排：根据实验要求，准备好所需的编程环境和工具。

根据实验要求逐步完成实验任务，注意记录并整理实验过程中遇到的问题和解决方法。

2.实验数据采集和处理：对于每个实验任务，根据要求采集并整理测试数据，进行相应的数据处理和分析。

记录实验过程中的数据和结果。

3.实验结果展示和分析：将实验结果进行适当的展示，例如表格、图形等形式，分析实验结果的特点和规律。

4.实验总结与反思：总结实验过程和结果，回顾实验中的收获和不足，提出改进意见和建议。

五、实验结果与分析根据实验步骤和要求完成实验任务后，得到了相应的实验结果。

对于每个实验任务，根据实验结果进行适当的分析。

《数据结构与算法统计》实验报告学院：班级：学号：姓名：一、实验目的1.熟悉VC++6.0环境，学习使用C++实现链表的存储结构；2.通过编程，上机调试，进一步理解线性表、链表的基本概念。

二、实验内容归并顺序表（选作）。

请按以下要求编程实现：①从键盘输入两个升序排列的整数序列linka和linkb，每个序列以输入0为结束标记。

②将链表linka和linkb归并为linkc，linkc仍然为升序排列。

归并完成后，linka和linkb为空表。

输出linkc。

③对linkc进行处理，保持升序不变，删除其中重复的整数，对重复的整数只保留一个，输出删除重复整数后的链表。

例如：linka输入为：10 20 30 40 50 0linkb输入为：15 20 25 30 35 40 45 50 0归并后的linkc为：10 15 20 20 25 30 30 35 40 40 45 50 50删除重复后的linkc为：10 15 20 25 30 35 40 45 50三、程序设计1、概要设计说明程序的主要功能，主程序的流程以及各个程序模块之间的调用关系，给出主要流程图。

应用单链线性表寄存数字序列。

⑴单链线性表的抽象数据类型线性表的定义如下：ADT LinkList {数据对象：D = { ai | ai ∈ElemSet, i=1,…,n，n≥0 }数据关系：R1 = { <ai-1, ai> | ai-1,ai ∈D, i=2, …,n }基本操作：Creat(LinkList &L)操作结果：构造单链线性表L。

MergeList(LinkList &La,LinkList &Lb,LinkList &Lc)初始条件：单链线性表La，Lb，Lc已经存在。

操作结果：归并La，Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列。

Delete(LinkList &L)初始条件：链表L已经存在。

实验报告四图的存储方式和应用（学科：数据结构）姓名单位班级学号实验日期成绩评定教师签名批改日期实验名称：实验四图的存储方式和应用4.1建立图的邻接矩阵【问题描述】根据图中顶点和边的信息编制程序建立图的邻接矩阵。

【基本要求】（1）程序要有一定的通用性。

（2）直接根据图中每个结点与其他结点的关联情况输入相关信息，程序能自动形成邻接矩阵【测试用例】【实现提示】（1）对图的顶点编号。

（2）在上图中，以顶点1为例，因为顶点2,3,4与顶点1关联，可以输入信息1 2 3 4，然后设法求出与顶点1关联的结点，从而求得邻接矩阵中相应与顶点1的矩阵元素。

实验图4-1【实验报告内容】设计程序代码如下:#include<stdio.h>#define MaxVertexNum 5#define MaxEdgeNum 20#define MaxValue 1000typedef int VertexType;typedef VertexType vexlist [MaxVertexNum];typedef int adjmatrix [MaxVertexNum] [MaxVertexNum];void Createl(vexlist Gv,adjmatrix GA,int n,int e){int i,j,k,w;printf("输入%d个顶点数据\n",n);for(i=0;i<n;i++) scanf("%d",&Gv[i]);for(i=0;i<n;i++)for(j=0;j<n;j++){if(i==j) GA[i][j]=0;else GA[i][j]=MaxValue;}Printf（“输入一条边的两端点序号i和j及边上的权w\n”）;printf("输入%d条无向带权边\n",e);for(k=1;k<=e;k++){scanf("%d%d%d",&i,&j,&w);GA[i][j]=GA[j][i]=w;}}void main(){vexlist vl;adjmatrix a;Createl(vl,a,5,8);}。