青岛大学数据结构与算法——第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

九 案例分析与实现

• 一元多项式的运算-相加
• 稀疏多项式运算
• 图书管理系统

十 图示