第二章 线性表 线性表 顺序表 单链表 线性表的物理实现 循环链表 双向链表 单链表的变化形式 多项式 链表的应用
1 第二章 线性表 线性表 顺序表 单链表 循环链表 双向链表 多项式 线性表的物理实现 单链表的变化形式 链表的应用
第二章 线性表 §2.1线性表 定义 n（≥0)个表项的有限序列 L=（a1,42,3am） -a是表项，n是表长度。 一第一个表项是表头，最后一个是表尾 2
2 第二章 线性表 §2.1 线性表 • 定义 n（ 0）个表项的有限序列 L =（a1 , a2 , …, an） – ai是表项，n是表长度。 – 第一个表项是表头，最后一个是表尾
线性表的特点 为简单起见，假定表中元素的数据类型 相同 线性表中，结点和结点间的关系是一对 一的 有序表和无序表 6 线性表的存储方式 顺序存储方式一 顺序表 链表存储方式一链表 3
• 线性表的特点 –为简单起见，假定表中元素的数据类型 相同 – 线性表中，结点和结点间的关系是一对 一的 – 有序表和无序表 • 线性表的存储方式 –顺序存储方式 —— 顺序表 – 链表存储方式 —— 链表 a1 a2 a3 a4 a5 a6 3
§2.2顺序表 顺序表可用一维数组实现 i 时 ,i>0时 2 5 7 8 9 35 27 4918 60 54 77 83 41 02 -i*l LOC(i)=LOC(i-1)+1=a+i* 4
§2.2 顺序表 顺序表可用一维数组实现 − + = = ( ) , 0 时 α , 0 时 ( ) LOC i l i i LOC i 1 LOC ( i ) = LOC ( i -1 ) + l =α+ i*l 4
顺序表的定义 -将线性表中的元素相继存放在一个连续的存 储空间中 顺序表的特点 -各表项的逻辑顺序与物理顺序一致 -对各个表项可以顺序访问，也可以随机访问 5
顺序表的定义 - 将线性表中的元素相继存放在一个连续的存 储空间中 顺序表的特点 - 各表项的逻辑顺序与物理顺序一致 - 对各个表项可以顺序访问，也可以随机访问 5
结点的变体（异质数据） 25 3.3 62 74 1.0 63 ·若想在线性表中存放不同类型的数据，可采用等价 定义union: typedef union int val; /按data.val引用 char ch; /按data.ch引用 float dir; 按data.dir引用 union data*link;/按data.link引用 data; /整体上是同一类型data 6
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’
顺序表(SeqList)类的定义 #include /定义在“seq List..h”中 #include #include "linearList.h" const int defaultSize 100; template class E> class SeqList:public LinearList protected; E *data; /存放数组 int maxSize; 川最大可容纳表项的项数 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 delete]data;} /析构函数 int Size()const {return maxSize;} 川求表最大容量 int Length()const {return last+1;} 计算表长度 int Search(E&x)const; /搜索X在表中位置，数返回表项序号 int Locate(int i)const; /定位第个表项，函数返回表项序号 bool getData(inti,E&x)const,:/取第i个表项的值 bool Insert(int i,E x); /插入 bool Remove(int i,E&x); /删除 }; 8
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 sz){ if (SZ>0 maxSize sz;last =-1; data new E[maxSizel; /创建表存储数组 if(data==NULL){∥动态分配失败 cerr<<"存储分配错误！"<<end; exit(1); }; 9
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) maxSize L.Size(;last L.Length()-1; E value; data new E[maxSize]; /创建存储数组 if (data ==NULL) 川动态分配失败 {cerr<<"存储分配错误！"<<end; exit(1); for(inti=l;i<=last+l;i++)/传送各个表项 L.getData(i,value);data[i-1]value; }; 10
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;} }; 复制构造函数