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

计算机软件基础第二篇数据结构基础第九章栈、队列和数组一、栈（stack）（一）栈的概念1.栈：是一种后进先出的线性表，简称为LIFO表（LastInFirstOut）。2.栈顶（Top）：栈中进行插入、删除操作的一端（即：变化端）。3.栈底（Bottom）：栈中固定不变的一端。4.栈的存储结构：顺序存储和链式存储。一、栈（stack）（二）顺序栈-101234bottomtop栈空（top=-1）-101234topbottom1.形态进栈（top=0）Atop一、栈（stack）-101234bottomtop栈满（top=m-1）ABCDEtoptoptoptoptopbottom出栈-101234ABCDEtoptoptop栈的体积：一个栈所能容纳元素个数一、栈（stack）3.顺序栈的类型#definem100//定义栈的最大容量为100structseqstack{datatypedata[m];//栈内最多存放m个元素inttop;//指向栈顶的指针}s;一、栈（stack）4.顺序栈的基本运算----进栈step1:判断栈是否已满，若满，则上溢，否则进行下一步；step2:栈顶指针上移一个节点；Step3:将x加入到top指定的位置。voidpush(s,x){ if(s.top==m-1)上溢；

else { s.top++; s.data[s.top]=x; } }一、栈（stack）5.顺序栈的基本运算----退栈step1:判断栈是否为空，若空，则下溢，否则进行下一步；Step2:保留被删除元素到变量x中；step3:栈顶指针下移一个节点；voidpop(s){ if(s.top==-1)下溢；

else { x=s.data[s.top]; s.top--; } }一、栈（stack）（三）链栈1.形态Lsabx非空栈栈顶元素栈底元素Ls空栈链栈：是一个不带表头节点的单链表（栈顶指针直接指向栈顶元素）。一、栈（stack）（三）链栈2.类型定义structnode{datatypedata;structnode*next;}*Ls;一、栈（stack）（三）链栈3.进栈运算step1:申请一个新节点，并让s指向该节点；step2:将x赋给新节点的data域；step3:将原栈点链入新节点的next域；step4:新节点作为新的栈顶节点。voidinsert(Ls,x){ s=(structnode)malloc(sizeof(structnode)); s->data=x; s->next=Ls; Ls=s;}一、栈（stack）（三）链栈4.退栈运算step1:判断栈是否为空，如为空，则直接返回，否则进行第二步；step2:让p指栈顶元素；step3:栈顶指针向下移一位；step4:回收p。voiddel(Ls){if(Ls==NULL)return;else {p=Ls; Ls=Ls->next; free(p); }}一、栈（stack）1.铁路调度系统例9-1有a,b,c三列火车依次进栈，试问可能有多少种出栈顺序，它们分别是什么？（四）栈的运用例9-2有a,b,c,d,e,f六列火车依次进栈，试问能否得到下列出栈顺序：（1）cbedfa（2）cdfeab一、栈（stack）2.算术表达式求值对于算术表达式的求值，主要就是解决算术运算符的优先级问题，有以下规则：先进行乘除运算，再进行加减运算（乘除优先级大于加减）；对于相同优先级的运算符，从左向右计算；若要改变优先级，可使用括号。对有括号的表达式，先计算括号内，再计算括号外。在表达式的计算过程中，既要保存操作数，又要保存运算符。这时，可定义两个栈，一个用来保存操作数，一个用来保存运算符。

