云南大学软件学院数据结构实验

数据结构实验报告实验总结本次数据结构实验主要涉及线性表、栈和队列的基本操作以及链表的应用。

通过实验，我对这些数据结构的特点、操作和应用有了更深入的了解。

下面对每一部分实验进行总结。

实验一：线性表的基本操作线性表是一种常见的数据结构，本实验要求实现线性表的基本操作，包括插入、删除、查找、遍历等。

在实验过程中，我对线性表的结构和实现方式有了更清晰的认识，掌握了用数组和链表两种方式实现线性表的方法。

实验二：栈的应用栈是一种后进先出（LIFO）的数据结构，本实验要求利用栈实现简单的括号匹配和后缀表达式计算。

通过实验，我了解到栈可以方便地实现对于括号的匹配和后缀表达式的计算，有效地解决了对应的问题。

实验三：队列的应用队列是一种先进先出（FIFO）的数据结构，本实验要求利用队列实现银行排队和迷宫求解。

通过实验，我对队列的应用有了更加深入的了解，了解到队列可以解决需要按顺序处理的问题，如排队和迷宫求解等。

实验四：链表的应用链表是一种常用的数据结构，本实验要求利用链表实现学生信息管理系统。

通过实验，我对链表的应用有了更深入的了解，了解到链表可以方便地实现对于数据的插入、删除和修改等操作，并且可以动态地调整链表的长度，适应不同的需求。

通过本次实验，我掌握了线性表、栈、队列和链表的基本操作，并了解了它们的特点和应用方式。

同时，通过实际编程的过程，我对于数据结构的实现方式和效果有了更直观的认识，也锻炼了自己的编程能力和解决问题的能力。

在实验过程中，我遇到了一些问题，如程序逻辑错误和内存泄漏等，但通过调试和修改，最终成功解决了这些问题，对自己的能力也有了更多的信心。

通过本次实验，我深刻体会到了理论与实践的结合的重要性，也对于数据结构这门课程有了更加深入的理解。

总之，本次数据结构实验给予了我很多有益的启发和收获，对于数据结构的概念、特点和应用有了更深入的理解。

在以后的学习中，我会继续加强对数据结构的学习和研究，不断提高自己的编程能力和解决问题的能力。

数据结构实验小结数据结构实验是大二上学期的一门实践课程，通过实验的方式来加深对数据结构的理解和应用。

本次实验主要围绕线性表和栈的实现展开，通过编程实践的方式来深入理解数据结构的基本概念和操作方法。

在实验过程中，我首先对线性表和栈的基本概念进行了复习和理解，掌握了它们的定义、特点以及常用的操作方法。

其次，我通过编写代码来实现线性表和栈的功能，包括插入、删除、查找等操作。

在编写代码的过程中，我发现了一些问题，例如在插入元素的时候没有考虑到空间不足的情况，导致程序出错。

通过不断调试和修改，我逐渐完善了程序的功能，提高了代码的效率和稳定性。

在实验中，我还学会了使用调试工具来查找和解决代码中的问题，例如使用断点、单步调试等方法来追踪程序的执行过程。

这些调试工具为我解决了一些编程中的困惑和疑惑，大大提高了代码的可读性和可维护性。

此外，在实验过程中，我还深刻认识到数据结构对程序性能的影响。

通过对比不同数据结构的实现效果，我发现在处理大规模数据和频繁进行插入、删除操作时，链表结构的性能要优于数组结构。

这给我在实际编程中选择合适的数据结构提供了指导和启示。

通过这门实验课程，我不仅对数据结构有了更加深入的了解，还掌握了一些实际编程的技巧和方法。

我深切体会到了理论与实践相结合的重要性，只有将所学的知识应用到实际中，才能真正加深对知识的理解和掌握。

总的来说，数据结构实验是一门非常有意义的课程，通过实践的方式帮助我们更加深入地了解和应用数据结构。

通过实验，我不仅掌握了数据结构的基本概念和操作方法，还学会了一些实际编程的技巧和方法。

通过这门实验课程的学习，我不仅提升了我的编程能力，还培养了我的实践能力和解决问题的能力。

我相信这些在以后的学习和工作中都会有很大的帮助。

《数据结构》实验报告实验一一、实验目的及要求理解线性表的顺序存储结构；熟练掌握顺序表结构及其有关算法的设计；理解线性表的链式存储结构；熟练掌握动态链表结构及其有关算法的设计；根据具体问题的需要，设计出合理的表示数据的链表结构，并设计相关算法；深入了解栈和队列的特性，以便在实际问题背景下灵活运用他们；同时巩固对这两种结构的构造方法的理解。

二、实验环境硬件：计算机软件：Microsoft Visual C++三、实验内容1.以顺序表作存储结构，实现线性表的插入、删除；2.以单链表作存储结构，实现有序表的合并；3.利用栈（以顺序栈作存储结构）实现进制转换，并用队列（以链队列作存储结构）计算并打印杨辉三角。

四、源程序清单五、实验结果六、总结实验二一、实验目的及要求掌握二叉树的动态存储结构--二叉链表，掌握二叉树的三种遍历方法，会运用三种遍历的方法求解有关问题。

二、实验环境硬件：计算机软件：Microsoft Visual C++三、实验内容1.以二叉链表作存储结构，建立一棵二叉树；2.输出其先序、中序、后序遍历序列；3.求出它的深度；4.统计其叶子结点数四、源程序清单五、实验结果六、总结实验三一、实验目的及要求掌握图的存储结构及其建立算法，熟练掌握图的两种遍历算法及其应用。

二、实验环境硬件：计算机软件：Microsoft Visual C++三、实验内容1.以邻接矩阵法作存储结构，建立一个无向图；2.输出该图的深度优先搜索序列；3.输出该图的广度优先搜索序列；4. 设计算法求出该图的连通分量个数及边的数目。

四、源程序清单五、实验结果六、总结实验四一、实验目的及要求掌握顺序表的查找方法，尤其是折半查找方法。

掌握二叉排序树的查找算法。

二、实验环境硬件：计算机软件：Microsoft Visual C++三、实验内容1.建立一个顺序表，用顺序查找的方法对其实施查找；2.建立一个有序表，用折半查找的方法对其实施查找；3.建立一个二叉排序树，根据给定值对其实施查找；4.对同一组数据，试用三种方法查找某一相同数据，并尝试进行性能分析。

数据结构实验数据结构实验是计算机科学与技术专业的重要课程之一。

通过对这门课程的学习和实验，可以让学生深入了解数据结构在计算机科学中的重要性和应用。

一、实验的目的与意义数据结构实验的主要目的是帮助学生更深入地理解数据结构在计算机科学中的应用。

在实验中，学生可以通过编写代码和执行各种数据结构算法来更好地理解数据结构的实现原理。

通过实验，学生可以更清楚地了解算法的效率、时间复杂度和空间复杂度等概念。

此外，数据结构实验也有助于提高学生的编程能力。

在实验中，学生需要编写具有规范的代码，确保算法的正确性，同时还需要处理大量的数据，这可以提高学生的编程能力和耐心。

二、实验内容简介数据结构实验通常包括以下几个方面的内容：1.线性结构：顺序存储和链式存储线性表、栈、队列等。

2.非线性结构：数组、链表、二叉树等。

3.查找算法：顺序查找、二分查找、哈希查找等。

4.排序算法：插入排序、选择排序、归并排序、堆排序等。

5.图论算法：图的遍历、最短路径、最小生成树等。

6.字符串算法：KMP算法、BM算法等。

三、实验中的具体操作实验中的具体操作是根据具体的算法和数据结构来进行的。

以下是一个简单的例子：线性表的实验假设学生已经学习了顺序存储结构和链式存储结构的操作，以下是在实验中需要进行的具体操作：1.顺序存储结构创建一个空的顺序表插入一个元素到指定位置删除一个元素查找指定元素的位置输出顺序表的所有元素2.链式存储结构创建一个空的链表插入一个元素到指定位置删除一个元素查找指定元素的位置输出链表的所有元素在实验中，学生需要将这些操作封装成具体的函数，并且通过调用这些函数来实现对线性表的操作。

