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