浙师大数理与信息工程学院
学生实验报告
课程名称数据结构与算法
专业
姓名
学号
班级
教师
成绩
目录
实验一线性表的实现-3
实验二栈和队列的应用-14
实验三二叉树的建立与遍历-20 实验四图的建立与遍历-25
实验一线性表的实现
一、实验目的
1）掌握线性表的顺序存储结构和链式存储结构；
2）熟练掌握顺序表和链表基本算法的实现；
3）掌握利用线性表数据结构解决实际问题的方法和基本技巧；
4）按照实验题目要求独立正确地完成实验内容（编写、调试算法程序，提交程序清单及及相关实验数据与运行结果）；
二、实验内容
1、顺序表的基本操作实现实验
要求：数据元素类型ElemType取整型int。按照顺序存储结构实现如下算法（各算法边界条件和返回结果适当给出）：
1）创建任意整数线性表（即线性表的元素值随机在键盘上输入），长度限定在25之内；
2）打印（遍历）该线性表（依次打印出表中元素值）；
3）在线性表中查找第i个元素，并返回其值；
4）在线性表中第i个元素之前插入一已知元素；
5）在线性表中删除第i个元素；
6）求线性表中所有元素值（整数）之和；
2、链表（带头结点）基本操作实验
要求：数据元素类型ElemType取字符型char。按照动态单循环链表结构实现如下算法（各算法边界条件适当给出）：
1）创建任意字符型有序（递增排序）单循环链表（即链表的字符元素随机在键盘上输入），长度限定在15之内；
2）打印（遍历）该链表（依次打印出表中元素值）；
3）在链表中查找第i个元素，i合法返回元素值，否则，返回FALSE； 4）在链表中查找与一已知字符相同的第一个结点，有则返回TRUE，否则，返回FALSE；
5）在链表中按照有序方式插入一已知字符元素；
6）在线性表中删除第i个结点；
7）计算链表的长度。
8) 将链表逆序。（选作）
三、实验原理
顺序表和链表的基本操作的实现算法。
四、实验方法与步骤
首先定义顺序表和链表的存储结构，根据基本操作的算法，实现各个基本操作的函数，并在主函数中调用这些操作进行验证。
五、程序代码：
1.线性表:
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#include
#include
typedef int ElemType;
typedef int Status;
#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量
#define LISTINCREMEMT 10 //线性表存储空间的分配增量
typedef struct{
ElemType * elem; //存储空间基址
int length; // 当前长度
int listsize; //当前分配的存储容量（以sizeof(ElemType)为单位）
}SqList;
Status InitList_Sq(SqList&L){
//构造一个空的线性表
L.elem=(ElemType * )malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!L.elem)exit(OVERFLOW); //存储分配失败
L.length=0; //空表长度为0
L.listsize=LIST_INIT_SIZE;//初始存储容量
return OK;//初始化成功
}//InitList_Sq
Status creatlist(SqList &L,int len){// 通过键盘随机输入创建一个线性表（长度小于80）printf("Please input %d int numbers:\n", len);
for(int i=0;i { fflush(stdin); scanf("%d", L.elem+i); } L.length=len; return OK; } Status ListTraver(SqList L){ printf("the numbers:\n"); for(int i=0;i printf("%d\t",L.elem[i]); return OK; } Status GetElem(SqList L,int i,ElemType &e) { if(i>0&&i<=L.length) e=L.elem[i-1]; printf("The value of %dth elment is %d\n",i, e); return OK; } Status ListInsert_Sq(SqList &L,int i,ElemType e){ // 在顺序表L的第i 个元素之前插入新的元素e,。i 的合法范围为1≤i≤L.length+1 //int *q,*p; if(i<1||i>L.length+1) return ERROR;//i插入位置不合法 if(L.length>=L.listsize){// 当前存储空间已满，增加分配 ElemType * newbase=(ElemType *)realloc(L.elem, (L.listsize+LISTINCREMEMT)*sizeof(ElemType)); if(!newbase)exit(OVERFLOW);//存储分配失败 L.elem=newbase;// 新基址 L.listsize+=LISTINCREMEMT;// 增加存储容量 } ElemType *q=&(L.elem[i-1]);//指示插入位置 for(ElemType *p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p;//插入位置及之后的元素右移 *q=e;//插入e ++L.length;//表长加1 return OK; }//ListInsert_Sq int ListDelete_Sq(SqList &L,int i,ElemType &e){ //在顺序线性表L中删除第i个元素，并用返回其值。i的合法值为1<=i<=ListLength(L) if((i<1)||(i>L.length)) return ERROR;//删除位置不合法 ElemType *p=&(L.elem[i-1]);// p 为被删除元素的位置 e=*p;//被删除元素的值赋给e ElemType *q=L.elem+L.length-1;//表尾元素的位置 for(++p;p<=q;++p) *(p-1)=*p;//被删除元素之后的元素左移 --L.length;//表长减1 return e; }//ListDelete_Sq int ListSum(SqList L){ int s=0; for(ElemType i=0;i s=s+L.elem[i]; return s; } void main() { SqList L ; InitList_Sq(L); int len; printf("Please input the length of the List:\n"); fflush(stdin); scanf("%d",&len); creatlist(L,len); ListTraver(L); int pos; ElemType e=0; printf("Please input the position i to be searched:\n"); fflush(stdin); scanf("%d", &pos); GetElem(L,pos,e); printf("The value of %dth elment is %d\n",pos, e); ListTraver(L); printf("Please input the position i to be inserted:\n"); fflush(stdin); scanf("%d", &pos); printf("Please input the value e to be inserted:\n"); fflush(stdin); scanf("%d", &e); ListInsert_Sq(L, pos, e); ListTraver(L); printf("Please input the position i to be deleted:\n"); fflush(stdin); scanf("%d", &pos); ListDelete_Sq(L, pos, e); printf("the value deleted is %d \n", e); ListTraver(L); int s=ListSum(L); printf("sum: %d\n",s); } 2．链表: #include #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 #include typedef char ElemType; typedef int Status; typedef struct LNode{ ElemType data; // 数据域 struct LNode *next; // 指针域 }LNode ,*LinkList; Status InitList_L(LinkList &L){//构建一个空的单循环的链表L=(LinkList)malloc(sizeof(LNode));//L指向空链表 if(!L) exit(OVERFLOW); L->next=L;//构建循环链表表示：尾节点指针域指向头结点return OK; }//InitLinklist int compare(ElemType a,ElemType b){ if(a>b) return 1; if(a==b) return 0; if(a Status visit(ElemType e) { printf("%c\t",e); printf("\n"); return OK; } Status OrderListInsert_L(LinkList &L,ElemType e, Status((*compare)(ElemType a,ElemType b))){//按递增顺序插入e LNode *p=L; while(p->next!=L&&compare(p->next->data,e)<0) p=p->next; LNode *s=(LinkList)malloc(sizeof(LNode));//给新元素分配节点s->data=e; s->next=p->next; p->next=s; return OK; }//OrderListInser_L Status CreateList_L(LinkList &L,int n){ //if(n<=o) {printf("bad number\n"); return ERROR; //printf("\nplease input %d\n"); for(int i=n;i>0;--i){ fflush(stdin); char e=getchar(); OrderListInsert_L(L,e,compare); } return OK; }//GreateList_L Status ListTraverse(LinkList L,Status(*visit)(ElemType e)){ for(LNode *p=L->next;p!=L;p=p->next) if(!visit(p->data)) return ERROR; return OK; } Status GetElem(LinkList L,int i,ElemType &e){//L是带头结点的链表的头指针，以e返回第i 个元素 LNode *p=L->next; int j=1;//初始化，p指向第一个结点，j为计数器 while(p!=L&&j if(!p||j>i) return ERROR;//第i个元素不存在 e=p->data;//取第i 个元素 return OK; }//GetElem int LocateElem(LinkList L,ElemType e, Status (*compare)(ElemType,ElemType)){ //在顺序表中查询第一个满足判定条件的数据元素， // 若存在，则返回它的位序，否则返回FALSE LNode *p=L->next; int i=1;//i 的初值为第1 元素的位序 while(p!=L&&compare(p->data,e)<0){p=p->next;i++;} if(p!=L) return i; else return FALSE; }//LocateElem Status ListDelete_L(LinkList &L,int i,ElemType &e){ //在带头结点的循环链表中删除i个元素，并由e返回其值 LNode *p=L;int j=0; while(p->next != L && j p=p->next;++j; } if(p->next == L|| j > i-1) return ERROR;//删除位置不合理 LNode*q=p->next; p->next=q->next;//删除并释放结点 e=q->data; free(q); return OK; }//ListDelete_L int ListLenth_L(LinkList L){ int i=0; LNode *p=L; while(p->next != L) {++i; p=p->next;} return i; } void main() { LinkList L; InitList_L(L);// int len,i; printf("please input len:\n"); fflush(stdin); scanf("%d",&len); printf("please input the elem:\n"); CreateList_L(L,len); printf("the number:\n"); ListTraverse(L,visit); ElemType e='a'; for(i=1;i<=len;i++) { GetElem(L,i,e); } printf("please input the position you want:\n"); fflush(stdin); e=getchar(); printf("the position of the %c is %d",e,LocateElem(L,e,compare)); printf("\n"); printf("please input the elem insert:\n"); fflush(stdin); e=getchar(); OrderListInsert_L(L,e,compare); ListTraverse(L,visit); printf("please input the position delete:\n"); fflush(stdin); scanf("%d",&i); ListDelete_L(L,i,e); ListTraverse(L,visit); printf("the lenth of the list is %d:",ListLenth_L(L)); } 六、运行结果及结果分析 1.线性表 Please input the length of the List: 5 Please input 5 int numbers: 245 35 25 11111 453 the numbers: 245 35 25 11111 453 Please input the position i to be search ed: 3 The value of 3th elment is 25 The value of 3th elment is 25 the numbers: 245 35 25 11111 453 Please input the position i to be insert ed: 4 Please input the value e to be inserted: 22 the numbers: 245 35 25 22 11111 453 Please input the position i to b e deleted: 2 the value deleted is 35 the numbers: 245 25 22 11111 453 sum: 11856 请按任意键继续. . . 2.链表 please input len: 4 please input the elem: g h 7 5 the number: 5 7 g h please input the position you want: 2 the position of the 2 is 1 please input the elem insert: 4 4 5 7 g h please input the position delete: 3 4 5 g h the lenth of the list is 4:请按任意键继续. . . 实验二栈和队列的应用 一、实验目的 1）掌握栈与队列的数据类型描述及特点； 2）熟练掌握栈的顺序和链式存储存表示与基本算法的实现； 3）掌握队列的链式存储表示与基本操作算法实现; 4) 掌握栈与队列在实际问题中的应用和基本编程技巧; 5）按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结果. 二、实验内容 1）利用栈深度优先进行迷宫求解。 2）利用队列宽度优先进行迷宫求解。(选作) 三、实验原理 顺序栈、链栈、顺序队列与链队列的基本操作的实现算法，搜索的基本思想。 四、实验方法与步骤 1)定义顺序栈和顺序队列的存储结构； 2)实现顺序栈和顺序队列的基本操作； 3)基于搜索的基本思想，实现迷宫求解算法。 五、程序代码： #include using namespace std; class T //定义描述迷宫中当前位置的结构类型 { public: int x; //x代表当前位置的行坐标 int y; //y代表当前位置的列坐标 int dir; //0:无效,1:东,2:南,3:西,4:北 }; class LinkNode //链表结点 { friend class Stack; public: T data; LinkNode *next; }; class Stack { private: LinkNode *top; //指向第一个结点的栈顶指针 public: Stack(); //构造函数，置空栈 ~Stack(); //析构函数 void Push(T e); //把元素data入栈 T Pop(); //使栈顶元素出栈 T GetPop(); //取出栈顶元素 void Clear(); //把栈清空 bool empty(); //判断栈是否为空，如果为空则返回1，否则返回0 }; Stack::Stack() //构造函数，置空栈 { top=NULL; } Stack::~Stack() //析构函数 { } void Stack::Push(T e) //把元素x压入栈中 { LinkNode *P; P=new LinkNode; P->data=e; P->next=top; top=P; } T Stack::Pop() //使栈顶元素出栈 { T Temp; LinkNode *P; P=top; top=top->next; Temp=P->data; delete P; return Temp; } T Stack::GetPop() //取出栈顶元素 { return top->data; } void Stack::Clear() //把栈清空 { top=NULL; } bool Stack::empty() //判断栈是否为空，如果为空则返回1，否则返回0 { if(top==NULL) return 1; else return 0; } int move[4][2]={{0,1},{1,0},{0,-1},{-1,0}}; //定义当前位置移动的4个方向bool Mazepath(int **maze,int m,int n); //寻找迷宫maze中从（0，0）到（m,n）的路径 //到则返回true,否则返回false void PrintPath(Stack p); //输出迷宫的路径 void Restore(int **maze,int m,int n); //恢复迷宫 int** GetMaze(int &m,int &n); //获取迷宫 //返回存取迷宫的二维指针 int main() { int m=0,n=0; //定义迷宫的长和宽 int **maze; //定义二维指针存取迷宫 maze=GetMaze(m,n); //调用GetMaze(int &m,int &n)函数，得到迷宫 if(Mazepath(maze,m,n)) //调用Mazepath(int **maze,int m,int n)函数获取路径cout<<"迷宫路径探索成功!\n"; else cout<<"路径不存在!\n"; return 0; } int** GetMaze(int &m,int &n)//返回存取迷宫的二维指针 { int **maze; //定义二维指针存取迷宫 int i=0,j=0; cout<<"请输入迷宫的长和宽:"; int a,b;cin>>a>>b; //输入迷宫的长和宽 cout<<"请输入迷宫内容:\n"; m=a; n=b; //m,n分别代表迷宫的行数和列数 maze=new int *[m+2]; //申请长度等于行数加2的二级指针 for(i= 0;i { maze[i]=new int[n+2]; } for(i=1;i<=m;i++) //输入迷宫的内容，0代表可通，1代表不通 for(j=1;j<=n;j++) cin>>maze[i][j]; for(i=0;i maze[i][0]=maze[i][n+1]=1; for(i=0;i maze[0][i]=maze[m+1][i]=1; return maze; //返回存贮迷宫的二维指针maze }; bool Mazepath(int **maze,int m,int n)//寻找迷宫maze中从（0，0）到（m,n）的路径//到则返回true,否则返回false { Stack q,p; //定义栈p、q,分别存探索迷宫的过程和存储路径 T Temp1,Temp2; int x,y,loop; Temp1.x=1; Temp1.y=1; q.Push(Temp1); //将入口位置入栈 p.Push(Temp1); maze[1][1]=-1; //标志入口位置已到达过 while(!q.empty()) //栈q非空，则反复探索 { Temp2=q.GetPop(); //获取栈顶元素 if(!(p.GetPop().x==q.GetPop().x&&p.GetPop().y==q.GetPop().y)) p.Push(Temp2); //如果有新位置入栈，则把上一个探索的位置存入栈p for(loop=0;loop<4;loop++) //探索当前位置的4个相邻位置 { x=Temp2.x+move[loop][0]; //计算出新位置x位置值 y=Temp2.y+move[loop][1]; //计算出新位置y位置值 if(maze[x][y]==0) //判断新位置是否可达 { Temp1.x=x; Temp1.y=y; maze[x][y]=-1; //标志新位置已到达过 q.Push(Temp1); //新位置入栈 } if((x==(m))&&(y==(n))) //成功到达出口 { Temp1.x=m; Temp1.y=n; Temp1.dir=0; p.Push(Temp1); //把最后一个位置入栈 PrintPath(p); //输出路径 Restore(maze,m,n); //恢复路径 return 1; //表示成功找到路径 } } if(p.GetPop().x==q.GetPop().x&&p.GetPop().y==q.GetPop().y) //如果没有新位置入栈，则返回到上一个位置 { p.Pop(); q.Pop(); } } return 0; //表示查找失败，即迷宫无路经 } void PrintPath(Stack p) //输出路径 { cout<<"迷宫的路径为\n"; cout<<"括号内的内容分别表示为(行坐标,列坐标,数字化方向,方向)\n"; Stack t; //定义一个栈，按从入口到出口存取路径 int a,b; T data; LinkNode *temp; temp=new LinkNode; //申请空间 temp->data=p.Pop(); //取栈p的顶点元素，即第一个位置 t.Push(temp->data); //第一个位置入栈t delete temp; //释放空间 while(!p.empty()) //栈p非空，则反复转移 { temp=new LinkNode; temp->data=p.Pop(); //获取下一个位置 //得到行走方向 a=t.GetPop().x-temp->data.x; //行坐标方向 b=t.GetPop().y-temp->data.y; //列坐标方向 if(a==1) temp->data.dir=1; //方向向下，用1表示 else if(b==1) temp->data.dir=2; //方向向右，用2表示 else if(a==-1) temp->data.dir=3; //方向向上，用3表示 else if(b==-1) temp->data.dir=4; //方向向左，用4表示 t.Push(temp->data); //把新位置入栈 delete temp; } //输出路径，包括行坐标，列坐标，下一个位置方向 while(!t.empty()) //栈非空，继续输出 { data=t.Pop(); cout<<'('< { case 1:cout<<"↓)\n";break; case 2:cout<<"→)\n";break; case 3:cout<<"↑)\n";break; case 4:cout<<"←)\n";break; case 0:cout<<")\n";break; } } } void Restore(int **maze,int m,int n) //恢复迷宫 { int i,j; for(i=0;i for(j=0;j { if(maze[i][j]==-1) //恢复探索过位置，即把-1恢复为0 maze[i][j]=0; } } 六、运行结果及结果分析 请输入迷宫的长和宽:3 3 请输入迷宫内容: 0,0,0,1,1,0,1,1,0 迷宫的路径为 括号内的内容分别表示为(行坐标,列坐标,数字化方向,方向) (1,1,2,→) (1,2,1,↓) (2,2,1,↓) (3,2,2,→) (3,3,0,) 迷宫路径探索成功! 请按任意键继续. . .. 实验三二叉树的建立与遍历 一、实验目的 1）熟练掌握二叉树的二叉链表表示创建算法与实现； 2）熟练掌握先序、中序、后序和层次遍历二叉树的基本递归遍历算法与实现； 3）理解借用栈的先序、中序和后序非递归遍历算法与实现； 4）按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结果）； 二、实验内容 1) 创建二叉树：先序创建；（比如给定先序序列字符串来创建等） 2) 遍历二叉树：先，中，后序遍历，（选做）层次遍历； 3) 遍历过程中求解二叉树的属性：叶子结点数，结点数，深度，（选做） 宽度 4) 打印某节点所在的二叉树路径：根结点到某节点的路径；（选做） 5）二叉树置空：清空二叉树； 6) 子树互换：二叉树所有左右子树互换；(选作) 7）二叉树线索：中序线索二叉树。(选作) 三、实验原理 二叉树的遍历方法： 1）先序(根)遍历：(1)访问根结点；(2)先序遍历左子树；(3)先序遍历右子树； 2）中序(根)遍历：(1)中序遍历左子树；(2)访问根结点；(3)中序遍历右子树； 3）后序(根)遍历：(1)后序遍历左子树; (2)后序遍历右子树；(3)访问根结点; 4）按层次遍历：从上到下、从左到右访问各结点（提示：借用队列）四、实验方法与步骤 1）实现建立二叉树的函数； 2）重点实现4种二叉树遍历函数（层次遍历为选做）； 《数据结构课程实验》大纲 一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： （1）内容丰富，学习量大，给学习带来困难； （2）贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点； （3）所用到的技术多，而在此之前的各门课程中所介绍的专业性知识又不多，因而加大了学习难度； （4）隐含在各部分的技术和方法丰富，也是学习的重点和难点。 根据《数据结构课程》课程本身的技术特性，设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练，突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为18。 二、《数据结构课程实验》的目的和要求 不少学生在解答习题尤其是算法设计题时，觉得无从下手，做起来特别费劲。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。 为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术，与特定问题相关的技术等，要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上，掌握分析、解决实际问题的能力。 三、《数据结构课程实验》内容 课程实验共18学时，要求完成以下六个题目： 实习一约瑟夫环问题（2学时） 实验一顺序表问题 【实验报告】 《数据结构与算法》实验报告一 学院：计算机与信息学院班级： 学号：姓名： 日期：程序名： 一、上机实验的问题和要求： 顺序表的查找、插入与删除。设计算法，实现线性结构上的顺序表的产生以及元素的查找、插入与删除。具体实现要求： 1.从键盘输入10个整数，产生顺序表，并输出结点值。 调试数据：9 8 7 6 5 4 3 2 1 2.从键盘输入1个整数，在顺序表中查找该结点。若找到，输出结点的位置；若找不到， 则显示“找不到”。 调试数据：第一次输入11，第二次输入3 3.从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插 入在对应位置上，输出顺序表所有结点值，观察输出结果。 调试数据：第一次insert "11" after "6" ，第二次insert "86" at "2" 4.从键盘输入1个整数，表示欲删除结点的位置，输出顺序表所有结点值，观察输出结果。 调试数据：第一次delete the number at "2" ，第二次delete value "9" 注意：顺序表输出表现形式如下（实验报告上为截图）： 顺序表： 第一题 Initially Seq: head -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null 第二题 找不到 6 第三题 insert "11" after "6": head -> 9 -> 8 -> 7 -> 6 -> 11 -> 5 -> 4 -> 3 -> 2 -> 1 -> null insert"86"at"2":head -> 9 -> 8 -> 86 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null 第四题 delete the number at "2":head -> 9 -> 8 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 ->null delete value "9": head -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null 数据结构实验报告全集 实验一线性表基本操作和简单程序 1 ．实验目的 （1 ）掌握使用Visual C++ 6.0 上机调试程序的基本方法； （2 ）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2 ．实验要求 （1 ）认真阅读和掌握和本实验相关的教材内容。 （2 ）认真阅读和掌握本章相关内容的程序。 （3 ）上机运行程序。 （4 ）保存和打印出程序的运行结果，并结合程序进行分析。 （5 ）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>// 头文件 #include nodetype *create()// 建立单链表，由用户输入各结点data 域之值， // 以0 表示输入结束 { elemtype d;// 定义数据元素d nodetype *h=NULL,*s,*t;// 定义结点指针 int i=1; cout<<" 建立一个单链表"< 数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include 图实验一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template #include 华北电力大学 实验报告| | 实验名称数据结构实验 课程名称数据结构 | | 专业班级：学生姓名： 学号：成绩： 指导教师：实验日期：2015/7/3 实验报告说明： 本次实验报告共包含六个实验，分别为：简易停车场管理、约瑟夫环（基于链表和数组）、二叉树的建立和三种遍历、图的建立和两种遍历、hash-telbook和公司招工系统。 编译环境：visual studio 2010 使用语言：C++ 所有程序经调试均能正常运行 实验目录 实验一约瑟夫环（基于链表和数组） 实验二简易停车场管理 实验三二叉树的建立和三种遍历 实验四图的建立和两种遍历 实验五哈希表的设计 实验一：约瑟夫环 一、实验目的 1.熟悉循环链表的定义和有关操作。 二、实验要求 1.认真阅读和掌握实验内容。 2．用循环链表解决约瑟夫问题。 3.输入和运行编出的相关操作的程序。 4.保存程序运行结果 , 并结合输入数据进行分析。 三、所用仪器设备 1.PC机。 2.Microsoft Visual C++运行环境。 四、实验原理 1.约瑟夫问题解决方案： 用两个指针分别指向链表开头和下一个，两指针依次挪动，符合题意就输出结点数据，在调整指针，删掉该结点。 五、代码 1、基于链表 #include 实验项目名称：图的遍历 一、实验目的 应用所学的知识分析问题、解决问题，学会用建立图并对其进行遍历，提高实际编程能力及程序调试能力。 二、实验容 问题描述：建立有向图，并用深度优先搜索和广度优先搜素。输入图中节点的个数和边的个数，能够打印出用邻接表或邻接矩阵表示的图的储存结构。 三、实验仪器与设备 计算机，Code::Blocks。 四、实验原理 用邻接表存储一个图，递归方法深度搜索和用队列进行广度搜索，并输出遍历的结果。 五、实验程序及结果 #define INFINITY 10000 /*无穷大*/ #define MAX_VERTEX_NUM 40 #define MAX 40 #include typedef struct ArCell{ int adj; }ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { char name[20]; }infotype; typedef struct { infotype vexs[MAX_VERTEX_NUM]; AdjMatrix arcs; int vexnum,arcnum; }MGraph; int LocateVex(MGraph *G,char* v) { int c = -1,i; for(i=0;i 2009级数据结构实验报告 实验名称：约瑟夫问题 学生姓名：李凯 班级：21班 班内序号：06 学号：09210609 日期：2010年11月5日 1．实验要求 1）功能描述：有n个人围城一个圆圈，给任意一个正整数m，从第一个人开始依次报数，数到m时则第m个人出列，重复进行，直到所有人均出列为止。请输出n个人的出列顺序。 2）输入描述：从源文件中读取。 输出描述：依次从显示屏上输出出列顺序。 2. 程序分析 1）存储结构的选择 单循环链表 2）链表的ADT定义 ADT List{ 数据对象：D={a i|a i∈ElemSet,i=1,2,3,…n,n≧0} 数据关系：R={< a i-1, a i>| a i-1 ,a i∈D,i=1,2,3,4….,n} 基本操作： ListInit(&L)；//构造一个空的单链表表L ListEmpty(L); //判断单链表L是否是空表，若是，则返回1，否则返回0. ListLength(L); //求单链表L的长度 GetElem（L，i）；//返回链表L中第i个数据元素的值； ListSort(LinkList [内容要求] 1、存储结构：顺序表、单链表或其他存储结构，需要画示意图，可参考书上P59 页图2-9 2.2 关键算法分析 结点类： template 学期：2010-2011学年第一学期指导教师：杨华莉成绩： 实验一顺序表的基本操作 一、实验目的 1．掌握使用VC++6.0调试程序的基本方法； 2．掌握线性表的顺序存储结构的类型定义； 3．掌握顺序表的基本操作的实现,如：插入、删除、遍历、查找、排序、修改、合并等； 4．掌握顺序表的应用。 二、实验要求 1．认真阅读和掌握本实验的示例程序。 2．上机运行示例程序，打印出程序的运行结果，并作必要的说明。 3．对示例程序，按照对线性表的操作需要，在程序中至少添加2个顺序表的相关操作。如： i.查找并显示分数在区间[a，b）的学生信息； ii.查找并显示最高分或最低分学生信息； iii.统计不及格或及格人数及所占比例； iv.将信息表按学号、姓名或分数升序或降序排列； v.按学号顺序进行数据元素的插入； vi.删除指定学号或姓名的学生信息； vii.修改某个学生的信息； viii.其它。 4．重新改写主函数（要求必需调用自己添加的操作），打印出文件清单（自己添加的函数、修改后的主函数和运行结果）。 5．对修改后的程序，分析每一个算法（函数）的时间复杂度。 6．根据上述要求撰写实验报告，并简要给出算法设计小结和心得。 三、实验环境 1．台式计算机每人一台； 2．软件：Visual C++6.0 四、实验内容和实验结果 一．示例程序运行结果及说明 二．自己添加的新函数(至少2个)，要求加必要的注释。 SqList Delete_SqList(SqList &L)//删除学生信息 { Elemtype x; int i=0; int choice=DMenu(); char name[25]; int num,k; if(!L.length) { printf("表为空，无法删除!"); exit(0); } switch(choice) { case 1: //按姓名删除 printf("\n请输入要删除的学生的姓名\n"); scanf("%s",&name); k=strcmp(name,L.data[i].name);//比较姓名 if(k==0) { x=L.data[i-1]; for(int m=L.length-1;m>=i-1;--m) L.data[i-1]=L.data[i]; --L.length; break; } case 2: //按学号删除 printf("\n请输入要删除学生的学号\n"); scanf("%d",&num); if(num==L.data[i].num) { for(int m=L.length-1;m>=i-1;--m) L.data[i-1]=L.data[i]; --L.length; break; } case 3:break; } return L; 邻接矩阵的实现 1. 实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现2. 实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历3．设计与编码MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template int vertexNum, arcNum; }; #endif MGraph.cpp #include 云南大学软件学院数据结构实验报告 （本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助）实验难度： A □ B □ C □ 学期：2010秋季学期 任课教师: 实验题目: 查找算法设计与实现 姓名: 王辉 学号: 20091120154 电子邮件: 完成提交时间： 2010 年 12 月 27 日 云南大学软件学院2010学年秋季学期 《数据结构实验》成绩考核表 学号：姓名：本人承担角色： 综合得分：（满分100分） 指导教师：年月日（注：此表在难度为C时使用，每个成员一份。） （下面的内容由学生填写，格式统一为，字体: 楷体, 行距: 固定行距18，字号: 小四，个人报告按下面每一项的百分比打分。难度A满分70分，难度B满分90分）一、【实验构思（Conceive）】(10%) 1 哈希表查找。根据全年级学生的姓名，构造一个哈希表，选择适当的哈希函数和解决冲突的方法，设计并实现插入、删除和查找算法。 熟悉各种查找算法的思想。 2、掌握查找的实现过程。 3、学会在不同情况下运用不同结构和算法求解问题。 4 把每个学生的信息放在结构体中： typedef struct //记录 { NA name; NA tel; NA add; }Record; 5 void getin(Record* a)函数依次输入学生信息 6 人名折叠处理，先将用户名进行折叠处理折叠处理后的数，用除留余数法构造哈希函数，并返回模值。并采用二次探测再散列法解决冲突。 7姓名以汉语拼音形式，待填入哈希表的人名约30个，自行设计哈希函数，用线性探测再散列法或链地址法处理冲突；在查找的过程中给出比较的次数。完成按姓名查询的操作。将初始班级的通讯录信息存入文件。 二、【实验设计(Design)】(20%) （本部分应包括：抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明，主程序模块与各子程序模块间的调用关系） 1抽象数据类型的功能规格说明和结构体： #include 《数据结构》实验报告 ◎实验题目: 无向图的建立与遍历 ◎实验目的：掌握无向图的邻接链表存储，熟悉无向图的广度与深度优先遍历。 ◎实验内容：对一个无向图以邻接链表存储，分别以深度、广度优先非递归遍历输出。 一、需求分析 1.本演示程序中，输入的形式为无向图的邻接链表形式，首先输入该无向图的顶点数和边数，接着输入顶点信息，再输入每个边的顶点对应序号。 2.该无向图以深度、广度优先遍历输出。 3.本程序可以实现无向图的邻接链表存储，并以深度、广度优先非递归遍历输出。 4.程序执行的命令包括：（1）建立一个无向图的邻接链表存储（2）以深度优先遍历输出（3）以广度优先遍历输出（4）结束 5.测试数据： 顶点数和边数：6,5 顶点信息：a b c d e f 边的顶点对应序号： 0,1 0,2 0,3 2,4 3,4 深度优先遍历输出： a d e c b f 广度优先遍历输出： a d c b e f 二概要设计 为了实现上述操作，应以邻接链表为存储结构。 1.基本操作： void createalgraph(algraph &g) 创建无向图的邻接链表存储 void dfstraverseal(algraph &g,int v) 以深度优先遍历输出 void bfstraverseal(algraph &g,int v) 以广度优先遍历输出 2.本程序包含四个模块： （1）主程序模块 （2）无向图的邻接链表存储模块 （3）深度优先遍历输出模块 （4）广度优先遍历输出模块 3.模块调用图： 三详细设计 1.元素类型，结点类型和指针类型：typedef struct node { int adjvex; struct node *next; }edgenode; typedef struct vnode { char vertex; edgenode *firstedge; }vertxnode; typedef vertxnode Adjlist[maxvernum]; typedef struct { Adjlist adjlist; int n,e; }algraph; edgenode *s; edgenode *stack[maxvernum],*p; 2.每个模块的分析： （1）主程序模块 int main() 2011~2012第一学期数据结构实验报告 班级：信管一班 学号：201051018 姓名：史孟晨 实验报告题目及要求 一、实验题目 设某班级有M（6）名学生，本学期共开设N（3）门课程，要求实现并修改如下程序（算法）。 1. 输入学生的学号、姓名和 N 门课程的成绩（输入提示和输出显示使用汉字系统）， 输出实验结果。（15分） 2. 计算每个学生本学期 N 门课程的总分，输出总分和N门课程成绩排在前 3 名学 生的学号、姓名和成绩。 3. 按学生总分和 N 门课程成绩关键字升序排列名次，总分相同者同名次。 二、实验要求 1．修改算法。将奇偶排序算法升序改为降序。（15分） 2．用选择排序、冒泡排序、插入排序分别替换奇偶排序算法,并将升序算法修改为降序算法；。（45分）） 3．编译、链接以上算法，按要求写出实验报告（25）。 4. 修改后算法的所有语句必须加下划线，没做修改语句保持按原样不动。 5．用A4纸打印输出实验报告。 三、实验报告说明 实验数据可自定义，每种排序算法数据要求均不重复。 (1) 实验题目：《N门课程学生成绩名次排序算法实现》； (2) 实验目的：掌握各种排序算法的基本思想、实验方法和验证算法的准确性； (3) 实验要求：对算法进行上机编译、链接、运行； (4) 实验环境（Windows XP-sp3,Visual c++)； (5) 实验算法（给出四种排序算法修改后的全部清单）； (6) 实验结果（四种排序算法模拟运行后的实验结果）； (7) 实验体会（文字说明本实验成功或不足之处）。 三、实验源程序（算法） Score.c #include "stdio.h" #include "string.h" #define M 6 #define N 3 struct student { char name[10]; int number; int score[N+1]; /*score[N]为总分,score[0]-score[2]为学科成绩*/ }stu[M]; void changesort(struct student a[],int n,int j) {int flag=1,i; struct student temp; while(flag) { flag=0; for(i=1;i 图实验 一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template 《数据结构实验》的实验题目及实验报告模板 实验一客房管理（链表实验） ●实现功能：采用结构化程序设计思想，编程实现客房管理程序的各个功能函数，从而熟练 掌握单链表的创建、输出、查找、修改、插入、删除、排序和复杂综合应用等操作的算法 实现。以带表头结点的单链表为存储结构，实现如下客房管理的设计要求。 ●实验机时：8 ●设计要求： #include 本科实验报告 课程名称：数据结构（C语言版） 实验项目：线性表、树、图、查找、内排序实验地点：明向校区实验楼208 专业班级：学号： 学生姓名： 指导教师：杨永强 2019 年 1 月10日 #include 数据结构实验报告 第 6 次实验 学号：20141060106 姓名：叶佳伟 一、实验目的 1、复习图的逻辑结构、存储结构及基本操作； 2、掌握邻接矩阵、邻接表及图的创建、遍历； 3、了解图的应用。 二、实验内容 1、（必做题）假设图中数据元素类型是字符型，请采用邻接矩阵或邻接表实现图的以下基本操作： （ 1）构造图（包括有向图、有向网、无向图、无向网）； （ 2）根据深度优先遍历图； （ 3）根据广度优先遍历图。 三、算法描述 （采用自然语言描述） 四、详细设计 （画出程序流程图） 五、程序代码 （给出必要注释） #include int adj;/*顶点关系类型,对无权图,用1(是)或0(否)表示相邻否;对带权图,则为权值*/ char *info;/*弧相关信息指针*/ }AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { char vexs[MAX_VERTEX_NUM][5];/*顶点向量*/ AdjMatrix arcs; /*邻接矩阵*/ int vexnum, arcnum;/*图的当前顶点数和弧数*/ int kind; }MGraph; void CreateDG(MGraph *G); void CreateDN(MGraph *G); void CreateUDG(MGraph *G); void CreateUDN(MGraph *G); int LocateVex(MGraph *G, char v[]); void print(MGraph *G); int main(void) { MGraph *G; G = (MGraph *)malloc(sizeof(MGraph)); printf("请选者0-有向图,1-有向网,2-无向图,3-无向网: "); scanf("%d", &G->kind); switch(G->kind) { case DG : CreateDG(G); print(G); break; case DN : CreateDN(G); print(G); break; case UDG : CreateUDG(G); print(G); break; case UDN : CreateUDN(G); 数据结构(C语言版) 实验报告 专业班级学号姓名 实验1 实验题目：单链表的插入和删除 实验目的： 了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。 实验要求： 建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。 实验主要步骤： 1、分析、理解给出的示例程序。 2、调试程序，并设计输入数据（如：bat，cat，eat，fat，hat，jat，lat，mat，#），测试程序 的如下功能：不允许重复字符串的插入；根据输入的字符串，找到相应的结点并删除。 3、修改程序： （1）增加插入结点的功能。 （2）将建立链表的方法改为头插入法。 程序代码: #include"stdio.h" #include"string.h" #include"stdlib.h" #include"ctype.h" typedef struct node //定义结点 { char data[10]; //结点的数据域为字符串 struct node *next; //结点的指针域 }ListNode; typedef ListNode * LinkList; // 自定义LinkList单链表类型 LinkList CreatListR1(); //函数，用尾插入法建立带头结点的单链表 LinkList CreatList(void); //函数，用头插入法建立带头结点的单链表 ListNode *LocateNode(); //函数，按值查找结点 void DeleteList(); //函数，删除指定值的结点 void printlist(); //函数，打印链表中的所有值 void DeleteAll(); //函数，删除所有结点，释放内存 数据结构教程 上机实验报告 实验七、图算法上机实现 一、实验目的： 1.了解熟知图的定义和图的基本术语，掌握图的几种存储结构。 2.掌握邻接矩阵和邻接表定义及特点，并通过实例解析掌握邻接 矩阵和邻接表的类型定义。 3.掌握图的遍历的定义、复杂性分析及应用，并掌握图的遍历方 法及其基本思想。 二、实验内容： 1.建立无向图的邻接矩阵 2.图的深度优先搜索 3.图的广度优先搜索 三、实验步骤及结果： 1.建立无向图的邻接矩阵： 1)源代码： #include "" #include "" #define MAXSIZE 30 typedef struct { char vertex[MAXSIZE]; ertex=i; irstedge=NULL; irstedge; irstedge=p; p=(EdgeNode*)malloc(sizeof(EdgeNode)); p->adjvex=i; irstedge; irstedge=p; } } int visited[MAXSIZE]; ertex); irstedge; ertex=i; irstedge=NULL; irstedge;irstedge=p; p=(EdgeNode *)malloc(sizeof(EdgeNode)); p->adjvex=i; irstedge; irstedge=p; } } typedef struct node { int data; struct node *next; }QNode; ertex); irstedge;ertex); //输出这个邻接边结点的顶点信息 visited[p->adjvex]=1; //置该邻接边结点为访问过标志 In_LQueue(Q,p->adjvex); //将该邻接边结点送人队Q }数据结构实验报告格式
数据结构实验一顺序表问题及实验报告模板 - Copy
(完整版)数据结构实验报告全集
数据结构实验报告
数据结构实验报告图实验
数据结构实验报告完整
数据结构图的遍历实验报告
数据结构实验报告模板
数据结构实验报告模板(验证型)
数据结构实验报告图实验
数据结构实验报告七查找、
数据结构实验报告无向图
数据结构实验报告及心得体会
数据结构实验报告图实验
《数据结构实验》实验题目及实验报告模板
数据结构实验报告
数据结构实验报告
数据结构实验报告 - 答案汇总
数据结构图实验报告
相关主题
文本预览