032线性表2-单链表.ppt

OS * 数据结构 深圳大学 计算机与软件学院 白鉴聪 * 第二章 线性表 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 一元多项式的表示和实现 * 上节复习 线性表是n个数据元素的有限序列 数据同一性、数据顺序性 顺序表是用一组地址连续的存储单元依次存储线性表的数据元素 采用C语言中动态分配的一维数组表示顺序表 顺序表的数据结构包括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位置元素 练习 * 2.3 链表 链表的概念 链表是线性表的链式存储表示 链表中逻辑关系相邻的元素不一定在存储位置上相连，用一个链(指针)表示元素之间的邻接关系 线性表的链式存储表示主要有三种形式： 线性链表 循环链表 双向链表 * 2.3 链表 线性链表 线性链表的元素称为结点(node) 结点除包含数据元素信息的数据域外，还包含指示直接后继的指针域 每个结点，在需要时动态生成，在删除时释放 data next * 2.3 链表 单链表 每个结点只包含一个指针域的链表称为单链表 单链表可由头指针惟一确定 单链表最后一个元素的指针域为空（NULL） 为了操作方便，有时在线性链表的第一个结点之前附设一个头结点，其数据域可以为空，也可以为线性链表的长度信息。 4 a1 a2 a3 a4 ? L ? L a1 a2 a3 a4 ? L * 2.3 链表 单链表 单链表的定义 //定义一个结点，也是定义一个链表 typedef struct LNode { ElemType data; // 数据域 struct LNode *next; // 后继指针 } LNode, *LinkList; data next * 单链表 单链表的插入是在链表的第i-1元素与第i元素之间插入一个新元素 s-next = p-next; p-next = s; 2.3 链表 ai-1 ai s … … e 插入前 p … ai-1 ai s … e 插入后 p * 单链表 单链表插入的代码 Status ListInsert_L(LinkList L, int i, ElemType e) { // 在带头结点的单链表L中第i个位置之前插入元素e p = L; j = 0; while (p ji-1) {p = p-next; j++;} // 寻找i-1结点 if (!p || ji-1) return ERROR; s = (LinkList) malloc(sizeof(LNode)); // 生成新结点 s-data = e; s-next = p-next; p-next = s; // 插入L中 return OK; } // ListInsert_L 2.3 链表 * 单链表 单链表插入的算法时间复杂度主要取决于while循环中的语句频度 频度与在线性链表中的元素插入位置有关，因此线性链表插入的时间复杂度为O(n) 2.3 链表 * 单链表 单链表的删除是将第i元素删除 p-next = p-next -next 2.3 链表 p ai-1 ai+1 ai 删除前 ? ai-1 ai ai+1 p q 删除后 * 单链表 单链表删除的代码 Status ListDelete_L(LinkList L, int i, ElemType e) { // 在带头结点的单链表L中，删除第i个位置的元素 p = L; j = 0; while (p-next ji-1) {p = p-next; j++;} // 寻找i结点 if (!p-next || ji-1) return ERROR; q = p-next; p-next = q-next; // 删除i结点 e = q-data; // 取值 free(q); // 释放结点 return OK; } // ListDelete_L 2.3 链表 * 单链表 单