数据结构与算法线性表.

1物料管理LILST1DataStructuresandAlgorithms:List·线性表的定义及ADT·线性表的顺序存储结构·线性表的链接存储结构·单向循环链表·双链表、双向循环链表·一元多项式的加法目录第二章线性表2物料管理LILST2DataStructuresandAlgorithms:List1、线性表的定义及ADT1、线性结构的定义：空或者只有一个结点。或者1、存在唯一的一个被称之为”第一个“的结点。2、存在唯一的一个被称之为”最后一个“的结点。3、除第一个结点之外，每个结点均只有一个前驱结点。4、除最后一个结点之外，每个结点均只有一个后继结点。分为以下几大类：·线性表：进通过它们之间的相对位置，确定它们之间的相互关系的线性结构。e.g:序列：a1、a2、a3…………………an-1、an·分类表·时间有序表·频率有序表·序列2、结点或数据元素：结点（数据元素）：由多个数据项构成，每个数据项表示该结点的某种性质。如：学生登记表中的每个学生结点，由学号、姓名、性别、系别……等构成。存放在外存中的结点通常称之为记录。3物料管理LILST3DataStructuresandAlgorithms:List1、线性表的定义及ADT3、线形表List的ADTADT2.1:线性表List的ADTElement:{xi|xiElemSet,i=1,2,3,……n,n0}或Φ;ElemSet为结点集合。Relation:{xi,xi+1|xi,xi+1ElemSet,i=1,2,3,……n-1},x1为首结点，xn为尾结点。Operations:Constructor前提:无或指定List的规模。结果:分配相应空间及初始化。Clear前提:无。结果：删除表List中的所有结点并进行初始化。IsEmpty前提：无结果：表List为空返回True，否则返回False。IsFull前提：无结果：表List为满返回True，否则返回False。4物料管理LILST4DataStructuresandAlgorithms:List1、线性表的定义及ADT3、线形表List的ADTLength前提：无结果：返回表List中的结点个数。Get前提：表List非空且已知结点序号无结果：返回相应结点的数据值。Prior前提：表List非空，已知结点序号且该结点非首结点。结果：返回其直接前驱结点的序号。Next前提：表List非空，已知结点序号且该结点非尾结点结果：返回其直接后继结点的序号。Find前提：表List非空，已知结点的数据值。结果：查找成功，返回相应结点序号，否则返回查找失败标志Insert前提：已知待插入的数据值以及插入位置。结果：插入具有该数据值的结点，表List的结点个数增大1。Delete前提：表List非空，已知被删结点的数据值。结果：首先查找相应结点，查找成功则删除该结点，表List的结点个数将减少1。否则返回删除失败标志。5物料管理LILST5DataStructuresandAlgorithms:List2、线性表的顺序存储结构1、物理存储位置的计算：·顺序表示：在物理位置上紧靠在一起。如用数组表示线性表。·设第一个结点的存储地址为LOC(a0),余类推。设每个结点占用L个单元。则：an－1ai-1a1a0aiLOC(ai)=LOC(ai-1)+L=LOC(ai-2)+2L=LOC(ai-i)+i*L=LOC(a0)+i*L·随机存取：访问任何一个数据元素或结点花费同样多时间。6物料管理LILST6DataStructuresandAlgorithms:List2、线性表的顺序存储结构templateclassElemTypeclassSeqList{private:ElemType*elem;//顺序表存储数组，存放实际的数据结点。intlength;//顺序表中的结点个数，亦称表的长度。intMaxSize;//顺序表的的最大可能的长度。public:SeqList(intInitSize);//构造函数~SeqList();//析构函数voidClear();//清空顺序表boolIsEmpty()const{return(length==0);}//表为空返回TRUE,否则返回FALSE。boolIsFull()const{return(length==MaxSize)};//表是否已经满，满则返回TRUE，否则FALSE。intLength()const;//表的长度ElemTypeGet(inti)const;//返回第i个结点的值intNext(inti)const;//若第i个结点的直接后继结点存在，返回其下标，//否则返回0intPrior(inti)const;//若第i个结点的直接前驱结点存在，返回其下标，//否则返回0intFind(ElemTypee);//返回值等于e的结点的序号，无则返回07物料管理LILST7DataStructuresandAlgorithms:List2、线性表的顺序存储结构templateclassElemTypeclassSeqList{………………….intFind(ElemTypee);//返回值等于e的结点的序号，无则返回0intInsert(inti,constElemType&e);//在第i个位置上插入新的结点（值为e），并//使原来的第i个结点至最后一个结点的序号依次加1。//插入成功返回1，否则为0intDelete(ElemType&e,inti);//若第i个结点存在，删除并将其值放入e,//若i非法，则删除失败，返回0。};注意：本处惯例，0号单元不用。Length既是顺序表的当前结点个数，同时又是尾结点的指针。8物料管理LILST8DataStructuresandAlgorithms:List2、线性表的顺序存储结构2、主要函数的实现·顺序表的创建：templateclassElemTypeSeqListElemType::SeqList(intInitSize){//构造函数if(InitSize0){elem=newElemType[InitSize];//申请连续空间，返回空间首地址。Exception(!elem,”thereisnospaceinmemory”)//若申请空间失败，则程序中断。length=0;MaxSize=InitSize-1;}}251247998936length9物料管理LILST9DataStructuresandAlgorithms:List2、线性表的顺序存储结构·查找及其分析：成功查找的情况templateclassElemTypeintSeqListElemType::Find(ElemTypee){//按照下标从大到小顺序查找值为e的数组结点的下标并将其返回。//elem[0]做哨兵用,保证即使查找失败，也可以在哨兵位上能找到值e。elem[0]=e;inti=length;//初始位置为尾结点所在下标while(elem[i]!=e)i--;//不等时继续向前比较，找到返回结点下标，否则返回0。returni;}成功查找时的平均比较次数：等概率情况,n为表中结点数∑(n-i+1)/n=(n+1)/2时间复杂性为O(n)。i=n12、主要函数的实现251247998936length10物料管理LILST10DataStructuresandAlgorithms:List2、线性表的顺序存储结构3、插入和删除的时间复杂性分析：·插入（插如之后成为第i个结点，注意从第1个结点开始）：124789361401234567899插入·如图99插入之后成为第3个结点，移动5－（3－1）次。在一般情况下，插入之后成为第i个结点，移动n-(i-1)=n-i+1次。templateclassElemTypeintSeqListElemType::Insert(inti,constElemType&e){//在位置i上插入一个值为e的结点，原来的第i个结点变为第//i+1个结点，其余后继结点序号同样加1，插入成功返回1。Exception((i1)||(ilength+1),”iisnotcorrect.”);//插入位置i不合法Exception(MaxSize==length,”nospacefornewitem.”);//存储空间已经满了，无法插入。//从尾结点起到第i个结点逐个向后移动一个位置for(intj=length;j=i;j--)elem[j+1]=elem[j];elem[i]=e;//将要插入的结点值放入第i个结点的位置length++;//顺序表结点个数加1return1;//插入成功返回1}lengtht11物料管理LILST11DataStructuresandAlgorithms:List2、线性表的顺序存储结构3、插入和删除的时间复杂性分析：124789361401234567812479989361499插入124789361412478936141247893614·插入（插如之后成为第i个结点，注意从第1个结点开始）：·如图99插入之后成为第3个结点，移动5－（3－1）次。在一般情况下，插入之后成为第i个结点，移动n-(i-1)=n-i+1次。12物料管理LILST12DataStructuresandAlgorithms:List2、线性表的顺序存储结构3、插入和删除的时间复杂性分析：·插入后成为第3个结点，移动5－（3－1）次。在一般情况下，插入后成为第i个结点，移动n-i+1)次插入后成为第1个结点，移动n次插入后成为第i个结点，移动n-i+1次插入后成为第n个结点，移动1次。插入后成为第n＋1个结点，移动0次。总共n+1种情况·在长度为n的线性表中插入一个结点的平均次数为：∑(n-i+1)/(n+1)=n/2时间复杂性为O(n)。i=1n+113物料管理LILST13DataStructuresandAlgorithms:List2、线性表的顺序存储结构3、插入和删除的时间复杂性分析：·删除：1247893614012345678·如图结点的数据值为89的结点删除将移动5－3次。在一般情况下，删除第i个结点，移动n-1次。templateclassElemTypeintSeqListElemType::Delete(ElemType&e,inti){//若第i个结点存在，删除并将其值放入e,若i非法，删除失败。Exception((i1)||(ilength),”iisillgeal.”);e=elem[i];//将第i个结点值首先读出，用于返回。for(intj=i;jlength;j++)elem[j]=elem[j+1];//第i+1个结点到尾结点逐个前移。length--;//表长度减1。returni;//返回成功标志i。}length删除8914物料管理LILST14DataStructuresandAlgorithms:List2、线性表的顺序存储结构3、插入和删除的时间复杂性分析：·删除（删除线性表的第i个结点）：1247893614012345678124736141247361412473614删除15物料管理LILST15DataStructuresandAlgorithms:List2、线性表的顺序存储结构3、插入和删除的时间复杂性分析：·删除第3个结点，移动5-3次。在一般情况下，删除第i个结点，移动n-i次删除第1个结点，移动n-1次删除第i个结点，移动n-i次删除第n个结点，移动0次。总共n种情况·在长度为n的线性表中删除一个结点的平均次数为：∑(n-i)/n=(n-1)/2时间复杂性为O(n)。i=1n·另外，通过数据场之值x查找结点，代价O(n)。查找第i个结点，代价O(1)。16物料管理LILST16DataStructuresandAlgorith