《大学计算机基础与思维》第2章 线性数据结构.pptVIP

第2章 线性数据结构 2.1 线性表 2.2 栈和队列 2.3 串和数组 本章小结 2.1.1、线性表的定义及基本操作 几个线性表的例子： 例2-1 26个大写的英文字母表：(A，B，C，...，Z) 例2-2 某校从1996年到2002年各种型号计算机拥有量的变化情况，可以用线性表给出： (200，220，250，300，400，700，1200) 例2-3 某单位职工政治面貌登记表如表2-2所示，每个职工的情况为一条记录，它由职工号、姓名、性别、职称、工龄、政治面貌六个数据项组成。 注意： 线性表中数据元素在不同的环境下可以有不同的具体含 义，但在同一线性表中数据元素性质必须相同。 Next (L, x ) 初始条件：线性表L已存在； 操作结果：若x是L中的元素，且不是最后一个， 取其后继，否则后继为空元素。 Insert(L, i, x ) 初始条件：线性表L已存在，1=i=Length(L)+1; 操作结果：在线性表L的第i个元素之前插入一个新元素x， L的长度加1; Delete(L, i) 初始条件：线性表L已存在且非空， 1=i=Length(L) 操作结果：删除线性表L的第i个元素，L的长度减1； 2.1.2、线性表的顺序存储结构 步骤:（1）判断插入位置是否合适，合适转入步骤(2),否则输出:”插入位置不合适” (2) 判断线性表是否满,未满转入步骤(3),否则输出”线性表已满” （3）当插入位置合适时,把第n个至第i个元素依次后移一个位置 （4）在第i个元素插入元素x,并将表长增加1 指针的概念 假设p是一个pointer类型，区分指针型变量、指针、指针所指的结点和结点的内容这四个密切相关的不同概念： p的值（如果有的话）是一个指针，即是一个所指结点的地址 。 该指针（若不是NULL）指向的某个node型结点用*p来标识。 结点 *p是由两个域组成的记录，这两个域分别用p?data域和p?next域来标识，它们各有自己的值，p?data的值是一个数据元素，p?next的值是一个指针。 栈的五种基本运算： (1) Inistack(S)。初始化栈S为空栈。 (2) Empty(S)。判定S是否为空栈。若S是空栈则返回值为真(Ture)，否则返回值为假(False)。 (3) Push(S，x)。进栈操作。在栈S的栈顶插入数据元素x。 (4) Pop(S)。出栈操作。若栈S不是空栈，则删除栈顶元素。 (5) Gettop(S)。取栈顶元素。它只读取栈顶元素，不改变栈中的内容。 2 栈的存储结构 顺序栈运算 算法2-8 进栈算法。 (1) 定义 #define MAXMUM m /* m为栈中数据元素个数的最大可能值*/ int stack[MAXSIZE]; int top=-1; (2) 入栈 顺序栈运算 算法2-9 出栈算法。 (1) 定义 #define MAXMUM m /* m为栈中数据元素个数的最大可能值*/ int stack[MAXSIZE]; int top; (2) 出栈 当有两个栈共享大小为m的内存空间时，可以把两个栈的栈底分别设在给定内存空间的两端。然后，各自向中间伸展，仅当两个栈顶相遇时才发生溢出。使每个栈可利用的最大空间均有可能超过m/2。这种分配方法如图2-20所示。 2) 栈的链式存储结构——链栈 类似于单链表，链栈的C语言描述如下： struct snode{ int data; struct snode *link; }; typedef struct snode SNODE; 栈顶指针仍是top，其类型为SNODE *，相当于单链表的头指针，可惟一确定一个链栈。当top=NULL，表示一个空链栈。 链栈的运算 3)栈的应用 (1) Iniqueue(Queue)。初始化队列Queue，即置Queue为空队列。 (