《数据结构 第4讲 线性表-单链表》由会员分享，可在线阅读，更多相关《数据结构 第4讲 线性表-单链表（46页珍藏版）》请在金锄头文库上搜索。
1、第2章 线性表,2/50,顺序表用一维数组保存信息：1）线性表中的数据元素；2）线性表中数据元素的顺序关系；,课程回顾,*顺序存储：顺序表 SeqList,顺序表的基本操作（1）创建（2）查找：按位查找（随机存取） 按值查找（计算比较次数）（3）插入：计算结点移动次数，平均 时间复杂度的分析（4）删除：计算结点移动次数，平均 时间复杂度的分析（5）遍历,课程回顾,4/50,线性表按存储分类：1）顺序存储：顺序表 SeqList2）链式存储：链表,线性链表 LinkList （单链表）循环链表 CircularList双向链表 DoubleList静态链表 StaticList,Essentia
2、l of Lecture Two：,一、线性链表 二、单链表的基本操作 三、单链表实战应用,第2讲 单链表,难点,用一组任意的存储单元存储线性表的数据元素； 利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素；,一、线性链表 ( Linked List ),1. 链式存储结构的特点：,存储特点：逻辑次序和物理次序 不一定相同。 2.元素之间的逻辑关系 用指针表示。,例：(a1, a2 ,a3, a4)的存储示意图,链式存储示例：,a10200,a20325,a30300,a4 ,2. 链式存储基本的结点结构：,为了存储线性表，至少要保存两类信息：1）线性表中的数据元素；2）线性表中数据元素的
3、顺序关系；,注意：数据域用来存放数据元素，指针域用来存放当前结点的直接前驱或直接后继结点的地址。,3. 单链表,n个结点通过指针连成一个链表，若结点中只有一个指针域，则称为线性链表（即单链表）。,data：存储数据元素信息next：存储指向后继结点的地址,存储地址,1,7,13,19,25,31,37,43,43,13,1,NULL,37,19,25,7,例 线性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG),逻辑示意图,template struct Node DataType data; Node *next;,如何申请一个结点？,s=new Node ;,
4、4. 单链表的实现,s=new Node;,如何引用数据元素？,data,如何引用指针域？,next,s-next;,使用单链表时，关心的是数据元素以及数据元素之间的逻辑关系，而不是每个数据元素在存储器中的实际位置，因此右图的表示我们经常画成示意图。,单链表的示意图？,头指针first：指向第一个结点的地址。尾标志：终端结点的指针域为空。,头结点：在单链表的第一个元素结点之前附设一个类型相同的结点，以便空表和非空表处理统一。,非空表,如何将空表与非空表统一？,加上头结点之后，无论单链表是否为空，头指针始终指向头结点，便于空表和非空表做统一处理。,template class LinkList
5、public: LinkList( )； LinkList(DataType a , int n); LinkList( ); int Length( ); DataType Get(int i); int Locate(DataType x); void Insert(int i, DataType x); DataType Delete(int i); void PrintList( ); private: Node *first; /头指针;,单链表类的声明,操作接口：LinkList(DataType a , int n),头插法：将待插入结点插在头结点的后面 。,算法描述：first
6、=new Node; first-next=NULL;,1、构造函数,二、单链表的基本操作,头插法：将待插入结点插在头结点的后面 。,算法描述：s=new Node; s-data=a0;s-next=first-next;first-next=s;,插入第一个元素结点,first,算法描述：s=new Node; s-data=a1;s-next=first-next;first-next=s;,依次插入每一个结点,template LinkList : LinkList(DataType a , int n) first = new Node; first-next = NULL; for
7、 (i = 0; i data = ai; s-next = first-next; first-next = s; ,头插法建立单链表算法描述C+描述,尾插法：将待插入结点插在终端结点的后面。,算法描述：first=new Node; rear=first;,设置一个尾指针，指向终端结点,尾插法：将待插入结点插在终端结点的后面。,算法描述：s=new Node; s-data=a0;rear-next=s;rear=s;,插入第一个元素结点,尾插法：将待插入结点插在终端结点的后面。,算法描述：s=new Node; s-data=a1;rear-next=s;rear=s;,依次插入每一个结
8、点,35,尾插法：将待插入结点插在终端结点的后面。,算法描述：rear-next=NULL;,最后一个结点插入后,35,template LinkList : LinkList(DataType a , int n) first = new Node; /生成头结点 rear= first; /尾指针初始化 for (i = 0; i data = ai; rear-next = s; rear = s; rear-next = NULL; ,尾插法建立单链表算法描述C+描述,带头结点的单链表初始化,不带头结点的单链表初始化,带头结点的单链表在空表和非空表处理时统一，插入结点时不用考虑第1个结
9、点与其他结点的不同。,尾插法,主函数验证单链表的初始化,注意：头结点的data部分可以灵活使用，可以不存储任何信息，也可以根据需要存储单链表的长度。,操作接口： void PrintList( );,核心操作：工作指针后移。 从头结点出发，通过工作指针的反复后移而将整个单链表“审视”一遍的方法称为扫描（或遍历）。,first,a1,a2,an,ai,2、遍历,二、单链表的基本操作,设置一个工作指针p，指向当前结点，处理完之后指向后继结点，直到P为NULL为止。,操作接口： void PrintList( );,template void LinkList : PrintList( ) p =
10、first-next; /工作指针初始化 while (p != NULL) cout data; p = p-next; ,算法描述：,操作接口： int Length( );,核心操作：从第一个结点数到表尾。 从头结点出发，通过工作指针依次指向各个结点，则最后一个结点的序号即为表中结点的个数（链表的长度）。,first,a1,a2,an,ai,3、求表长,操作接口： int Length( );,template void LinkList : Length( ) p = first-next; count = 0; while (p != NULL) p = p-next; count+
11、; return count;,算法描述：,单链表的实现按位查找,操作接口： DataType Get(int i);,first,a1,a2,an,ai,1. 工作指针p初始化; 累加器count置1;2. 重复执行下述操作，直到p为空并且count值小于i： 2.1 工作指针p后移; 2.2 count+;3. 返回找到的第i个结点的元素值；,4、查找,template int LinkList : Get(int i) p = first-next; count = 1; while (p != NULL,单链表的实现按位查找,算法描述C+描述,顺序存取结构：在单链表中，即使知道被访问结
12、点的位置，也不能像顺序表一样直接按序号访问，只能从头指针出发逐个往下搜索，这种存储结构也称为：顺序存取结构。,template int LinkList : Locate(DataType x) p = first-next; count = 1; while (p != NULL) if (p-data = x) return count; /查找成功，返回序号 p = p-next; count+; return 0; /退出循环表明查找失败,单链表的实现按值查找,算法描述C+描述,操作接口： void Insert(int i, DataType x); 在单链表中第i（1=idata=x;s-next=p-next; p-next=s;,由于单链表带头结点，表头、表中、表尾三种情况的操作语句一致。,算法描述伪代码,1. 工作指针p初始化； 2. 查找第i-1个结点并使工作指针p指向该结点； 3. 若查找不成功，则插入位置不合理，抛出插入位 置异常； 否则， 3.1 生成一个元素值为x的新结点s； 3.2 将新结点s插入到结点p之后；,template void LinkList : Insert(int i, DataType x) p = first ; count = 0; /工作指针p应指向头结点 while (p != NULL /结点s插入结点p之后 ,
