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

九 案例分析与实现

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

十 图示