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

云南大学软件学院实验报告姓名：王定欢学号：20141120188专业：软件工程日期：2016-10-27 成绩：JAVA实验六一、实验目的：熟悉类的继承以及子类、抽象类的使用。

会使用子类、抽象类，会使用相关构造方法。

二、实验要求：Part1:Write a program called CollegeCourse that computes the cost of taking a college course. Include a constructor that requires a course ID number.Add a subclass Lab to compute a lab fee for a course that uses a lab. Write a program UseCourse to use the classes. Save the programs as CollegeCourse, Lab, and UseCourse. Put them all in a package called b6.For example, the output could be:The cost of your course is $180.0there is a $25.00 lab fee.The cost of your course is $205.0Part2:Create an abstract Auto（汽车） class with fields for the car make and price. Include get and set methods for these fields; the setPrice() method is abstract.Create two subclasses for individual automobile makers (for example, Ford and Chevy) and include appropriate setPrice() methods in each subclass. Finally, write a program that uses the Auto class and subclasses to display information about different cars.Sample Output:A new Ford costs $20000.0A new Chevy costs $22000.0三、实验内容：Part1、CollegeCourse.javapackage b6;public class CollegeCourse {public static String Id = "a123456";public double computCost(){d ouble cost = 180.0;return cost;}}Lab.javapackage b6;public class Lab extends CollegeCourse{public double LabFee(){double labFee = 25.0;return labFee;}}UseCourse.javapackage b6;public class UseCourse{public static void main(String[] args){CollegeCourse cost = new CollegeCourse();Lab labFee = new Lab();System.out.println("Your course Id is:"+CollegeCourse.Id);System.out.println("The cost of your course is:"+putCost());System.out.println("There is a $"+bFee()+" labFee");System.out.println("The cost of your courseis:"+(putCost()+bFee()));}}实验结果：Your course Id is:a123456The cost of your course is:180.0There is a $25.0 labFeeThe cost of your course is:205.0Part2、Auto.javapackage Auto;abstract class Auto {public String carMake;public double price;public void setMake(String carMake){ this.carMake = carMake;}public String getMake(){return carMake;}abstract void setPrice(double price);abstract double getPrice();}Chevy.javapackage Auto;//抽象类不能实例化对象public class Chevy extends Auto{//重写父类方法void setPrice(double price) {// TODO Auto-generated method stubthis.price = price;}double getPrice() {// TODO Auto-generated method stubreturn price;}}Ford.javapackage Auto;public class Ford extends Auto{//抽象类不能实例化对象，不能声明为抽象类@Override//重写父类方法void setPrice(double price) {// TODO Auto-generated method stubthis.price = price;}double getPrice() {// TODO Auto-generated method stubreturn price;}}AutoTest.javapackage Auto;public class AutoTest {public static void main(String[] args) {// TODO Auto-generated method stubFord f = new Ford();Chevy c = new Chevy();f.setPrice(20000);c.setPrice(22000);System.out.println("A new Ford costs:"+f.getPrice());System.out.println("A new Chevy costs:"+c.getPrice());}}实验结果：Part3、附加题：Shape.javapackage Shape;public abstract class Shape {public Shape(){}public abstract double computePerimeter();public abstract double computeArea();public abstract String getType();}class Circle extends Shape{private double radius;public Circle(double radius){//super();this.radius = radius;}public double computePerimeter(){return Math.pow(radius, 2);}public double computeArea(){return Math.pow(radius, 2)*Math.PI;}public String getType(){return"Circle";}}class Rectangle extends Shape{private double length;private double wide;public Rectangle(double length,double wide){super();this.length = length;this.wide = wide;}public double computePerimeter(){return (length+wide)*2;}public double computeArea(){return length*wide;}public String getType(){return"Rectangle";}}class Triangle extends Shape{private double b1,b2,b3;public Triangle(double b1,double b2,double b3){ super();this.b1 = b1;this.b2 = b2;this.b3 = b3;}public double computePerimeter(){return b1+b2+b3;}public double computeArea(){double s = (b1+b2+b3)/2;return Math.sqrt(s*(s-b1)*(s-b2)*(s-b3));}public String getType(){return"Rectangle";}}ShapeInfo.javapackage Shape;public class ShapeInfo {public void printShapeInfo(Shape s){System.out.println("图像类型："+s.getType());System.out.println("周长："+putePerimeter());System.out.println("面积："+puteArea());}}Test.javapackage Shape;public class Test {public static void main(String[] args) {// TODO Auto-generated method stubShape cir = new Circle(4);Shape rec = new Rectangle(5,8);Shape tri = new Triangle(6,6,6);Shape[] shape = new Shape[3];shape[0] = cir;shape[1] = rec;shape[2] = tri;ShapeInfo info = new ShapeInfo();for(Shape s : shape){i nfo.printShapeInfo(s);}}}实验结果：四、实验总结：通过本次实验，认识到了继承、父类、子类之间的关系，同时还学会了如何灵活运用抽象类，继承抽象类的子类必须对基类中的所有抽象方法进行重写，抽象类不能被实例化。

