数据结构与算法实验指导书70459.docx
《数据结构与算法实验指导书70459.docx》由会员分享，可在线阅读，更多相关《数据结构与算法实验指导书70459.docx（27页珍藏版）》请在冰点文库上搜索。
数据结构与算法实验指导书70459
计算机和信息学院
实验一顺序表
【实验目的】
熟练掌握线性表在顺序存储结构上的基本操作。
【实验平台】
操作系统：
Windows2000或WindowsXP
开发环境：
C或C++
【实验内容及要求】
顺序表的查找、插入和删除。
设计算法，实现线性结构上的顺序表的产生以及元素的查找、插入和删除。
具体实现要求：
1.从键盘输入10个整数，产生顺序表，并输出结点值。
2.从键盘输入1个整数，在顺序表中查找该结点。
若找到，输出结点的位置；若找不到，则显示“找不到”。
3.从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插入在对应位置上，输出顺序表所有结点值，观察输出结果。
4.从键盘输入1个整数，表示欲删除结点的位置，输出顺序表所有结点值，观察输出结果。
【参考框架】
#include
#include
//顺序表的定义：
#defineListSize100//表空间大小可根据实际需要而定，这里假设为100
typedefintDataType;//DataType可以是任何相应的数据类型如int,float或char
typedefstruct
{DataTypedata[ListSize];//向量data用于存放表结点
intlength;//当前的表长度
}SeqList;
voidmain（）
{
SeqListL;
inti,x;
intn=10;//欲建立的顺序表长度
L.length=0;
voidCreateList（SeqList*L,intn）;
voidPrintList（SeqListL,intn）;
intLocateList（SeqListL,DataTypex）;
voidInsertList（SeqList*L,DataTypex,inti）;
voidDeleteList（SeqList*L,inti）;
CreateList（&L,n）;//建立顺序表
PrintList（L,n）;//打印顺序表
printf（"输入要查找的值：
"）;
scanf（"%d",&x）;
i=LocateList（L,x）;//顺序表查找
printf（"输入要插入的位置：
"）;
scanf（"%d",&i）;
printf（"输入要插入的元素：
"）;
scanf（"%d",&x）;
InsertList（&L,x,i）;//顺序表插入
PrintList（L,n）;//打印顺序表
printf（"输入要删除的位置：
"）;
scanf（"%d",&i）;
DeleteList（&L,i）;//顺序表删除
PrintList（L,n）;//打印顺序表
}
//顺序表的建立：
voidCreateList（SeqList*L,intn）
{
//在此插入必要的语句
}
//顺序表的打印：
voidPrintList（SeqListL,intn）
{
//在此插入必要的语句
}
//顺序表的查找：
intLocateList（SeqListL,DataTypex）
{
//在此插入必要的语句
}
//顺序表的插入：
voidInsertList（SeqList*L,DataTypex,inti）
{
//在此插入必要的语句
}
//顺序表的删除：
voidDeleteList（SeqList*L,inti）
{
//在此插入必要的语句
}
【实验报告】
《数据结构和算法》实验报告一
学院：
班级：
学号：
姓名：
日期：
程序名：
L2211.CPP
一、上机实验的问题和要求：
顺序表的查找、插入和删除。
设计算法，实现线性结构上的顺序表的产生以及元素的查找、插入和删除。
具体实现要求：
5.从键盘输入10个整数，产生顺序表，并输出结点值。
6.从键盘输入1个整数，在顺序表中查找该结点。
若找到，输出结点的位置；若找不到，则显示“找不到”。
7.从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插入在对应位置上，输出顺序表所有结点值，观察输出结果。
8.从键盘输入1个整数，表示欲删除结点的位置，输出顺序表所有结点值，观察输出结果。
二、源程序及注释：
三、运行输出结果：
四、调试和运行程序过程中产生的问题及采取的措施：
实验二链表
【实验目的】
熟练掌握线性表在链式存储结构上的基本操作。
【实验平台】
操作系统：
Windows2000或WindowsXP
开发环境：
C或C++
【实验内容及要求】
单链表的查找、插入和删除。
设计算法，实现线性结构上的单链表的产生以及元素的查找、插入和删除。
具体实现要求：
9.从键盘输入20个整数，产生带表头的单链表，并输出结点值。
10.从键盘输入1个整数，在单链表中查找该结点。
若找到，则显示“找到了”；否则，则显示“找不到”。
11.从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插入在对应位置上，输出单链表所有结点值，观察输出结果。
12.从键盘输入1个整数，表示欲删除结点的位置，输出单链表所有结点值，观察输出结果。
13.将单链表中值重复的结点删除，使所得的结果表中个结点值均不相同，输出单链表所有结点值，观察输出结果。
14.删除其中所有数据值为偶数的结点，输出单链表所有结点值，观察输出结果。
15.把单链表变成带表头结点的循环链表，输出循环单链表所有结点值，观察输出结果。
16.（★）将单链表分解成两个单链表A和B，使A链表中含有原链表中序号为奇数的元素，而B链表中含有原链表中序号为偶数的元素，且保持原来的相对顺序，分别输出单链表A和单链表B的所有结点值，观察输出结果。
【参考框架】
#include
#include
//单链表的定义：
typedefintDataType;//DataType可以是任何相应的数据类型如int,float或char
typedefstructnode//结点类型定义
{DataTypedata;//结点的数据域
structnode*next;//结点的指针域
}ListNode;
typedefListNode*LinkList;
voidmain（）
{
inti;
DataTypekey,x;
LinkListhead;
ListNode*p;
LinkListCreateList（void）;
voidPrintList（LinkListhead）;
LinkListLocateNode（LinkListhead,DataTypekey）;
LinkListGetNode（LinkListhead,inti）;
voidInsertList（LinkListhead,DataTypex,inti）;
voidDeleteList（LinkListhead,inti）;
voidDeleteManyList（LinkListhead）;
voidDeleteEvenList（LinkListhead）;
voidChangeCircList（LinkListhead）;
voidPrintCircList（LinkListhead）;
head=CreateList（）;//建立单链表
PrintList（head）;//打印单链表
printf（"输入要查找的值：
"）;
scanf（"%d",&key）;
p=LocateNode（head,key）;//单链表查找
printf（"请输入欲插入元素的位置：
"）;
scanf（"%d",&i）;
printf（"请输入欲插入的元素：
"）;
scanf（"%d",&x）;
InsertList（head,x,i）;//单链表插入
PrintList（head）;//打印单链表
printf（"请输入欲删除结点的位置：
"）;
scanf（"%d",&i）;
DeleteList（head,i）;//单链表删除
PrintList（head）;//打印单链表
DeleteManyList（head）;//删除重复值
PrintList（head）;//打印单链表
DeleteEvenList（head）;//删除偶数值
PrintList（head）;//打印单链表
ChangeCircList（head）;//修改为循环单链表
PrintCircList（head）;//打印循环单链表
/*voidDivideList（LinkListhead,LinkList*A,LinkList*B）;
//分割成两个单链表
DivideList（head,&A,&B）;
PrintList（A）;
PrintList（B）;
*/
}
//单链表的建立：
LinkListCreateList（void）
{
//在此插入必要的语句
}
//单链表的打印：
voidPrintList（LinkListhead）
{
//在此插入必要的语句
}
//单链表的查找1：
LinkListLocateNode（LinkListhead,DataTypekey）
{
//在此插入必要的语句
}
//单链表的查找2：
LinkListGetNode（LinkListhead,inti）
{
//在此插入必要的语句
}
//单链表的插入：
voidInsertList（LinkListhead,DataTypex,inti）
{
//在此插入必要的语句
}
//单链表的删除：
voidDeleteList（LinkListhead,inti）
{
//在此插入必要的语句
}
//删除单链表中重复值：
voidDeleteManyList（LinkListhead）
{
//在此插入必要的语句
}
//删除单链表中偶数值：
voidDeleteEvenList（LinkListhead）
{
//在此插入必要的语句
}
//修改为循环单链表：
voidChangeCircList（LinkListhead）
{
//在此插入必要的语句
}
//循环单链表的打印：
voidPrintCircList（LinkListhead）
{
//在此插入必要的语句
}
/*
//分割成两个单链表
voidDivideList（LinkListhead,LinkList*A,LinkList*B）;
{
//在此插入必要的语句
}
*/
【实验报告】
《数据结构和算法》实验报告二
学院：
班级：
学号：
姓名：
日期：
程序名：
L2311.CPP
一、上机实验的问题和要求：
单链表的查找、插入和删除。
设计算法，实现线性结构上的单链表的产生以及元素的查找、插入和删除。
具体实现要求：
1.从键盘输入20个整数，产生带表头的单链表，并输出结点值。
2.从键盘输入1个整数，在单链表中查找该结点。
若找到，则显示“找到了”；否则，则显示“找不到”。
3.从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插入在对应位置上，输出单链表所有结点值，观察输出结果。
4.从键盘输入1个整数，表示欲删除结点的位置，输出单链表所有结点值，观察输出结果。
5.将单链表中值重复的结点删除，使所得的结果表中个结点值均不相同，输出单链表所有结点值，观察输出结果。
6.删除其中所有数据值为偶数的结点，输出单链表所有结点值，观察输出结果。
7.把单链表变成带表头结点的循环链表，输出循环单链表所有结点值，观察输出结果。
8.（★）将单链表分解成两个单链表A和B，使A链表中含有原链表中序号为奇数的元素，而B链表中含有原链表中序号为偶数的元素，且保持原来的相对顺序，分别输出单链表A和单链表B的所有结点值，观察输出结果。
二、源程序及注释：
三、运行输出结果：
四、调试和运行程序过程中产生的问题及采取的措施：
实验三树
【实验目的】
熟练掌握在链式二叉树在二叉链表存储结构上的基本操作。
【实验平台】
操作系统：
Windows2000或WindowsXP
开发环境：
C或C++
【实验内容及要求】
要求采用二叉链表作为存储结构，完成二叉树的建立，前序、中序和后序遍历的操作，求所有叶子及结点总数的操作等。
具体实现要求：
17.基于先序遍历的构造算法：
输入是二叉树的先序序列，但必须在其中加入虚结点以示空指针的位置。
假设虚结点输入时用空格字符表示。
18.用广义表表示所建二叉树。
19.分别利用前序遍历、中序遍历、后序遍历所建二叉树。
20.求二叉树结点总数，观察输出结果。
21.求二叉树叶子总数，观察输出结果。
22.交换各结点的左右子树，用广义表表示法显示新的二叉树。
23.（★）二叉树采用链接存储结构，其根结点指针为T，设计一个算法对这棵二叉树的每个结点赋值：
（注意要修改DataType类型）
a）叶结点的值为3
b）只有左孩子或右孩子的结点则其值分别等于左孩子或右孩子的值
c）左、右孩子均有的结点，则其值等于左、右孩子结点的值之和
d）用广义表表示法显示所建二叉树
【参考框架】
#include
#include
//二叉树的链式存储表示
typedefcharDataType;//应由用户定义DataType的实际类型
typedefstructnode
{DataTypedata;
structnode*lchild,*rchild;//左右孩子指针
}BinTNode;//结点类型
typedefBinTNode*BinTree;
voidmain（）
{
voidListBinTree（BinTreeT）;//用广义表表示二叉树
voidDisplayBinTree（BinTreeT）;//用凹入表表示二叉树
voidCreateBinTree（BinTree*T）;//构造二叉链表
voidPreorder（BinTreeT）;//前序遍历二叉树
voidInorder（BinTreeT）;//中序遍历二叉树
voidPostorder（BinTreeT）;//后序遍历二叉树
intnodes（BinTreeT）;//计算总结点数
intleafs（BinTreeT）;//计算总叶子数
BinTreeswap（BinTreeT）;//交换左右子树
BinTreeT;
printf（"请输入先序序列（虚结点用空格表示）：
\n"）;
CreateBinTree（&T）;
ListBinTree（T）;
printf（"\n"）;
DisplayBinTree（T）;
printf（"前序遍历：
\n"）;
Preorder（T）;
printf（"\n"）;
printf（"中序遍历：
\n"）;
Inorder（T）;
printf（"\n"）;
printf（"后序遍历：
\n"）;
Postorder（T）;
printf（"\n"）;
printf（"二叉树的总结点数为%d\n",nodes（T））;
printf（"二叉树的总叶子结点数为%d\n",leafs（T））;
T=swap（T）;
ListBinTree（T）;
printf（"\n"）;
}
//构造二叉链表
voidCreateBinTree（BinTree*T）
{
//在此插入必要的语句
}
//用广义表表示二叉树
voidListBinTree（BinTreeT）
{
//在此插入必要的语句
}
//用凹入表表示二叉树
voidDisplayBinTree（BinTreeT）
{
//在此插入必要的语句
}
//前序遍历二叉树
voidPreorder（BinTreeT）
{
//在此插入必要的语句
}
//中序遍历二叉树
voidInorder（BinTreeT）
{
//在此插入必要的语句
}
//后序遍历二叉树
voidPostorder（BinTreeT）
{
//在此插入必要的语句
}
//计算总结点数
intnodes（BinTreeT）
{
//在此插入必要的语句
}
//计算总叶子数
intleafs（BinTreeT）
{
//在此插入必要的语句
}
//交换左右子树
BinTreeswap（BinTreeT）
{
//在此插入必要的语句
}
【实验报告】
《数据结构和算法》实验报告三
学院：
班级：
学号：
姓名：
日期：
程序名：
L61.CPP
一、上机实验的问题和要求：
要求采用二叉链表作为存储结构，完成二叉树的建立，前序、中序和后序遍历的操作，求所有叶子及结点总数的操作等。
具体实现要求：
i.基于先序遍历的构造算法：
输入是二叉树的先序序列，但必须在其中加入虚结点以示空指针的位置。
假设虚结点输入时用空格字符表示。
ii.用广义表表示所建二叉树。
iii.分别利用前序遍历、中序遍历、后序遍历所建二叉树。
iv.求二叉树结点总数，观察输出结果。
v.求二叉树叶子总数，观察输出结果。
vi.交换各结点的左右子树，用广义表表示法显示新的二叉树。
vii.（★）二叉树采用链接存储结构，其根结点指针为T，设计一个算法对这棵二叉树的每个结点赋值：
（注意要修改DataType类型）
a.叶结点的值为3
b.只有左孩子或右孩子的结点则其值分别等于左孩子或右孩子的值
c.左、右孩子均有的结点，则其值等于左、右孩子结点的值之和
d.用广义表表示法显示所建二叉树
二、源程序及注释：
三、运行输出结果：
四、调试和运行程序过程中产生的问题及采取的措施：
实验四Huffman树
【实验目的】
理解建立Huffman树的算法。
【实验平台】
操作系统：
Windows2000或WindowsXP
开发环境：
C或C++
【实验内容及要求】
阅读理解建立Huffman树的算法，对该算法进行运行及调试。
具体实现要求：
1.调试并运行Huffman算法。
2.（★）求Huffman树的带权路径长度WPL。
【参考框架】
#include
#include
#include
//Huffman树的存储结构
#definen100//叶子数目
#definem2*n-1//树中结点总数
typedefstruct//结点类型
{floatweight;//权值，不妨设权值均大于零
intlchild,rchild,parent;//左右孩子及双亲指针
}HTNode;
typedefHTNodeHuffmanTree[m];//HuffmanTree是向量类型
typedefstruct
{charch;//存储字符
charbits[n+1];//存放编码位串
}CodeNode;
typedefCodeNodeHuffmanCode[n];
voidInitHuffmanTree（HuffmanTreeT）;//初始化Huffman树
voidInputWeight（HuffmanTreeT）;//输入权值
voidSelectMin（HuffmanTreeT,inti,int*p1,int*p2）;
voidmain（）
{
voidCreateHuffmanTree（HuffmanTreeT）;//构造Huffman树
voidCharSetHuffmanEncoding（HuffmanTreeT,HuffmanCodeH）;
HuffmanTreeT;
HuffmanCodeH;
CreateHuffmanTree（T）;
CharSetHuffmanEncoding（T,H）;
}
voidCreateHuffmanTree（HuffmanTreeT）
{//构造Huffman树，T[m-1]为其根结点
inti,p1,p2;
InitHuffmanTree（T）;//将T初始化
InputWeight（T）;//输入叶子权值至T[0..n-1]的weight域
for（i=n;i{SelectMin（T,i-1,&p1,&p2）;
//在T[0..i-1]中选择两个权最小的根结点，其序号分别为p1和p2
T[p1].parent=T[p2].parent=i;
T[i].lchild=p1;//最小权的根结点是新结点的左孩子
T[i].rchild=p2;//次小权的根结点是新结点的右孩子
T[i].weight=T[p1].weight+T[p2].weight;
}
}
voidInitHuffmanTree（HuffmanTreeT）
{//初始化Huffman树
inti;
for（i=0;i{
T[i].weight=0;
T[i].lchild=T[i].rchild=T[i].parent=NULL;
}
}
voidInputWeight（HuffmanTreeT）
{//输入权值
inti;
for（i=0;i{
printf（"请输入第%d个权值：
",i+1）;
scanf（"%f",&T[i].weight）;
}
}
voidSelectMin（HuffmanTreeT,inti,int*p1,int*p2）
{//在T中选择两个权最小的根结点
intj;
floatmin1,min2;
min1=min2=-1;
for（j=0;j<=i;j++）
if（T[j].parent==NULL）
{
if（T[j].w
升级会员 