《《数据结构》陈慧南 第02章》由会员分享，可在线阅读，更多相关《《数据结构》陈慧南 第02章（70页珍藏版）》请在金锄头文库上搜索。
1、南京邮电大学计算机学院陈慧南2006年9月 数据结构 DataStructuresinC 南京邮电大学计算机学院陈慧南2006年9月 第2章线性表 南京邮电大学计算机学院陈慧南2006年9月 2 1线性表ADT2 2线性表的顺序表示2 3线性表的链接表示2 4多项式的算术运算 南京邮电大学计算机学院陈慧南2006年9月 2 1线性表ADT 南京邮电大学计算机学院陈慧南2006年9月 线性表的定义线性表是n 0 个元素a0 a1 an 1的线性序列 记为 a0 a1 an 1 其中n是线性表中元素的个数 称为线性表的长度 n 0时称为空表 ai是表中下标为i的元素 i 0 1 n 1 称ai是a
2、i 1的直接前驱元素 ai 1是ai的直接后继元素 线性表是动态数据结构 它的表长可以改变 南京邮电大学计算机学院陈慧南2006年9月 线性表ADTADTLinearList 数据 0个或多个元素的线性序列 a0 a1 an 1 其最大允许长度为MaxListSize 运算 Create 创建一个空线性表 Destroy 撤消一个线性表 IsEmpty 若线性表空 则返回true 否则返回false Length 返回表中元素个数 南京邮电大学计算机学院陈慧南2006年9月 Find i x 在x中返回表中下标为i的元素ai 若不存在 则返回false 否则返回true Search x 若x
3、不在表中 则返回 1 否则返回x在表中的下标 Insert i x 在元素ai之后插入x 若i 1 则x插在第一个元素a0前 若插入成功 则返回true 否则返回false Delete i 删除元素ai 若删除成功 则返回true 否则返回false Update i x 将元素ai的值修改为x 若修改成功 则返回true 否则返回false Output out 把表送至输出流 插入x到表 a0 a1 an 1 南京邮电大学计算机学院陈慧南2006年9月 线性表类templateclassLinearList public virtualboolFind inti T 南京邮电大学计算机学
4、院陈慧南2006年9月 2 2线性表的顺序表示 南京邮电大学计算机学院陈慧南2006年9月 2 2 1顺序存储结构 顺序存储表示是用一组地址连续的存储单元依次存储线性表中元素 顺序表顺序表示的线性表称为顺序表 南京邮电大学计算机学院陈慧南2006年9月 地址计算公式若已知顺序表中每个元素占k个存储单元 第一个元素a0在计算机内存中的首地址是loc a0 则表中任意一个元素ai在内存中的存储地址loc ai 为loc ai loc a0 i k随机存取结构只要给定loc a0 和k 就可以确定线性表中任意一个元素的存储地址 换句话说 顺序表是一种随机存取结构 南京邮电大学计算机学院陈慧南2006
5、年9月 2 2 2顺序表类 顺序表类templateclassSeqList publicLinearList public 公有函数SeqList intmSize SeqList delete elements boolFind inti T 南京邮电大学计算机学院陈慧南2006年9月 private 私有数据intmaxLength 顺序表的最大长度T elements 动态一维数组的指针 南京邮电大学计算机学院陈慧南2006年9月 动态存储分配构造函数 构建一个空线性表templateSeqList SeqList intmSize maxLength mSize elements n
6、ewT maxLength n 0 南京邮电大学计算机学院陈慧南2006年9月 析构函数 撤消一个顺序表templateSeqList SeqList delete elements 南京邮电大学计算机学院陈慧南2006年9月 2 2 3线性表运算实现 搜索运算Find i x 查找下标为i的元素ai 在x中返回表中下标为i的元素ai 即表中第i 1个元素 如果不存在 则返回false 否则返回true x elements i 渐近时间复杂度 O 1 南京邮电大学计算机学院陈慧南2006年9月 templateboolSeqList Find inti T 南京邮电大学计算机学院陈慧南200
7、6年9月 插入运算Insert i x 在表中下标为i的元素ai后插入x 若i 1 则将新元素x插在最前面 若插入成功 返回true 南京邮电大学计算机学院陈慧南2006年9月 插入运算的平均时间复杂度分析 设顺序表长度为n 共有n 1个可插入元素的位置 并设在各位置处插入元素的概率是相等的 即Pi 1 n 1 在位置i i 1 0 n 1 后插入一个元素要移动n i 1个元素 南京邮电大学计算机学院陈慧南2006年9月 templateboolSeqList Insert inti Tx 在元素ai之后插入xif in 1 越界检查couti j elements j 1 elements
8、j elements i 1 x n returntrue 南京邮电大学计算机学院陈慧南2006年9月 删除运算Delete i 删除元素ai 南京邮电大学计算机学院陈慧南2006年9月 删除运算的平均时间复杂度分析 设顺序表长度为n 则删除元素ai i 0 n 1 要移动n i 1元素 若删除表中每个元素的概率是相等的 即Qi 1 n 南京邮电大学计算机学院陈慧南2006年9月 templateboolSeqList Delete inti 删除元素aiif n 下溢出检查coutn 1 cout OutOfBounds endl returnfalse 从前往后逐个前移元素for intj
9、 i 1 j n j elements j 1 elements j n returntrue 南京邮电大学计算机学院陈慧南2006年9月 voidmain intx 10 SeqListr 4 r Insert 1 x r Insert 1 x r Output cout 请复习C 理解这一函数 南京邮电大学计算机学院陈慧南2006年9月 线性表的顺序存储表示的优缺点优点 随机存取 存储空间利用率高 缺点 插入 删除效率低 必须按事先估计的最大元素个数分配连续的存储空间 难以临时扩大 南京邮电大学计算机学院陈慧南2006年9月 2 3线性表的链接表示 南京邮电大学计算机学院陈慧南2006年9
10、月 2 3 1单链表 链接存储表示单链表的结点结构单链表结构 南京邮电大学计算机学院陈慧南2006年9月 注意事项头指针first是指向单链表的头结点的指针最后一个结点的指针域为 地址值为0逻辑上相邻的元素在物理上不一定相邻不能出现 断链 现象 南京邮电大学计算机学院陈慧南2006年9月 结点类 include linearlist h templateclassSingleList 超前声明templateclassNode private Telement Node link friendclassSingleList 南京邮电大学计算机学院陈慧南2006年9月 单链表类templatec
11、lassSingleList publicLinearList public SingleList first NULL n 0 SingleList boolFind inti T 南京邮电大学计算机学院陈慧南2006年9月 private Node first 顺序表类SeqList 单链表类SingleList是抽象线性表类LinearList类的派生类 南京邮电大学计算机学院陈慧南2006年9月 构造函数SingleList first NULL n 0 析构函数templateSingleList SingleList Node p while first p first link
12、deletefirst first p 南京邮电大学计算机学院陈慧南2006年9月 搜索运算必须从头指针开始沿链逐个计数查找 称为顺序查找搜索运算的平均 最坏的渐近时间复杂度 O n 南京邮电大学计算机学院陈慧南2006年9月 templateboolSingleList Find inti T 南京邮电大学计算机学院陈慧南2006年9月 插入运算修改两个指针域的值插入渐近时间复杂度 O 1 q link p link p link q 南京邮电大学计算机学院陈慧南2006年9月 插入运算步骤 生成数据域为x的新结点 q指向新结点 从first开始找第i 1个结点 p指向该结点 将q插入p之后
13、 表长加1 南京邮电大学计算机学院陈慧南2006年9月 templateboolSingleList Insert inti Tx if in 1 cout q newNode q element x Node p first 找ai元素所在的结点pfor intj 0 jlink first i 2 南京邮电大学计算机学院陈慧南2006年9月 if i 1 q link p link 新结点q插在p之后p link q else q link first 新结点q插在头结点之前first q n returntrue 删除结点p是指删除指针变量p所指示的结点 p 南京邮电大学计算机学院陈慧南
14、2006年9月 单链表的删除只需修改一个指针 q link p link 但还需使用 deletep 语句回收结点占用的空间 南京邮电大学计算机学院陈慧南2006年9月 单链表的步骤从first开始找第i 1个结点 p指向该结点 q指向p之前驱结点 从单链表中删除p 释放p之空间 表长减1 南京邮电大学计算机学院陈慧南2006年9月 templateboolSingleList Delete inti if n coutn 1 cout p first q first for intj 0 jlink 南京邮电大学计算机学院陈慧南2006年9月 if i 0 first first link
15、删除头结点else p q link q link p link deletep n returntrue 南京邮电大学计算机学院陈慧南2006年9月 单链表运算的优缺点优点单链表插入和删除只需修改一两个指针 无需移动元素 如已知前驱结点 插入删除运算的时间为O 1 可以动态分配结点空间 线性表的长度只受内存大小限制 缺点查找运算费时 只能顺序查找 不能随机查找 南京邮电大学计算机学院陈慧南2006年9月 2 3 2带表头结点的单链表 请区分 表头结点 和 头结点 南京邮电大学计算机学院陈慧南2006年9月 templateHeaderList HeaderList Node first ne
16、wNode first link NULL n 0 南京邮电大学计算机学院陈慧南2006年9月 templateboolHeaderList Insert inti Tx if in 1 cout p first for intj 0 jlink Node q newNode q element x q link p link p link q n returntrue 南京邮电大学计算机学院陈慧南2006年9月 templateboolHeaderList Delete inti if n coutn 1 cout q first p for intj 0 jlink p q link q link p link deletep n returntrue 南京邮电大学计算机学院陈慧南2006年9月 2 3 3单循环链表 南京邮电大学计算机学院陈慧南2006年9月 2 3 4双向链表 南京邮电大学计算机学院陈慧南2006年9月 结点类templateclassDoubleList 超前声明templateclassDNode private Telement DNode lLink r
