北京理工大学《数据结构与算法设计》实验报告实验一

数据结构与算法分析实验报告一、实验目的本次实验旨在通过实际操作和分析，深入理解数据结构和算法的基本概念、原理和应用，提高解决实际问题的能力，培养逻辑思维和编程技巧。

二、实验环境本次实验使用的编程语言为 Python，使用的开发工具为 PyCharm。

操作系统为 Windows 10。

三、实验内容（一）线性表的实现与操作1、顺序表的实现使用数组实现顺序表，包括插入、删除、查找等基本操作。

通过实验，理解了顺序表在内存中的存储方式以及其操作的时间复杂度。

2、链表的实现实现了单向链表和双向链表，对链表的节点插入、删除和遍历进行了实践。

体会到链表在动态内存管理和灵活操作方面的优势。

（二）栈和队列的应用1、栈的实现与应用用数组和链表分别实现栈，并通过表达式求值的例子，展示了栈在计算中的作用。

2、队列的实现与应用实现了顺序队列和循环队列，通过模拟银行排队的场景，理解了队列的先进先出特性。

（三）树和二叉树1、二叉树的遍历实现了先序、中序和后序遍历算法，并对不同遍历方式的结果进行了分析和比较。

2、二叉搜索树的操作构建了二叉搜索树，实现了插入、删除和查找操作，了解了其在数据快速查找和排序中的应用。

（四）图的表示与遍历1、邻接矩阵和邻接表表示图分别用邻接矩阵和邻接表来表示图，并比较了它们在存储空间和操作效率上的差异。

2、图的深度优先遍历和广度优先遍历实现了两种遍历算法，并通过对实际图结构的遍历，理解了它们的应用场景和特点。

（五）排序算法的性能比较1、常见排序算法的实现实现了冒泡排序、插入排序、选择排序、快速排序和归并排序等常见的排序算法。

2、算法性能分析通过对不同规模的数据进行排序实验，比较了各种排序算法的时间复杂度和空间复杂度。

四、实验过程及结果（一）线性表1、顺序表在顺序表的插入操作中，如果在表头插入元素，需要将后面的元素依次向后移动一位，时间复杂度为 O(n)。

删除操作同理，在表头删除元素时，时间复杂度也为 O(n)。

数据结构与算法实习_实验指导书数据结构与算法课程实习实验指导书目录实验一顺序表的基本操作 (2)实验二链表的基本操作 (3)实验三二叉树的基本操作 (4)实验四综合应用 (5)附录A 实验报告示例 (9)附录B实验报告封面、评语得分表 (12)实验一顺序表的基本操作【实验目的】1、掌握顺序存储的概念，学会对顺序表的基本操作。

2、加深对顺序存储数据结构的理解，逐步培养解决实际问题的能力。

【实验性质】设计型实验【实验内容】1、实现顺序表显示；2、实现顺序表插入；3、实现顺序表查找（显示比较次数）；4、实现顺序表删除（显示移动次数）；5、实现顺序表排序（分别实现简单选择、快速，显示比较次数、移动次数）；6、实现顺序表的折半查找（显示比较次数）；7、编程实现一个顺序表的就地逆置，即利用原表的存储空间将顺序表逆置；8顺序表有序插入（显示比较次数、移动次数），屏幕提示后，从键盘输入一个元素值，在经过排序的线性表中插入这个元素；屏幕显示比较次数和移动次数，应有溢出判断和报告；9、要求以较高的效率实现删除顺序表中元素值在x到y（x和y自定）之间的所有元素;10、编程实现将两个非递减的顺序表进行合并，要求同样的数据元素只出现一次；*11、编程实现顺序表的shell排序（步长为5, 3，1）；*12、编程实现堆排序算法；*13、利用三元组顺序表存储矩阵，实现矩阵的转置（请独立写程序实现）。

【实验环境】VC++ 6.0【实验要求】将如上文件保存在命名为学号+姓名”勺文件夹中并上传到指定的服务器。

实验二链表的基本操作【实验目的】1、掌握链表的概念，学会对链表进行操作。

2、加深对链式存储结构的理解，逐步培养解决实际问题的编程能力。

【实验性质】设计型实验【实验内容】1、实现单链表的创建；2、实现单链表的显示；3、实现单链表的查找（显示比较次数）；4、实现单链表的插入；5、实现单链表的删除（显示比较次数）；6、对已创建的链表（数据不限）进行直接插入排序；7、将链接存储线性表逆置，即最后一个结点变成第1个结点，原来倒数第2个结点变成第2个结点，如此等等；8、生成有序的两个单链表A和B （链表的数据和个数自定），其首结点指针分别为a 和b,要求将两个单链表合并为一个有序的单链表C,其首结点指针为c,并且合并后的单链表的数据不重复；9、将一个首结点指针为a的单链表A分解成两个单链表A和B，其首结点指针分别为a和b，使得链表A中含有原链表A中序号为奇数的元素，而链表B中含有原链表A中序号为偶数的元素，且保持原来的相对顺序；10、请编程实现链栈的基本操作函数，并通过调用这些基本函数，实现十进制和八进制转换的功能。

《数据结构与算法分析》课程实验报告【实验目的】1. 理解图形结构的逻辑和存储特点。

2. 掌握图形结构遍历递归算法。

【实验内容】1. 用邻接矩阵或者邻接表存储一个图形结构。

2. 采用深度或者广度优先搜索算法，遍历一个图，并输出遍历结果。

【实验方式】个人实验。

【实验设备与环境】PC机，Windows XP操作系统，VC++6.0开发环境。