同时，学生还需要进行大量的测试和调试，以保证代码的正确性和实验的效果。

四、实验中的注意事项在进行数据结构实验时，学生需要注意以下几个方面：1.理论和实验相结合：不仅要理解理论知识，还要进行实验操作，才能更好地掌握数据结构。

2.代码规范：要写出规范、可读性强的代码，让他人容易理解。

数据结构形考实践实验一、背景介绍数据结构是计算机科学中重要的基础概念之一，是研究数据组织、存储、管理和操作的方法和原则。

在计算机科学领域，对于数据结构的掌握和实践是非常重要的，因为它直接影响着程序的效率和性能。

为了更好地理解和应用数据结构，形考实践实验是必不可少的一环。

二、实验目的数据结构形考实践实验的目的是通过实际应用的方式，巩固和加深对数据结构的理解，并提高对数据结构的实践能力。

本实验旨在让学生通过解决实际问题的方式，熟悉和掌握常见的数据结构及其应用场景。

三、实验内容3.1实验环境在进行数据结构形考实践实验之前，我们需要准备好实验环境，包括以下方面的内容：-操作系统：建议使用W in do ws/L in ux/M a cO S等常见操作系统；-集成开发环境（ID E）：可以选择V is ua l St ud io Co de、E cl i ps e等常用ID E；-编程语言：可以选择C/C++、J av a、Py t ho n等常用编程语言。

3.2实验步骤在进行数据结构形考实践实验时，我们可以按照以下步骤进行：1.阅读实验要求和相关文献，了解本次形考实验的目标和要求。

2.分析问题需求，确定合适的数据结构和算法。

3.设计和实现相应的数据结构和算法，注意代码的可读性和可维护性。

4.编写测试用例，对实现的数据结构和算法进行测试和验证。

5.解决实际问题，并对实现的数据结构和算法的效率进行评估和分析。

6.总结实验过程和结果，撰写实验报告。

3.3实验要求在进行数据结构形考实践实验时，需要满足以下要求：1.合理选择和使用数据结构和算法，解决实际问题。

2.程序必须能够正确运行，并具有较高的效率和性能。

3.实验报告要求详细描述实验过程、实验结果和分析。

四、实验案例为了更好地理解数据结构的应用，下面我们给出一个实验案例作为参考。

4.1问题描述假设我们需要设计一个学生信息管理系统，其中包括学生姓名、年龄、性别和成绩等信息。

一、实验背景数据结构是计算机科学中一个重要的基础学科，它研究如何有效地组织和存储数据，并实现对数据的检索、插入、删除等操作。

为了更好地理解数据结构的概念和原理，我们进行了一次数据结构实训实验，通过实际操作来加深对数据结构的认识。

二、实验目的1. 掌握常见数据结构（如线性表、栈、队列、树、图等）的定义、特点及操作方法。

2. 熟练运用数据结构解决实际问题，提高算法设计能力。

3. 培养团队合作精神，提高实验报告撰写能力。

三、实验内容本次实验主要包括以下内容：1. 线性表（1）实现线性表的顺序存储和链式存储。

（2）实现线性表的插入、删除、查找等操作。

2. 栈与队列（1）实现栈的顺序存储和链式存储。

（2）实现栈的入栈、出栈、判断栈空等操作。

（3）实现队列的顺序存储和链式存储。

（4）实现队列的入队、出队、判断队空等操作。

3. 树与图（1）实现二叉树的顺序存储和链式存储。

（2）实现二叉树的遍历、查找、插入、删除等操作。

（3）实现图的邻接矩阵和邻接表存储。

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

4. 算法设计与应用（1）实现冒泡排序、选择排序、插入排序等基本排序算法。

（2）实现二分查找算法。

（3）设计并实现一个简单的学生成绩管理系统。

四、实验步骤1. 熟悉实验要求，明确实验目的和内容。

2. 编写代码实现实验内容，对每个数据结构进行测试。

3. 对实验结果进行分析，总结实验过程中的问题和经验。

4. 撰写实验报告，包括实验目的、内容、步骤、结果分析等。

五、实验结果与分析1. 线性表（1）顺序存储的线性表实现简单，但插入和删除操作效率较低。

（2）链式存储的线性表插入和删除操作效率较高，但存储空间占用较大。

2. 栈与队列（1）栈和队列的顺序存储和链式存储实现简单，但顺序存储空间利用率较低。

（2）栈和队列的入栈、出队、判断空等操作实现简单，但需要考虑数据结构的边界条件。

3. 树与图（1）二叉树和图的存储结构实现复杂，但能够有效地表示和处理数据。

数据结构实验报告一、实验目的数据结构是计算机科学中重要的基础课程，通过本次实验，旨在深入理解和掌握常见数据结构的基本概念、操作方法以及在实际问题中的应用。

具体目的包括：1、熟练掌握线性表（如顺序表、链表）的基本操作，如插入、删除、查找等。

2、理解栈和队列的特性，并能够实现其基本操作。

3、掌握树（二叉树、二叉搜索树）的遍历算法和基本操作。

4、学会使用图的数据结构，并实现图的遍历和相关算法。

二、实验环境本次实验使用的编程环境为具体编程环境名称，编程语言为具体编程语言名称。

三、实验内容及步骤（一）线性表的实现与操作1、顺序表的实现定义顺序表的数据结构，包括数组和表的长度等。

实现顺序表的初始化、插入、删除和查找操作。

2、链表的实现定义链表的节点结构，包含数据域和指针域。

实现链表的创建、插入、删除和查找操作。

（二）栈和队列的实现1、栈的实现使用数组或链表实现栈的数据结构。

实现栈的入栈、出栈和栈顶元素获取操作。

2、队列的实现采用循环队列的方式实现队列的数据结构。

完成队列的入队、出队和队头队尾元素获取操作。

（三）树的实现与遍历1、二叉树的创建以递归或迭代的方式创建二叉树。

2、二叉树的遍历实现前序遍历、中序遍历和后序遍历算法。

3、二叉搜索树的操作实现二叉搜索树的插入、删除和查找操作。

（四）图的实现与遍历1、图的表示使用邻接矩阵或邻接表来表示图的数据结构。

2、图的遍历实现深度优先遍历和广度优先遍历算法。

四、实验结果与分析（一）线性表1、顺序表插入操作在表尾进行时效率较高，在表头或中间位置插入时需要移动大量元素，时间复杂度较高。

删除操作同理，在表尾删除效率高，在表头或中间删除需要移动元素。

2、链表插入和删除操作只需修改指针，时间复杂度较低，但查找操作需要遍历链表，效率相对较低。

（二）栈和队列1、栈栈的特点是先进后出，适用于函数调用、表达式求值等场景。

入栈和出栈操作的时间复杂度均为 O(1)。

2、队列队列的特点是先进先出，常用于排队、任务调度等场景。

实验1（2学时）实验名称：线性表及其应用实验内容：1.实现顺序表的删除操作；2.实现单链表的删除操作；3.编程实现单链表相同数据元素删除操作；4.实现带有头结点的单链表的逆置操作。

实验目的与要求：1.深刻理解线性表的抽象数据类型；2.熟练掌握线性表的两种存储方式的基本操作的实现。

实验环境或器材、原理与说明：装有VC++6.0的PC机实验过程（步骤）或程序代码：（必须有）实验预习过程中的问题：（必须有）实验结果与分析：（必须有）实验体会与建议：（必须有）实验2（2学时）实验名称：栈和队列及其应用实验内容：1.实现顺序栈和链栈的出栈、取栈顶元素操作；2.实现循环队列和链队列的出队、取队头元素操作；3.设计算法编程实现，利用循环队列生成杨辉三角形。

实验目的与要求：1.掌握栈的基本操作；2.掌握队列的基本操作；3.会使用栈和队列的基本操作解决较复杂的应用题。

实验环境或器材、原理与说明：装有VC++6.0的PC机实验过程（步骤）或程序代码：（必须有）实验预习过程中的问题：（必须有）实验结果与分析：（必须有）实验体会与建议：（必须有）实验3（2学时）实验名称：串实验内容：1.使用串的堆分配存储方法实现串的基本操作；2.编写程序实现：求子串在主串中的位置，并置换子串。

