第3课-线性链表

本课内容线性表的链式存储结构——线性链表教学重点：链表的建立与删除操作学习要求1.理解链式存储结构的特点2.掌握线性链表的基本操作：链表的建立链表的插入链表的删除链表的合并

复习：

线性表顺序存储结构的特点：

用物理位置上的邻接关系来表示结点间的逻辑关系，可以随机存取表中的任一结点；

插入和删除操作时需移动大量的结点;

因此适合建立后较少进行更改、主要进行查询操作的应用场合。

为避免大量的结点移动操作，介绍线性表的另一种存储方式:链式存储结构，简称链表(LinkedList)。

2.3线性表的链式存储和运算实现

1.线性表的链式存储结构用一组任意的存储单元（即可以连续也可以是不连续的）存储线性表的数据元素。对线性表中的每一个数据元素，都需用两部分来存储：一部分用于存放数据元素值，称为数据域；另一部分用于存放指示该结点直接前驱或直接后继结点的地址（指针），称为指针域。把对应一个数据元素的存储块称为“结点”。

链式存储方式可用于表示线性结构，也可用于表示非线性结构。2.3.1线性链表

1.链表的结点结构每个元素在存储时对应一个“结点”，结点的结构如下所示：数据域data存储数据元素的信息，指针域next存储该元素的直接后继的地址。这种只有一个指针的结点形成的链表称为单向链表，也称为“线性链表”。结点数据类型的描述如下：typedef

struct

Lnode{

ElemTypedata;

/*结点数据值*/

struct

LNode*next;

/*下一个结点的地址*/}LNode,*LinkList;其中，LNode为描述以上结构的类型，而LinkList为指向LNode数据的指针类型;

图2-7线性链表结构示意图

设有一个线性表（A,B,C,D,E）存储空间具有10个存储结点，该线性表在存储空间中的存储情况如图2-7(a)所示。头指针headABCDE47291∧(b)线性表的逻辑状态

2.链式结构特点每个结点的存储地址存放在直接前驱的指针域中。所以要访问链表中的某个数据元素，必须由头指针head得到第一个结点（数据A）的地址，由该结点的指针域得到第二个结点（数据B）的地址，……链表这种顺着指针链依次访问数据元素的特点，表明链表是一种顺序存储结构，只能顺序操作链表中元素。不能像顺序表（数组）那样可以按下标随机存取。

在链表存储结构中，不要求存储空间的连续性，数据元素之间的逻辑关系由指针来确定。由于链式存储的灵活性，这种存储方式既可用于表示线性结构，也可以用来表示非线性结构。2.3.2单向链表的操作

单链表分为带头结点和不带头结点两种类型。为了简化插入、删除操作，采用带头结点的表示方式。（空间换时间策略）如图2-8是带头结点的链表示意图图2-8（a）为带头结点的空链表

(b)为带头结点的长度为3的单链表

1．初始化链表initlist(L)的实现空链表中没有元素结点,但应有一个头结点，其指针域为空。StatusInitList(Lnode**L){*L=(LNode*)malloc(sizeof(LNode));/*申请一个结点的存储空间*/if(*L!=0){(*L)->next=NULL;returnok;}elsereturn(error);}该函数调用方法：

Lnode*head;

InitList(&head);

主函数需传递头指针变量的地址给InitList()函数。2.3.2单向链表的操作（1）2．求线性表长度Getlen(L)的实现设计思路：设置一个初值为0的计数器变量和一个跟踪链表结点的指针p。初始时p指向链表中的第一个结点，然后顺着next域依次指向每个结点，并使计数器加1。当p为0时，结束该过程。

int

Getlen(LinkListL){intnum=0;/*计数*/

LNode*p=L->next;/*指向第一个元素结点*/while(p!=NULL){num++;p=p->next;}return(num);}2.3.2单向链表的操作（2）3．按序号取元素Getelem(L,i)算法——p29算法2.8的C函数实现

