数据结构实验讲义.ppt

数据结构和算法实验讲座，发表者：赵喜联系方式：工作单位：实验楼1-401楼电话：件：539051256电子邮件：hx，实验一c语言复习，教育目的和要求本实验的目的大家都是c语言的使用方法，特别是指导、 帮助复习结构内容，以及今后各实验的准备教学重点和难点指针、结构、数组3种数据类型的混合使用、实验预习检查内容、指针指向数组后，数组元素的访问有哪些形式？ 定义以下类型后，表达式a3.num的逻辑含义是什么？ 类型是什么structstudentlongnum； 浮点核心； structstudent*next； a5；3号元素的num数据域long型、例题、# define null0struct student long num； 浮点核心； structstudent*next； main()structstudenta，b，c，*head，*p； a.num=99101； a.score=89.5； b.num=99103； b.score=90； c.num=99107； c.score=85； /a、b、c变量代入，head=p=a；=P=，第二讲义性表，要求把握教育目的和数据结构中表的基本概念。 熟悉线性表的基本操作，通过顺序存储结构和链接存储结构实现插入、删除、检索等运算。 熟悉链表的各种操作和应用。 教学重点和难点线性表的基本操作是链接记忆结构上的实现。 预习检查内容，主结构# include # define maxlen 50 typedefinetelemtype； 结构数据类型 elemtype * elem； intlength； typedefstructdatatypesqlist；voidcreate(sqlist*a)inti，n； a-elem=(elemtype * ) malloc (maxlen * sizeof (elemtype )； printf (创建序列表n ) : printf (输入元素数目) scanf(“%d”，=temp； ，(1) * (a-elemi ) (2) * (a-elema-length-1-I ) (3) * (a-elema-length-1-I )、*(voidsdisp(sqlist*a)inti； for(i=0； ielem i )； ，voidmain()sqlistb，*a； a=create (a ) disp (a ) invert (a ) disp (a ) ，例题，一个链路表的第一个节点指针为head，反转该链路表的函数，即最后的节点是第一个节点，倒数第二个节点是第二个节点。 实验内容和要求，4，7，13必须进行，其馀老师选择几题4，键盘输入学生信息(包括学号和成绩)，以学号0为结束标志，制作对应的线性表，输出各节点的数据。 注意：请尝试用顺序表和单链接表两种不同的记忆结构来实现。 设计七、一个算法求a和b两个单链表示集合的和集合。 提示：合并a和b。 9 .将单链表b中单链表a中未出现的节点用插件方法合并到单链表a中。 实验三堆栈和队列，教学目的和要求可以理解堆栈和队列的特性，灵活应用。 熟悉堆栈和队列的各种操作和应用。 教育重点和难点堆栈和相关队列的各种操作和应用，实验预习检验内容，1，堆栈指针是堆栈顶部元素的地址或堆栈顶部元素的地址，标准是什么，由程序员自己决定，在堆栈和堆栈操作时实现。 2、在实际应用中，采用普通队列还是循环队列的依据是什么？答：在实际应用中，是否存在假溢出问题。 在例题中，在链接表中存储n个字符，设计算法，利用堆栈判断该字符串是否是中心对称。 例如，假设abccba是中心对称字符串，根据问题填写完备程序，首先使用create ()函数从用户输入的字符串创建相应的链接表，调用judge ()函数来判断是否是中心对称字符串。 judge ()函数首先将字符串放在堆栈中，然后将堆栈中的字符与链接表中的字符进行比较。 实验内容和要求，3、4必定要做，5选择3，在算术式中加入括号、方括号、方括号这3种括号，制作判断其中括号是否一致的算法。 4、在医院就诊的过程中，患者先排队等候，排队等候主要重复两件事： (1)患者到诊室时，将病历交给护士，排队等候诊察。 (2)护士从队列中取出下一位患者的病历，该患者进入诊察室就诊。5、设计程序，演示用算子优先法评价算术式的过程。 基本要求：从终端输入语法正确、不包含变量的整数表达式作为字符串。 利用教科书表3.1中给出的运算符优先关系，实现算术四则混合运算式的评价，按照教科书的例子3_1，显示评价中的运算符堆栈、运算数堆栈、输入文字和主要操作的变化过程。 测试数据：3*(7-2)，为完成实验内容和要求，讨论，第三题，下列步骤是否正确：实验四列，教学目的和要求掌握字符串的基本概念，记忆方法和主要运算。 将字符串运算应用于文本编辑。 教学重点和难点部分列操作、实验预习检查内容、列顺序记忆结构有哪两种记忆方式？ 答：静态分配和动态分配的序列存储结构。 静态分配： typedef struct charch max strlen ； intlengthsstring； 动态分配： typedefstructchar*ch； intlength； hsring； 例题，接下来是替换函数，以顺序存储方式存储串，用s2串替换包括从串s1中的第I个字符开始的第j个字符(包括第I个字符)的子串，并且将函数名称转换成replace(s1，I，j，s2)。 示例： replace(“abcd”，1，3，XYZ”)返回“xyzd”。 (空白栏)提示：在s1中提取由位置I之前的所有字符构成的部分列str1，提取由位置I j-1以后的所有字符构成的部分列str2，最后连接str1、s2、str2来构成结果列。 实验内容和要求，3，4必须做，5选择3，采用顺序结构存储列，写出s2是否为s1的部分列的函数index(s1，s2)。 如果是，则返回主字符串中的位置，否则返回-1。 4、基本运算单元创建用于删除串s1的所有s2子串的算法。 提示：本问题通过3题的index ()函数和删除部分列函数循环实现。 5、已知的s=“(xyz) *、t=“(x z)*y”。 试着利用连接、子字符串的求出、置换等操作，将s转换为t。 实验内容和要求，实验五序列和广义表，教学目的和熟练掌握序列的记忆表达和实现。 熟悉广义表格记忆结构的特性。 教学重点和难点序列的记忆表示和常用操作的实现，实验预习检查内容，序列和一般线性表有什么区别？ 答：为什么数组结构固定数据元素是相同的并且数组元素是可随机访问的？可以从地址计算公式中获得任何元素的地址、例题，假定数组R0.n-1的n个元素中有多个零元素，并且将r中的所有非零元素顺序移到r数组的开头的算法提示：用I指定应附加在非0要素上的下标，j遍历r，当Rj不是0时，I和j不同时，交换RI和Rj。实验内容和要求，3、6必须设计3、1个算法，将A0.n-1的所有奇数移动到偶数之前。 需要时间复杂性为O(n )，而不添加存储空间。 提示： I从左到右，指a的左偶数，j从右到左，指a的右奇数，交换Ai和Aj。 循环直到I大于等于j。 6、稀疏矩阵运算器的基本要求：“用具有行逻辑链路信息的三元组顺序表示稀疏矩阵，实现两个矩阵的相加、减法和乘法运算。 稀疏矩阵的输入格式以三元数组表示，运算结果的矩阵以常规数组格式列出。 掌握实验内容和要求、实验六树、教学目的和要求1 .二叉树、二叉树顺位数的概念和记忆方法。 2 .掌握二叉树的扫描算法。 3 .熟练创建实现树的各种运算的算法。 教学重点和难点二叉树的扫描操作及其应用，实验预习检验内容，1，以下程序段的功能是什么？2，二叉树的扫描常用方法是什么？答： 1，编制排序树2，序言，中序，后序，层次，例题，求二叉树的节点数和叶数，实验内容和要求，3，4必须是3，编程4、编制程序，依次扫描二叉树，印刷层号。 实验7图，教学目的和要求1 .熟悉图的各种记忆方法。2 .掌握遍历图的递归和非递归算法。 3 .理解图的相关算法。 实现教学重点和难点图的制作和图的常用操作，实验预习检查内容，以下程序的功能是什么图的存储结构？ 在制作a:1、图2的该程序中，图中的存储结构在邻接表、例题中设计算法，判断无向图g是否连接。 返回连通和1否则返回0。 实验内容和要求，2、3必须编制2、程序，实现无向图的深度优先搜索。 3、有存储有邻接表的图g，分别设计用于实现求出图中的各顶点的曝光度的要求的算法，计算图中的曝光度为0的顶点数。 掌握实验八检索、教学目的和要求1 .顺序检索、二分法检索和块检索的算法。 2 .线性表的检索方法可以解决实际问题。 教学重点和难点的顺序检索，二分检索的实现和应用，实验预习检查内容，顺序检索，二分检索的对象有什么不同？ 另外，按照：的顺序检索的对象可以是秩序或无序的表，二进制检索的对象必须是规则表，依次检索、二进制检索的对象分别是什么？3360的顺序检索对象可以是顺序表或链接表，二进制检索的对象仅仅是顺序表或例题，在一个无序表a中使用顺序检索算法实验内容和要求，2一定要做，3选择2，给一个升序规则表a提供用二分搜索算法找值x要素的递归算法，实验排九，教学目的和要求1 .把握各种排序方法的基本思想和优缺点。 2 .理解各种排序方法的依据原则，以便根据情况选择适当的排序方法。 教育的重点和难点是各种排序方法的实现和应用，实验预习检验内容，快速排序的基本思想是什么？是将要排序的记录在一次排序中