数据结构实验指导与课程设计教程(陈建新 李志敏)(上)
- 格式：doc
- 大小：88.50 KB
- 文档页数：23
2、数据结构设计
顺序循环队列的数据类型：
#define MaxSize 100/*最大元素个数*/
typedef struct/*顺序循环队列的类型定义*/
{ElemType data[MaxSize];/*队列元素存储空间*/
int front;/*队头指针*/
int rear;/*队尾指针*/
} CircSeqQueue;
2、数据结构设计
由于C语言中一维数组（即向量）也是采用顺序存储表示，因此可用一维数组data[MAXSIZE]来描述顺序表，其中MAXSIZE是一个预先设定的常数(100)，至于顺序表的长度（即线性表中元素的数目）可用一个整型变量length来表示，元素类型假定为ElemType（ElemType可以是任何相应的数据类型如int,char等），用结构类型来定义顺序表的类型。
LocateElem(SqList L, ElemType x)
/*定位函数。返回L中第个与x相等的数据元素的位置（从算起）。否则返回值为。*/
Insert(SqList &L, ElemType x,inti)
/*在线性表L中第i（≤i≤L.length）个数据元素之前插入一个数据元素x*/
Dlete(SqList &L,inti)
//将由指针pQ所指向的队列变为空队
4、界面设计
union1(LinkList *head,LinkList *B,LinkList *&C)
//A和B是两个带头结点的递增有序的单链表，本算法将两表合并成，一个带头结点的递增有序单链表C，利用原表空间。
4、界面设计
指导用户按照正确的格式输入数据。
5、编码实现
（见源代码）
6、运行测试
建立链表，输入相关数据，测试各功能函数。
//使用表尾添加法，向头指针为head的链表中插入一个结点，其值为x
CreatList(LinkList *head,intn)
//生成含有n个结点的单链表
output(LinkList *head)
//输出单链表
GetNode(LinkList *head,inti)
//在带头结点的单链表中查找第i个结点，找到返回该结点指针，否则返回NULL
2、数据结构设计
顺序栈的数据类型：
#define MaxSize 100/*最大元素个数*/
typedef struct/*顺序栈的类型定义*/
{ElemType data[MaxSize];/*栈元素存储空间*/
int top;/*栈顶指针*/
} SeqStack;
3、功能（函数）设计插入和另一端删除的线性表，是生活中排队的抽象。
插入的一端称为队尾(Rear)、插入操作通称进队(Enqueue)；删除的一端称为队头(Front)、删除操作通称出队(Dequeue)。队列是有着先进先出(First In First Out—FIFO)的特性，也称为先进先出表。这里是采用顺序存储结构来实现的队列为顺序队列。队列的顺序存储结构也是利用一维数组来依次存放从队尾到队头的元素。设置front来指示队列当前队头元素的位置、rear来指示队列当前队尾元素的位置。顺序队列随着插入和删除操作的进行，队头和队尾标志顺序向后移动，当元素被插入到数组中的最高位置上之后，队列的空间就用完了，数组的低端还有许多空闲空间，但已经无法插入，这种现象通称为顺序队列的“假溢出”。为解决顺序队列的“假溢出”，可以将存储队列的数组看作是首尾相连的循环结构（循环队列）。循环队列判满和空的条件：front永远指向队头元素的前一个位置，队列中有一个元素空间不可用，队空判断条件：rear==front，队满判断条件：(rear + 1) % MaxSize==front。
实验三 顺序栈实验
实验目的：理解顺序栈的逻辑结构和存储结构，熟练掌握顺序栈的相关操作。
1、问题描述
栈是限制为仅仅能在表的一端插入和删除的线性表，是生活中某些过程的抽象。
插入删除的的一端称为栈顶(Top)、插入操作通常称为进栈或者入栈(Push)。不能插入删除的一端称为栈底(Bottom)、删除操作通常称为出栈或者退栈(Pop)。依据栈的定义，栈顶的元素总是最后进栈的，并且是最先出栈的；栈底元素正好相反，最先进栈，最后出栈，因此，栈有着后进先出(Last In First Out—LIFO)的特性，也称为后进先出表。使用顺序表来表示一个栈。
5、编码实现
实验目的：理解链表的逻辑结构和存储结构，熟练掌握链表的相关操作。
1、问题描述
链表是用一组任意的存储单元来依次存储线性表中的各个数据元素，这些存储单元可以是连续的，也可以是不连续的。用链接存储结构表示线性表的一个元素时至少要有两部分信息:一是这个数据元素的值，二是这个数据元素的直接后继的存储地址。这两部分信息一起组成了链表的一个结点。数据域用来存放数据元素的值；指针域（又称链域）用来存放该数据元素的直接后继结点的地址。链表正是通过每个结点的指针域将线性表的n个结点按其逻辑次序链接成为一个整体。通常用箭头表示链域中的指针，于是单链表就可以直观地画成用箭头链接起来的结点序列，单链表中每个结点的存储地址存放在其直接前驱的指针域中，因此访问单链表的每一个结点必须从表头指针开始进行。对单链表的操作主要有：建立单链表、查找（按序号查找、按值查找）、插入一个结点、删除一个结点、求表长等。
//在带头结点的单链表中删除值为x的结点
DeleteNode(LinkList *head,inti)
//在带头结点的单链表中删除第i个结点
Length(LinkList *head)
//在带头结点的单链表中求表的长度
InsertOrder(LinkList *head,intx)
//在有序单链表L中插入值为x的结点，插入后仍然有序
6、运行测试
运行程序，输入顺序表的数据，建立顺序栈，测试各功能函数。
实验四 链式栈实验
实验目的：理解链式栈的逻辑结构和存储结构，熟练掌握链式栈的相关操作。
1、问题描述
问题描述同前面的顺序栈，这里是使用一个链表来表示一个栈。使用带表头结点的链表，这样所有对栈的初始化和判断条件都需要作相应的更改。
2、数据结构设计
/*删除线性表L中第i（≤I<L.length）个数据元素*/
Clear(SqList &L)/*清空线性表L*/
MergeList(SqList la, SqList lb, SqList &lc)
/*合并表有序表la和lb到表lc中，使得lc依然有序*/
4、界面设计
指导用户按照正确的格式输入数据。
LocateNode(LinkList *head, ElemType x)
//在带头结点的单链表中查找值为x的结点，找到返回结点指针，否则返回NULL
InsertNode(LinkList *head,inti, ElemType x)
//在带头结点的单链表中第i个结点位置上插入值为x的结点
DeleteNode1(LinkList *head, ElemType x)
实验的验收将分为两个部分。
第一部分是上机操作，包括检查程序运行和即时提问。
第二部分是提交书面的实验报告。
实验一
实验目的：理解顺序表的逻辑结构和存储结构，熟练掌握顺序表的相关操作。
1、问题描述
顺序表是指采用顺序存储结构的线性表，它利用内存中的一片起始位置确定的连续存储区域来存放表中的所有元素。可以根据需要对表中的任何数据元素进行访问，元素的插入、删除可以在表中的任何位置进行。
StackInitial(SeqStack *pS)//创建一个由指针pS所指向的空顺序栈
IsEmpty(SeqStack *pS)//顺序栈为空时返回，否则返回
IsFull(SeqStack *pS)//栈为满时返回，否则返回
Push(SeqStack *pS, ElemType e)//若栈不满，则元素e进栈
数据结构基础算法实现
实验要求
本课程是计算机科学技术中处于核心地位的一门专业基础课，它的主要研究内容是在程序开发中合理组织数据。通过对计算机数据机构的学习与研究，掌握设计的主要方法。为今后从事软件开发和软件理论研究打下良好的实验基础。
在《数据结构》的课程实验过程中，要求学生做到：
（1）预习实验指导书有关部分，认真做好实验内容的准备，就实验可能出现的情况提前作出思考和分析。
EnQueue(CircSeqQueue *pQ, ElemType e)
//若队列不满，则元素e进队
DeQueue(CircSeqQueue *pQ)
//若循环队列不为空，则删除队头元素，并返回它的值
GetFront(CircSeqQueue *pQ)
//若队列不为空，则返回队头元素的值
MakeEmpty(CircSeqQueue *pQ)
#define MAXSIZE 100/*MAXSIZE为线性表可能的最大长度*/
#define ERROR -1
typedef struct
{
ElemTypedata[MAXSIZE];
intlength;/*length为线性表的长度*/
}SqList;/*线性表定义*/
3、功能（函数）设计
顺序表的基本操作：
InitList(SqList &L)/*初始化操作，将线性表L置空*/
CreatSqlist(SqList &L,intn)/*建立一个顺序存储的线性表*/
Output(SqList L)/*输出顺序表L*/
IsEmpty(SqList L)/*判断表是否为空。如果L是空表，返回，否则返回*/
GetElem(SqList L,inti)/*取表中第i元素。*/
（2）仔细观察上机和上网操作时出现的各种现象，记录主要情况，作出必要说明和分析。
顺序循环队列的数据类型：
#define MaxSize 100/*最大元素个数*/
typedef struct/*顺序循环队列的类型定义*/
{ElemType data[MaxSize];/*队列元素存储空间*/
int front;/*队头指针*/
int rear;/*队尾指针*/
} CircSeqQueue;
2、数据结构设计
由于C语言中一维数组（即向量）也是采用顺序存储表示，因此可用一维数组data[MAXSIZE]来描述顺序表，其中MAXSIZE是一个预先设定的常数(100)，至于顺序表的长度（即线性表中元素的数目）可用一个整型变量length来表示，元素类型假定为ElemType（ElemType可以是任何相应的数据类型如int,char等），用结构类型来定义顺序表的类型。
LocateElem(SqList L, ElemType x)
/*定位函数。返回L中第个与x相等的数据元素的位置（从算起）。否则返回值为。*/
Insert(SqList &L, ElemType x,inti)
/*在线性表L中第i（≤i≤L.length）个数据元素之前插入一个数据元素x*/
Dlete(SqList &L,inti)
//将由指针pQ所指向的队列变为空队
4、界面设计
union1(LinkList *head,LinkList *B,LinkList *&C)
//A和B是两个带头结点的递增有序的单链表，本算法将两表合并成，一个带头结点的递增有序单链表C，利用原表空间。
4、界面设计
指导用户按照正确的格式输入数据。
5、编码实现
（见源代码）
6、运行测试
建立链表，输入相关数据，测试各功能函数。
//使用表尾添加法，向头指针为head的链表中插入一个结点，其值为x
CreatList(LinkList *head,intn)
//生成含有n个结点的单链表
output(LinkList *head)
//输出单链表
GetNode(LinkList *head,inti)
//在带头结点的单链表中查找第i个结点，找到返回该结点指针，否则返回NULL
2、数据结构设计
顺序栈的数据类型：
#define MaxSize 100/*最大元素个数*/
typedef struct/*顺序栈的类型定义*/
{ElemType data[MaxSize];/*栈元素存储空间*/
int top;/*栈顶指针*/
} SeqStack;
3、功能（函数）设计插入和另一端删除的线性表，是生活中排队的抽象。
插入的一端称为队尾(Rear)、插入操作通称进队(Enqueue)；删除的一端称为队头(Front)、删除操作通称出队(Dequeue)。队列是有着先进先出(First In First Out—FIFO)的特性，也称为先进先出表。这里是采用顺序存储结构来实现的队列为顺序队列。队列的顺序存储结构也是利用一维数组来依次存放从队尾到队头的元素。设置front来指示队列当前队头元素的位置、rear来指示队列当前队尾元素的位置。顺序队列随着插入和删除操作的进行，队头和队尾标志顺序向后移动，当元素被插入到数组中的最高位置上之后，队列的空间就用完了，数组的低端还有许多空闲空间，但已经无法插入，这种现象通称为顺序队列的“假溢出”。为解决顺序队列的“假溢出”，可以将存储队列的数组看作是首尾相连的循环结构（循环队列）。循环队列判满和空的条件：front永远指向队头元素的前一个位置，队列中有一个元素空间不可用，队空判断条件：rear==front，队满判断条件：(rear + 1) % MaxSize==front。
实验三 顺序栈实验
实验目的：理解顺序栈的逻辑结构和存储结构，熟练掌握顺序栈的相关操作。
1、问题描述
栈是限制为仅仅能在表的一端插入和删除的线性表，是生活中某些过程的抽象。
插入删除的的一端称为栈顶(Top)、插入操作通常称为进栈或者入栈(Push)。不能插入删除的一端称为栈底(Bottom)、删除操作通常称为出栈或者退栈(Pop)。依据栈的定义，栈顶的元素总是最后进栈的，并且是最先出栈的；栈底元素正好相反，最先进栈，最后出栈，因此，栈有着后进先出(Last In First Out—LIFO)的特性，也称为后进先出表。使用顺序表来表示一个栈。
5、编码实现
实验目的：理解链表的逻辑结构和存储结构，熟练掌握链表的相关操作。
1、问题描述
链表是用一组任意的存储单元来依次存储线性表中的各个数据元素，这些存储单元可以是连续的，也可以是不连续的。用链接存储结构表示线性表的一个元素时至少要有两部分信息:一是这个数据元素的值，二是这个数据元素的直接后继的存储地址。这两部分信息一起组成了链表的一个结点。数据域用来存放数据元素的值；指针域（又称链域）用来存放该数据元素的直接后继结点的地址。链表正是通过每个结点的指针域将线性表的n个结点按其逻辑次序链接成为一个整体。通常用箭头表示链域中的指针，于是单链表就可以直观地画成用箭头链接起来的结点序列，单链表中每个结点的存储地址存放在其直接前驱的指针域中，因此访问单链表的每一个结点必须从表头指针开始进行。对单链表的操作主要有：建立单链表、查找（按序号查找、按值查找）、插入一个结点、删除一个结点、求表长等。
//在带头结点的单链表中删除值为x的结点
DeleteNode(LinkList *head,inti)
//在带头结点的单链表中删除第i个结点
Length(LinkList *head)
//在带头结点的单链表中求表的长度
InsertOrder(LinkList *head,intx)
//在有序单链表L中插入值为x的结点，插入后仍然有序
6、运行测试
运行程序，输入顺序表的数据，建立顺序栈，测试各功能函数。
实验四 链式栈实验
实验目的：理解链式栈的逻辑结构和存储结构，熟练掌握链式栈的相关操作。
1、问题描述
问题描述同前面的顺序栈，这里是使用一个链表来表示一个栈。使用带表头结点的链表，这样所有对栈的初始化和判断条件都需要作相应的更改。
2、数据结构设计
/*删除线性表L中第i（≤I<L.length）个数据元素*/
Clear(SqList &L)/*清空线性表L*/
MergeList(SqList la, SqList lb, SqList &lc)
/*合并表有序表la和lb到表lc中，使得lc依然有序*/
4、界面设计
指导用户按照正确的格式输入数据。
LocateNode(LinkList *head, ElemType x)
//在带头结点的单链表中查找值为x的结点，找到返回结点指针，否则返回NULL
InsertNode(LinkList *head,inti, ElemType x)
//在带头结点的单链表中第i个结点位置上插入值为x的结点
DeleteNode1(LinkList *head, ElemType x)
实验的验收将分为两个部分。
第一部分是上机操作，包括检查程序运行和即时提问。
第二部分是提交书面的实验报告。
实验一
实验目的：理解顺序表的逻辑结构和存储结构，熟练掌握顺序表的相关操作。
1、问题描述
顺序表是指采用顺序存储结构的线性表，它利用内存中的一片起始位置确定的连续存储区域来存放表中的所有元素。可以根据需要对表中的任何数据元素进行访问，元素的插入、删除可以在表中的任何位置进行。
StackInitial(SeqStack *pS)//创建一个由指针pS所指向的空顺序栈
IsEmpty(SeqStack *pS)//顺序栈为空时返回，否则返回
IsFull(SeqStack *pS)//栈为满时返回，否则返回
Push(SeqStack *pS, ElemType e)//若栈不满，则元素e进栈
数据结构基础算法实现
实验要求
本课程是计算机科学技术中处于核心地位的一门专业基础课，它的主要研究内容是在程序开发中合理组织数据。通过对计算机数据机构的学习与研究，掌握设计的主要方法。为今后从事软件开发和软件理论研究打下良好的实验基础。
在《数据结构》的课程实验过程中，要求学生做到：
（1）预习实验指导书有关部分，认真做好实验内容的准备，就实验可能出现的情况提前作出思考和分析。
EnQueue(CircSeqQueue *pQ, ElemType e)
//若队列不满，则元素e进队
DeQueue(CircSeqQueue *pQ)
//若循环队列不为空，则删除队头元素，并返回它的值
GetFront(CircSeqQueue *pQ)
//若队列不为空，则返回队头元素的值
MakeEmpty(CircSeqQueue *pQ)
#define MAXSIZE 100/*MAXSIZE为线性表可能的最大长度*/
#define ERROR -1
typedef struct
{
ElemTypedata[MAXSIZE];
intlength;/*length为线性表的长度*/
}SqList;/*线性表定义*/
3、功能（函数）设计
顺序表的基本操作：
InitList(SqList &L)/*初始化操作，将线性表L置空*/
CreatSqlist(SqList &L,intn)/*建立一个顺序存储的线性表*/
Output(SqList L)/*输出顺序表L*/
IsEmpty(SqList L)/*判断表是否为空。如果L是空表，返回，否则返回*/
GetElem(SqList L,inti)/*取表中第i元素。*/
（2）仔细观察上机和上网操作时出现的各种现象，记录主要情况，作出必要说明和分析。
