数据结构-基于C语言的描述第2版课件 第10章 课程实验

DATASTRUCTUREDATASTRUCTUREDataStructureBYPENGBO

数据结构课程实验与程序设计语言课程实验不同。数据结构课程中实验多属于创造性活动，需要自己进行问题分析、结构设计、算法编写、编码实现、上机调试以及程序测试。数据结构课程实验是一种自主性很强的学习过程。

第10章主要内容课程实验第章10《数据结构–基于C语言的描述》（第2版）-清华大学出版社DATASTRUCTUREDATASTRUCTUREDataStructureBYPENGBO第10章主要内容课程实验第章1010.1

实验概述10.2

实验内容《数据结构–基于C语言的描述》（第2版）-清华大学出版社10.1实验概述

数据结构实验是一种全面综合训练，实验多属于创造性的活动，需自己进行问题分析、结构设计、算法编写、编码实现、上机调试及程序测试。因此，数据结构实验是一种自主性很强的学习过程。10.1实验概述10.1.1教学目的

实要内容包括：线性表、栈和队列、数组和广义表、树和二叉树、图、查找、排序；每个内容更包括两类实验：验证实验和设计实验。其中：

（1）验证实验侧重点在于熟练掌握基本数据结构，而不强调面面俱到；

（2）设计实验主要内容是针对具体问题，应用某几个知识点，自己设计方案，并上机实现，目的是培养读者对数据结构的综合应用能力。本章要达到的学习目的如下：

●深化理解和掌握书本上的理论知识，将书本上的知识变“活”

●学会如何把书本上有关数据结构和算法的知识用于解决实际问题

●培养数据结构的应用能力和软件工程所需要的实践能力10.1实验概述10.1.2实验步骤拿到一个题目后，一般不要急于编写代码，而是首先要理解问题，明确给定的条件和要求解决的问题，然后按照自顶向下、逐步求精、分而治之的策略，逐一解决子问题。具体步骤如下：

（1）问题分析和任务定义；

（2）数据类型和系统设计（包括概要设计和详细设计）；

（3）算法转化和编码实现；

（4）上机测试和程序调试。10.2实验内容

课程实验的侧重点在于基本的数据结构，而不强调面面俱到。通过实践，对常用数据结构的基本概念以及不同实现方法得到进一步的掌握，并对在不同存储结构上实现不同的运算方式和技巧有所体会。10.2实验内容10.2.1线性表●实验1顺序表基本操作【题目】

线性表采用顺序存储结构，实现如下任务：（1）初始化顺序表InitList_Sq(SqList&L)；（2）创建顺序表CreatList_Sq(SqList&L)；（3）插入第i个元素InsertElem_Sq(SqList&L,inti,ElemTypee)；（4）删除第i个元素DeleteElem_Sq(SqList&L,inti,ElemType&e)；（5）输出顺序表元素TraverseList_Sq(SqListL)；（6）销毁顺序表DestroyList_Sq(SqListL)。

验证实验10.2实验内容10.2.1线性表●实验1顺序表基本操作【输入】（1）线性表长及线性表元素；（2）插入位置及元素；（3）删除位置。【输出】（1）创建的顺序表；（2）插入元素后的顺序表。若插入位置不合理，则给出相应信息；若插入元

素后溢出，则给出相应信息；（3）删除的元素；（4）删除元素后的顺序表。若删除位置不合理，则给出相应信息。

验证实验10.2实验内容10.2.1线性表●实验2单链表基本操作

验证实验【题目】

线性表采用链式存储结构，实现如下任务：（1）初始化单链表InitList_L(LinkList&L)；（2）创建单链表CreatList_L(LinkList&L)；（3）求出第i个元素GetElem_L(LinkListL,inti,ElemType&e)；（4）求出给定元素的位置LocateElem_L(LinkListL,ElemTypee)；（5）求出给定元素的前驱元素PreElem_L(LinkListL,ElemTypee)；（6）求出给定元素的后继元素NextElem_L(LinkListL,ElemTypee)；（7）插入第i个元素ListInsert_L(LinkList&L,inti,ElemTypee)；（8）删除第i个元素ListDelete_L(LinkList&L,inti,ElemType&e)；（9）输出单链表元素TraverseList_L(LinkListL)；（10）销毁单链表DestroyList_L(LinkListL)。10.2实验内容10.2.1线性表●实验2单链表基本操作

