数据结构上机实验

上机实验要求及规范

《数据结构》课程具有比较强的理论性，同时也具有较强的可应用性和实践性，因此上机实验是一个重要的教学环节。一般情况下学生能够重视实验环节，对于编写程序上机练习具有一定的积极性，但是容易忽略实验的总结，忽略实验报告的撰写。对于一名大学生必须严格训练分析总结能力、书面表达能力。需要逐步培养书写科学实验报告以及科技论文的能力。拿到一个题目，一般不要急于编程，而是应该按照面向过程的程序设计思路（关于面向对象的训练将在其它后继课程中进行），首先理解问题，明确给定的条件和要求解决的问题，然后按照自顶向下，逐步求精，分而治之的策略，逐一地解决子问题。具体步骤如下：

1.问题分析与系统结构设计

充分地分析和理解问题本身，弄清要求做什么（而不是怎么做），限制条件是什么。按照以数据结构为中心的原则划分模块，搞清数据的逻辑结构（是线性表还是树、图？），确定数据的存储结构（是顺序结构还是链表结构？），然后设计有关操作的函数。在每个函数模块中，要综合考虑系统功能，使系统结构清晰、合理、简单和易于调试。最后写出每个模块的算法头和规格说明，列出模块之间的调用关系（可以用图表示），便完成了系统结构设计。

2.详细设计和编码

详细设计是对函数（模块）的进一步求精，用伪高级语言（如类C语言）或自然语言写出算法框架，这时不必确定很多结构和变量。

编码，即程序设计，是对详细设计结果的进一步求精，即用某种高级语言（如C/C++语言）表达出来。尽量多设一些注释语句，清晰易懂。尽量临时增加一些输出语句，便于差错矫正，在程序成功后再删去它们。

3.上机准备

熟悉高级语言用法，如C语言。熟悉机器（即操作系统），基本的常用命令。静态检查主要有两条路径，一是用一组测试数据手工执行程序（或分模块进行）；二是通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑，在这个过程中再加入一些注释和断言。如果程序中逻辑概念清楚，后者将比前者有效。

4.上机调试程序

调试最好分块进行，自底向上，即先调试底层函数，必要时可以另写一个调用驱动程序，表面上的麻烦工作可以大大降低调试时所面临的复杂性，提高工作效率。

5.整理实习报告

在上机实开始之前要充分准备实验数据，在上机实践过程中要及时记录实验数据，在上机实践完成之后必须及时总结分析，写出实验报告。

注意：1.算法中元素类型根据实际需要选择。

2.实验题目前带*者难度较高，学生可自选；其余部分为基本内容，应尽量完成（至少完成80%，否则实验不合格）。

实验一线性表

一、实验目的

1. 了解线性表的逻辑结构特性，以及这种特性在计算机内的两种存储结构。

2. 重点是线性表的基本操作在两种存储结构上的实现；其中以链表的操作为侧重点；并进一步学习结构化的程序设计方法。

二、实验内容

1. 输入整型元素序列利用插入算法建立一个非递减有序表。请设计程序实现。要求：采用顺序存储结构实现；采用链式存储结构实现；比较两种方法的优劣。

2. 设计程序实现把题1建立的顺序表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。

3. 设计程序实现把题1建立的单链表中值相同的多余结点的删除。

4. 约瑟夫环问题。有n个人围坐一圈，现从某个人开始报数，数到M的人出列，接着从出列的下一个人开始重新报数，数到M的人又出列，如此下去，直到所有人都出列为止。试设计确定他们出列次序的程序。要求选择单向循环链表作为存储结构模拟整个过程，并依次输出出列人的编码。

*5. 用链表建立通讯录。通讯录内容有：姓名、通讯地址、电话号码。要求：通讯录是按姓名项的字母顺序排列的；能查找通讯录中某人的信息。

*6. 超长正整数的加法，设计一个程序实现两个任意长的整数求和运算

【提示】可采用一个带有头结点的循环链表来表示一个非负的超大整数。从低位开始每四位组成的数字，依次放在链表的第一个、第二个、……第n个结点中，不足四位的最高位存放在链表的最后一个结点中，表头结点值规定为-1。

例如：大整数“567890987654321”可用如下的头结点的链表表示：

按照此数据结构，可以从两个表头结点开始，顺序依次对应相加，求出所需要的进位后，将其代入下一个结点进行运算。

*7. 综合训练。利用单链表实现一个班级学生信息管理（数据录入、插入、删除、排序、查找等）。

实验二栈和队列

一、实验目的

1. 掌握栈这种数据结构特性及其主要存储结构，并能在现实生活中灵活运用。

2. 掌握队列这种数据结构特性及其主要存储结构，并能在现实生活中灵活运用。

3. 了解和掌握递归程序设计的基本原理和方法。

二、实验内容

1．采用顺序存储实现栈的初始化、入栈、出栈操作。

2．采用顺序存储实现循环队列的初始化、入队、出队操作。

3. 设单链表中存放着n个字符，利用栈结构，试设计算法判断字符串是否中心对称。例如xyzzyx即为中心对称的字符串。

4. 假设一个一维向量data[0…maxsize-1]存放一个循环队列中的元素，同时设变量rear和len分别指示循环队列中队尾元素的位置和内含元素的个数。试写出此循环队列的队满条件，并设计出相应的入队和出队的算法。

*5. 阿克曼函数（Ackermann’s function）定义如下：

人们之所以研究该函数，是因为m和n值的较小增长都会引起函数值的极快增长。

（1）设计一个递归算法的源程序，上机运行。

（2）设计一个非递归算法的源程序，上机运行。并进行比较。

*6．综合训练。利用栈实现表达式求值算法。

*7．二项式(a+b) ⁿ展开后，其系数构成杨辉三角形，利用队列写出打印杨辉三角形的前n行的程序。

