《数据结构A第02 章陈 慧南课件》由会员分享，可在线阅读，更多相关《数据结构A第02 章陈 慧南课件（85页珍藏版）》请在金锄头文库上搜索。
1、南京邮电大学计算机学院 2007年1月,数据结构,Data Structures in C+,南京邮电大学计算机学院 2007年1月,第2章 线性表,南京邮电大学计算机学院 2007年1月,2.1 线性表ADT 2.2 线性表的顺序表示 2.3 线性表的链接表示 2.4 多项式的算术运算,南京邮电大学计算机学院 2007年1月,2.1 线性表ADT,南京邮电大学计算机学院 2007年1月,线性表的定义 线性表是n(0)个元素a0,a1,an-1 的线性序列，记为: (a0,a1,an-1)。其中n是线性表中元素的个数，称为线性表的长度；n=0时称为空表。 ai是表中下标为i的元素（i=0,1,
2、n-1），称ai是ai+1的直接前驱元素，ai+1是ai的直接后继元素。 线性表是动态数据结构，它的表长可以改变。,南京邮电大学计算机学院 2007年1月,线性表抽象数据类型（ADT ） ADT LinearList 数据： 0个或多个元素的线性序列（a0,a1,.,an-1），其最大允许长度为MaxListSize。 运算： Create()： 创建一个空线性表。 Destroy()：撤消一个线性表。 IsEmpty()：若线性表空返回true；否则返回false。 Length()： 返回表中元素个数。,南京邮电大学计算机学院 2007年1月,Find(i,x)：在x中返回表中下标为i的元
3、素ai。若不存在，则返回false，否则返回true。 Search(x)：若x不在表中，则返回-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)：把表送至输出流 ,南京邮电大学计算机学院 2007年1月,线性表的C+模板抽象类 template class LinearList
4、 public: virtual bool IsEmpty() const=0; virtual int Length() const=0; virtual bool Find(int i,T,南京邮电大学计算机学院 2007年1月,2.2 线性表的顺序表示,南京邮电大学计算机学院 2007年1月,2.2.1 顺序存储结构,顺序存储表示 是用一组地址连续的存储单元依次存储线性表中元素。 顺序表示的线性表称为顺序表。,南京邮电大学计算机学院 2007年1月,地址计算公式 若已知顺序表中每个元素占k个存储单元，第一个元素a0在计算机内存中的首地址是loc(a0)，则表中任意一个元素ai在内存中的存
5、储地址loc(ai)为 loc(ai)=loc(a0)+i*k 只要给定loc(a0)和k，就可以确定线性表中任意一个元素的存储地址，换句话说，顺序表是一种随机存取结构。,南京邮电大学计算机学院 2007年1月,程序2.1 线性表的C+类 template class LinearList public: virtual bool IsEmpty() const=0; virtual int Length() const=0; virtual bool Find(int i,T,2.2.2 顺序表类,南京邮电大学计算机学院 2007年1月,template class SeqList: pub
6、lic LinearList public: /公有成员函数 SeqList(int mSize); SeqList() Delete elements; ; bool IsEmpty() const; int Length() const; bool Find(int i,T,SeqList L(5);/定义一个顺序表对象,程序2.2 线性表的顺序表实现,南京邮电大学计算机学院 2007年1月,动态存储分配,template class SeqList: public LinearList public: SeqList(int mSize); private: int maxLength;
7、 /顺序表的最大长度 T *elements; /动态一维数组的指针 ;,顺序表在一维数组中的存储,南京邮电大学计算机学院 2007年1月,构造函数，构建一个空线性表 template SeqList:SeqList(int mSize) maxLength=mSize; elements=new TmaxLength; n=0; ,南京邮电大学计算机学院 2007年1月,析构函数，撤消一个顺序表 template SeqList: SeqList() delete elements; ,南京邮电大学计算机学院 2007年1月,2.2.3 线性表运算实现,查找下标为i的元素ai Find(i,
8、x): 在x中返回表中下标为i的元素ai (即表中 第i+1个元素)。如果不存在，则返回 false，否则返回true。,x=elementsi; 渐近时间复杂度：O(1),南京邮电大学计算机学院 2007年1月,template bool SeqList:Find(int i,T ,渐近时间复杂度：O(1),南京邮电大学计算机学院 2007年1月,插入运算 Insert(i,x)：在表中下标为i的元素ai后插入x。 若i=-1，则将新元素x插在最前面。 若插入成功，返回true；,南京邮电大学计算机学院 2007年1月,南京邮电大学计算机学院 2007年1月,插入运算的平均时间复杂度分析：
9、设顺序表长度为n，则在位置i（i=-1,0,.,n-1)后插入一个元素要移动n-i-1个元素。 设共有n+1个可插入元素的位置，并设在各位置处插入元素的概率是相等的，即Pi=1/(n+1) 。 则平均情况下在表中插入元素需要移动元素的个数为：,渐进时间复杂度：O(n),南京邮电大学计算机学院 2007年1月,template bool SeqList:Insert(int i,T x) /在元素ai之后插入x if (in-1) /越界检查 couti;j-) /从后往前逐个后移元素 elementsj+1=elementsj; elementsi+1=x; n+; return true;
10、,南京邮电大学计算机学院 2007年1月,删除运算 Delete(i)： 删除元素ai。,南京邮电大学计算机学院 2007年1月,南京邮电大学计算机学院 2007年1月,删除运算的平均时间复杂度分析: 设顺序表长度为n，则删除元素ai（i=0,n-1）,要移动n-i-1元素。 若删除表中每个元素的概率是相等的，即Qi=1/n。 则平均情况下从表中删除一个元素需要移动元素的个数为：,渐近时间复杂度：O(n),南京邮电大学计算机学院 2007年1月,template bool SeqList:Delete(int i) /删除元素ai if (!n) /下溢出检查 coutn-1) /越界检查 c
11、out“Out Of Bounds“endl; return false; for (int j=i+1;jn;j+) /从前往后逐个前移元素 elementsj-1=elementsj; n-; return true; ,南京邮电大学计算机学院 2007年1月,void main() int x=10; SeqList r(4); /定义一个有4个整型元素的顺序表对象 r.Insert(-1,x); r.Insert(-1,x); r.Output(cout); /? 请复习C+，理解这一函数 ,南京邮电大学计算机学院 2007年1月,顺序表的应用集合求“并”,两集合求并的算法思想是： 置
12、i=0； 若i小于集合LB的元素个数，则做，否则转； 取出集合LB中i位置的元素x； 若x不在集合LA中，则将其插入集合LA的最后位置； i+； 转继续 结束。,例2.1 求集合A和B的并A,分析：集合可以看成是线性表，用顺序表LA和LB分别表示集合A和B，“并”的结果放在LA中。,南京邮电大学计算机学院 2007年1月,用顺序表类SeqList实现集合“并”算法的程序，存入头文件seqlistu.h中。 #include “seqlist.h“ template void Union(SeqList /其插入集合LA中 ,南京邮电大学计算机学院 2007年1月,#include “seqli
13、stu.h“ const int SIZE=20; void main() SeqList LA(SIZE); /定义顺序表对象LA，表示集合A SeqList LB(SIZE); /定义顺序表对象LB，表示集合B for(int i=0;i5;i+) /插入元素04，构造集合LA=0,1,2,3,4 LA.Insert(i-1,i); for(i=5;i10;i+) /插入59，构造集合B=5,6,7,8,9 LB.Insert(i-6,i); LB.Insert(-1,0); /LB中插入0，LB=0,5,6,7,8,9 LB.Insert(3,2); /LB中插入2，LB=0,5,6,7
14、,2,8,9 LB.Insert(LB.Length()-1,4); /LB中插入4，LB=0,5,6,7,2,8,9,4 Union(LA, LB); /两集合合并，结果放入LA中 LA.Output(cout); /输出最终结果LA=0,1,2,3,4,5,6,7,8,9 ,南京邮电大学计算机学院 2007年1月,线性表的顺序存储表示的优缺点 优点： 随机存取； 存储空间利用率高。 缺点： 插入、删除效率低； 必须按事先估计的最大元素个数分配连续的存储空间，难以临时扩大。,南京邮电大学计算机学院 2007年1月,2.3 线性表的链接表示,南京邮电大学计算机学院 2007年1月,线性表的链接
15、存储表示法 （1）单链表 （2）带表头结点的链表 （3）循环链表 （4）双向链表,南京邮电大学计算机学院 2007年1月,2.3.1 单链表,单链表结构,单链表的结点结构,空单链表,南京邮电大学计算机学院 2007年1月,单链表在内存中的示意图,注意： 单链表头指针first不能少 最后一个结点的指针域为 逻辑上相邻的元素在物理上不一定相邻 不能出现“断链”现象,first,非空单链表,南京邮电大学计算机学院 2007年1月,类间关系 顺序表类SeqList、单链表类SingleList是抽象线性表类LinearList类的派生类。,LinearList,friend,SeqList,SingleList,Node,南京邮电大学计算机学院 2007年1月,单链表结点类 #include “linearlist.h“ template class SingleList； /超前声明 template class Node private: T element; Node *link; friend class SingleList; ;,南京邮电大学计算机学院 2007年1月,单链表类 template