StatusGetelem(LinkList

L,int

i,Elemtype*e){LNode*p=L->next;/*P指向第一个元素结点*/

intpos=1;/*结点序号,也是计数器*/while(p&&pos<i){p=p->next;pos++;}if(!p||pos>i)

returnerror;/*参数非法,第i个元素不存在*/*e=p->data;/*返回第i个元素的数据域值*/returnok;}

注意：由于C语言中参数传递采用“传值”方法，需要将e定义为指针变量才能返回第i个元素的值.2.3.2单向链表的操作（3）

单链表结点的插入是利用修改结点指针域的值，使其指向新的链接位置来完成的插入操作，而无需移动任何元素。假定在链表中值为ai的结点之前插入一个新结点，要完成这种插入必须首先找到所插位置的前一个结点，再进行插入。假设指针p指向待插位置的前驱结点，指针new指向新结点，则完成该操作的过程如图2-9所示。

4．链表的插入算法Insertelem(L,i,x)的实现2.3.2单向链表的操作_插入插入结点过程示意图,注意修改指针的次序(1)令指针p指向要插入结点的前驱(循环语句）(2)生成一个新的空白结点

new=(lnode*)malloc(sizeof(lnode));(3)填充新结点的数据域和指针域

new->data=e;

new->next=p->next;(4)令前驱的指针域next指向新结点

p->next=new;head

p

newead0b算法2.9的C函数实现/*在头指针为L的链表第i个位置前插入元素e*/statusInsertElem(LinkList

L,inti,ElemTypee){LNode*p=L,*s;

intpos=0;/*找待插入结点的前驱(第i-1个结点)，令变量p指向它*/while(p&&pos<i-1){p=p->next;pos++;}if(p==null||pos>i-1)returnerror;/*插入位置i非法*//*生成新结点,并填充数据*/s=(LNode*)malloc(sizeof(LNode));s->data=e;s->next=p->next;/*修改前驱结点的next域,指向新结点*/p->next=s;returnok;}

其中LinkList本身就是指针类型，等价于Lnode*5．链表的删除运算delelem(L,I,e)的实现要删除链表中第i个结点，首先在单链表中找到删除结点的前一个结点，并用指针p指向它，指针q指向要删除的结点。将p的指针域修改为待删除结点q的后继结点的地址,并释放结点q所占存储空间，如图2-10所示。

要删除结点q:首先由头指针开始顺序找到其前驱P;删除结点q：P->next=q->next;

Free(q);图2-10线性链表的删除过程示意图

head

p

qaj-1a1aj+1aj

5．链表的删除运算_算法2.10的C函数实现/*删除链表L的第i个结点并用变量e返回其值*/StatusDeleteElem(LinkList

L,inti,ElemType*e){LNode*p=L,*q;/*P指向头结点*/

intpos=0;/*结点序号,也是计数器*/while(p->next&&pos<i-1)/*找第i-1个结点*/{p=p->next;pos++;}if(p->next==0||pos>i-1)

returnerror;/*参数非法,第i个元素不存在*/q=p->next;/*q指向待删除的结点*/*e=q->data;/*返回第i个元素的数据域值*/p->next=q->next;/*删除结点q*/

free(q);/*释放结点所占空间*/returnok;}在插入和删除算法中，都是先查询确定操作位置，然后再进行插入和删除操作。所以其时间复杂度均为O(n)。另外在算法中实行插入和删除操作时没有移动元素的位置，只是修改了指针的指向，所以采用链表存储方式时插入、删除操作的效率要比顺序存储方式的高。算法分析6．链表的创建——算法2.11的C函数实现/*以数组x中的n个数据创建带头结点的链表,成功返回头指针*/LinkList

CreateList(int

n,ElemTypex[]){inti;

LNode*p,*head;head=(LNode*)malloc(sizeof(LNode));/*生成头结点*/if(!head)return0;

head->next=0;

for(i=n-1;i>=0;i--){p=(*LNode)malloc(sizeof(LNode));/*创建新结点*/if(!p)return0;p->data=x[i];

p->