实验三串

一、实验目的

1. 熟悉串类型的实现方法，了解简单文字处理的设计方法。

2. 熟悉C语言的字符和把字符串处理的原理和方法。

3. 熟悉C语言常见的字符串处理函数。

二、实验内容

1. 输入一个由若干单词组成的文本行，每个单词之间用若干个空格隔开，统计此文本中单词的个数。

2. 设s、t为两个字符串，分别放在两个一维数组中，m、n分别为其长度，判断t是否为s的子串。如果是，输出子串所在位置，否则输出0。

3. 设计可以在主串s中第i个位置插入一个子串t的程序。

4. 串的置换。将主串s中的t串，置换为v串。

实验四数组

一、实验目的

1. 熟悉数组的存储结构及应用。

2. 熟悉稀疏矩阵的“三元组表”和“十字链表”存储结构，运用它们进行矩阵简单运算处理。

二、实验内容

1. 编写用“三元组表”存储稀疏矩阵，进行矩阵处理的程序。

（1）矩阵转置（2）矩阵相加

2. 给定一奇数n，构造一个n阶魔阵。n阶魔阵是一个n阶方阵，其元素由自然数1，2，3，…，n组成。魔阵的每行元素之和，每列元素之和以及主、副对角线元素之和均相等。即对于给定的奇整数n以及i=l，2，3，…，n，魔阵a满足条件。

要求输出结果的格式要具有n阶方阵的形式。

*3. 迷宫实验。迷宫实验是取自心理学的一个古典实验，在该实验中，把一只老鼠从一个无顶大盒子的口放入，在盒中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找出路以到达出口，对同一只老鼠重复进行上述实验，一直到老鼠从入口到出口，而不走错一步，老鼠经多次实验终于得到它学习走通迷宫的路线。

试设计一个算法，寻找一条从迷宫入口到出口的最短路径。要求程序输出：（1）一条通路的二元组( i,j)数据序列，(i,j)表示通路上某一点的坐标。（2）用一种标志(如数字8)在二维数组中标出该条通路，并在屏幕上输出二维数组。

实验五树与二叉树

一、实验目的

1. 熟练掌握二叉树在二叉链表存储结构中的常用遍历方法：先序递归遍历、中序递归和非递归遍历、后序递归遍历。了解二叉树的按层遍历、先序非递归遍历及后序递归遍历。

2. 用树解决实际问题，如哈夫曼编码等。

3. 加深对“数据结构+算法=程序”的理解和认识，提高编写较复杂程序的能力。

二、实验内容

1. 一棵具有n个结点的完全二叉树以一维数组作为存储结构，试设计一个对该完全二叉树进行先序遍历的算法。

2. 二叉树的建立和操作。

（1）对右图所示的二叉树建立二叉链表存储结构。

（2）采用递归算法中序遍历该二叉树。

（3）采用非递归算法中序遍历该二叉树。

（4）求该二叉树的高度。

（5）求该二叉树的叶子个数。

（6）对该二叉树，建立相应的中序线索二叉树，并实现中序遍历。

3. 已知一棵二叉树的先序遍历序列和中序遍历序列，写出可以唯一确定一棵二叉树的算法。

*4. 哈夫曼树问题。

利用哈夫曼编码进行通讯可以大大提高信道利用率，缩短信息传输时间，降低传输成本，但是，这要求在发送端通过一个编码系统对待传数据进行预先编码；在接受端将传来的数据进行解码（复原）。对于双工信道（即可以双向传输的信道），每端都要有一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼的编译码系统。

要求：（1）从终端读入字符集大小为n（即n个字符和n个权值），建立哈夫曼树，进行编码并且输出，并将它存于文件hfmtree中。

（2）利用已建好的哈夫曼编码文件hfmtree，对键盘输入的正文进行译码。输出字符正文，再输出该文的二进制码。

请用下表中给出的字符集和频度的实际统计数据建立哈夫曼树：

并实现以下报文的译码和输出：“THIS PROGRAM IS MY FAVORITE”。

实验六图

一、实验目的

1. 熟悉图的两种常用的存储结构（邻接矩阵、邻接表），以及在这两种存储结构上的两种遍历图的方法，即深度优先遍历和广度优先遍历。进一步掌握递归算法的设计方法。

2. 掌握图的经典算法。

二、实验内容

1. 设计一个程序，为下图的建立邻接矩阵，并进行深度优先遍历。

2. 设计一个程序，为题1的图建立邻接表，并进行广度优先遍历。

3. 试写一个算法，判别以邻接表方式存储的有向图G中是否存在由顶点vi到顶点vj的路径(i≠j)。

4. 假设以—个带权有向图表示某一区域的公交线路网，图中顶点代表一些区域中的重要场所，弧代表已有的公交线路，弧上的权表示该线路上的票价。试设计一个交通指南系统，指导前来咨询者以最低的票价从区域中的某一场所到达另一场所。

*5. 软件专业的学生要学习一系列课程，其中有些课程必须在其先修课程完成后才能学习，具体关系见下表：

假设每门课程的学习时间为一学期，试为该专业的学生设计教学计划，使他们能在最短的时间内修完这些课程。

实验七查找

一、实验目的

1. 掌握几种典型的查找方法（折半查找、二叉排序树的查找、哈希查找）。

2. 了解各种查找算法的特点、使用范围和效率。

二、实验内容

1. 二叉排序树的建立、查找和删除。设有一组数据(33，88，22，55，90，11，66，99)，边输入边插入建立二叉排序树。然后查找78，删除90。

2.编写折半查找的算法的递归调用程序。

*3.设有一组关键字(19,14,23,1,68,20,84,27,56,11,10,79),建立一个哈希查找表。

（1）哈希函数采用: H(key)= key % P(其中P=11)，若发生冲突后，用链地址法解决冲突。

