顺序存储的线性表

《顺序存储的线性表》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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