《教学课件第3单元线性数据结构二》由会员分享，可在线阅读，更多相关《教学课件第3单元线性数据结构二（53页珍藏版）》请在金锄头文库上搜索。
1、第第3单元单元 线性数据结构（二）线性数据结构（二）l 1.3 栈和队列栈和队列 (P32P46)l 1.4 串和数组串和数组 (P47P55)11.3 栈和队列栈和队列一、栈的逻辑结构和运算一、栈的逻辑结构和运算l1.堆栈堆栈(Stack)概念概念1) 只允许在同一端进行插入和删除操作只允许在同一端进行插入和删除操作的特殊线性表。的特殊线性表。 2) 允许进行插入和删除操作的一端称为允许进行插入和删除操作的一端称为栈顶，另一端为栈底；栈顶，另一端为栈底；3) 栈底固定，而栈顶浮动；栈底固定，而栈顶浮动；4) 特点：后进先出（特点：后进先出（LIFO）。）。5) 空栈空栈:元素个数为零的栈。元
2、素个数为零的栈。22. 栈的基本运算栈的基本运算lSetnull(Stack) 置栈为空；置栈为空；lEmpty(Stack) 判断栈是否为空；判断栈是否为空；lPush(Stack,x) 进栈进栈-在栈顶插入元素在栈顶插入元素x lPop(Stack) 出栈出栈-删除栈顶元素；删除栈顶元素；lGettop(Stack) 取栈顶元素取栈顶元素l 顺序栈顺序栈: 采用顺序存储结构的栈采用顺序存储结构的栈l 链栈链栈: 采用链式存储结构的栈采用链式存储结构的栈3 出栈序列 操作序列 1 2 3 s x s x s x 1 3 2 s x s s x x 2 1 3 s s x x s x 2 3
3、1 s s x s x x 3 2 1 s s s x x x例例1-10l有三个元素的进栈序列是有三个元素的进栈序列是1，2，3。写出可能的出栈序列。写出可能的出栈序列。43.与堆栈操作有关的术语与堆栈操作有关的术语l1) 栈顶指针栈顶指针TOP用来指出栈顶元素所在的位置用来指出栈顶元素所在的位置l2) 栈空条件：栈空条件： top = -1l3) 栈满条件：栈满条件： top = MAXSIZE-1l4) 上溢上溢 栈满后再进行入栈操作栈满后再进行入栈操作,产生上溢。产生上溢。l5) 下溢下溢 栈已空栈已空,再执行出栈操作，产生下溢。再执行出栈操作，产生下溢。5二、栈的存储结构之一二、栈的
4、存储结构之一:顺序栈顺序栈l1) 采用顺序存储结构的栈采用顺序存储结构的栈l2) 实现实现: 使用一维数组使用一维数组l3) 栈顶位置随进栈和出栈而变化。栈顶位置随进栈和出栈而变化。l4) C语言描述：语言描述： #define MAXSIZE n int stackMAXSIZE; int top = -1; /*下标从下标从0开始开始*/6栈操作举例栈操作举例l a1 a2 an栈底栈底栈顶栈顶MAXSIZE-1TOP1.top=-1A B C2.(空栈空栈)top=2(A、B、C进栈进栈）A B3.top=1(C出栈出栈）4.A B C D E Ftop=MAXSIZE-1(栈满栈满）7
5、算法算法1-8 进栈算法进栈算法step1 判断栈满否，判断栈满否， 若满，显示溢出信息，停止执行若满，显示溢出信息，停止执行 否则，执行否则，执行step 2； Step2 栈顶指针栈顶指针top上移上移(加加1)；Step3 在在top所指的位置插入元素所指的位置插入元素x。8算法算法1-8 进栈算法程序进栈算法程序lpush（int x）l if（top = MAXSIZE -1）l printf（“栈上溢！栈上溢！n”）; l exit （1）; l else l top +； /* 栈指针加栈指针加 1 */l stacktop=x ； /* 元素元素 x进栈进栈 */l l 9算法
6、算法1-9 出栈算法出栈算法 step1 判断栈是否为空；判断栈是否为空； 若空，输出下溢信息，并停止执行；若空，输出下溢信息，并停止执行； 否则，执行否则，执行step2； step2 弹出（删除）栈顶元素；弹出（删除）栈顶元素； step3 栈顶指针栈顶指针top下移下移(减减1)。 step4 返回栈顶元素返回栈顶元素 10算法算法1-9 出栈算法程序出栈算法程序lpop（ ）l int x;l if( top = = -1）l printf(“栈下溢栈下溢n”); exit(1);l elsel x = stack top；top - - ； l return x ；l 115) 两栈
7、共享一个栈空间两栈共享一个栈空间两栈共享：两个栈底分别设在两端，栈两栈共享：两个栈底分别设在两端，栈顶指针顶指针top1和和top2相对中间位置移动，相对中间位置移动，栈间分界线不定。栈间分界线不定。l a.l b.lc. top1 =0 top2=MAXSIZE-1 空栈空栈top1top2栈栈1、栈、栈2均有元素均有元素top1top2栈满栈满12二、栈的存储结构之二二、栈的存储结构之二:链栈链栈l1. 顺序栈的问题顺序栈的问题 1) 最多实现最多实现2个栈的共享个栈的共享 2) 不能用于最大空间事先不知的情况不能用于最大空间事先不知的情况l解决方法解决方法: 链栈链栈13链栈存储结构链栈
8、存储结构l2. 链栈存储结构的链栈存储结构的C语言描述：语言描述： struct snode intdata; struct snode *link; ; typedef struct snode SNODE ; SNODE *top;l链栈空：链栈空：top = NULLl链栈满链栈满: t = NULL /*t为申请的结点为申请的结点l 申请结点失败申请结点失败 14链栈示意图链栈示意图a1a2a3NULL栈底栈底top栈顶栈顶.ai15算法算法1-10 进栈操作算法进栈操作算法lstep1 申请一个链栈结点申请一个链栈结点,l 若若 t=NULL,则链满则链满;l 否则否则,执行执行st
9、ep2 ;lstep2 在在top所指结点之前插入新结所指结点之前插入新结点点,并将并将top指向新申请的结点指向新申请的结点t。16算法算法1-10 进栈操作程序进栈操作程序l push(int x)l SNODE *t;l t=(SNODE * )malloc(sizeof(SNODE);l if (t = = NULL )l printf(“栈已满栈已满n”);l exit(1); l elsel t-data = x; t-link = top;top= t; l 17算法算法1-11 出栈操作算法出栈操作算法l l step1 若链栈空，输出栈溢出信息；若链栈空，输出栈溢出信息； l
10、 否则，执行否则，执行step 2。l step2 删除删除top所指结点，并使所指结点，并使topl 指向被删除结点的后继结点指向被删除结点的后继结点l step3 释放被删除结点的存储空间释放被删除结点的存储空间l step4 返回栈顶元素返回栈顶元素18算法算法1-11 出栈操作程序出栈操作程序l pop( )l SNODE *p; int x;l if ( top = = NULL )l printf(“栈下溢栈下溢n”）；）； exit(1); l else l p=top; top=top-link; l x = p -data ； free(p) ; l return x;l 1
11、9三、队列三、队列l1. 队列概念队列概念1) 只允许在表的一端进行删除操作，在只允许在表的一端进行删除操作，在表的另一端进行插入的特殊线性表。表的另一端进行插入的特殊线性表。2) 队尾队尾(rear)：进行插入操作的一端：进行插入操作的一端3) 队头队头(front)：进行删除操作的一端：进行删除操作的一端4) 特点：先进先出（特点：先进先出（FIFO）。）。a1 a2 an入队插入出队出队删除删除frontrear20 2、队列的操作、队列的操作lSetnull(Queue) 清空队列清空队列lEmpty(Queue) 判断队列是否为空判断队列是否为空lAddqueue(Queue,x)
12、入队入队(插入插入)lDelqueue(Queue) 出队出队(删除删除)lFrontqueue(Queue) 取队头元素取队头元素21 四、队列的顺序存储四、队列的顺序存储l1. 定义空队列定义空队列: 用一维数组用一维数组 #define MAXSIZE n int queueMAXSIZE； int front=-1, rear=-1;l front：队头指针：队头指针;l rear：队尾指针：队尾指针;空队列：空队列：front = rear满队列：满队列：rear = MAXSIZE-1222.入队出队操作入队出队操作l约定：约定：lfront: 总是指向队头元素的前一个位置；总是指
13、向队头元素的前一个位置；lrear: 总是指向队尾元素的位置总是指向队尾元素的位置l结果：结果： 对任何元素，操作都一样对任何元素，操作都一样l 出队出队: 入队入队: l front = front + 1 ； rear=rear+1;l x = queue front； queuerear=x; l frontreara1 a2 an23 举例：顺序队列的入队、出队操作举例：顺序队列的入队、出队操作l1）空队列）空队列l2）A、B、C、D、E入队入队l3）A、B、C出队出队frontrear D E frontrearA B C D E frontrear入队时，入队时，rear在变在变出
14、队时，出队时，front在变在变24 l4）F、G、H入队入队l5）D、E、F、G、H出队，出现假出队，出现假“溢出溢出” frontfrontrear D E F G H rear253. 假溢出假溢出l假溢出假溢出队列是空的情况下出现的溢出。队列是空的情况下出现的溢出。l解决方法解决方法 1) 整个队列左移整个队列左移,费时费时 2) 队列的首尾相连队列的首尾相连-循环队列循环队列l目的目的 队列中真正没有空位置时，才产生溢出。队列中真正没有空位置时，才产生溢出。 264、循环队列、循环队列l1.出队出队(队头指针移动队头指针移动)front=(front+1)%MAXSIZE；l等价于：
15、等价于： if (front+1= MAXSIZE) front = 0 ;else front=front+1;2.入队入队(队尾指针移动队尾指针移动)rear=(rear+1)%MAXSIZErear=(rear+1)%MAXSIZE；等价于：等价于： if (rear+1=MAXSIZE) rear = 0; else rear=rear+1;27 循环队列队空、队满条件循环队列队空、队满条件l约定约定:队头指针指示的队头指针指示的结点不用于存储结点不用于存储元素元素,只作标志只作标志即保留一个节点即保留一个节点l队空条件队空条件front = rear ；l队满条件队满条件front
16、= (rear+1) % MAXSIZErearfront013 2MAXSIZE -1.012.i reari+1front.MAXSIZE -1a1a2a3ai空满28算法算法1-12:循环队列入队算法循环队列入队算法lstep1 判别队列是否已满判别队列是否已满;lstep2 队尾指针后移一个位置队尾指针后移一个位置,将新结将新结点元素值存入当前结点单元。点元素值存入当前结点单元。l 程序程序(略略)29算法算法1-13 循环队列出队算法循环队列出队算法lstep1 判别队列是否为空判别队列是否为空;若空若空,则显则显示示下溢下溢;lstep2 队头指针后移一个位置。队头指针后移一个位置
17、。lstep3 返回队头元素返回队头元素l 程序程序(略略)30五五.队列的链式存储结构队列的链式存储结构l用带头结点的单链表作为队列的链式用带头结点的单链表作为队列的链式存储结构。存储结构。lC语言描述语言描述 struct qnode int data ； struct qnode * next； typedef struct qnode QNODE ； QNODE *front , *rear；31链队列的表示链队列的表示l链队列满链队列满: T = = NULL 没有存储空间没有存储空间l链队列空链队列空: front = =rear l l空队列空队列:l非空队列非空队列:l l f
18、ront rearNULLfront rear NULL.ana2a132算法算法1-14 链队列的入队算法链队列的入队算法lstep1 申请建立一个新结点申请建立一个新结点T;lstep2 判别判别T是否为是否为NULL;若是若是,表示表示l 队列已满队列已满;lstep3 若非空若非空,将将T插入链中插入链中,修改修改rearl 指针。指针。33链队列的入队操作链队列的入队操作laddqueue(int x)l QNODE *t;l t = (QNODE*)malloc(sizeof(QNODE);l if （ t = = NULL）l printf(”无可用空间无可用空间n”);exit
19、(1);l elsel rear - next = t; rear = t;l t -data = x; t -next = NULL ; l 34链队列的出队操作链队列的出队操作l两种情况两种情况:队列长度为队列长度为1,修改头结点指针域和队尾修改头结点指针域和队尾指针。指针。队列长度大于队列长度大于1,只修改头结点指针域只修改头结点指针域an NULLfrontrearQueueQueueQueueQueuefrontrearNULLan TQueueQueueQueueQueuefrontrearrearfronta1 an NULLa1a2 .a2 .an NULL35 栈的应用栈的应
20、用-例例1: 递归过程递归过程l计算计算5的阶乘（的阶乘（5!=54321） if ( n = = 1) return (1); else return ( n * f(n-1); f(2)f(2)f(3)f(3)f(4)f(4)f(5)f(5)top f(1)=1 f(1)=1 2*f(1) f(2)=2*f(1)2*f(1) f(2)=2*f(1)3*f(2) f(3)=3*f(2)3*f(2) f(3)=3*f(2)4*f(3) f(4)=4*f(3)4*f(3) f(4)=4*f(3)5*f(4) f(5)=5*f(4)5*f(4) f(5)=5*f(4)36栈的应用栈的应用-例例2:
21、程序的嵌套调用程序的嵌套调用 main sub1 sub2 sub3l sub2sub2sub1sub1mainmaintop371.4 串和数组串和数组l一一. 串及其运算串及其运算l1. 串的概念串的概念1) 定义定义: 特殊的线性表特殊的线性表,每个数据元素仅每个数据元素仅由单个字符组成由单个字符组成, 如如: A=very good2) 串的长度串的长度: 串中的字符个数串中的字符个数3) 空串空串:串长度为串长度为04) 空格串空格串: 组成串的元素都是空格组成串的元素都是空格5) 子串子串:串中任意个连续字符组成的序列串中任意个连续字符组成的序列6) 两个串的相等两个串的相等:38
22、2.串的基本操作串的基本操作lLENGTH(S) 求串求串S的长度的长度lSUBSTR(S,start,len) 求求S的子串的子串lCONCAT(S1,S2) S2联接在联接在S1末尾末尾lINDEX(S1,S2) 确定确定S2在在S1中的位置中的位置lREPLACE（S1，S2，S3） 用用S3替换串替换串S1中所有与串中所有与串S2相等且不重相等且不重叠的子串叠的子串39二二.串的存储结构串的存储结构l1. 顺序存储结构顺序存储结构l 用连续存储单元存储串的字符序列用连续存储单元存储串的字符序列l 使用字编址方式时，设使用字编址方式时，设1字字4个字节个字节,则则:l(1)非紧缩存储非紧
23、缩存储:一个字的存储单元中只存一个字的存储单元中只存放放1个字符。个字符。l 特点：存储密度低特点：存储密度低,浪费空间浪费空间l(2) 紧缩存储紧缩存储 一个单元中存放一个单元中存放4个字符；个字符；l 特点：节省空间特点：节省空间 访问时要花费分离时间访问时要花费分离时间402. 链表存储结构链表存储结构l (1) 结点由数据域和指针域组成结点由数据域和指针域组成l 图图1-38 l (2) 指针域通常两个字节指针域通常两个字节l 若数据域占一个字节若数据域占一个字节:l 有效存储密度有效存储密度=1/3l 若数据域占四个字节若数据域占四个字节:l 有效存储密度有效存储密度=4/6=2/3
24、413.堆存储结构堆存储结构堆结构堆结构:一种动态存储结构，定义一个很一种动态存储结构，定义一个很大的连续空间和相应的指针结构。大的连续空间和相应的指针结构。指针用来指示串在堆中的位置指针用来指示串在堆中的位置例如，例如，a=BEI，b= JING， c=，d=SHANGHAI；串名串长串名串长 起始地址起始地址a 3 1 b 5 4 c 0 9 d 8 9 B E I J I N G S HA N G H A I 42三三.数组数组l1、数组的定义、数组的定义l数组是有限个数组元素的集合数组是有限个数组元素的集合l数组中所有元素有相同的数据类型数组中所有元素有相同的数据类型l每个数组元素值可
25、以用数组名和一组每个数组元素值可以用数组名和一组下标值唯一的确定；下标值唯一的确定；432.数组元素之间的关系数组元素之间的关系lm行行n列二维数组可以看作是列二维数组可以看作是m个或个或n个一个一维数组维数组:Amxn = (a11a12a1n),(a21a22a2n),. (am1am2amn)或或: a11 a12 a1n a21 a22 a2nlAmxn = am1 am2 amn.443.数组的操作数组的操作l两种基本的操作：两种基本的操作：给定下标，存取相应的数组元素；给定下标，存取相应的数组元素；给定下标，修改相应数组元素的值。给定下标，修改相应数组元素的值。454.数组的顺序存
26、储结构数组的顺序存储结构l无论几维数组无论几维数组,在计算机中都是按一维在计算机中都是按一维数组来存放。数组来存放。l二维数组存放通常采用两种方式：二维数组存放通常采用两种方式：按行优先顺序按行优先顺序按列优先顺序按列优先顺序461) 按行优先顺序存储按行优先顺序存储l按行优先将数组看作若干个行向量按行优先将数组看作若干个行向量l数组中的每个元素由元素的两个下标数组中的每个元素由元素的两个下标表达式唯一的确定。表达式唯一的确定。l地址计算公式：地址计算公式： LOC(aij)=LOC(a11)+(i-1)*n+(j-1)*Ll L: 每个元素所占的存储单元每个元素所占的存储单元472)按列优先
27、顺序存储按列优先顺序存储l 将数组看作若干个列向量。将数组看作若干个列向量。l 数组中的每个元素由元素的两个下标数组中的每个元素由元素的两个下标表达式唯一的确定。表达式唯一的确定。l 地址计算公式：地址计算公式：LOC(aij)=LOC(a11)+(j-1)*m+(i-1)*Ll L: 每个元素所占的存储单元。每个元素所占的存储单元。485.矩阵的压缩存储矩阵的压缩存储l压缩的含义：压缩的含义：相同值的多个元素占用一个存储单元；相同值的多个元素占用一个存储单元；零元素不分配存储单元。零元素不分配存储单元。l(1)特殊矩阵的压缩存储特殊矩阵的压缩存储特殊矩阵特殊矩阵:值相同的元素或非零元素分布值
28、相同的元素或非零元素分布有一定规律的矩阵有一定规律的矩阵压缩压缩:将二维数组的元素压缩到一维数组将二维数组的元素压缩到一维数组关键关键:两个数组的下标之间建立映象关系两个数组的下标之间建立映象关系49例例: 对称矩阵的压缩存储对称矩阵的压缩存储l 对称矩阵的元素满足：对称矩阵的元素满足： aij = aji 1 i ，j nl n*n 个元素压缩存放到个元素压缩存放到 n（n+1）/2 个单元的一维数组中。个单元的一维数组中。l Aij在一维数组中的地址为：在一维数组中的地址为：l i（i-1）/2+j 当当i jl LOC(aij) = l j（j-1）/2+i 当当ij 50对称矩阵的压缩
29、存储对称矩阵的压缩存储l 设有设有A3x3矩阵矩阵,l a11l A3x3 = a21 a22l a31 a32 a33l 存于一维数组存于一维数组S6l S6=(a11, a21,a22, a31,a32,a33)l 1 2 3 4 5 6 LOC(a31)=3(3-1)/2+1= 4 LOC(a22)=2(2-1)/2+2= 3 LOC(a21)=2(2-1)/2+1= 251l常见的特殊矩阵常见的特殊矩阵:对称矩阵对称矩阵 存储主对角线以上存储主对角线以上(下下)的元的元素素上上(下下)三角矩阵三角矩阵 只存储三角阵元素；只存储三角阵元素；带状矩阵带状矩阵 只存储带状元素；只存储带状元素
30、；l(2) 稀疏矩阵的压缩存储稀疏矩阵的压缩存储 利用三元组只存储非零元素；利用三元组只存储非零元素； 三元组三元组: (i,j,aij)52作业、思考题作业、思考题l思考题：思考题：试写出试写出“在带头结点的单循环链表中求表长的在带头结点的单循环链表中求表长的算法算法”。假设一单循环链表的长度大于假设一单循环链表的长度大于1，且表中即无头，且表中即无头结点也无头指针。已知结点也无头指针。已知S为指向链表中某结点的为指向链表中某结点的指针。试写出删除表中结点指针。试写出删除表中结点S 的算法。的算法。假设以数组假设以数组sequm-1存放循环队列的元素，存放循环队列的元素，设变量设变量rear和和quelen分别为指示队尾元素位置分别为指示队尾元素位置和队中元素个数，试写出入队和出队算法。和队中元素个数，试写出入队和出队算法。l第第1章作业：章作业：l 8、10、1153
