第二章线性表 线性表 顺序表 单链表 线性表的物理实现 ·循环链表 双向链表单链表的变化形就 多项式链表的应用
1 第二章 线性表 线性表 顺序表 单链表 循环链表 双向链表 多项式 线性表的物理实现 单链表的变化形式 链表的应用
第二章线性表 §2.1线性表 定义 n(≥0)个表项的有限序列 u142…n a是表项,m是表长度。 第一个表项是表头,最后一个是表尾
2 第二章 线性表 §2.1 线性表 • 定义 n（ 0）个表项的有限序列 L =（a1 , a2 , …, an） – ai是表项，n是表长度。 – 第一个表项是表头，最后一个是表尾
线性表的特点 为简单起见,假定表中元素的数据类型 相同 线性表中,结点和结点间的关系是一对 的 有序表和无序表 线性表的存储方式 顺序存储方式—顺序表 链表存储方式—链表
• 线性表的特点 –为简单起见，假定表中元素的数据类型 相同 – 线性表中，结点和结点间的关系是一对 一的 – 有序表和无序表 • 线性表的存储方式 –顺序存储方式 —— 顺序表 – 链表存储方式 —— 链表 a1 a2 a3 a4 a5 a6 3
§22顺序表 顺序表可用一维数组实现 c i=0时 LoC (i LOC(i-1)+l,i>0时 0123456789 a35274918605477834102 乙* LOC (i)=LOC(i-1)+l=a+i*
§2.2 顺序表 顺序表可用一维数组实现 − + = = ( ) , 0 时 α , 0 时 ( ) LOC i l i i LOC i 1 LOC ( i ) = LOC ( i -1 ) + l =α+ i*l 4
顺序表的定义 将线性表中的元素相继存放在一个连续的存 储空间中 顺序表的特点 各表项的逻辑顺序与物理顺序一致 对各个表项可以顺序访问,也可以随机访问
顺序表的定义 - 将线性表中的元素相继存放在一个连续的存 储空间中 顺序表的特点 - 各表项的逻辑顺序与物理顺序一致 - 对各个表项可以顺序访问，也可以随机访问 5
结点的变体(异质数据) 25s33.36274“t1.0“6 若想在线性表中存放不同类型的数据,可采用等价 定义unon: typedef union int val: 按 data. va引用 char c h 按 data. ch引用 float dir. 按 data. diri引用 union data * link;/按data.ink引用 }data;/蹩体上是同一类型data
6 结点的变体（异质数据） • 若想在线性表中存放不同类型的数据，可采用等价 定义union： typedef union { int val; //按data.val引用 char ch; //按data.ch引用 float dir; //按data.dir引用 union data *link; //按data.link引用 } data; //整体上是同一类型data 25 ‘s’ 3.3 62 74 ‘t’ 1.0 ‘6’
顺序表( Senlis类的定义 #include ∥定义在“ seqlist. h”中 #include nclude“ linear list. h" const int defaultsize =100 template class e> class Seqlist: public linearlistse>& protected E *data /存放数组 int max Size:大可容纳表项的项数 int last ∥当前已存表项的最后位置 void resize( int newSize);/改变数组空间大小
7 顺序表(SeqList)类的定义 #include //定义在“seqList.h”中 #include #include “linearList.h" const int defaultSize = 100; template class SeqList: public LinearList { protected: E *data; //存放数组 int maxSize; //最大可容纳表项的项数 int last; //当前已存表项的最后位置 void reSize(int newSize); //改变数组空间大小
public Seqlist(int sz= defaultsize ) 构造函数 Seqlist(seqlist& l) ∥复制构造函数 Seqlisto deletel] data; ∥析构函数 int Size( const{ return max Size;}求表最大容量 int Length0 const{ return last-+l;}计算表长度 int Search(E& x)const ∥搜索在表中位置,函数返回表项序号 int Locate(int 1)const; ∥定位第1个表项,函数返回表项序号 bool getData(inti,E&x) const,/取第个表项的值 bool Insert(int i,E x) /插入 bool remove(int i, e& x) /删除
8 public: SeqList(int sz = defaultSize); //构造函数 SeqList(SeqList& L); //复制构造函数 ～SeqList() {delete[ ] data;} //析构函数 int Size() const {return maxSize;} //求表最大容量 int Length() const {return last+1;} //计算表长度 int Search(E& x) const; //搜索x在表中位置，函数返回表项序号 int Locate(int i) const; //定位第 i 个表项，函数返回表项序号 bool getData(int i, E& x) const; //取第i个表项的值 bool Insert(int i, E x); //插入 bool Remove(int i, E& x); //删除 };
顺序表的构造函数 include∥操作“exit”存放在此 # include" seqlist. h/操作实现放在 seqList. cpp? template Seqlist: Seqlist(int szi if(z>0){ maxSize=sz: last=-1 daa=newE[ maxsize];∥刨建表存储数组 if(data=NULL){∥2态分配失败 cerr<<"存储分配错误!"<<endl: eX
9 顺序表的构造函数 #include //操作“exit”存放在此 #include “seqList.h” //操作实现放在“seqList.cpp” template SeqList::SeqList(int sz) { if (sz > 0) { maxSize = sz; last = -1; data = new E[maxSize]; //创建表存储数组 if (data == NULL){ //动态分配失败 cerr << "存储分配错误！" << endl; exit(1); } } };
复制构造函数 template Seqlist: Seqlist( Seqlist&l)i maxSize=L Size; last=L. Length0-1 E value data=newE[ maxSize];1创建存储数组 if ( data== NULL) ∥励动态分配失败 {cerr<<"存储分配错误!"<<endl;exi(1);} for(inti=1;i<= last+1;计++)传送各个表项 (L getData(i, value); datai-1=value; 1
10 template SeqList::SeqList ( SeqList& L ) { maxSize = L.Size(); last = L.Length()-1; E value; data = new E[maxSize]; //创建存储数组 if (data == NULL) //动态分配失败 {cerr << "存储分配错误！" << endl; exit(1);} for (int i = 1; i <= last+1; i++) //传送各个表项 {L.getData(i, value); data[i-1] = value;} }; 复制构造函数