实验难度： A □ B □ C □序号学号姓名成绩指导教师（签名）学期：2017秋季学期任课教师: 刘宇实验题目:组员及组长:承担工作：联系电话:电子邮件:完成提交时间：年月日一、【实验构思（Conceive）】(10%)（本部分应包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计等相关知识，对问题进行概要性地分析）（一）二叉排序树的查找算法及算法原理：对给定的二叉排序树，如果想知道某元素是否在其中出现，可以和根结点比较，如果相等结束；如果不等，若比其大，进入右子树；否则进入左子树；继续按照上面的方法，直到出现相等或者到某分支结束为止，返回查找信息。

（二）哈希表的查找算法及其原理：给定K值，根据造表时设定的哈希函数求得哈希地址，若表中此位置上没有记录，则查找不成功；否则比较关键字，若和给定值相等，则查找成功；否则根据造表时设定的处理冲突的方法找到“下一地址”，直至哈希表中某个位置为“空”或者表中所记录的关键字等于给定值时为止。

二、【实验设计(Design)】(20%)（本部分应包括：抽象数据类型的定义和基本操作说明，程序包含的模块以及各模块间的调用关系，关键算法伪码描述及程序流程图等，如有界面则需包括界面设计，功能说明等）抽象数据类型定义：typedef int KeyType;typedef struct{char *name;int namenum;}Name;typedef struct{Name data;int pos;}HashTable;typedef struct Hash //链地址结构{Name data;int pos;struct Hash *next;}*Hash_P,Hash_L;typedef struct BSTNode{KeyType key;struct BSTNode *lc,*rc;}*BSTree;算法及各模块实现见第七部分【代码】调用关系：三、【实现（Implement）】(30%)（本部分应包括：抽象数据类型各操作的具体实现代码、关键操作的具体算法实现、函数实现，主程序实现等，并给出关键算法的时间复杂度分析。

实验五、六传输层协议分析实验报告序号：姓名：学号：2016 成绩1．实验目的：理解TCP报文首部格式和字段的作用，TCP连接的建立和释放过程，TCP数据传输过程中编号与确认的过程；分析UDP协议报文格式。

2．实验环境：连网环境，可以是局域网，也可以是连入Internet的单机。

3．实验步骤：(1)启动Etherel协议分析软件，并开始抓包。

(2)启动某个基于TCP的应用程序，例如连接某个FTP站点，或通过浏览器访问某个网页。

(3)等出现浏览的网页后停止数据包的捕获。

(4)出现协议分析界面，将filter 一栏填入tcp，则只显示TCP协议信息，通过此信息，可以看到TCP连接的三次握手过程和协商的初始的序列号，数据传输过程以及拆除连接的相应信息。

4．实验分析，回答下列问题实验五 TCP协议分析打开捕获文件,通过捕获的数据包分析TCP建立连接的三次握手的过程，并将TCP建立连接过程中的三个报文填写下来。

字段名称第一条报文第二条报文第三条报文报文序号 1 2 3Sequence Number 0 0 1 Acknowedgement Numbber 0 1 1ACK 0 1 1SYN 1 1 0（1）TCP建立连接时的三个报文，其报文首部与其他TCP报文有什么不同？都使用了SYN 协议。

TCP 建立连接时的三个报文的首部都具有Options 字段，且其Sequence 和Acknowedgement Numbber为0或者1。

SYN是发送标志位，ACK是确认标志位。

（2）报文首部的OPTION字段的作用是什么？值为多少？表明本端所能接收的最大长度的报文段。

值为12bytes。

（3）分析TCP数据传输阶段的前8个报文，将报文信息填入到表中数据传送阶段第一个报文的序号字段值是否等于连接建立时第三个报文的序号？相等(4)捕获一个拆除TCP连接的数据包,附上捕获截图,主要要包含拆除连接的数据包部分,分析TCP释放连接的过程，选择TCP释放连接过程当中的四个报文，将报文信息填在下表。

课程：数据结构实验学期：2014-2015学年第一学期任课教师：专业：信息安全学号：姓名：成绩：实验5 图基础实验一、实验目的1.掌握图的存储结构及其遍历。

二、实验软硬件环境（CPU、OS、IDE）：三、实验任务（要求写出核心代码，并对运行结果截图）1）使用邻接矩阵和邻接表储表示分别实现如下给定的图1、图2、图3所示图的物理存储结构。

2）在1）所建立的图形存储结构上分别实现深度优先搜索遍历和广度优先搜索遍历，并给出遍历结果（序列）。

图3 有向图实验代码：#include<stdio.h>#include<stdlib.h>#define MAXVEX 20#define OK 1#define ERROR 0#define OVERFLOW -1#define INFINITY 65535#define QueueSize 20 //队列中最大元素个数typedef int QElemType; //队列的元素的类型typedef int VertexType;typedef int EdgeType;typedef enum{False,True}Boolean; //Boolean是布尔类型，其值是ture或false Boolean visited[MAXVEX]; //访问标志的数组。

typedef struct{VertexType vexs[MAXVEX];EdgeType arc[MAXVEX][MAXVEX];int numVertexes,numEdges;} MGraph; //邻接矩阵。

typedef struct EdgeNode //边表结点。

{int adjvex;struct EdgeNode *next;}EdgeNode;typedef struct VertexNode //顶点表结点。

