【大学数据结构课件】线性表.pptVIP

内容提要 3.1 线形表的基本概念 存储结构:顺序存储结构(顺序表)和链式存储结构(链表) 3.2 顺序表 顺序表的定义 顺序表的数据类型定义 顺序表的基本操作 3.3 链表 单链表 静态链表 循环链表 双向链表 3.4 广义表 3.1 线性表的基本概念 线性表：B=(A,R), A={ai|i=1,2,..,n}, R={ai-1,ai|i=2,3,…,n} 起始元素：a1 终止元素： an 数据元素的位序：i 线性表的长度：n 空表：n为0时的线性表 常见的操作： 存储结构：顺序存储结构(顺序表) 链式存储结构(链表) 3.2 顺序表 顺序表：用一组地址连续的存储单元按线性表的元素间的逻辑顺序一次存放数据元素。它是一种随即存取结构。 顺序表的数据类型定义： 顺序表(cont’d) 1、顺序表的基本操作(创建) 顺序表(cont’d) 1、顺序表的基本操作(查找) 顺序表(cont’d) 1、顺序表的基本操作(删除) 顺序表(cont’d) 1、顺序表的基本操作(插入) 顺序表(cont’d) 2、顺序表的操作实例 顺序表(cont’d) 2、顺序表的操作实例 3.3 链表之单链表 1、单链表定义 结点：数据元素与指向后继的指针存储在一起称为结点 数据域：结点中存放数据元素的部分 指针域：结点中存放指针的部分 单链表：结点中只有一个指针的链表 链表之单链表(cont’d) 2、单链表的数据类型定义： 链表之单链表(cont’d) 3、单链表的基本操作(创建) 链表之单链表(cont’d) 3、单链表的基本操作(遍历) 链表之单链表(cont’d) 3、单链表的基本操作(定位) 链表之单链表(cont’d) 3、单链表的基本操作（定位） 链表之单链表(cont’d) 3、单链表的基本操作(删除) 链表之单链表(cont’d) 3、单链表的基本操作(插入) 链表之单链表(cont’d) 4、单链表的操作实例 链表之单链表(cont’d) 链表之静态链表 1、静态链表：用一维数组存放的线性链表 2、静态链表的数据类型定义： 链表之静态链表(cont’d) 3、静态链表的实例：(用－1表示后继是空) 链表之静态链表(cont’d) 4、静态链表的管理算法(初始化)： 链表之静态链表(cont’d) 4、静态链表的管理算法(分配)： 链表之静态链表(cont’d) 4、静态链表的管理算法(回收)： 链表之静态链表(cont’d) 5、静态链表的操作实例： 链表之循环链表和双向链表 1、循环链表：表尾结点的next指针指向表头结点的链表。 2、双向链表：结点存在两个指针域，一个指向后继结点，另一个指向前驱结点。 3、双向循环链表： 链表之循环链表和双向链表(cont’d) 4、双向链表的数据类型定义： 链表之循环链表和双向链表(cont’d) 链表之循环链表和双向链表(cont’d) 3.4 广义表 1、广义表：线性表的推广，当线性表中的数据元素也可以是个线性表时，这个线性表就是广义表。 原子：广义表中本身不是表的数据元素，用小写字母表示 子表：广义表中本身也是广义表的数据元素，表名用大写字母表示 2、广义表的表示方法：表名=(item,item….,item) 3、广义表的实例： A=( ) B=(e) C=(a,(b,c,d)) D=(A,B,C,f) 广义表(cont’d) 4、广义表的数据类型定义： 《数据结构》 第二章 线性表 typedef struct glnode {int tag; /*用于区分原子项还是子表项*/ union {elemtype data; /*存放原子项的数据元素*/ struct glnode *head; /*指向子表的表头指针*/ }item; struct glnode *next; /*指向后继结点*/ }*GLIST; * * 访问元素 删除元素 插入元素 查找元素 排序 合并拆分 数据元素的逻辑顺序与在内存中的存储顺序完全一致，必需要额外存储数据元素之间的关系 #define MAXSIZE 100 /*顺序表的最大长度*/ typedef struct { elemtype elem[MAXSIZE]; /*elemtype可以根据实际需要而定*/ int len; /*顺序表当前的长度*/ }SQLIST; void createsqlist(SQLIST *L) { int i; prin