线性表的链式存储.ppt

《线性表的链式存储.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第三章线性表的链式存储主讲人：张雄线性表定义：线性表是一个线性结构，它是一个含有n≥0个结点的有限序列，对于其中的结点，有且仅有一个开始结点没有前驱但有一个后继结点，有且仅有一个终端结点没有后继但有一个前驱结点，其它的结点都有且仅有一个前驱和一个后继结点。一般地，一个线性表可以表示成一个线性序列：k1,k2,…,kn，其中k1是开始结点，kn是终端结点。线性表在计算机中的存储基本上市采取顺序存储和链式存储两种方式。2.1线性表的定义及其运算线性表举例:(A,B,C,...,Z)表中数据元素为单个字母字

2、符(400,420,500,...,600,650)表中数据元素为整数(stu1,stu2,...,stu100)数据元素类型为下列所示的结构类型：structstu{intnum;//学生学号char*name;//学生姓名intc;//C语言成绩...;}链式存储链式存储结构的特点用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的）结点结构数据域指针域链表中结点的逻辑次序和物理次序不一定相同，为了能够正确的表现结点之间的逻辑关系，在存储每个结点的同时，还必须存储指

3、示其后继结点的地址（或位置）信息（称为指针（pointer）或链（link））顺序存储结构与链表存储结构比较1.存储空间的比较顺序表的存储空间利用率为100%。在链表中的每个结点，除了数据域外，还要额外设置指针域，它的的存储存储空间利用率只为50%。由此可见，当线性表的长度变化不大，易于事先确定其大小时，宜采用顺序表作为存储结构。2.运行时间的比较顺序表是一种随机存取结构，可以在O(1)时间内直接地存取表中任一结点，所以当很少做插入和删除、仅做查找操作时时，宜采用顺序表做存储结构。对于插入和删除操作，

4、在链表中只需要修改指针不必移动数据元素。而在顺序表中进行时，平均要移动表中近一半的结点。因此，对于频繁进行插入和删除的线性表来说，宜采用链表做存储结构。3.应用语言的比较静态链表在存储分配上有不足之处，但它仍然具有插入和删除方便的特点。即使对于具有指针类型的语言，当线性表的长度不变，仅需改变结点之间的相对关系时，静态链表比动态链表可能更方便。链式存储单链表带头结点的单链表循环单链表双链表栈和队列的链式存储实现2.3线性表的链式存储结构1.单链表与指针术语表示每个数据元素的两部分信息组合在一起被称为结点

5、；其中表示数据元素内容的部分被称为数据域（data）；表示直接后继元素存储地址的部分被称为指针或指针域（next）。单链表的简化形式如图2.3所示：图2.3单链表结构示意图单链表单链表是线性表链式存储的一种形式，其中的节点一般含有两个域，一个存放数据信息的info,另一个是指向该结点的后继结点存放地址的指针next域。空单链表：head——>^非空单链表：Head……^单链表的实现链表实现的头文件：typedefintdatatype;typedefstructlink_node{datatypein

6、fo;structlink_node*next;}node;例1删除单链表：删除实际上就是要把第i个位置上的元素从链表中删除，例如下图为把第i个元素从链表中删除：Pi-1Xtempi+1i由于删除的是第i个位置上的元素，因此i的取值范围是1到表长，具体做法：先用p指针找到第I个元素的前驱，然后用指针temp事先保存好p的指针域，接着让p的指针域指向第i+1个结点。最后释放temp指向的空间，这样就完成了删除的操作。带头结点链表的删除代码：intListDelete(LinkListL,inti){in

7、tj=1;linklistp=L,temp;for(;p->next&&jnext,j++);if(i<1

8、

9、!p->next)returnERROR;temp=p->next;p->next=temp->next;Free(temp);returnOK}例2单链表的插入：插入实际上就是要把新元素插入到第i个元素之前，下图为把元素s插入到第i个元素结点之前。SPi-121i由于s是插入到第i个位置之前的，因此i的取值范围是1到表长+1.具体做法：先用指针p找到第i-1个结点的位置，

10、然后修改S的指针域，让其指向第i个结点，接着再去修改p的指针域让其指向S，这样就完成了插入的操作了带头结点的插入代码：intListLinsert(LinkListL,intI,ElemTypevalue){intj=1;linklistp=L,s;for(;p&&jnext,j++);if(i<1

11、

12、p==NULL)returnERROR;S=(linklist)malloc(sizeof(LNode));S->next=p->next