实验目的与要求：1.了解串的操作特性；2.掌握串的基本操作以顺序存储方式进行存储的实现。

实验环境或器材、原理与说明：装有VC++6.0的PC机实验过程（步骤）或程序代码：（必须有）实验预习过程中的问题：（必须有）实验结果与分析：（必须有）实验体会与建议：（必须有）实验4（4学时）实验名称：树及其应用实验内容：1.完成指导书实训内容“1调试验证”部分；2.创建一颗二叉树，并按其形状显示输出；3.按照先序、中序和后序顺序分别对给定二叉树线索化。

实验目的与要求：1.理解树、二叉树的含义与性质，树和二叉树的存储结构；2.掌握二叉树的三种遍历方法和相应算法。

数据结构实验报告——实验7一、实验目的掌握二叉链表及二叉树的创建、遍历；二、实验内容1、（必做题）假设二叉树中数据元素类型是字符型，请采用二叉链表实现二叉树的以下基本操作：（1）根据二叉树的先序序列和中序序列构造二叉树；（2）根据先序遍历二叉树；（3）根据中序遍历二叉树；（4）根据后序遍历二叉树。

测试数据包括如下错误数据：先序：1234；中序：12345先序：1234；中序：1245先序：1234；中序：42312、（必做题）对于一棵二叉树，请实现：（1）计算二叉树的叶子数目；（2）计算二叉树的深度。

3、（选做题）给定n个权值，请构造它们的最优二叉树（赫夫曼树）。

三、算法描述（采用自然语言描述）1、分别输入n个先序序列和中序序列，先序序列中第一个字符为根节点，在中序序列中找到根节点所在的位置，在根节点左边的为左子树节点，在根节点右边的为右子树节点，然后采用递归的形式依次对左右子树进行构造；二叉树的遍历也是采用递归的形式，先序遍历二叉树：先序遍历根，先序遍历左子树，先序遍历右子树；中序遍历二叉树：中序遍历左子树，中序遍历根，中序遍历右子树；后序遍历二叉树：后序遍历左子树，后序遍历右子树，后序遍历根。

四、详细设计五、程序代码（给出必要注释）1、#include <stdio.h>#include <stdlib.h>#include <malloc.h>#define N 100typedef char ElementType ;typedef struct node{ElementType data ;struct node * leftChild ;struct node * rightChild ;}BTNode;BTNode *createBT(char *pre , char *in ,int n) {BTNode *b;char *p ;int k ;if(n<=0)return NULL;b=(BTNode *)malloc(sizeof(BTNode));b->data = *pre ;int j=0;for(p=in;p<in+n;p++){if(*p == *pre)break;}k=p-in;b->leftChild = createBT(pre+1,in,k);b->rightChild = createBT(pre+1+k,p+1,n-k-1);return b ;void showBTPreOrder(BTNode *b){if(b != NULL){printf("%c ",b->data);showBTPreOrder(b->leftChild);showBTPreOrder(b->rightChild);}}void showBTInOrder(BTNode *b){if(b!=NULL){showBTInOrder(b->leftChild);printf("%c ",b->data);showBTInOrder(b->rightChild);}}void showBTTailOrder(BTNode *b){if(b==NULL)return;showBTTailOrder(b->leftChild);showBTTailOrder(b->rightChild);printf("%c ",b->data);}int main(){char pre[N];char in[N];int n = 0;char ch;BTNode* b=NULL;printf("请输入先序序列\n");while((ch = getchar())&&ch!='\n')pre[n++] = ch;printf("请输入中序序列\n");n = 0;while((ch = getchar())&&ch!='\n')in[n++] = ch;b=createBT(pre,in,n);printf("先序遍历二叉树:\n");showBTPreOrder(b);printf("\n");printf("中序遍历二叉树:\n");showBTInOrder(b);printf("\n");printf("后序遍历二叉树:\n");showBTTailOrder(b);printf("\n");return 0 ;}2、#include <stdio.h>#include <stdlib.h>#include <malloc.h>#define N 100typedef char ElementType ;typedef struct node{ElementType data ;struct node * leftChild ;struct node * rightChild ;}BTNode;BTNode *createBT(char *pre , char *in ,int n) {BTNode *b;char *p ;int k ;if(n<=0)return NULL;b=(BTNode *)malloc(sizeof(BTNode));b->data = *pre ;int j=0;for(p=in;p<in+n;p++){if(*p == *pre)break;}k=p-in;b->leftChild = createBT(pre+1,in,k);b->rightChild = createBT(pre+1+k,p+1,n-k-1);return b ;}int Count(BTNode * top){if(top == NULL){return 0;}else if ((top->leftChild==NULL) && (top->rightChild==NULL)){ return 1;}else{return Count(top->leftChild)+Count(top->rightChild);}}int TreeDepth(BTNode * top){int rightdep=0;int leftdep=0;if(top==NULL)return -1;if(top->leftChild!=NULL)leftdep=TreeDepth(top->leftChild);elseleftdep=-1;if(top->rightChild!=NULL)rightdep=TreeDepth(top->rightChild);elserightdep=-1;return (rightdep>leftdep) ? rightdep+1 : leftdep+1;}int main(){char pre[N];char in[N];int n = 0;char ch;BTNode* b=NULL;printf("请输入先序序列\n");while((ch = getchar())&&ch!='\n')pre[n++] = ch;printf("请输入中序序列\n");n = 0;while((ch = getchar())&&ch!='\n')in[n++] = ch;b=createBT(pre,in,n);printf("二叉树的叶子数目为：%d\n",Count(b));printf("二叉树的深度为：%d\n",TreeDepth(b));return 0 ;}六、测试和结果（给出测试用例，并给出测试结果）1、2、七、用户手册（告诉用户如何使用程序，使用注意事项等）两个程序只能输入字符，并且两次输入的字符个数要一样，字符个数上限为100。

云南大学软件学院实验报告课程：计算机网络原理实验任课教师：姓名：学号：专业：成绩：实验八、Link States Algorithm的实现1．实验目的：通过编程模拟实现LSA.2．实验环境：软件开发平台，可以使用任何编程语言。

3．实验要求（1）求网络中任何两个结点之间的最短路径（网络中至少有4个节点）。

（2）得到任何一个节点上的转发表。

4.实验内容、拓扑结构通过链路状态算法计算A点到其它各点的cost，最终输出A的路由表。

# include<stdio.h># include<stdlib.h># define maxlen 10# define large 999 //(该处设置路径最大值，表示不存在该路线)typedef struct{int vexnum;char vexs[maxlen];int arcs[maxlen][maxlen];}graph;void init_graph(graph *g)//初始化图{int i = 0,j = 0;g -> vexnum = 5; //根据题目此处将图的节点数初始化为5个for(i = 0; i < 5; i++) //经过两层循环将条路径初始化为无穷大for(j = 0; j < 5; j++)g -> arcs[i][j] = 999;g -> arcs[0][1] = 7; g -> arcs[1][0] = 7; //将相邻两个节点的路径初始化为其权值g -> arcs[0][4] = 1; g -> arcs[4][0] = 1;g -> arcs[1][2] = 1; g -> arcs[2][1] = 1;g -> arcs[2][3] = 2; g -> arcs[3][2] = 2;g -> arcs[1][4] = 8; g -> arcs[4][1] = 8;g -> arcs[3][4] = 2; g -> arcs[4][3] = 2;g -> vexs[0] = 'A'; //将节点值初始化g -> vexs[1] = 'B';g -> vexs[2] = 'C';g -> vexs[3] = 'D';g -> vexs[4] = 'E';}void shortpath_dijkstra(graph g)//寻找最短路径{int cost[maxlen][maxlen]; //cost[i][j]: 节点i到节点j的成本int dist[maxlen]; //dist[i]: 源节点到i节点的距离或者是成本int path[maxlen]; //已经经过了的节点int s[maxlen]; //如果 s[i] = 1,那么i节点已经纳入最短路径集合int i,j,v0,min,u;char e;printf("Input the source point(AorBorCorDorE):");//用户输入源节点scanf("%c",&e);switch(e){case'A':v0=0;break;case'B':v0=1;break;case'C':v0=2;break;case'D':v0=3;break;case'E':v0=4;break;}for(i = 0; i < g.vexnum; i++){for(j = 0; j < g.vexnum; j++)cost[i][j] = g.arcs[i][j];}for(i = 0; i < g.vexnum; i++){dist[i] = cost[v0][i]; //初始化源节点到各个节点的成本，如果与源节点相邻则成本为权值，否则为无穷大if(dist[i] < large && dist[i] > 0)path[i] = v0;s[i] = 0;}s[v0] = 1;for(i = 0; i < g.vexnum; i++){min = large;u = v0;for(j = 0; j < g.vexnum; j++)if(s[j] == 0 && dist[j] < min){min = dist[j];u = j;}s[u] = 1;for(j = 0; j < g.vexnum; j++)if(s[j] == 0 && dist[u] + cost[u][j] < dist[j]){dist[j] = dist[u] + cost[u][j];path[j] = u;}}printf("Output%c\n\n",e);for(i = 0; i < g.vexnum; i++)if(s[i] == 1){u = i;while(u != v0){printf(" %c <- ",g.vexs[u]);u = path[u];}printf(" %c ",g.vexs[u]);printf(" :%d \n",dist[i]);}else printf(" %c <- %c: no path \n",g.vexs[i],g.vexs[v0]);}int main(){graph g;init_graph(&g);shortpath_dijkstra(g);system("pause");return 0;}从A点开始，寻找到其余各点的最短路径截图如下：4．实验分析，回答下列问题（1）给出LSA算法的主要思想。

