线 性 结 构信息技术.pptx

程序设计基础线 性 结 构 线性表是最基本、最简单、最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。线性表的逻辑结构简单，便于实现和操作。 线性表是一个含有n（n≥0）个结点的有限序列。当n=0时，称之为空表；当n=1，线性表仅有一个结点，此结点既是开始结点又是终端结点；当n>1时，对于其中的结点，有且仅有一个开始结点没有前驱但有一个后继结点，有且仅有一个终端结点没有后继但有一个前驱结点，其它的结点都有且仅有一个前驱和一个后继结点。1.1 线性表 线性结构1.定义返回集合中必存在唯一的一个“最后元素”集合中必存在唯一的一个“第一元素”AB除第一个元素之外，均有唯一的前驱除最后一个元素之外，均有唯一的后继DC1.1 线性表 线性表具有下面的几个基本特征: 线性结构在线性表逻辑结构上的基本操作有以下几种：GetElem（L,i）：取表中元素。Length（L）：求表长。2InitList（L）：初始化表。314LocateElem（L,x）：定位。返回元素x在线性表L中的位置。65PriorElem（L,x,pre_x）：取元素x的直接前驱。NextElem（L,x,next_x）：取元素x的直接后继。1.1 线性表 2.线性表的基本操作 线性结构 9 8 7PrintList（L）：输出线性表。ListDelete（L,i）：删除元素。ListInsert（L,i,x）：插入元素。1.1 线性表 线性结构 线性表的顺序存储是指用一组连续的存储单元依次存储线性表中的每个数据元素。用这种存储形式存储的线性表又称为顺序表。在程序设计中，往往用一维数组来做顺序表的存储。1.1 线性表 3.线性表的顺序存储 线性结构 相邻两个数据元素的存储位置计算公式为： LOC(ai+1)=LOC(ai)+L 线性表中任意一个数据元素的存储位置的计算公式为： LOC(ai+1)=LOC(a1)+(i-1)*L1.1 线性表 存储地址内存单元...da1d+La2d+2La3...d+(i-1)Lai...d+(n-1)Lan...... 线性结构采用顺序存储的形式来存储线性表有两大优点： （2）利用上述给出的数学公式，可以快速地计算出任何一个数据元素的存储地址，这在访问线性表中的任一数据元素所花费的时间开销是相同的，适宜于静态查找。这种存取元素的方法称为随机存取法，使用这种存取方法的存储结构被称为随机存储结构。 （1）数据元素的存储位置反映了线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构（物理结构）一致；1.1 线性表 线性结构 缺点：采用顺序存储方式的线性表需要程序预先定义线性表结构，占用固定的内存空间。如果要进行插入数据元素和删除数据元素的操作时，则需移动大量结点。 前面提到过，顺序表的存储空间大小需要在程序设计时预选设置一固定值，这就导致在表中的数据元素个数发生动态变化时会出现表满的情况发生。为了能够避免这种现象，引入了用链式存储方式存储线性表的方法，这样存储形式的线性表称之为链表。链表有单链表、双链表和循环链表之分。 1.1 线性表 线性结构4.线性表的链式存储batcatmatfat∧head…datanext1.1 线性表 单链表采用一个结点存放一个数据元素，每个结点除了包括存放数据元素值的数据域 (data) 外，还包括指向下一个元素的存储位置的指针域（next），最后一个结点的指针域为空 NULL(图示中用∧表示)。单链表的结点结构如下所示： 线性结构 以线性表(bat，cat，fat，hat，jat，lat，mat)为例，来看一下以单链表形式存储的图示： 和顺序表相比，用单链表的存储形式更适合于表中元素频繁变动的线性表。 栈（Stack）是一种特殊的表，这种表只在表的一端进行插入和删除操作。允许插入和删除数据元素的这一端称为栈顶；而另一固定的一端称为栈底。不含任何元素的栈称为空栈。对栈中元素的操作是按照“后进先出”的原则进行的，即后进栈的元素先处理，所以栈又称为后进先出(Last In First Out)表，简称为LIFO表。1.2 栈 线性结构出栈进栈an栈顶an-1···a2a1栈底1.2 栈 线性结构1置空栈 initStack(s)：设置一个空栈S。2进栈 push(S,x)：将元素x进到栈S中。3gettop(S,x)：将栈s的栈顶元素赋给x，栈指针递减。pop(s,x)：将栈s的栈顶元素赋给x，栈指针递减。45判断栈空stackempty(s)：若栈为空，返回1，否则返回0。1.2 栈 栈的基本操作包含下面几种： 线性结构1.2 栈 栈用顺序表存储，分配一块连续的内存区域存放栈中元素，并用一个变量指向当前