数据结构CC++第三章单链表.pptVIP

数据结构 第三章 链表 第三章 链表 知 识 点 单链表的结点形式、组织方法和特点 单链表的基本运算和相应的算法 循环链表的组织方法和基本运算算法 双链表的结点形式、组织方法和特点 双链表的基本运算和相应的算法 顺序表与链表比较，各自的优、缺点 链表的应用 用十字链表表示稀疏矩阵 难 点 双链表插入、删除运算的算法 利用链接结构的特点设计有效算法，解决与链表结构相关的应用问题 要 求 熟练掌握以下内容: 单链表的结构特点、基本运算并能设计简单算法 循环链表的结构特点、基本运算并能设计简单算法 双链表的结构特点、基本运算并能设计简单算法 第三章目录 3.1 单链表及其运算 3.2 循环链表与双向链表 3.3 链表应用举例 3.4 表示稀疏矩阵的十字链表 3.5 应用举例及分析 小 结 习题与练习 3.1 单链表 1. 结点: 在链式存储结构中，结点不仅存放数据元素的值，还附加一个指针（链），用来指向该结点的直接后继结点。 其中，data部分称为数据域，用于存储线性表的一个元素，next部分称为指针域或链域，用于存放一个指针，即存放该结点的直接后继结点的地址。 2. 单链表 所有结点通过指针的链接而构成的线性表称为单链表。线性表（a1，a2，……an，）的单链表可直观地画成： head是单链表的头指针，指向开始结点a1, an是终端结点，其指针域为空，不指向任何结点。 一个单链表由头指针head唯一标识和确定，因此，可用头指针来命名单链表。 3. 单链表的类型定义 假设线性表中数据元素的类型为datatype，单链表的类型定义如下： typedef struct node { datatype data; struct node *next; }*linklist; linklist是指向struct node类型变量的指针类型。Struct node是结构体类型。一个结点是由两个域data和next组成,data是结点的数据域，next是结点的链域，next是一个linklist类型的指针类型。 链表中每个结点的建立和和删除，需要通过动态地分配和撤销内存空间来实现。C语言中是利用库函数malloc和free来分配和撤销内存空间。C++提供了较简便而功能较强的运算符new和delete来分配和撤销内存空间。格式： new 类型 delete 指针变量 4、 单链表的基本运算 （1）建立单链表 建立有n个结点的单链表 #define NULL 0 #include iostream Using namespace std; typedef struct node { datatype data; struct node *next; }*linklist; （2）遍历(Traversal)：根据表头指针，依次访问单链表的各个结点。 例如，当要打印或显示出各个结点的数值域值、计算单链表的长度 (即结点数目)或寻找某一个结点时都需要遍历单链表。 假设head是单链表的头指针，计算一个已建立好的单链表的结点个 数的算法如下： （3）插入 例如，在单链表中第i个结点(i≥0)之后插入一个元素为x的结点。 实现插入算法主要完成三个基本操作： 1) 在单链表上找到插入位置，即找到第i个结点。 可以用遍历的方法，即从表头起顺次访问单链表的结点，直至找到第i个结点。 2) 生成一个以x为值的新结点。 可通过C++的new运算符来产生。 3) 将新结点链入单链表中。 需要改变相关结点的指针 ，如下面的图所示。 假设指针p指向单链表中的第i个结点，指针s指向已生成的新结点，链入新结点的操作如下： 将新结点*s的链域指向结点*p的后继结点 (即s-next=p-next)； 将结点*p的链域指向新结点(即p-next=s)。 void insert (linklist head, int i, int x) {linklist s, p; int j; s=new node /*生成新结点*/ s-data = x; if(i= =0) /*如果i=0,则将s所指结点插入到表头*/ {s-next=head; head=s; } 假设指针q指向待删除结点的前一个结点，指针p指向要删除的结点，删除该结点的操作如下：将该结点的前一个结点*q的链域指向*p的后继结点（即q-next=p-next）。 void del (linklist head,