辽宁科技大学《数据结构实验指导书》(自动化tongxin)

1、数据结构实 验 指 导 书 适用专业：自动化、电子、通信等目 次前 言3实验一 线性表的操作5实验二 栈和队列的操作13实验三 图算法18实验四 排序选择20前 言数据结构是计算机及相关专业的一门核心基础课程，也是很多高校考研专业课之一。它主要介绍线性结构、树结构、图结构三种逻辑结构元素的存储实现，在此基础上介绍一些典型算法及时、空效率分析。这门课程的主要任务是培养学生的算法设计能力及良好的程序设计习惯。通过学习，要求学生能够掌握典型算法的设计思想及程序实现，能够根据实际问题选取合适的存储方案，设计出简洁、高效、实用的算法，为后续课程的学习及软件开发打下良好的基础。学习这门课程，习题和实验是两

2、个关键环节。学生理解算法，上机实验是最佳的途径之一。因此，实验环节的好坏是学生能否学好数据结构的关键。为了更好地配合学生实验，特编写试验指导书。希望同学们在使用本实验指导书及进行实验的过程中，能够帮助我们不断地发现问题，并提出建议，使数据结构成为具有省内一流水平的课程。一、实验目的 更好的理解算法的思想、培养编程能力。二、实验要求1、 每次实验前学生必须根据试验内容认真准备实验程序及调试时所需的输入数据。 2、在指导教师的帮助下能够完成实验内容，得出正确的实验结果。 3、实验结束后总结实验内容、书写实验报告。 4、遵守实验室规章制度、不缺席、按时上、下机。 5、实验学时内必须做数据结构的有关内

3、容，不允许上网聊天或玩游戏，如发现上述现象，取消本次上机资格，平时成绩扣10分。四、说明 1、本实验的所有算法中元素类型可以根据实际需要选择。 2、实验题目中带者为较高要求，学生可自选；其余部分为基本内容，应尽量完成（至少完成70%，否则实验不合格）。 3、数据结构是很多高校的硕士研究生入学考试的专业课之一，希望有志于考研的学生能够在学习过程中注意各种算法的理解，以便为考研做一定的准备。五、实验报告的书写要求 1明确实验的目的及要求； 2记录实验的输入数据和输出结果； 3说明实验中出现的问题和解决过程； 4写出实验的体会和实验过程中没能解决的问题；六、参考书目 数据结构-C语言描述-耿国华等

4、高等教育出版社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#include<iostream.h>const 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 &quo

7、t;溢出" if (i<1 | i>L.length+1) 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 (i<1 | i>L.length) cout<<&quo

8、t;位置不合法" x=L.datai-1; for (j=i; j<L.length; j+) L.dataj-1=L.dataj; /注意第j个元素存在数组下标为j-1处 L.length-; return x;void PrintList(SeqList &L)for(int i=0;i<L.length;i+)cout<<L.datai<<endl;void main()SeqList L;init(L);for(int i=1;i<=10;i+)Insert(L,i,i);PrintList(L);2#include<i

9、ostream.h>#include<stdlib.h>typedef int datatype;typedef struct Node datatype data; struct Node *next; LNode,*Linklist;/*Linklist initlist()LNode * first;first=new LNode; first->next=NULL; return first;*/Linklist Creat_LinkList1() LNode *first;first=new LNode; first->next=NULL; /*空表*/

10、LNode *s; datatype x; /*设数据元素的类型为int*/int n,i=0;cout<<"输入n值 "<<endl; cin>>n;while (i<n) cin>>x; s=new LNode; s->data=x; s->next=first->next; first->next=s;i+; return first;void Insert(LNode *first, int i,datatype x)LNode *p,*s;p=first;int j=0;while(p&

11、amp;&j<i-1)p=p->next;j+;if(!p) cout<<"位置不合法！ "s=new LNode; /*申请、填装结点*/ s->data=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) cou

12、t<<"不存在元素 ！ " x=q->data; p->next=q->next; /*新结点插入在第i-1个结点的后面*/ delete q; return x;void huafen(Linklist &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->

13、;next=q;r=q;q=p->next;void print(Linklist &first)LNode *p;p=first->next;while(p)cout<<" "<<p->data; p=p->next;void main()Linklist A,B;B=new LNode; B->next=NULL;A=Creat_LinkList1();print(A);cout<<endl;cout<<"the huafen result"huafen(A,B);

14、print(A);cout<<endl;print(B);cout<<endl;3#include<iostream.h>#include<stdlib.h>typedef 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,

15、int i) LNode *p;int j; p=first->next; j=1; /或p=first; j=0; while (p && j<i) p=p->next; /工作指针p后移 j+; if (!p) cout<< "位置不合法" else return p->data; void Insert(CList &first, int i, datatype x) LNode *p,*s;int j; p=first ; j=0; /工作指针p初始化while (p && j<i-1

16、)p=p->next; /工作指针p后移j+;if (!p) cout<< "位置不合法"else s=new LNode; s->data=x; /向内存申请一个结点s，其数据域为xs->next=p->next; /将结点s插入到结点p之后p->next=s; datatype Delete(CList &first,int i) LNode *p,*q;int j;datatype x;p=first ; j=0; /工作指针p初始化 while (p && j<i-1) /查找第i-1个结点 p

