数据结构 02章 线性表.pptVIP

单循环链表和非循环单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”。 即 p-next ==NULL 而是“后继是否为头结点” 即　　　p-next == head Location_Sq( L, e)－－P.27 初始条件： 操作结果： 线性表 L 已存在，e为给定值 返回 L 中第 1 个等于 e 的元素的 　　 下标(≥0)。 若这样的元素不存在，则报错处理。 // 查找定位函数 int Location_Sq (SqList L, int e) { // 在顺序表中查找第一个满足判定条件的数据元素， // 若存在，则返回它的下标，否则报错。 } O( n ) if (i = L.length) return ERROR; else return i; 算法的时间复杂度为： i = 0; 　 // i的初值为第1元素的下标 while ( i L.length L.elem[i] != e) i ++; 　　// 顺序查找 //找到满足条件的元素 // 没有找到满足条件的元素 P.29 例2.4 一. 概念 　　　用一组地址任意的存储单元存放线性表中的数据元素。 2.3.1 单链表的定义及存储 以 元素 （数据元素的映象－－数据域） + 指针 （指示后继元素的存储位置－－指针域） = 结点 （表示数据元素ai的存储映象） 以“结点的序列”表示的线性表 ?? 称作链表 以线性表中第 1 个数据元素 的存储地址作为线性表的(入口)地址，称作线性表的头指针。 头结点 a1 a2 … ... an ^ 头指针 头指针 　有时为了操作方便，在第 1 个结点之前虚加一个“头结点”，以指向头结点的指针作为链表的头指针。 空指针 线性表为空表时， 头结点的指针域为空 ? typedef struct LNode { ElemType 　data; // 数据域 struct LNode *next; // 指针域 } LNode, *LinkList; 二.结点和单链表的结构描述 P.31 图2-8，图2-9 2.3.2 单链表基本运算的实现 LocationElem(L, i, e) // 查取第i个数据元素 ListInsert_L(L, i, e) 　　　　　　//第i个结点之前插入数据元素 ListDelete_L(L, i, e) // 删除第i个数据元素 InitList_L(L) // 建一个带头结点的空线性表 CreateList_L(L, n) 　// 生成含 n 个数据元素的链表 int InitList_L( LinkList L) { L=(LinkList) malloc ( sizeof (LNode)); if (L==NULL) exit (OVERFLOW); L-next =NULL; return OK; }// InitList_L InitList_L(L) // 建一个带头结点的空单链表－－P.32,算法2.9 L 2. 查取单链表的第 i 个 元素－－P.32 LocationElem(L, i, e) 21 18 30 75 42 56 ∧ p p p j 1 2 3 －－ 算法2.10 i=3 i=7 P=^ j=7 因此，查找第 i 个数据元素的基本操作为移动指针，比较 j 和 i. 单链表是一种顺序存取的结构，为查找第 i 个数据元素，必须从第1 个数据元素起，依次顺链查找。 令 j 为记数器，指针 p 同步指向线性表中的第 j 个数据元素。 int LocationElem(LinkList L, int i, int e) {// 在带头结点的空链表中，查第i个数据元素 LinkList p= L-next ; int j=1; while ( ji p!=NULL) { p= p-next; j++; } if ( p==NULL|| ji ) return ERROR; e= p-data; return OK; } ai-1 3. 在单链表第i个结点之