【数据结构及函数定义】（1）类的定义：类的数据成员，成员函数．．．．．．．．．．．．．．．．．．．（2）主函数main（）实现初始化操作，完成对子函数的调用．．．．．．．．．．．．．．．．．．．（3）子函数．．．．．．．．．．．．．．．．．．．。

【测试数据与实验结果】（请用截图的方式展示实验结果，并辅以必要的文字说明）【源程序清单】（请附上源程序）#include<iostream>using namespace std;#include<string.h>class Graph{public:c har Vtx[20];d ouble AdjMtx[20][20];i nt CurrentVnum;i nt CurrentEnum;G raph(){CurrentVnum=CurrentEnum=0;} i nt first_adj(int v);i nt next_adj(int v1,int v2);v oid visite(int v);v oid DFS();v oid DFS(int v,int visited[]);~Graph(){}};int Graph::first_adj(int v){f or(int v1=0;v1<CurrentVnum;v1++)if(AdjMtx[v][v1]>0)return v1;return -1;}int Graph::next_adj(int v1,int v2) {f or(int vn=v2+1;vn<CurrentVnum;vn++)if(AdjMtx[v1][vn]>0)return vn;return -1;}void Graph::visite(int v){c out<<Vtx[v]<<" ";}void Graph::DFS(){i nt *visited=new int[CurrentVnum];f or(int i=0;i<CurrentVnum;i++)visited[i]=0;f or(i=0;i<CurrentVnum;i++){if(visited[i]==0)DFS(i,visited);}d elete[] visited;}void Graph::DFS(int v,int visited[]) {v isite(v);v isited[v]=1;i nt w=first_adj(v);w hile(w!=-1){if(!visited[w])DFS(w,visited);w=next_adj(v,w);}}int LocateVex(Graph G,char u){i nt i;f or(i=0;i<G.CurrentVnum;i++)if(u==G.Vtx[i])return i;return -1;}void creat(Graph &G){i nt i,j,k;c har va,vb;c out<<"请输入图的顶点数,弧数:";c in>>G.CurrentVnum>>G.CurrentEnum;c out<<"请输入"<<G.CurrentVnum<<"个顶点的值:";f or(i=0;i<G.CurrentVnum;i++)cin>>G.Vtx[i];f or(i=0;i<G.CurrentVnum;i++)for(j=0;j<G.CurrentVnum;j++)G.AdjMtx[i][j]=0;c out<<"请输入"<<G.CurrentEnum<<"条弧的弧尾,弧头(以空格作为间隔):\n";f or(k=0;k<G.CurrentEnum;k++){cin>>va>>vb;i=LocateVex(G,va);j=LocateVex(G,vb);if(i!=j){G.AdjMtx[i][j]=1;G.AdjMtx[j][i]=1;}else G.AdjMtx[i][j]=1;}}void main(){G raph G;c reat(G);c out<<"深度优先搜索序列:"<<endl;G.DFS();c out<<endl;。

《数据结构与算法设计》实验报告——实验一学院：班级：学号：姓名：一、实验目的1.通过实验实践、巩固线性表的相关操作；2.熟悉VC环境，加强编程、调试的练习；3.用C语言编写函数，实现循环链表的建立、插入、删除、取数据等基本操作；4.理论知识与实际问题相结合，利用上述基本操作实现约瑟夫环。

二、实验内容1、采用单向环表实现约瑟夫环。

请按以下要求编程实现：①从键盘输入整数m，通过create函数生成一个具有m个结点的单向环表。

环表中的结点编号依次为1，2，……，m。

②从键盘输入整数s（1<=s<=m）和n，从环表的第s个结点开始计数为1，当计数到第n个结点时，输出该第n结点对应的编号，将该结点从环表中消除，从输出结点的下一个结点开始重新计数到n，这样，不断进行计数，不断进行输出，直到输出了这个环表的全部结点为止。

三、程序设计1、概要设计为实现上述程序功能，应用单向环表寄存编号，为此需要建立一个抽象数据类型：单向环表。

（1）、单向环表的抽象数据类型定义为：ADT Joseph{数据对象：D={ai|ai∈ElemSet,i=1,2,3……,n,n≥0}数据关系：R1={ <ai-1,ai>|ai∈D,i=1,2,……,n}基本操作：create(&L,n)操作结果：构造一个有n个结点的单向环表L。

show(L)初始条件：单向环表L已存在。

操作结果：按顺序在屏幕上输出L的数据元素。

Josephf( L,m,s,n)初始条件：单向环表L已存在， s>0,n>0，s<m。

操作结果：返回约瑟夫环的计算结果。

}ADT Joseph（2）、主程序流程主程序首先调用create(&L,n)函数，创建含有m个节点的单向环表L，然后调用show(L)函数，顺序输出链表中的数据，最后调用Josephf( L,m,s,n)函数，依次输出报的数。