17、=p->next; j+; if (!p| !p->next) cout<< "位置不合法" /结点p不存在或结点p的后继结点不存在 else q=p->next; 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 j; void Cr

18、eateCList( 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

19、=first->next;while(p->next!=first)cout<<p->data<<" " p=p->next; cout<<p->data<<" " void main() CList C; int a6=15,12,54,65,9,23;int x,i,j;CreateCList(C,a,6);print(C);cout<<endl;j=count(C);cout<<j<<endl;cout<<"输入x

20、值插入的位置i"<<endl;cin>>x>>i;Insert(C,i,x); print(C);说明： 1算法的定义可以以头文件的方式存储,主函数实现该头文件的包含即可调用 2. 静态数组存储结构的顺序表定义，要求表中元素的最大个数 可以使用#define MAXSIZE 50 3程序的编写可以使用C+语言中类的形式如顺序表Const int MAXSIZE=50;typedef int DataType；class SeqList protected： DataType listMAXSIZE； /静态数组定义 int size；/当前元素个数

21、 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 i）const；/取数据元素 ； 4. 单链表是由一个一个的结点组成的，因此，要定义和实现单链表，必须先定义结点。 实验二 栈和队列的操作实验类型：验证性 实验要求：必修实验学时： 2学时一、实验目的 1掌握栈的存储特点

22、及基本操作的实现。 2掌握队列的基本算法及其应用算法的程序实现。 3. 了解串的存储特点及基本操作的实现。二、实验要求1掌握栈、队列及串的特点及实现。2提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。三、实验内容 1. 堆栈测试和应用问题。要求： 设计一个主函数实现对顺序栈相关算法进行测试。测试方法为：依次把数据元素1,2,3,4,5入栈，然后弹出栈中的数据元素并在屏幕上显示。2.链式队列测试和应用问题.要求： 设计一个链式队列代码.测试方法为：依次把数据元素1,2,3,4,5入对列，然后出队列中的数据元素并在屏幕上显示.*3.

23、编写判断一个字符序列是否是回文的函数，要求使用栈和队列.4设计串采用顺序存储结构，一个姓名用串来表示，编写函数实现姓名的逆置。如white John变成John white.*5. 设计一个带头结点的循环单链表类，实现约瑟夫环问题；问题描述：设编号为1,2,，n(n>0)个人按顺时针方向围坐-圈，每人持有一个正整数密码。开始时任意给出一个报数上限值m从第一个人开始顺时针方向自1起顺序报数。报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新自1起顺序报数.如此下去，直到所有人全部出列为止。要求设计一个程序模拟此过程，并给出出列人的编号序列。 测试数据

24、： n=7,7个人的密码依次为3,1,7,2,4,8,4 初始报数上限值m=20 四、程序样例1#include<iostream.h>#include<stdlib.h>typedef int datatype; const int MAXSIZE=50; typedef struct datatype dataMAXSIZE; int top; SeqStack; void Init_SeqStack(SeqStack &s)s.top= -1; int Empty_SeqStack(SeqStack &s) if (s.top= -1) retur

25、n 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; /*栈空不能出栈 */ e

26、lse 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);/cout<<Top_SeqStack(s)<

27、<endl;for( i=1;i<=10;i+)Pop_SeqStack(s,x);cout<<" "<<x<<endl; 2 #include<iostream.h>#include<stdlib.h>typedef int datatype;typedef struct node datatype data; struct node *next; QNode; /*链队结点的类型*/typedef struct QNode *front,*rear; LQueue; void Init_LQueue

