线性表链式映像 数据结构PPT（课件）知识介绍.pptVIP

2.3 线性表类型的实现 ----链式映象;一、单链表; 用一组地址任意的存储单元存放线性表中的数据元素。; 以线性表中第一个数据元素 的存储地址作为线性表的地址，称作线性表的头指针。; Typedef struct LNode { ElemType data; // 数据域 struct Lnode *next; // 指针域 } LNode, *LinkList; ; 因此，查找第 i 个数据元素的基本操作为：移动指针，比较 j 和 i .; Status GetElem_L(LinkList L, int i, ElemType e) { // L是带头结点的链表的头指针，以 e 返回第 i 个元素 } // GetElem_L;ai-1; 因此，在单链表中第 i 个结点之前进行插入的基本操作为: 找到线性表中第i-1个结点，然后修改其指向后继的指针。; Status ListInsert_L(LinkList L, int i, ElemType e) { // L 为带头结点的单链表的头指针，本算法 // 在链表中第i 个结点之前插入新的元素 e } // LinstInsert_L;s = new LNode; // 生成新结点 s-data = e; s-next = p-next; p-next = s; // 插入 return OK;;线性表的操作ListDelete (L, i, e)在链表中的实现:; 在单链表中删除第 i 个结点的基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。; Status ListDelete_L(LinkList L, int i, ElemType e) { // 删除以 L 为头指针(带头结点)的单链表中第 i 个结点 } // ListDelete_L;单链表的生成;例如：逆位序输入 n 个数据元素的值， 建立带头结点的单链表。;void HCreateList_L(LinkList L, int n) { // 逆序输入 n 个数据元素，建立带头结点的单链表 } // HCreateList_L;void TCreateList_L(LinkList L, int n) { // 顺序输入 n 个数据元素，建立带头结点的单链表 } // TCreateList_L;用上述定义的单链表实现线性表的操作时， 存在的问题：; 最后一个结点的指针域的指针又指回第一个结点的链表。; 2. 双向链表;双向循环链表;双向链表的操作特点：;ai-1;ai-1;ai-1