《数据结构域算法设计-第二章 顺序存储的线性表 课件》由会员分享，可在线阅读，更多相关《数据结构域算法设计-第二章 顺序存储的线性表 课件（24页珍藏版）》请在金锄头文库上搜索。
1、第二章 顺序存储的线性表,1、什么是线性表？线性表是由n(n=0)个数据元素a1,a2,an组成的一个有限序列。 2、数据元素的含义 3、非空线性表的特点,线性表顺序存储结构的基本特点,线性表中所有元素所占的存储空间是连续的。 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。,在线性表的顺序存储结构中，如果各元素所占的存储空间相等，则要在线性表中查找某一个元素是非常方便的。 设首元的存储地址（指第一个字节的地址）为ADR(a1)，每个数据元素占k个字节，则ADR(ai)=ADR(a1)+(i-1)k,在程序设计语言中，通常定义一个一维数组来表示线性表的顺序存储空间。 这是因为程序设计语言
2、中的一维数组与计算机中实际的存储空间结构类似，有些甚至是相同的。 在线性表的顺序存储结构下，可以对线性表进行各种处理，主要有： 插入、删除、查找、排序、分解、各并、复制、逆转等等。,线性表在顺序存储结构下的插入运算,算法描述：在一般情况下，要在第i(1 i n)个元素之前插入一个元素，首先从最后一个元素开始直到第i个元素(共n-i+1个)依次向后移动一个位置，空出第i个位置；然后将新元素插入到第i项。插入结束后，线性表长度加1。,算法实现,输入：线性表的存储空间V(1：m)；线性表的长度n(n m)；插入的位置i;插入的新元素b。 输出：插入后的线性表的存储空间V(1：m)及线性表的长度n。,
3、PROCEDURE INSL(V,m,n,i,b) if (n=m) then OVERFLOW; return if ( i n) then i=n+1 if ( i 1) then i=1 For j=n to i by -1 do V(j+1)=V(j) V(j) = b n =n +1 END,线性表在顺序存储结构下的删除运算,算法描述：在一般情况下，如果要删除第i (1 i n)个元素，则需从第i+1个元素开始，直到第n个元素(共n-i个)依次向前移动一个位置。然后表的长度减1。,算法实现,输入：线性表的存储空间V(1：m)；线性表的长度n(n m)；删除的位置i。 输出：删除后的线
4、性表的存储空间V(1：m)；表的长度n(n m)。,PROCEDURE DESL(V,m,n,i) if (n=0) then under_flow;return if (in) then “Not this element in the list.”; return For j=i to n-1 do V(j)=V(j+1) n=n-1 END,栈及其应用,1、什么是栈？栈(Stack)是限定在一端进行插入与删除的线性表。允许插入与删除的一端称为栈顶，另一端称为栈底。栈顶元素总是最后被插入的元素，从而也是最先能被删除的元素。栈底元素则反之。因此，栈又称为“后进先出”线性表。,栈的基本操作,入
5、栈 退栈 初始化 判空 取栈顶元素,栈的顺序存储,与一般线性表一样，在程序设计中用一维数组S(1 : m)作为栈的顺序存储空间，其中m为栈的最大容量。 栈底指针指向栈空间的低地址一端，即数组的起始地址。 建立一个容量为m的空栈的顺序存储空间，可用C语言描述如下：,#include void init_stack(s,m,top) ET * s; int m, * top; s=malloc (m * sizeof(ET) );* top =0;return; ,入栈运算,入栈运算是指在栈顶位置插入一个新元素。 这个运算分为两个步骤：首先将栈顶指针加一，然后将新元素插入到栈顶指针所指位置。,算法
6、实现,输入：栈顺序存储空间S(1 : m);栈顶指针top;入栈的元素x； 输出：x入栈后的栈顺序存储空间S (1 : m)及栈顶指针top。,PROCEDURE PUSH(S,m,top,x) If (top=m) then Stack overflow; return top= top+1 S(top)=x END,退栈运算,退栈运算分两种情况：提取或删除栈顶元素。若为前者，则将栈顶元素赋给一个指定的变量，然后再将栈顶指针top减1；一般为前者。 输入：栈顺序存储空间S(1 : m);栈顶指针top; 输出：退栈后的栈顺序存储空间S(1 : m);栈顶指针top;存放弹出元素的变量y。,算
7、法,PROCEDURE POP(S,m,top,y) If (top=0) then Stack underflow;return y=S(top) top=top-1; END;,栈的应用一：表达式求值,现以简单的算术表达式为例，假设在表达式中只有+、-、 * 、/ 四种运算符，所有的运算对象均为单变量。 为了便于处理，还假设表达式的最后有一个结束符“ ； ”，而且“ ； ”的优先级最低。,四则运算的规则,A、先乘除，后加减 B、从左算到右 C、先括号内，后括号外,设栈,在具体处理表达式之前，先设置两个栈： 1、运算符栈：用于在处理过程中存放运算符。开始时，在该栈中先压入一个“ ; ”. 2、操作符栈：用于在处理过程中存放操作数。,算法实现,从左至右依次读出表达式中的符号，每读出一个符号按以下原则进行处理： 1、若读出的是操作数，则将该操作数压入操作数栈，并依次读下一个符号。 2、若读出的是运算符栈，则作进一步判断：,A、若读出的运算符优先级 大于 运算符栈栈顶运算符的优先级，则将读出的运算符压入运算符栈，并依次读下一个符号。 B、若以上反之（不大于），则从操作数栈连续退出两个操作数，并从运算符栈退出一个运算符作相应的运算，再将结果压入操作数栈。 C、若读出的是表达式结束符“ ； ”，且运算符栈栈顶亦为“ ； ”，则表达式处理结束。最后的计算结果放在操作数栈的栈顶位置,
