通信数据结构课件陈雄峰2第二章线性表.pptVIP

第二章 线性表 重点：链表的数组和链接实现 。 难点：链表的链接实现 。 知识点： 线性表 顺序表 链表 顺序表与链表的比较 线性表 定义： n（?0）个数据元素的有限序列，记作（a1, …ai-1, ai, ai+1,…, an） 其中,ai 是表中数据元素，n 是表长度。 特点: 同一线性表中元素具有相同特性。 相邻数据元素之间存在序偶关系。 除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。 除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。 2.1线性表类型的定义 抽象数据类型线性表的定义如下： LinearList=(D,R) ， 其中： D={ ai| ai∈ElemSet,i=0,1,2, …，n-1 n≥1} R={ai-1，ai| ai-1，ai∈D, i=1,2, …，n} Elemset为某一数据对象集；n为线性表的长度。 线性表的基本操作有如下几种：（P19） 对线性表 基本操作实现后，可以被直接调用来实现复杂操作。 2.2线性表的顺序表示和实现－顺序存储结构 定义：将线性表中的元素相继存放在一个连续的存储空间中。 存储结构：数组。 特点：线性表的顺序存储方式。 存取方式：顺序存取 顺序存储结构示意图 顺序存储结构： 线性表的动态分配顺序存储结构： 初始化：分配一个预定义大小的存储空间，并将当前长度置为0。 顺序表的删除操作 2.3 线性表的链式表示和实现 链表是线性表的链接存储表示 单链表： 静态链表 循环链表 双向链表 以上均可有头结点和无头结点 单链表(Singly Linked List) 定义：用一组地址任意的存储单元存放线性表中的数据元素。 线性链表: （a1,a2,…,an） 单链表(Singly Linked List) 例：线性表：（ZHOU,ZHAO,SUN,WU,WANG,ZHANG,LI） 在C语言中用“结构指针”描述 typedef struct LNode{ ElemType data; struct LNode *next; }LNode,*LinkList; 带表头结点的单链表 表头结点位于表的最前端，本身不带数据，仅标志表头。 设置表头结点的目的:简化链表操作的实现。 算法2.8 Status GetElem_L(LinkList L,int i, ElemType e) { // L为带头结点的单链表的头指针。 // 当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR LinkList p; p = L-next; int j = 1; // 初始化，p指向第一个结点，j为计数器 while (p ji) { // 顺指针向后查找，直到p指向第i个元素或p为空 p = p-next; ++j; } if ( !p || ji ) return ERROR; // 第i个元素不存在 e = p-data; // 取第i个元素 return OK; } // GetElem_L 插入结点：指针p所指的结点后插入指针ｓ所指的结点 插入结点：指针p所指的结点后插入指针ｓ所指的结点① s-next=p-next② p-next=s 算法2.9 Status ListInsert_L(LinkList L, int i, ElemType e) { // 在带头结点的单链线性表L的第i个元素之前插入元素e LinkList p,s; p = L; int j = 0; while (p j i-1) { // 寻找第i-1个结点 p = p-next; ++j; } if (!p || j i-1) return ERROR; // i小于1或者大于表长 s = (LinkList)malloc(sizeof(LNode)); // 生成新结点 s-data = e; s-next = p-next; // 插入L中 p-next = s; return OK; } // LinstInsert_L 删除结点：删除指针ｐ所指的结点后的结点 删除结点：删除指针ｐ所指的结点后的结点 删除结点：删除指针ｐ所指的结点后的结点 删除结点：删除指针ｐ所指的结点后的结点 算法2.10 Status ListDelete_L(LinkList L, int i, ElemType e) {