（四）栈的运用一、栈（stack）例9-3已知x=9+4*6/8-5,试写出表达式求值时栈的变化过程（四）栈的运用例9-4分析下列程序，写出运算结果，说明其功能。voidf(intn){if(n>1){f(n/2);printf("%1d",n%2);}

main(){f(26);}一、栈（stack）例9-5利用栈逆置单链表。（四）栈的运用voidg(s,head){lnitstack(s);p=head->next;while(p!=NULL{push(s,p-data);p=p->next}p=head->next;while(!empty(s))｛p->data=pop(s);p=p->next;}}二、队列（queue）（二）顺序队列1.形态：-1102345f=r=-1队列空-1102345f入队列arbcrr注意：入队时，头指针保持不动，尾指针往后移。二、队列（queue）（二）顺序队列1.形态：-1102345f队列满-1102345f出队列rabcdefabcdefrfff注意：出队时，尾指针保持不动，头指针往后移。二、队列（queue）（二）顺序队列2.类型定义：#definem100structseqq{datatypedata[m];intfront;intrear;}sq;二、队列（queue）3.顺序队列的基本运算----入队step1:判断队列是否已满，若满，则返回，否则进行下一步；step2:队尾指针后移一个节点；Step3:在队尾指针的位置加入x。voidenterq(sq,x){ if(sq.rear==m-1)return; else { sq.rear++; sq.data[sq.rear]=x; }}

二、队列（queue）4.顺序队列的基本运算----出队step1:判断队列是否为空，若空，则返回，否则进行下一步；Step2:保留被删除元素到变量x中；step3:栈顶指针后移一个节点；voiddeq(sq){ if(sq.front==sq.rear=-1)return；

else { x=s.data[sq.front]; sq.front++; } }二、队列（queue）（三）循环队列1.顺序队列的假满：当队列中r=m-1，f不等于-1时，顺序队列出现假满现象。如：0-112345678abcfr二、队列（queue）（三）循环队列2.循环队列：把顺序队列的头尾相接所形成的一个环形队列，称为循环队列，如图：0123456789abcfr说明：（1）无论是入队列，还是出队列，均沿着逆时针方向进行；（2）牺牲了f所指空间。二、队列（queue）（三）循环队列3.循环队列的几个关键点：（1）循环队列空的条件：front=rear;（2）循环队列满的条件：front=（rear

+1）%m;（3）循环队列满时，元素个数为：m-1;（4）一般情况下，循环队列中，元素个数为（rear-front+m）%m;

二、队列（queue）4.顺序队列与循环队列的比较：顺序队列循环队列队列空的条件rear=front=-1rear=front队列满的条件front=-1且rear=m-1front=(rear+1)%m队列满时，所存元素的个数m个m-1个队列在一般情况下，所储元素的个数rear-front（rear-front+m）%m二、队列（queue）（四）链队列1.形态abx非空第一个元素节点最后一个元素节点空2.特点：frontfront头节点（1）是一个单链表；（2）是一个队列，入队在r后面，出对在头节点后面；二、队列（queue）（五）队列应用3.循环队列的几个关键点：（1）循环队列空的条件：front=rear;（2）循环队列满的条件：front=（rear

+1）%m;（3）循环队列满时，元素个数为：m-1;（4）一般情况下，循环队列中，元素个数为（rear-front+m）%m;二、队列（queue）（三）循环队列3.循环队列的几个关键点：（1）循环队列空的条件：front=rear;（2）循环队列满的条件：front=（rear

+1）%m;（3）循环队列满时，元素个数为：m-1;（4）一般情况下，循环队列中，元素个数为（rear-front+m）%m;三、数组（一）二维数组的概念1.二维数组的操作2.二维数组的存储结构1）以行为主序的存储方法2）以列为主序的存储方法（二）二维数组元素地址的计算例9-6已知数组A[10][8],每个元素占4个字节，数组的首地址为1000，试分别以行和以列为主序求，元素A[5][3]的地址三、数组（二）二维数组元素地址的计算例9-7已知二维数组A[9][10],试问元素A[8][5]按行存储的地址与哪个元素按列存储的地址相同。四、特殊矩阵的压缩存储（一）基本概念1.特殊矩阵2.矩阵的压缩存储对零元素不分配空间，相同元素只分配一个空间。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个存储空间012345001

1234

2

567

3

8910

4

1112135

1416四、特殊矩阵的压缩存储（二）特殊矩阵1.三对角阵例9-8若已知B[0]存储地址为1000，每个元素占3个字节，试问三对角阵A压缩存储元素A5,4在B中的地址是多少？k=2i+j=2*5+4=14四、特殊矩阵的压缩存储（二）特殊矩阵2.三角阵1）已知i、j,求k。

01234500

112

2345

36789

41011121314

5151617181920下三角阵四、特殊矩阵的压缩存储（二）特殊矩阵2.三角阵1）已知i、j,求k。

上三角阵01234500123451

6789102

111213143

1516174

18195

20四、特殊矩阵的压缩存储（二）特殊矩阵2.三角阵由，得k=19。

例9-9一个对称阵A按下三角阵压缩存储到B[0]开始的一维数组中，已知b[0]的首地址为1000，每个元素占4个字节，试问矩阵A4,5的存储地址是多少？历年真题演练1.（2009.4单选）按照1，2，3，4，5的次序入栈时，不可能的出栈序列是（）。A1，2，3，4，5

B2，3，4，5，1C5，