数据结构c版第2章线性表.ppt

1 2.3 线性表的链接存储结构及实现 静态存储分配：在编译时为变量分配内存，并且一 经分配就始终占有固定的存储单元，直到该变量退出 其作用域。 动态存储分配：在程序的运行期间根据实际需要随时 申请内存，并在不需要时释放。C+中动态存储分配是 通过指针实现的。 2 静态存储分配 顺序表事先确定容量 链 表动态存储分配 运行时分配空间 n链式存储分配的特点： 根据线性表的长度动态的申请存储空间，以解决 顺序存储中存在的存储空间难以确定的问题。 n链式存储结构的实现 单链表 双向链表 循环链表等 3 单链表：线性表的链接存储结构之一。 存储思想：用一组任意的存储单元存放线性表的元素。 连续 不连续 零散分布 4 存储特点： 1.逻辑次序和物理次序 不一定相同。 2.元素之间的逻辑关系 用指针表示。 例：(a1, a2 ,a3, a4)的存储示意图 单链表 0200 0208 0300 0325 a1 0200 a2 0325 a3 0300 a4 5 单链表 单链表是由若干结点构成的； 单链表的结点只有一个指针域。 data：存储数据元素 next：存储后继结点的地址 data next 单链表的结点结构： 数据域指针域 0200 0208 0300 0325 a1 0200 a2 0325 a3 0300 a4 结点 数据域 指针域 6 单链表 template struct Node T data; Node *next; /此处也可以省略 ; 如何申请一个结点？ data next 单链表的结点结构 ： 7 单链表 p=new Node ;template struct Node T data; Node *next; ; data next单链表的结点结构： p Node 8 单链表 p=new Node ; data next p Node 如何引用数据元素？ p-data ; *p.data ; data 如何引用指针域？ next p-next; 9 区分：指针变量、指针、指针所指结点、 结点的值 P60 单链表 10 单链表 0200 0208 0300 0325 a1 0200 a2 0325 a3 0300 a4 first a1a2 an 非空表 first=NULL 空表 重点在数据元素之间的逻辑关系的 表示，所以，将实际存储地址抽象。 什么是存储结构？ 11 单链表 0200 0208 0300 0325 a1 0200 a2 0325 a3 0300 a4 first a1a2 an 非空表 first=NULL 空表 头指针：指向第一个结点的地址。 尾标志：终端结点的指针域为空。 12 单链表 0200 0208 0300 0325 a1 0200 a2 0325 a3 0300 a4 first a1a2 an 非空表 first=NULL 空表 空表和非空表不统一，缺点？ 如何将空表与非空表统一？ 13 单链表 头结点：在单链表的第一个元素结点之前附设一个类 型相同的结点，以便空表和非空表处理统一。 非空表 first a1a2 an 空表 first 14 单链表 template class LinkList public: LinkList( )； LinkList(T a , int n); LinkList( ); int Length( ); T Get(int i); int Locate(T x); void Insert(int i, T x); T Delete(int i); void PrintList( ); private: Node *first; / 单链表的头指针 , 可以省略 ; 单链表类的声明 15 单链表的实现按位查找 操作接口T Get(int i):查找第i个元素并返回其值 v核心操作（关键操作）：工作指针后移。从头结点 （或开始结点）出发，通过工作指针的反复后移而将 整个单链表“审视”一遍的方法称为扫描（或遍历） 。 first a1 p a2 p an ai pp 查找成功 p 查找失败 16 1. 工作指针p初始化; 累加器j初始化; 2.1 工作指针p后移; 2.2 累加器j加1; 2. 循环直到p为空或p指向第i个结点 3. 若p为空，则第i个元素不存在，抛出查找位 置异常；否则查找成功，返回结点p的数据元素 ； 单链表的实现按位查找 算法描述伪代码 17 单链表的实现按位查找 template T LinkList:Get(int i) p=first-next; j=1; while (p j+; if (!p) throw “位置“; else return p-data; 算法描述C+描述 p+ +能否完成指针后移？ a1a2 ppp 复杂性分析 template T LinkList:Get(int i) Node *p; int j; p=first-next; j=1; /或p=first; j=0; while (p /工作指针p后移 j+; if (!p) throw “位置“; else return p-data; 查找算法的基本语句是工 作指针 p 后移，该语句执 行的次数与被查结点在表 中的位置有关。 在查找成功的情况下，若 查找位置为 i （ 1 i n ），则需要执行 i-1 次 ， 等概率情况下，平均时 间性能为 O ( n ) 。 单链表是顺序存取结构 18 总结单链表算法的设计模式 （1）设工作指针并初始化 在单链表中，一般要从头指针出发扫描单链表。由于 头指针具有标识单链表的作用，因此，一般不能修改 头指针（除非要修改表头），而是设工作指针。如果 将工作指针初始化在头结点处，则用p=first实现；如 果将工作指针p初始化在开始结点处，则用 p=first-next实现。 19 总结单链表算法的设计模式 （2）通过工作指针的反复后移将整个单链表扫描一 遍 在单链表类中没有定义表长，因此不能用表长来控制 循环，而要用工作指针p来控制，其一般形式为 While(p!=NULL) p=p-next; 单链表算法的核心操作是“工作指针后移”。扫描 是单链表的一种常用技术 20 单链表的实现插入 操作接口void Insert(int i, T x):将值为x的新结点插入 到单链表的第i个位置，即将x插入到ai-1和ai之间 如何实现结点ai-1、x和ai之间逻辑关系的变化？ p x s first a1ai-1an ai 算法描述： s=new Node; s-data=x; s-next=p-next; p-next=s; 21 单链表的实现插入 注意分析边界情况表头、表尾。 first a1an ai p x s 算法描述： s=new Node; s-data=x; s-next=p-next; p-next=s; p x s 由于单链表带头结点， 表头、表中、表尾三种 情况的操作语句一致。 22 单链表的实现插入 算法描述伪代码 1. 工作指针p初始化；累加器j初始化； 2. 查找第i-1个结点并使工作指针p指向该结点； 3. 若查找不成功，说明插入位置不合理，抛出插 入位置异常；否则， 3.1 生成一个元素值为x的新结点s； 3.2 将新结点s插入到结点p之后； 23 单链表的实现插入 template void LinkList:Insert(int i, T x) p=first ; j=0; while (p j+; 算法描述C+描述 if (!p) throw “位置“; else s=new Node; s-data=x; s-next=p-next; p-next=s; ， 基本语句？时间复杂度？算法中让p指向第i个结点可以吗？ 24 单链表的实现插入 template void LinkList:Insert(int i, T x) if(i=1)/处理在表头插入的特殊情况 s=new Node； s-data=x; s-next=first; firs=s; 不带头结点单链表的插入算法 ， else 与带头结点的单 链表插入操作相同 25 单链表的实现删除 操作接口T Delete(int i):将单链表的第i个结点删去 并返回被删元素值; p 如何实现结点ai-1和ai之间逻辑关系的变化？ first a1ai-1ai+1ai 算法描述： q=p-next; x=q-data; p-next=q-next; delete q; q 26 单链表的实现删除 算法描述： q=p-next; x=q-data; p-next=q-next; delete q; 注意分析边界情况表头、表尾。 pqpq 表尾的特殊情况： 虽然被删结点不存在， 但其前驱结点却存在。 p-next=NULL first a1ana2 27 单链表的实现删除 算法描述伪代码 1.工作指针p初始化；累加器j清零； 2. 查找第i-1个结点并使工作指针p指向该结点； 3. 若p不存在或p不存在后继结点，则抛出位置异常； 否则， 3.1 暂存被删结点和被删元素值； 3.2 摘链，将结点p的后继结点从链表上摘下； 3.3 释放被删结点； 3.4 返回被删元素值； 28 单链表的实现删除 template T LinkList:Delete(int i) p=first ; j=0; while (p j+; 算法描述C+描述 if (!p | | !p-next) throw “位置”; else q=p-next; x=q-data; p-next=q-next; delete q; return x; 基本语句？时间复杂度？ 29 小结： 在单链表上实现插入和删除操作，无须移动 元素，在将工作指针指向合适的位置后，仅 需要修改结点之间链接关系的指针。 30 单链表的实现构造函数 操作接口LinkList(T a , int n)：生成一个具有n个结点 的单链表，其数据元素为数组an的各数组元素 头插法：将待插入结点插在头结点的后面 。 算法描述： first=new Node; first-next=NULL; 数组a 3512243342 初始化 first 31 单链表的实现构造函数 头插法：将待插入结点插在头结点的后面 。 数组a 3512243342 算法描述： s=new Node; s-data=a0; s-next=first-next; first-next=s; 插入第一个元素结点 first 35s 操作接口LinkList(T a , int n)：生成一个具有n个结点 的单链表，其数据元素为数组an的各数组元素 32 单链表的实现构造函数 头插法：将待插入结点插在头结点的后面 。 操作接口LinkList(T a , int n)：生成一个具有n个结点 的单链表，其数据元素为数组an的各数组元素 数组a 3512243342 算法描述： s=new Node; s-data=a1; s-next=first-next; first-next=s; 依次插入每一个结点 12s first 35 33 单链表的实现构造函数 template LinkList: LinkList(T a , int n) first=new Node; first-next=NULL; /初始化一个空链表 for (i=0; i; s-data=ai; /建立一个结点 s-next=first-next; first-next=s; /插入到头结点之后 算法描述： 34 单链表的实现构造函数 尾插法：将待插入结点插在终端结点的后面。 算法描述： first=new Node; rear=first; 数组a 3512243342 初始化 first rear 操作接口LinkList(T a , int n)：生成一个具有n个结点 的单链表，其数据元素为数组an的各数组元素 35 单链表的实现构造函数 尾插法：将待插入结点插在终端结点的后面。 操作接口LinkList(T a , int n)：生成一个具有n个结点 的单链表，其数据元素为数组an的各数组元素 算法描述： s=new Node; s-data=a0; rear-next=s; rear=s; 数组a 3512243342 插入第一个元素结点 first rear 35s rear 36 单链表的实现构造函数 尾插法：将待插入结点插在终端结点的后面。 操作接口LinkList(T a , int n)：生成一个具有n个结点 的单链表，其数据元素为数组an的各数组元素 数组a 3512243342 算法描述： s=new Node; s-data=a1; rear-next=s; rear=s; 依次插入每一个结点 first rear 35 rear 12s rear 37 单链表的实现构造函数 尾插法：将待插入结点插在终端结点的后面。 操作接口LinkList(T a , int n)：生成一个具有n个结点 的单链表，其数据元素为数组an的各数组元素 数组a 3512243342