验证实验【输入】（1）线性表长及元素；（2）待取出元素的位置；（3）待查找的元素；（4）插入位置及元素；（5）删除位置。【输出】（1）创建的单链表；（2）给定位置元素。若不存在则输出相应信息；（3）查找元素位置。若不存在则给出相应信息；（4）给定元素前驱元素。若不存在则给出相应信息；（5）给定元素后继元素。若不存在则给出相应信息；（6）插入元素后单链表。若插入位置不合理则输出

相应信息；（7）删除元素及删除元素后单链表。若删除位置不

合理，则给出相应信息。10.2实验内容10.2.1线性表

设计实验●实验3一元多项式相加问题【题目】

已知A(x)=a0+a1x+……+anxn和B(x)=b0+b1x+……+bmxm，且在A(x)和B(x)中指数相差很多，求A(x)=A(x)+B(x)。要求：（1）设计此两个多项式的数据结构；（2）设计两个多项式相加算法，且除两个多项式所占空间外不开辟新空间；（3）分析算法的时间复杂度。【输入】（1）多项式A(x)中每一项的系数和指数（以系数=0和指数=0表示结束）；（2）多项式B(x)中每一项的系数和指数（以系数=0和指数=0表示结束）。【输出】两个多项式相加的结果。10.2实验内容10.2.1线性表

设计实验●实验4约瑟夫环问题【题目】

设有编号为1，2，……的n（n>0）个人围成一个圈，每人持有一个密码m，从第1人开始报数，报到m时停止，报m的人出局，再从其下一个人重新报数，报到m时停止，报m的人出局，……，如此继续直到剩下最后一个人为获胜者。给定n和m，设计算法求n个人出局次序及获胜者。要求：（1）建立模型，确定存储结构；（2）对任意n个人，密码为m，实现约瑟夫环；（3）分析算法的时间复杂度。【输入】（1）参与人数；（2）出局密码。【输出】（1）参与人的编号；（2）顺序出局的人；（3）获胜人的编号。10.2实验内容10.2.2栈和队列●实验1顺序栈基本操作【题目】

栈采用顺序存储结构，实现如下任务：（1）初始化顺序栈InitStack_Sq(SqStack&S)；（2）创建顺序栈CreateStack_Sq(SqStack&S)；（3）入栈Push_Sq(SqStack&S,ElemTypee)；（4）出栈Pop_Sq(SqStack&S,ElemType&e)；（5）输出顺序栈元素TraverseStack_Sq(SqStackS)；（6）销毁顺序栈DestroyStack_Sq(SqStackS)。

验证实验【输入】栈的元素个数及元素值。【输出】（1）创建的顺序栈；（2）出栈后的栈元素。●实验2链队列基本操作【题目】

队列采用链存储结构，实现如下任务：（1）初始化链队列InitQueue_L(LinkQueue&Q)；（2）创建链队列CrwateQueue_L(LinkQueue&Q)；（3）入队EnQueue_L(LinkQueue&Q,ElemTypee)；（4）出队DeQueue_L(LinkQueue&Q,ElemType&e)；（5）输出链队列元素TraverseQueue_L(LinkQueueQ)；（6）销毁链队列DestroyQueue_L(LinkQueueQ)。

验证实验10.2实验内容10.2.2栈和队列【输入】队列的元素个数及元素值。【输出】（1）创建的链队列；（2）出队后的队列元素。●实验3表达式求值问题

设计实验【题目】

对一个合法的中缀表达式求值。假设表达式只包含+、-、×、÷四个双目运算符，且运算符本身不具有二义性。只能进行整数四则运算，支持小括号。对不能整除的将按两个整数除法规则进行取整。要求：（1）正确解释表达式，符合四则运算规则；（2）输出计算过程和最后计算结果；（3）分析算法的时间复杂度。10.2实验内容10.2.2栈和队列【输入】表达式。【输出】（1）表达式求值过程；（2）表达式求值结果。●实验4双端队列问题【题目】