（3）、函数调用关系图2、详细设计(1)、数据类型设计typedef int ElemType; //定义元素类型typedef struct Lnode{ElemType data;struct Lnode *next;}Lnode,*Linklist; //定义节点类型，指针类型（2）、操作算法程序实现：void create(Linklist &L,int m){//生成一个具有m个结点的单向环表，环表中的结点编号依次为1，2，……，m Linklist h,p;L=(Linklist)malloc(sizeof(Lnode));L->data = 1;h=L;for(int i=2;i<=m;i++){p = (Linklist)malloc(sizeof(Lnode));p->data = i; //生成新节点，数据为节点编号h->next = p;h = p; //插入链表}h->next = L; //形成循环链表}void show(Linklist L,int m){//从第一个节点开始依次输出节点编号printf("The numbers of the list are: \n"); //提示用户Linklist h;h=L;for(int i=1;i<=m;i++){printf("%d ",h->data);h = h->next;}printf("\n");}void Josephf(Linklist &L,int m,int s,int n){//实现约瑟夫环Linklist h,q;h = L;q = L;while(h->data != s) //定位开始的节点h = h->next;while(q->next!=h) //定位在开始位置的上一个节点q = q->next;for(int j=1;j<=m;j++){int i=1;while(i<n){q=q->next;i++;}printf("%d ",q->next->data); //依次输出报号为n的节点q->next = q->next->next; //删除已输出节点}printf("\n");}（3）、主程序的代码实现：int main(){int s,m,n;Linklist L;printf("请输入节点数m：\n");scanf("%d",&m);create(L,m); //建立循环链表show(L,m); //输出链表数据printf("请输入起始位置s：\n");scanf("%d",&s);printf("请输入报的数n：\n");scanf("%d",&n);Josephf(L,m,s,n); //输出所报数字return 0;}四、程序调试分析1.引用标识符&不符合C语言语法，应使用C++;2.为了实现循环链表，建立时应该不设头结点且第一个节点就存储编号数据；3.删除节点时要定位到前一个指针，所以在定位开始位置后还要再定位到前一个指针；4.输出时要注意增加“ ”（空格）和“\n”（换行），使输出易于辨识。

《数据结构与算法设计》实验报告——实验二一、实验目的按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。

二、实验内容简单计算器。

请按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。

要求：①从键盘输入一个完整的表达式，以回车作为表达式输入结束的标志。

②输入表达式中的数值均为大于等于零的整数。

中间的计算过程如果出现小数也只取整。

例如，输入：4+2*5= 输出：14输入：(4+2)*(2-10)= 输出：-48三、程序设计概要设计1、宏定义#define TRUE 1#define FALSE 0#define OK 1#define ERROR 02、基本函数：（1）void InitStack_char(SqStack *S) //char型栈初始化（2）void InitStack_int(sqStack *S) //int型栈初始化（3）void Push_char(SqStack *S,char ch) //char型元素进栈（4）void Push_int(sqStack *S,int num) //int型元素进栈（5）char GetTop_char(SqStack *S) //取char型栈顶元素（6）int GetTop_int(sqStack *S) //取int型栈顶元素（7）Status In(char c) //判断是否为运算符，若是运算符则返回，否则返回（8）char Precede(char a,char b) //判断两运算符的先后次序（9）Status Pop_char(SqStack *S,char &x) //char型栈出栈（10）Status Pop_int(sqStack *S,int &x) //int型栈出栈（11）int Operate(int a,char theta,int b) //计算a和b运算结果3、流程图详细设计数据类型typedef struct node //构造char型栈{char ch;struct node *next;}node;typedef struct{struct node *base;struct node *top;}SqStack;typedef struct lnode //构造int型栈{int num;struct lnode *next;}lnode;typedef struct{struct lnode *base;struct lnode *top;}sqStack;操作部分void InitStack_char(SqStack *S){S->base = (node *)malloc(sizeof(node));S->base->next=NULL;S->top = S->base;} //char型栈初始化void InitStack_int(sqStack *S){S->base = (lnode *)malloc(sizeof(lnode));S->base->next=NULL;S->top = S->base;} //int型栈初始化void Push_char(SqStack *S,char ch){node *p;p=(node*)malloc(sizeof(node));p->ch=ch;p->next=S->top;S->top=p;} //char型元素进栈Status Push_int(sqStack *S,int num){lnode *p;p=(lnode*)malloc(sizeof(lnode));p->num=num;p->next=S->top;S->top=p;return OK;} //int型元素进栈char GetTop_char(SqStack *S){return (S->top->ch);} //取char型栈顶元素int GetTop_int(sqStack *S){return (S->top->num);} //取int型栈顶元素Status Pop_char(SqStack *S,char &x){if(S->base == S->top)return ERROR;node *p;p=S->top;x=p->ch;S->top=p->next;free(p);return OK;} //char型栈出栈Status Pop_int(sqStack *S,int &x){if(S->base == S->top)return ERROR;lnode *p;p=S->top;x=p->num;S->top=p->next;free(p);return OK;} //int型栈出栈计算功能int Operate(int a,char theta,int b){int i,z = 1;switch(theta){case '+':z = (a + b);break;case '-':z = (a - b);break;case '*':z = (a * b);break;case '/':z = (a / b);break;case '^':for(i = 1;i<=b;i++)z = z*a;break;}return (z);} //计算a和b运算结果Status In(char c){if(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')'||c=='='||c=='^') return OK;elsereturn ERROR;} //判断是否为运算符char Precede(char a,char b){if(a=='+'||a=='-'){if(b=='+'||b=='-'||b==')'||b=='=')return '>';elsereturn '<';}if(a=='*'||a=='/'){if(b=='('||b=='^')return '<';elsereturn '>';}if(a=='('){if(b==')')return '=';elsereturn '<';}if(a==')'){if(b!='(')return '>';}if(a=='#'){if(b=='=')return '=';elsereturn '<';}if(a=='^')return ('>');} //判断两运算符的先后次序主函数int main() //主函数{char c,x,theta;int a,b,c1; //定义变量SqStack OPTR; //定义字符栈sqStack OPNR; //定义整型栈InitStack_char(&OPTR); //初始化InitStack_int(&OPNR); //初始化Push_char(&OPTR,'#'); //将字符型栈底设为#c = getchar(); //从键盘输入得到字符while(c!='='||GetTop_char(&OPTR)!='#') //判定是否执行循环if(!In(c)){c1 = 0;while(!In(c)){c1 = c1*10+c-'0';c = getchar();}Push_int(&OPNR,c1);} //当扫描字符不是运算符时，转化为整型数存入栈中else{switch(Precede(GetTop_char(&OPTR),c)) //判定运算符的优先关系{case '<':Push_char(&OPTR,c);c = getchar();break; //当前运算符优先级高，存入char栈case '=':Pop_char(&OPTR,c);c = getchar();break; //运算符次序相等，存入char栈case '>': //当前运算符优先级低Pop_char(&OPTR,theta);Pop_int(&OPNR,b);Pop_int(&OPNR,a);Push_int(&OPNR, Operate(a,theta,b));//计算运算结果，并存入int栈break; //继续循环}}printf("%d\n",GetTop_int(&OPNR)); //计算完成，取出int栈顶元素，并输出return 0;}四、程序调试分析编写程序的过程中遇到了很多的问题，最突出的两个问题就是整数和两位数的运算处理，一开始修改了主函数部分之后，原来可以执行一位数运算的程序出现了error，由于没有及时保存，并且之前的代码无法恢复，只得重新编写一次。

