2014软基新后缀版栈队列串数组

1、软件技术基础线性结构栈、队列制作主讲段景山栈的引入请看下面的案例，并思考问题小陈作业没有及时完成，第二天写完后，交到段老师的办公室里，正好段老师不在。小陈看到大家的作业本都摞成一叠放在段老师的办公桌上，就把自己的作业本放到本子堆上。正要离开的时候，转过了一个念头，就想把本子插到作业本堆的下面。这在他费力地搬开上面的作业本时，段老师回来了，及时地制止了他小陈为什么想要把作业放到下面？这反映出“作业本堆”结构的什么特点？栈结构2、堆栈 stack栈是特殊的线性表，仅在表的一端进行插入或删除操作是抽屉一类物理实体的逻辑抽象类似仓库、抽屉的结构an.a2a1栈顶入栈出栈栈底特点：（1）对栈内数据的操作

2、总在栈顶进行 （2）数据进栈称为“压入”push（3）数据出栈称为“弹出”pop（4）遵循“后进先出”的原则LIFO用数组实现栈顺序栈（一）2.1用数组实现栈（1）定义若定义a0为栈底，top为栈顶（2）压入 push将新元素放在栈顶当新元素入栈时，栈顶上移，新元素放在栈顶。aMAX-1.253150.360栈顶typedef struct stack_typeelemtype dataMAXNUM;int top; /栈顶元素所在位置stack_type;.stack.top = stack.top + 1;stack.datastack.top = new_one;new_one栈顶元素所

