《数据结构实验指导书(自动化tongxin).doc》由会员分享，可在线阅读，更多相关《数据结构实验指导书(自动化tongxin).doc（22页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构实 验 指 导 书 适用专业：自动化、电子、通信等目 次前 言3实验一 线性表的操作5实验二 栈和队列的操作13实验三 图算法18实验四 排序选择20前 言数据结构是计算机及相关专业的一门核心基础课程，也是很多高校考研专业课之一。它主要介绍线性结构、树结构、图结构三种逻辑结构元素的存储实现，在此基础上介绍一些典型算法及时、空效率分析。这门课程的主要任务是培养学生的算法设计能力及良好的程序设计习惯。通过学习，要求学生能够掌握典型算法的设计思想及程序实现，能够根据实际问题选取合适的存储方案，设计出简洁、高效、实用的算法，为后续课程的学习及软件开发打下良好的基础。学习这门课程，习题和实验是两
2、个关键环节。学生理解算法，上机实验是最佳的途径之一。因此，实验环节的好坏是学生能否学好数据结构的关键。为了更好地配合学生实验，特编写试验指导书。希望同学们在使用本实验指导书及进行实验的过程中，能够帮助我们不断地发现问题，并提出建议，使数据结构成为具有省内一流水平的课程。一、实验目的 更好的理解算法的思想、培养编程能力。二、实验要求1、 每次实验前学生必须根据试验内容认真准备实验程序及调试时所需的输入数据。 2、在指导教师的帮助下能够完成实验内容，得出正确的实验结果。 3、实验结束后总结实验内容、书写实验报告。 4、遵守实验室规章制度、不缺席、按时上、下机。 5、实验学时内必须做数据结构的有关内
3、容，不允许上网聊天或玩游戏，如发现上述现象，取消本次上机资格，平时成绩扣10分。三、实验环境 VC+6.0四、说明 1、本实验的所有算法中元素类型可以根据实际需要选择。 2、实验题目中带者为较高要求，学生可自选；其余部分为基本内容，应尽量完成（至少完成70%，否则实验不合格）。 3、数据结构是很多高校的硕士研究生入学考试的专业课之一，希望有志于考研的学生能够在学习过程中注意各种算法的理解，以便为考研做一定的准备。五、实验报告的书写要求 1明确实验的目的及要求； 2记录实验的输入数据和输出结果； 3说明实验中出现的问题和解决过程； 4写出实验的体会和实验过程中没能解决的问题；六、参考书目 数据结
4、构-C语言描述-耿国华等 高等教育出版社DATA STRUCTURE WITH C+ William Ford,William Topp清华大学出版社（影印版）数据结构（C语言描述） 严蔚敏 清华大学出版社实验一 线性表的操作实验类型：验证性 实验要求：必修实验学时： 2学时一、实验目的参照给定的顺序表和链表的程序样例，验证给出的线性表的常见算法线性表理解。二、实验要求1掌握顺序表和链表的特点。掌握线性表的常见算法。2提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。三、实验内容1.设计一个静态数组存储结构的顺序表，要求编程实现如
5、下任务：建立一个线性表，首先依次输人数据元素1，2，3，10，然后删除数据元素6，最后依次显示当前线性表中的数据元素。要求采用顺序表实现，假设该顺序表的数据元素个数在最坏情况下不会超过50个。2. 设计一个带头结点的单链表，要求：(1)生成一个整数线性表，实现将其分解成两个链表，其中一个全部为奇数，另一个全部为偶数（尽量利用已知的存储空间）。(2)设计一个测试主函数，实际运行验证所设计单链表类的正确性。3.设计一个带头结点的循环链表，要求： (1)带头结点循环单链表的函数包括：取数据元素个数、插入、删除、取数据元素. (2)设计一个测试主函数，实际运行验证所设计循环单链表的正确性.*4.设计一
6、个单链表实现一元多项式求和问题。要求： （1）设计存储结构表示一元多项式； （2）设计算法实现一元多项式相加。 四、程序样例1#includeconst int MaxSize=50;typedef int datatype;typedef struct datatype dataMaxSize;int length;SeqList;void init(SeqList &L)L.length=0; void Insert(SeqList &L, int i, datatype x) int j; if (L.length=MaxSize) throw 溢出; if (iL.length+1)
7、throw 位置不合法; for (j=L.length; j=i; j-) L.dataj=L.dataj-1; /注意第j个元素存在数组下标为j-1处 L.datai-1=x; L.length+;datatype Delete(SeqList &L,int i) int j;datatype x; if (L.length=0) cout上溢; if (iL.length) cout位置不合法; x=L.datai-1; for (j=i; jL.length; j+) L.dataj-1=L.dataj; /注意第j个元素存在数组下标为j-1处 L.length-; return x;
8、void PrintList(SeqList &L)for(int i=0;iL.length;i+)coutL.dataiendl;void main()SeqList L;init(L);for(int i=1;i=10;i+)Insert(L,i,i);PrintList(L);2#include#includetypedef int datatype;typedef struct Node datatype data; struct Node *next; LNode,*Linklist;/*Linklist initlist()LNode * first;first=new LNod
9、e; first-next=NULL; return first;*/Linklist Creat_LinkList1() LNode *first;first=new LNode; first-next=NULL; /*空表*/LNode *s; datatype x; /*设数据元素的类型为int*/int n,i=0;cout输入n值 n;while (ix; s=new LNode; s-data=x; s-next=first-next; first-next=s;i+; return first;void Insert(LNode *first, int i,datatype x)
10、LNode *p,*s;p=first;int j=0;while(p&jnext;j+;if(!p) coutdata=x; s-next=p-next; /*新结点插入在第i-1个结点的后面*/ p-next=s;datatype Delete(LNode *first, datatype x)LNode *p,*q;p=first;q=p-next;while(q&q-data!=x)p=q;q=q-next;if(!q) coutdata; p-next=q-next; /*新结点插入在第i-1个结点的后面*/ delete q; return x;void huafen(Linkli
11、st &first,Linklist &first1)LNode *p,*q,*r;p=first;q=first-next;r=first1;while(p-next!=NULL)if(q-data)%2!=0)p=q;q=q-next;elsep-next=q-next;r-next=q;r=q;q=p-next;void print(Linklist &first)LNode *p;p=first-next;while(p)cout data; p=p-next;void main()Linklist A,B;B=new LNode; B-next=NULL;A=Creat_LinkLi
12、st1();print(A);coutendl;coutthe huafen result;huafen(A,B);print(A);coutendl;print(B);coutendl;3#include#includetypedef int datatype;typedef struct Node datatype data; struct Node *next; LNode,*CList;void initCList(CList &first)first=new LNode; first-next=first; /建立只有头结点的空链表 datatype Get(CList first,
13、int i) LNode *p;int j; p=first-next; j=1; /或p=first; j=0; while (p & jnext; /工作指针p后移 j+; if (!p) coutdata; void Insert(CList &first, int i, datatype x) LNode *p,*s;int j; p=first ; j=0; /工作指针p初始化while (p & jnext; /工作指针p后移j+;if (!p) coutdata=x; /向内存申请一个结点s，其数据域为xs-next=p-next; /将结点s插入到结点p之后p-next=s;
14、datatype Delete(CList &first,int i) LNode *p,*q;int j;datatype x;p=first ; j=0; /工作指针p初始化 while (p & jnext; j+; if (!p| !p-next) coutnext; x=q-data; /暂存被删结点 p-next=q-next; /摘链 delete q; return x; int count(CList first) LNode *p;int j; p=first; j=0; while (p-next!=first) p=p-next; /工作指针p后移 j+; return
15、 j; void CreateCList( CList &first,datatype a, int n) LNode *s; int i=n-1;first=new LNode; first-next=first; /初始化一个空链表 /for (int i=n-1; i=0; i-) while(i=0) s=new LNode; s-data=ai; /为每个数组元素建立一个结点 s-next=first-next; /插入到头结点之后 first-next=s;i-; void print(CList &first)LNode *p;p=first-next;while(p-next!
16、=first)coutdatanext; coutdata ; void main() CList C; int a6=15,12,54,65,9,23;int x,i,j;CreateCList(C,a,6);print(C);coutendl;j=count(C);coutjendl;cout输入x值插入的位置ixi;Insert(C,i,x); print(C);说明： 1算法的定义可以以头文件的方式存储,主函数实现该头文件的包含即可调用 2. 静态数组存储结构的顺序表定义，要求表中元素的最大个数 可以使用#define MAXSIZE 50 3程序的编写可以使用C+语言中类的形式如顺序
17、表Const int MAXSIZE=50;typedef int DataType；class SeqList protected： DataType listMAXSIZE； /静态数组定义 int size；/当前元素个数 public： SeqList(int max=0)；/构造函数 -SeqList(void)；/析构函数 int Size(void)const；/取当前数据元素个数 void Insert（coast DataType& item, int i）；/插入 DataType Delete（const int i ）；/删除 DataType GetData（int
18、i）const；/取数据元素 ； 4. 单链表是由一个一个的结点组成的，因此，要定义和实现单链表，必须先定义结点。 实验二 栈和队列的操作实验类型：验证性 实验要求：必修实验学时： 2学时一、实验目的 1掌握栈的存储特点及基本操作的实现。 2掌握队列的基本算法及其应用算法的程序实现。 3. 了解串的存储特点及基本操作的实现。二、实验要求1掌握栈、队列及串的特点及实现。2提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。三、实验内容 1. 堆栈测试和应用问题。要求： 设计一个主函数实现对顺序栈相关算法进行测试。测试方法为：依次把数据
19、元素1,2,3,4,5入栈，然后弹出栈中的数据元素并在屏幕上显示。2.链式队列测试和应用问题.要求： 设计一个链式队列代码.测试方法为：依次把数据元素1,2,3,4,5入对列，然后出队列中的数据元素并在屏幕上显示.*3.编写判断一个字符序列是否是回文的函数，要求使用栈和队列.4设计串采用顺序存储结构，一个姓名用串来表示，编写函数实现姓名的逆置。如white John变成John white.*5. 设计一个带头结点的循环单链表类，实现约瑟夫环问题；问题描述：设编号为1,2,，n(n0)个人按顺时针方向围坐-圈，每人持有一个正整数密码。开始时任意给出一个报数上限值m从第一个人开始顺时针方向自1起
20、顺序报数。报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新自1起顺序报数.如此下去，直到所有人全部出列为止。要求设计一个程序模拟此过程，并给出出列人的编号序列。 测试数据： n=7,7个人的密码依次为3,1,7,2,4,8,4 初始报数上限值m=20 四、程序样例1#include#includetypedef int datatype; const int MAXSIZE=50; typedef struct datatype dataMAXSIZE; int top; SeqStack; void Init_SeqStack(SeqStack &s
21、)s.top= -1; int Empty_SeqStack(SeqStack &s) if (s.top= -1) return 1; else return 0;void Push_SeqStack (SeqStack &s, datatype x) if (s.top=MAXSIZE-1) cout栈满endl; /*栈满不能入栈*/ else s.top+; s.datas.top=x; void Pop_SeqStack(SeqStack &s, datatype &x) if (Empty_SeqStack ( s ) ) cout栈空endl; /*栈空不能出栈 */ else
22、x=s.datas.top; s.top-; /*栈顶元素存入*x，返回*/ datatype Top_SeqStack(SeqStack s) if ( Empty_SeqStack ( s ) ) cout栈空endl; /*栈空*/ else return (s.datas.top ); void main() SeqStack s;int x,i;Init_SeqStack(s);for( i=1;i=10;i+)Push_SeqStack(s,i);/coutTop_SeqStack(s)endl;for( i=1;i=10;i+)Pop_SeqStack(s,x);cout xen
23、dl; 2 #include#includetypedef int datatype;typedef struct node datatype data; struct node *next; QNode; /*链队结点的类型*/typedef struct QNode *front,*rear; LQueue; void Init_LQueue(LQueue &q) QNode *p; /*申请头尾指针结点*/ p=new QNode; /*申请链队头结点*/ p-next=NULL; q.front=q.rear=p; void In_LQueue(LQueue &q , datatype
24、 x) QNode *p;p=new QNode; /*申请新结点*/ p-data=x; p-next=NULL; q.rear-next=p; q.rear=p; int Empty_LQueue( LQueue q) if (q.front=q.rear) return 1; else return 0; int Out_LQueue(LQueue &q , datatype &x) QNode *p;if (Empty_LQueue(q) ) cout队空next; q.front-next=p-next; x=p-data;/*队头元素放x中*/ delete p; if (q.fr
25、ont-next=NULL) q.rear=q.front; return 1; void main()LQueue q;Init_LQueue(q);int i,x;for(i=1;i10;i+)In_LQueue(q,i);coutEmpty_LQueue(q)endl;Out_LQueue(q,x); Out_LQueue(q,x);cout xendl;3 void main()LQueue q;SeqStack s;Init_LQueue(q);Init_SeqStack(s);int i,flag=1;char a5=abba;char x,y;i=0;while(i4)/for(
26、i=1;i10;i+)In_LQueue(q,ai);Push_SeqStack(s,ai);i+;while(!Empty_LQueue(q)Out_LQueue(q,x); Pop_SeqStack(s,y);if(x!=y)flag=0;if(!flag) cout不是回文endl;else cout是回文 endl;4#include #include void ReverseName(char *name, char *newName)char *p;p = strchr(name, );/p指在空格 位置*p = 0;/把空格换为0，因此name的长度只包括名部分strcpy(ne
27、wName, p+1);/指针p+1指示的是原姓名串name的姓部分strcat(newName, ,);/新姓名串newName等于姓+逗号strcat(newName, name);/新姓名串newName等于姓+逗号+名*p = ;/恢复原姓名串name为开始时的状态void main(void)char name = William Topp, newName30;ReverseName(name, newName);cout Name: name endl;cout ReverseName: newName endl;注意问题1重点理解栈、队列和串的算法思想，能够根据实际情况选择合适
28、的存储结构。 2栈、队列的算法是后续实验的基础（树、图、查找、排序等）。实验三 图算法实验类型：验证性 实验要求：必修实验学时： 2学时一、实验目的参照给定的图类的程序样例，验证给出的有关图的常见算法，并实现有关的操作。二、实验要求1掌握图的特点，利用图的邻接矩阵和邻接表的存储结构实现图的常见算法。2提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。三、实验内容 1. 设计图的邻接表或邻接矩阵，并给出相应测试程序的输出结果。2. 根据1中内容，编写图的深度或广度优先遍历算法，并写出测试结果*3.假设图G采用邻接表存储，设计一个算法
29、，输出图G中从顶点u到顶点v的长度为l 的所有简单路径。四、程序样例const int MaxVertexNum=10; /*最大顶点数设为100*/ typedef char VertexType; /*顶点类型设为字符型*/ typedef int EdgeType; /*边的权值设为整型*/ typedef struct VertexType vexsMaxVertexNum; /*顶点表*/ EdgeType edgesMaxVertexNumMaxVertexNum; /*邻接矩阵，即边表*/ int n,e; /*顶点数和边数*/ Mgraph; /*Maragh是以邻接矩阵存储的
30、图类型*/ / 建立一个图的邻接矩阵存储的算法如下： void CreateMGraph(Mgraph &G) /*建立有向图G的邻接矩阵存储*/ int i,j,k,w; char ch; cout请输入顶点数和边数(输入格式为:顶点数,边数):nG.nG.e;/*输入顶点数和边数*/ cout请输入顶点信息(输入格式为:顶点号 ):nendl; for (i=0;iG.vexsi; /*输入顶点信息，建立顶点表*/ for (i=0;iG.n;i+) for (j=0;jG.n;j+) G.edgesij=0; /*初始化邻接矩阵*/ cout请输入每条边对应的两个顶点的序号(输入格式为:
31、i,j):nendl; for (k=0;kij; /*输入e条边，建立邻接矩阵*/ G.edgesij=1; /*若加入G-edgesji=1;，*/ /*则为无向图的邻接矩阵存储建立*/ for (i=0;iG.n;i+) for (j=0;jG.n;j+) cout G.edgesij; coutendl; void BFSM(Mgraph G,int k) /*以Vi为出发点，对邻接矩阵存储的图G进行BFS搜索*/ int i,j; LQueue Q; Init_LQueue(Q); int visitedMaxVertexNum; coutvisit vertex:V%cnG.vex
32、skendl; /*访问原点Vk*/ visitedk=1; In_LQueue(Q,k); /*原点Vk入队列*/ while (!Empty_LQueue(Q) Out_LQueue(Q,i); /*Vi出队列*/ for (j=0;jG.n;j+) /*依次搜索Vi的邻接点Vj*/ if (G.edgesij=1 & !visitedj) /*若Vj未访问*/ coutvisit vertex:V%cnG.vexsjendl; /*访问Vj */ visitedj=1; In_LQueue(Q,j); /*访问过的Vj入队列*/ /*BFSM*/ void BFSTraverseAL(M
33、graph &G) /*广度优先遍历以邻接矩阵存储的图G*/ int i; int visitedMaxVertexNum; for (i=0;iG.n;i+) visitedi=0; /*标志向量初始化*/ for (i=0;iG.n;i+) if (!visitedi) BFSM(G,i); /* vi未访问过，从vi开始BFS搜索*/ /*BFSTraverseAL*/void main()Mgraph g;CreateMGraph(g);BFSTraverseAL(g);实验四 排序选择实验类型：综合性 实验要求：必修实验学时： 2学时一、实验目的 掌握常见的排序算法的思想及其适用条件
34、。掌握常见的排序算法的程序实现。二、实验要求1掌握各种查找算法的特点，测试并验证查找的常见算法。2提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。三、实验内容输入一组关键字序列分别实现下列排序，同时统计进行排序时关键字的比较次数和数据移动次数。 1.实现简单选择排序、直接插入排序、冒泡排序、堆排序和归并排序。 2.实现希尔排序算法。 3.实现快速排序算法（取第一个记录或中间记录作为基准记录）。 *4.实现折半插入排序。5.在主函数中设计一个简单的菜单，分别测试上述算法。*6.双向起泡排序。在起泡排序中，若待排序序列为正序，只需一
35、趟扫描，而待排序序列为反序时，需进行n-1趟扫描。对于初始序列（94，10，12，18，42，44，67）只需扫描2趟，而对于初始序列（12，18，42，44，67，94，10）就需扫描6趟。造成这种不对称的原因：每趟扫描仅能使最小数据下沉一个位置，如果改变扫描方向，情况正好相反，即每趟从后往前扫描，都能使当前无序区中最大数据上浮一个位置。为了改变上述两种情况下的不对称性，可以在排序过程中交替改变扫描方向，称之为双向起泡排序。四、程序样例void swap(int &x,int &y)int temp;temp=x;x=y;y=temp;void InsertSort(int a,int n)int x,i,j;for(i=1;in;i+)if(aiai-1) x=ai; /*为统一算法设置监测*/for(j=i-1;x aj;j-)aj+1=aj; /*记录后移*/aj+1=x; /*插入到正确位置*/void SelectSort(int a,int n)int i,j,t