双端队列是插入和删除可在两端进行的线性表，表两端分别称作端点1和端点2。设计双端队列数据结构，实现入队、出队基本操作。要求：（1）设计存储结构表示双端队列；（2）设计双端队列插入和删除算法；（3）分析算法的时间复杂度。10.2实验内容10.2.2栈和队列

设计实验【输入】（1）队列元素个数，以及入队元素值；（2）分别从端点1和端点2入队的元素值；【输出】（1）创建的队列；（2）从端点1入队后队列，以及从端点2入队后队列；（3）从端点1出队元素值和出队后队列，以及从端点2出队元素值和出队后队列。10.2实验内容10.2.3串

验证实验●实验1串基本操作【题目】

实现如下任务：（1）创建串a、串b、串c、串d的堆分配顺序表；（2）输出串a和长度、串b和长度、串c和长度、串d和长度；（3）将串b合并到串a上，并输出合并后的串a和长度；（4）将串c插入到串a的第i个位置上，并输出插入后的串a和长度；（5）用串d替换串a从第i个位置开始连续len个字符，并输出替换后的

串a和长度。10.2实验内容10.2.3串

验证实验●实验1串基本操作【输入】（1）串a、串b、串c、串d；（2）将串c插入到串a的位置i；（3）用串d替换串a的起始位置i和字符个数len。【输出】（1）串a和长度、串b和长度、串c和长度、串d和长度；（2）将串b合并到串a上后的串a和长度；（3）将串c插入到串a的第i个位置上后的串a和长度；（4）用串d替换串a从第i个位置开始连续len个字符后的串a和长度。

验证实验●实验2比较两个串大小【题目】

完成串比较运算Strcmp(s,t)。实现如下任务：（1）如果s大于t，则Strcmp(s,t)=1；（2）如果s等于t，则Strcmp(s,t)=0；（3）如果s小于t，则Strcmp(s,t)=-1。10.2实验内容10.2.3串【输入】串s和串t。【输出】比较结果（Strcmp(s,t)值）。

设计实验●实验3求最长连续相同字符平台问题【题目】如果输入一个串是"2018ssss10ssssss"，则输出的第一个最长平台就是"ssssss"。要求：实现求解串S中出现的第一个最长的连续相同字符构成的平台，并分析算法的时间复杂度。10.2实验内容10.2.3串【输入】字符串。【输出】第一个最长的连续相同字符构成的平台。

设计实验●实验4BF算法实现模式匹配问题【题目】从主串S="s1s2…sn"的第pos个字符开始寻找模式T="t1t2…tm"的过程，通常称为模式匹配（PatternMatching）。要求：如果匹配成功则返回T在S中的位置，如果匹配失败则返回0，并分析算法的时间复杂度。10.2实验内容10.2.3串【输入】（1）主串字符；（2）模式字符；（3）起始位置。【输出】模式匹配结果。10.2实验内容10.2.4数组和广义表

验证实验●实验1三元组顺序表基本操作【题目】

实现如下任务：（1）创建三元组顺序表CreateSMatrix_TSM(TSMatrix&M)；（2）输出三元组顺序表元素TraverseSMatrix_TSM(TSMatrixM)；（3）使用直接取、顺序存方法转置TransSMatrix_TSM(TSMatrixM,TSMatrix&T)。【输入】（1）稀疏矩阵的行数、列数、非零元个数；（2）按照行优先顺序输入稀疏矩阵的非零元值。【输出】（1）原三元组顺序表；（2）使用直接取、顺序存转置算法转置后的三元组顺序表。

验证实验●实验2对称矩阵相乘【题目】

已知两个n×n的对称矩阵按压缩存储方法存储在一维数组A和B中，完成对称矩阵A和B相乘。实现如下任务：（1）输入时对称矩阵只输入下三角形元素，存入一维数组；（2）A×B的结果存入二维数组，并输出。10.2实验内容10.2.4数组和广义表【输入】（1）对称矩阵的行数（即列数）；（2）对称矩阵A的下三角形元素；（3）对称矩阵B的下三角形元素。【输出】A×B的结果。

