数据结构实验指导书（C版）

SeqList L; /*定义变量L为顺序表类型*/ Creat(&L, r, 5); /*建立具有5个元素的顺序表*/ printf(\当前线性表的数据为：\

PrintList(&L); /*输出当前线性表1 2 3 4 5*/

Insert(&L, 2, 8); /*在第2个位置插入值为8的元素*/ printf(\执行插入操作后数据为：\

PrintList(&L); /*输出插入后的线性表1 8 2 3 4 5*/

printf(\当前线性表的长度为：%d\\n\ /*输出线性表的长度6*/ printf(\请输入查找的元素值：\ scanf(\ i = Locate(&L, x);

if (0 == i) printf(\查找失败\\n\

else printf(\元素%d的位置为：%d\\n\ printf(\请输入查找第几个元素值：\ scanf(\

if (Get(&L, i, &x) == 1) printf(\第%d个元素值是%d\\n\ else printf(\线性表中没有第%d个元素\\n\ printf(\请输入要删除第几个元素：\ scanf(\

if (Delete(&L, i, &x) == 1) { /*删除第i个元素*/ printf(\删除第%d个元素是%d，删除后数据为：\

PrintList(&L); /*输出删除后的线性表*/ }

else printf(\删除操作失败\\n\return 0; }

2、链栈的实现

1. 实验目的

⑴掌握栈的链接存储结构； ⑵验证链栈及其基本操作的实现； ⑶验证栈的操作特性。 2. 实验内容

⑴建立一个空栈；

⑵对已建立的栈进行插入、删除、取栈顶元素等基本操作。 3. 实现提示

定义链栈中的结点结构（链栈中结点结构基于单链表相同），定义链栈的数据类型——链栈结构体，包括入栈、出栈、取栈顶元素等基本操作。本节的实验采用模板实现，要求学生：

3

（1）假设栈元素为字符型，修改主函数；

（2）重新设计测试数据，考查栈的上溢、下溢等情况，修改主函数。 4. 实验程序

在编程环境下新建一个工程“链栈验证实验”，并新建相应文件，文件包括链栈结构体的定义，范例程序如下：

typedef int DataType; /*栈元素的数据类型，假设为int型*/ typedef struct Node {

DataType data; /*存放栈元素的数据域*/ struct Node*next; /*存放下一个结点的地址*/

} Node;

Node *top;

/*栈顶指针*/

文件包括链栈初始化、入栈、出栈、获取栈顶元素、判空操作成员函数的定义，范例程序如下：

void InitStack(Node *top) {

top = NULL; }

void Push(Node *top, DataType x) {

Node *s = (Node *)malloc(sizeof(Node)); /*申请一个结点s*/ s->data = x;

s->next = top; top = s; /*将结点s插在栈顶*/ }

int Pop(Node *top, DataType *ptr) {

Node *p = top;

if (top == NULL) {printf(\下溢错误，删除失败\\n\

*ptr = top->data; /*存储栈顶元素*/ top = top->next; /*将栈顶结点摘链*/ free(p); return 1; }

int GetTop(Node *top, DataType *ptr) {

if (top == NULL) {printf(\下溢错误，取栈顶失败\\n\

4

*ptr = top->data; return 1; }

int Empty(Node *top) {

if (top == NULL) return 1; /*栈空则返回1*/ else return 0; }

在定义了链栈的存储结构并实现了基本操作后，可以调用实现基本操作的函数来完成相应的功能。范例程序如下： #include #include #include

/*将单链表的结点结构定义和链栈的各个函数定义放到这里*/ int main( ) {

DataType x;

Node *top = NULL; /*定义链栈的栈顶指针并初始化*/ InitStack(top); /*初始化链栈*/ printf(\对15和10执行入栈操作，\

Push(top, 15); Push(top, 10);

if (GetTop(top, &x) == 1)

printf(\当前栈顶元素为：%d\\n\ /*输出当前栈顶元素10*/ if (Pop(top, &x) == 1) printf(\执行一次出栈操作，删除元素：%d\\n \ /*输出出栈元素10*/

if (GetTop(top, &x) == 1)

printf(\当前栈顶元素为：%d\\n\ /*输出当前栈顶元素15*/ printf(\请输入待插入元素：\ scanf(\

Push(&S, x);

if (Empty(top) == 1) printf(\栈为空\\n\

else

printf(\栈非空\\n\ /*栈有2个元素，输出栈非空*/ DestroyStack(top);

return 0; }

3、前序遍历二叉树

1. 实验目的

5

⑴掌握二叉树的逻辑结构； ⑵掌握二叉树的二叉链表存储结构； ⑶验证二叉树的二叉链表存储及遍历操作。 2. 实验内容

⑴建立一棵含有n个结点的二叉树，采用二叉链表存储； ⑵输出前序遍历该二叉树的遍历结果。 3. 实现提示

定义二叉树的数据类型——二叉树结点结构体BiNode，在BiNode基础上实现题目要求的建立二叉链表、前序遍历等基本操作。建立二叉链表可以采用扩展二叉树的一个遍历序列，例如前序序列，将扩展二叉树的前序序列由键盘输入，建立该二叉树的二叉链表存储。

简单起见，本实验假定二叉树的数据元素为char型，要求学生： （1）将实验程序调试通过后，用模板类改写； （2）加入层序遍历二叉树等基本操作。 4. 实验程序

在编程环境下新建一个工程“二叉链表验证实验”，并新建相应文件，文件包括二叉树结构体的定义，范例程序如下： typedef char DataType; typedef struct BiNode {

DataType data;

struct BiNode *lchild, *rchild; } BiNode; BiNode *root;

文件包括建立二叉链表、前序遍历操作成员函数的定义，范例程序如下： BiNode* CreatBiTree(BiNode*root) {

char ch;

cin >> ch; /*输入结点的数据信息*

if (ch == '# ') root = NULL; /*递归结束，建立一棵空树*/ else {

root = (BiNode *)malloc(sizeof(BiNode)); /*生成新结点*/

root->data = ch; /*新结点的数据域为ch*/ root->lchild = Creat(root->lchild); /*递归建立左子树*/ root->rchild = Creat(root->rchild); /*递归建立右子树*/ }

return root; }

6