第2章 线性表单链表.pptVIP

2.3.5 双向链表 单链表 插入算法： void ListInsert_Dul(DuLinkList L, DuLNode *p, DuLNode *e) { s-prior = p? prior; p? prior -next =s; s-next =p; p-prior = s; } 删除算法： void ListDelete_Dul(DuLinkList L, DuLNode *p, ElemTypee) { e=p-data; p -prior -next = p-next; p-next-prior = p- prior; delete p; } * * 2.3 线性表的链式表示和实现 现在讨论线性表的另一种存储表示 ━━ 链表，并以此来实现线性表类型的操作。在具体实现中，淡化了位序的概念。 一、单链表 二、结点和单链表的 C++语言描述 三、单链表的基本操作 四、单链表的创建操作 五、其它形式的链表 用一组地址任意的存储单元存放线性表中的数据元素。 一、单链表 以元素(数据元素的存储空间) + 指针(指示后继元素存储位置) = 结点 (表示数据元素 或 数据元素的存储空间) 以“结点的序列”表示线性表 ?? 称作链表 以线性表中第一个数据元素a1的存储地址作为线性表的地址，称作线性表的头指针。 头结点 a1 a2 … ... an ^ 头指针 头指针 有时为了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针。 空指针 线性表为空表时， 头结点的指针域为空 ? 数据域 指针域 typedef struct LNode { ElemType data; // 数据域 struct LNode *next; // 指针域 } LNode, *LinkList; 二、结点和单链表的描述 LinkList L； // L 为单链表的头指针 数据域data 指针域next L?next L?data 1、求 线性表的长度--统计链表中结点个数 L 21 18 30 75 42 56 ∧ p k 0 p 1 p 2 p 3 4 p 5 p p 6 三、单链表的基本操作 一边遍历链表一边进行统计k的个数，当遍历指针p为空时，k为线性表的长度。 p=L; k=0; while ( p ) { k++; p=p-next; } 注意： 由于各结点的地址不是连续的，因此指针p向后移动不能为p++ int ListLength_L( LinkList L ) { // L 为链表的头指针，本函数返回 L 所指链表的长度 p=L; k=0; while ( p ) { k++; p=p-next; // k 计非空结点数 }//while return k; } // ListLength_L 算法时间复杂度为: O(n) n为表长 2、查找元素操作 一边遍历链表一边比较给定值e与结点p的数据域值。查找结果有两种可能：找到时，返回第一个和值e 相等的数据结点指针p；找不到，返回空指针。 p p p e = 30 58 L 21 18 30 75 30 56 ∧ p p p p p p p p=L; while ( p-data != e ) p=p-next; if(p) cout“找到”;else cout“找不到”endl; p p的指向的结点是要找的结点 LNode* LocateElem_L( LinkList L， ElemType e ) { p=L; while ( p p-data != e ) p=p-next; return p; } // LocateElem_L 算法时间复杂度为: O(n) 3.插入结点操作 在p所指结点之前，插入已经生成的结点s。 思路: （1）确定p指针原来的前驱结点q位置。 从头遍历链表，确定前驱结点的指针q。