顺序表的插入资料.ppt

《顺序表的插入资料.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、顺序表的插入线性表的特点为简单起见，假定表中元素的数据类型相同线性表中，结点和结点间的关系是一对一的有序表和无序表线性表的存储方式顺序存储方式——顺序表链表存储方式——链表a1a2a3a4a5a62§2.2顺序表顺序表可用一维数组实现LOC(i)=LOC(i-1)+l=α+i*l3顺序表的定义将线性表中的元素相继存放在一个连续的存储空间中顺序表的特点各表项的逻辑顺序与物理顺序一致对各个表项可以顺序访问，也可以随机访问4结点的变体（异质数据）若想在线性表中存放不同类型的数据，可采用等价定义union：typedefunion{intval;//

2、按data.val引用charch;//按data.ch引用floatdir;//按data.dir引用uniondata*link;//按data.link引用}data;//整体上是同一类型data25‘s’3.36274‘t’1.0‘6’5顺序表(SeqList)类的定义#include//定义在“seqList.h”中#include#include“linearList.h"constintdefaultSize=100;templateclassSeqList:publi

3、cLinearList{protected:E*data;//存放数组intmaxSize;//最大可容纳表项的项数intlast;//当前已存表项的最后位置voidreSize(intnewSize);//改变数组空间大小6public:SeqList(intsz=defaultSize);//构造函数SeqList(SeqList&L);//复制构造函数～SeqList(){delete[]data;}//析构函数intSize()const{returnmaxSize;}//求表最大容量intLength()const{re

4、turnlast+1;}//计算表长度intSearch(E&x)const;//搜索x在表中位置，函数返回表项序号intLocate(inti)const;//定位第i个表项，函数返回表项序号boolgetData(inti,E&x)const;//取第i个表项的值boolInsert(inti,Ex);//插入boolRemove(inti,E&x);//删除};7顺序表的构造函数#include//操作“exit”存放在此#include“seqList.h”//操作实现放在“seqList.cpp”template

5、SeqList::SeqList(intsz){if(sz>0){maxSize=sz;last=-1;data=newE[maxSize];//创建表存储数组if(data==NULL){//动态分配失败cerr<<"存储分配错误！"<SeqList::SeqList(SeqList&L){maxSize=L.Size();last=L.Length()-1;Evalue;data=newE[maxSize];//创建存储数组if(dat

6、a==NULL)//动态分配失败{cerr<<"存储分配错误！"<intSeqList::Search(E&x)const{//在表中顺序搜索与给定值x匹配的表项，找到则//函数返回该表项是第几个元素，否则函数返回0for(inti=0;i<=last;i++)//顺序搜索if(data[i]==x)re

7、turni+1;//表项序号和表项位置差1return0;//搜索失败};10顺序表的搜索（查找）x=48x=5011顺序查找数据的时间代价（比较次数分析）搜索成功：表项i的查找概率pi，比较次数ci若搜索概率pi相等，则平均比较次数搜索不成功：数据比较n次ACN(AverageComparingNumber)(假设表的长度为n,即n=last+1)12顺序表的插入13表项的插入算法templateboolSeqList::Insert(inti,Ex){//将新元素x插入到表中第i(1≤i≤last+2)个表项位//置

8、。if(last==maxSize-1)returnfalse;//表满if(i<1

9、

10、i>last+2)returnfalse;//参数i不合理for(intj=