数据结构实验报告题目：线性表班级：网络工程1401班学号： 1408020106指导教师：高峰日期： 2016/7/6实验一：线性表一：实验要求掌握数据结构中线性表的基本概念。

熟练掌握线性表的基本操作：创建、插入、删除、查找、输出、求长度及合并并运算在顺序存储结构撒谎能够的实验。

熟练掌握链表的各种操作和应用。

二．实验内容1. 编程实现在顺序存储的有序表中插入一个元素（数据类型为整型）。

2. 编程实现把顺序表中从i个元素开始的k个元素删除（数据类型为整型）。

三：实验过程及步骤源代码：#include<stdio.h>#include<malloc.h>#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef struct{int * elem;int length;int listsize;}SqList;//SqList sq;void InitList_Sq(SqList *sq) //初始化列表{sq->elem=(int *)malloc(LIST_INIT_SIZE*sizeof(int));sq->length=0;sq->listsize=LIST_INIT_SIZE;printf("---申请空间成功---!\n");}void GetElem(SqList *sq,int i)//获取第i位置元素的值{int *p;p=&(sq->elem[i-1]);printf("%d",*p);printf("\n");}int ListInsert_Sq(SqList *sq,int i,int a)//在i位置之前插入a{int *p,*q;if(i<=0||i>sq->length+1){printf("---位置不合法---!\n");return 0;}if(sq->length>=sq->listsize){int* newbase=(int *)realloc(sq->elem,(sq->listsize+LISTINCREMENT)*sizeof(int)); if(!newbase){printf("申请空间溢出\n");return 0;}sq->elem=newbase;sq->listsize+=LISTINCREMENT;}p=&(sq->elem[i-1]);//p指向第i位置的元素q=&(sq->elem[sq->length-1]);//q指向最后一个元素for(;q>=p;--q) *(q+1)=*q;*p=a;++sq->length;return 1;}int ListDelete_Sq(SqList *sq,int i) //删除i位置上的值{int *p,*q;if(i<1||i>sq->length) return 0;p=&(sq->elem[i-1]);//p指向第i位置的元素q=sq->elem+sq->length-1;//q指向最后一个元素for(++p;p<=q;++p){*(p-1)=*p;}--sq->length;return 1;}void visit(SqList *sq)//输出数据{int i=1;for(;i<=sq->length;i++){int *p;p=&sq->elem[i-1];printf("%d",*p);printf(" ");}}void main(){int i=1,a=0,boo=1,number=0;SqList s,*sq;sq=&s;InitList_Sq(sq);printf("初始化空表\n");printf("输入数据个数：\n");scanf("%d",&number);printf("输入%d个数据：",number);printf("\n");for(;i<=number;i++){scanf("%d",&a);if(boo=ListInsert_Sq(sq,i,a)){printf("---插入成功！---\n");}else{printf("---插入不成功,重新插入---！\n"); i=i-1;}}printf("输出所有元素\n");visit(sq);printf("\n");printf("输出删除的位置:");scanf("%d",&a);if(boo=ListDelete_Sq(sq,a)){printf("---数据删除成功！---\n");}else{printf("---没有删除成功---\n");}printf("输出所有元素:\n");visit(sq);printf("\n");printf("输出要显示数据的位置：");scanf("%d",&a);printf("输出%d位置数值\n",a);if(a<0||a>sq->length){printf("---输出位置的数据不存在---\n");}else{GetElem(sq,a);}}步骤：1.初始化空表2.顺序插入数据后输出所有元素3.选择删除位置，删除数据后输出所有元素4.选择查看的数据位置，输出选择查看的数据四：实验结果及分析分析：本程序在实现顺序存储插入以及删除i个元素开始的k个元素删除（数据类型为整型）。

数据结构与算法实验报告实验目的：1.加深对链表的理解，掌握链表的基本操作；2.掌握递归算法的设计思想及应用。

实验内容：本次实验主要包括两个部分的实现与测试，分别为链表的基本操作及递归算法的应用。

一、链表的基本操作1.链表的创建链表的创建主要包括新建链表头结点和逐个插入新结点两个步骤。

首先通过malloc函数新建一个链表头结点，并使链表头结点的指针域为空。

然后通过循环输入新节点的数据值，并将新节点插入到链表的尾部。

