青岛大学数据结构与算法——第2章
一 概述
- 线性表的定义和特点
- 线性表示例
- 线性表的类型定义
- 线性表的顺序表示和实现
- 线性表的链式表示和实现
- 顺序表和链式表的比较
- 线性表的应用
- 案例分析与实现
二 线性表的定义和特点
2.1 定义和特点
2.2 示例
- 26个英文字母表
- 学生登记表
- 12星座
三 线性表示例
- 1元多项式运算
- 稀疏多项式运算
- 图书管理系统
四 线性表的类型定义
4.1 抽象数据类型ADT定义
4.2 基本操作
- InitList
- DestoryList
- ClearList
- ListEmpty
- ListLength
- GetElem
- LocateElem
- PriorElem
- NextElem
- ListInsert
- ListDelete
- ListTraverse
五 线性表的顺序表示和实现
5.1 C语言补充
- 数组分配：数组静态分配，数组动态分配
- 动态分配相关函数：malloc、sizeof、free
- C++：new 动态分配、delete
- 参数传递方式：
- 传值方式：整形、实型、字符型
- 传址方式：指针、引用、数组
5.2 线性表(一维数组)
- 依次存储
- 地址连续
- 中间没有空出存储单元
- 第i和第i+1之间满足关系
- 随机存储
- 类型相同
5.3 示例
- 顺序表基本操作的实现
- 线性表L的初始化
- 销毁线性表L
- 求线性表L的长度
- 判断线性表L是否为空
- 顺序表的取值
- 顺序表的查找分析法(ASL)
- 插入不同位置(头部/中间/尾部)演示
- 删除不同位置(头部/中间/尾部)演示
- 图书表第顺序存储结构表示
- 多项式顺序存储结构表示
5.4 线性表的总结
- 优点：存储密码大、可以随机存取表中任一元素
- 缺点：插入、删除元素，需要移动大量元素；浪费存储空间；静态存储，不能自由扩充
六 线性表的链式表示和实现
6.1 链式表示
- 物理位置任意
- 可以连续，可以不连续
6.2 示例
- 姓名(链式表示)
- 26个字母表(链式表示)
6.3 相关术语
- 节点：数据域、指针域
- 链表：n个节点
- 分类：单链表、双链表、循环链表
- 头指针/头节点/首元节点
- 存储结构：点头节点/不带点头节点
- 空表
6.4 单链表
- 单链表的存储结构
- 单链表的表示
- 单链表的操作：初始化、判空、销毁DestoryList_L、清空ClearList、表长ListLength_L、第i个元素的内容GetElem_L、按值查找位置LocateElem_L、在第i个节点前插入值为e的新节点ListInert_L、删除第i个节点ListDelete_L、建立单链表：头插法CreateList_H、尾插法Create_R
6.5 循环链表
概念：
- 头尾相连的链表
- 循环条件：p!=NULL、p->next!=NULL;
- 时间复杂度O(1)
操作：循环链表合并
6.6 双向链表
- 结构：prior、data、next
- 双向链表：双向循环链表
- 双向循环链表操作：插入ListInsert_Dul、删除ListDelete_Dul
七 顺序表和链表的比较
- 单链表、循环链表、双向链表比较
- 顺序链表和链表比较
八 线性表的应用-合并
- 线性表的合并union
- 有序表的合并-顺序表实现MergeList_Sq
- 有序表的合并-链表实现MergeList_L
九 案例分析与实现
- 一元多项式的运算-相加
- 稀疏多项式运算
- 图书管理系统
十 图示
