第3课-线性链表

1、本课内容线性表的链式存储结构线性链表教学重点：链表的建立与删除操作1学习要求1.理解链式存储结构的特点2.掌握线性链表的基本操作： 链表的建立 链表的插入 链表的删除 2复习： 线性表顺序存储结构的特点： 用物理位置上的邻接关系来表示结点间的逻辑关系， 可以随机存取表中的任一结点； 插入和删除操作时需移动大量的结点(平均移动一半元素) 因此适合建立后较少进行更改、主要进行查询操作的应用场合。 为避免大量的结点移动操作，介绍线性表的另一种存储方式: 链式存储结构，简称链表(Linked List)。 32.3 线性表的链式存储和运算实现 1.线性表的链式存储结构 用一组任意的存储单元（即可以连续

2、也可以是不连续的）存储线性表的数据元素。对线性表中的每一个数据元素，都需用两部分来存储：一部分用于存放数据元素值，称为数据域；另一部分用于存放该结点直接前驱或直接后继结点的地址（指针），称为指针域。 把对应一个数据元素的存储块称为“结点”。 链式存储方式可用于表示线性结构，也可用于表示非线性结构。42.3.1 线性链表 1.链表的结点结构 每个元素在存储时对应一个“结点”，结点的结构如下所示： 数据域 data 存储数据元素的信息， 指针域 next 存储该元素的直接后继的地址。这种只有一个指针的结点形成的链表称为单向链表，也称为“线性链表”。5结点数据类型的 描述如下：typedef str

3、uct node DataType data; /*结点数据值*/ struct node *next; /*下一个结点的地址*/ LNode,*LinkList;其中，LNode为描述以上结构的类型名， LinkList为指向LNode数据的指针类型名; 6图 2-7 线性链表结构示意图 设有一个线性表（A,B,C,D,E）存储空间具有10个存储结点，该线性表在存储空间中的存储情况如图2-7(a)所示。 7 2. 链式结构特点 每个结点的存储地址存放在直接前驱的指针域中。 要访问链表中的某个数据元素，必须由头指针head得到第一个结点（数据A）的地址，由该结点的指针域得到第二个结点的地址，

4、这种顺着指针链依次访问数据元素的特点，表明链表是一种顺序访问的结构，只能顺序操作链表中元素。不能像顺序表（数组）那样可以按下标随机存取。 在链表存储结构中，不要求存储空间的连续性，数据元素之间的逻辑关系由指针来确定。 由于链式存储的灵活性，这种存储方式既可用于表示线性结构，也可以用来表示非线性结构。82.3.2 单向链表的操作实现 单链表分为带头结点和不带头结点两种类型。为了简化插入、删除操作，采用带头结点的表示方式。（空间换时间策略） 如图2-8是带头结点的链表示意图图2-8（a）为带头结点的空链表 (b)为带头结点的长度为3的单链表9 1初始化链表initlist(L)的实现 空链表中没有

