(3)--第2章 线性表-单链表（完整版）.ppt

《(3)--第2章 线性表-单链表（完整版）.ppt》由会员分享，可在线阅读，更多相关《(3)--第2章 线性表-单链表（完整版）.ppt（41页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-线性表的链式表示及实现第2章 线性表1 1.掌握链表的定义、创建、查找、插入和删除掌握链表的定义、创建、查找、插入和删除 4.4.能够从时间和空间复杂度的角度能够从时间和空间复杂度的角度比较比较顺序顺序表和表和链表两种链表两种存储结构的不同特点及其适用场合存储结构的不同特点及其适用场合 教学目标结点结点在存储器中的位置是在存储器中的位置是任意任意的，的，即逻辑上相邻逻辑上相邻的数据元素在物理上不一定相邻的数据元素在物理上不一定相邻线性表的链式表示通过通过“链链”建立起数据元素之间的逻辑关系建立起数据元素之间的逻辑关系借助指示元素存储地址的借助指示元素存储地址的指针实现指针实现各结点由两个域组

2、成：各结点由两个域组成：数据域：数据域：存储元素数值数据存储元素数值数据指针域：指针域：存储直接后继结点的存储位置存储直接后继结点的存储位置a1heada2an单链表单链表链表的优缺点优点优点数据元素的个数可以自由扩充数据元素的个数可以自由扩充插入、删除等操作不必移动数据，只需修改链接指针，插入、删除等操作不必移动数据，只需修改链接指针，修改效率较高修改效率较高缺点缺点存储密度小存储密度小存取效率不高，访问时只能通过头指针进入链表，并通过存取效率不高，访问时只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余每个结点的指针域向后扫描其余结点结点（顺藤摸瓜）（顺藤摸瓜），所以所以寻找第一个

3、结点和最后一个结点所花费的时间寻找第一个结点和最后一个结点所花费的时间不等不等这种存取元素的方法被称为这种存取元素的方法被称为顺序存取法顺序存取法单链表的两种形式单链表的两种形式ZHAOQIANLISUNZHOUWUZHENG/WANGHZHAOQIANLISUNZHOUWUZHENG/WANGH区别：区别：无头结点无头结点有头结点有头结点头头指针、头结点和首元结点指针、头结点和首元结点 头指针头指针 头结点头结点首元结点首元结点a1heada2infoan头指针头指针是指向链表中第一个结点的指针是指向链表中第一个结点的指针首元结点首元结点是指链表中存储第一个数据元素是指链表中存储第一个数据元

4、素a a1 1的结点的结点头结点头结点是在链表的首元结点之前附设的一个结点；数是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息据域内只放空表标志和表长等信息讨论讨论1.1.如何表示如何表示空表空表？有头结点时，有头结点时，当头结点的指针域为空当头结点的指针域为空时表示空表时表示空表非空表非空表 空表空表0ana0headhead表头表头结点结点第一个第一个结点结点不带头结点的单链表不带头结点的单链表L L为空的条件是（）为空的条件是（）L=NULL;L=NULL;L-next=NULL;L-next=NULL;A AB B提交提交单选题单选题2 2分分带头带头结点的单链表

5、结点的单链表L L为空的条件是（）为空的条件是（）L=NULL;L=NULL;L-next=NULL;L-next=NULL;A AB B提交提交单选题单选题2 2分分讨论讨论2 2.在链表中设置在链表中设置头结点头结点有什么好处？有什么好处？便于便于首元结点首元结点的处理的处理首元结点的地址保存在头结点的指针域中首元结点的地址保存在头结点的指针域中,所以所以在链表的第一个位置上的操作和其它位置一致，无须在链表的第一个位置上的操作和其它位置一致，无须进行特殊处理进行特殊处理;便于便于空表和非空表空表和非空表的统一处理的统一处理无论链表是否为空，头指针都是指向头结点的非无论链表是否为空，头指针都

6、是指向头结点的非空指针，因此空表和非空表的处理也就统一了。空指针，因此空表和非空表的处理也就统一了。讨论讨论3.3.头结点的头结点的数据域数据域内装的是什么？内装的是什么？头结点的头结点的数据域数据域可以为空，也可存放线性表可以为空，也可存放线性表长度长度等附加信息，但此结点不能计入链表长度值。等附加信息，但此结点不能计入链表长度值。头结点的数据域头结点的数据域H H单链表的定义和实现非空表非空表空表空表单链表是由表头唯一确定，因此单链表可单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名以用头指针的名字来命名若头指针名是若头指针名是L，则把链表称为表，则把链表称为表L 单链表的存储结