{int data;EdgeNode *firstedge;}VertexNode,AdjList[MAXVEX];typedef struct{AdjList adjlist;int numVertexes,numEdges; //图中当前顶点数边数。

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

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

二、实验目的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）二叉树和图的存储结构实现复杂，但能够有效地表示和处理数据。

云南大学软件学院数据结构实验报告（本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助）实验难度： A □ B □ C □学期：任课教师:实验题目: 实验五树及其应用小组长:联系电话:电子邮件:完成提交时间：年月日云南大学软件学院2010学年秋季学期《数据结构实验》成绩考核表学号：姓名：本人承担角色：课题分析，算法设计，程序编写，后期调试，完成实验报告综合得分：（满分100分）指导教师：年月日（注：此表在难度为C时使用，每个成员一份。

）云南大学软件学院2010学年秋季学期《数据结构实验》成绩考核表学号：姓名：本人承担角色：课题分析，算法设计，后期调试，完成实验报告综合得分：（满分100分）指导教师：年月日（注：此表在难度为C时使用，每个成员一份。

）（下面的内容由学生填写，格式统一为，字体: 楷体, 行距: 固定行距18，字号: 小四，个人报告按下面每一项的百分比打分。

难度A满分70分，难度B满分90分）一、【实验构思（Conceive）】(10%)（本部分应包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计、算法等相关知识）1.数据结构算法的知识：●树的定义。

●树的节点和边的表示。

●树的存储结构。

●树的分类：二叉树—》Heffman树。

●树的遍历：前序遍历，中序遍历，后序遍历。

2.面向对象的程序设计相关知识：●C#基本语法知识。

●类的定义，实例化。

●对象的生成调用。

●变量的传递。

二、【实验设计(Design)】(20%)（本部分应包括：抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明，主程序模块与各子程序模块间的调用关系）本实验创建了四个类Form类//用于窗口的初始化，控制各控件的属性和动作Data类//用于本程序所需的频度表数组的生成以及调用HuffmanTree类//用于构造Huffman树以及控制树的各项操作HuffmanTreeNode类//用于构造Huffman树的节点抽象数据类型的功能规格说明：窗口初始化：private void Form1_Load(object sender, EventArgs e)转换模式：private void button1_Click(object sender, EventArgs e)private void button1_Click(object sender, EventArgs e)开始按钮：private void button3_Click(object sender, EventArgs e)声明全局数组：public member[] allMembers = new member[27];定义结构体数组：public struct member{public char ch;//保存频度字符public int frequentness;//保存频度}Data的构造函数（创建Huffman树）public Data()Data类中的寻找当前最大项函数：public int FindMax()Data类中的寻找当前第二大项函数：public int FindSecondMax()Data类中的计算当前有效项的数目的函数：public int Count() HuffmanTreeNode类中创建节点的构造函数：public HuffmanTreeNode (char ch2 ,int frequentness2)HuffmanTree类中定义的节点类型：public HuffmanTreeNode root,p,r; HuffmanTree类中实例化一个Data类来构造频度表：public DatafrequentnessTable; HuffmanTree类中的构造函数，创建一棵Huffman树：public HuffmanTree() HuffmanTree类中的成员函数，对于指定的字符实行中序遍历，遍历完之后逆向回溯得到该字符的Huffman编码：public int SearchTree()HuffmanTree类中的两个节点变量，用于判断左右子树：public int SearchTree()主程序模块伪代码说明：创建新的字母频度表：frequentnessTable = new Data();创建栈来倒装输出赫夫曼编码：Stack<char> HuffmanCode = Stack<char>;退出程序：this.Close（）子程序伪代码说明（HuffmanTree）：构建Huffman树：public HuffmanTreeNode root,p,r;核心程序段（生成Huffman编码）：while (r == root){r = p.parent;if (p == r.left)HuffmanCode.Push('1');//栈中存1elseHuffmanCode.Push('0');//栈中存0p = p.parent;}返回栈中元素个数：public int count { get{ return list.Count; } }主程序模块与各子程序模块间的调用关系：Class Form1调用Class Data初始化程序所要的各项数据。

一、实训目的本次数据结构实训旨在通过实践操作，加深对数据结构理论知识的理解，提高解决实际问题的能力。

通过实训，使学生能够熟练掌握各种基本数据结构及其操作方法，并能够将这些知识应用于解决实际问题。

二、实训环境1. 操作系统：Windows 102. 编程语言：C语言3. 开发环境：Visual Studio 20194. 实训教材：《数据结构》（C语言版）三、实训内容本次实训主要内容包括线性表、栈、队列、树、图等基本数据结构的创建、操作和应用。

1. 线性表（1）单链表的创建、插入、删除和查找操作（2）双向链表的创建、插入、删除和查找操作（3）循环链表的创建、插入、删除和查找操作2. 栈（1）栈的创建、入栈、出栈和判断栈空操作（2）应用栈实现括号匹配3. 队列（1）队列的创建、入队、出队和判断队列空操作（2）应用队列实现广度优先搜索4. 树（1）二叉树的创建、插入、删除和遍历操作（2）二叉查找树的创建、插入、删除和查找操作5. 图（1）图的创建、添加边、删除边和遍历操作（2）图的深度优先遍历和广度优先遍历四、实训过程1. 线性表首先，我们学习了单链表、双向链表和循环链表的基本概念和创建方法。

通过编写代码，实现了链表的插入、删除和查找操作。

在实训过程中，我们遇到了一些问题，如链表插入操作时指针的移动、删除操作时避免内存泄漏等。

通过查阅资料和与同学讨论，我们逐步解决了这些问题。

2. 栈接着，我们学习了栈的基本概念和操作方法。

通过编写代码，实现了栈的创建、入栈、出栈和判断栈空操作。

在实训过程中，我们遇到了栈空和栈满的情况，通过设置标志位和循环队列的方法解决了这些问题。

此外，我们还学习了应用栈实现括号匹配，加深了对栈的应用理解。

3. 队列然后，我们学习了队列的基本概念和操作方法。

通过编写代码，实现了队列的创建、入队、出队和判断队列空操作。

在实训过程中，我们遇到了队列空和队列满的情况，通过设置标志位和循环队列的方法解决了这些问题。

数据结构实验报告第 6 次实验一、实验目的1．理解栈是操作受限（插入push, 删除pop）的线性表, 受限的是插入删除的位置。

2．在链式存储结构下实现：StackEmpty, Push,Pop, 几个基本操作。

3．通过调用基本操作实现括号匹配算法。

二、实验内容（问题）写一个算法, 识别依次读入的一个字符序列是否为形如‘序列1&序列2’模式的字符序列。

其中序列1和序列2中都不含字符‘&’, 且序列2是序列1的逆序列。

例如, ‘a+b&b+a’是属该模式的字符序列, 而’1+3&3-1’则不是。

测试数据: ’1+3&3-1’; ’a+b+c&c+b+a’; ’a+b+c&c+b’; ’b+c&c+b+a’;提示：利用栈 , 利用已实现的基本操作三、算法描述（给出自然语言描述的算法）1.向后依次扫描字符序列, 如果考察的字符不等于‘&’则入栈, 遇到‘&’则停止。

2.从‘&’后继续扫描, 考察字符的时候, 栈顶元素出栈, 若二者相等, 继续扫描；不等, 模式不成立。

3.扫描结束后, 栈空则模式成立四、详细设计（画流程图）五、程序代码#include<stdio.h>#include<stdlib.h>#define True 1#define False 0#define OK 1#define ERROR 0typedef int status;typedef char ElemType;typedef struct SNode{ElemType data;struct SNode *next;}SNode, *LinkStack;status InitStack(LinkStack &S);int StackEmpty(LinkStack S);status Push(LinkStack &S, ElemType e);status Pop(LinkStack &S, ElemType &e);status Is_Match(ElemType f[20]);main(){ElemType formula[20];int i;for(i=0;i<=3;i++){printf("\n请输入一个字符序列表达式: ");scanf("%s",formula);if(Is_Match(formula)==1) printf(" \n这个表达式符合‘序列1&序列2’模式！\n"); else printf("\n 这个表达式不符合‘序列1&序列2’模式！\n");}return(1);}status InitStack(LinkStack &S){S=NULL;return(OK);}int StackEmpty(LinkStack S){if(S==NULL) return(True);else return(False);}status Push(LinkStack &S, ElemType e){LinkStack p;p=(LinkStack)malloc(sizeof(SNode));if(!p) return(ERROR);p->data=e;p->next=S;S=p;return(OK);}status Pop(LinkStack &S, ElemType &e){LinkStack p;if(!S) return(ERROR);e=S->data;p=S;S=S->next;free(p);return(OK);}status Is_Match(ElemType f[20]){LinkStack St; ElemType *p,c;InitStack(St);p=f;for(;*p!='&';p++){ Push(St,*p);if(!Push(St, *p)) return(ERROR);}p++;for(;*p!='\0';p++){Pop(St,c);if(!Pop(St,c)) return(ERROR);else if(c!=*p) return(ERROR);}if(StackEmpty(St)) return(OK);else return(ERROR);}七、用户手册（教用户怎么用这个程序）用途: 判断字符串是否是“序列1&序列2’模式”用法：启动此程序, 屏幕会提示你输入数据, 输入数据并按下回车键即可。

云南大学软件学院数据结构实验报告（本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助）实验难度：A□ B □ C ■序号学号姓名成绩12指导教师：（签名）学期：2012秋季学期任课教师:实验题目: 图及其应用小组长:联系电话:电子邮件:完成提交时间：2012年12月 20日云南大学软件学院2012学年秋季学期《数据结构实验》成绩考核表学号：姓名：本人承担角色：小组长综合得分：（满分100分）指导教师：年月日学号：姓名：本人承担角色：组员综合得分：（满分100分）指导教师：年月日（注：此表在难度为C时使用，每个成员一份。

）一、【实验构思（Conceive）】(10%)（本部分应包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计、算法等相关知识）本实验要求设计一个校园导游系统，要求通过图这一数据结构计算两点之间的最短距离，实现校园导航功能。

首先要收集校园景点信息和景点之间的距离信息，然后利用图存储校园景点信息和景点之间的距离信息，最后使用Dijkstra算法计算最短路径。

离散数学相关知识：正确合理使用与或非之间的关系，进行程序分支判断，保证程序正常进行，以及图的使用。

二、【实验设计(Design)】(20%)本次实验使用C进行编写，自定义函数2个：void init_graph(graph *g)//图的初始化函数void shortest_path(graph *g,int s, int t,int n)//求最短路径的算法主函数为功能选择界面三、【实现描述（Implement）】(30%)主函数显示开始界面，选择相应的功能求最短路径。

人性化设计：1.在输入出现错误时例如功能选择错误时，程序会给出友好的提示；2. 界面友好，容易上手。

四、【代码】(10%)#include<iostream>#include<stdio.h>#include<stdlib.h>#include<windows.h>#define INFINITY 9999 //最大距离#define MAX_NODES 30 //最大结点数int dist[MAX_NODES][MAX_NODES]; //dist[i][j]表示i、j连线的权重int path[MAX_NODES];using namespace std;typedef struct VertexType{char* sight; //景点名称//char* info; //景点描述}VertexType; //定义顶点的类型typedef struct{int vexnum;VertexType vex[MAX_NODES];}graph;void init_graph(graph *g){int a,x,y=0;g->vexnum = 27;g->vex[0].sight="云大西二门";g->vex[1].sight="百家道";g->vex[2].sight="文典广场";g->vex[3].sight="云大会堂";g->vex[4].sight="中山邦翰楼";g->vex[5].sight="仰止楼";g->vex[6].sight="桦苑";g->vex[7].sight="楠苑";g->vex[8].sight="格物楼";g->vex[9].sight="楠苑体育场";g->vex[10].sight="知味堂";g->vex[11].sight="楠苑超市";g->vex[12].sight="综合服务楼";g->vex[13].sight="楸苑";g->vex[14].sight="力行楼";g->vex[15].sight="软件楼";g->vex[16].sight="校医院";g->vex[17].sight="明远楼";g->vex[18].sight="至公大道";g->vex[19].sight="行政办公楼";g->vex[20].sight="云大北门";g->vex[21].sight="文汇楼";g->vex[22].sight="余味堂";g->vex[23].sight="梓苑超市";g->vex[24].sight="梓苑";g->vex[25].sight="钟楼";g->vex[26].sight="校车乘车点";for(x=0;x<g->vexnum;x++)for(y=0;y<g->vexnum;y++)dist[x][y]=INFINITY;//下边是可直接到达的景点间的距离，由于两个景点间距离是互相的，所以要对图中对称的边同时赋值 dist[0][1]=dist[1][0]=10;dist[1][2]=dist[2][1]=20;dist[2][3]=dist[3][2]=20;dist[1][4]=dist[4][1]=50;dist[4][5]=dist[5][4]=200;dist[4][6]=dist[6][4]=130;dist[5][7]=dist[7][5]=600;dist[5][8]=dist[8][5]=800;dist[5][9]=dist[9][5]=600;dist[7][8]=dist[8][7]=100;dist[7][9]=dist[9][7]=600;dist[7][10]=dist[10][7]=150;dist[7][11]=dist[11][7]=110;dist[7][12]=dist[12][7]=100;dist[8][12]=dist[12][8]=80;dist[9][11]=dist[11][9]=700;dist[10][11]=dist[11][10]=5;dist[10][12]=dist[12][10]=50;dist[10][13]=dist[13][10]=150;dist[12][13]=dist[13][12]=100;dist[12][26]=dist[26][12]=20;dist[13][14]=dist[14][13]=200;dist[13][15]=dist[15][13]=250;dist[13][16]=dist[16][13]=700;dist[13][26]=dist[26][13]=100;dist[14][15]=dist[15][14]=20;dist[14][16]=dist[16][14]=500;dist[14][17]=dist[17][14]=1500;dist[16][17]=dist[17][16]=1300;dist[17][18]=dist[18][17]=50;dist[17][25]=dist[25][17]=300;dist[18][19]=dist[19][18]=30;dist[19][20]=dist[20][19]=100;dist[20][21]=dist[21][20]=950;dist[20][22]=dist[22][20]=900;dist[21][22]=dist[22][21]=150;dist[21][24]=dist[24][21]=110;dist[21][25]=dist[25][21]=750;dist[22][23]=dist[23][22]=40;dist[22][24]=dist[24][22]=120;dist[23][24]=dist[24][23]=60;dist[24][1]=dist[1][24]=300;}void shortest_path(graph *g,int s, int t,int n){struct state{int predecessor; //前驱节点int length; //到起始点的距离int label;}state[MAX_NODES];int i,k,min,mypath[MAX_NODES];struct state * p;for(p=&state[0]; p<&state[n]; p++){p->predecessor = -1;p->length = INFINITY;p->label = 0;}state[t].length = 0;state[t].label = 1;k = t; //当前工作结点do{for(i=0; i<n; i++){if(dist[k][i]!=0 && state[i].label==0){if(state[k].length+dist[k][i]<state[i].length){state[i].length = state[k].length+dist[k][i]; state[i].predecessor = k;}}}k=0;min=INFINITY;for(i=0; i<n; i++){if(state[i].label==0 && state[i].length<min){k=i;min=state[i].length;}}state[k].label = 1;}while(k!=s);i=0;k=s;do{path[i] = k;k = state[k].predecessor;mypath[i]=path[i];i++;}while(k>=0);for(i--;i>0;i--){printf("%s->",g->vex[mypath[i]].sight);}printf("%s\n",g->vex[mypath[i]].sight);printf("\n距离为%d m\n",min);}int main(){int m,s,e,c;graph g;g.vexnum = 27;init_graph(&g);printf("\n===========================================================\n");printf("\n 呈贡云南大学校园导游 \n");printf("\n\n");//打印景点列表for(m=0;m<g.vexnum;m++){printf("\t%2d：%s\t\t",m,g.vex[m].sight);if(++m<27&&m!=7)printf("\t%2d：%s\t\n",m,g.vex[m].sight);else if(m==7)printf("\t %d：%s\t\n",m,g.vex[m].sight);elseprintf("\n");}printf("\n===========================================================\n");printf("\n\t■■■■■■■■■■■■■■■■■\n");printf("\t■ ■\n");printf("\t■ 1、查询景点路径■\n");printf("\t■ ■\n");printf("\t■ 0、退出■\n");printf("\t■ ■\n");printf("\t■■■■■■■■■■■■■■■■■\n");while(1){printf("\n===========================================================\n");printf("\n请输入您的选择：");scanf("%d",&c);while(!(c==0||c==1)){printf("\n输入非法，请重新选择：\n");scanf("%d",&c);}switch(c){case 0:exit(0);case 1:printf("\n输入出发点与结束点：");scanf("%d %d",&s,&e);while(s<0||s>26||e<0||e>26||s==e){printf("\n输入非法，请重新选择：");scanf("%d %d",&s,&e);}printf("\n从“ %s ”到“ %s ”的最短路径为\n\n",g.vex[s].sight,g.vex[e].sight); shortest_path(&g,e,s,g.vexnum);break;}//switch}//whilereturn 0;}。

数据结构实验六报告第一篇：数据结构实验六报告实验六报告课程名称：数据结构实验名称：二叉树的应用实验日期2011/11/23一、实验目的：掌握赫夫曼二叉树的建立及赫夫曼编码的生成。

二、实验内容与要求：根据给定的n个权值生成赫夫曼二叉树，输出赫夫曼编码。

三、数据结构设计顺序表的存储结构，建立了二叉树的关系Struct HTNode{int weight;unsigned int parent,lchild,rchild;};四、算法设计1、从数据中选择较小的两个数据元素void Select(HTNode *HT, const int n, int &a, int &b){ //选择较小的两个元素} int x,y;x=y=0x7fff;for(int j=0;jif(HT[j].parent==0)if(HT[j].weight2、建立赫夫曼树void CreatHuff(HTNode *HT,int *p,const int n){} int m=2*n-1;int i,a,b;for(i=0;iSelect(HT ,i,a,b);HT[a].parent=HT[b].parent=i;HT[i].weight=H T[a].weight+HT[b].weight;HT[i].lchild=a;HT[i].rchild=b;}3、生成赫夫曼编码void HuffCoding(HTNode *HT, Huffcode &HC, const int n){ //}HC=newchar*[n+1];char *code=new char[n];code[n-1]='';int i,j,p,k;for(i=0;i} delete[] code;j=n-1;k=i;while(HT[k].parent){p=HT[k].parent;if(HT[p].lchild==k)code[--j]='0';else code[--j]='1';k=p;} HC[i]=(char*)malloc((n-j)*sizeof(char));HC[i]=new char[n-j];strcpy(HC[i],&code[j]);五、测试结果测试数据一：测试数据二：六、心得体会这次实验是在前面的实验基础之上，加上只用了顺序表的存储结构，所以比较简单。

云南大学软件学院实验报告课程：数据库原理与实用技术实验任课教师：刘宇、张璇姓名：学号：专业：信息安全成绩：实验6 数据库完整性实验6-1 完整性约束1、创建规则（用图形或者语句方法创建）（1）创建入学日期规则“Enter_University_date_rule”，假定该学校于1923年4月30日创建。

要求：入学日期必须大于等于学校创建日期，并且小于等于当前日期测试：（2）创建学生年龄规则“Age_rule”。

要求：学生年龄必须在15～30岁之间测试：（3）创建学生性别规则“Sex_rule”。

要求：性别只能为“男”或“女”测试：《数据库原理与实用技术》实验3 / 21（4）创建学生成绩规则“Score_rule ”。

要求：学生成绩只能在0～100之间（5）用图形方法查看学生成绩规则“Score_rule ”，截图为：双击：成绩：（6）用语句方法查看学生成绩规则“Score_rule ”，语句为：2、删除规则Enter_University_date_rule3、创建默认（用图形或者语句方法创建）（1）创建默认时间“Time_default”为当前系统时间（2）创建默认入学年龄“Age_default”为18岁（3）用图形方法查看默认入学年龄“Age_default”，截图为：《数据库原理与实用技术》实验5 /21（4）用语句方法查看默认入学年龄“Age_default ”，语句为：4、删除默认入学年龄“Age_default ”5、创建声明式默认：在创建表的过程中创建声明式默认 （1）创建表“default_example ”，表中包含字段pid 、name 、sex 、age 。

要求设定sex 的默认值为“男”、age 的默认值为18。

编号 姓名 性别 年龄 101 苏晴 女 201马拯山20执行结果为：输入数据：获取数据结果为：（2）在表中增加新的默认，将编号默认为100。

插入一条记录，执行结果为：6、在“学生管理数据库”各个数据表中建立相应的主键、外键、惟一值、以及check约束，要求：学生的年龄必须是两位数，其中第一位是1或2：学生表如下：《数据库原理与实用技术》实验授课表如下课程表如下：7/ 21成绩表如下：删除check 约束：学生表的：《数据库原理与实用技术》实验9/21授课表的：课程表的：成绩表的:7、完成教科书456页如下习题：[7.1]a：实验6-2 触发器《数据库原理与实用技术》实验11 / 211、使用触发器（1）创建一个触发器trig_update ，返回对“学生表”进行更新操作后，被更新的记录条数（2）执行触发器（3）修改触发器trig_update ，除返回被更新的记录条数外，再返回学生的所有基本信息2、使用触发器的两个特殊表：插入表（inserted）和删除表（deleted）。

一、实验背景随着计算机技术的飞速发展，数据结构作为计算机科学的重要基础，已经成为现代软件开发和数据处理的关键技术。

为了提高学生的数据结构应用能力，我们学校开设了数据结构实验实训课程。

本课程旨在通过实验实训，使学生深入理解数据结构的基本概念、性质、应用，掌握各种数据结构的实现方法，提高编程能力和解决实际问题的能力。

二、实验内容本次数据结构实验实训主要包括以下内容：1. 数据结构的基本概念和性质通过实验，使学生掌握线性表、栈、队列、串、树、图等基本数据结构的概念、性质和应用场景。

2. 数据结构的存储结构通过实验，使学生熟悉线性表、栈、队列、串、树、图等数据结构的顺序存储和链式存储方法，了解不同存储结构的优缺点。

3. 数据结构的操作算法通过实验，使学生掌握线性表、栈、队列、串、树、图等数据结构的插入、删除、查找、遍历等基本操作算法。

4. 数据结构的实际应用通过实验，使学生了解数据结构在各个领域的应用，如网络数据结构、数据库数据结构、人工智能数据结构等。

三、实验过程1. 实验准备在实验开始前，教师首先对实验内容进行讲解，使学生了解实验目的、实验步骤和实验要求。

同时，教师要求学生预习实验内容，熟悉相关理论知识。

2. 实验实施（1）线性表：通过实现线性表的顺序存储和链式存储，实现插入、删除、查找等操作。

（2）栈和队列：通过实现栈和队列的顺序存储和链式存储，实现入栈、出栈、入队、出队等操作。

（3）串：通过实现串的顺序存储和链式存储，实现串的插入、删除、查找等操作。

（4）树：通过实现二叉树、二叉搜索树、平衡二叉树等，实现树的插入、删除、查找、遍历等操作。

（5）图：通过实现图的邻接矩阵和邻接表存储，实现图的插入、删除、查找、遍历等操作。

3. 实验总结实验结束后，教师组织学生进行实验总结，总结实验过程中的收获和不足，提出改进措施。

四、实验成果通过本次数据结构实验实训，学生取得了以下成果：1. 掌握了数据结构的基本概念、性质和应用场景。

实验难度： A □ B □ C □学期：2017秋季学期任课教师: 刘宇实验题目:组员及组长:承担工作：联系电话:电子邮件:完成提交时间：2017年10月24日一、【实验构思（Conceive）】(10%)（本部分应包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计等相关知识，对问题进行概要性地分析）实验要求制作一个复数计算器，要求能进行实数和虚数的混合运算，首先要解决的问题是复数的四则运算，确保运算正确无误。

然后要解决的就是分离复数这个问题。

分离复数最简单的方法就是输入复数的时候分别输入实部虚部，然后打印。

但这过于简单，于是采取输入一个字符串来接入这个复数，然后用数组的方法进行实部虚部的分离。

用到的数学知识：复数四则运算，与或非运算，进行分支判断；程序设计知识：目标分析->设计算法->程序编写->后期调试。

二、【实验设计(Design)】(20%)（本部分应包括：抽象数据类型的定义和基本操作说明，程序包含的模块以及各模块间的调用关系，关键算法伪码描述及程序流程图等，如有界面则需包括界面设计，功能说明等）抽象数据类型的定义：typedef struct Complex //构造复数结构Complex{float real; //定义实部为realfloat imag; //定义虚部为imag}Complex;基本操作：功能一可以字符串形式输入一个复数，用数组的方法从字符串中分离出实部和虚部；功能二可以对输入的两个复数进行简单的加减乘除的四则运算。

模块：加法函数：Complex Add(Complex z1, Complex z2)减法函数：Complex Sub(Complex z1, Complex z2)乘法函数：Complex Mul(Complex z1, Complex z2)除法函数：Complex Div(Complex z1, Complex z2)打印函数：void print_Complex(Complex z)分离实部函数：float Getreal(Complex z)分离虚部函数：float Getimag(Complex z)分离函数：void spread_Complex()算法伪码描述（分离函数）：输入一个复数字符串；实部标志为flag1，虚部标志为flag2，得到flag1和flag2的取值，判断该复数是否是完整的复数，或是纯实数、纯虚数；用符号来判断一个完整的复数的实部虚部，如果判断出字符串中接收到了‘+’或者‘-’，则符号前面的算实部，将符号舍去，后面的即为虚部，直到遇上‘i’。

云南大学软件学院实验报告课程：信息安全工程实验任课教师：林英姓名：学号：专业：成绩：实验6.防火墙实验一、实验目的：通过实验理解入防火墙的功能和工作原理，学习NAT转换原理，熟悉NAT在一般网络环境中的应用、Linux系统中iptables防火墙以及Windows防火墙的配置和使用。

二、实验原理NAT转换实验：网络地址转换(NAT，Network Address Translation)是Internet 工程任务组(IETF，Internet Engineering Task Force)的一个标准，是把内部私有IP地址转换成合法网络IP地址的技术，允许一个整体机构以一个公用IP地址出现在Internet上。

IPtables防火墙配置实验：IPtables是复杂的，它集成到linux内核中。

用户通过IPtables，可以对进出你的计算机的数据包进行过滤。

通过IPtables命令设置你的规则，来把守你的计算机网络──哪些数据允许通过，哪些不能通过，哪些通过的数据进行记录(log)。

Windows防火墙实验：Windows防火墙是一个基于主机的状态防火墙，它丢弃所有未请求的传入流量，即那些既没有对应于为响应计算机的某个请求而发送的流量(请求的流量)，也没有对应于已指定为允许的未请求的流量(异常流量)。

Windows防火墙提供某种程度的保护，避免那些依赖未请求的传入流量来攻击网络上的计算机的恶意用户和程序。

三、实验步骤NAT转换实验一、连接防火墙服务器，开始实验启动实验客户端，选择“防火墙”中的“NAT转换实验”，点击“连接”。

连接成功后，会提示连接成功，主界面会显示连接IP信息及防火墙规则操作画面。

二、添加静态路由打开本地主机cmd命令行，输入route add 172.21.0.0 mask 255.255.0.0 172.20.2.1，添加路由。

三、验证网络连通性输入ping 172.21.3.76，如图所示。

云南大学软件学院数据结构实验6预览说明:预览图片所展示的格式为文档的源格式展示,下载源文件没有水印,内容可编辑和复制实验难度：A □ B □ C □学期：2017秋季学期任课教师:实验题目:组员及组长:承担工作：联系电话:电子邮件:完成提交时间：年月日一、【实验构思（Conceive）】(10%)（本部分应包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计等相关知识，对问题进行概要性地分析）1.基本思路：用无向网表示校区内的各建筑的平面图，图中顶点表示主要建筑，存放建筑的编号、名称、简介等信息，图中的边表示建筑间的道路，存放路径长度等信息，将导游图看作一张带权无向图，顶点表示校园的各个建筑，边表示各建筑之间的道路，边上的权值表示距离；根据用户的输入信息用迪杰斯特拉算法计算出任意两个地点之间的最短路径，并用二维数组来存储相关的信息，输出给用户；同时用数组存储各个地点的相关信息，当用户输入要了解的地点名称是，调用相关函数输出该地点的相关信息给用户。

2、在程序中运用到了图的相关知识以及迪杰斯特拉算法和哈密尔顿图的遍历等，无向图的相关知识和相关操作，还有图的存储及相关的数据结构。

二、【实验设计(Design)】(20%)（本部分应包括：抽象数据类型的定义和基本操作说明，程序包含的模块以及各模块间的调用关系，关键算法伪码描述及程序流程图等，如有界面则需包括界面设计，功能说明等）主程序模块：该模块包含一个main函数，在main函数中调用其他函数和子程序。

int main(){int v0, v1;int i, num;char flag;Create(NUM, 11);do{flag = Menu();switch (flag){case'1':system("cls");//清空屏幕的当前内容List();//输出景点列表printf("\请选择起点景点（0~26）：");scanf("%d", &v0);printf("\请选择终点景点（0~26）：");scanf("%d", &v1);ShortPath(v0);//求出最短路径Output(v0, v1);//输出结果printf("\请按任意键继续...\");getchar();//利用getchar()函数让程序运行到上一行时，等待下下一个按键时才返回getchar();break;system("cls");List();printf("\请输入您要查找的景点编号："); scanf("%d", &num);for (i = 0; i<="" p="">{if (num == g.vex[i].number){printf("\你要查找的景点信息如下："); printf("\%s:", g.vex[i].sight);printf("%s\\", g.vex[i].description); printf("\按任意键返回...");getchar();getchar();break;}}if (i == NUM){printf("\没有找到！");printf("\按任意键返回...");getchar();getchar();}break;case'e':exit(0);}} while (flag != '0');}流程图：子程序模块包括：地点列表函数、输出函数、哈密尔顿图的遍历函数、迪杰斯特拉算法判断最短路径函数、创建图的函数。

实验六、传输层可靠传输协议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协议可靠传输的差错检测、重传、累计确认、定时器的可靠传输策略。