数据结构 线性表

线性结构的定义：,如果一个数据元素序列满足：（1）除第一个和最后一个数据元素外，每个数据元素只有一个前驱数据元素和一个后继数据元素；（2）第一个数据元素没有前驱数据元素；（3）最后一个数据元素没有后继数据元素。则称这样的数据结构为线性结构。,简言之，线性结构反映结点间的逻辑关系是的。,线性结构包括：线性表、堆栈、队列、字符串、数组等，其中最典型、最常用的是-,线性表,一对一(1:1),第2章线性表,2.1线性表2.2顺序表2.3单链表2.4循环单链表2.5双向链表2.6仿真链表,2.1线性表,2.1.1线性表的定义,线性表是一种可以在任意位置进行插入和删除数据元素操作的、由n（n0）个相同类型数据元素a0,a1,a2,.,an-1组成的线性结构。,（a0,a1,ai-1，ai,ai1，,an-1）,线性表的逻辑结构：,n=0时称为,数据元素,线性起点,ai的直接前趋,ai的直接后继,下标，是元素的序号，表示元素在表中的位置,n为元素总个数，即表长。n0,空表,线性终点,用符号（）表示,（A,B,C,D,Z）,例2分析学生情况登记表是什么结构。,分析：数据元素都是同类型（记录），元素间关系是线性的。,注意：同一线性表中的元素必定具有相同特性！,例1分析26个英文字母组成的英文表是什么结构。,分析：数据元素都是同类型（字母），元素间关系是线性的。,数据集合线性表的数据元素集合可以表示为序列a0,a1,a2,.,an-1，每个数据元素的数据类型可以是任意的类类型。操作集合（1）求当前数据元素个数getSize()（2）插入数据元素insert(i,obj)（3）删除数据元素delete(i)（4）取数据元素getData(i)（5）线性表是否空isEmpty(),2.1.2线性表抽象数据类型,在线性表的第i个数据元素前插入数据元素obj。,删除线性表的第i个数据元素。,线性表抽象数据类型的接口定义如下：,interfaceListvoidinsert(inti,Objectobj);/插入Objectdelete(inti);/删除ObjectgetData(inti);/取数据元素intgetSize();/求元素个数boolisEmpty();,2.2.1顺序表,2.2顺序表,用一组地址连续的存储单元依次存储线性表的各个数据元素。即采用顺序存储结构的线性表。它通常采用数组实现数据元素的存储。,注意：在C#中数组的下标是从0开始，即：listArrayn的有效范围是从listArray0listArrayn-1,(1)逻辑上相邻的数据元素，其物理上也相邻；(2)若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组的下标）。,设首元素a0的存放地址为LOC(a0)（称为首地址），设每个数据元素占用L个存储空间，则表中任一数据元素的存放地址为：LOC(ai+1)=LOC(ai)+LLOC(ai)=LOC(a0)+L*i,对上述公式的解释如图所示,线性表顺序存储特点：,地址内容元素在表中的位序,0,i,1,n-1,空闲区,i+1,L,b=LOC(a0),b+L,b+iL,b+(n-1)L,b+(maxSize-1)L,LOC(ai)=LOC(a0)+L*i,线性表的顺序存储结构示意图,设有一维数组，下标的范围是到，每个数组元素用相邻的个存储单元存储。设存储数组元素的首地址是8，则的地址是多少？,23,LOC(M3)=8+53=23,解：已知地址计算通式为：,LOC(ai)=LOC(a0)+L*i,例1,2.2.2顺序表类类包含成员变量和成员函数。,成员变量用来表示抽象数据类型中定义的数据集合,成员函数用来表示抽象数据类型中定义的操作集合,顺序表类实现接口List。顺序表类的public成员函数主要是接口List中定义的成员函数。,classSeqList:ListconstintdefaultSize=10;intmaxSize;intsize;ObjectlistArray;,publicSeqList()initiate(defaultSize);,publicSeqList(intsize)initiate(size);,存储数据元素的数组,数组中当前存储的数据元素的个数,构造函数,构造函数,privatevoidinitiate(intsz)maxSize=sz;size=0;listArray=newObjectsz;,确定maxSize的数值，初始化size的数值，为数组申请内存空间并使listArray等于（指向）所分配的内存空间。,publicvoidinsert(inti,Objectobj)if(size=maxSize)thrownewException(顺序表已满无法插入！);if(isize)thrownewException(参数错误！);for(intj=size;ji;j-)listArrayj=listArrayj-1;listArrayi=obj;size+;,插入步骤（1）把下标size-1至下标i中的数组元素依次后移；（2）把数据元素x插入到listArrayi中；（3）把当前数据元素个数size加1。,在线性表的第i个位置前插入一个元素的示意图如下：,插入25,i=5,28,28,28,28,30,30,30,30,42,42,42,42,77,77,77,77,25,publicObjectdelete(inti)if(size=0)thrownewException(顺序表已空无法删除！);if(isize-1)thrownewException(参数错误！);Objectit=listArrayi;for(intj=i;jsize-1;j+)listArrayj=listArrayj+1;size-;returnit;,删除步骤（1）把数据元素listArrayi存放到临时变量x中；（2）把下标i+1至下标size-1中的数组元素依次前移；（3）把当前数据元素个数size减1。,Objectit=listArrayi;for(intj=i;jsize-1;j+)listArrayj=listArrayj+1;size-;,删除顺序表中某个指定的元素的示意图如下：,publicObjectgetData(inti)if(i=size)thrownewException(参数错误！);returnlistArrayi;,publicintgetSize()returnsize;,publicboolisEmpty()returnsize=0;,读取数据元素,2.2.3顺序表的效率分析,算法时间主要耗费在移动元素的操作上，而移动元素的个数取决于插入或删除元素的位置.,思考：若插入在尾结点之后，则根本无需移动（特别快）；若插入在首结点之前，则表中元素全部要后移（特别慢）；应当考虑在各种位置插入（共n+1种可能）的平均移动次数才合理。,插入、删除成员函数时间效率分析:,推导：假定在每个元素位置上插入数据元素的可能性都一样（即概率P相同），则应当这样来计算平均移动次数：将所有位置的移动次数相加，然后取平均。若在a0前插入，需要移动的元素最多，后移n次；若在a1前面插入，要后移n-1个元素，后移次数为n-1;若在an-1前面插入，要后移1个元素；若在an-1之后插入，则后移0个元素；所有可能的元素移动次数合计：0+1+n=n(n+1)/2,故插入时的平均移动次数为：n(n+1)/2/（n+1）n/2O(n),共有多少种插入形式?连头带尾有n+1种!,同理可证：顺序表删除一元素的时间效率为:T（n)=(n-1)/2O(n),插入效率：,删除效率：,即插入、删除算法的平均时间复杂度为O(n),顺序表支持随机读取，因此，顺序表取数据元素的时间复杂度为O（1）。,例：建立一个线性表，首先依次输入数据元素1,2,3,10，然后删除数据元素5，最后依次显示当前线性表中的数据元素。(顺序表),classSeqListTeststaticvoidMain(stringargs)SeqListseqList=newSeqList(100);intn=10;tryfor(inti=0;in;i+)seqList.insert(i,i+1);seqList.delete(4);for(inti=0;iseqList.size();i+)Console.WriteLine(seqList.getData(i)+);catch(Exceptione)Console.WriteLine(e.Message);,1234678910,链式存储结构,本节小结,线性表顺序存储结构特点：逻辑