03.单链表.ppt

OS 第二章线性表(二) 数据结构 2012年09月17日 深圳大学网络工程系 蔡茂国 * 上节复习 线性表是n个数据元素的有限序列 数据同一性、数据顺序性 顺序表是用一组地址连续的存储单元依次存储线性表的数据元素 采用动态分配的一维数组表示顺序表 顺序表的数据结构包括elem[]、length、listsize 顺序表的创建： 分配空间给elem，length=0，listsize=初始设定值 顺序表的插入：顺序表对象、位置、数据 后移元素，插入，length+1，n-i+1个元素往后移动 时间复杂度O(n) 顺序表的删除：顺序表对象、位置 前移元素（覆盖第i元素），length-1，n-i+1个元素往后移动 时间复杂度O(n) * 已知一顺序表包含数值11,22,33,44,55,66,77,88,99,111共10个元素，若执行以下操作，计算共移动了多少次，并给出执行后的结果 在第5位置插入数值101 在第8位置插入数值202 删除第3位置元素 练习 一、链表 * 第二节　线性链表 链表是线性表的链式存储表示 链表中逻辑关系相邻的元素不一定在存储位置上相连，用一个链(指针)表示元素之间的邻接关系 　线性表的链式存储表示主要有三种形式： 线性链表[单链表] 循环链表 双向链表 第２章　线性表 二、线性链表 * 第二节　线性链表 线性链表的元素称为结点(node) 结点除包含数据元素信息的数据域外，还包含指示直接后继的指针域 每个结点，在需要时动态生成，在删除时释放 第２章　线性表 data next 二、线性链表 * 第二节　线性链表 每个结点只包含一个指针域的链表称为单链表 单链表可由头指针惟一确定 单链表最后一个元素的指针域为空（NULL） 为了操作方便，有时在线性链表的第一个结点之前附设一个头结点，其数据域可以为空，也可以为线性链表的长度信息。 第２章　线性表 4 a1 a2 a3 a4 ? L ? L a1 a2 a3 a4 ? L 三、线性链表的定义 * 第二节　线性链表 定义一个结点 struct LNode { ElemType data; // 数据域 struct LnodeElemType *next; // 后继指针 } LNode; LNode *head; // 定义结点指针 第２章　线性表 data next 三、线性链表的定义 * 第二节　线性链表 定义一个单链表 class Linklist{ private: LnodeElemType* head; //定义链表头 }； 第２章　线性表 四、找指定元素 * 第二节　线性链表 按值查找，在链表中查找是否有结点值等于给定值key的结点 从头结点开始，顺链一步步查找 第２章　线性表 a2 ai an ? L … … a1 四、找指定元素 * 第二节　线性链表 在链表中找第i个元素 不能象顺序表中那样直接按序号i访问结点，而只能从链表的头结点出发，沿链域next逐个结点往下有哪些信誉好的足球投注网站，直到有哪些信誉好的足球投注网站到第i个结点为止。因此，链表不是随机存取结构 第２章　线性表 a2 ai an ? L … … a1 四、找指定元素(按位置) * 第二节　线性链表 LNode *SearchLinkList(int i) { int j; LNodeELemType *p; p = head; j = 0; // p指向第一个结点 while (p j i) {p = p-next; j++;} // 顺指针查找 if (!p) return(NULL); // 第i元素不存在 return(p-data); }} // SearchLinkList 第２章　线性表 a2 ai an ? L … … a1 四、找指定元素(按值) * 第二节　线性链表 LNode *Locate_Node(ElemType key) { LnodeElemType *p=head; while ( p!=NULL p–data!=key) p=p–next; if (pp–data==key) return p; else { printf(“所要查找的结点不存在!!\n”); return(NULL); } } 第２章　线性表 a2 ai an ? L … … a1 访问整个单链表的代码框架 bool Traverse() { LnodeElemType *p; p=head; /* 使p指向第一个结点 */ while (p!=NULL) { //………你要执行的代码写这里 p=p–next;