Chapter1线性表.docVIP

Chapter 1 线性表 线性表的逻辑结构 逻辑结构 逻辑定义??? 　线性表（Linear List）是由n（n≥0）个数据元素（结点）a1，a2，…，an组成的有限序列。???　 数据元素的个数n定义为表的长度（n=0时称为空表）。??? 　 将非空的线性表（n＞0）记作：（a1，a2，…，an）??? 　 数据元素ai（1≤i≤n）只是个抽象符号，其具体含义在不同情况下可以不同。逻辑结构特征　　对于非空的线性表:??? 　 有且仅有一个开始结点a1，没有直接前趋，有且仅有一个直接后继a2；???　 有且仅有一个终结结点an，没有直接后继，有且仅有一个直接前趋an-1；??? 　 其余的内部结点ai（2≤i≤n-1）都有且仅有一个直接前趋ai-1和一个ai+1。顺序存储结构 顺序表顺序表的定义 (1) 顺序存储方法　??? 即把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里的方法。(2) 顺序表（Sequential List）　??? 用顺序存储方法存储的线性表简称为顺序表（Sequential List）。结点ai 的存储地址LOC（ai）= LOC（a1）+（i-1）*c?? 1≤i≤n每个结点所占用存储空间大小亦相同占用c个存储单元顺序表上的基本运算链式存储结构 单链表链接方式存储的线性表简称为链表（Linked List）。??? 　链表的具体存储表示为：　　 用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的）　　 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)）单链表的运算1、建立单链表（1） 头插法建表（2） 尾插法建表（3）尾插法建带头结点的单链表单链表的查找运算（1）按序号查找（2） 按值查找插入运算 4删除运算循环链表 循环链表是一种首尾相接的链表。1、循环链表（1）单循环链表——在单链表中，将终端结点的指针域NULL改为指向表头结点或开始结点即可。（2）多重链的循环链表——将表中结点链在多个环上。2、带头结点的单循环链表3、仅设尾指针的单循环链表??? 　用尾指针rear表示的单循环链表对开始结点a1和终端结点an双链表双向链表（Double Linked List）??? 　双（向）链表中有两条方向不同的链，即每个结点中除next域存放后继结点地址外，还增加一个指向其直接前趋的指针域prior。顺序表和链表的比较 栈栈和队列是两种特殊的线性表，它们的逻辑结构和线性表相同，只是其运算规则较线性表有更多的限制，故又称它们为运算受限的线性表栈 栈的定义及基本运算栈的定义??? 　栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。　　(1)通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。　　(2)当表中没有元素时称为空栈。　　(3)栈为后进先出（Last In First Out）的线性表，简称为LIFO表。2、栈的基本运算（1）InitStack（S）??? 　构造一个空栈S。（2）StackEmpty（S）??? 　判栈空。若S为空栈，则返回TRUE，否则返回FALSE。（3）StackFull（S）??? 　判栈满。若S为满栈，则返回TRUE，否则返回FALSE。注意：　??? 该运算只适用于栈的顺序存储结构。（4）Push（S，x）??? 　进栈。若栈S不满，则将元素x插入S的栈顶。（5）Pop（S）??? 　退栈。若栈S非空，则将S的栈顶元素删去，并返回该元素。（6）StackTop（S）??? 　取栈顶元素。若栈S非空，则返回栈顶元素，但不改变栈的状态。顺序栈 栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。1、 顺序栈的类型定义? #define StackSize 100 //假定预分配的栈空间最多为100个元素? typedef char DataType;//假定栈元素的数据类型为字符? typedef struct{????? DataType data[StackSize];????? int top;???? }SeqStack; ? 注意：　??? 顺序栈中元素用向量存放??? 　栈底位置是固定不变的，可设置在向量两端的任意一个端点??? 　栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top（通常称top为栈顶指针）来指示当前栈顶位置2、 顺序栈的基本操作 ? 前提条件：??? 　设S是SeqStack类型的指针变量。若栈底位置在向量