数据结构实验指导手册版.docx
- 文档编号:14322842
- 上传时间:2023-06-22
- 格式:DOCX
- 页数:44
- 大小:295.15KB
数据结构实验指导手册版.docx
《数据结构实验指导手册版.docx》由会员分享,可在线阅读,更多相关《数据结构实验指导手册版.docx(44页珍藏版)》请在冰点文库上搜索。
数据结构实验指导手册版
五邑大学计算机学院
数据结构实验指导手册
2015年3月
目 录
实验一 线性表1
1.实验目的1
2.实验内容1
3.解题思路1
实验二 栈4
1.实验目的4
2.实验内容4
3.解题思路4
实验三 队列8
1.实验目的8
2.实验内容8
3.解题思路8
实验四 二叉树12
1.实验目的12
2.实验内容12
3.解题思路12
实验五 哈夫曼树18
1.实验目的18
2.实验内容18
3.解题思路18
实验六 图的基本存储21
1.实验目的21
2.实验内容21
3.解题思路21
实验七 图的应用26
1.实验目的26
2.实验内容26
3.解题思路26
实验八 查找30
1.实验目的30
2.实验内容30
3.解题思路30
实验九 排序32
1.实验目的32
2.实验内容32
3.解题思路32
说明36
附录 实验报告模板37
实验一 线性表
1.实验目的
(1)了解线性表的逻辑结构特性是数据元素之间存在着线性关系,在计算机中表示这种关系有顺序存储结构和链式存储结构;
(2)掌握这两种存储结构的描述方法;
(3)掌握线性表的基本操作(查找、插入、删除);
(4)考虑时间和空间复杂度设计算法。
2.实验内容
(1)创建一个顺序表,存放在数组A[N]中,元素的类型为整型,设计算法调整A,使其左边的所有元素小于0,右边的所有元素大于0(要求算法的时间复杂度和空间复杂度均为O(n))。
(2)建立一个循环单链表,其节点有prior,data和next三个域,其中data为数据域,存放元素的有效信息,next域为指针域,指向后继节点,prior为指针域,它的值为NULL。
编写一个算法将此表改为循环双链表。
3.解题思路
(1)如图1-1所示,设立两个工作指针i和j,i由数组的左端向右移动,查找大于等于0的数,j由数组的右端向左端移动,查找小于0的数,然后交换,如图1-2所示,直到i>=j,调整结束。
图1-1
图1-2
算法描述(C语言)如下:
voidquickSwapList(inta[],intn)
{
inti=0,j=n-1;//n为顺序表的长度,即数的个数
while(i { while(a[i]<0&&i while(a[j]>=0&&i if(i { intt=a[i];a[i]=a[j];a[j]=t; } i++; j--; } } (2)如图1-3所示,已建有一个单循环链表(带头结点),first指向头结点。 设立两个工作指针p和q,分别指向头结点和第1个结点;执行q->prior=p;,建立第1个结点的前驱指针,如图1-4所示;同步移动工作指针p和q分别指向下一个结点,如图1-5所示,建立q指向结点的前驱,直到q==first为止,再将头结点的前驱设为最后一个结点,如图1-6所示。 图1-3 图1-4 图1-5 图1-6 算法描述(C语言)如下: voidsingleCircleToDoubleCircleLinkList(structNode*first) { structNode*p,*q; p=first;//工作指针p指向头结点 q=first->next;//工作指针q指向第1个结点 while(q! =first) { q->prior=p;//置结点q的前驱为指针p指向的结点 p=p->next;//移动工作指针p q=q->next;//移动工作指针q } q->prior=p;//置头结点的前驱为最后一个结点 } 实验二 栈 1.实验目的 (1)理解栈的定义、特点及与线性表的异同; (2)熟悉顺序栈的组织方法,栈满、栈空的判断条件及其描述; (3)掌握栈的基本操作(进栈、退栈等)。 2.实验内容 (1)设计一个算法,将一般算术表达式转化为逆波兰表达式,并求逆波兰表达式的值。 (2)设计两个栈S1、S2都采用顺序栈方式,并且共享一个存储区[0,MaxLen-1],为了尽量利用空间,减少溢出的可能,可采用栈顶相向、迎面增长的存储方式,如图2-1所示。 设计一个有关栈的入栈和出栈算法。 图2-1 3.解题思路 (1)一般算术表达(中缀表达),如#3*(4+2)/2-5#,#为表达式界定符,逆波兰表达式(后缀表达式),如前述表达的后缀表达式为: 342+*2/5-。 设中缀表达式的运算符有+、-、*、/、#五种,运算符的优先级别从高到低为()、*、/、+、-、#;有括号先算括号内,再算括号外的,多层括号由内向外进行。 中缀表达式转换为后缀表达式需要用到一个临时栈optr暂存运算符。 转换算法描述(伪代码)如下: 1.将栈optr初始化为#; 2.从左至右依次扫描表达式的每个字符,执行下述操作 2.1若当前字符是运算对象,则输出该字符,处理下一个字符; 2.2若当前字符是运算符且优先级别比栈optr的栈顶运算符的优先级高,则将该字符入栈optr,处理下一个字符; 2.3若当前字符是运算符且优先级别比栈optr的栈顶运算符优先级别低,则将栈optr的栈顶元素弹出并输出; 2.4若当前字符是运算符且优先级别与栈optr的栈顶运算符的优先级相等,则将栈optr的栈顶元素弹出,处理下一个字符。 后缀表达式求值,由于后缀表达中所有的计算按运算符出现的顺序从左向右进行,不用再考虑运算符的优先级。 设定一个临时堆栈opnd暂存计算过程的中间结果。 后缀表达式计算算法描述(伪代码)如下: 1.初始化栈opnd为空; 2.从左到右依次扫描表达式的每一个字符,执行下述操作; 2.1若当前是运算对象,则入栈opnd,处理下一个字符; 2.2若当前字符是运算符,则从栈opnd出栈两个运算对象,执行运算并将结果入栈opnd,处理下一个字符; 3.输出栈opnd的栈顶元素,即表达式的运算结果。 (2)两栈共享存储空间,需要解决的关键问题在于如何判断栈满和栈空,由于两栈共享存储空间,入栈和出栈的时候还需要区分是哪个栈。 设lsTop是左栈(数组下标为0的一端为栈底)栈顶指针,rsTop为右栈(数组下标为MaxLen-1的一端为栈底)栈顶指针,显然,当两个栈都为空时,lsTop==-1,rsTop==MaxLen,如图2-2所示;当栈满时,rsTop和lsTop存在以下关系: rsTop==lsTop+1,如图2-3所示。 图2-2 图2-3 入栈算法描述(C语言)如下: //入栈,s=1,入左栈,s=2,入右栈,x为入栈元素 voidpush(ints,intx) { if(rsTop==lsTop+1)//栈满 { printf("栈已满! \n"); return; } if(s==1)//入左栈 { lsTop++; dsStack[lsTop]=x; } elseif(s==2)//入右栈 { rsTop--; dsStack[rsTop]=x; } else printf("该栈不存在! \n"); return; } 出栈算法描述(C语言)如下: //出栈,s=1,出左栈,s=2,出右栈,x返回出栈元素,成功函数返回1,否则返回0 intpop(ints,int*x) { if(s==1)//出左栈 { if(lsTop==-1) { printf("栈已空! \n"); return0; } *x=dsStack[lsTop]; lsTop--; } elseif(s==2)//出右栈 { if(rsTop==MaxLen) { printf("栈已空! \n"); return0; } *x=dsStack[rsTop]; rsTop++; } else { printf("该栈不存在! \n"); return0; } return1; } 实验三 队列 1.实验目的 (1)理解队列的定义、特点及与线性表的异同; (2)熟悉队列的组织方法,队列满、队列空的判断条件及其描述; (3)掌握队列的基本操作(入队、出队等)。 2.实验内容 (1)假设以数组sequ[MaxSize]存放环形队列的元素,同时Rear和Len分别指示环形队列中队尾元素的位置和内含元素的个数。 设计相应的入队和出队算法。 (2)某汽车轮渡口,过江渡船每次能载10辆车过江。 过江车辆分别为客车类和货车类,上船有如下规定: 同类车先到先上船,客车先于货车上渡船,且每上4辆客车,才允许上一辆货车;若等待客车不足4辆则以货车代替;若无货车等待则允许客车都上船。 设计一个算法模拟渡口管理。 3.解题思路 (1)解决问题的关键在于以下两点: 如何使用软件的方法构造环形队列和如何通过Rear和Len来确定队头元素所在的位置。 对于第1点,通过模运算来实现,即Rear=(Rear+1)%MaxSize;第2个问题,当队尾元素的下标大于队头元素的下标时,如图3-1所示,显然,Rear-Len+1即为队头元素的下标;当队尾元素的下标小于队头元素的下标时,如图3-2所示,此时队头元素的下标为: (Rear+MaxSize)-Len+1;为使这两种情况统一处理,采用以下表达式来计算队头元素的下标: ((Rear+MaxSize)-Len+1)%MaxSize。 队空和队满的问题通过Len的值即可判断出,Len=0显然是队空,Len=MaxSize则为队满。 图3-1 图3-2 环形队列入队算法描述(C语言)如下: //入队 voidentryQueue(intx) { if(Len==MaxSize)//队满 { printf("队列已满,不能入队\n"); return; } Rear=(Rear+1)%MaxSize;//移动队尾指针 sequ[Rear]=x;//入队 Len++;//长度加1 return; } 环形队列出队算法描述(C语言)如下: //出队,返回出队元素 intexitQueue(void) { intx,First;//队头元素的下标 if(Len==0)//队空 { printf("队列已空,不能出队\n"); return-1; } First=((Rear+MaxSize)-Len+1)%MaxSize;//计算队头元素的下标 x=sequ[First];//获得队头元素 Len--;//长度减1 returnx;//返回队头元素 } (2)建立3个队列,分别为客车队列bus,货车队列truck和渡船队列ferry,设置3个变量标识已上渡船的客车数量busNum、货车数量truckNum和总数量totalNum。 渡口管理示意图(某个状态)如图3-3所示,图中以*代表客车,#代表货车。 图3-3 当车辆到达渡口时,客车入bus队列,货车入truck队列。 当上渡船的汽车数量totalNum小于10时,循环扫描客车队列和货车队列,若busNum<4且客车队列不为空,将客车队列的队头汽车出队上船,busNum++,totalNum++;若busNum<4且客车队列为空但货车队列不为空,将货车队列的队头汽车出队上船,置busNum=0,truckNum++,totalNum++;若busNum>=4,且货车队列不为空,将货车队列的队头汽车出队上渡船,置busNum=0,totalNum++,truckNum++;若客车队列不空但货车队列为空,则将客车队列的队头汽车出队上渡船,置totalNum++,busNum++,truckNum=0;若客车队列和货车队列都为空时等待车辆的到达。 渡口管理算法描述(伪代码)如下: 1.初始化各队列为空,置totalNum=0,busNum=0,truckNum=0; 2.输入到达渡口的汽车序列,将客车和货车分别入队; 3.当totalNum 3.1如果busNum<4且客车队列不为空,将客车队列的队头汽车出队上渡船,置totalNum++,busNum++; 3.2如果busNum<4且客车队列为空,但是货车队列不为空,将货车队列的队头汽车出队上渡船,置totalNum++,truckNum++,busNum=0; 3.3如果busNum>=4且货车队列不为空,将货车队列的队头汽车出队上渡船,置totalNum++,truckNum++,busNum=0; 3.4如果busNum>=4且货车队列为空,但客车队列不为空,将各车队列的队头汽车出队上渡船,置totalNum++,truckNum=0,busNum++; 3.5如果客车队列和货车队列都为空,中止循环; 4.输出当前客车、货车汽车等待情况和渡船装载汽车情况,算法结束。 实验四 二叉树 1.实验目的 (1)掌握二叉树的结构特性和二叉链表存储结构; (2)理解二叉树、完全二叉树、满二叉树的概念和存储特点; (3)掌握二叉树遍历的递归和非递归方法。 2.实验内容 (1)假设二叉树采用链接存储方式存储,分别编写一个二叉树先序遍历的递归算法和非递归算法。 (2)一棵完全二叉树以顺序方式存储,设计一个递归算法,对该完全二叉树进行中序遍历。 3.解题思路 (1)采用扩展二叉树的先序遍历序列来建立一棵二叉树,如图4-1(a)所示的一棵二叉树,其扩展先序遍历序列为图4-1(c)所示,其中#表示为空。 图4-1 二叉树链表结点结构如下: structbiTreeNode { chardata;//二叉树元素为字符型,存放A-Z等 structbiTreeNode*leftChild,*rightChild;//左孩子、右孩子指针 }; 创建二叉树的递归算法描述(C语言)如下: structbiTreeNode*creatBiTree(structbiTreeNode*T) { charch; staticinti=0; ch=node[i];//数组node存放了要创建的二叉树的扩展先序遍历序列 i++; if(ch=='#') { T=NULL;//#代表空子树; } else { T=(structbiTreeNode*)malloc(sizeof(structbiTreeNode)); if(! T)exit(0); T->data=ch;//数据域为ch T->leftChild=creatBiTree(T->leftChild);//递归建立左子树 T->rightChild=creatBiTree(T->rightChild);//递归建立右子树 } returnT; } 二叉树的先序遍历递归算法描述(C语言)如下: voidpreOrder(structbiTreeNode*T) { if(T==NULL)//递归调用结束条件 return; else { printf("%c",T->data);//访问根结点T的数据域 preOrder(T->leftChild);//前序递归遍历T的左子树 preOrder(T->rightChild);//前序递归遍历T的右子树 } } 二叉树的先序遍历非递归算法相对较难,其关键是: 在先序遍历过某结点的整个左子树后,如何找到该结点的右子树的根指针。 需要定义一个堆栈存放遍历过的结点的指针,以便能通过它找到该结点的右子树。 一般情况下,设要遍历的二叉树的根指针为bt,可能有两种情况: (a)若bt! =NULL,则表明当前的二叉树不为空,此时,输出根结点bt的值并将bt保存到栈中,准备继续遍历bt的左子树。 (b)若bt==NULL,则表明以bt为根指针的二叉树遍历完毕,并且bt是栈顶指针所指结点的左子树,若栈不空,则应根据栈顶指针所指结点找到待遍历右子树的根指针并赋给bt,以继续遍历下去;若栈空,则表明整个二叉树遍历完毕,应结束。 二叉树先序遍历非递归算法描述(伪代码)如下: 1.栈s初始化; 2.循环直到bt为空且栈s为空; 2.1当bt不空时循环 2.1.1输出bt->data; 2.1.2将指针bt保存在栈中; 2.1.3继续遍历bt的左子树; 2.2如果栈s不空,则 2.2.1将栈顶元素弹出至bt; 2.2.2准备遍历bt的右子树; 二叉树先序遍历非递归算法描述(C语言)如下: voidnPreOrder(structbiTreeNode*bt) { top=-1;//采用顺序栈,并假定不会发生上溢 while(bt! =NULL||top! =-1)//两个条件都不成立才退出循环 { while(bt! =NULL) { printf("%c",bt->data); s[++top]=bt;//将根指针bt入栈 bt=bt->leftChild; } if(top! =-1)//栈非空 { bt=s[top--]; bt=bt->rightChild; } } } (2)完全二叉树是指: 对一棵具有n个结点的二叉树按层序编号,如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同,则这棵二叉树称为完全二叉树。 如图4-2所示,即为一棵完全二叉树。 其先序遍历为: ABDHIEJCFG,中序遍历为: HDIBJEAFCG,后序遍历为: HIDJEBFGCA。 图4-2 采用顺序存储即按层序编号的顺序存储所有结点,如图4-3所示,采用一维数组node[MaxSize]存储图4-1所示的完全二叉树,下标为0的单元(即node[0])存放结点数,下标为1的单元存放根结点,以此类推。 图4-3 若要在此存储结构上实现完全二叉树的递归中序遍历,需要解决的关键问题在于如何确定一个结点(叶子结点除外)的左孩子和右孩子所在的下标,以及其双亲结点(根结点除外)的下标。 由二叉树【性质5-5】可知: 对一棵具有n个结点的完全二叉树中的结点从1开始按层序编号,则对任意的编号为i(1<=i<=n)的结点(简称结点i),有: (a)如果i>1,结点i的双亲的编号为i/2;否则结点i是根结点,无双亲。 (b)如果2i<=n,则结点i的左孩子的编号为2i;否则结点i无左孩子。 (c)如果2i+1<=n,则结点i的右孩子的编号为2i+1;否则结点i无右孩子。 显然,按图4-3所示的存储方式,结点所在的下标与层序编号一致。 在二叉链表的递归中序遍历算法的基础上,用结点下标代替结点的地址,即可实现顺序存储的递归中序遍历。 顺序存储的完全二叉树递归中序遍历算法描述(C语言)如下: voidseqInOrder(inti) { if(i==0)//递归调用的结束条件 return; else { if(2*i<=node[0]) seqInOrder(2*i);//中序遍历i的左子树 else seqInOrder(0); printf("%2c",node[i]);//输出根结点 if(2*i+1<=node[0]) seqInOrder(2*i+1);//中序遍历i的右子树 else seqInOrder(0); } } 与此类似的,其递归先序和后序遍历算法分别如下: 顺序存储的完全二叉树递归先序遍历算法描述(C语言)如下: voidseqPreOrder(inti) { if(i==0)//递归调用的结束条件 return; else { printf("%2c",node[i]);//输出根结点 if(2*i<=node[0]) seqPreOrder(2*i);//先序遍历i的左子树 else seqPreOrder(0); if(2*i+1<=node[0]) seqPreOrder(2*i+1);//先序遍历i的右子树 else seqPreOrder(0); } } 顺序存储的完全二叉树递归后序遍历算法描述(C语言)如下: voidseqPostOrder(inti) { if(i==0)//递归调用的结束条件 return; else { if(2*i<=node[0])//后序遍历i的左子树 seqPostOrder(2*i); else seqPostOrder(0); if(2*i+1<=node[0])//后序遍历i的右子树 seqPostOrder(2*i+1); else seqPostOrder(0); printf("%2c",node[i]);//输出根结点 } } 实验五 哈夫曼树 1.实验目的 (1)理解哈夫曼树的概念、结构特性和哈夫曼编码原理; (2)掌握构造哈夫曼树的基本方法; (3)掌握运用哈夫曼树进行哈夫曼编码的方法; 2.实验内容 根据哈夫曼(Huffman)编码的原理,编写一个程序,在用户输入节点权重的基础上建立它的哈夫曼编码。 3.解题思路 这涉及哈夫曼树。 首先回顾几个术语: 叶子结点的权值: 指对叶子结点赋予的一个有意义的数值量;二叉树的带权路径长度: 从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和叫做二叉树的带权路径长度。 哈夫曼树: 给定一组具有确定权值的叶子结点,可以构造出不同的二叉树,将其中带权路径长度最小的二叉树称为哈夫曼树。 哈夫曼树可用于构造最短的不等长编码方案,称为哈夫曼编码树。 规定哈夫曼编码树的左分支代表0,右分支代表1,则从根结点到每个叶子结点所经过的路径组成的0和1的序列便为该叶子结点对应字符的编码,称为哈夫曼编码。 哈夫曼算法的基本思想是: (a)初始化: 由给定的n个权值 构造n棵只有一个根结点的二叉树,从而得到一个二叉树集合 ; (b)选取与合并: 在F中选取根结点的权值最小的两棵二叉树分别作为左、右子树,构造一棵新的二叉树,这棵新二叉树的根结点的权值为其左、右子树根结点的权值之和。 (c)删除与加入: 在F中删除作为左、右子树的两棵二叉树,并将新建立的二叉树加入到F中。 (d)重复(b)和(c)两步,当集合F中只剩下一棵二
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 指导 手册