《数据结构之线性结构 2.ppt》由会员分享，可在线阅读，更多相关《数据结构之线性结构 2.ppt（24页珍藏版）》请在金锄头文库上搜索。
1、线性结构,数据结构,什么是数据结构？,数据结构(Data Structure),用于描述计算机中数据的存储、组织形式。合理的数据结构可以给程序带来更高的存储和运行效率。,常用的数据结构有哪些？,1.线性结构 2.树型结构 3.图型结构,栈、队列、链表,栈,栈(stack)是一种特殊的线性结构，它只能在一端进行插入和删除操作。 能插入和删除的一端栈顶（top），另一端称为栈底 (bottom)。 不含任何元素的栈称为空栈。 只允许在栈顶进行插入和删除，所以栈的操作是按“后进先出”（Last In First Out）的原则进行的。,栈底(bottom),栈顶(top),栈的实例1：汉诺塔,栈的实
2、例2：弹夹,栈顶(top),装弹、出弹,2,8,5,top（栈顶）,用数组模拟栈的“后进先出”,加入一个数,7,取出栈顶元素,再取出栈顶元素,9,bottom（栈底,值为0）,数组（栈）,1,2,3,4,5,6,下标,栈为空的条件是：top=bottom,top始终指向栈顶,一般情况下，top的值就表示了栈中的元素个数,/插入（压栈） void push(char x) if(top=maxn) cout“full“; else top+; stacktop=x; ,/删除(弹栈) void pop() if(top=0) cout“empty“; else coutstacktop; top
3、-; ,const int maxn=1000 char stackmaxn+1; int top=0;,4 3 2 1,使用栈进行算术表达式求值,表达式：3 ( 5 2 ) + 7 ,数字,运算符,3,(,5,2,3,+,9,7,5 2 = 3,3 3 = 9,7 + 9 = 16,结果便是16！,16,栈的实例2：混合运算,考题（初赛）,若S是一个大小为4的栈，若元素1，2，3，4，5，6，7按顺序依次进栈，则这7个元素的出栈顺序可能为（ ） A.1,2,3,4,5,6,7 B.1,4,3,5,7,2,6 C.1,3,2,4,7,5,6 D.2,3,7,6,5,4,1,栈的实例3：火车调度
4、(NKOJ 1914),某城市有一个火车站，如下图 所示，现有 n（n =10000）节火车车厢，顺序编号为 1,2,3,.,n，按编号连续依次从 A 方向的铁轨驶入车站，从 B 方向铁轨驶出。一旦车厢进入车站就不能再回到 A 方向的铁轨上；在车站的门口有工人可以将车厢拖出车站，工人一次只能拖一节车厢，并且只能将车厢拖入B方向的铁轨。一旦车厢出了车站就不能再回到车站。车站一开始为空，最多能停放 10000 节车厢。 为了方便装货，调度员需要将车厢从新排列，问能否将车厢编号排列成A1,A2,An。也就是使车厢从B方向驶出的编号是A1,A2,An。如果能输出“yes“，否则输出“no“。 输入格式
5、： 第一行，一个整数n 第二行，n个用空格间隔的整数，表示出站时车厢编号要排列成的顺序A1,A2,An 输出格式： 一行，一个单词“yes“或者“no“ 样例输入1： 5 3 2 5 4 1 样例输出1: yes 样例输入2： 5 3 1 5 4 2 样例输出2: no,驶入,驶出,/将题目要求的出站序列读入a数组，然后通过栈从左到右依次去匹配a数组 #include #include using namespace std; int s10001,a10001,n,i,j,top=0; /s数组用于模拟栈 int main() scanf(“%d“, ,队列,队列（queue）是另一种特殊的线性表，它的特点是删除操作在一头进行，插入操作在另一头进行。 允许删除的一端称为队首（head）,允许插入的一端称为队尾(tail)。 不含任何元素的队称为空队。 队列的修改是按先进先出(First In First Out)的原则进行,队首（head）,队尾（tail）,用数组模拟队列的“先进先出”,C,1,2,3,4,5,6,7,8,数组（队列）,数组下标,F,X,M,1. 插入数据：,2. 插入数据：,3. 插入数据：,4. 删除数据,4. 删除数据,5. 插入数据：,当head=tail时表示队列为空,head指向队首 tail指向下一个空位 在队首进行删除 在队尾进行插入,