设计实验●实验3魔方阵问题【题目】魔方阵，又叫幻方阵，在我国古代称为“纵横图”。它是在一个n×n的矩阵中填入1到n2

的数字（n为奇数），使得每一行、每一列、每条对角线的累加和都相等。下图是一个3阶魔方阵。要求：（1）设计存储结构表示魔方阵；（2）设计算法完成n阶魔方阵的填数；（3）分析算法的时间复杂度。10.2实验内容10.2.4数组和广义表【输入】方阵阶数n（1

n

15，且为奇数）。【输出】填数后的n阶魔方阵。

设计实验●实验4广义表元素查找问题【题目】

在创建好的广义表存储结构中，查找给定元素。要求：（1）创建广义表的存储结构；（2）在广义表中查找给定元素；（3）分析算法的时间复杂度。10.2实验内容10.2.4数组和广义表【输入】（1）字符序列（广义表书写形式）；（2）输入要查找的元素。【输出】（1）创建的广义表；（2）查找结果。●实验1树的二叉链表基本操作【题目】

实现如下任务：（1）初始化树二叉链表InitTree(CSTree&T)；（2）创建树二叉链表CreateTree(CSTree&T)；（3）先序遍历树PreOrderTraverse(CSTreeT)；（4）后序遍历树PostOrderTraverse(CSTreeT)；（5）层序遍历树FloorTraverse(CSTreeT)；（6）销毁树二叉链表DestroyTree(CSTreeT)。10.2实验内容10.2.5树和二叉树

验证实验【输入】树的元素。【输出】（1）先序遍历序列；（2）后序遍历序列；（3）层序遍历序列。10.2实验内容10.2.5树和二叉树●实验2二叉树的二叉链表基本操作【题目】

实现如下任务：（1）初始化二叉树二叉链表InitBiTree(BiTree&BT)；（2）创建二叉树二叉链表CreateBiTree(BiTree&BT)；（3）先序遍历二叉树PreOrderBiTree(BiTreeBT)；（4）中序遍历二叉树InOrderBiTree(BiTreeBT)；（5）后序遍历二叉树PostOrderBiTree(BiTreeBT)；（6）销毁二叉树二叉链表DestroyBiTree(BT)。

验证实验【输入】二叉树的元素。【输出】（1）先序遍历序列；（2）中序遍历序列；（3）后序遍历序列。

设计实验●实验3判断两棵二叉树是否相似问题【题目】如果已知两棵二叉树B1和B2皆为空，或者皆不空且B1的左、右子树和B2的左、右子树分别相似，则称二叉树B1和B2相似。要求：（1）设计算法并实现，判别给定两棵二叉树是否相似；（2）分析算法的时间复杂度。10.2实验内容10.2.5树和二叉树【输入】（1）第1棵二叉树的字符序列（按照先序顺序，空树用字符'#'表示）；（2）第2棵二叉树的字符序列（按照先序顺序，空树用字符'#'表示）。【输出】（1）第1棵二叉树创建成功信息，以及第1棵二叉树先序序列；（2）第2棵二叉树创建成功信息，以及第2棵二叉树先序序列；（3）判别给定两棵二叉树是否相似信息。

设计实验●实验4哈夫曼编码问题【题目】

利用哈夫曼编码通讯可提高信道利用率，缩短信息传输时间，降低传输成本。这要求在发送端通过一个编码系统对待传数据进行预先编码；在接受端将传来的数据进行解码。对于双工信道，每端都要有一个完整的编/译码系统。试为这样的信息收发站设计一个哈夫曼的编码系统。要求：（1）输入字符集大小n、n个字符和权值，建立哈夫曼树，进行前缀编码；（2）利用已建好的哈夫曼编码，对输入的正文编码，并输出该文二进制码。（3）分析算法的时间复杂度。10.2实验内容10.2.5树和二叉树【输入】（1）字符集大小n；（2）n个字符；（3）n个权值。【输出】（1）创建哈夫曼树成功信息；（2）字符集中所有字符的哈夫曼编码；（3）输入正文的编码。10.2实验内容10.2.6图●实验1邻接矩阵的基本操作【题目】

