首页 考试资料幻灯片工程技术公务员考试小学教学中学教学大学教学外语资料
数据结构实验书


第四节 思考题

1. 假设有两个按元素值递增有序排列的线性表 A 和 B,均以单链表作存储结构,请编写算法将表 A 和表 B 归并成一个按元素非递减有序(允许值相同)排列的线性表 C,并要求利用原表(即表 A 和表 B)的结点空 间存放表 C。 (上海交通大学一九九九年硕士生入学考试试题) 【简要分析】除了指向线性表 C 头结点的指针外,还需设置三个指针 Pa,Pb,Pc;首先 Pa,Pb 分别指向 线性表 A 和 B 的表头,Pc 指向 A 和 B 的表头值较小的结点,线性表 C 头节点的指针等于 Pc;然后,比较 Pa 与 Pb 的值的大小,让 Pc 的后继指向较小值的指针,接着 Pc 向后移动,较小值的指针也向后移动,以 此类推,直到 Pa,Pb 中某一个为空,这时,让 Pc 的后继指向 Pa,Pb 中非空的指针就完成了 C 表的建立。 2. 给定一个整数数组 b[0..N-1], b 中连续相等元素构成的子序列称为平台.试设计算法,求出 b 中最长平 台的长度. (中科院计算机技术研究所 1999 年硕士入学考试数据结构与程序设计试题) 【简要分析】设置一个平台长度变量 Length 和一个计数器 Sum。初始化 Length 为 1,Sum 为 1,再设置两 下标指针 i、j,首先,i 指向第一个数组元素,j 指向其次的第二个元素,比较 i、j 指向元素值的大小, 若相等,则 Sum++,i++,j++,再次比较 i、j 指向元素值的大小;若不相等,则比较 Length 与 Sum 的大 小,如果 Sum 值大于 Length,则把 Sum 的值赋给 Length,Sum 的值重置为 1,同时 i,j 也向前各移动一位; 重复上面的过程,直到 i 指向最后一个元素为止,此时的 Length 就是最长平台的长度。

3. 参加知识竞赛的 n 个学校(编号为 1?n),每个学校派至多 m 名学生参赛,每个学生的编号有二位学 校代码和五位座位编号构成。统计每个学校的参赛学生的平均分,并依次确定学校的名次;查找竞赛的最 高分和最低分,并计算它们的方差;给出前三名学生的具体信息。 【简要分析】本题解决办法较多。我们可以采用单链表来对所有学生的信息进行存储,至多需要 n*m 个结 点,每个结点至少包含如下几个域:2 位学校代码、5 位座位编号、学生姓名、竞赛成绩等。也可以采用顺 序表来对所有学生的信息进行存储,构造一个结构体数组,至多需要 n*m 个数组元素,每个数组元素的数 据项值与单链表中的结点域值类似。然后再另外构造一个存储学校信息的顺序表或单链表,每个结点至少 包含如下几个域:二位学校代码、学校名称、学校取得的平均分、学校名次等。在构造好所有的存储结构 之后,就可以编制相应的计算平均分、排序、查找、输出等算法了。

第三章
【实验目的】

栈和队列的应用

1. 熟练掌握栈和队列的结构,以及这两种数据结构的特点; 2. 能够在两种存储结构上实现栈的基本运算,特别注意栈满和栈空的判断条件及描述方法; 3. 熟练掌握链队列和循环队列的基本运算,并特别注意队列满和队列空的判断条件和描述方法;

第一节 知识准备
一、栈: 1. 基本概念 栈是一种限定仅在表的一端进行插入与删除操作的线性表。允许进行插入与删除操作的这一端称为栈顶, 而另一端称为栈底,不含元素的空表称为空栈,插入与删除分别称进栈与出栈。 由于插入与删除只能在同一端进行,所以较先进入栈的元素,在进行出栈操作时,要比较后才能出栈。特 别是,最先进栈者,最后才能出栈,而最晚进栈者,必最先出栈。因此,栈也称作后进先出 (Last In First Out)的线性表,简称 LIFO 表。

栈示意图见图 3-1

2. 栈的抽象数据类型定义: ADT Stack{ 数据对象:D={ | 数据关系:R1={< , 基本操作: InitStack(&S) StackEmpty(S) StackLength(S) GetTop(S,&e) Push(&S,e) Pop(&S,&e) }ADT Stack 构造一个空栈 S 判断栈 S 是否为空 返回栈 S 的元素个数,即栈的长度 取栈 S 的栈顶元素 将元素 e 入栈 删除 S 的栈顶元素并用 e 返回其值(即出栈) ∈ElemSet, >| i=1,2,...,n, n>=0} i=2,...,n}

, ∈D,

3. 栈的表示: 栈有两种存储表示方法:顺序存储结构和链式存储结构。 (1)顺序存储结构: #define STACK_INIT_SIZE #define STACKINCREMENT typedef struct{ SElemType *base; SElemType *top; int StackSize; }SqStack; (2)链式存储结构: Typedef struct Lnode{ ElemType struct data; Lnode *next; //栈底指针 //栈顶指针 //栈的当前容量 100; //存储空间初始分配量 10; //存储空间分配增量

}Lnode, *LinkList; 二、队列: 1. 与栈相对应, 队列是一种先进先出的线性表。 它只允许在表的一端进行插入, 而在另一端进行删除元素。 允许插入的一端称队尾,允许删除的一端称队头。插入与删除分别称为入队与出队。队列示意图见图 3-2: ────────────── 出队 ←a1 a2 ?? an-1 ←an 进队

────────────── 队头 图 3-2 队列 队尾

2. 队列的抽象数据类型定义: ADT Queue{ 数据对象:D={ | 数据关系:R1={< , 基本操作: InitQueue(&Q) 构造一个空队列 Q ∈ElemSet, >| i=1,2,...,n, n>=0} i=2,...,n}

, ∈D,

QueueEmpty(Q) QueueLenght(Q) GetHead(Q,&e) EnQueue(&Q,e) DeQueue(&Q,&e) }ADT Queue

判断队列是否为空 返回队列 Q 的元素个数,即队列的长度 取队列 Q 的队头元素,并用 e 返回 将元素 e 入队列 删除非空队列 Q 的队头元素,并用 e 返回其值

3. 队列的表示: 队列有两种表示方法:链队列、循环队列(顺序队列)。 (1) 链队列的表示: typedef struct QNode{ QElemType data; struct QNode *next;

}QNode,*QueuePtr; typedef struct{ QueuePtr QueuePtr front; rear;

}LinkQueue; (2) 循环队列的表示(见第二节)

第二节 循环队列的表示和实现
【问题描述】 设计一个抽象数据类型队列的顺序表示和实现的演示程序。 【数据描述】 #define MaxQsize typedef struct { QElemType int int }SqQueue; 【算法描述】 Status InitQueue(SqQueue &Q){ front; rear; *base;//初始化的动态分配存储空间 //头指针,若队列不空,指向队列头元素 //尾指针,若队列不空,指向队列尾元素的下一个位置 100 //最大队列长度

//构造一个空队列 Q Q.base=(QelemType *)malloc(MaxQsize*sizeof(QelemType));

123456789101112131415161718192021222324252627282930

 


 

  【Top

最新搜索

 


 

热点推荐