数据结构-堆栈和队列实验报告

实验报告实验报告 课程数据结构实验名称实验二 堆栈和队列 学号姓名实验日期 2012 10 18 实验二 堆栈和队列 实验目的 实验目的 1 熟悉栈这种特殊线性结构的特性 2 熟练并掌握栈在顺序存储结构和链表存储结构下的基本运算 3 熟悉队列这种特殊线性结构的特性 3 熟练掌握队列在链表存储结构下的基本运算 实验原理 堆栈顺序存储结构下的基本算法 堆栈链式存储结构下的基本算法 队列顺序存储结构下的基本算法 队列链式存储结构下的基本算法 实验内容 3 18 链式堆栈设计 要求 1 用链式堆栈设计实现堆栈 堆栈的操作集合要求包括 初始化 StackInitiate S 非 空否 StackNotEmpty S 入栈 StackiPush S x 出栈 StackPop S d 取栈顶数据元素 StackTop S d 2 设计一个主函数对链式堆栈进行测试 测试方法为 依次把数据元素 1 2 3 4 5 入栈 然后出栈并在屏幕上显示出栈的数据元素 3 定义数据元素的数据类型为如下形式的结构体 Typedef struct char taskName 10 int taskNo DataType 首先设计一个包含 5 个数据元素的测试数据 然后设计一个主函数对链式堆栈进行测试 测试方法为 依次吧 5 个数据元素入栈 然后出栈并在屏幕上显示出栈的数据元素 3 19 对顺序循环队列 常规的设计方法是使用対尾指针和对头指针 对尾指针用于指示当 前的対尾位置下标 对头指针用于指示当前的対头位置下标 现要求 1 设计一个使用对头指针和计数器的顺序循环队列抽象数据类型 其中操作包括 初始 化 入队列 出队列 取对头元素和判断队列是否为空 2 编写一个主函数进行测试 实验结果 3 18 typedef struct snode DataType data struct snode next LSNode 初始化操作 void StackInitiate LSNode head 初始化带头结点链式堆栈 if head LSNode malloc sizeof LSNode NULL exit 1 head next NULL 判非空操作 int StackNotEmpty LSNode head 判堆栈是否非空 非空返回 1 空返回 0 if head next NULL return 0 else return 1 入栈操作 int StackPush LSNode head DataType x 把数据元素 x 插入链式堆栈 head 的栈顶作为新的栈顶 LSNode p if p LSNode malloc sizeof LSNode NULL printf 内存空间不足无法插入 n return 0 p data x p next head next 新结点链入栈顶 head next p 新结点成为新的栈顶 return 1 出栈操作 int StackPop LSNode head DataType d 出栈并把栈顶元素由参数 d 带回 LSNode p head next if p NULL printf 堆栈已空出错 return 0 head next p next 删除原栈顶结点 d p data 原栈顶结点元素赋予 d free p 释放原栈顶结点内存空间 return 1 取栈顶数据元素操作 int StackTop LSNode head DataType d 取栈顶元素并把栈顶元素由参数 d 带回 LSNode p head next if p NULL printf 堆栈已空出错 return 0 d p data return 1 撤销 void Destroy LSNode head LSNode p p1 p head while p NULL p1 p p p next free p1 2 主函数程序 include include typedef int DataType include LinStack h void main void LSNode myStack int i x StackInitiate for i 0 i 5 i if StackPush myStack i 1 0 printf error n return if StackTop myStack return else printf The element of local top is d n x printf The sequence of outing elements is n while StackNotEmpty myStack StackPop myStack printf d x printf n Destroy myStack printf This program is made by10273206 n 运行结果为 3 设计结构体和测试函数如下 include include include typedef struct char taskName 10 int taskNo DataType include LinStack h void main LSNode myStack FILE fp DataType task x if fp fopen task txt r NULL printf 不能打开文件 task txt n exit 0 StackInitiate while feof fp fscanf fp s d StackPush myStack task fclose fp while StackNotEmpty myStack StackPop myStack printf s d n x taskName x taskNo Destroy myStack printf This program is made by 10273206 n 运行结果为 3 19 1 typedef struct DataType queue MaxQueueSize int front 队头指针 int count 计数器 SeqCQueue 初始化操作初始化操作 QueueInitiate SeqCQueue Q void QueueInitiate SeqCQueue Q 初始化顺序循环队列 Q Q front 0 定义初始队头指针下标 Q count 0 定义初始计数器值 判非空否操作 判非空否操作 QueueNotEmpty SeqCQueue Q int QueueNotEmpty SeqCQueue Q 判断顺序循环队列 Q 非空否 非空时返回 1 否则返回 0 if Q count 0 return 1 else return 0 入队列操作 入队列操作 QueueAppend SeqCQueue Q DataType x int QueueAppend SeqCQueue Q DataType x 把数据元素 x 插入顺序循环队列 Q 的队尾 成功时返回 1 否则返回 0 if Q count MaxQueueSize printf The queue is full n return 0 else int r r Q front Q count Q queue r x Q count return 1 出队列操作 出队列操作 QueueDelete SeqCQueue Q DataType d int QueueDelete SeqCQueue Q DataType d 删除顺序循环队列队头数据元素并赋值 d 成功时返回 1 否则返回 0 if Q count 0 printf The queue is empty n return 0 else d Q queue Q front Q front Q front 1 MaxQueueSize Q count return 1 取对头数据元素操作取对头数据元素操作 QueueGet SeqCQueue Q DataType d int QueueGet SeqCQueue Q DataType d 取顺序循环队列队头数据元素并赋值 d 成功时返回 1 否则返回 0 if Q count 0 printf The queue is empty n return 0 else d Q queue Q front return 1 2 主函数程序 include define MaxQueueSize 100 typedef int DataType include SeqQueue h void main void int i j d SeqCQueue myQueue QueueInitiate if QueueNotEmpty myQueue 0 printf 队列为空 请输入数据元素 n 判空 for i 0 i 10 i if QueueAppend printf 元素个数为 d n myQueue count 输出元素个数 for j 0 j 9 j if QueueDelete printf d d 出队列并显示元素 printf n if QueueNotEmpty m