实现如下任务：（1）创建无向图邻接矩阵CreateUDG_MG(MGraph&G)；（2）输出无向图邻接矩阵TraverseUDG_MG(MGraphG)；（3）深度优先遍历DFSTraverseUDG_MG(MGraphG)；（4）广度优先遍历BFSTraverseUDG_MG(MGraphG)。

验证实验【输入】（1）无向图顶点数和边数；（2）无向图中的顶点信息；（3）图各边的起点和终点。【输出】（1）无向图的邻接矩阵；（2）深度优先遍历序列；（3）广度优先遍历序列。●实验2有向图邻接表基本操作【题目】

实现如下任务：（1）创建有向图邻接表CreateDG_ALG(ALGraph&G)；（2）输出有向图邻接表TraverseDG_ALG(ALGraphG)；（3）深度优先遍历DFSTraverseDG_ALG(ALGraphG)；（4）广度优先遍历BFSTraverseDG_ALG(ALGraphG)；（5）销毁有向图邻接表DestroyDG_ALG(ALGraphG)。

验证实验10.2实验内容10.2.6图【输入】（1）有向图顶点数和弧数；（2）有向图中的顶点信息；（3）图中各弧起点和终点。【输出】（1）有向图的邻接表；（2）深度优先遍历序列；（3）广度优先遍历序列。●实验3学生选修课程问题

设计实验【题目】

下图给出了学生应该学习的课程。学生应该按照怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业？要求：（1）设计存储结构表示课程及课程之间的关系；（2）实现学生无矛盾、顺利地完成学业的课程顺序；（3）分析算法的时间复杂度。10.2实验内容10.2.6图【输入】课程数、课程，以及课程关系。【输出】无矛盾、顺利地完成学业的课程顺序。●实验4建造物流配送中心问题

设计实验【题目】给定4个城市之间的交通图如下图所示（图中弧上数字表示城市之间的道路长度）。要在4个城市之间选择一个城市建造一个物流配送中心，并使得到物流配送中心最远的城市到物流配送中心的路程最短。要求：（1）设计存储结构表示城市及城市之间的关系；（2）求出物流配送中心最远城市到物流配送中心的最短路程；（3）分析算法的时间复杂度。5个城市交通图10.2实验内容10.2.6图●实验4建造物流配送中心问题

设计实验【输入】（1）城市数和城市关系数；（2）城市；（3）城市关系和权值。【输出】（1）建造物流配送中心的城市；

（2）物流配送中心最远城市到物流配送中心的最短路径及其长度。10.2实验内容10.2.6图10.2实验内容10.2.7查找●实验1顺序表的查找【题目】

实现如下任务：创建顺序表，采用顺序查找技术查找表中与输入值k相等的元素。若查找成功，则给出其比较次数以及在表中位置；若查找不成功，则给出相应信息。

验证实验【输入】（1）顺序表元素个数及元素值；（2）待查元素k。【输出】（1）创建的顺序表；（2）待查元素的比较次数；（3）查找成功时，待查元素在表中位置；查找不成功时，相应信息。●实验2有序表的查找【题目】

实现如下任务：创建有序表，采用折半查找技术查找表中与输入值k相等的元素。若查找成功，则给出其比较次数以及在表中位置；若查找不成功，则给出相应信息。

验证实验10.2实验内容10.2.7查找【输入】（1）有序表元素个数及元素值；（2）待查元素k。【输出】（1）创建的有序表；（2）待查元素的比较次数；（3）查找成功时，待查元素在表中位置；查找不成功时，相应信息。●实验3二叉排序树查找问题【题目】在二叉排序树中动态查找输入值为k的元素。要求：（1）创建二叉排序树；（2）如果查找成功，则给出其比较次数；（3）如果查找不成功，则给出其比较次数，并将待查元素插入二叉排序树。

设计实验10.2实验内容10.2.7查找【输入】（1）一组无序序列；（2）待查元素k。【输出】（1）创建的二叉排序树；（2）待查元素的比较次数；（3）查找不成功时相应信息，及插入待查元素后二叉排序