3、在位置a1a2元素个数为top1顺序栈（一）（3）弹出 pop从栈顶移出一个数据栈顶元素拷贝出来栈顶下移拷贝出来的栈顶作为函数返回值46aMAX-1.253150a1a2栈顶out360elemptype pop(stack_type *stack)elemtype out;if(stack-top datastack-top;stack-top = stack-top -1;return out;顺序栈（一）（4）栈空判断（5）置栈空（6）栈满判断if( stack.top = = 0 ? )if( stack.top = MAXNUM 1 )a1stack.top栈顶元素所在位置top的数

4、理含义非常别扭顺序栈（常用定义）若定义top为栈顶之上新空间位置（2）压入（3）弹出（4）栈空判断条件（5）置栈空 （6）栈满判断条件amax-1.a1a0.atop栈顶new_onea1a2stack.top = stack.top + 1;stack.datastack.top = new_one;atopstack.top = stack.top 1;out = stack.datastack.top;stack.top = 0stack.top = 0;元素个数为top有更好的逻辑解读stack.top = MAX_NUM顺序栈（6）栈的应用程序的调用，中断的嵌套proc A( ) .

5、 call B( ); . call C( );proc B( ).call C( ).proc C( ).A和B都会调用C，单从函数C的角度，当C执行完后，应该返回A还是B呢？顺序栈（6）栈的应用程序的嵌套，中断的嵌套proc A( ) . call B( ); . call C( );proc B( ).call C( ).proc C( ).程序A程序B程序C程序A程序B程序C程序C利用用户栈实现了程序调用后回到调用处用数组实现栈程序的嵌套与局部变量程序的指令位置和局部变量都存放在用户栈当C()被调用时c函数的局部变量会覆盖B的局部变量proc A( ) int a,b; . call

6、B( ); call C( );proc B( ) int x,y;.程序A a、b程序B x、y程序C o、pproc C( ) int o,p;.用链表实现栈2.2用链表实现栈（1）定义a1a2anhead栈顶在表头typedef struct lstack_typenode_type * top;int length;lstack_type;入栈出栈top链栈（2）压入push（3）弹出popvoid push(stack, new_node)new_node-next = stack-top;stack-top = new_node;stack-length +;node_type *

7、 pop(stack)node_type* out;out = stack-top;stack-top = stack-top-next;stack-length -;return out;a1newstack-topout链栈（4）栈空判断stack.top = NULL;（5）置栈空能否简单的使用 stack.top = NULL ?如果栈中还有链点，必须逐个将链点占用的空间释放int isEmpty(stack)if(stack.top = NULL)return YES;else return NO;void clean(stack)node_type * temp;while( !

8、empty(stack)temp = pop(stack);free(temp); 1、逐个将链点弹出2、释放链点空间a1a2an入栈出栈队列的引入你到食堂打饭时，是选择排队呢，还是到窗口前挤一下，试试运气，看能不能早点买到？在美国，有一次到迪斯尼专卖店买小朋友的礼物。选好了一双漂亮的小鞋子后，看到有一个收银台是空的，就直接走到那里去交钱，可是售货员却不给结账，仔细一瞧，原来大家都在另一边排队呢！老外真是死板啊。又一次，大家去坐公交，我们到公交站时，还没有人，后来陆陆续续来了一些老外。车来了，因为我们是最早到的，就习惯性地就先走到车门边，可是这一次又遭到了周围眼光的鄙视，原来大家都在站牌前依次

9、排队。后来，我们就养成了习惯：在美国，要先找排队的位置。为什么要排队呢？队列这种结构有什么特点呢？为什么一定要排队呢？队列3、队列类似于排队机制的结构队列是特殊的线性表，节点的插入仅限于在表尾进行，节点的删除仅限于在表头进行入队出队队头队尾队列特点：（1）对队列的操作在表的两端进行（2）仅在队尾加入节点入队enqueue（3）仅在队首移出节点出队dequeue（4）遵循“先进先出”的原则FIFO入队出队队头队尾用数组实现队列3.1用数组实现队列（1）定义a0队首队尾a1.anMAXfrontreartypedef struct queue_typeelemtype dataMAXNUM;int

10、 front;int rear;queue_type;用数组实现队列（2）入队与出队移元素？移队首、尾指针frontrear入队出队入队出队入队数组空间溢出而使操作失败，但此时数组前面是有空间的平均N次移动元素？用循环数组实现队列3.2用循环数组实现队列入队rear = rear + 1( )% MAXNUMfrontrear% 整除取余设MAXNUM 5，rear4则新元素加入队列后：rear （41） 50，新元素放在a0内用循环数组实现队列frontrearfrontrear“循环队列”元素位置？用循环数组实现队列frontrearfrontrear“循环队列”元素位置？用循环数组实现队

11、列队满条件“队空条件”frontrearfrontrearfront = = rear ？(rear + 1) % MAXNUM = = front如果rear表示队尾节点的位置，则有一个节点的队列的指针位置 与 队空时相同产生了二义frontrear用循环数组实现队列队空条件队满条件frontrearfrontrearfront = = rear(rear + 1) % MAXNUM = = front定义：rear为指向队尾下一个可存放节点的位置！（此乃正途）队列满时还有一个空位置！用循环数组实现队列frontrearfrontrear循环队列元素位置？frontrear用循环数组实现队列

12、void enqueue(queue, new_one)queue-dataqueue-rear = new_one;queue-rear = (queue-rear +1) % MAXNUM; 入队算法frontrearif( (queue-rear + 1) % MAXNUM = = queue-front )error(1);else队尾指示向后移动一格队列尾部放入新节点队列已满？用循环数组实现队列出队算法课堂练习frontrearelemtype dequeue(queue) elemtype out； if( queue-rear = = queue-front )error(2);

13、 elseout queue-dataqueue-front;queue-front = (queue-front +1) % MAXNUM; return out；用循环数组实现队列思考：在循环队列的第K个元素后插入一个新元素插队如何确定aK的位置？如何搬移节点，以腾出空位放入新元素？frontrear扩展：循环队列空间的充分利用教材作业第13题设置一个变量tag，用来标明当front=rear时，究竟是队列变满（tag=1），还是队列变空（tag = 0）frontrearvoid enqueue(queue, new_one)if( queue-front = queue-rear )i

14、f( queue-tag = 1 )return;/队列满了queue-dataqueue-rear = new_one;queue-rear = (queue-rear +1) % MAXNUM; /插入新元素，看看要不要设置队满状态if( queue-front = queue-reat )queue-tag = 1;tag?0:1用链表实现队列3.3用链表实现队列（一）定义a1a2anfrontreartypedef struct lqueue_typenode_type * front;node_type * rear;int length;用链表实现队列（二） 入队新链点插入到队尾注

15、意：队列为空时，rear和front都要指向新元素（三） 出队删除队首链点注意：当队列被删空时，rear指针也要置空new_node-next = NULL;list-rear -next = new_node;list-rear = new_node;list-front = list-front-next；if(list-front = NULL)list-rear = NULL;temp = list-front;a1a2anfrontrearif( list-front = NULL)list-front = new_node;串结构4、串串即字符串：由零到多个字符组成的连续有限序列串

16、是一种线性结构串符合线性表的特性（特别是顺序表）字符串的特殊性在于对串有一些特殊的操作元素字符元素间的关系字符串中字符的先后次序线性串的自学引导与线性表相比，串操作的特殊性在什么地方对比紧缩格式与非紧缩格式，为什么会有这两种格式。结合串的操作，谈谈顺序存储串和链接式存储串各自的优、缺点。串结构4.1访问操作基本访问：根据字符在串中位置获得字符；根据字符获得它在串中位置遍历：逐个访问串中字符部分访问（求子串）：获得串中指定位置开始的多个元素获得子串在串中的位置课堂练习：以姓名为例分别给出各种操作应用示例。如：Duan Jingshan取得J所在的位置可以获得姓的长度串结构4.2插入基本插入：在串

17、中指定位置插入一个字符子串插入：在串中指定位置插入多个字符4.3删除基本删除：在串中指定位置删除字符子串删除：在串中指定位置删除多个字符4.4其它操作串连接：一个串连在另一个串的后面，形成新串求串长、串比较、子串替换 .串的操作是文字处理软件的基础串结构4.5串的实现（1）字符数组（用数组实现串）紧缩格式：数组每一个单元类型都是字符型，可放入一个字节的字符非紧缩格式（思考：有什么用？）数组的单元不是字符型24个字节Duana0a1a2a3char a4;共4字节Duanlong a4;共16字节a0a1a2a3串结构（2）字符链表（用链表实现串）链表的每个链点的元素域放入一个字符操作方便，但空

18、间开销大链点元素域占一个字节链点指针域占四个字节开销为4/5studetn二维数组（矩阵）5、二维数组行关系，列关系均是线性关系5.1二维数组的顺序存放（一）行优先存放计算aij的存放位置：设每个元素占据S个存储单元a11a12aijamna21.a11 a12. a1na21 a22. ai1 ai2 .ain. am1 am2 . amnLoc(aij) = Loc(a11) + ( i - 1)*n + (j - 1)*S计算前面有多少个元素ji二维数组（二）列优先存放a11 a21. am1a12 a22. am2a1j a2j .aii. a1n a2n . amnLoc(aij)

19、= Loc(a11) + ( j - 1)*m + (i - 1)*Sa11a12aijamna21.ji二维数组5.2矩阵的压缩存储(1)对称矩阵，三角矩阵的压缩对称矩阵：a i , j = a j , i 三角矩阵：上三角为0，或下三角为0只存储上或下三角内的元素，节约近一半的存储空间a11 a21a22a31a32a33a41 aii. an1 an2 . ann.1356342742155360二维数组(1)对称矩阵，三角矩阵的压缩i = j 时，元素位于下三角Loc(aij) = Loc(a11) + ( i ( i - 1) / 2 + ( j - 1)*Si j 时，元素位于上三

20、角Loc(aij) = Loc(a11) + ( j ( j - 1) / 2 + ( i - 1)*Sa11 a21a22a31a32a33a41 aii. an1 an2 . ann.13563427421553601+2+3+(i-1)二维数组三对角矩阵（带状矩阵）a11a12000a21a22a23000a32a33a34000a43a4400000ann-10000an-1nanna11 a12a21a22a23a32a33 aii-1 aii aii+1 . annLoc(aij) = Loc(a11) + ( ( i - 1)*2 + j - 1)*S特殊矩阵压缩的应用一副普通的

21、图当然不会总是特殊矩阵但是把图分成很多小块，那么一个小块是特殊矩阵的概率就很高了矩阵压缩的引入三角和方框是两幅32*32大小，256位色的bmp图片，即每个像素点用1个字节记录。二维数组(2)稀疏矩阵矩阵中的非零元素很少，分布没有规律利用三元存储法先形成三元矩阵再按照行优先顺序方式存储。aij行值，列值，元素值AMN=行数列数 非零元素个数行值 列值 元素值.第一行第一个非零元素.行值 列值 元素值第二个非零元素二维数组稀疏矩阵压缩存储例100630000000100X48000000000412431126134A6351735800500000行数 列数 非零元素个数a18 = 4,8,5,1,1,1,2,4,1,3,2,6,3,7,5,4,1,3二维数组稀疏矩阵三元组定义1)定义三元组元素2)定义三元组typedef struct tuple3tpint row_num; /*行号*/int col_num; /*列号*/elemtype value; /*元素值*/ tuple3tptypedef struct tuple3int row; /*行数*/i