计算机软件基础(自考本科栈、队列)

1、（一）栈的概念（一）栈的概念1. 栈：是一种栈：是一种后进先出后进先出的线性表，简称为的线性表，简称为LIFO表表（Last In First Out）。）。2. 栈栈顶顶（Top）：栈中进行插入、删除操作的一）：栈中进行插入、删除操作的一端（即：变化端）。端（即：变化端）。3. 栈栈底底（Bottom）：栈中固定不变的一端。）：栈中固定不变的一端。4. 栈的存储结构：顺序存储和链式存储。栈的存储结构：顺序存储和链式存储。（二）顺序栈（二）顺序栈1. 形态形态3. 顺序栈的类型顺序栈的类型4. 顺序栈的基本运算顺序栈的基本运算-进栈进栈step1:判断栈判断栈是否已满，若是否已满，若满，则上溢

2、，满，则上溢，否则进行下一否则进行下一步；步；step2:栈顶指栈顶指针上移一个节针上移一个节点；点；Step3: 将将x加加入到入到top指定指定的位置。的位置。void push( s, x) if(s.top=m-1) 上溢；上溢； else s.top+;s.datas.top=x; 5. 顺序栈的基本运算顺序栈的基本运算-退栈退栈step1:判断栈判断栈是否为空，若是否为空，若空，则下溢，空，则下溢，否则进行下一否则进行下一步；步；Step2: 保留被保留被删除元素到变删除元素到变量量x中；中；step3:栈顶指栈顶指针下移一个节针下移一个节点；点；void pop(s) if(s.

3、top=-1) 下溢；下溢； else x=s.datas.top;s.top-; （三）链栈（三）链栈1. 形态形态链栈：是一个不带表头节点的单链表（栈顶指针直接链栈：是一个不带表头节点的单链表（栈顶指针直接指向栈顶元素）。指向栈顶元素）。（三）链栈（三）链栈2. 类型定义类型定义（三）链栈（三）链栈3. 进栈运算进栈运算step1:申请一个新申请一个新节点，并让节点，并让s s指向指向该节点；该节点；step2:将将x x赋给新节赋给新节点的点的datadata域；域；step3:将原栈点链将原栈点链入新节点的入新节点的nextnext域；域；step4:新节点作为新节点作为新的栈顶节点。