（2）哈希函数采用: H(key)= key % P(其中P=11)，若发生冲突后，用线性探测再散列方法解决冲突。

实验八排序

一、实验目的

1. 熟悉几种典型的排序方法。

2. 了解各种排序算法的特点、使用范围和效率。

二、实验内容

1. 输入一组关键字序列分别实现下列排序:

（1）直接插入排序、直接选择排序和冒泡排序

（2）希尔排序

（3）堆排序

（4）快速排序

2. 统计成绩。给出n个学生的考试成绩表，每条信息由姓名与分数组成，试设计—个算法：

（1）按分数高低次序，打印出每个学生在考试中获得的名次，分数相同的为同一名次；

（2）要求学生的考试成绩表必须通过键盘输入数据而建立，同时要对输出进行格式控制。

（3）分别用冒泡排序和快速排序算法实现。

*3. 综合训练：采用几组不同数据测试各个排序算法的性能（比较次数和移动次数）。

数据结构实验报告

实验名称：_______________________________ 评分：________

专业：___________ 班级：___________ 小组编号：_______

第二篇：数据结构上机实验源代码

数据结构上机实验源代码

栈的应用

十进制数转换为八进制数，

逆序输出所输入的数

实验代码：

//stack.h，头文件

class stack{

public:stack();

bool empty()const;

bool full()const;

error_code gettop(elementtype &x)const;

error_code push(const elementtype x);

error_code pop();

private:

int count;

elementtype data[maxlen];

};

stack::stack(){

count=0;

}

bool stack::empty()const

{

return count==0;

}

bool stack::full()const

{

return count==maxlen;

}

error_code stack::gettop(elementtype &x)const