引言概述正文内容
1.实验环境配置
1.1硬件要求
计算机硬件配置要求
操作系统要求
附加硬件设备要求（如虚拟机等）
1.2软件要求
编程语言要求（如C/C++、Java等）开发环境配置（如IDE、编译器等）1.3实验库和工具
实验需要使用的库文件和工具
如何获取和配置实验库和工具
2.实验内容介绍
2.1实验目标和背景
数据结构实验的作用和意义
实验背景和相关应用领域介绍
2.2实验概述
实验内容的大致流程和步骤
实验中可能遇到的问题和挑战
2.3实验要求
对学生实验流程和实验结果的要求
实验过程中需要注意的事项和技巧
3.实验步骤
3.1实验准备
配置实验环境
获取实验所需数据和文件
3.2实验具体步骤
根据实验要求将数据结构知识应用到具体问题中根据实验要求实现相应的算法和数据结构
3.3实验示例代码
提供示例代码以供学生参考和学习
解析示例代码中的关键步骤和实现细节
4.实验答案
4.1实验题目
实验题目及相关说明
确定实验的具体要求和目标
4.2实验答案解析
对实验答案的具体实现进行解析
对实验中可能遇到的问题和错误进行分析和解决4.3实验答案示例
提供实验答案的示例代码
解析实验答案中的关键实现步骤和说明
5.实验总结
5.1实验成果评估
对学生实验成果进行评估
分析实验结果的优点和不足
5.2实验心得
学生对本次实验的收获和感想
学生对未来实验的建议和展望
总结。

一、实验目的1. 理解串的定义、性质和操作；2. 掌握串的基本操作，如串的创建、复制、连接、求子串、求逆序、求长度等；3. 熟练运用串的常用算法，如串的模式匹配算法（如KMP算法）；4. 培养编程能力和算法设计能力。

二、实验环境1. 操作系统：Windows 102. 编程语言：C++3. 开发环境：Visual Studio 2019三、实验内容1. 串的创建与初始化2. 串的复制3. 串的连接4. 串的求子串5. 串的求逆序6. 串的求长度7. 串的模式匹配算法（KMP算法）四、实验步骤1. 串的创建与初始化（1）创建一个串对象；（2）初始化串的长度；（3）初始化串的内容。

2. 串的复制（1）创建一个目标串对象；（2）使用复制构造函数将源串复制到目标串。

3. 串的连接（1）创建一个目标串对象；（2）使用连接函数将源串连接到目标串。

4. 串的求子串（1）创建一个目标串对象；（2）使用求子串函数从源串中提取子串。

5. 串的求逆序（1）创建一个目标串对象；（2）使用逆序函数将源串逆序。

6. 串的求长度（1）获取源串的长度。

7. 串的模式匹配算法（KMP算法）（1）创建一个模式串对象；（2）使用KMP算法在源串中查找模式串。

五、实验结果与分析1. 串的创建与初始化实验结果：成功创建了一个串对象，并初始化了其长度和内容。

2. 串的复制实验结果：成功将源串复制到目标串。

3. 串的连接实验结果：成功将源串连接到目标串。

4. 串的求子串实验结果：成功从源串中提取了子串。

5. 串的求逆序实验结果：成功将源串逆序。

6. 串的求长度实验结果：成功获取了源串的长度。

7. 串的模式匹配算法（KMP算法）实验结果：成功在源串中找到了模式串。

六、实验总结通过本次实验，我对串的定义、性质和操作有了更深入的了解，掌握了串的基本操作和常用算法。

在实验过程中，我遇到了一些问题，如KMP算法的编写和调试，但在老师和同学的指导下，我成功地解决了这些问题。

数据结构课程实验报告目录1. 实验简介1.1 实验背景1.2 实验目的1.3 实验内容2. 实验方法2.1 数据结构选择2.2 算法设计2.3 程序实现3. 实验结果分析3.1 数据结构性能分析3.2 算法效率比较3.3 实验结论4. 实验总结1. 实验简介1.1 实验背景本实验是数据结构课程的一次实践性操作，旨在帮助学生加深对数据结构的理解和运用。

1.2 实验目的通过本实验，学生将学会如何选择合适的数据结构来解决特定问题，了解数据结构与算法设计的关系并能将其应用到实际问题中。

1.3 实验内容本实验将涉及对一些经典数据结构的使用，如链表、栈、队列等，并结合具体问题进行算法设计和实现。

2. 实验方法2.1 数据结构选择在实验过程中，需要根据具体问题选择合适的数据结构，比如针对需要频繁插入删除操作的情况可选择链表。

2.2 算法设计针对每个问题，需要设计相应的算法来实现功能，要考虑算法的效率和实际应用情况。

2.3 程序实现根据算法设计，编写相应的程序来实现功能，并进行调试测试确保程序能够正确运行。

3. 实验结果分析3.1 数据结构性能分析在实验过程中，可以通过对不同数据结构的使用进行性能分析，如时间复杂度和空间复杂度等，以便选择最优的数据结构。

3.2 算法效率比较实验完成后，可以对不同算法在同一数据结构下的效率进行比较分析，找出最优算法。

3.3 实验结论根据实验结果分析，得出结论并总结经验教训，为后续的数据结构和算法设计提供参考。

4. 实验总结通过本次实验，学生将对数据结构与算法设计有更深入的了解，并能将所学知识应用到实际问题中，提高自己的实践能力和解决问题的能力。

实验一顺序表基本操作的实现与应用顺序表的运算·create(sqlist A)：创建顺序表A，并返回其中的元素个数。

·disp(sqlist A,int n)：输出一个具有n个元素的顺序表A。

·ins(sqlist A,int n, int i,elemtype x)：在顺序表A的第i个元素前插入一个元素x。

若i=0，则新元素作为第1个元素；若i=n，则插入在顺序表的最后。

·del(sqlist A, int n, int i)：在顺序表A中删除第i个元素。

·find(sqlist A, int n, elemtype x)：在一个有n个元素的顺序表A中查找元素值为x 的元素。

一、【实验目的】掌握线性表在顺序存储下的插入与删除等基本运算二、【实验内容】1、设计顺序表的基本运算算法。

2、编写一个算法实现两个有序（从小到大）顺序表合并成为一个顺序表，合并后的结果放在第一个顺序表中，不另设新的顺序表存储（假设这两个有序顺序表中没有相同的元素）。

3、请编写26个字母按特定字母值插入或删除的完整程序。