2.链表的插入链表的插入操作主要包括在链表头部插入新节点、在链表尾部插入新节点和在链表中间插入新节点。

在插入链表头部时，首先通过malloc函数生成新节点，并将链表头节点指针域的原指向设置为新节点；在插入链表尾部时，首先通过循环找到链表的尾节点，并生成新节点，将尾节点指针域的原指向设置为新节点；在插入链表中间时，首先通过循环找到要插入的位置节点，然后生成新节点，并将新节点指针域的原指向设置为下一个节点，将前一个节点的指针域设置为新节点。

3.链表的删除链表的删除操作主要包括删除头节点、删除尾节点和删除中间节点。

在删除头节点时，首先通过free函数释放头节点的内存空间，然后将链表的头节点指针指向第二个节点；在删除尾节点时，首先通过循环找到倒数第二个节点，并将倒数第二个节点的指针域置空，最后通过free函数释放尾节点的内存空间；在删除中间节点时，首先通过循环找到要删除的节点的前一个节点，然后将前一个节点的指针域指向要删除节点的下一个节点，最后通过free函数释放要删除节点的内存空间。

4.链表的查询链表的查询操作主要包括按位置查询和按值查询。

在按位置查询时，通过循环找到指定位置的节点，然后返回节点的数据值；在按值查询时，通过循环比较节点的数据值与指定值，找到匹配的节点，并返回该节点的位置。

二、递归算法的应用递归算法是一种函数自己调用自己的算法设计思想，具有简洁、清晰的特点。

本次实验主要应用递归算法解决实际问题，包括斐波那契数列的求解和二叉树的遍历。

数据结构与算法实验报告（二）实验人： 学号: 时间：2013.4.23实验名称：迷宫问题实验原理：利用一个二维数组maze[i][j]表示迷宫，其中，. 数组元素值为1，表示该位置是墙壁，不能通行；元素值为0，表示该位置是通路。

假定从maze[1][1]出发，出口位于maze[m] [n]。

移动方向可以是8个方向(东，东南，南，西南，西，西北，北和东北)。

实验过程记录：（1）//比较A, B是否是同一点if (A.x==B.x&&A.y==B.y){return 1;}else{return 0;}（2） case 2:B.x=A.x+1;B.y=A.y+1;break;case 3:B.x=A.x;B.y=A.y+1;break;case 4:B.x=A.x-1;B.y=A.y+1;break;case 5:B.x=A.x-1;B.y=A.y;break;case 6:B.x=A.x-1;B.y=A.y-1;break;case 7:B.x=A.x;B.y=A.y-1;break;case 8:B.x=A.x+1;B.y=A.y-1;break;（3） maze[curpos.x][curpos.y]=8; //写一个函数留下足迹,将maze[curpos.x] [curpos.y] == 0改为不等于0，1的数字（4）maze[(e.seat).x][(e.seat).y] =3; //留下不能通过的记号，将maze[(e.seat). x][(e.seat).y] == 0改为未用过的数字实验过程中的问题：实验结果报告与实验总结：迷宫是:(1 表示障碍，0表示可以通过)1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 0 1 0 0 0 1 1 0 0 0 1 1 1 1 1 11 1 0 0 0 1 1 0 1 1 1 0 0 1 1 1 11 0 1 1 0 0 0 0 1 1 1 1 0 0 1 1 11 1 1 0 1 1 1 1 0 1 1 0 1 1 0 0 11 1 1 0 1 0 0 1 0 1 1 1 1 1 1 1 11 0 0 1 1 0 1 1 1 0 1 0 0 1 0 1 11 0 0 1 1 0 1 1 1 0 1 0 0 1 0 1 11 0 1 1 1 1 0 0 1 1 1 1 1 1 1 1 11 0 0 1 1 0 1 1 0 1 1 1 1 1 1 0 11 1 1 0 0 0 1 1 0 1 1 0 0 0 0 0 11 0 0 1 1 1 1 1 0 0 0 1 1 1 1 0 11 0 1 0 0 1 1 1 1 1 0 1 1 1 1 0 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1一条通路的二元组数据序列:->(1,1)->(2,2)->(2,3)->(3,4)->(4,3)->(5,3)->(6,2)->(7,2)->(6,1)->(7,1)->(8,1) ->(9,1)->(9,2)->(10,3)->(10,4)->(10,5)->(9,5)->(8,6)->(8,7)->(9,8)->(10,8)->(11, 8)->(11,9)->(12,10)->(11,10)->(10,11)->(10,12)->(10,13)->(10,14)->(11,15)->(12, 15)路径是沿着 8 走1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 8 1 3 3 3 1 1 3 3 3 1 1 1 1 1 11 1 8 8 3 1 1 3 1 1 1 3 3 1 1 1 11 0 1 1 8 3 3 3 1 1 1 1 3 3 1 1 11 1 1 8 1 1 1 1 3 1 1 3 1 1 3 3 11 1 1 8 1 0 0 1 3 1 1 1 1 1 1 1 11 8 8 1 1 0 1 1 1 3 1 0 0 1 0 1 11 8 8 1 1 0 1 1 1 3 1 0 0 1 0 1 11 8 1 1 1 1 8 8 1 1 1 1 1 1 1 1 11 8 8 1 1 8 1 1 8 1 1 1 1 1 1 0 11 1 1 8 8 8 1 1 8 1 1 8 8 8 8 0 11 0 0 1 1 1 1 1 8 8 8 1 1 1 1 8 11 0 1 0 0 1 1 1 1 1 8 1 1 1 1 8 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Press any key to continue思考与疑问：。

