《数据结构c版第2章线性表.ppt》由会员分享，可在线阅读，更多相关《数据结构c版第2章线性表.ppt（42页珍藏版）》请在金锄头文库上搜索。
1、12.3 线性表的线性表的链接存储结构及实现链接存储结构及实现 静态存储分配静态存储分配：在编译时为变量分配内存，并且一：在编译时为变量分配内存，并且一经分配就始终占有固定的存储单元，直到该变量退出经分配就始终占有固定的存储单元，直到该变量退出其作用域。其作用域。动态存储分配动态存储分配：在程序的运行期间根据实际需要随：在程序的运行期间根据实际需要随时申请内存，并在不需要时释放。时申请内存，并在不需要时释放。C+C+中动态存储分配中动态存储分配是通过是通过指针指针实现的。实现的。2静态存储分配静态存储分配 顺序表顺序表事先确定容量事先确定容量 链链 表表动态存储分配动态存储分配 运行时分配空间
2、运行时分配空间 n链式存储分配的特点：链式存储分配的特点：根据线性表的长度动态的申请存储空间，以解决根据线性表的长度动态的申请存储空间，以解决顺序存储中存在的存储空间难以确定的问题。顺序存储中存在的存储空间难以确定的问题。n链式存储结构的实现链式存储结构的实现单链表单链表 双向链表双向链表 循环链表等循环链表等 3单链表：单链表：线性表的链接存储结构之一。线性表的链接存储结构之一。存储思想：存储思想：用一组用一组任意任意的存储单元存放线性表的元素。的存储单元存放线性表的元素。连续连续不连续不连续零散分布零散分布4存储特点：存储特点：1.1.逻逻辑辑次次序序和和物物理理次次序序不一定相同。不一定
3、相同。 2.2.元素之间的逻辑关系元素之间的逻辑关系 用指针表示。用指针表示。例：例：( (a a1 1, , a a2 2 , ,a a3 3, , a a4 4) )的存储示意图的存储示意图单链表单链表0200020803000325 a10200 a20325 a30300 a4 5单链表单链表单链表是由若干结点构成的；单链表是由若干结点构成的；单链表的结点只有一个指针域。单链表的结点只有一个指针域。datadata：存储数据元素存储数据元素nextnext：存储后继结点的地址存储后继结点的地址 data next单链表的结点结构：单链表的结点结构：数据域数据域指针域指针域0200020
4、803000325 a10200 a20325 a30300 a4 结点结点数据域数据域指针域指针域6单链表单链表template struct Node T data; Node *next; /此处此处也可以省略也可以省略; 如何申请一个结点如何申请一个结点？ data next单链表的结点结构：单链表的结点结构：7单链表单链表p=new Node ;template struct Node T data; Node *next; data next单链表的结点结构：单链表的结点结构： pNode8单链表单链表p=new Node ; data next pNode如何引用数据元素如何引用
5、数据元素？p-data ;*p.data ;data如何引用指针域如何引用指针域？nextp-next;9区区分分：指指针针变变量量、指指针针、指指针针所所指指结结点点、 结点的值结点的值P60P60单链表单链表10单链表单链表0200020803000325 a10200 a20325 a30300 a4 firsta1a2an非空表非空表first=NULL空表空表重点在数据元素之间的逻辑关系的重点在数据元素之间的逻辑关系的表示，所以，将实际存储地址抽象。表示，所以，将实际存储地址抽象。什么是存储结构什么是存储结构？11单链表单链表0200020803000325 a10200 a2032
6、5 a30300 a4 firsta1a2an非空表非空表first=NULL空表空表头指针：头指针：指向第一个结点的地址。指向第一个结点的地址。尾标志：尾标志：终端结点的指针域为空。终端结点的指针域为空。12单链表单链表0200020803000325 a10200 a20325 a30300 a4 firsta1a2an非空表非空表first=NULL空表空表空表和非空表不统一，缺点？空表和非空表不统一，缺点？如何将空表与非空表统一如何将空表与非空表统一？13单链表单链表头结点：头结点：在单链表的第一个元素结点之前附设一个类在单链表的第一个元素结点之前附设一个类型相同的结点，以便空表和非空
7、表处理统一。型相同的结点，以便空表和非空表处理统一。 非空表非空表firsta1a2an空表空表first14单链表单链表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 *firs
8、t; / / 单单链链表表的的头头指指针针 , , 可以省略可以省略;单单链链表表类类的的声声明明15单链表的实现单链表的实现按位查找按位查找操作接口操作接口T T Get(intGet(int i): i):查找第查找第i i个元素并返回其值个元素并返回其值v核心操作（关键操作）：核心操作（关键操作）：工作指针后移工作指针后移。从头结点。从头结点（或开始结点）出发，通过工作指针的反复后移而将（或开始结点）出发，通过工作指针的反复后移而将整个单链表整个单链表“审视审视”一遍的方法称为一遍的方法称为扫描扫描（或遍历）。（或遍历）。firsta a1 1p pa a2 2p pa an na ai
9、 ip pp p查找成功查找成功p p查找失败查找失败161. 1. 工作指针工作指针p p初始化初始化; ; 累加器累加器j j初始化初始化; ;2.1 2.1 工作指针工作指针p p后移后移; ;2.2 2.2 累加器累加器j j加加1;1;2. 2. 循环直到循环直到p p为空或为空或p p指向第指向第i i个结点个结点3. 3. 若若p p为为空空，则则第第i i个个元元素素不不存存在在，抛抛出出查查找找位位置异常；否则查找成功，返回结点置异常；否则查找成功，返回结点p p的数据元素；的数据元素；单链表的实现单链表的实现按位查找按位查找算法描述算法描述伪代码伪代码17单链表的实现单链表
10、的实现按位查找按位查找template T LinkList:Get(int i) p=first-next; j=1; while (p & jnext; j+; if (!p) throw 位置位置; else return p-data; 算法描述算法描述C+C+描述描述p+ +能否完成指针后移？能否完成指针后移？a1a2ppp复杂性分析复杂性分析template T LinkList:Get(int i) Node *p; int j; p=first-next; j=1; /或或p=first; j=0; while (p & jnext; /工作指针工作指针p后移后移 j+; if
11、 (!p) throw 位置位置; else return p-data;查找算法的基本语句是工查找算法的基本语句是工作作指针指针 p p 后移后移，该语句执，该语句执行的次数与被查结点在表行的次数与被查结点在表中的位置有关。中的位置有关。在在查找成功的查找成功的情况下，若情况下，若查找位置为查找位置为 i （ 1 i n ），），则需要执行则需要执行 i-1 i-1 次，次， 等概率情况下，平均时间等概率情况下，平均时间性能为性能为 O ( n ) 。单链表是顺序存取结构单链表是顺序存取结构18总结单链表算法的设计模式总结单链表算法的设计模式 （1 1）设工作指针并初始化）设工作指针并初始化
12、在单链表中，一般要从头指针出发扫描单链表。由于在单链表中，一般要从头指针出发扫描单链表。由于头指针具有标识单链表的作用，因此，头指针具有标识单链表的作用，因此，一般不能修改一般不能修改头指针头指针（除非要修改表头），而是（除非要修改表头），而是设工作指针设工作指针。如果。如果将工作指针初始化在头结点处，则用将工作指针初始化在头结点处，则用p=first实现；如实现；如果将工作指针果将工作指针p p初始化在开始结点处，则用初始化在开始结点处，则用p=first-next实现。实现。19总结单链表算法的设计模式总结单链表算法的设计模式 （2 2）通过工作指针的反复后移将整个单链表扫描）通过工作指针
13、的反复后移将整个单链表扫描一遍一遍在单链表类中没有定义表长，因此不能用表长来控制在单链表类中没有定义表长，因此不能用表长来控制循环，而要用循环，而要用工作指针工作指针p p来控制来控制，其一般形式为，其一般形式为While(pWhile(p!=NULL)!=NULL) p=p-next; p=p-next; 单链表算法的核心操作是单链表算法的核心操作是“工作指针后移工作指针后移”。扫。扫描是单链表的一种常用技术描是单链表的一种常用技术20单链表的实现单链表的实现插入插入操操作作接接口口void Insert(int i, T x):将将值值为为x x的的新新结结点点插插入入到单链表的第到单链表
14、的第i i个位置，即将个位置，即将x x插入到插入到ai-1和和ai之间之间 如何实现结点如何实现结点a ai-1i-1、x x和和a ai i之间逻辑关系的变化？之间逻辑关系的变化？pxsfirsta1ai-1anai算法描述：算法描述：s=new Node; s-data=x;s-next=p-next; p-next=s;21单链表的实现单链表的实现插入插入注意分析注意分析边界边界情况情况表头、表尾。表头、表尾。 firsta1anaipxs算法描述：算法描述：s=new Node; s-data=x;s-next=p-next; p-next=s;pxs由于单链表带头结点，由于单链表带
15、头结点，表头、表中、表尾三种表头、表中、表尾三种情况的操作语句一致。情况的操作语句一致。 22单链表的实现单链表的实现插入插入算法描述算法描述伪代码伪代码 1. 1. 工作指针工作指针p p初始化；累加器初始化；累加器j j初始化；初始化； 2. 2. 查找第查找第i-1i-1个结点并使工作指针个结点并使工作指针p p指向该结点；指向该结点； 3. 3. 若若查查找找不不成成功功，说说明明插插入入位位置置不不合合理理，抛抛出出插插入位置异常；否则，入位置异常；否则， 3.1 3.1 生成一个元素值为生成一个元素值为x x的新结点的新结点s s； 3.2 3.2 将新结点将新结点s s插入到结点
16、插入到结点p p之后；之后；23单链表的实现单链表的实现插入插入 template void LinkList:Insert( (int i, T x) ) p=first ; j=0; while ( (p & j-next; j+; 算法描述算法描述C+C+描述描述 if (!p) throw 位置位置; else s=new Node; s-data=x; s-next=p-next; p-next=s; ，基本语句？时间复杂度？基本语句？时间复杂度？算法中让算法中让p指向第指向第i个结点可以吗？个结点可以吗？24单链表的实现单链表的实现插入插入 template void LinkLi
17、st:Insert( (int i, T x) ) if(i=1)/处理在表头插入的特殊情况处理在表头插入的特殊情况 s=new Node； s-data=x; s-next=first; firs=s; 不带头结点单链表的插入算法不带头结点单链表的插入算法， else 与带头结点的单与带头结点的单链表插入操作相同链表插入操作相同 25单链表的实现单链表的实现删除删除操操作作接接口口T T Delete(intDelete(int i):i):将将单单链链表表的的第第i i个个结结点点删删去去并返回被删元素值并返回被删元素值; ; p如何实现结点如何实现结点a ai-1i-1和和a ai i之
18、间逻辑关系的变化？之间逻辑关系的变化？firsta1ai-1ai+1ai算法描述：算法描述：q=p-next; x=q-data;p-next=q-next; delete q;q26单链表的实现单链表的实现删除删除算法描述：算法描述：q=p-next; x=q-data;p-next=q-next; delete q;注意分析注意分析边界边界情况情况表头、表尾。表头、表尾。 pqpq表尾的特殊情况：表尾的特殊情况：虽然被删结点不存在，虽然被删结点不存在，但其前驱结点却存在。但其前驱结点却存在。 p-next=NULLfirsta1ana227单链表的实现单链表的实现删除删除算法描述算法描述伪
19、代码伪代码 1.1.工作指针工作指针p p初始化；累加器初始化；累加器j j清零；清零； 2. 2. 查找第查找第i-1i-1个结点并使工作指针个结点并使工作指针p p指向该结点；指向该结点； 3. 3. 若若p p不存在或不存在或p p不存在后继结点，则抛出位置异常；不存在后继结点，则抛出位置异常； 否则，否则， 3.1 3.1 暂存被删结点和被删元素值；暂存被删结点和被删元素值； 3.2 3.2 摘链，将结点摘链，将结点p p的后继结点从链表上摘下；的后继结点从链表上摘下； 3.3 3.3 释放被删结点；释放被删结点； 3.4 3.4 返回被删元素值；返回被删元素值； 28单链表的实现单链
20、表的实现删除删除template T LinkList:Delete(int i) p=first ; j=0; while (p & jnext; j+; 算法描述算法描述C+C+描述描述 if (!p | | !p-next) throw “位置位置”; else q=p-next; x=q-data; p-next=q-next; delete q; return x; 基本语句？时间复杂度？基本语句？时间复杂度？29小结：小结：在单链表上实现插入和删除操作，无须移动在单链表上实现插入和删除操作，无须移动元素，在将工作指针指向合适的位置后，仅元素，在将工作指针指向合适的位置后，仅需要修改
21、结点之间链接关系的指针。需要修改结点之间链接关系的指针。30单链表的实现单链表的实现构造函数构造函数操操作作接接口口LinkList(T a , int n)：生生成成一一个个具具有有n n个个结结点点的单链表，其数据元素为数组的单链表，其数据元素为数组anan 的各数组元素的各数组元素头插法：头插法：将待插入结点插在头结点的后面将待插入结点插在头结点的后面 。算法描述：算法描述：first=new Node; first-next=NULL; 数组数组a3512243342初始化初始化first31单链表的实现单链表的实现构造函数构造函数头插法：头插法：将待插入结点插在头结点的后面将待插入结
22、点插在头结点的后面 。数组数组a3512243342算法描述：算法描述：s=new Node; s-data=a0;s-next=first-next;first-next=s; 插入第一个元素结点插入第一个元素结点first35s操操作作接接口口LinkList(T a , int n)：生生成成一一个个具具有有n n个个结结点点的单链表，其数据元素为数组的单链表，其数据元素为数组anan 的各数组元素的各数组元素32单链表的实现单链表的实现构造函数构造函数头插法：头插法：将待插入结点插在头结点的后面将待插入结点插在头结点的后面 。操操作作接接口口LinkList(T a , int n)：
23、生生成成一一个个具具有有n n个个结结点点的单链表，其数据元素为数组的单链表，其数据元素为数组anan 的各数组元素的各数组元素数组数组a3512243342算法描述：算法描述：s=new Node; s-data=a1;s-next=first-next;first-next=s; 依次插入每一个结点依次插入每一个结点12sfirst3533单链表的实现单链表的实现构造函数构造函数template LinkList: LinkList(T a , int n) first=new Node; first-next=NULL; /初始化一个空链表初始化一个空链表 for (i=0; in; i
24、+) s=new Node; s-data=ai; /建立一个结点建立一个结点 s-next=first-next; first-next=s; /插入到头结点之后插入到头结点之后 算法描述：算法描述：34单链表的实现单链表的实现构造函数构造函数尾插法：尾插法：将待插入结点插在终端结点的后面。将待插入结点插在终端结点的后面。 算法描述：算法描述：first=new Node; rear=first;数组数组a3512243342初始化初始化firstrear操操作作接接口口LinkList(T a , int n)：生生成成一一个个具具有有n n个个结结点点的单链表，其数据元素为数组的单链表，
25、其数据元素为数组anan 的各数组元素的各数组元素35单链表的实现单链表的实现构造函数构造函数尾插法：尾插法：将待插入结点插在终端结点的后面。将待插入结点插在终端结点的后面。 操操作作接接口口LinkList(T a , int n)：生生成成一一个个具具有有n n个个结结点点的单链表，其数据元素为数组的单链表，其数据元素为数组anan 的各数组元素的各数组元素算法描述：算法描述：s=new Node; s-data=a0;rear-next=s;rear=s;数组数组a3512243342插入第一个元素结点插入第一个元素结点firstrear35srear36单链表的实现单链表的实现构造函数
26、构造函数尾插法：尾插法：将待插入结点插在终端结点的后面。将待插入结点插在终端结点的后面。 操操作作接接口口LinkList(T a , int n)：生生成成一一个个具具有有n n个个结结点点的单链表，其数据元素为数组的单链表，其数据元素为数组anan 的各数组元素的各数组元素数组数组a3512243342算法描述：算法描述：s=new Node; s-data=a1;rear-next=s;rear=s;依次插入每一个结点依次插入每一个结点firstrear35rear12srear37单链表的实现单链表的实现构造函数构造函数尾插法：尾插法：将待插入结点插在终端结点的后面。将待插入结点插在终
27、端结点的后面。 操操作作接接口口LinkList(T a , int n)：生生成成一一个个具具有有n n个个结结点点的单链表，其数据元素为数组的单链表，其数据元素为数组anan 的各数组元素的各数组元素数组数组a3512243342算法描述：算法描述：rear-next=NULL;最后一个结点插入后最后一个结点插入后firstrear35rear42srear38单链表的实现单链表的实现构造函数构造函数算法描述：算法描述：template LinkList: LinkList( (T a , int n) ) first=new Node ; rear=first; for ( (i=0;
28、in; i+) ) s=new Node ; s-data=ai; rear-next=s; rear=s; rear-next=NULL; 39单链表的实现单链表的实现析构函数析构函数析构函数将单链表中所有结点的存储空间释放。析构函数将单链表中所有结点的存储空间释放。 操作接口操作接口LinkList( )firsta1a2anaipq算法描述：算法描述：q=p; p=p-next;Delete q;p注意：保证链表未处理的部分不断开注意：保证链表未处理的部分不断开 40单链表的实现单链表的实现析构函数析构函数算法描述算法描述-1：template LinkList: LinkList( )( ) p=first; while ( (p) ) /释放放单链表的每一个表的每一个结点的存点的存储空空间 q=p; /暂存被存被释放放结点点 p=p-next; /使使单链表不断开表不断开 delete q; 41单链表的实现单链表的实现析构函数析构函数算法描述算法描述-2：template LinkList: LinkList() while (first) p=first; q=first-next; delete q; first=q; 思考：不带头结思考：不带头结点的单链表的析点的单链表的析构？构？42