4、新的栈顶节点。void insert(Ls, x)s=(struct node)malloc(sizeof(struct node);s-data=x;s-next=Ls;Ls=s;（三）链栈（三）链栈4. 退栈运算退栈运算step1:判断栈是否为空，判断栈是否为空，如为空，则直接返回，否如为空，则直接返回，否则进行第二步；则进行第二步；step2:让让p p指栈顶元素；指栈顶元素；step3:栈顶指针向下移一栈顶指针向下移一位；位；step4:回收回收p。void del(Ls) if(Ls=NULL) return; else p=Ls; Ls=Ls-next; free(p); 1.铁路

5、调度系统铁路调度系统例9-1 有a,b,c三列火车依次进栈，试问可能有多少种出栈顺序，它们分别是什么？（四）栈的运用（四）栈的运用例9-2 有a,b,c,d,e,f六列火车依次进栈，试问能否得到下列出栈顺序：（1）cbedfa（2）cdfeab2.算术表达式求值算术表达式求值对于算术表达式的求值，主要就是解决算术运算符的优先级问题，有以下规则：先进行乘除运算，再进行加减运算（乘除优先级大于加减）；对于相同优先级的运算符，从左向右计算；若要改变优先级，可使用括号。对有括号的表达式，先计算括号内，再计算括号外。 在表达式的计算过程中，既要保存操作数，又要保存运算符。这时，可定义两个栈，一个用来保存

6、操作数，一个用来保存运算符。（四）栈的运用（四）栈的运用例例9-3 已知已知x=9+4*6/8-5,试写出表达式求值时栈的变试写出表达式求值时栈的变化过程化过程（四）栈的运用（四）栈的运用例例9-4 分析下列程序，写出运算结果，说明其功能。分析下列程序，写出运算结果，说明其功能。void f(int n)if(n1) f(n/2); printf(%1d,n%2);例例9-5 利用栈逆置单链表。利用栈逆置单链表。（四）栈的运用（四）栈的运用void g(s,head)lnitstack(s); p=head-next;while(p!=NULLpush(s,p-data); p=p- next

7、p=head-next;while(!empty(s)p-data=pop(s);p=p-next;（二）顺序队列（二）顺序队列1. 形态：形态：队列空队列空入队列入队列（二）顺序队列（二）顺序队列1. 形态：形态：队列队列满满出出队列队列（二）顺序队列（二）顺序队列2. 类型定义：类型定义：3. 顺序队列的基本运算顺序队列的基本运算-入队入队step1:判断队列是判断队列是否已满，若满，则否已满，若满，则返回，否则进行下返回，否则进行下一步；一步；step2:队尾指针后队尾指针后移一个节点；移一个节点；Step3: 在队尾指针在队尾指针的位置加入的位置加入x。void enterq(sq,x

8、) if(sq.rear=m-1) return; else sq.rear+;sq.datasq.rear=x; 4. 顺序队列的基本运算顺序队列的基本运算-出队出队step1:判断队列是判断队列是否为空，若空，则否为空，若空，则返回，否则进行下返回，否则进行下一步；一步；Step2: 保留被删除保留被删除元素到变量元素到变量x中；中；step3:栈顶指针后栈顶指针后移一个节点；移一个节点；void deq(sq) if(sq.front=sq.rear=-1) return； else x=s.datasq.front;sq.front+; （三）循环队列（三）循环队列1. 顺序队列的假满

9、：当队列中顺序队列的假满：当队列中r=m-1，f不等于不等于-1时，时，顺序队列出现假满现象。如：顺序队列出现假满现象。如：（三）循环队列（三）循环队列2. 循环队列：把顺序队列的头尾相接所形成的一个循环队列：把顺序队列的头尾相接所形成的一个环形队列，称为循环队列，如图：环形队列，称为循环队列，如图： 说明说明：（1）无论是入队列，还）无论是入队列，还是出队列，均沿着逆时针是出队列，均沿着逆时针方向进行；方向进行；（2）牺牲了）牺牲了f所指空间。所指空间。（三）循环队列（三）循环队列3. 循环队列的几个关键点：循环队列的几个关键点：（1）循环队列）循环队列空空的条件：的条件：front=rea

10、r;（2）循环队列）循环队列满满的条件：的条件：front=（ rear）%m;（3）循环队列）循环队列满满时，元素个数为：时，元素个数为：m-1;（4）一般情况下，循环队列）一般情况下，循环队列中中，元素个数为，元素个数为（rear-front+m）%m;4. 顺序队列与循环队列的比较：顺序队列与循环队列的比较：顺序队列顺序队列循环队列循环队列队列队列空空的条件的条件rear=front=-1rear=front队列队列满满的条件的条件front=-1且且rear=m-1front=(rear+1)%m队列队列满满时，所时，所存元素的个数存元素的个数m个个m-1个个队列在一般情队列在一般情况

11、下，所储元况下，所储元素的个数素的个数rear-front（rear-front+m）%m（四）链队列（四）链队列1. 形态形态2.特点：特点：（1）是一个单链表；）是一个单链表；（2）是一个队列，入队在）是一个队列，入队在r后面，出对在头节点后面；后面，出对在头节点后面；（五）队列应用（五）队列应用3. 循环队列的几个关键点：循环队列的几个关键点：（1）循环队列）循环队列空空的条件：的条件：front=rear;（2）循环队列）循环队列满满的条件：的条件：front=（ rear）%m;（3）循环队列）循环队列满满时，元素个数为：时，元素个数为：m-1;（4）一般情况下，循环队列）一般情况下

12、，循环队列中中，元素个数为，元素个数为（rear-front+m）%m;（三）循环队列（三）循环队列3. 循环队列的几个关键点：循环队列的几个关键点：（1）循环队列）循环队列空空的条件：的条件：front=rear;（2）循环队列）循环队列满满的条件：的条件：front=（ rear）%m;（3）循环队列）循环队列满满时，元素个数为：时，元素个数为：m-1;（4）一般情况下，循环队列）一般情况下，循环队列中中，元素个数为，元素个数为（rear-front+m）%m;（一）二维数组（一）二维数组 的概念的概念1.二维数组二维数组 的操作的操作2.二维数组二维数组 的存储结构的存储结构1）以行为主

13、序的存储方法）以行为主序的存储方法2）以列为主序的存储方法）以列为主序的存储方法（二）二维数组（二）二维数组 元素地址的计算元素地址的计算例例9-6 已知数组已知数组A108,每个元素占每个元素占4个字节，数个字节，数组的首地址为组的首地址为1000，试分别以行和以列为主序求，试分别以行和以列为主序求，元素元素A53的地址的地址（二）二维数组（二）二维数组 元素地址的计算元素地址的计算例例9-7 已知二维数组已知二维数组A910,试问元素试问元素A85按行按行存储的地址与哪个元素按列存储的地址相同。存储的地址与哪个元素按列存储的地址相同。（一）基本概念（一）基本概念1.特殊矩阵特殊矩阵2.矩阵

14、的压缩存储矩阵的压缩存储对零元素不分配空间，相同元素只分配一个空间。对零元素不分配空间，相同元素只分配一个空间。3.矩阵压缩存储要解决的问题矩阵压缩存储要解决的问题设有设有n阶特殊矩阵阶特殊矩阵A，将非零元素按行依次存放在一，将非零元素按行依次存放在一维数组维数组B中，若中，若Aij=Bk1）已知）已知i、j,求求k。2) 已知已知k，求，求i、j。（二）特殊矩阵（二）特殊矩阵1.三对角阵三对角阵1）已知）已知i、j,求求k。 k=3i-1+j-i+1=2i+j 已知已知k，求，求i、j。 i=(k+1)/3 j=k-2i三对角阵压缩存储至少三对角阵压缩存储至少需要需要3n-2个存储空间个存储

15、空间01234500112342 5673 89104 1112135 1416（二）特殊矩阵（二）特殊矩阵1.三对角阵三对角阵例例9-8 若已知若已知B0存储地址为存储地址为1000，每个元素占，每个元素占3个字个字节，试问三对角阵节，试问三对角阵A压缩存储元素压缩存储元素A5,4在在B中的地址中的地址是多少？是多少？k=2i+j=2*5+4=14（二）特殊矩阵（二）特殊矩阵2.三角阵三角阵1）已知）已知i、j,求求k。 01234500112234536789410111213145151617181920jiik2) 1(（二）特殊矩阵（二）特殊矩阵2.三角阵三角阵1）已知）已知i、j,

16、求求k。 ijinik2) 12(01234500123451 6789102 111213143 1516174 18195 20（二）特殊矩阵（二）特殊矩阵2.三角阵三角阵由由 ，得，得 k=19。 jiik2) 1(1.（2009.4单选）按照单选）按照1，2，3，4，5的次序入栈时，的次序入栈时，不可能的出栈序列是（不可能的出栈序列是（ ）。）。A 1，2，3，4，5 B 2，3，4，5，1 C 5，4，3，2，1 D 5，4，1，2，32.（2010.4单选）若入栈数据元素序列是单选）若入栈数据元素序列是a，b，c，d，则不可能的出栈序列是（则不可能的出栈序列是（ ）。）。A a，b，c，d B c，b，a，d C d，c，b，a D