数据结构与算法实验报告实验目的：本次实验主要目的是掌握数据结构与算法的基本概念和实际应用。

通过设计和实现特定的数据结构和算法，加深对其原理和应用的理解，培养分析和解决实际问题的能力。

实验内容：本次实验包括以下几个部分：1\实验环境和工具介绍在本部分，将介绍实验所使用的开发环境和工具，包括操作系统、编程语言、集成开发环境等。

2\实验设计和思路本部分将详细介绍实验的设计思路、算法的选择和实现方式。

具体包括数据结构的选择、算法的设计原理、时间和空间复杂度分析等。

3\实验步骤和代码实现在本部分，将详细列出实验的具体步骤和算法的实现代码。

包括数据结构的定义和操作、算法的实现和测试数据的等。

4\实验结果和分析在本部分，将展示实验的运行结果，并对实验结果进行分析和讨论。

包括实际运行时间、空间占用、算法的优缺点等方面的讨论。

5\实验总结和思考在本部分，将对整个实验进行总结和思考。

包括实验过程中遇到的问题和解决方法，对实验结果的评价，以及对进一步的研究方向的思考等内容。

附件：本文档附带以下附件：1\源代码：包括数据结构的定义和操作，算法的实现等。

2\测试数据：用于验证算法实现的测试数据。

3\实验结果截图：包括算法运行结果、时间和空间占用等方面的截图。

法律名词及注释：1\数据结构：在计算机科学中，数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。

2\算法：算法是解决问题的一系列清晰而简明的指令，是计算或操作的一种良定义的规程。

3\时间复杂度：时间复杂度是度量算法运行时间长短的一个表达式，用大O符号表示。

4\空间复杂度：空间复杂度是度量算法运行过程中所需的存储空间的一个表达式，用大O符号表示。

结语：本文档详细介绍了数据结构与算法实验的设计思路、步骤和实现代码，并对实验结果进行了分析和讨论。

实验过程中，我们掌握了数据结构与算法的基本概念和实际应用，提高了问题解决能力和编程实践能力。

《数据结构与算法统计》实验报告学院：班级：学号：姓名：一、实验目的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已经存在。

北理工数据结构实验报告《数据结构与算法设计》实验报告——实验二学院：自动化学院班级：____学号：__姓名：_____一、实验目的1、熟悉VC 环境，学习使用C 语言实现栈的存储结构。

2、通过编程、上机调试，进一步理解栈的基本概念。

3、锻炼动手编程，独立思考的能力。

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

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

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

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

