实验四
实验名称 栈和队列及其应用 实验性质 设计性 实验学时数 4学时
一、实验目的
1．掌握栈与队列的抽象数据类型描述及特点。
2．掌握栈和队列的顺序和链式存储结构与基本算法实现。
3．掌握栈和队列在实际问题中的应用和基本编程技巧。
二、实验内容
1. 栈和队列在不同存储结构上进行插入、删除等操作的算法。
2. 通过栈或队列解决现实中的一些问题。
三、
实
验
过
程
1、实验题目
[问题描述]
以下题目根据自己兴趣和能力可选作一道作为实验题目：
（1）根据栈的数据结构，建立一个顺序栈和链栈并实现对其基本操作；
（2）根据队列的数据结构，建立一个循环队列和链队并实现对其基本操作；
（3）根据教材4.3.3节介绍的思想，设计并实现一个对简化表达式求值的系统
（4）银行业务队列简单模拟。设某银行有A、B两个业务窗口，其中A窗口的处理速度是B窗口的2倍，给定到达银行的顾客序号，请按业务完成的顺序输出顾客序列（假设奇数编号到A窗口办理，偶数编号到B窗口办理，不同窗口同时处理完2个顾客，A窗口优先输出）。
[基本要求]
（1）按实验内容编写完整的程序，并上机验证。
（2）实验完成后，提交电子档教师验收程序，并提交填写好的实验报告。
[测试数据]
由学生依据软件工程的测试技术自己确定。注意测试边界数据。
2、源程序
#include
#include
#define Stack_Size 100
#define StackElementType int
#define TRUE 1 #define FALSE 0
typedef struct //顺序栈
{
StackElementType elem[Stack_Size];
int top;
}SeqStack;
typedef struct node //链栈
{
StackElementType data;
C语⾔中都有哪些常见的数据结构你都知道⼏个？
上次在⾯试时被⾯试官问到学了哪些数据结构，那时简单答了栈、队列/(ㄒoㄒ)/~~其它就都想不起来了，今天有空整理了⼀下⼏种常见的数
据结构，原来我们学过的数据结构有这么多~
⾸先，先来回顾下C语⾔中常见的基本数据类型吧O(∩_∩)OC语⾔的基本数据类型有：整型int，浮点型float，字符型char等等
添加描述
那么，究竟什么是数据结构呢？
数据结构是计算机存储、组织数据的⽅式。数据结构是指相互之间存在⼀种或多种特定关系的数据元素的集合
⼤部分数据结构的实现都需要借助C语⾔中的指针和结构体类型
下⾯，进⼊今天的重点啦O(∩_∩)O⼏种常见的数据结构
（1）线性数据结构：元素之间⼀般存在元素之间存在⼀对⼀关系，是最常⽤的⼀类数据结构，典型的有：数组、栈、队列和线性表
（2）树形结构：结点间具有层次关系，每⼀层的⼀个结点能且只能和上⼀层的⼀个结点相关，但同时可以和下⼀层的多个结点相关，称
为“⼀对多”关系，常见类型有：树、堆
（3）图形结构：在图形结构中，允许多个结点之间相关，称为“多对多”关系
下⾯分别对这⼏种数据结构做⼀个简单介绍：1、线性数据结构：典型的有：数组、栈、队列和线性表
（1）数组和链表a、数组：存放着⼀组相同类型的数据，需要预先指定数组的长度，有⼀维数组、⼆维数组、多维数组等
b、链表：链表是C语⾔中⼀种应⽤⼴泛的结构，它采⽤动态分配内存的形式实现，⽤⼀组任意的存储单元存放数据元素链表的，⼀般为每
个元素增设指针域，⽤来指向后继元素c、数组和链表的区别：
从逻辑结构来看：数组必须事先定义固定的长度，不能适应数据动态地增减的情况；链表动态地进⾏存储分配，可以适应数据动态地增减的
情况，且可以⽅便地插⼊、删除数据项（数组中插⼊、删除数据项时，需要移动其它数据项）
从内存存储来看：（静态)数组从栈中分配空间（⽤NEW创建的在堆中）, 对于程序员⽅便快速,但是⾃由度⼩；链表从堆中分配空间, ⾃由度
数据结构单链表（c语⾔描述）
最近看了⼀些有关数据结构c语⾔描述下的视频，整理好了⾃⼰的思路，按照⾃⼰的想法写了⼀篇数据结构单链表的操作，为⾃⼰考研
之路留下⼀些痕迹。
1.⾸先创建结构体，声明静态的全局变量
typedef int ElemType;
typedef struct Node{
ElemType data; //储存数据
struct Node *next; //指向下⼀个元素
}node,*link;
static int num=0; //单链表的长度
2.接下来是单循环链表的创建
void initList(link &T)
{
link currentNode,temp; //⽬前位置的节点 和开始节点
int number; //申请链表的长度
int data; //数据
printf("请输⼊你想要创建链表的长度");
scanf("%d",&number);
num=number; //全局变量中单链表的长度
T=(Node*)malloc(sizeof(Node));
if(!T)
{
printf("空间申请失败\n");
}
T->next=NULL;
temp=T; // 开始节点
//实⾏尾插法
printf("请依次输⼊链表储存的数值\n");
if(number>0)
{
while(number--) //temp指向的是链表中最后⼀个元素
{
scanf("%d",&data);
currentNode=(Node*)malloc(sizeof(Node));
if(!currentNode)
{
printf("空间申请失败");
}
currentNode->data=data;
currentNode->next=NULL; //⽣成新的结点
temp->next=currentNode;
temp=currentNode; //结点向下移⼀位
第1章 绪 论
习 题
一、问答题
1. 什么是数据结构？
2. 四类基本数据结构的名称与含义。
3. 算法的定义与特性。
4. 算法的时间复杂度。
5. 数据类型的概念。
6. 线性结构与非线性结构的差别。
7. 面向对象程序设计语言的特点。
8. 在面向对象程序设计中，类的作用是什么？
9. 参数传递的主要方式及特点。
10. 抽象数据类型的概念。
二、判断题
1. 线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。
2. 算法就是程序。
3. 在高级语言（如C、或 PASCAL）中，指针类型是原子类型。
三、计算下列程序段中X=X+1的语句频度
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
for(k=1;k<=j;k++)
x=x+1;
[提示]：
i=1时： 1 = (1+1)×1/2 = (1+12)/2
i=2时： 1+2 = (1+2)×2/2 = (2+22)/2
i=3时： 1+2+3 = (1+3)×3/2 = (3+32)/2
…
i=n时： 1+2+3+……+n = (1+n)×n/2 = (n+n2)/2
f(n) = [ (1+2+3+……+n) + (12 + 22 + 32 + …… + n2 ) ] / 2
=[ (1+n)n/2 + n(n+1)(2n+1)/6 ] / 2 =n(n+1)(n+2)/6
=n3/6+n2/2+n/3
区分语句频度和算法复杂度：
O(f(n)) = O(n3)
四、试编写算法求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…anxn的值Pn(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能的小，规定算法中不能使用求幂函数。注意：本题中的输入ai(i=0,1,…,n), x和n，输出为Pn(x0).通常算法的输入和输出可采用下列两种方式之一：
