《数据结构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