数据结构2-3.pptVIP

线性表的链式表示与实现 顺序存储与链式存储的比较 链表是指用一组任意的存储单元来依次存放线性表的结点，因此，链表中结点的逻辑次序和物理次序不一定相同。 结点结构： ，结点的两个域： data域是数据域，用来存放结点的值； next是指针域（亦称链域），用来存放结点的直接后继的地址。 线性表的链式表示与实现 链表的每一个结点只有一个链域，故将这种链表称为单链表（Single Linked)。 单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。 由于终端结点无后继，故终端结点的指针域为空，即null（图示中也可用^表示)。 线性链表实例，参见P27 线性表的链式表示与实现 单链表存储结构 Typedef struct LNode{ ElemType data; struct LNode *next; } LNode，*LinkList; //注意区分指针变量和结点变量这两个不同的概念。 单链表中遍历或寻找某个数据元素的方法， 若p-data=ai, p-next-data=ai+1 单链表创建（尾插法建表）参见算法2.11 P30 算法2.8：单链表存取元素，P29 算法2.9：单链表插入元素，P29 算法2.10：单链表删除元素， P30 算法2.12：将两个有序链表并为一个有序链表，P31 静态链表 一维数组来描述线性链表 数组的第一个分量表示结点的值．同时用游标(指示器cur)代替指针指示结点在数组中的相对位置，数组的第零分量可看成头结点，其指针域指示链表的第一个结点。 这种存储结构仍需要预先分配一个较大的空间，但在作线性表的插入和删除操作时不需移动元素，仅需修改指针。故仍具有链式存储结构的主要优点。 为了和指针型描述的线性链表相区别，给这种用数组描述的链表起名叫静态链表。 例如：图2.10(b)展示了图2.10(a)所示线性表在插入数据元素SHI和删除数据元素ZHENG之后的状况。 在静态链表中实现线性表的操作和动态链表相似，以整型游标i代替动态指针p，i=S[i].cur的操作实为指针后移(类似于p=p-next)。 例如，在静态链表中实现的定位函数LocateElem如算法2.13所示。 * 数据结构 第二章 线性表 next data 建表的过程就是动态生成链表的过程 两种建表方式：头插法建表与尾插法建表。 单链表是非随机存取的存储结构 注意：修改指针的顺序