《数据结构》课程实验指导书
扬州大学信息工程学院
实验一 线性表
一、实验目的
1．掌握用C语言上机调试线性表的基本方法。 2．掌握线性表的基本操作。 二、实验内容
创建并打印一个单链表。
三、基本要求
要求生成线性表时，从键盘上读取元素，用链式存储结构（单链表）实现存储。单链表数据元素限定为非”0”整数，单链表的长度不限，数据元素输入的以”0”为结束标志。 四、参考程序
实验二 栈
一、实验目的
1．掌握栈的特点，即先进后出的原则。 2．掌握栈的存储结构。
3．掌握栈的基本运算，如入栈、出栈等运算及其实现。 二、实验内容
判断表达式中开、闭括号是否配对出现。
三、基本要求
运用栈实现表达式开、闭括号是否配对出现算法。先要实现栈的基本操作算法，包括初始化栈、进栈、退栈等。本程序中，表达式中的元素限定为char型，表达式的长度<100。表达式输入的为一个以“#”为结束标志的字符串。若用户输入的表达式中少了左括号或少了右括号，打印“括号不匹配”。若输入的表达式左右括号匹配，打印“括号匹配”。 四、参考程序
1
实验三 数组
一、实验目的
了解数组的存储表示方法及其运算。
二、实验内容
若矩阵A中的某一元素A[i，j]是第i行中的最小值，而又是第j列中的最大值，则称A[i，j]为矩阵A中的一个鞍点。请写出一个可确定此鞍点位置的算法（如果这个鞍点存在）。 三、基本要求
要求算法要考虑某行中具有多个相同的且又是该行中最小的元素的情况。四、参考程序
2
实验四 二叉树
一、实验目的
1．进一步掌握指针变量、动态变量的含义。
2．掌握二叉树的结构特性，以及各种存储结构的特点及适用范围。 3．掌握用指针类型描述、访问和处理二叉树的运算。 二、实验内容
实现二叉树的遍历。 三、基本要求
以二叉链表表示二叉树，实现二叉树先序遍历、中序遍历、后序遍历的递归算法；直接利用栈的基本操作，实现二叉树先序遍历的非递归算法。 四、参考程序
3
