南京航空航天大学数据结构软件技术上机报告
《计算机软件技术基础》
实验报告I—数据结构
班号：0312401 学号：031240117 姓名：尚林伟Email：235445892@https://www.wendangku.net/doc/88694007.html, 签名：尚林伟
南京航空航天大学
2014年11月5日
目录
实验一：顺序表、单链表的定义、创建、插入和删除操作，将数据元素显示出来。P1~5
实验二：二叉树的链式存储结构的数据结构定义、创建、先序/中序/后序遍历，并将结果序列输出。P5~6
实验三：图的邻接表和邻接矩阵数据结构的定义、创建；图的深度优先遍历、广度优先遍历。P6~12
实验总结：P13
一、实验要求
●简述每一部分的对象、目的和要求；
●画出算法(程序)的流程图；
●说明程序的数据输入要求和输出结果
的特点与结论；
●附源程序清单；
●实验的总结：遇到的问题以及解决的办
法、方法的优缺点；忌空、大话简述每
一部分。
●对源程序的功能块做适当注释。其他未
尽事项按写报告的一般要求进行。
●报告统一采用A4纸正反面打印(正文采
用5号字体，单倍行距)或手写，左侧
装订。
每人独立完成实验，如发现实验程序或
报告的内容雷同，雷同双方（或多方）
报告视为无效。
实验报告格式如附件提供的模板，提交
的文档格式应严格按规定的模板格式
（文字水印格式为“DS2014_学号_姓
名”，如“DS2014_0312yyyxx_张三”）。
二、实验内容
实验一：顺序表、单链表的定义、创建、插入和删除操作，将数据元素显示出来。
题目分析：此题考查的是线性结构中的顺序表和单链表的基本操作。首先说顺序表，是用内存中地址连续的一块存储空间存放线性表，而内存中地址空间本就是连续的，因此在定义了顺序表以后，只需申请一个指向首地址的指针即可，要想进行添加或删除只需移动指针所指位置找到需要修改的位置即可。
而对于单链表，由于其在内存中位置不连续，而由指针与数据构成一个结点，依次串联，因此修改操作中头指针发挥了巨大用处。此题目在书中就有完整的参考程序代码，可以参照书上的代码进行编程。
程序思路：
顺序表：首先定义顺序表，接着调用顺序表初始化函数SeqList *init_SeqList()申请一个长度为new SeqList[sizeof(SeqList)]的空间，接下来调用顺序表创建函数esta_SeqList(SeqList*L)来进行对顺序表的创建，此函数要求用户输入数组，以-1为结束标志，接下来要求用户进行插入操作，当表满以及插入位置错误时都有提示，接下来就是删除，程序最后会把顺序表的元素用for 循环输出出来
其中比较重要的插入和删除函数流程图如下：（使用流程图绘图软件绘制）
单链表:首先依然是定义一个单链表，接着调用CREATE_SL(SLNODE *h)函数用尾插法建立单链表，使用while循环，要求用户输入数据，以-1为结束标志，接着调用前插算法Insert_LinkList(SLNODE *h,int i,int x)函数进行插入操作，此函数对错误操作都有考虑，接下来就调用Del_LinkList(SLNODE *h,int i)函数进行删除操作，对错误操作也有处理。还有一个输出函数void Print_LinkList(SLNODE *h)用for循环对单链表的数据进行输出。
其中比较重要的插入函数流程图如下：（使用流程图绘图软件绘制）
操作演示：
顺序表*************************** 即将为您建立一个顺序表，请以-1结尾
请您输入一个整数
1
请您输入一个整数
2
请您输入一个整数
4
请您输入一个整数
-1
恭喜你，创建顺序表成功^_^
输入需插入的数据:
3
输入需插入的结点:
3
插入成功^-^
1 2 3 4 输入需删除的结点
1
删除成功^-^
顺序表元素为：
2 3 4
单链表******************************* 欢迎使用单链表程序，感谢伟大的尚林伟同学给你带来了方便
请输入一组数，以-1为结尾
1
2
4
-1
单链表创建成功^-^
输入需插入的数据:
3
输入需插入的结点:
3
插入成功^-^
链表h数据如下
1 2 3 4
输入需删除的结点
4
删除成功^-^
链表h数据如下
1 2 3 源程序代码：
顺序表******************************* //031240117尚林伟
#include
#define SeqList struct listtype
#define MaxSize 1000
SeqList
//定义一个顺序表
{
int data[MaxSize];
int last;
};
SeqList *init_SeqList()
//顺序表的初始化
{
SeqList *L;
L=new SeqList[sizeof(SeqList)];
L->last=-1;
return L;
}
SeqList *esta_SeqList(SeqList*L)
//建立一个顺序表
{
int i,x;
cout<<"即将为您建立一个顺序表，请以-1结尾"< for(i=0;x!=-1;i++) { cout<<"请您输入一个整数"< cin>>x; L->data[i]=x; L->last++; } L->last--; return L; } int Insert_SeqList(SeqList *L,int i,int x) //顺序表插入操作 { int j; i=i-1; if(L->last==MaxSize) { cout<<"很抱歉，顺序表已经满了-_-!!!"< return (-1); } if(i<0||i>L->last) { cout<<"位置错误鸟-_-!!!"< return 0; } if((L->last+1)==0) L->data[L->last+1]=x; else { for(j=L->last;j>=i;j--) L->data[j+1]=L->data[j]; L->data[i]=x; } L->last++; return(1); } int Delete_SeqList(SeqList *L,int i) //顺序表删除操作 { int j; i=i-1; if(i<0||i>L->last) { cout<<"你个傻逼，第i个元素不存在-_-!!!"< return(0); } for(j=i;j<=L->last-1;j++) L->data[j]=L->data[j+1]; L->last--; return(1); } void out_SeqList(SeqList*L)//顺序表元素的输出 { int i; if( L->last!=-1) { for(i=0;i<=L->last;i++) cout< } else cout<<"顺序表为空"< } void main() { SeqList *l; int i,x; l=init_SeqList(); esta_SeqList(l); cout<<"恭喜你，创建顺序表成功^_^"< cout<<"输入需插入的数据:"< cin>>x; cout<<"输入需插入的结点:"< cin>>i; if(Insert_SeqList(l,i,x)) cout<<"插入成功^-^"< else cout<<"插入失败-_-!"< out_SeqList(l); cout<<"输入需删除的结点"< cin>>i; if(Delete_SeqList(l,i)) cout<<"删除成功^-^"< else cout<<"删除失败-_-!"< cout<<"顺序表元素为："< out_SeqList(l); } 单链表******************************* //031240117尚林伟 #include #define SLNODE struct node SLNODE //定义一个单链表 { int data; SLNODE *next; }; void CREATE_SL(SLNODE *h) //尾插法创建一个单链表 { SLNODE *p,*s; int x; h->next=NULL; cout<<"欢迎使用单链表程序，感谢伟大的尚林伟同学给你带来了方便"< cout<<"请输入一组数，以-1为结尾"< cin>>x; while(x!=-1) { s=new SLNODE[sizeof(SLNODE)]; s->data=x; if(h->next==NULL) h->next=s; else p->next=s; p=s; cin>>x; } p->next=NULL; } int Insert_LinkList(SLNODE *h,int i,int x) //单链表的前插操作 { SLNODE *p,*s; int j; p=h;j=0; while(p->next!=NULL&&j { p=p->next; j++; } if(j!=i-1) { cout<<"i不存在不能插入!!!"< return 0; } else { s=new SLNODE[sizeof(SLNODE)]; s->data=x; s->next=p->next; p->next=s; return 1; } } int Del_LinkList(SLNODE *h,int i) //单链表的删除操作 { SLNODE *p,*s; int j; p=h; j=0; while(p->next!=NULL&&j { p=p->next; j++; } if(j!=i-1) { cout<<"i不存在不能删除!!!"< return 0; } else { if(p->next==NULL) { cout<<"第i个节点不存 在!!!"< return 0; } else { s=p->next; p->next=s->next; delete s; return 1; } } } void Print_LinkList(SLNODE *h) //输出链表数据 { SLNODE *p; p=h->next; cout<<"链表h数据如下"< for( ;p->next!=NULL;p=p->next) { cout< } cout< } void main() //主函数 { SLNODE *h; int i,x; h=new SLNODE[sizeof(SLNODE)]; h->next=NULL; CREATE_SL(h); cout<<"单链表创建成功^-^"< cout<<"输入需插入的结点:"< if(Insert_LinkList(h,i,x)) cout<<"插入成功^-^"< cout<<"插入失败-_-!"< cout<<"输入需删除的结点"< if(Del_LinkList(h,i)) cout<<"删除成功^-^"< cout<<"删除失败-_-!"< } 实验二、二叉树的链式存储结构的数据结构 定义、创建、先序/中序/后序遍历，并将结果序列输出。 题目分析:本题考察的是二叉树的链式存储结构的运用，二叉树由一个根与左右两个结点构成，因此一个结点可用三个域来组成，除了一个数据域，还有两个指针域，分别用来指向该结点左子结点和右子结点的存储地址，由此，便可以把一个一个的结点结合起来形成二叉树。当需要进行遍历时，只需按顺序访问结点并依次访问相应的左或右结点即可。 程序思路： 首先是对二叉树的定义，结构体中包含一个整形的数据以及该结构体的左右结点 指针，接着调用Create( )函数进行二叉树 的建立，该函数利用递归调用的原理，会让你从左结点开始不断输入左结点的左结点，以0为结束标志，然后输入最左的结点的右结点，由此依次返回根结点。接下来是先序遍历，从根节点开始，先输出左结点，再输出右结点。中序遍历先输出左结点，接着是根结点，然后是右结点。后序遍历先输出左结点，然后是右结点，最后输出根结点。 其中比较重要的三种遍历流程图如下：（使用流程图绘图软件绘制） 操作演示： 二叉树******************************* 欢迎使用二叉树，请输入你心目中的结点数据吧（0表示空结点哟^_^） 1 输入左结点 2 输入左结点 0 输入右结点 0 输入右结点 3 输入左结点 0 输入右结点 0 先序遍历二叉树元素为 1 2 3 中序遍历二叉树元素为 2 1 3 后序遍历二叉树元素为 2 3 1 源程序代码： 二叉树******************************* //031240117尚林伟 #include #define MAXNODE 100 typedef struct binode //定义二叉树的二叉链表 { int data; struct binode *lchild,*rchild; }BiTree; BiTree *Create( ) //建立一棵二叉树 { BiTree *bt; int ch; cin>>ch; if(ch==0) { bt=NULL; } else { bt=new binode[sizeof(binode)]; bt->data=ch; cout<<"输入左结点"< bt->lchild=Create(); cout<<"输入右结点"< bt->rchild=Create(); } return bt; }; void PreOrder(BiTree *bt) //先序遍历 { if(bt==NULL) return; cout< PreOrder(bt->lchild); PreOrder(bt->rchild); } void InOrder(BiTree *bt) //中序遍历 { if(bt==NULL) return; InOrder(bt->lchild); cout< InOrder(bt->rchild); } void PostOrder(BiTree *bt) //后序遍历 { if(bt==NULL) return; PostOrder(bt->lchild); PostOrder(bt->rchild); cout< } void main() //主函数 { BiTree *bt; cout<<"欢迎使用二叉树，请输入你心目中的结点数据吧（0表示空结点哟^_^）"< bt=Create(); cout<<"先序遍历二叉树元素为"< PreOrder(bt); cout< cout<<"中序遍历二叉树元素为"< InOrder(bt); cout< cout<<"后序遍历二叉树元素为"< PostOrder(bt); cout< } 实验三、图的邻接表和邻接矩阵数据结构的定义、创建；图的深度优先遍历、广度优先遍历。 题目分析：图是由非空的顶点和一个描 述顶点之间联系——边的集合组成。因此， 图应该用结构体来定义，在c++语言中，学 习了类的定义，如果用来做图，会变得很简 单。此题考察的主要是图的邻接矩阵以及邻 接表的基本操作。程序书上都有列举，但由 于我学的是c++,因此要看懂书上的程序有 一些困难，所以我上网搜索了一些资料，最 后决定用c++语言来做。 程序思路： 图的邻接表：首先需要对邻接表进行定 义，我并没有只用一个结构体，而是用了三 个来对邻接表中各数据进行了定义。由于邻 接表的储存方式需要用到队列，因此接下来 就是对队列的定义，仿照书上的程序完成了 对队列的定义后，接下来就是对图的创建， 再然后是两种遍历方式的代码。主函数开 始，先定义一个表G，然后调用void CreatAdjList（）函数创建邻接表，此函数会 要求用户依次输入顶点，边等信息，因为是 无向图，所以有两次建立边表的过程。接着 要求用户选择一个定点，接着从这个顶点开 始深度优先及广度优先遍历，并把结果显示 出来。 其中比较重要的创建，先序遍历，后序 遍历函数流程图如下：（使用流程图绘图软 件绘制） 图的邻接矩阵：对邻接矩阵的做法我参 考了网上查到的资料，决定用c++中的类来 做。首先定义一个图类，其中的元素除了顶 点和边的信息外，还有一个创建函数void creatadj()，这样用一个类就把邻接矩阵的定 义和创建都做好了。类定义以后，只需编辑 两个遍历函数即可。主函数开始，先调用创 建函数创建图，依然是让用户选择一个顶点 开始深度优先遍历，同时用了一个for循环 来进行多次遍历，每一个循环结束会询问用 户是否继续遍历，选否，则退出for循环。 广度优先遍历原理与深度优先遍历一样。 其中比较重要的先序遍历，后序遍历函 数流程图如下：（使用流程图绘图软件绘制） 操作演示： 邻接表*************************** 请输入顶点数和边数: 5 7 开始输入顶点表: 1 2 3 4 开始输入边表信息: 请输入边 1 请输入边 3 请输入边 4 请输入边 请输入边 请输入边 3 请输入边 2 请输入开始遍历的顶点:2 该图的深度优先遍历结果为: 2 1 0 3 4 该图的广度优先遍历结果为: 2 0 1 3 0 4 邻接矩阵************************* 请输入8个顶点信息 1 2 3 4 5 6 7 请输入第1条边，共15条边0 1 请输入第2条边，共15条边1 2 请输入第3条边，共15条边2 3 请输入第4条边，共15条边3 4 请输入第5条边，共15条边4 5 请输入第6条边，共15条边5 6 请输入第7条边，共15条边6 7 请输入第8条边，共15条边3 4 请输入第9条边，共15条边2 3 请输入第10条边，共15条边1 2 请输入第11条边，共15条边6 4 请输入第12条边，共15条边7 5 请输入第13条边，共15条边5 1 请输入第14条边，共15条边2 7 请输入第15条边，共15条边6 2 恭喜恭喜，图创建成功啦^_^ 0 1 0 0 1 0 0 0 1 0 1 0 0 1 1 0 0 1 0 1 0 0 0 0 0 0 1 0 1 1 0 0 1 0 0 1 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 请输入深度优先遍历开始访问的顶点 4 从4出发的深度优先遍历序列为 3 2 1 0 4 5 6 继续进行深度优先遍历吗（1/2）?2 请输入广度优先遍历开始访问的顶点 4 从4出发的广度优先遍历序列为 3 2 4 5 1 0 6 继续进行广度优先遍历吗（1/2）？2 源程序代码： 邻接表*************************** //031240117尚林伟 #include #define MaxVerNum 50 struct edgenode //图的邻接表的定义{ int endver; int inform; edgenode* edgenext; }; struct vexnode { char vertex; edgenode* edgelink; }; struct Graph { vexnode adjlists[MaxVerNum]; int vexnum; int arcnum; }; /*************************************/ struct QueueNode //队列的定义及相关函数的实现 { int nData; QueueNode* next; }; struct QueueList { QueueNode* front; QueueNode* rear; }; void EnQueue(QueueList* Q,int e) { QueueNode *q=new QueueNode; q->nData=e; q->next=NULL; if(Q==NULL) return; if(Q->rear==NULL) Q->front=Q->rear=q; else { Q->rear->next=q; Q->rear=Q->rear->next; } } void DeQueue(QueueList* Q,int* e) { if (Q==NULL) return; if (Q->front==Q->rear) { *e=Q->front->nData; Q->front=Q->rear=NULL; } else { *e=Q->front->nData; Q->front=Q->front->next; } } /***********************************/ void CreatAdjList(Graph* G) //图的邻接表的创建 { int i,j,k; edgenode* p1; edgenode* p2; cout<<"请输入顶点数和边数:"< cin>>G->vexnum>>G->arcnum; cout<<"开始输入顶点表:"< for (i=0;i { cin>>G->adjlists[i].vertex; G->adjlists[i].edgelink=NULL; } cout<<"开始输入边表信息:"< for (k=0;k { cout<<"请输入边 cin>>i>>j; p1=new edgenode; p1->endver=j; p1->edgenext=G->adjlists[i].edgelink; G->adjlists[i].edgelink=p1; p2=new edgenode; p2->endver=i; p2->edgenext=G->adjlists[j].edgelink; G->adjlists[j].edgelink=p2; } } //-----------------------深度优先遍历 void DFS(Graph *G,int i,int visit[]) { cout< visit[i]=1; edgenode *p=new edgenode; p=G->adjlists[i].edgelink; if(G->adjlists[i].edgelink&&!visit[p->e ndver]) { DFS(G,p->endver,visit); } } void DFStraversal(Graph *G,char c) { cout<<"该图的深度优先遍历结果为:"< int visit[MaxVerNum]; for(int i=0;i { visit[i]=0; } int m; for (i=0;i { if (G->adjlists[i].vertex==c) { m=i; DFS(G,i,visit); break; } } for(i=0;i { if(visit[i]==0) DFS(G,i,visit); } cout< } //--------------------广度优先遍历 void BFS(Graph* G,int v,int visit[]) { QueueList *Q=new QueueList; Q->front=Q->rear=NULL; EnQueue(Q,v); while(Q->rear!=NULL) { int e=0; DeQueue(Q,&e); cout< visit[e]=1; edgenode* p=new edgenode; p=G->adjlists[e].edgelink; if(p) { int m=p->endver; if(m==0) { EnQueue(Q,m); while(visit[m]==0) { p=p->edgenext; if(p==NULL) break; m=p->endver; EnQueue(Q,m); } } } } } void BFStraversal(Graph *G,char c) { cout<<"该图的广度优先遍历结果为:"< int visited[MaxVerNum]; for (int i=0;i { visited[i]=0; } int m; for (i=0;i { if (G->adjlists[i].vertex==c) { m=i; BFS(G,i,visited); break; } } for(i=0;i { if(visited[i]==0) BFS(G,i,visited); } cout< } void main() //主函数 { Graph * G=new Graph; CreatAdjList(G); char ch; cout<<"请输入开始遍历的顶点:"; cin>>ch; DFStraversal(G,ch); BFStraversal(G,ch); } 邻接矩阵************************* //031240117尚林伟 #include const int n=8; const int e=15; #define elemtype int bool visited[n+1]; class graph//图的邻接矩阵的定义及创建 { public: elemtype v[n+1]; int arcs[n+1][n+1]; void creatadj() { int i,j,k; cout<<"请输入"< for (k=1;k<=n;k++) cin>>v[k]; for(i=1;i<=n; i++) for(j=1;j<=n;j++) arcs[i][j]=0; for(k=1;k<=e;k++) { cout<<"请输入第"< cin>>i>>j; cout< arcs[i][j]=1; arcs[j][i]=1; } } void dfs(int i) //深度优先遍历 { int j; cout< visited[i]=true; for(j=1;j<=n;j++) if((arcs[i][j]==1)&&(!visited[j])) dfs(j); } void bfs(int i) //广度优先遍历 { int q[n+1]; int f,r,j; f=r=0; cout< visited[i]=true; r++;q[r]=i; while(f { f++;i=q[f]; for(j=1;j<=n;j++) if((arcs[i][j]==1)&&(!visited[j])) { cout< visited[j]=true; r++;q[r]=j; } } } }; void main() //主函数 { int i,j;graph g; int yn=1; g.creatadj(); cout<<"恭喜恭喜，图创建成功啦^_^"< { for(j=1;j<=n;j++) cout< cout< } while(yn==1) { for(i=1;i<=n;i++) visited[i]=false; cout<<"请输入深度优先遍历开始访问 的顶点"; cin>>i; cout< cout<<"从"< 序列为"< g.dfs(i); cout< 吗（1/2）?"; cin>>yn; } yn=1; while(yn==1) { for(i=1;i<=n;i++) visited[i]=false; cout<<"请输入广度优先遍历开始访问 的顶点"; cin>>i; cout< cout<<"从"< 序列为"< g.bfs(i); cout< 吗（1/2）？"; cin>>yn; } } 三、实验总结 通过此次数据结构上机实验，我对顺序表，链表，树，二叉树，队列及图的两种储存方式都有了较为深刻的认识。只不过之前学习的是c++，某些语句与c语言不同，所以最开始遇到了一些困难，上网查阅资料对比了c++以及c语言的特点以后，已经基本解决了这个问题。由于偏爱c++语言，再加上建立的文件也是cpp格式，所以索性所有的程序都改为用c++语言来做。前面的还好，做到图的那一部分，发现书上的语句有一些错误，编译不能通过，所以我上网查阅了别人用c++语言做的程序，并参考他们的做法编写了图的邻接表程序。偶然浏览到一篇博客，是关于用c++语言中的类来做图的邻接矩阵的，觉得用类来定义不仅代码简单而且易懂，所以我仿照别人的做法编写了图的邻接矩阵的程序代码。 由于在之前上过全国的c++辅导课，对树，队列，以及栈都有一定认识。这次试验在巩固的基础上加深了对这些知识的认识，相信对我以后的学习生活也有很大益处。 数据结构上机实验报告 学院：电子工程学院 专业：信息对抗技术 姓名： 学号： 教师：饶鲜日期： 目录 实验一线性表................................................. - 4 - 一、实验目的................................................ - 4 - 二、实验代码................................................ - 4 - 三、实验结果............................................... - 14 - 四、个人思路............................................... - 15 -实验二栈和队列.............................................. - 15 - 一、实验目的............................................... - 15 - 二、实验代码............................................... - 16 - 三、实验结果............................................... - 24 - 四、个人思路............................................... - 25 -实验三数组.................................................. - 26 - 一、实验目的............................................... - 26 - 二、实验代码............................................... - 26 - 三、实验结果............................................... - 28 - 四、个人思路............................................... - 28 -实验四树.................................................... - 29 - 一、实验目的............................................... - 29 - 二、实验代码............................................... - 29 - 《数据结构课程实验》大纲 一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： （1）内容丰富，学习量大，给学习带来困难； （2）贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点； （3）所用到的技术多，而在此之前的各门课程中所介绍的专业性知识又不多，因而加大了学习难度； （4）隐含在各部分的技术和方法丰富，也是学习的重点和难点。 根据《数据结构课程》课程本身的技术特性，设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练，突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为18。 二、《数据结构课程实验》的目的和要求 不少学生在解答习题尤其是算法设计题时，觉得无从下手，做起来特别费劲。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。 为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术，与特定问题相关的技术等，要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上，掌握分析、解决实际问题的能力。 三、《数据结构课程实验》内容 课程实验共18学时，要求完成以下六个题目： 实习一约瑟夫环问题（2学时） 《数据结构实验指导书》答案 实验一： 1、请编写函数int fun(int *a, int *b),函数的功能是判断两个指针a和b所指存储单 元的值的符号是否相同；若相同函数返回1，否则返回0。这两个存储单元中的值都不为0。在主函数中输入2个整数、调用函数fun、输出结果。 #include 数fun、输出结果。 #define N 10 #include 华农数据结构上机实验答案 数据结构上机答案 1.1顺序线性表的基本操作 #include { newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*size of(ElemType)); L.elem=newbase; L.listsize+=LISTINCREMENT; } q=&(L.elem[i-1]); for(p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p; *q=e; ++L.length; return OK; } int ListDelete_Sq(SqList &L,int i,int &e) { ElemType *q,*p; if(i<1||i>L.length) return ERROR; p=&(L.elem[i-1]); e=*p; q=L.elem+L.length-1; for(++p;p<=q;p++) *(p-1)=*p; L.length--; return OK; } int main() { SqList T; int a,i; ElemType e,x; if(InitList_Sq(T)) { printf("A Sequence List Has Created.\n"); } while(1) { printf("1:Insert element\n2:Delete element\n3:Load all elements\n0:Exit\nPlease choose:\n"); scanf("%d",&a); switch(a) 数据结构实验报告全集 实验一线性表基本操作和简单程序 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）熟练掌握线性表的两种存储方式 （2）掌握链表的操作和应用。 （3）掌握指针、结构体的应用 （4）按照不同的学校，不同项目和不同的名次要求，产生各学校的成绩单、团体总分报表。 二、实验内容： 【问题描述】 参加运动会的n个学校编号为1~n。比赛分成m个男子项目和w个女子项目，项目编号分别为1~m和m＋1~m＋w。由于各项目参加人数差别较大，有些项目取前五名，得分顺序为7，5，3，2，1；还有些项目只取前三名，得分顺序为5，3，2。写一个统计程序产生各种成绩单和得分报表。 【基本要求】 产生各学校的成绩单，内容包括各校所取得的每项成绩的项目号、名次（成绩）、姓名和得分；产生团体总分报表，内容包括校号、男子团体总分、女子团体总分和团体总分。 【测试数据】 对于n＝4，m＝3，w＝2，编号为奇数的项目取前五名，编号为偶数的项目取前三名，设计一组实例数据。 【实现提示】 可以假设m≤20，m≤30，w≤20，姓名长度不超过20个字符。每个项目结束时，将其编号、类型符（区分取前五名还是前三名）输入，并按名次顺序输入运动员姓名、校名（和成绩）。 【选作内容】 允许用户指定某些项目可采取其他名次取法。 实验二停车场管理 一、实验目的： （1）熟练掌握栈顺存和链存两种存储方式。 （2）掌握栈的基本操作及应用。 （3）以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。 二、实验内容： 【问题描述】 设停车场是一个可停放n辆汽车的长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车信放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场院，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。 【基本要求】 以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。 【测试数据】 设n=2，输入数据为：(A，1，5)，（A，1，15），（A，3，20），（A，4，25），（A，5，30），（D，2，35），（D，4，40），（E，0，0）。其中：A表示到达（Arrival）；D表示离去（Departure）；E表示输入结束（End）。 【实现提示】 需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。 【选作内容】 （1）两个栈共享空间，思考应开辟数组的空间是多少？ （2）汽车可有不同种类，则他们的占地面积不同收费标准也不同，如1辆客车和1.5辆小汽车的占地面积相同，1辆十轮卡车占地面积相当于3辆小汽车的占地面积。（3）汽车可以直接从便道开走，此时排在它前面的汽车要先开走让路，然后再依次排到队尾。 （4）停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请思考如何修改结构以满足这种要求。 数据结构实验报告 一．顺序表 要求：实现顺序表的初始化、在指定位置插入和删除元素。 算法思路：线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。顺序表的初始化操作就是为顺序表分配一个预定义大小的空间，并将线性表的当前长度设为“0”。线性表的插入操作是在线性表的第i-1个数据元素和第i个元素之间插入新的数据元素，使得长度为n的线性表变成长度为n+1的线性表，而删除恰好相反长度变为n-1的线性表，而且删除点后面的元素要往前移动一个位。 程序代码： #include for(i=0;i 数据结构基础及深入及考试 复习资料 习题及实验参考答案见附录 结论 1、数据的逻辑结构是指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。 2、数据的物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。存储结构可分为4大类：顺序、链式、索引、散列 3、抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）。它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。 4、算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。 5、在数据结构中，从逻辑上可以把数据结构分成（ C ） A、动态结构和表态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 6、算法的时间复杂度取决于（ A ） A、问题的规模 B、待处理数据的初态 C、问题的规模和待处理数据的初态 线性表 1、线性表的存储结构包括顺序存储结构和链式存储结构两种。 2、表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（ E ），删除一个元素需要移动的元素的个数为（ A ）。 A、(n-1)/2 B、n C、n+1 D、n-1 E、n/2 F、(n+1)/2 G、(n-2)/2 3、“线性表的逻辑顺序与存储顺序总是一致的。”这个结论是（ B ） A、正确的 B、错误的 C、不一定，与具体的结构有关 4、线性表采用链式存储结构时，要求内存中可用存储单元的地址（ D ） A、必须是连续的 B、部分地址必须是连续的C一定是不连续的D连续或不连续都可以 5、带头结点的单链表为空的判定条件是（ B ） A、head==NULL B、head->next==NULL C、head->next=head D、head!=NULL 6、不带头结点的单链表head为空的判定条件是（ A ） A、head==NULL B、head->next==NULL C、head->next=head D、head!=NULL 7、非空的循环单链表head的尾结点P满足（ C ） A、p->next==NULL B、p==NULL C、p->next==head D、p==head 8、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（ B ） A、O(1) B、O(n) C、O(n2) D、O(nlog2n) 9、在一个单链表中，若删除p所指结点的后继结点，则执行（ A ） 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 《数据结构与算法》课程实验内容与要求 一、课程简介 本课程着重讲述①线性结构、树型结构、图等典型数据结构的逻辑特点、存储结构及其相应的基本算法。②各种查找算法③典型内部排序算法。 二、实验的作用、地位和目的 数据结构是一门技术基础课，通过实验深刻理解各种逻辑结构、存储结构的特性，培养为实际问题分析其数据对象、基本操作，选择逻辑结构、存储结构灵活应用基本算法，设计出具有专业水准的应用程序的能力。 三、实验方式与要求 ①首先要求学生在课下完成问题分析、算法设计，基本完成程序设计。 ②实验时，每位学生使用一台微机，独立调试，完成程序。 ③程序调试好后，由指导教师检测运行结果，并要求学生回答相关的问题。教师评出检查成绩。 ④学生记录程序的输入数据，运行结果及源程序。 ⑤在一周内完成实验报告。 四、考核方式与实验报告要求 实验成绩由指导教师根据学生的实验完成情况、源程序质量、回答问题情况、实验报告质量、实验纪律等方面给分。 学生在实验后的一周内提交实验报告。实验报告按照首页附件中实验报告模版书写。实验报告中应包括如下内容： ?实验内容按任课教师下达的实验任务填写（具体实验题目和要求）； ?实验过程与实验结果应包括如下主要内容： 算法设计思路简介 算法描述：可以用自然语言、伪代码或流程图等方式 算法的实现和测试结果：包括算法运行时的输入、输出，实验中出现的问题及解决办法等 ?源程序清单与实验结果或其它说明可打印，并装订在实验报告首页之后。 ?实验报告雷同者，本次实验成绩为0分或雷同实验报告平分得分 五、实验的软硬件环境 硬件环境：PⅡ以上微型计算机 软件环境：Windows98/2000, VC++6.0或turbo C 六、实验内容安排 实验一线性表应用 实验时间：2016年3月14日1-4节（地点：7-215） 实验目的：理解线性表的逻辑特点；掌握顺序表、链表存储结构，以及线性表的基本操作，如插入、删除、查找，以及线性表合并等操作在顺序存储结构和链式存储结构上的实现算法，并能够在实际问题背景下的灵活运用线性表来解决问题，实现相应算法。 具体实验题目与要求：（任课教师根据实验大纲自己指定） 每位同学可从下面题目中选择1-2题实现： 1．一元稀疏多项式简单的计算器 1）问题描述：用线性表表示一元稀疏多项式，设计一个一元多项式运算器 2）要求: （1）采用单链表存储结构一元稀疏多项式 （2）输入并建立多项式 （3）输出多项式 （4）实现多项式加、减运算 2．单链表基本操作练习 1）问题描述：在主程序中提供下列菜单： 1…建立链表 2…连接链表 3…输出链表 0…结束 2）实验要求：算法中包含下列过程，分别完成相应的功能： CreateLinklist(): 从键盘输入数据，创建单链表 ContLinklist()：将前面建立的两个单链表首尾相连 OutputLinklist()：输出显示单链表 3．约瑟夫环问题 1）问题描述：有编号为1, 2…n 的n 个人按顺时针方向围坐一圈，每人持有一个正整数密码。开始给定一个正整数m，从第一个人按顺时针方向自1开始报数，报到m者出列，不再参加报数，这时将出列者的密码作为m，从出列者顺时针方向的下一人开始重新自1开始报数。如此下去，直到所有人都出列。试设计算法，输出出列者的序列。 2）要求: 采用顺序和链式两种存储结构实现 实验报告格式及要求：按附件中实验报告模版书写。（具体要求见四） 实习一： 1、编写一个读入一个字符串，把它存入一个链表，并按相反的次序打印的程序。 2、设有一个单位的人员工资有如下信息：name、department、 base pay、allowance、total。现从键盘输入一组人员工资数据并将它们存储到名为paydata的文件中；再从paydata取出工资数据并给每个人的base pay增加100元，增加后将工资数据显示于屏幕(每行1人)。请编写能够完成上述工作的程序。 代码如下： 1.#include 《数据结构》课程上机实验指导书 实验一 【实验名称】顺序表的基本算法 【实验目的】 创建一个顺序表，掌握线性表顺序存储的特点。设计和验证顺序表的查找、插入、删除算法。 【实验要求】 （1）从键盘读入一组整数，按输入顺序形成顺序表。并将创建好的顺序表元素依次打印在屏幕上。 设计一个带选择菜单的主函数，菜单中具备任意选择删除、插入、查找数据元素（2）的功能。 当选择删除功能时，从键盘读入欲删除的元素位置或元素值，按指定方式删除；3（）当选择插入功能时，从键盘读入新元素值和被插入位置，在指定位置插入；当选择查找功能时，从键盘读入欲查找的元素值，返回其位置序号。 （4）每种操作结束后，都能在屏幕上打印出此时顺序表元素的遍历结果。 【实验步骤】、实验前先写好算法。1 上机编写程序。2、编译。3、调试。4、 综合实例！，2-62-8！带菜单的主函数参考书上2.5，，，书上参考算法例程：2-12-42-5注意：顺序表的结构体！typedef struct { datatype items[listsize]; int length; }SpList; 实验二 【实验名称】单链表的基本算法 【实验目的】 创建一个单链表，掌握线性表链式存储的特点。设计和验证链表的查找、插入、删除、求表长的算法。【实验要求】 （1）从键盘读入一组整数，按输入顺序形成单链表。并将创建好的单链表元素依次打印在屏幕上。（注意：选择头插法或者尾插法！） 设计一个带选择功能菜单的主函数，菜单中至少具备任意选择删除、插入、查找（2）数据元素，和求单链表表长等几项功能。 当选择删除功能时，从键盘读入欲删除的元素位置，按指定位置删除；当选择插）（3入功能时，从键盘读入新元素值和被插入位置，在指定位置插入；当选择查找功能时，从键盘读入欲查找的元素值，返回其位置序号；当选择求表长功能时，返回该单链表表长的数值。 （4）每种操作结束后，都能在屏幕上打印出此时单链表元素的遍历结果。 【实验步骤】、实验前先写好算法。1 、上机编写程序。2 编译。3、调试。4、 综合实例！！带菜单的主函数参考书上，2-132-15，2-172.5，，书上参考算法例程：2-102-12 另外，注意，指针的初始化！指针的操作必须谨慎！链表的结构体如下：typedef struct Node { Datatype ch; struct Node *next; }LNode, *Pnode, *Linklist; 实验三 【实验题】 1．狐狸逮兔子 围绕着山顶有10个圆形排列的洞，狐狸要吃兔子，兔子说：“可以，但必须找到我，我就藏身于这十个洞中，你先到１号洞找，第二次隔１个洞（即3号洞）找，第三次隔２个洞（即6号洞）找，以后如此类推，次数不限。”但狐狸从早到晚进进出出了1000次，仍没有找到兔子。问兔子究竟藏在哪个洞里？ （提示：这实际上是一个反复查找线性表的过程。） 【数据描述】 定义一个顺序表，用具有10个元素顺序表来表示这10个洞。每个元素分别表示围着山顶的一个洞，下标为洞的编号。 #define LIST_INIT_SIZE 10 //线性表存储空间的初始分配量 typedef struct { ElemType *elem; //存储空间基址 int length; //当前长度 int listsize; //当前分配的存储容量（以sizeof(ElemType)为单位） }SqList; 【算法描述】 status InitList_Sq(SqList &L) { //构造一个线性表L L.elem=(ElemType )malloc(LIST_INIT_SIZE*sizeof(ElemType)); If(!L.elem) return OVERFLOW; //存储分配失败 L.length=0; //空表长度为0 L.listsize=LIST_INIT_SIZE; //初始存储容量 return OK; } //InitList_Sq status Rabbit(SqList &L) { //构造狐狸逮兔子函数 int current=0; //定义一个当前洞口号的记数器，初始位置为第一个洞口 for(i=0;i 习题二 ⒉１描述以下四个概念的区别：头指针变量，头指针，头结点，首结点（第一个结点）。解：头指针变量和头指针是指向链表中第一个结点（头结点或首结点）的指针；在首结点之前附设一个结点称为头结点；首结点是指链表中存储线性表中第一个数据元素的结点。若单链表中附设头结点，则不管线性表是否为空，头指针均不为空，否则表示空表的链表的头指针为空。 2.2简述线性表的两种存储结构有哪些主要优缺点及各自使用的场合。 解：顺序存储是按索引直接存储数据元素，方便灵活，效率高，但插入、删除操作将引起元素移动，降低了效率；而链式存储的元素存储采用动态分配，利用率高，但须增设表示结点之间有序关系的指针域，存取数据元素不如顺序存储方便，但结点的插入和删除十分简单。顺序存储适用于线性表中元素数量基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素的情况；而链式存储适用于频繁进行元素动态插入或删除操作的场合。 2.3 在头结点为h的单链表中，把值为b的结点s插入到值为a的结点之前，若不存在a，就把结点s插入到表尾。 Void insert(Lnode *h,int a,int b) {Lnode *p,*q,*s; s=(Lnode*)malloc(sizeof(Lnode)); s->data=b; p=h->next; while(p->data!=a&&p->next!=NULL) {q=p; p=p->next; } if (p->data==a) {q->next=s; s->next=p;} else {p->next=s; s->next=NULL; } } 2.4 设计一个算法将一个带头结点的单链表A分解成两个带头结点的单链表A和B，使A中含有原链表中序号为奇数的元素，而B中含有原链表中序号为偶数的元素，并且保持元素原有的相对顺序。 Lnode *cf(Lnode *ha) {Lnode *p,*q,*s,*hb; int t; p=ha->next; q=ha; t=0; hb=(Lnode*)malloc(sizeof(Lnode)); s=hb; while(p->next!=NULL) {if (t==0) {q=p;p=p->next;t=1;} else {q->next=p->next; p->next=s->next; s->next=p; s=p; p=p->next; t=0; } } s->next=NULL; return (hb); } 2013-03-08 上机实验题 1.构建两个顺序表示的非空线性表LA和LB (数据元素为整型，其值自行确定)； 2.从线性表LA中删除第i 个元素； 3.将元素e插入到线性表LB中的第i个元素之后； 4.假设LA中不含重复的元素 (LB同)，将线性表LA和LB合并，并输出结果，要求结 果中不含重复的元素。 //构建两个顺序表（定义、初始化） //在一个顺序表中删除指定位置的元素 //在一个顺序表中指定位置插入一个新元素 //将两个线性表LA和LB进行合并 //遍历LB, 如果其中的数据元素不在LA中，则将其插入LA，否则不予处理 //打印线性表LA #define List_Init_Size 100 #define LISTINCREMENT 10 typedef int Status; typedef struct { int * elem; int length; // 当前长度 int ListSize; // 当前分配的存储容量 }SqList; Status Initialize_table (SqList &L) {// 初始化线性表 int i, m, data; L.elem=(int *)malloc(List_Init_Size *sizeof(int)); if (!L.elem) { // 为线性表分配空间 printf("Overflow"); return FAILURE; } L.ListSize=List_Init_Size; L.length=0; printf ("Please input the size of linear table (<=%d): "+ List_Init_Size); scanf_s("%d",&m); for (i=0;i数据结构上机实验报告
数据结构实验报告格式
数据结构上机实验答案
华农数据结构上机实验答案
数据结构实验报告全集
数据结构实验报告
数据结构课程设计题目及要求
数据结构上机实验报告
数据结构(第4版)习题及实验参考答案数据结构复习资料完整版(c语言版)
数据结构实验报告模板
《数据结构与算法》上机实验要求
数据结构上机答案(c语言版)
数据结构上机实验指导
数据结构实验题参考答案
数据结构上机例题及答案
数据结构 上机实验题及题解