数 据 结 构 实 验 指 导 书
南京工程学院
信息管理与信息系统教研室
2014年3月
实验一 线性表操作
一、实验目的
1.熟悉C语言的上机环境，进一步掌握C语言的结构特点。 2.掌握线性表的顺序存储结构的定义及C语言实现。
3.掌握线性表的链式存储结构——单链表的定义及C语言实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。
二、实验内容
1.顺序线性表的建立、插入及删除。
2.链式线性表的建立、插入及删除。
三、实验步骤
1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插入元素68。
3.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。
四、实现提示
1.由于C语言的数组类型也有随机存取的特点，一维数组的机内表示就是顺序结构。因此，可用C语言的一维数组实现线性表的顺序存储。
在此，我们利用C语言的结构体类型定义顺序表： #define MAXSIZE 1024 typedef int elemtype; /* 线性表中存放整型元素 */ typedef struct { elemtype vec[MAXSIZE]; int len; /* 顺序表的长度 */ }sequenlist; 将此结构定义放在一个头文件sqlist.h里，可避免在后面的参考程序中代码重复书写，另外在该头文件里给出顺序表的建立及常量的定义。
2.注意如何取到第i个元素，在插入过程中注意溢出情况以及数组的下标与位序（顺序表中元素的次序）的区别。
3.单链表的结点结构除数据域外，还含有一个指针域。用C语言描述结点结构如下：
typedef int elemtype; typedef struct node { elemtype data; //数据域
struct node *next; //指针域
}linklist; 注意结点的建立方法及构造新结点时指针的变化。构造一个结点需用到C语言的标准函数malloc()，如给指针变量p分配一个结点的地址：
p=(linklist *)malloc(sizeof(linklist));该语句的功能是申请分配一个类型为linklist的结点的地址空间，并将首地址存入指针变量p 中。当结点不需要时可以用标准函数free(p)释放结点存储空间，这时p为空值（NULL）。
五、思考与提高
1.如果按由表尾至表头的次序输入数据元素，应如何建立顺序表。 2.在main函数里如果去掉L=&a语句，会出现什么结果？
实验二
栈和队列的应用
一、实验目的
1.掌握栈的顺序表示和实现 2.掌握队列的链式表示和实现
二、实验内容
1.编写一个程序实现顺序栈的各种基本运算。 2.实现队列的链式表示和实现。
三、实验步骤
1.顺序栈 (1)初始化顺序栈; (2) 插入元素 (3) 删除栈顶元素 (4) 取栈顶元素 (5) 遍历顺序栈 (6) 置空顺序栈 2.链队列
(1) 初始化并建立链队列 (2.)入链队列 (3) 出链队列 (4) 遍历链队列
四、实现提示
1./*定义顺序栈的存储结构*/ typedef struct { ElemType stack[MAXNUM]; int top; }SqStack;
/*初始化顺序栈函数*/ void InitStack(SqStack *p)
{q=(SqStack*)malloc(sizeof(SqStack) );/*申请空间*/} /*入栈函数*/ void Push(SqStack *p,ElemType x) {if(p->toptop=p->top+1; /*栈顶+1*/ p->stack[p->top]=x; } /*数据入栈*/ } /*出栈函数*/ ElemType Pop(SqStack *p) {x=p->stack[p->top]; /*将栈顶元素赋给x*/ p->top=p->top-1; } /*栈顶-1*/ /*获取栈顶元素函数*/ ElemType GetTop(SqStack *p) { x=p->stack[p->top];} /*遍历顺序栈函数*/ void OutStack(SqStack *p) { for(i=p->top;i>=0;i--) printf(\"第%d个数据元素是：%6d\\n\",i,p->stack[i]);} /*置空顺序栈函数*/ void setEmpty(SqStack *p) { p->top= -1;} 可参考代码： #include \"stdio.h\" #define StackSize 100 typedef int ElemType; main() {
SqStack S;
ElemType e;
int N;
/*初始化顺序栈*/ /*入栈*/ /*出栈*/ /*遍历顺序栈*/ getch(); }
2./*定义链队列*/ typedef struct Qnode { ElemType data; struct Qnode *next; }Qnodetype; typedef struct { Qnodetype *front; Qnodetype *rear; }Lqueue;
/*初始化并建立链队列函数*/ void creat(Lqueue *q)
{ h=(Qnodetype*)malloc(sizeof(Qnodetype)); /*初始化申请空间*/ h->next=NULL; q->front=h; q->rear=h; for(i=1;idata=x; s->next=NULL; q->rear->next=s; q->rear=s;} /*出链队列函数*/ ElemType Ldelete(Lqueue *q) { p=q->front->next; q->front->next=p->next; if(p->next==NULL) q->rear=q->front; x=p->data; free(p);} /*释放空间*/ /*遍历链队列函数*/ void display(Lqueue *q) { while(p!=NULL) /*利用条件判断是否到队尾*/ { printf(\"%d-->\",p->data); p=p->next; } } 可参考如下代码： #include \"stdio.h\" #define MaxSize 100 typedef int ElemType; main() {
LinkQueue Q;
ElemType e;
/*初始化并建立链队列*/
/*入链队列*/ /*出链队列*/
*遍历链队列*/
}
DestoryQueue(&Q);
getch(); }
五、思考与提高
1.读栈顶元素的算法与退栈顶元素的算法有何区别？
2 试写一个算法，判别读入的一个以‘@’为结束符的字符序列是否是‚回文‛。 实验三 树操作
一、实验目的
1.通过实验，掌握二叉树的建立与存储 2.通过实验，掌握二叉树的遍历方法
二、实验内容
1.练习二叉树的建立与存储 2.练习二叉树的遍历
三、实验步骤
1.建立二叉链表的结构描述、二叉树的建立、二叉树的先序、中序与后序遍历算法。
2.建立二叉树,并通过调用函数, 输出先序遍历、中序遍历与后序遍历的结果。
四、实现提示
1.采用递归方法建立二叉树：
首先建立二叉树的根 结点，然后建立其左右子树，直到空子树为止。
2.先序遍历、中序遍历与后序遍历二叉树。 #include #include typedef int Status; typedef char ElemType; typedef struct BiTNode { ElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; /*建立二叉树*/
BiTree CreateBiTree(BiTree &T) { } /*先序遍历*/ Status PreOrderTraverse(BiTree T) { } /*中序遍历*/ Status InOrderTraverse(BiTree T) { } /*后序遍历*/ Status PostOrderTraverse(BiTree T) { }
int main() { BiTree T; CreateBiTree(T); PreOrderTraverse(T); printf(\"\\n\"); /*先序遍历*/ InOrderTraverse(T); printf(\"\\n\"); /*中序遍历*/ PostOrderTraverse(T); printf(\"\\n\"); /*后序遍历*/
return 0; }
五、思考与提高
编写递归算法，计算二叉树中叶子结点的数目。
