《数据结构》实验指导书由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构实验指导书c”。
数 据 结 构 实 验 指 导 书
南京工程学院
信息管理与信息系统教研室
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个数据元素是：%6dn”,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.读栈顶元素的算法与退栈顶元素的算法有何区别？试写一个算法，判别读入的一个以‘@’为结束符的字符序列是否是‚回文‛。实验三 树操作
一、实验目的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;}
五、思考与提高
编写递归算法，计算二叉树中叶子结点的数目。
目 录 实验一线性表、栈和队列的基本操作............................................................1 实验二二叉树的基本操作............................................
目 录 实验规则················································2 实验环境····················......
《数据结构》实验(训)指导书电气与信息工程学院实验中心 前 言《数据结构》是计算机相关专业的一门核心基础课程，也是很多高校研究生入学考试专业课必考课程之一。它主要介绍......
石 家 庄 铁 道 大 学实 验 任 务 书课程名称： 数据结构 实验学时： 8 适用专业： 自动化类专业 开设学院： 电气与电子工程学院 石 家 庄 铁 道 大 学14学年—15学年第 2学期 数......
数 据 结 构 实 验 指 导 书数据结构实验指导书目录数据结构实验指导书 ...................................................................................................