{

if(empty())return underflow;

else{

x=data[count-1];

return success;

}

error_code stack::push(const elementtype x)

{

if(full())return overflow;

data[count]=x;

count++;

return success;

}

error_code stack::pop()

{

if(empty())return underflow;

count--;

return success;

}

//主程序

#include<iostream.h>

enum error_code{overflow,underflow,success};

typedef int elementtype;

const int maxlen=20;

#include"stack.h"

void read_write() //逆序输出所输入的数

{

stack s;

int i;

int n,x;

cout<<"please input num int n:";

cin>>n;

for(i=1;i<=n;i++)

{

cout<<"please input a num:";

cin>>x;

s.push(x);

}

while(!s.empty())

{

s.gettop(x);

cout<<x<<" ";

s.pop();

}

cout<<endl;

}

void Dec_to_Ocx(int n) //十进制转换为八进制

{

stack s1;

int mod,x;

while(n!=0)

{

mod=n%8;

s1.push(mod);

n=n/8;

}

cout<<"the ocx of the dec is:";

while(!s1.empty())

{

s1.gettop(x);

cout<<x;

s1.pop();

}

cout<<endl;

}

void main()

{int n;

// read_write();

cout<<"please input a dec:";

cin>>n;

Dec_to_Ocx(n);

}

队列的应用

打印n行杨辉三角

实验代码：

//queue.h

class queue{

public:queue(){

count=0;

front=rear=0;}

bool empty(){

return count==0;

}

bool full(){

return count==maxlen-1;

}

error_code get_front(elementtype &x){

if(empty())return underflow;

x=data[(front+1)%maxlen];

return success;

}

error_code append(const elementtype x)

{

if(full())return overflow;

rear=(rear+1)%maxlen;

data[rear]=x;

count++;

return success;

}

error_code serve(){

if(empty())return underflow;

front=(front+1)%maxlen;

count--;

return success;

}

private:int count;

int front;

int rear;

int data[maxlen];

};

//主程序

#include<iostream.h>

enum error_code{overflow,underflow,success};

typedef int elementtype;

const int maxlen=20;

#include"queue.h"

void out_number(int n) //打印前n行的杨辉三角

{

int s1,s2;

int i;

int j;

int k;

queue q;

for(i=1;i<=(n-1)*2;i++)

cout<<" ";

cout<<"1 "<<endl;

q.append(1);

for(i=2;i<=n;i++)

{

s1=0;

for(k=1;k<=(n-i)*2;k++)

cout<<" ";

for(j=1;j<=i-1;j++)

{

q.get_front(s2);

q.serve();

cout<<s1+s2<<" ";

q.append(s1+s2);

s1=s2;

}

cout<<"1 "<<endl;

q.append(1);

}

void main()

{int n;

cout<<"please input n:";

cin>>n;

out_number(n);

}

单链表实验

实验目的: 实验目的

（1）理解线性表的链式存储结构。

（2）熟练掌握动态链表结构及有关算法的设计。

（3）根据具体问题的需要，设计出合理的表示数据的链表结构，并设计相关算法。

实验任务

说明1：本次实验中的链表结构均为带头结点的单链表。

说明2：为使实验程序简洁直观，下面的部分实验程序中将所需要的函数以调用库函数的形式给出，并假设将库函数放在程序文件“linklist.h”中，同时假设该库函数文件中定义了链表结构中的指针类型为link，结点类型为node，并定义了部分常用运算。

例如构建链表、以某种方式显示链表、从文件中读入一个链表、跟踪访问链表结点等。

各运算的名称较为直观，并有相应的注释，因而易于理解和实现。

读者在上机实验时，需要自己设计出所涉及到的库函数，或者将函数放在实验程序中，以方便实验程序的调试。如时间紧的话，也可到作者的网站下载以供参考（不完全相同）。

编写算法实现下列问题的求解。

<1>求链表中第i个结点的指针（函数），若不存在，则返回NULL。

实验测试数据基本要求：

第一组数据：链表长度n≥10，i分别为5，n，0，n+1，n+2

第二组数据：链表长度n=0，i分别为0，2

<2>在第i个结点前插入值为x的结点。

实验测试数据基本要求：

第一组数据：链表长度n≥10，x=100, i分别为5,n,n+1,0,1,n+2

第二组数据：链表长度n=0，x=100，i=5

<3>删除链表中第i个元素结点。

实验测试数据基本要求：

第一组数据：链表长度n≥10，i分别为5,n,1,n+1,0

第二组数据：链表长度n=0， i=5

<4>在一个递增有序的链表L中插入一个值为x的元素，并保持其递增有序特性。

实验测试数据基本要求：

链表元素为（10,20,30,40,50,60,70,80,90,100）,

x分别为25，85，110和8

<5>将单链表Ｌ中的奇数项和偶数项结点分解开，并分别连成一个带头结点的单链表，然后再将这两个新链表同时输出在屏幕上，并保留原链表的显示结果，以便对照求解结果。

实验测试数据基本要求：

第一组数据：链表元素为（1,2,3,4,5,6,7,8,9,10,20,30,40,50,60）

第二组数据：链表元素为（10,20,30,40,50,60,70,80,90,100）

<6>求两个递增有序链表L1和L2中的公共元素，并以同样方式连接成链表L3。

实验测试数据基本要求：

第一组

第一个链表元素为（1，3，6，10，15，16，17，18，19，20）

第二个链表元素为（1，2，3，4，5，6，7，8，9，10，18，20，30）

第二组

第一个链表元素为（1，3，6，10，15，16，17，18，19，20）

第二个链表元素为（2，4，5，7，8，9，12，22）

第三组

第一个链表元素为（）

第二个链表元素为（1，2，3，4，5，6，7，8，9，10）

实验代码:

//linklist.h

enum error_code{arrange_error,null,success};

typedef struct node{elementtype data;

struct node *next;

}node;

class list{

private:node *head;

int count;

public:list() //链表的初始化

{head=new node;

head->next=NULL;

count=0;

}

int length() //求链表的长度

{

return count;

}

/***********取链表中第i个节点的指针**********************/

node * locate(const int i)

{

node *p=head;

int j=0;

if(i<1||i>length())return NULL;

while(p!=NULL)

{if(j==i)return p;

p=p->next;

j++;}

return NULL;

}

/***************在第i节点之前插入数为x的节点****************/

error_code insert(const int i,const elementtype x)

{node *p=head;

int j=0;

while(j!=i-1&&p!=NULL)

{p=p->next;

j++;

}

if(i<1||i>count+1){cout<<"该位置前不能插入元素"<<endl;

return arrange_error;}

node *s=new node;

s->data=x;

s->next=p->next;

p->next=s;

count++;

cout<<"插入成功！"<<endl;

return success;

}

/***************删除第i个节点*****************************/

error_code delete_element(const int i)

{

node *p=head;

int j=0;

while(j!=i-1&&p!=NULL)

{p=p->next;

j++;

}

if(i<1||i>length()){cout<<"此元素不存在"<<endl;

return arrange_error;}

node *u=p->next;

p->next=u->next;

count--;

delete u;

cout<<"删除成功"<<endl;

return success;

}

/******************若原链表递增，插入一个元素保持其递增的顺序***********/

error_code insert1(const elementtype x)

{node *p=head->next;

if(head->next->data>x){node *u=new node;

u->data=x;

u->next=head->next;

head->next=u;

return success;

}

while(p->next!=NULL){

if(p->next->data>x){node *u=new node;

u->data=x;

u->next=p->next;

p->next=u;

return success;

}

p=p->next;

}

node *u=new node;

u->data=x;

u->next=NULL;

p->next=u;

return success;

}

//取链表头结点的地址

node *gethead()

{return head;}

//输出链表中的所有元素

error_code print()

{node *p=head->next;

while(p!=NULL)

{cout<<p->data<<" ";

p=p->next;

}

cout<<endl;

return success;

}

error_code depart( )

{list a;

list b;

node *pa=a.gethead();

node *pb=b.gethead();

node *p=head->next;

while(p!=NULL){

if((p->data)%2==1)

{node *u=new node;

u->data=p->data;

pa->next=u;

pa=u;

pa->next=NULL;

}

if((p->data)%2==0){

node *u=new node;

u->data=p->data;

pb->next=u;

pb=u;

pb->next=NULL;

}

p=p->next;

}

cout<<"链表所有的奇数项为："<<endl;

a.print();

cout<<"链表所有的偶数项为："<<endl;

b.print();

return success;

}

void interset(list b,list &c)

{

node *pa,*pb,*rc,*u;

pa=head->next;

pb=b.gethead()->next;

rc=c.gethead();

while(pa!=NULL&&pb!=NULL)

{

if(pa->data<pb->data)pa=pa->next;

else if(pa->data>pb->data)pb=pb->next;

else{

u=new node;

u->data=pa->data;

rc->next=u;

rc=u;

c.count++;

pa=pa->next;

pb=pb->next;

}

rc->next=NULL;

cout<<"两链表中的公共元素为："<<endl;

c.print();

}

};

// 主程序

#include<iostream.h>

typedef int elementtype;

#include"linklist.h"

void main()

{

list a;list b;list c;

int m;

int n;

int j;

int i;

int choice;

elementtype temp;

{

cout<<"0，实验结束"<<endl;

cout<<"1，实验要求1"<<endl;

cout<<"2，实验要求2"<<endl;

cout<<"3，实验要求3"<<endl;

cout<<"4，实验要求4"<<endl;

cout<<"5，实验要求5"<<endl;

cout<<"6，实验要去6"<<endl;

cout<<"请选择所要做的实验"<<endl;

cin>>choice;

switch(choice)

{

case 0:cout<<"实验结束"<<endl;

break;

case 1://*****************实验要求1

cout<<"请输入a链表的长度："<<endl;

cin>>m;

for(j=1;j<=m;j++)

{

cout<<"请输入元素的值"<<endl;

cin>>temp;

a.insert(j,temp);

}

cout<<"请输入i的值"<<endl;

cin>>i;

if(a.locate(i)!=NULL)cout<<"链表第"<<i<<"个元素的值为："<<a.locate(i)->data<<endl;

else cout<<"NULL"<<endl;

cout<<"请输入i的值"<<endl;

cin>>i;

if(a.locate(i)!=NULL)cout<<"链表第"<<i<<"个元素的值为："<<a.locate(i)->data<<endl;

else cout<<"链表第"<<i<<"个元素的值为：NULL"<<endl;

cout<<"请输入n的值"<<endl;

cin>>n;

for(j=0;j<3;j++)

{

if(a.locate(n+j)!=NULL)cout<<"链表第"<<n+j<<"个元素的值为："<<a.locate(n+j)->data<<endl;

else cout<<"链表第"<<n+j<<"个元素的值为：NULL"<<endl;

}

break;

case 2://******************实验要求2

cout<<"请输入a链表的长度："<<endl;

cin>>m;

for(j=1;j<=m;j++)

{

cout<<"请输入元素的值"<<endl;

cin>>temp;

a.insert(j,temp);

}

cout<<"请输入x的值："<<endl;

cin>>temp;

for(j=1;j<=3;j++)

{cout<<"请输入插入点的位置："<<endl;

cin>>i;

a.insert(i,temp);

}

cout<<"请输入n的值："<<endl;

cin>>n;

for(j=0;j<3;j++)

{

a.insert(n+j,temp);

}

break;

case 3://******************实验要求3

cout<<"请输入a链表的长度："<<endl;

cin>>m;

for(j=1;j<=m;j++)

{

cout<<"请输入元素的值"<<endl;

cin>>temp;

a.insert(j,temp);

}

int n1;

cout<<"请输入要删除的元素的位置"<<endl;

cin>>i;

a.delete_element(i);

cout<<"请输入n的值"<<endl;

cin>>n;

a.delete_element(n);

n1=n+1;

cout<<"请输入要删除的元素的位置"<<endl;

cin>>i;

a.delete_element(i);

cout<<"删除"<<n+1<<"位置的元素"<<endl;

a.delete_element(n1);

cout<<"请输入要删除的元素的位置"<<endl;

cin>>i;

a.delete_element(i);

break;

case 4://*************实验要求4

cout<<"请输入a链表的长度："<<endl;

cin>>m;

for(j=1;j<=m;j++)

{

cout<<"请输入元素的值"<<endl;

cin>>temp;

a.insert(j,temp);

}

cout<<"链表未插入前的，其中的只有："<<endl;

a.print();

for(j=1;j<=4;j++)

{

cout<<"请输入要插入的元素x的值："<<endl;

cin>>temp;

a.insert1(temp);

cout<<"插入后链表中的值为："<<endl;

a.print();

}

break;

case 5://***********实验要求5

cout<<"请输入a链表的长度："<<endl;

cin>>m;

for(j=1;j<=m;j++)

{

cout<<"请输入元素的值"<<endl;

cin>>temp;

a.insert(j,temp);

}

a.depart();

break;

case 6://**************************************************实验要求6

cout<<"请输入a链表的长度："<<endl;

cin>>m;

for(j=1;j<=m;j++)

{

cout<<"请输入元素的值"<<endl;

cin>>temp;

a.insert(j,temp);

}

cout<<"请输入链表的长度："<<endl;

cin>>m;

for(j=1;j<=m;j++)

{

cout<<"请输入元素的值"<<endl;

cin>>temp;

b.insert(j,temp);

}

a.interset(b,c);

cout<<"链表中的元素有："<<endl;

b.print();

cout<<"链表中的元素有："<<endl;

a.print();

break;

default:

{

cout<<"请选择正确的实验要求"<<endl;

break;

}

}while(choice!=0);

}

双链表实验

实验要求,判断双链表是否对称

//dlinklist.h

//双循环链表类的定义

struct Node

{

T data;

Node *next;

Node *prior;

};

class DLinkList

{

private:

Node *Head;

int count;

public:

DLinkList() ;//构造函数，创建空双循环链表

~DLinkList();//析构函数，删除表空间

void CreateList(int n);//创建具有n个元素的双循环链表

void ListDisplay();//输出表元素

void symmetry();//判断链表中的元素是否对称

};

//双循环链表类的实现

DLinkList::DLinkList()//构建函数，建一空双循环链表

{

Head=new Node;

Head->next=Head;

Head->prior=Head;

count=0;

}

DLinkList::~DLinkList()//析构函数，释放链表所占空间

{

Node *p,*q;

while(q->next!=Head) q=q->next; //定位q到尾结点？？？

while(Head!=Head->next)

{//从头结点开始，依次释放结点

p=Head;

Head=Head->next;

q->next=Head;

Head->prior=q;

delete p;

count--;

}

Head=NULL;//头结点指向空

}

void DLinkList::CreateList(int n)

{//尾插法(正序)创建具有n个元素的双循环链表

Node *p,*s;//设置工作指针。p指向尾结点

p=Head;

cout<<"请依次输入"<<n<<"个元素值："<<endl;

for(int i=1;i<=n;i++)

{

s=new Node;//新建元素结点

cin>>s->data;//输入新建数据元素值

s->next=p->next;//新结点链入表尾

p->next=s;

s->prior=p;

Head->prior=s;

p=s;

count++;

}

void DLinkList::ListDisplay()

{//显示链表

Node *p;

p=Head->next;

int i=1;

while(p!=Head)

{

cout<<i<<"\t";

cout<<p->data<<endl;

p=p->next;

i++;

}

void DLinkList::symmetry()

{

Node *p,*s;

int i;

p=Head->next;

s=Head->prior;

for(i=1;i<=count/2;i++)

{

if(p->data!=s->data){cout<<"链表不对称"<<endl;break;}

p=p->next;

s=s->prior;

}

if(i==count/2+1)cout<<"链表对称"<<endl;

}

//主程序

#include<iostream.h>//cout,cin

typedef int T;

#include "dLinklist.h"

void main() //主函数

{

int i;

DLinkList L;//

int choice;

{//显示主菜单

cout<<"1-创建双循环链表\n";

cout<<"2-判断链表是否对称\n";

cout<<"3-显示链表\n";

cout<<"4-退出\n";

cout<<"Enter choice:";

cin>>choice;

switch(choice)

{

case 1://创建链表

cout<<"请输入要创建的链表中元素个数:";

cin>>i;//将创建的链表中数据元素的个数

cout<<endl;

L.CreateList(i);

break;

case 2://判断链表是否为空

L.symmetry();

break;

case 3://显示表

L.ListDisplay();

cout<<endl;

break;

case 4://退出

cout<<"结束运行"<<endl;

break;

default://

cout<<"Invalid choice\n";

break;

}

}while(choice!=4);//结束

}

二叉树的试验

试验要求:二叉树的构建,二叉树的前序,中序,后序遍历算法,查找替换树中的节点,交换一棵树的左右子树

试验代码:

#include<iostream.h>

enum error_code{success};

typedef char elementtype;

typedef struct bnode{

elementtype data;

struct bnode *lchild,*rchild;

}bnode, *bitree;

class bitre{

private:bnode *root;

void create(bitree &T);

int high(bnode *T);

void preorder(bnode *T);//先序遍历

void inorder(bnode *T);//中序遍历

void postorder(bnode *T);//后序遍历

public:

bnode * getroot(){return root;}

void create(){create(root);}

int high(){return high(root);}

void preorder(){preorder(root);}//先序遍历

void inorder(){inorder(root);}//中序遍历

void postorder(){postorder(root);}//后序遍历

void search(bnode *T,char &num,bitree &m);//查找

void jhuan(bnode * T,char &num,char &temp);//替换

void jbitree(bnode *T,char &num);//交换一个节点的左右子树

};

void bitre::jbitree(bnode *T,char &num)//交换一个节点的左右子树

{

if(T!=NULL)

{

if(T->data==num)

{

bnode *temp;

temp=T->lchild;

T->lchild=T->rchild;

T->rchild=temp;

}

jbitree(T->lchild,num);

jbitree(T->rchild,num);

}

void bitre::jhuan(bnode *T,char &num,char &temp)//替换树中的元素

{

if(T!=NULL)

{

if(T->data==num){T->data=temp;cout<<"交换成功"<<endl;}

jhuan(T->lchild,num,temp);

jhuan(T->rchild,num,temp);

}

void bitre::search(bnode *T,char &num,bitree &m) //查找元素并返回该元素的地址

{

if(T!=NULL)

{

if(T->data==num)m=T;

search(T->lchild,num,m);

search(T->rchild,num,m);

}

int max(int m,int n) //求最大值

{return (m>=n)?m:n;}

int bitre::high(bnode *T)

{

if(T==NULL){

return 0;

}

else return max(high(T->lchild),high(T->rchild))+1;

}

void bitre::create(bitree &T) //创建一颗二叉树

{char x;

cin>>x;

if ( x== '.' ) T = NULL;

else{T = new bnode;

T -> data = x;

create ( T -> lchild );

create ( T -> rchild );

}

void bitre::preorder(bnode *T)

{

if(T!=NULL)

{

cout<<T->data;

preorder(T->lchild);

preorder(T->rchild);

}

void bitre::inorder(bnode *T)

{

if(T!=NULL)

{

inorder(T->lchild);

cout<<T->data;

inorder(T->rchild);

}

void bitre::postorder(bnode *T)

{

if(T!=NULL)

{

postorder(T->lchild);

postorder(T->rchild);

cout<<T->data;

}

void main()

{ char ch;

char dh;

bitre t;

bitree a;

cout<<"请按先序序列输入二叉树中元素的值"<<endl;

t.create();

cout<<"树的先序序列为"<<endl;

t.preorder();

cout<<endl;

cout<<"树的中序序列为"<<endl;

t.inorder();

cout<<endl;

cout<<"树的后序序列为"<<endl;

t.postorder();

cout<<endl;

cout<<"请输入查找的元素：";

cin>>ch;

t.search(t.getroot(),ch,a);

cout<<a->data<<endl;

cout<<"请先后输入待交换的元素与交换的元素"<<endl;

cin>>ch;

cin>>dh;

t.jhuan(t.getroot(),ch,dh);

cout<<"请输入待交换节点的元素值"<<endl;

cin>>ch;

t.jbitree(t.getroot(),ch);

t.preorder();

cout<<endl;

}

图的试验

试验要求:

图的构建,实现图的深度遍历算法与广度遍历算法,以及图的有关操作

试验代码:

/*-------------------------------单链队列------------------------------*/

//linkqueue.h

#ifndef LINKNODE

#define LINKNODE

template <class T>

struct LinkNode{

T data;

LinkNode<T> *next;

};

template <class T>

class LinkedQueue{

protected:

LinkNode<T> *front;

LinkNode<T> *rear;

int length;

public:

LinkedQueue();

~LinkedQueue();

void ClearQueue();

bool IsEmpty() const;

int GetLength() const;

LinkNode<T>* GetHead() const;//返回对头元素

bool EnQueue(T &elem);

bool DeQueue(T &receive);

bool QueueTraverse(bool (*Visit)(T &elem));

};

template <class T>

LinkedQueue<T>::LinkedQueue()

{

front = new LinkNode<T>;

if(!front) return;

rear = front;

front->next = false;

length=0;

}

template <class T>

LinkedQueue<T>::~LinkedQueue()

{

ClearQueue();

delete front;

}

template <class T>

void LinkedQueue<T>::ClearQueue()//从队头清到队尾

{

LinkNode<T> *temp = front->next;

while(front->next)

{

front->next = temp->next;

delete temp;

temp = front->next;

}

rear = front;

length=0;

}

template <class T>

bool LinkedQueue<T>::IsEmpty() const

{

return (front==rear)?true:false;

}

template <class T>

int LinkedQueue<T>::GetLength() const

{

return length;

}

template <class T>

LinkNode<T>* LinkedQueue<T>::GetHead() const

{

return front;

}

template <class T>

bool LinkedQueue<T>::EnQueue(T &elem)

{

LinkNode<T> *temp = new LinkNode<T>;

if(!temp) return false;

temp->data = elem; temp->next = false;

rear->next = temp;

rear = temp;

++length;

return true;

}

template <class T>

bool LinkedQueue<T>::DeQueue(T &receive)

{

if(front==rear) return false;

LinkNode<T> *temp = front->next;//指向队头元素

receive = temp->data;

front->next = temp->next;

delete temp;

if(!front->next) rear = front;

--length;

return true;

}

template <class T>

bool LinkedQueue<T>::QueueTraverse(bool (*Visit)(T &elem)) //从队头到队尾进行一次遍历

{

LinkNode<T> *temp=front->next;

while(temp)

{

if(!Visit(temp->data))

return false;

temp = temp->next;

}

return true;

}

#endif

//主程序

// 数组表示法

#include "iostream"

#include "string"

#include "iomanip"

#include "LinkQueue.h"

using namespace std;

#define MAX_VERTEX_NUM 20 //最大顶点数

const int infinity = INT_MAX;

struct ArcCell{

int adj; //对无权图有1，0表示是否相邻，对带权图，则为权值类型

char *info; //该弧的相关信息

};

template <class T>

struct _MGraph{

T vexs[MAX_VERTEX_NUM];//顶点表

ArcCell arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵，即边表

int vexnum;//顶点数

int arcnum;//边数

int kind;//是以邻接矩阵存储的图类型

};

template <class T>

class MGraph{

_MGraph<T> mgraph;

bool visited[MAX_VERTEX_NUM];

public:

int LocateVex (T u); //图存在，图中存在顶点u 则返回该顶点在图中的位置

T GetVex(int index); //图存在，index是图中某个顶点的序号则返回index的顶点

void PutVex(T v,T value); //图存在，v是，v是G中某个顶点返回v的第一个临接点的序号若无领接点则返回空

int NextAdjVex(T v,T w); //图存在，v是图中某个顶点则对v赋值value

int FirstAdjVex(T v); //图存在图中某个顶点，w是v的邻接点返回v的相对于w的下一个邻接点的序号若w是v的最后一个邻接点则返回空

bool CreateUDG(); //构造无向图

void DFS(int index); //从第index出发递归的深度优先遍历图

bool (*VisitFunc)(T v); //访问顶点v的方式

void DisPlay(); //输出邻接矩阵

bool DFSTraverse(bool (*visit)(T v));//图存在，对图进行深度优先遍历

bool BFSTraverse(bool (*visit)(T v));//图存在，对图进行广度优先遍历

};

template <class T>

bool visit(T v)

{

cout<<v<<" ";

return true;

}

template <class T>

T MGraph<T>::GetVex(int index)//ok

{

if(index<0||index>=mgraph.vexnum)

return false;//越界返回空

return mgraph.vexs[index];

}

template <class T>

void MGraph<T>::PutVex(T v,T value)//ok

{

int index = LocateVex(v);

if(index<0)

return;

mgraph.vexs[index] = value;

}

template <class T>

bool MGraph<T>::CreateUDG()//ok

//构造无向图

{

int i , j ;T v1, v2;

cout<<"请输入无向图的顶点个数，边的个数: ";

cin>>mgraph.vexnum>>mgraph.arcnum;

cout<<"请输入各个顶点: ";

for(i = 0;i<mgraph.vexnum;i++)

//构造顶点向量

{

cin>>mgraph.vexs[i];

}

for(i = 0;i<mgraph.vexnum;i++)

//初始化邻接矩阵

{

for(j = 0;j<mgraph.vexnum;j++)

{

mgraph.arcs[i][j].adj = 0;

mgraph.arcs[i][j].info = false;

}

for(i = 0;i<mgraph.arcnum;i++)

//构造邻接矩阵

{

cout<<"请输入一条边依附的两个顶点: ";

cin>>v1>>v2 ;

int m = LocateVex(v1);

int n = LocateVex(v2);

mgraph.arcs[m][n].adj = 1;// <v1, v2>

mgraph.arcs[n][m].adj = 1;// <v2, v1>

}

mgraph.kind = 2;

return true;

}

template <class T>

int MGraph<T>::LocateVex(T u)//ok

{

for(int i = 0 ;i<MAX_VERTEX_NUM;i++)

{

if(u == mgraph.vexs[i])

{

return i;

}

return -1;

}

template <class T>

int MGraph<T>::FirstAdjVex(T v)//ok

{

int temp = LocateVex(v); int j = 0;

if(mgraph.kind==1||mgraph.kind==3)

j = infinity;

for(int i = 0 ;i<mgraph.vexnum;i++)

{

if(mgraph.arcs[temp][i].adj!=j)

{

return i;

}

return -1; //无邻接点返回空

}

template <class T>

int MGraph<T>::NextAdjVex(T v,T w)//ok

{

int id_v = LocateVex(v);

int id_w = LocateVex(w);

int j = 0;

if(mgraph.kind==1||mgraph.kind==3)

j = infinity;

for(int i = id_w+1;i<mgraph.vexnum;i++)

{

if(mgraph.arcs[id_v][i].adj!=j)

{

return i;

}

return -1;

}

template <class T>

void MGraph<T>::DisPlay()

{

int i,j;

char graphkind[7];

char arckind[3];

switch(mgraph.kind)

{

case 0:strcpy(graphkind,"有向图");

strcpy(arckind,"弧");

break;

case 1:strcpy(graphkind,"有向网");

strcpy(arckind,"弧");

break;

case 2:strcpy(graphkind,"无向图");

strcpy(arckind,"边");

break;

case 3:strcpy(graphkind,"无向网");

strcpy(arckind,"边");

break;

}

cout<<mgraph.vexnum<<"个顶点"<<mgraph.arcnum<<"条"<<arckind<<"的"<<graphkind<<endl;

//输出顶点

cout<<"顶点为";

for(i = 0;i<mgraph.vexnum;i++)

{

cout<<mgraph.vexs[i]<<" ";

}

//输出权值的邻接矩阵

cout<<"权值的邻接矩阵为: "<<endl;

for(i = 0;i<mgraph.vexnum;i++)

{

for(j = 0;j<mgraph.vexnum;j++)

{

if(mgraph.arcs[i][j].adj==infinity)

cout<<setw(5)<<"∞"<<'\t';

else

cout<<setw(5)<<mgraph.arcs[i][j].adj<<'\t';

}

cout<<endl<<endl;

}

template <class T>

void MGraph<T>::DFS(int index)

//从第index个顶点出发递归地深度优先遍历图

{

T v1;int i;

visited[index] = true;//已访问

VisitFunc(mgraph.vexs[index]);//访问index 的顶点

v1 = GetVex(index);

for(i = FirstAdjVex(v1);i>=0;i = NextAdjVex(v1,GetVex(i)))

{

if(!visited[i])

DFS(i);//对v的尚未访问的邻接顶点w递归调用DFS

}

template <class T>

bool MGraph<T>::DFSTraverse(bool (*visit)(T v))

{

int i ;

VisitFunc = visit;

for(i = 0;i<MAX_VERTEX_NUM;i++)

{

visited[i] = false;

}

for(i = 0;i<mgraph.vexnum;i++)

//对每个未被访问的顶点进行深度优先遍历

{

if(!visited[i])

DFS(i);

}

cout<<endl;

return true;

}

template <class T>

bool MGraph<T>::BFSTraverse(bool (*visit)(T v))

{

LinkedQueue<int> q;int i,j,receive; T u1;

for(i = 0;i<MAX_VERTEX_NUM;i++)

{

visited[i] = false;

}

for(i = 0;i<mgraph.vexnum;i++)

//对每个未被访问的顶点进行广度优先遍历

{

if(!visited[i])

{

visited[i] = true;

if(!visit(mgraph.vexs[i]))

return false;

q.EnQueue(i);

while(!q.IsEmpty())

{

q.DeQueue(receive); //对头元素出队并置为receive

u1 = GetVex(receive);

for(j = FirstAdjVex(u1);j>=0;j = NextAdjVex(u1,GetVex(j)))

{

if(!visited[j])

{

visited[j] = true;

if(!visit(mgraph.vexs[j]))

return false;

q.EnQueue(j);

}

cout<<endl;

return true;

};

//菜单

void ShowOper()

{

cout<<endl;

cout<<"0. 建立图"<<endl;

cout<<"1. 返回顶点v在图中的位置"<<endl;

cout<<"2. 返回所需位置的顶点的值"<<endl;

cout<<"3. 改变某个已知顶点v的值"<<endl;

cout<<"4. 在图中，从第一个顶点出发深度优先遍历图"<<endl;

cout<<"5. 在图中，从第一个顶点广度优先遍历图"<<endl;

cout<<"6. 显示图"<<endl;

cout<<"7. 退出"<<endl;

cout<<"请选择你要的操作: "<<endl;

}

void main()

{

int opchoice;

MGraph<string> g;//case0

{ ShowOper();

cin>>opchoice;

switch(opchoice)

{

case 0:

{

g.CreateUDG();

cout<<endl;

break;

}

case 1:

{

string a;

cout<<"请输入您要的所要查询位置的顶点的名称 ";

cin>>a;

cout<<"顶点"<<a<<"在图中的位置为"<<g.LocateVex(a)<<endl;

cout<<endl;

break;

}

case 2:

{

int index;

cout<<"请输入您要的所要查询顶点的位置";

cin>>index;

cout<<"位置为"<<index<<"的顶点为"<<g.GetVex(index)<<endl;

cout<<endl;

break;

}

case 3:

{

string v;

string value;

cout<<"请输入您要的所要更改的顶点的值";

cin>>v;

cout<<"请输入您要的所要更改的顶点的新值";

cin>>value;

g.PutVex(v,value);

cout<<endl;

break;

}

case 4:

{

cout<<"从第一个顶点出发深度优先遍历图的序列为"<<endl;

g.DFSTraverse(visit);

cout<<endl;

break;

}

case 5:

{

cout<<"从第一个顶点出发广度优先遍历图的序列为"<<endl;

g.BFSTraverse(visit);

cout<<endl;

break;

}

case 6:

{

g.DisPlay();

cout<<endl;

break;

}

case 7:

cout<<"结束运行，Bye-Bye!"<<endl;

break;

default:

cout<<"选择不合理，请重选!"<<endl;

}//case

}while(opchoice!=7);

}//main

相关推荐

数据结构上机实验

上机实验要求及规范

实验一 线性表

实验二 栈和队列

实验三 串

实验四 数组

实验五 树与二叉树

实验六 图

实验七 查找

实验八 排序

数据结构实验报告

第二篇：数据结构上机实验源代码

专栏推荐

实验一线性表

实验二栈和队列

实验三串

实验四数组

实验五树与二叉树

实验六图

实验七查找

实验八排序