计算机软件技术基础第3讲(第二章)ppt课件.ppt

《计算机软件技术基础第3讲(第二章)ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、信息科学与工程学院计算机软件技术基础二O一O年十月12.3线性链表及其运算2.3.1线性链表的基本概念线性表的顺序存储结构具有结构简单、运算方便的优点，尤其是小线性表或长度固定的线性表对于大的线性表，特别是元素变动频繁的大线性表不宜采用顺序存储结构，而应采用链式存储结构存储结点：数据结构中的每一个数据结点对应于一个存储单元，这种存储单元称为存储结点在链式存储方式中，要求每个结点有两部分组成：一部分数用于存放数据元素值，称为数据域一部分用于存放下一个数据元素的存储序号（存储结点的地址），即指向该节点的后件结点，称为指针域。22.3线性链表及其运算链式存储方式既可以用于表示线性结构，也可以

2、表示非线性结构。数据元素之间的逻辑关系由指针域来确定线性链表：线性表的链式存储结构称为线性链表为适应线性表的链式存储结构，计算机存储空间被划分为一个个小块，每一个小块占若干个字节，这些小块称为存储结点存储结点数据域指针域图2.18线性链表的存储空间图2.19线性链表的一个存储结点3structstudentdatanextaistructstudent{longnum;floatscore;sturctstudent*next};structstudent*head;2.3线性链表及其运算data2.3线性链表及其运算线性链表的逻辑结构：在线性链表中，用一个专门的指针HEAD指向线性链

3、表中第一个数据元素的结点线性链表中最后一个结点的指针域为空，用NULL或0表示图2.20线性链表的逻辑结构52.3线性链表及其运算线性链表的存储结构：线性链表（a1,a2,a3,a4,a5）,存储空间有10个存储结点（如2.21a）为了直观地表示该线性链表中各元素之间的前后件关系，用图（b)表示线性链表的逻辑状态图2.21线性链表例62.3线性链表及其运算在线性链表的存储结构中，各数据结点的存储序号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致各数据元素之间的前后件关系是由各结点的指针域来指示的指向线性表中的第一个结点的指针HEAD称为头指针当HEAD=NULL(或0)

4、时称为空表上述讨论的线性链表称为线性单链表。这种链表中，每一个结点只有一个指针域，由这个指针只能找到后件结点，不能找到前件结点线性双向链表：对线性链表中的每个结点设置两个指针，一个为左指针（Llink）,用于指向其前向结点；另一个为右指针（Rlink）,用于指向其后件结点，这样的线性链表称为双向链表72.3线性链表及其运算2.3.2线性链表的基本运算线性表的插入：指在链式存储结构下的线性表中插入一个元素基本思想：首先从可利用的栈中给该新元素分配一个新结点，以用于存储该元素的值，然后将存放新元素值的结点链接到线性链表中指定的位置假设可利用栈与线性链表如图2.26(a)所示，现在要在线性链

5、表中包含元素x的结点前插入一个新元素b，插入过程如下：8建立链表操作(从链尾到链头)head...④head=p;②p=malloc(sizeof(structnode));p->data=a[i];①for(i=0;inext=head;建立链表操作(从链头到链尾)...④p->next=q;②q=malloc(sizeof(structnode));q->data=a[i];①for(i=0;inext=NULL;⑤p=q;链表的插入操作......④p->next=q;②q=malloc(sizeof(structnode));q->d

6、ata=x;①if(p满足插入条件)③q->next=p->next;2.3线性链表及其运算2.3.2线性链表的基本运算线性表的删除：指在链式存储结构下的线性表中删除包含指定元素的结点基本思想：首先要在线性链表中找到这个结点，然后将要删除结点放回到可利用栈假设可利用栈与线性链表如图2.27(a)所示，现在要在线性链表中删除包含元素x的结点，删除过程如下：12链表的删除操作......③p->next=q->next;④free(q);②q=p->next;①if(p->next满足删除条件)2.3线性链表及其运算（1）在线性链表中寻找包含元素x的前一个结点，设该结点号为q，则包含元素x

7、的结点序号p=NEXT(q)图2.26线性链表的删除（2）将结点q后的结点p从线性链表中删除（即让结点q的指针指向包含元素x的结点p的指针指向的结点)（如图b）（3）将包含元素x的结点p送回可利用栈（如图c）14链表的输出操作......③p=p->next;①while(p)②printf("%d",p->data);链表的查找操作......③p2=p1;p1=p1->nxet;①while(num!=p1->num&&p1!=NULL)②