三、【源程序及运行结果】实验二单链表基本操作的实现与应用单链表单链表节点的类型定义如下：typedef int elemtype; //定义数据域的类型typedef struct linknode{ //定义节点类型elemtype data;struct linknode *next;} linknode;单链表的运算·create()：创建单链表，由用户输入各节点data 域的值，以0表示输入结束，最后返回建立的单链表的头指针。

·disp(nodetype *h)：输出单链表h的所有节点的data 域的值。

·len(nodetype *h)：返回单链表h的长度。

·find(nodetype *h,int i)：返回单链表h中第i个节点的指针。

数据结构实验报告一、实验目的数据结构是计算机科学中的重要基础课程，通过本次实验，旨在加深对常见数据结构（如数组、链表、栈、队列、树、图等）的理解和运用，提高编程能力和问题解决能力，培养算法设计和分析的思维。

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

三、实验内容1、数组与链表的实现与操作分别实现整数数组和整数链表的数据结构。

实现数组和链表的插入、删除、查找操作，并比较它们在不同操作下的时间复杂度。

2、栈与队列的应用用数组实现栈结构，用链表实现队列结构。

模拟栈的入栈、出栈操作和队列的入队、出队操作，解决实际问题，如表达式求值、任务调度等。

3、二叉树的遍历构建二叉树的数据结构。

实现先序遍历、中序遍历和后序遍历三种遍历算法，并输出遍历结果。

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

实现图的深度优先搜索（DFS）和广度优先搜索（BFS）算法，并分析它们的时间复杂度。

四、实验步骤1、数组与链表数组的实现：定义一个固定大小的整数数组，通过索引访问和操作数组元素。

链表的实现：定义链表节点结构体，包含数据和指向下一个节点的指针。

插入操作：对于数组，若插入位置在末尾，直接赋值；若不在末尾，需移动后续元素。

对于链表，找到插入位置的前一个节点，修改指针。

删除操作：数组需移动后续元素，链表修改指针即可。

查找操作：数组通过索引直接访问，链表需逐个节点遍历。

2、栈与队列栈的实现：用数组模拟栈，设置栈顶指针。

队列的实现：用链表模拟队列，设置队头和队尾指针。

入栈和出栈操作：入栈时，若栈未满，将元素放入栈顶，栈顶指针加 1。

出栈时，若栈不为空，取出栈顶元素，栈顶指针减 1。

入队和出队操作：入队时，在队尾添加元素。

出队时，取出队头元素，并更新队头指针。

3、二叉树构建二叉树：采用递归方式创建二叉树节点。

先序遍历：先访问根节点，再递归遍历左子树，最后递归遍历右子树。

中序遍历：先递归遍历左子树，再访问根节点，最后递归遍历右子树。

数据结构实验报告1线性表的顺序存储结构一、实验目的本次实验的主要目的是深入理解线性表的顺序存储结构，并通过编程实现其基本操作，包括创建线性表、插入元素、删除元素、查找元素以及输出线性表等。

通过实际操作，掌握顺序存储结构的特点和优势，同时也了解其在不同情况下的性能表现。

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

三、实验原理1、线性表的定义线性表是由 n（n≥0）个数据元素组成的有限序列。

在顺序存储结构中，线性表的元素存储在一块连续的存储空间中，通过数组来实现。

2、顺序存储结构的特点存储密度高，无需额外的指针来表示元素之间的关系。

可以随机访问表中的任意元素，时间复杂度为 O(1)。

插入和删除操作需要移动大量元素，平均时间复杂度为 O(n)。