(1)、栈的抽象数据类型定义为：ADT Stack{数据对象：D={|,1,2,,,0}i i a a ElemSet i n n ∈=≥数据关系：R1=11{,|,,2,,}i i i i a a a a D i n --∈=约定n a 端为栈顶，1a 端为栈底。

基本操作：InitStack(&S)操作结果：创建一个空栈S。

GetTop(S,&e)初始条件：栈S已存在且非空。

操作结果：用e返回S的栈顶元素。

Push(&S,e)初始条件：栈S已存在。

操作结果：插入元素e为新的栈顶元素。

Pop(&S,&e)初始条件：栈S已存在且非空。

操作结果：删除S的栈顶元素，并用e返回其值。

In(m,a[])操作结果：若m是运算符，返回TRUE。

Precede(m, n)初始条件：m，n为运算符。

操作结果：若m优先级大于n，返回>，反之亦然。

Operation(a, theta,b)初始条件：a，b为整数，theta为运算符。

数据结构及算法实验报告这个实验是关于数据结构和算法的，通过这个实验，我们可以学习和掌握许多知识。

在实验中，我学习了一些重要的数据结构和算法，例如树、排序算法等等。

实验的第一部分是有关树的，我们需要实现一个二叉搜索树。

我决定使用C++语言来实现，因为它在处理指针和链表方面非常方便。

实现一个二叉搜索树不是很困难，但是实验的任务并不仅仅是让我们实现一个树节点的数据结构。

我们还需要在这个树上实现一些基本操作，例如插入、删除和搜索等等。

由于这个二叉搜索树应该是可扩展的，我们需要使用递归算法来实现这些操作。

在实现的过程中，我们需要注意一些细节，例如树的高度、平衡问题和递归的退出条件。

这些都是需要仔细考虑的问题，因为一旦出错，就会影响树的效率和准确性。

在实现的过程中，我遇到了一些挑战。

其中一个问题是如何在树上搜索一个节点。

尽管二叉搜索树是一种优秀的搜索工具，但是我们需要找到正确的节点，否则就会返回错误的结果。

为了解决这个问题，我使用了递归算法，并在每个节点上设置了一个唯一的键，以便进行比较。

在实现二叉搜索树后，下一个任务是实现排序算法。

我选择了快速排序算法，因为这种算法具有快速、高效和可扩展的优点。

快速排序算法基于分治算法，将输入数组分成两个子数组，然后递归地排序这些子数组。

在排序的过程中，我们需要选择一个基准值，并将数组元素按照比基准值小或大的方式进行分组。

在实现的过程中，我遇到了一些麻烦。

其中一个问题是如何选择基准值。

由于不同的基准值会导致不同的分组结果，我需要选择一个方法来确定哪一个基准值是最好的。

我选择了随机选择基准值的方法，因为它可以在不同数据集上得到比较好的结果。

除了快速排序算法外，我还实现了一些其他的排序算法，例如冒泡排序、选择排序和插入排序等等。

这些算法都是基本的排序算法，但它们可以帮助我们更好地理解和掌握排序算法的基本原理。

通过这个实验，我学习了许多有关数据结构和算法的知识。

我现在可以更好地处理树、排序算法等问题，也可以更好地在实际项目中使用它们。

数据结构与算法实验报告编制教师袁宇丽审定何文孝（适用于计算机科学学院2012级本科学生）2013至2014学年第二学期计算机科学学院实验名称：线性表的应用指导教师：余文春实验日期：2014年月日实验地点：北503 成绩：实验目的：1、掌握线性表及其顺序存储与链式存储结构的概念。

2、掌握两种存储方式的基本运算、实现方法和技术。

3、灵活应用线性表进行程序设计，解决实际问题。

实验内容：约瑟夫(Joseph)问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。

报m的人出列，从他在顺时针方向上的下一个人开始重新从1报数，同样报到m的人出列，如此下去，直至所有人全部出列为止。

利用循环链表为存储结构模拟此过程，按照出列的顺序输出依次出列人的编号。

基本要求：1、写出完成实验内容的实验方法和源代码。

2、写出实验数据及运行结果。

3、写出在实验过程中所遇到的问题及解决办法。

实验总结及意见：实验评价（教师）：实验名称：栈及队列的应用指导教师：余文春实验日期：2014年月日实验地点：北503 成绩：实验目的：1、掌握队列及其存储结构的概念。

2、掌握栈、队列的基本运算、实现方法和技术。

3、能用栈、队列的知识和操作技术设计有一定难度的程序。

实验内容：1、假设算术表达式仅由加(+)、减(-)、乘(*)、除(\)运算符组成，编写一个借助堆栈把中缀表达式转换为后缀表达式的函数，为使问题简化，可不考虑中缀表达式不正确的情况。

2、假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。

跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。

若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。

现要求写一算法模拟上述舞伴配对问题。

基本要求：1、写出完成实验内容的实验方法和源代码。

2、写出实验数据及运行结果。

3、写出在实验过程中所遇到的问题及解决办法。

《数据结构与算法设计》实验报告——实验二一、实验目的按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。

二、实验内容简单计算器。

请按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。

要求：①从键盘输入一个完整的表达式，以回车作为表达式输入结束的标志。

②输入表达式中的数值均为大于等于零的整数。

中间的计算过程如果出现小数也只取整。

例如，输入：4+2*5= 输出：14输入：(4+2)*(2-10)= 输出：-48三、程序设计概要设计1、宏定义#define TRUE 1#define FALSE 0#define OK 1#define ERROR 02、基本函数：（1）void InitStack_char(SqStack *S) //char型栈初始化（2）void InitStack_int(sqStack *S) //int型栈初始化（3）void Push_char(SqStack *S,char ch) //char型元素进栈（4）void Push_int(sqStack *S,int num) //int型元素进栈（5）char GetTop_char(SqStack *S) //取char型栈顶元素（6）int GetTop_int(sqStack *S) //取int型栈顶元素（7）Status In(char c) //判断是否为运算符，若是运算符则返回，否则返回（8）char Precede(char a,char b) //判断两运算符的先后次序（9）Status Pop_char(SqStack *S,char &x) //char型栈出栈（10）Status Pop_int(sqStack *S,int &x) //int型栈出栈（11）int Operate(int a,char theta,int b) //计算a和b运算结果3、流程图详细设计数据类型typedef struct node //构造char型栈{char ch;struct node *next;}node;typedef struct{struct node *base;struct node *top;}SqStack;typedef struct lnode //构造int型栈{int num;struct lnode *next;}lnode;typedef struct{struct lnode *base;struct lnode *top;}sqStack;操作部分void InitStack_char(SqStack *S){S->base = (node *)malloc(sizeof(node));S->base->next=NULL;S->top = S->base;} //char型栈初始化void InitStack_int(sqStack *S){S->base = (lnode *)malloc(sizeof(lnode));S->base->next=NULL;S->top = S->base;} //int型栈初始化void Push_char(SqStack *S,char ch){node *p;p=(node*)malloc(sizeof(node));p->ch=ch;p->next=S->top;S->top=p;} //char型元素进栈Status Push_int(sqStack *S,int num){lnode *p;p=(lnode*)malloc(sizeof(lnode));p->num=num;p->next=S->top;S->top=p;return OK;} //int型元素进栈char GetTop_char(SqStack *S){return (S->top->ch);} //取char型栈顶元素int GetTop_int(sqStack *S){return (S->top->num);} //取int型栈顶元素Status Pop_char(SqStack *S,char &x){if(S->base == S->top)return ERROR;node *p;p=S->top;x=p->ch;S->top=p->next;free(p);return OK;} //char型栈出栈Status Pop_int(sqStack *S,int &x){if(S->base == S->top)return ERROR;lnode *p;p=S->top;x=p->num;S->top=p->next;free(p);return OK;} //int型栈出栈计算功能int Operate(int a,char theta,int b){int i,z = 1;switch(theta){case '+':z = (a + b);break;case '-':z = (a - b);break;case '*':z = (a * b);break;case '/':z = (a / b);break;case '^':for(i = 1;i<=b;i++)z = z*a;break;}return (z);} //计算a和b运算结果Status In(char c){if(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')'||c=='='||c=='^') return OK;elsereturn ERROR;} //判断是否为运算符char Precede(char a,char b){if(a=='+'||a=='-'){if(b=='+'||b=='-'||b==')'||b=='=')return '>';elsereturn '<';}if(a=='*'||a=='/'){if(b=='('||b=='^')return '<';elsereturn '>';}if(a=='('){if(b==')')return '=';elsereturn '<';}if(a==')'){if(b!='(')return '>';}if(a=='#'){if(b=='=')return '=';elsereturn '<';}if(a=='^')return ('>');} //判断两运算符的先后次序主函数int main() //主函数{char c,x,theta;int a,b,c1; //定义变量SqStack OPTR; //定义字符栈sqStack OPNR; //定义整型栈InitStack_char(&OPTR); //初始化InitStack_int(&OPNR); //初始化Push_char(&OPTR,'#'); //将字符型栈底设为#c = getchar(); //从键盘输入得到字符while(c!='='||GetTop_char(&OPTR)!='#') //判定是否执行循环if(!In(c)){c1 = 0;while(!In(c)){c1 = c1*10+c-'0';c = getchar();}Push_int(&OPNR,c1);} //当扫描字符不是运算符时，转化为整型数存入栈中else{switch(Precede(GetTop_char(&OPTR),c)) //判定运算符的优先关系{case '<':Push_char(&OPTR,c);c = getchar();break; //当前运算符优先级高，存入char栈case '=':Pop_char(&OPTR,c);c = getchar();break; //运算符次序相等，存入char栈case '>': //当前运算符优先级低Pop_char(&OPTR,theta);Pop_int(&OPNR,b);Pop_int(&OPNR,a);Push_int(&OPNR, Operate(a,theta,b));//计算运算结果，并存入int栈break; //继续循环}}printf("%d\n",GetTop_int(&OPNR)); //计算完成，取出int栈顶元素，并输出return 0;}四、程序调试分析编写程序的过程中遇到了很多的问题，最突出的两个问题就是整数和两位数的运算处理，一开始修改了主函数部分之后，原来可以执行一位数运算的程序出现了error，由于没有及时保存，并且之前的代码无法恢复，只得重新编写一次。

数据结构与算法实验报告数据结构与算法实验报告1.引言在本实验中，我们将研究和实现一些经典的数据结构和算法，以及它们在各种问题中的应用。

本文档详细介绍了每个实验的目标、方法、结果和分析。

2.实验一：线性表的操作2.1 实验目标本实验旨在熟悉线性表的基本操作，并通过实践掌握线性表的顺序存储结构和链式存储结构的实现。

2.2 实验方法2.2.1 实验环境- 编程语言：C++- 开发工具：Visual Studio Code2.2.2 实验步骤1.实现顺序存储结构的线性表。

2.实现链式存储结构的线性表。

3.通过编写测试用例，验证线性表的各种操作。

2.3 实验结果与分析通过实验，我们完成了线性表的顺序存储结构和链式存储结构的实现，并且通过测试用例验证了它们的正确性。

3.实验二：树的操作3.1 实验目标本实验旨在熟悉树的基本操作，并通过实践掌握二叉树和平衡二叉树的实现。

3.2 实验方法3.2.1 实验环境- 编程语言：C++- 开发工具：Visual Studio Code3.2.2 实验步骤1.实现二叉树的基本操作，如插入节点、删除节点等。

2.实现平衡二叉树，并保持其平衡性。

3.通过编写测试用例，验证树的各种操作。

3.3 实验结果与分析通过实验，我们完成了二叉树和平衡二叉树的实现，并且通过测试用例验证了它们的正确性。

4.实验三：图的操作4.1 实验目标本实验旨在熟悉图的基本操作，并通过实践掌握图的表示方法和常用算法。

4.2 实验方法4.2.1 实验环境- 编程语言：C++- 开发工具：Visual Studio Code4.2.2 实验步骤1.实现图的邻接矩阵表示法和邻接链表表示法。

2.实现图的深度优先搜索和广度优先搜索算法。

3.通过编写测试用例，验证图的各种操作和算法的正确性。

4.3 实验结果与分析通过实验，我们完成了图的邻接矩阵表示法和邻接链表表示法的实现，以及深度优先搜索和广度优先搜索算法的实现，并且通过测试用例验证了它们的正确性。

河南工程学院理学院学院实验报告（数据结构与算法）学期:课程:专业:班级:学号:姓名:指导教师:目录实验一线性表1 ................. 错误!未定义书签。

实验二线性表2 ................. 错误!未定义书签。

实验三栈和队列的应用........... 错误!未定义书签。

实验四赫夫曼编码............... 错误!未定义书签。

实验二线性表2（循环链表实现约瑟夫环）错误!未定义书签。

实验一线性表1 ................. 错误!未定义书签。

实验二线性表2 ................. 错误!未定义书签。

实验三栈和队列的应用........... 错误!未定义书签。

实验四赫夫曼编码............... 错误!未定义书签。

实验四赫夫曼编码实验一线性表1 ................. 错误!未定义书签。

实验二线性表2 ................. 错误!未定义书签。

实验三栈和队列的应用........... 错误!未定义书签。

实验四赫夫曼编码............... 错误!未定义书签。

实验六排序算法实验一线性表1一、实验学时： 2学时二、实验目的1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系。

在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。

2.熟练掌握这两类存储结构的描述方法以及线性表的基本操作在这两种存储结构上的实现。

三、实验内容1. 编写程序，实现顺序表的合并。

2. 编写程序，实现单链表的合并。

四、主要仪器设备及耗材硬件：计算机一台软件：VC++ ，MSDN2003或者以上版本五、算法设计1. 顺序表合并的基本思想程序流程图：2. 单链表合并的基本思想程序流程图六、程序清单七、实现结果八、实验体会或对改进实验的建议实验二线性表2一、实验学时： 2学时二、实验目的1.了解双向循环链表的逻辑结构特性，理解与单链表的区别与联系。