4线性表的链式表示和实现资料.ppt

线性表的链式表示和实现 导入: 注意： a) 要让p指向第i-1个而不是第i个元素（否则，不容易找到前驱以便插入）。 b) 能够插入的条件： p j==i-1 。即使第i个元素不存在，只要存在第i-1个元素，仍然可以插入第i个元素。 c) 新建结点时需要动态分配内存。 s = (LinkList) malloc(sizeof(LNode)); 若检查是否分配成功，可用 if ( s==NULL ) exit(1); // 分配失败则终止程序 d) 完成插入的步骤：①②。技巧：先修改新结点的指针域。 注意： a) 要求p找到第i-1个而非第i个元素。 b) 能够进行删除的条件：p-next j==i-1 。 c) 释放结点的方法。 free(s); d) 完成删除的步骤：①②。 6）链表的遍历（求表长） void PrintList_L ( LinkList L ) { LinkList p = L-next ; while(p) { printf ( p-data ) ; //改为统计个数 p=p-next ; } } 课堂总结主要内容：线性表的链式表示和实现（取元素、插入、删除、清空、建单链表，遍历）。 重点难点：单链表的插入、删除算法。 作业1. 请写出顺序表和单链表的类型定义，并在这两种定义的基础上分别给出在第i个结点之前插入一个数据元素e的算法。 * * 教学目的：掌握线性表的链式表示和实现:单链表类型C语言描述，取元素、插入、删除、清空等算法。 重点难点：单链表的插入、删除算法。 2.3 线性表的链式表示和实现 教学内容 顺序表定义、操作特点？ typedef struct { } SqList; // 俗称 顺序表 #define MAXSIZE 100 // 线性表存储空间的分配量，即数组长度 ElemType Elem[MAXSIZE]; //存放线性表的数组 int length; // 当前长度 内容回顾 结构决定操作，为了避免顺序表的缺点，就要改变其存储结构，本节我们将讨论线性表的另一种表示方法---链式存储结构，由于，它不要求逻辑上相邻的元素在物理位置上也相邻，因此它没有顺序存储结构所具有的弱点，但同时也失去了顺序表可随机存取的优点。 1、单链表 2、结点和单链表的 C 语言描述 3、线性表的操作在单链表中的实现 2.3 线性表的链式表示和实现 以元素(数据元素的映象) –数据域 + 指针(指示后继元素存储位置)-指针域（指针/链） = 结点(表示数据元素或 数据元素的映象) n个结点（ai(1=i=n)）链结成一个链表，即为线性表（a1,a2,---an）的链式存储结构。由于此链表的每个结点中只包含一个指针域，故称为线性链表或单链表。 ai ai+1 1、单链表 以线性表中第一个数据元素 的存储地址作为线性表的地址，称作线性表的头指针。 头结点 a1 a2 … ... an ^ 头指针 头指针 有时为了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针。 空指针 线性表为空表时， 头结点的指针域为空 ? typedef struct LNode { ElemType data; //数据域 struct LNode *next; //指针域 } LNode, *LinkList; LinkList L； //L为单链表的头指针 2、结点和单链表的 C 语言描述 1) GetElem_L(L, i, e) // 取第i个数据元素 2) ListInsert_L (L, i, e) // 插入数据元素 3) ListDelete_L (L, i, e) // 删除数据元素 4) ClearList_L (L) // 重置线性表为空表 5) CreateList_L (L, n) // 生成含 n 个数据元素的链表 3、线性表的操作在单链表中的实现 6) PrintList_L(LinkList