5、元素结点,但应有一个头结点，其指针域为空。Status InitList(Linklist &L) / C+的语法，表示传址 L=(Linklist )malloc(sizeof(LNode); /*申请一个结点的存储空间*/ if (L!=0) L-next=NULL; return ok; else return (error); 该函数的调用方法： Linklist head; /声明指向链表头指针的变量 InitList(head); /调用初始化函数 主函数将指针变量head的地址传给 InitList()函数。（编译程序知道）2.3.2 单向链表的操作（1）10 1初始化链表ini

6、tlist(L)的实现 空链表中没有元素结点,但应有一个头结点，其指针域为空。 /创建空链表，成功返回头指针，否则返回0Linklist InitList() /*申请一个结点的存储空间*/ linklist L=(Linklist )malloc(sizeof(Lnode); if (L) L-next=0; return L; 该函数的调用方法： Linklist head=Initlist(); /声明指向链表头指针的变量 主函数需将指针变量head的地址传给 InitList()函数。（程序自己负责）2.3.2 单向链表的操作（1）112求线性表长度Getlen(L)的实现 线性表长度

7、=表中数据结点的个数 设计思路：设置一个初值为0的计数器变量和一个跟踪链表结点的指针p。初始时p指向链表中的第一个结点，然后顺着next域依次指向每个结点，并使计数器加1。当p为0时，结束该过程。 int Getlen(LinkList L) int num=0; /*计数*/ LinkList p=L-next; /*指向第一个元素结点*/ while (p!=NULL) num+; p=p-next; return(num); 2.3.2 单向链表的操作（2）122用for语句描述： 线性表长度=表中数据结点的个数 设计思路：设置一个初值为0的计数器变量和一个跟踪链表结点的指针p。初始时p

8、指向链表中的第一个结点，然后顺着next域依次指向每个结点，并使计数器加1。当p为0时，结束该过程。 int Getlen(LinkList L) int num=0; /*计数*/ LinkList p=L-next; /*指向第一个元素结点*/ for ( ;p!=NULL; num+) p=p-next; return(num); 13 单链表结点的插入是利用修改结点指针域next的值，使其指向新的链接位置来完成的插入操作，而无需移动任何元素。 假定在链表中值为ai的结点之前插入一个新结点，要完成这种插入必须首先找到所插位置的前一个结点，再进行插入。假设指针p指向待插位置的前驱结点，指针

9、new指向新结点，则完成该操作的过程如图2-9所示。 3链表的插入算法Insertelem(L,i,x)的实现2.3.2 单向链表的插入操作 (重点)14插入结点过程示意图, 注意修改指针的次序(1)令指针p指向要插入结点的前驱(循环语句）(2)生成一个新的空白结点 new=(lnode*)malloc(sizeof(lnode);(3)填充新结点的数据域和指针域 new-data=e; new-next=p-next;(4)令前驱的指针域next指向新结点 p-next=new; 15算法的C函数实现/*在头指针为L的链表第i个位置插入元素e*/status InsertElem(LinkL

10、ist L,int i, DataType e) LinkLis p=L, s; int pos=0; /*找待插入结点的前驱(第i-1个结点)，令变量p指向它*/ while (p & posnext; pos+; if (p=null| posi-1) return error; /*插入位置i非法*/ /*生成新结点,并填充数据*/ s=(LinkList)malloc(sizeof(LNode); s-data=e; s-next=p-next; /*修改前驱结点的next域,指向新结点*/ p-next=s; return ok; 164链表的删除运算delelem(L,I,e)的实

11、现 要删除链表中第i个结点，首先在单链表中找到删除结点的前趋结点，并用指针p指向它，指针q指向要删除的结点。 将p的指针域修改为待删除结点q的后继结点的地址,并释放结点q所占存储空间，如图2-10所示。 17要删除结点 q:1.首先由头指针开始顺序找到其前驱 P;2.从链表中删除结点q ：p-next=q-next;3.释放结点 q 所占空间：free(q);图2-10 线性链表的删除过程示意图 head p qaj-1a1aj+1aj18 5链表的删除运算_算法2.10的C函数实现/*删除链表L的第i个结点并用变量e返回其值*/Status DeleteElem(LinkList L,int

12、 i, ElemType *e) LinkList p=L, q; /* P指向头结点*/ int pos=0; /* 结点序号,也是计数器*/ while (p-next & posnext; pos+; if (p-next=0 |posi-1) return error; /*参数非法,第i个元素不存在*/ q=p-next; /*q指向待删除的结点*/ *e=q-data; /*返回第i个元素的数据域值*/ p-next=q-next; /*删除结点q*/ free(q); /*释放结点所占空间*/ return ok;19在插入和删除算法中，都是先查询确定操作位置，然后再进行插入和删

13、除操作。所以其时间复杂度均为O(n)。另外在算法中实行插入和删除操作时没有移动元素的位置，只是修改了指针的指向，所以采用链表存储方式时插入、删除操作的效率要比顺序存储方式的高。算法分析205链表的创建C函数实现/*以数组x中的n个数据创建带头结点的链表,成功返回头指针*/LinkList CreateList(int n,DataType x) int i; LNode *p,*head; head=(LNode *)malloc(sizeof(LNode); /*生成头结点*/ if (!head) return 0; head-next=0; for (i=n-1; i=0; i-) p=(* LNode)malloc(sizeof(LNode); /*创建新结点*/ if (!p) return 0; p-data=xi; p-next=head-next; /*插入到表头*/ head-next=p; return head; 该算法的特点是：每次将新生