7、构定义typedef struct LNodetypedef struct LNode ElemType data;ElemType data;/数据域数据域 struct LNode *next;struct LNode *next;/指针域指针域LNode,*LinkList;LNode,*LinkList;/*LinkList/*LinkList为为LnodeLnode类型的指针类型的指针LNode*pLinkListpLNode*p注意区分指注意区分指针变量和量和结点点变量两个不同的概念量两个不同的概念指指针变量量p：表示：表示结点地址点地址结点点变量量*p：表示一个：表示一个结点点若

8、若p-data=ai,则则p-next-data=ai+1对于对于链表，常用的三条语句链表，常用的三条语句如下：如下：p=L-next;/p指向首元结点指向首元结点while(p!=NULL)/p未到表尾未到表尾p=p-next;/p指向下一个结点指向下一个结点另外，另外，指针保留技术指针保留技术：q=p;p=p-next;单链表基本操作的实现n初始化初始化n求表长求表长n取值取值n查找查找n插入插入n删除删除1.1.初始化初始化(构造一个空表构造一个空表)【算法步骤算法步骤】（1）生成新结点作头结点，用头指针）生成新结点作头结点，用头指针L指向头结点。指向头结点。（2）头结点的指针域置空。）

9、头结点的指针域置空。【算法描述算法描述】StatusInitList_L(LinkList&L)L=newLNode;L-next=NULL;returnOK;pLa1a2.pi0 1p2p=NULLan2.2.求求表表长长（“数数”结点结点：）【算法算法步骤步骤】（1）指针）指针p初始化指向首元结点，计数器初始化指向首元结点，计数器i初始化为初始化为0；（2）只要）只要p不为空，重复执行：不为空，重复执行：i增增1，p后移后移n-1n【算法描述算法描述】intListLength_L(LinkListL)/返回返回L L中数据元素中数据元素个数（表长）个数（表长）LinkListp;p=L-

10、next;/p/p指向第一个结点指向第一个结点i=0;/计数器从计数器从0 0开始开始while(p)/遍历单链表遍历单链表,统计结点数统计结点数i+;p=p-next;returni;思考：顺序表里如何找到第思考：顺序表里如何找到第i i个元素？个元素？链表链表的查找：要从链表的头指针出发，的查找：要从链表的头指针出发，顺着链域顺着链域nextnext逐个结点往下搜索，直至逐个结点往下搜索，直至搜索到第搜索到第i i个结点为止。因此，链表不是个结点为止。因此，链表不是随机存取结构随机存取结构3 3.取值取值（根据位置（根据位置i i获取相应位置数据元素的内容）获取相应位置数据元素的内容）20

11、L211830754256 pppj1 2 3pp1i=3i=156p7例：分别取出表中例：分别取出表中i=3和和i=15的元素的元素从第从第1 1个结点（个结点（L-nextL-next）顺链扫描，用指针）顺链扫描，用指针p p指向当前扫描指向当前扫描到的结点，到的结点，p p初值指向首元。初值指向首元。j j做计数器，累计当前扫描过的结点数，做计数器，累计当前扫描过的结点数，j j初值为初值为1 1。当当p p不为空并且不为空并且j!=ij!=i时，重复执行：计数器时，重复执行：计数器j j加加1 1，p p后移。后移。扫描结束后，当扫描结束后，当j j=i i时，时，p p所指的结点就是

12、要找的第所指的结点就是要找的第i i个个结点，否则，不存在结点，否则，不存在【算法步骤算法步骤】【算法描述算法描述】/获取线性表获取线性表L L中中的第个的第个数据元素的内容数据元素的内容LinkListGetElem_L(LinkListL,int)/初始化，初始化，p初值指向首元，初值指向首元，j初值为初值为1/向后扫描，直到向后扫描，直到p指向第指向第i个元素或个元素或p为空为空/找到第找到第i个结点个结点/第第i个元素不存在个元素不存在p=p-next;+j;while(p&jnext;j=1;if(j=i)returnp;elsereturnNULL;用指针用指针p p指向当前扫描到

13、的结点，指向当前扫描到的结点，p p初值指向首元。初值指向首元。当当p p不不为为空空并并且且p p指指向向结结点点不不等等于于所所查查找找元元素素e e，重重复复执执行行：p p后移；后移；如如果果找找到到其其值值和和e e相相等等的的元元素素，则则返返回回当当前前地地址址，否否则则返返回回“NULLNULL”（指针当前值）（指针当前值）。L2118307556px=30pp找到找到，返回地址（指针当前值），返回地址（指针当前值）x=51p未找到，返回NULL（指针当前值）4.4.查找查找（根据指定数据获取数据所在的位置）（根据指定数据获取数据所在的位置）【算法步骤算法步骤】ppLNode*

14、LocateELem_L(LinkListL，Elemtypee)/返回返回L中值为中值为e的数据元素的的数据元素的地址地址，查找失败返回，查找失败返回NULLp=L-next;/p初始化指向首元初始化指向首元while(p&p-data!=e)/未找到未找到p后移后移p=p-next;returnp;/找到找到p指向指向e位置，找不到位置，找不到p为为NULL【算法描述算法描述】intLocateELem_L(LinkListL，Elemtypee)/返回返回L中值为中值为e的数据元素的的数据元素的位置序号位置序号，查找失败返回，查找失败返回0p=L-next;j=1;while(p&p-d

15、ata!=e)p=p-next;j+;if(p)returnj;elsereturn0;【算法描述算法描述】将值为将值为x x的新结点插入到表的第的新结点插入到表的第i i（1 1in+1in+1）个）个结点的位结点的位置上，即插入到置上，即插入到a ai-1i-1与与a ai i之间之间5.5.插入插入（在第（在第i-1i-1个结点后插入值为个结点后插入值为X X的新结点）的新结点）【算法步骤算法步骤】（1 1）找到）找到a ai-1i-1存储位置存储位置p p（2 2）生成一个新结点）生成一个新结点*s s（3 3）将新结点）将新结点*s s的数据域置为的数据域置为x x（4 4）新结点）

16、新结点*s s的指针域指向结点的指针域指向结点a ai i（5 5）令结点）令结点*p p的指针域指向新结点的指针域指向新结点*s ss=(LinkList)malloc(sizeof(LNode);/生成新结点s-data=e;s-next=p-next;/修改指针p-next=s;/插入eai-1aiai-1sp思考思考：修改指针的两个步骤能：修改指针的两个步骤能互换么互换么？StatusListInsert_L(LinkList&L,inti,ElemTypee)/在在L L中第中第i i个元素之前插入数据元素个元素之前插入数据元素e e p=L;j=0;while(p&jnext;+j

17、;/寻找第寻找第i1个结点个结点if(!p|ji1)returnERROR;/i大于表长大于表长+1或者小于或者小于1s=newLNode;/生成新结点生成新结点ss-data=e;/将结点将结点s的数据域置为的数据域置为es-next=p-next;/将结点将结点s插入插入L中中p-next=s;returnOK;【算法描述算法描述】p-next=p-next-next?ai-1ai-1aiaiai+1ai+1pq删除前删除前删除后删除后5.5.删除删除（删除第（删除第 i i 个结点）个结点）【算法步骤算法步骤】（1 1）找到找到a ai-1i-1存储位置存储位置p p（2 2）临时保存结

18、点临时保存结点a ai i的地址在的地址在q q中，以备释放中，以备释放（3 3）令令p-nextp-next指向指向a ai i的直接后继结点的直接后继结点（4 4）将将a ai i的值保留在的值保留在e e中中（5 5）释放释放a ai i的空间的空间StatusListDelete_L(LinkList&L,inti,ElemType&e)/将线性表将线性表L L中第中第i i个数据元素删除个数据元素删除p=L;j=0;while(p-next&jnext;+j;if(!(p-next)|ji-1)returnERROR;/删除位置不合理删除位置不合理q=p-next;/临时保存被删结点

19、的地址以备释放临时保存被删结点的地址以备释放p-next=q-next;/改变删除结点前驱结点的指针域改变删除结点前驱结点的指针域e=q-data;/保存删除结点的数据域保存删除结点的数据域deleteq;/释放删除结点的空间释放删除结点的空间 return OK;【算法描述算法描述】1.查找查找:因线性链表只能顺序存取，即在查找时要因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为从头指针找起，查找的时间复杂度为O(n)。2.插入和删除插入和删除:因线性链表不需要移动元素，只要因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为修改指针，一般情况下时间复杂度为O(

20、1)。但是，如果要在单链表中进行前插或删除操作，但是，如果要在单链表中进行前插或删除操作，由于要从头查找前驱结点，所耗时间复杂度为由于要从头查找前驱结点，所耗时间复杂度为O(n)。链表的运算时间效率分析链表的运算时间效率分析链式存储的优点是插入、删除元素时不会引起后续链式存储的优点是插入、删除元素时不会引起后续元素的移动，缺点是只能顺序访问各元素。元素的移动，缺点是只能顺序访问各元素。对对错错A AB B提交提交单选题单选题2 2分分链表不具有的特点是链表不具有的特点是()()。可随机访问任一个元素可随机访问任一个元素插入删除不需要移动元素插入删除不需要移动元素不必事先估计存储空间不必事先估计

21、存储空间所需空间与线性表长度成正比所需空间与线性表长度成正比A AB BC CDD提交提交单选题单选题2 2分分下面的叙述正确的是下面的叙述正确的是()()。线性表在链式存储时，查找第线性表在链式存储时，查找第i i个元素的时个元素的时间同间同i i的值成反比的值成反比线性表在链式存储时，查找第线性表在链式存储时，查找第i i个元素的时个元素的时间同间同i i的值无关的值无关线性表在顺序存储时，查找第线性表在顺序存储时，查找第i i个元素的时个元素的时间同间同i i的值成正比的值成正比线性表在顺序存储时，查找第线性表在顺序存储时，查找第i i个元素的时个元素的时间同间同i i的值无关的值无关A

22、 AB BC CDD提交提交单选题单选题2 2分分顺序表和链表的比较比较项目顺序表链表空间存储空间预先分配，会导致空间闲置或溢出现象动态分配，不会出现存储空间闲置或溢出现象存储密度不用为表示结点间的逻辑关系而增加额外的存储开销，存储密度等于1需要借助指针来体现元素间的逻辑关系，存储密度小于1时间存取元素随机存取，按位置访问元素的时间复杂度为O(1)顺序存取，按位置访问元素时间复杂度为O(n)插入、删除平均移动约表中一半元素，时间复杂度为O(n)不需移动元素，确定插入、删除位置后，时间复杂度为O(1)适用情况 表长变化不大，且能事先确定变化的范围 很少进行插入或删除操作，经常按元素位置序号访问数

23、据元素 长度变化较大 频繁进行插入或删除操作n从一个空表开始，重复读入数据：从一个空表开始，重复读入数据：u生成新结点生成新结点u将读入数据存放到新结点的数据域中将读入数据存放到新结点的数据域中u将该新结点插入到链表的前端将该新结点插入到链表的前端单链表的建立（前插法）单链表的建立（前插法）p-data=anp-data=an-1L-next=pp-next=L-next单链表的建立（前插法）单链表的建立（前插法）voidCreateList_F(LinkList&L,intn)L=newLNode;L-next=NULL;/先建立一个带头结点的单链表先建立一个带头结点的单链表for(i=n;

24、i0;-i)p=newLNode;/生成新结点生成新结点cinp-data;/输入元素值输入元素值p-next=L-next;L-next=p;/插入到表头插入到表头【算法描述算法描述】n从一个空表从一个空表L开始，将新结点逐个插入到链表的尾部，尾指开始，将新结点逐个插入到链表的尾部，尾指针针r指向链表的尾结点。指向链表的尾结点。n初始时，初始时，r同同L均指向头结点。每读入一个数据元素则申请一均指向头结点。每读入一个数据元素则申请一个新结点，将新结点插入到尾结点后，个新结点，将新结点插入到尾结点后，r指向新结点。指向新结点。单链表的建立（尾插法）单链表的建立（尾插法）voidCreateList_L(LinkList&L,intn)/正位序输入正位序输入n个元素的值，建立带表头结点的单链表个元素的值，建立带表头结点的单链表LL=newLNode;L-next=NULL;r=L;/尾指针尾指针r指向头结点指向头结点for(i=0;ip-data;/输入元素值输入元素值p-next=NULL;r-next=p;/插入到表尾插入到表尾r=p;/r指向新的尾结点指向新的尾结点【算法描述算法描述】