数据结构 线性表.ppt

第三章(第一部分)线性表杨震北京邮电大学计算机科学与技术学院幕五褒逆吸倍透杆皱涪悯炽恬嘲丛裁毫椎超兢浆传瑟荣团疏谐熔伐卑恿纱数据结构线性表数据结构线性表提纲线性表定义1向量(顺序表):在数据元素的非空有限集中数据元素间是线性关系,数据元素在表中的位置只取决于其序号存在唯一的一个被称作“第一个”的数据元素和唯一的一个被称作“最后一个”的数据元素除第一个外,每个数据元素均只有一个前驱;除最后一个外,每个数据元素均只有一个后继形式定义:由n(n0)个数据元素组成的有序序列。Linear_list=(D,S)其中:D={ai|aiD0,i=0,1,,n-1n0}R={N}N={<ai-1,ai>|ai-1,aiD0,i=1,2,,n-1}D0为某个数据对象或者简记为:(a0,a1,…,ai,…an-1)n0(n为表长。当n=0,称为空表)(顺序表)bb+cb+(i-1)cb+(n-1)cb+(max-1)ca0a1aian-1空闲c个存储单元起始地址为b、最多可容纳max个元素的向量隐宗瑰藏境涂篷净凶夷粹例酒脯煞柒难径华棕佃通菊嚏预裤郡缺恰火涅汁数据结构线性表数据结构线性表BUPTSCST4BUPT向量的构造函数与析构函数tempate<typenameT>structVector{T*elem;\\T为数据元素的类型intsize;intcapacity;Vector(intn=0;Tconst&t=T()):elem(0),size(0),capacity(0){elem=(T*)malloc(n*sizeof(T));uninitialized_fill(elem,elem+n,t);size=capacity=n;}virtual~Vector(){free(elem);}}向量的基地址向量中实际元素个数向量能容纳的元素个数桑孝默揍欠沽樟呻颂焚因纪员始携闯雄驴外轨策喘虾苟疚鼎吐昏汤蠢箩陨数据结构线性表数据结构线性表BUPTSCST5BUPT向量的判空与求长度template<typenameT>structVector{boolempty(void)const{returnsize==0;}intsize(void)const { returnsize; }郸爬咏饼钙挪筒溯秩湛爪滤结惹泅矫吾版王溅帘蚜楔坝侍骏呜哩醛壮塑烤数据结构线性表数据结构线性表BUPTSCST6BUPT向量迭代子template<typenameT>structVector{ typedefT*Iterator; Iteratorbegin(void) { returnelem; } Iteratorend(void) { returnelem+size; }返回向量首元素地址返回向量尾元素的下一个地址地址膊隶幅驭瞅宇公晒狮苇呕劝壶递原眷涎很牲俱凭瞩腾蚁洛袍夜想呛细泻儿数据结构线性表数据结构线性表BUPTSCST7BUPT获取向量成员Template<typenameT>StructVector{ T&front(void) { returnelem[0]; } T&back(void) { returnelem[szie-1]; } T&operator[](inti) {//前提条件:0<=i<=size; returnelem[i]; }取向量首元素取向量尾元素取向量第i个元素猫便选柔苔堑笺萝齿繁晴昭屯材藩踊叮累飘仕瘩禹酥抿邪栋颤界狄置侄嫩数据结构线性表数据结构线性表BUPTSCST8BUPT向量元素的删除Template<typenameT>StrcutVector{ voidpop_back(void) { size--; } voiderase(Iteratorpos) { memmove(pos,pos+1,sizeof(T)*(elem+--size-pos)); }a0a1aiai+1…………an-2an-1a0a1ai+1…………an-1C语言的标准库函数督布拣缠足叉熏驯妆洽斟覆兽氓都敏交誓牟汽撤防再裕穗鹃氏松绸绒荆吴数据结构线性表数据结构线性表BUPTSCST9BUPTvoid*memmove(void*dest,void*source,size_tcount)  {      void*ret=dest;     if(dest<=source||dest>=(source+count))      {