第九章链表1.ppt

(4)单链表的查找运算 1)按序号查找 2)按值查找 3.2 单链表的基本运算 1)按序号查找 从单链表的头指针出发，顺着链逐个向下有哪些信誉好的足球投注网站，直至有哪些信誉好的足球投注网站到第i个结点为止。 按序号查找的计数器j初值的设定： 设单链表的长度为n，要查找表中第i个结点，仅当1≤i ≤n时，i值是合法的。但有时需要查找头结点的位置，故把头结点看作是第0个结点，因此计数器j的初值设定因单链表有无头结点而不同： 带头结点的单链表 计数器j的初值j=0 不带头结点的单链表 计数器j的初值j=1 3.2 单链表的基本运算 按序号查找算法操作步骤: step1 初始化：指针p指向头指针,计数器j置0； step2 p非空且计数器j小于i，循环 ； step3 每循环一次,p后移一个位置,计数器j加1 ； step4 循环结束,判断计数器j是否等于要查找的序号； step5 若相等，则返回该结点的指针p；若不相等，则返回NULL。 3.2 单链表的基本运算 * * 1.线性表的基本概念及运算 2.线性表的顺序存储结构及其运算 3.线性表的链式存储结构及其运算 第九章 线性表 线性表的链式存储结构 线性表的顺序表示的特点是用物理位置上的邻接关系来表示结点间的逻辑关系，这一特点使我们可以随机存取表中的任一结点，但它也使得实现线性表的插入和删除操作会移动大量的结点。同时，顺序存储时，人们必须说明顺序表中元素的多少。 为避免大量结点的移动和克服表中元素的确定性。我们介绍线性表的另一种存储方式，链式存储结构，简称为链表(Linked List)。 3.1 线性表的链式存储结构 (1)链表的定义与分类 链表的定义： 采用链接方式存储的线性表称为链表 链表分类： 实现方式 动态链表 静态链表 链接方式 单链表 循环链表 双向链表 3.1 线性表的链式存储结构 (2)链表有关基本概念 链表对存储空间的要求 链表是用一组任意的存储单元来存放线性表的元素，这组存储单元既可以是连续的，也可以是不连续的。因此为了正确表示元素间的逻辑关系,还必须存储指示其后继元素的地址。这两部分信息组成数据元素ai的存储映像，即结点。 链表存储结构形式为： 数据域： 存储数据元素信息的域称作数据域，data域是数据域 指针域： 存储后继元素存储位置的域称作指针域，指针域中存储的信息称指针或地址，next域是指针域。 3.1 线性表的链式存储结构 (2)链表有关基本概念（续） 线性表的链式存储结构： n个结点链接成一个链表，即为线性表的链式存储结构。 单链表： 链表的每个结点中只包含一个指针域，故将这种链表称为单链表。 头指针： 单链表中除开始结点外每个结点的存储地址都是存放在其前趋结点的指针域（next）中，而开始结点无前趋，故应该设头指针head指向开始结点。 终端结点的指针域： 由于终端结点没有后续结点，其指针域为空，即为NULL(也可以用∧表示)。 3.1 线性表的链式存储结构 (3)单链表示意图 右图是线性表（zhao, qian, sun, li, zhou, wu, zheng, wang）的单链表示意图。 也被称为静态链表。 3.1 线性表的链式存储结构 (4)单链表的一般图示法 由于单链表只注重结点间的逻辑顺序，并不关心每个结点的实际存储位置，因此我们通常是用箭头来表示链域的指针，于是链表就可以更直观地画成箭头链接起来的结点序列。 下图是线性表（zhao, qian, sun, li, zhou, wu, zheng, wang）的单链表示意图。 单链表是由头指针唯一确定的,因此单链表可以用头指针的名字命名. 3.1 线性表的链式存储结构 (5)用C语言描述单链表 链表结构的C语言描述为：(数据结构定义)typedf int dataype;struct node /* 结点类型 */{ datatype data; /* 数据域 */ struct node ?next; /* 指针域 */}linklist;linklist ?head，?p; /* 指针类型说明 */ 递归定义形式 3.1 线性表的链式存储结构 (6)对结点操作的标准函数: 结点存储单元分配 p=(linklist *)malloc(sizeof(linklist)); 结点存储单元释放 free(p); 对结点的访问: (*p).data p-data 访问结点的数据域 (*p).next p-next