0数据结构02线性表.ppt

武汉生物工程学院 /* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */ /* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */ Status ListDelete(SqList *L,int i,ElemType *e) { int k; if (L-length==0) /* 线性表为空 */ return ERROR; if (i1 || iL-length) /* 删除位置不正确 */ return ERROR; *e=L-data[i-1]; if (iL-length) /* 如果删除不是最后位置 */ { for(k=i;kL-length;k++)/* 将删除位置后继元素前移 */ L-data[k-1]=L-data[k]; } L-length--; return OK; } 武汉生物工程学院 顺序存储结构的优缺点 逻辑相邻，物理相邻 可随机存取任一元素 存储空间使用紧凑 插入、删除操作需要移动大量的元素 预先分配空间需按最大空间分配，利用不充分 缺点： 优点： 武汉生物工程学院 武汉生物工程学院 一、单链表 二、结点和单链表的 C 语言描述 三、线性表的操作在单链表中的实现 四、一个带头结点的单链表类型 五、其它形式的链表 武汉生物工程学院 用一组地址任意的存储单元存放线性表中的数据元素。 一、单链表 以元素(数据元素的映象) + 指针(指示后继元素存储位置) = 结点 (表示数据元素及关系的映象) 以“结点的序列”表示线性表 ?? 称作链表 武汉生物工程学院 以线性表中第一个数据元素 的存储地址作为线性表的地址，称作线性表的头指针。 头结点 a1 a2 … ... an ^ 头指针 头指针 有时为了操作方便，在第一个数据元素结点之前增加一个“虚”的“头结点”，并且以指向头结点的指针作为链表的头指针。 空指针 线性表为空表时， 头结点的指针域为空 ? 武汉生物工程学院 武汉生物工程学院 typedef struct LNode { ElemType data; // 数据域 struct LNode *next; // 指针域 } LNode, *LinkList; 二、结点和单链表的 C 语言描述 LinkList L； // L 为单链表的头指针 武汉生物工程学院 三、单链表操作的实现 GetElem(L, i, e) // 取第i个数据元素 ListInsert(L, i, e) // 插入数据元素 ListDelete(L, i, e) // 删除数据元素 ClearList(L) // 重置线性表为空表 CreateList(L, n) // 生成含 n 个数据元素的链表 武汉生物工程学院 线性表的操作 2.8 GetElem(L, i, e) 单链表是一种顺序存取的结构，为找第 i 个数据元素，必须先找到第 i-1 个数据元素。 因此，查找第 i 个数据元素的基本操作为：移动指针，比较 j 和 i 。 令指针 p 始终指向线性表中第 j 个数据元素。 武汉生物工程学院 Status GetElem_L(LinkList L, int i, ElemType e) { // L是带头结点的链表的头指针，以 e 返回第 i 个元素 } // GetElem_L 算法时间复杂度为: O(ListLength(L)) p = L-next; j = 1; //p指向第一个结点，j为计数器 while (p ji) { p = p-next; ++j; } // 顺指针向后查找，直到 p 指向第 i 个元素或 p 为空 if ( !p || ji ) return ERROR; // 第 i 个元素不存在 e = p-data; // 取得第 i 个元素 return OK; 武汉生物工程学院 线性表的操作 2.9