28、(LQueue &q) QNode *p; /*申请头尾指针结点*/ p=new QNode; /*申请链队头结点*/ p->next=NULL; q.front=q.rear=p; void In_LQueue(LQueue &q , datatype 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 ret

29、urn 0; int Out_LQueue(LQueue &q , datatype &x) QNode *p;if (Empty_LQueue(q) ) cout<<"队空"<<endl; /*队空，出队失败*/ else p=q.front->next; q.front->next=p->next; x=p->data;/*队头元素放x中*/ delete p; if (q.front->next=NULL) q.rear=q.front; return 1; void main()LQueue q;

30、Init_LQueue(q);int i,x;for(i=1;i<10;i+)In_LQueue(q,i);cout<<Empty_LQueue(q)<<endl;Out_LQueue(q,x); Out_LQueue(q,x);cout<<" "<<x<<endl;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(i&

31、lt;4)/for(i=1;i<10;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 <string.h>#include <iostream.h>void ReverseNa

32、me(char *name, char *newName)char *p;p = strchr(name, ' ');/p指在空格' '位置*p = '0'/把空格换为'0'，因此name的长度只包括名部分strcpy(newName, p+1);/指针p+1指示的是原姓名串name的姓部分strcat(newName, ",");/新姓名串newName等于姓+逗号strcat(newName, name);/新姓名串newName等于姓+逗号+名*p = ' '/恢复原姓名串name为开始时

33、的状态void main(void)char name = "William Topp", newName30;ReverseName(name, newName);cout << "Name: "<< name << endl;cout << "ReverseName: "<< newName << endl;注意问题1重点理解栈、队列和串的算法思想，能够根据实际情况选择合适的存储结构。 2栈、队列的算法是后续实验的基础（树、图、查找、排序等）。实验三 图算法实

34、验类型：验证性 实验要求：必修实验学时： 2学时一、实验目的参照给定的图类的程序样例，验证给出的有关图的常见算法，并实现有关的操作。二、实验要求1掌握图的特点，利用图的邻接矩阵和邻接表的存储结构实现图的常见算法。2提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。三、实验内容 1. 设计图的邻接表或邻接矩阵，并给出相应测试程序的输出结果。2. 根据1中内容，编写图的深度或广度优先遍历算法，并写出测试结果*3.假设图G采用邻接表存储，设计一个算法，输出图G中从顶点u到顶点v的长度为l 的所有简单路径。四、程序样例const int

35、MaxVertexNum=10; /*最大顶点数设为100*/ typedef char VertexType; /*顶点类型设为字符型*/ typedef int EdgeType; /*边的权值设为整型*/ typedef struct VertexType vexsMaxVertexNum; /*顶点表*/ EdgeType edgesMaxVertexNumMaxVertexNum; /*邻接矩阵，即边表*/ int n,e; /*顶点数和边数*/ Mgraph; /*Maragh是以邻接矩阵存储的图类型*/ / 建立一个图的邻接矩阵存储的算法如下： void CreateMGraph

36、(Mgraph &G) /*建立有向图G的邻接矩阵存储*/ int i,j,k,w; char ch; cout<<"请输入顶点数和边数(输入格式为:顶点数,边数):n"<<endl; cin>>G.n>>G.e;/*输入顶点数和边数*/ cout<<"请输入顶点信息(输入格式为:顶点号 ):n"<<endl; for (i=0;i<G.n;i+) cin>>G.vexsi; /*输入顶点信息，建立顶点表*/ for (i=0;i<G.n;i+) fo

37、r (j=0;j<G.n;j+) G.edgesij=0; /*初始化邻接矩阵*/ cout<<"请输入每条边对应的两个顶点的序号(输入格式为:i,j):n"<<endl; for (k=0;k<G.e;k+) cin>>i>>j; /*输入e条边，建立邻接矩阵*/ G.edgesij=1; /*若加入G->edgesji=1;，*/ /*则为无向图的邻接矩阵存储建立*/ for (i=0;i<G.n;i+) for (j=0;j<G.n;j+) cout<<" "

38、<<G.edgesij; cout<<endl; void BFSM(Mgraph G,int k) /*以Vi为出发点，对邻接矩阵存储的图G进行BFS搜索*/ int i,j; LQueue Q; Init_LQueue(Q); int visitedMaxVertexNum; cout<<"visit vertex:V%cn"<<G.vexsk<<endl; /*访问原点Vk*/ visitedk=1; In_LQueue(Q,k); /*原点Vk入队列*/ while (!Empty_LQueue(Q) Ou

39、t_LQueue(Q,i); /*Vi出队列*/ for (j=0;j<G.n;j+) /*依次搜索Vi的邻接点Vj*/ if (G.edgesij=1 && !visitedj) /*若Vj未访问*/ cout<<"visit vertex:V%cn"<<G.vexsj<<endl; /*访问Vj */ visitedj=1; In_LQueue(Q,j); /*访问过的Vj入队列*/ /*BFSM*/ void BFSTraverseAL(Mgraph &G) /*广度优先遍历以邻接矩阵存储的图G*/ i

40、nt i; int visitedMaxVertexNum; for (i=0;i<G.n;i+) visitedi=0; /*标志向量初始化*/ for (i=0;i<G.n;i+) if (!visitedi) BFSM(G,i); /* vi未访问过，从vi开始BFS搜索*/ /*BFSTraverseAL*/void main()Mgraph g;CreateMGraph(g);BFSTraverseAL(g);实验四 排序选择实验类型：综合性 实验要求：必修实验学时： 2学时一、实验目的 掌握常见的排序算法的思想及其适用条件。掌握常见的排序算法的程序实现。二、实验要求1掌握各种查找算法的特点，测