四、实验内容及步骤1、定义线性表的数据结构｀｀｀cppdefine MAX_SIZE 100 ／／定义线性表的最大长度typedef struct ｛int dataMAX_SIZE; ／／存储线性表元素的数组int length; ／／线性表的当前长度｝ SeqList;｀｀｀2、初始化线性表｀｀｀cppvoid InitList(SeqList L) ｛L>length ＝ 0; ／／初始时线性表长度为 0｝｀｀｀3、判断线性表是否为空｀｀｀cppbool ListEmpty(SeqList L) ｛return （Llength ＝＝ 0)；｝｀｀｀4、求线性表的长度｀｀｀cppint ListLength(SeqList L) ｛return Llength;｝｀｀｀5、按位查找操作｀｀｀cppint GetElem(SeqList L, int i) ｛if （i ＜ 1 ｜｜ i ＞ Llength) ｛printf(＂查找位置不合法!＼n"）；return －1;｝return Ldatai 1;｝｀｀｀6、按值查找操作｀｀｀cppint LocateElem(SeqList L, int e) ｛for （int i ＝ 0; i ＜ Llength; i+＋）｛if （Ldatai ＝＝ e) ｛return i ＋ 1;｝｝return 0; ／／未找到返回 0｝｀｀｀7、插入操作｀｀｀cppbool ListInsert(SeqList L, int i, int e) ｛if （L>length ＝＝ MAX_SIZE) ｛／／表已满printf(＂表已满，无法插入!＼n"）；return false;｝if （i ＜ 1 ｜｜ i ＞ L>length ＋ 1) ｛／／插入位置不合法printf(＂插入位置不合法!＼n"）；return false;｝for （int j ＝ L>length; j ＞＝ i; j) ｛／／移动元素L>dataj ＝ L>dataj 1;｝L>datai 1 ＝ e; ／／插入元素L>length+＋；／／表长加 1return true;｝｀｀｀8、删除操作｀｀｀cppbool ListDelete(SeqList L, int i) ｛if （L>length ＝＝ 0) ｛／／表为空printf(＂表为空，无法删除!＼n"）；return false;｝if （i ＜ 1 ｜｜ i ＞ L>length) ｛／／删除位置不合法printf(＂删除位置不合法!＼n"）；return false;｝for （int j ＝ i; j ＜ L>length; j+＋）｛／／移动元素L>dataj 1 ＝ L>dataj;｝L>length; ／／表长减 1return true;｝｀｀｀9、输出线性表｀｀｀cppvoid PrintList(SeqList L) ｛for （int i ＝ 0; i ＜ Llength; i+＋）｛printf(＂％d ＂， Ldatai)；｝printf(＂＼n"）；｝｀｀｀10、测试用例｀｀｀cppint main(）｛SeqList L;InitList(＆L)；ListInsert(＆L, 1, 10)；ListInsert(＆L, 2, 20)；ListInsert(＆L, 3, 30)；ListInsert(＆L, 4, 40)；ListInsert(＆L, 5, 50)；printf(＂线性表的长度为：％d\n"， ListLength(L)）；printf(＂查找第 3 个元素：％d\n"， GetElem(L, 3)）；int loc ＝ LocateElem(L, 30)；if （loc) ｛printf(＂元素 30 的位置为：％d\n"， loc)；｝ else ｛printf(＂未找到元素 30\n"）；｝ListDelete(＆L, 3)；printf(＂删除第 3 个元素后的线性表：＂）；PrintList(L)；return 0;｝｀｀｀五、实验结果及分析1、实验结果成功创建并初始化了线性表。

实验六、传输层可靠传输协议GBN编程实验报告序号：姓名：学号：成绩指导老师：一、实验目的：1、通过编写实现一个简单可靠的数据传输协议GBN的发送和接收代码，模拟可靠数据传输2、理解TCP协议可靠传输的差错检测、重传、累计确认、定时器的可靠传输策略。

二、实验指导：参考教材。

动画演示：三、实验要求：编程实现一个GBN传输协议的发送方和接收方两程序，采用编程语言不限，要求能将发送――接收流程以及处理方法表现出来.1.实验流程图如下:N2.实验截图与代码如下: 截图: 传送下一个数据包结束代码及注释:一、GBN.h#pragma once#include <stdio.h>//基础功能模块的数据结构声明#define BIDIRECTIONAL 1 /* change to 1 if you're doing extra credit andwrite a routine called B_output *//* a "msg" is the data unit passed from layer 5 (teachers code) to layer4 (students' code). It contains the data (characters) to be delivered tolayer 5 via the students transport level protocol entities. */struct msg{ char data[20];};/* a packet is the data unit passed from layer 4 (students code) to layer3 (teachers code). Note the pre-defined packet structure, which allstudents must follow. */struct pkt{int seqnum;int acknum;int checksum;char payload[20];};#define WINDOWSIZE 8#define MAXBUFSIZE 50#define RTT 15.0#define NOTUSED 0#define NACK -1#define TRUE 1#define FALSE 0#define A 0#define B 1//网络仿真部分数据结构声明***********************************************************struct event{float evtime; /* event time */int evtype; /* event type code */int eventity; /* entity where event occurs */struct pkt *pktptr; /* ptr to packet (if any) assoc w/ this event */ struct event *prev;struct event *next;};/* possible events: */#define TIMER_INTERRUPT 0#define FROM_LAYER5 1#define FROM_LAYER3 2#define OFF 0#define ON 1//基础功能模块的函数声明******************************************************************* void ComputeChecksum(struct pkt *packet);//计算校验和int CheckCorrupted(struct pkt packet);//检查数据是否出错void A_output( struct msg message);//A端向外发送数据void A_input(struct pkt packet);//A端接收数据void A_timerinterrupt();//A计时器超时void A_init();//A端初始化void B_output(struct msg message);void B_input(struct pkt packet);void B_timerinterrupt();void B_init();//网络仿真部分的函数声明**************************************************void init(); //初始化仿真器float jimsrand();//随机数发生器[0,1]//处理事件列表部分的函数声明*********************************************void generate_next_arrival();//产生下一个到达的分组void insertevent(struct event *p);//向事件列表中插入一条新的事件void printevlist();//打印事件列表//******************************************************************** //**********************计时器模块*********************************** void stoptimer(int);//停止计时器void starttimer(int,float);//启动计时器//******************************************************************** *//**************************网络各层之间传送模块***********************void tolayer3(int AorB,struct pkt packet);//向第3层发送信息void tolayer5(int AorB,char datasent[20]);//向第5层发送信息二、GBN.c#include "GBN.h"#include <stdio.h>#include <string.h>#include <stdlib.h>extern int TRACE = 1; /* for my debugging */为我的调试extern int nsim = 0; /* number of messages from 5 to 4 so far */目前为止信息的数字是从5到4extern int nsimmax = 0; /* number of msgs to generate, then stop */如果信息产生的数字为0，然后就停止extern float time = 0.000;float lossprob; /* probability that a packet is dropped */数据包可能会丢失float corruptprob; /* probability that one bit is packet is flipped*/这一点的数据包可能会被弹出去float lambda; /* arrival rate of messages from layer 5 */ 第五层到达的信息的次序int ntolayer3; /* number sent into layer 3 */被传送到第三层的数据static int nlost = 0; /* number lost in media */在媒介中数据丢失static int ncorrupt = 0; /* number co rrupted by media*/被媒介毁坏的数据static int expectedseqnum = 0; /* expected se quence number at receiver side */在接收者这边接收到预期的序列数据static int nextseqnum; /* next sequence number to use in sender side */下一个序列数据使用在发送者这边static int base; /* t he head of sender window */发送者的头窗口struct pkt winbuf[WINDOWSIZE]; /* window packets buffer */数据包缓冲区窗口static int winfront,winrear; /* front and rear points of wind ow buffer */窗口缓冲区的前方点和后方点static int pktnum; /* packet number of window buffer */窗口缓冲区的数据包个数struct msg buffer[MAXBUFSIZE]; /* sender message buffer */发送消息缓冲区int buffront,bufrear; /* front and rear pointers of buffer */缓冲区的前指针与后指针static int msgnum; /* message number of buffer */信息数量的缓冲int packet_lost =0;int packet_corrupt=0;int packet_sent =0;extern int packet_correct=0;extern int packet_resent =0;int packet_timeout=0;extern struct event *evlist = NULL; /* the event list *///计算校验和void ComputeChecksum( struct pkt *packet){int checksum;int i;checksum = packet->seqnum;checksum = checksum + packet->acknum;for ( i=0; i<20; i++ )checksum = checksum + (int)(packet->payload[i]);checksum = 0-checksum;packet->checksum = checksum;}//检查是否出错int CheckCorrupted(struct pkt packet){int checksum;int i;checksum = packet.seqnum;checksum = checksum + packet.acknum;for ( i=0; i<20; i++ )checksum = checksum + (int)(packet.payload[i]);if ( (packet.checksum+checksum) == 0 )return (FALSE);elsereturn (TRUE);}//A端向外发送数据/* called from layer 5, passed the data to be sent to other side */ void A_output(struct msg message){int i;struct pkt sendpkt;/* if window is not full */if ( nextseqnum < base+WINDOWSIZE ){printf("----A: New message arrives, send window is not full, send new messge to layer3!\n");/* create packet */sendpkt.seqnum = nextseqnum;sendpkt.acknum = NOTUSED;for ( i=0; i<20 ; i++ )sendpkt.payload[i] = message.data[i];/* computer checksum */ComputeChecksum (&sendpkt);/* send out packet */tolayer3 (A, sendpkt);/* copy the packet to window packet buffer */winrear = (winrear+1)%WINDOWSIZE;pktnum ++;winbuf[winrear] = sendpkt;for (i=0; i<20; i++)winbuf[winrear].payload[i]= sendpkt.payload[i];/* update state variables */nextseqnum = nextseqnum+1;starttimer(A,RTT);B_input(sendpkt);A_input(sendpkt);}/* if window is full */else{printf("----A: New message arrives, send window is full,");/* if buffer full, give up and exit*/if ( msgnum == MAXBUFSIZE){printf (" Error: Sender buffer is full! \n");exit (1);}/* otherwise, buffer the message */else{printf("buffer new message!\n");bufrear = (bufrear+1) % MAXBUFSIZE;for (i=0; i<20; i++)buffer[bufrear].data[i] = message.data[i];msgnum ++;}}}//B端向外发送数据/* called from layer 5, passed the data to be sent to other side */ void B_output(struct msg message){int i;struct pkt sendpkt;/* if window is not full */if ( nextseqnum < base+WINDOWSIZE ){printf("----A: New message arrives, send window is not full, send new messge to layer3!\n");/* create packet */sendpkt.seqnum = nextseqnum;sendpkt.acknum = NOTUSED;for ( i=0; i<20 ; i++ )sendpkt.payload[i] = message.data[i];/* computer checksum */ComputeChecksum (&sendpkt);/* send out packet */tolayer3 (A, sendpkt);A_input(sendpkt);/* copy the packet to window packet buffer */winrear = (winrear+1)%WINDOWSIZE;pktnum ++;winbuf[winrear] = sendpkt;for (i=0; i<20; i++)winbuf[winrear].payload[i]= sendpkt.payload[i];/* if it is the first packet in window, start timeout */ //if ( base == nextseqnum )//{//starttimer(A,RTT);//printf("----A: start a new timer!\n");// }/* update state variables */nextseqnum = nextseqnum+1;}/* if window is full */else{printf("----A: New message arrives, send window is full,");/* if buffer full, give up and exit*/if ( msgnum == MAXBUFSIZE){printf (" Error: Sender buffer is full! \n");exit (1);}/* otherwise, buffer the message */else{printf("buffer new message!\n");bufrear = (bufrear+1) % MAXBUFSIZE;for (i=0; i<20; i++)buffer[bufrear].data[i] = message.data[i];msgnum ++;}}}//A端接收数据void A_input(struct pkt packet){struct pkt sendpkt;int i;/* if received packet is not corrupted and ACK is received */if ( (CheckCorrupted(packet) == FALSE) && (packet.acknum != NACK) ) {printf("----A: ACK %d is correctly received,",packet.acknum);packet_correct++;/* delete the acked packets from window buffer */winfront = (winfront+(packet.acknum+1-base)) % WINDOWSIZE; pktnum = pktnum - (packet.acknum+1-base);/* move window base */base = packet.acknum+1;stoptimer(A);if ( base < nextseqnum){//starttimer(A,RTT);printf ("\n\n\nsend new packets!");}/* if buffer is not empty, send new packets */while ( (msgnum!=0) && (nextseqnum<base+WINDOWSIZE) ) {/* create packet */sendpkt.seqnum = nextseqnum;sendpkt.acknum = NOTUSED;buffront = (buffront+1) % MAXBUFSIZE;for ( i=0; i<20 ; i++ )sendpkt.payload[i] = buffer[buffront].data[i];/* computer checksum */ComputeChecksum (&sendpkt);/* if it is the first packet in window, start timeout */if ( base == nextseqnum ){//starttimer(A,RTT);printf ("send new packets!\n");}/* send out packet */tolayer3 (A, sendpkt);/* copy the packet to window packet buffer */winrear = (winrear+1)%WINDOWSIZE;winbuf[winrear] = sendpkt;pktnum ++;/* update state variables */nextseqnum = nextseqnum+1;/* delete message from buffer */msgnum --;}}elseprintf ("----A: NACK is received, do nothing!\n");}//B端接收数据*****************************************************一定要调用这个/* Note that with simplex transfer from a-to-B, there is no B_output() */ /* called from layer 3, when a packet arrives for layer 4 at B*/void B_input(struct pkt packet){struct pkt sendpkt;int i;/* if not corrupted and received packet is in order */if ( (CheckCorrupted(packet) == FALSE) && (packet.seqnum == expectedseqnum)){printf("\n----B: packet %d is correctly received, send ACK!\n",packet.seqnum);/* send an ACK for the received packet *//* create packet */sendpkt.seqnum = NOTUSED;sendpkt.acknum = expectedseqnum;for ( i=0; i<20 ; i++ )sendpkt.payload[i] = '0';/* computer checksum */ComputeChecksum (&sendpkt);/* send out packet *///tolayer3 (B, sendpkt);/* update state variables */expectedseqnum = expectedseqnum+1;printf("----B:expectedseqnum = %d\n",expectedseqnum);/* deliver received packet to layer 5 *///tolayer5(B,packet.payload);}/* otherwise, discard the packet and send a NACK */else{printf("----B: packet %d is corrupted or not I expects, send NACK!\n",packet.seqnum);/* create packet */sendpkt.seqnum = NOTUSED;sendpkt.acknum = NACK;for ( i=0; i<20 ; i++ )sendpkt.payload[i] = '0';/* computer checksum */ComputeChecksum (&sendpkt);/* send out packet */tolayer3 (B, sendpkt);}}//A计时器超时/* called when A's timer goes off */void A_timerinterrupt(){int i;printf("----A: time out,resend packets!\n");/* start timer */starttimer(A,RTT);/* resend all packets not acked */for ( i=1; i<=pktnum; i++ ){packet_resent++;tolayer3(A,winbuf[(winfront+i)%WINDOWSIZE]);}}//B计时器超时/* called when B's timer goes off */void B_timerinterrupt(){int i;printf("----B: time out,resend packets!\n");/* start timer */starttimer(B,RTT);/* resend all packets not acked */for ( i=1; i<=pktnum; i++ ){packet_resent++;tolayer3(B,winbuf[(winfront+i)%WINDOWSIZE]);}}//A端初始化/* entity A routines are called. You can use it to do any initialization */void A_init()base = 0;nextseqnum = 0;buffront = 0;bufrear = 0;msgnum = 0;winfront = 0;winrear = 0;pktnum = 0;}//B端初始化/* entity B routines are called. You can use it to do any initialization */void B_init(){expectedseqnum = 0;}//初始化仿真器void init() /* initialize the simulator */{int i;float sum, avg;float jimsrand();FILE *fp;fp = fopen ("parameter.txt","r");printf("----- Stop and Wait Network Simulator Version 1.1 -------- \n\n");printf("Enter the number of messages to simulate: ");//fscanf(fp,"%d",&nsimmax);scanf("%d",&nsimmax);printf("\nEnter packet loss probability [enter 0.0 for no loss]: "); //fscanf(fp, "%f",&lossprob);scanf("%f",&lossprob);printf("\nEnter packet corruption probability [0.0 for no corruption]: "); //fscanf(fp,"%f",&corruptprob);scanf("%f",&corruptprob);printf("\nEnter average time between messages from sender's layer5 [ > 0.0]: ");//fscanf(fp,"%f",&lambda);scanf("%f",&lambda);printf("\nEnter TRACE: ");//fscanf(fp,"%d",&TRACE);scanf("%d",&TRACE);printf("\n\n");srand(9999); /* init random number generator */sum = 0.0; /* test random number generator for students */for (i=0; i<1000; i++)sum=sum+jimsrand(); /* jimsrand() should be uniform in [0,1] */avg = sum/1000.0;/*if(avg < 0.25 || avg > 0.75){printf("It is likely that random number generation on your machine\n" ); printf("is different from what this emulator expects. Please take\n"); printf("a look at the routine jimsrand() in the emulator code. Sorry. \n");exit(0);}*/printf("%f",avg);ntolayer3 = 0;nlost = 0;ncorrupt = 0;time=0.0; /* initialize time to 0.0 */generate_next_arrival(); /* initialize event list */}//随机数发生器float jimsrand(){double mmm = 2147483647; /* largest int - MACHINE DEPENDENT */float x; /* individual students may need to change mmm */x = rand()/mmm; /* x should be uniform in [0,1] */return(x);}//**************************************************************************************//*******************************事件处理部分*******************************************void generate_next_arrival(){double x,log(),ceil();struct event *evptr;float ttime;int tempint;//if (TRACE>2)//printf("-----------------GENERATE NEXT ARRIVAL: creating new arrival\n");x = lambda*jimsrand()*2; /* x is uniform on [0,2*lambda] *//* having mean of lambda */evptr = (struct event *)malloc(sizeof(struct event));evptr->evtime = time + x;evptr->evtype = FROM_LAYER5;if (jimsrand()<0.5){evptr->eventity = A;}evptr->eventity = B;insertevent(evptr);}//向事件列表中插入一条新的事件void insertevent(struct event *p){struct event *q,*qold;if (TRACE>2){//printf(" INSERTEVENT: time is %lf\n",time);//printf(" INSERTEVENT: future time will be %lf\n",p->evtime);}q = evlist; /* q points to front of list in which p struct inserted */if (q==NULL)/* list is empty */{evlist=p;p->next=NULL;p->prev=NULL;}else{for (qold = q; q !=NULL && p->evtime > q->evtime; q=q->next) qold=q;if (q==NULL)/* end of list */{qold->next = p;p->prev = qold;p->next = NULL;}else if (q==evlist)/* front of list */p->next=evlist;p->prev=NULL;p->next->prev=p;evlist = p;}else /* middle of list */{p->next=q;p->prev=q->prev;q->prev->next=p;q->prev=p;}}}//打印事件列表void printevlist(){struct event *q;int i;printf("--------------\nEvent List Follows:\n");for(q = evlist; q!=NULL; q=q->next){printf("Event time: %f, type: %d entity: %d\n",q->evtime,q->evtype,q->eventity);}printf("--------------\n");}//启动计时器void starttimer(int AorB,float increment){struct event *q;struct event *evptr;if (TRACE>2)printf("\n----A: START TIMER: starting timer at %f\n",time);/* be nice: check to see if timer is already started, if so, then warn *//* for (q=evlist; q!=NULL && q->next!=NULL; q = q->next) */for (q=evlist; q!=NULL ; q = q->next)if ( (q->evtype==TIMER_INTERRUPT && q->eventity==AorB) ){//printf("Warning: attempt to start a timer that is already started\n");return;}/* create future event for when timer goes off */evptr = (struct event *)malloc(sizeof(struct event));evptr->evtime = time + increment;evptr->evtype = TIMER_INTERRUPT;evptr->eventity = AorB;insertevent(evptr);}//停止计时器/* called by students routine to cancel a previously-started timer */ void stoptimer(int AorB) /* A or B is trying to stop timer */{struct event *q,*qold;if (TRACE>2)printf("\n----A: STOP TIMER: stopping timer\n");/* for (q=evlist; q!=NULL && q->next!=NULL; q = q->next) */for (q=evlist; q!=NULL ; q = q->next)if ( (q->evtype==TIMER_INTERRUPT && q->eventity==AorB) )/* remove this event */{if (q->next==NULL && q->prev==NULL)evlist=NULL; /* remove first and only event on listelse if (q->next==NULL) /* end of list - there is one in front */ q->prev->next = NULL;else if (q==evlist) /* front of list - there must be event after */{q->next->prev=NULL;evlist = q->next;}else /* middle of list */{q->next->prev = q->prev;q->prev->next = q->next;}free(q);return;}//printf("Warning: unable to cancel your timer. It wasn't running.\n");}//向第三层发送信息/************************** TOLAYER3 ***************/void tolayer3(int AorB,struct pkt packet){struct pkt *mypktptr;struct event *evptr,*q;float lastime, x, jimsrand();int i;ntolayer3++;/* simulate losses: */if (jimsrand() < lossprob){nlost++;if (TRACE>0)printf(" TOLAYER3: packet being lost\n");return;}/* make a copy of the packet student just gave me since he/she may decide *//* to do something with the packet after we return back to him/her */ mypktptr = (struct pkt *)malloc(sizeof(struct pkt));mypktptr->seqnum = packet.seqnum;mypktptr->acknum = packet.acknum;mypktptr->checksum = packet.checksum;for (i=0; i<20; i++)mypktptr->payload[i] = packet.payload[i];if (TRACE>2){printf(" TOLAYER3: seq: %d, ack %d, check: %d ", mypktptr->seqnum,mypktptr->acknum, mypktptr->checksum);for (i=0; i<20; i++)printf("%c",mypktptr->payload[i]);printf("");}/* create future event for arrival of packet at the other side */evptr = (struct event *)malloc(sizeof(struct event));evptr->evtype = FROM_LAYER3; /* packet will pop out from layer3 */ evptr->eventity = (AorB) % 2; /* event occurs at other entity */evptr->pktptr = mypktptr; /* save ptr to my copy of packet *//* finally, compute the arrival time of packet at the other end. medium can not reorder, so make sure packet arrives between 1 and 10 time units after the latest arrival time of packetscurrently in the medium on their way to the destination */lastime = time;/* for (q=evlist; q!=NULL && q->next!=NULL; q = q->next) */for (q=evlist; q!=NULL ; q = q->next)if ( (q->evtype==FROM_LAYER3 && q->eventity==evptr->eventity) ) lastime = q->evtime;evptr->evtime = lastime + 1 + 9*jimsrand();/* simulate corruption: */if (jimsrand() < corruptprob){ncorrupt++;if ( (x = jimsrand()) < .75)mypktptr->payload[0]='Z'; /* corrupt payload */else if (x < .875)mypktptr->seqnum = 999999;elsemypktptr->acknum = 999999;if (TRACE>0)printf(" TOLAYER3: packet being corrupted\n");}//if (TRACE>2)//printf(" TOLAYER3: scheduling arrival on other side\n");insertevent(evptr);}//向第五层发送信息/************************** TOLAYER5 ***************/void tolayer5(int AorB,char datasent[20]){int i;if (TRACE>2){printf(" TOLAYER5: data received: ");for (i=0; i<20; i++)printf("%c",datasent[i]);printf("\n");}}三、GBN-CS.c#include "GBN.h"#include <stdio.h>#include <string.h>#include <stdlib.h>extern int TRACE ; /* for my debugging */extern int nsim ; /* number of messages from 5 to 4 so far */extern int nsimmax; /* number of msgs to generate, then stop */extern float time;extern int packet_correct;extern int packet_resent;extern struct event *evlist;int main(){struct event *eventptr;struct msg msg2give;struct pkt pkt2give;int i,j;char c;init();A_init();B_init();while (1){eventptr = evlist; /* get next event to simulate */ if (eventptr==NULL)goto terminate;evlist = evlist->next; /* remove this event from event list */if (evlist!=NULL)evlist->prev=NULL;if (TRACE >= 2){printf("\nEVENT time: %f,",eventptr->evtime);printf(" type: %d",eventptr->evtype);if (eventptr->evtype==0)printf(", timerinterrupt ");else if (eventptr->evtype==1)printf(", fromlayer5 ");elseprintf(", fromlayer3 ");printf(" entity: %d\n",eventptr->eventity);}time = eventptr->evtime; /* update time to next event time*/if (nsim==nsimmax)break; /* all done with simulation */if (eventptr->evtype == FROM_LAYER5 ){generate_next_arrival(); /* set up future arrival *//* fill in msg to give with string of same letter */j = nsim % 26;for (i=0; i<20; i++)msg2give.data[i] = 97 + j;if (TRACE>2){printf(" MAINLOOP: data given to student: ");for (i=0; i<20; i++)printf("%c", msg2give.data[i]);printf("\n");}nsim++;if (eventptr->eventity == A){A_output(msg2give);}else{B_output(msg2give);}}else if (eventptr->evtype == FROM_LAYER3){pkt2give.seqnum = eventptr->pktptr->seqnum;pkt2give.acknum = eventptr->pktptr->acknum;pkt2give.checksum = eventptr->pktptr->checksum;for (i=0; i<20; i++)pkt2give.payload[i] = eventptr->pktptr->payload[i];if (eventptr->eventity == A) /* deliver packet by calling */ A_input(pkt2give); /* appropriate entity */elseB_input(pkt2give);free(eventptr->pktptr); /* free the memory for packet */ }else if (eventptr->evtype == TIMER_INTERRUPT){if (eventptr->eventity == A)A_timerinterrupt();elseB_timerinterrupt();}else{printf("INTERNAL PANIC: unknown event type \n");}free(eventptr);}terminate:printf(" Simulator terminated at time %f\n after sending %d msgs from layer5\n",time,nsim);printf(" correctly sent pkts: %d \n", packet_correct);printf(" resent pkts: %d \n", packet_resent);system("pause");}附源代码及注释四. 实验小结通过本次试验了解了编程实现简单可靠的数据传输GBN协议，模拟了可靠数据传输理解了TCP协议可靠传输的差错检测、重传、累计确认、定时器的可靠传输策略。

数据结构实验报告总结引言：在学习计算机科学与技术的过程中，数据结构是一个重要的基础课程。

通过实验课的学习，我们不仅可以理解和掌握数据结构的基本概念，还能够通过实践运用所学知识解决实际问题。

本文将对数据结构实验进行总结，介绍实验过程中的收获和体会。

第一章：实验背景与目的本次实验的背景是通过对各种数据结构的实际操作，了解不同数据结构在不同场景下的应用特点。

实验目的是培养我们对数据结构的理论知识与实际运用的能力，锻炼编程与调试的技巧。

第二章：数据结构实验内容与方法本次实验包括线性表、栈、队列、树、图等多个实验，每个实验通过使用不同数据结构解决相关问题。

我们使用C语言进行编程，并运用相应的算法来实现各种数据结构的基本操作。

实验过程中，我们需要运用已学习的数据结构知识，并进行算法设计与分析。

第三章：实验过程与结果在实验过程中，我们首先针对每个数据结构的特点，进行算法设计。

然后，通过编写程序实现算法，并进行调试。

在方法上，我们采用逐步调试的方法，先验证算法的正确性，再进行性能测试。

实验结果表明，我们所实现的数据结构能够解决相关问题，并具有较好的性能。

测试数据的输入规模和复杂度也对运行时间和内存占用有一定的影响。

第四章：实验中的收获与体会通过实验，我们对数据结构的理论知识有了更加深刻的理解。

实践中，我们不仅解决了各种具体问题，还培养了思考和解决问题的能力。

在具体的实验环节中，编程与调试的过程让我们学会了如何运用所学知识解决实际的、复杂的问题。

在实验报告的撰写中，我们进一步锻炼了书面表达的能力。

结论：通过本次数据结构实验，我们深入学习和理解了各种数据结构和算法，锻炼了编程和调试的技巧。

实验中，我们不仅仅是在机械地运用数据结构知识，更是在思考和探索如何将所学知识应用到具体问题中。

这次实验让我们见识到数据结构的强大和灵活性，同时也让我们意识到实践的重要性。

通过实验的整个过程，我们对计算机科学的实际应用有了更深刻的认识，也为以后的学习与工作打下了坚实的基础。