第第2章章基本数据结构基本数据结构2.1线性表线性表2.2数组数组2.3字符串字符串22.1线性表线性表ADT线性表线性表线性表（线性表（LinearList）u例例126个大写英文字母组成的字母表个大写英文字母组成的字母表（A，B，C，Z）u例例2某个学生宿舍学生姓名某个学生宿舍学生姓名（“wan”，“li”，“zhao”，“ye”，“hao”，“jia”）u例例3学生信息情况登记表学生信息情况登记表姓姓名名学学号号性性别别年年龄龄班班级级家庭住址家庭住址陈陈燕燕060001女女21计计06内蒙古内蒙古刘刘伟伟060002男男21计计06北京北京王树林王树林060003男男22计计06山东山东32.1线性表线性表ADT线性表线性表定义定义u由由n(n 0)个性质相同的数据元素个性质相同的数据元素a1,a2,an组组成的成的有限序列有限序列u数据元素的个数数据元素的个数n(n 0)定义为表的长度，当定义为表的长度，当n=0时称为空表时称为空表u常常将非空的线性表（常常将非空的线性表（n0）记作：）记作：L=(a1,a2,ai,an)注意：这里的数据元素注意：这里的数据元素ai(1 i n)只是一个抽象只是一个抽象的符号，其具体含义在不同的情况下可以不同。的符号，其具体含义在不同的情况下可以不同。452.1线性表线性表ADT线性表线性表抽象数据类型线性表的定义抽象数据类型线性表的定义ADTListData数据元素表数据元素表size：数据元素的个数：数据元素的个数OperationConstructorProcess：创建空表：创建空表ClearProcess：清空线性表：清空线性表IsEmptyProcess：判断线性表是否为空：判断线性表是否为空Output：若线性表为空，返回：若线性表为空，返回true，否则返回，否则返回false62.1线性表线性表ADT线性表线性表LengthProcess：求线性表中元素个数：求线性表中元素个数Output：返回线性表中元素个数：返回线性表中元素个数GetElemInput：要取出的元素的位置：要取出的元素的位置Process：取出指定位置上的元素：取出指定位置上的元素Output：返回取出的元素值：返回取出的元素值LocateInput：要定位的元素：要定位的元素Process：为指定元素定位：为指定元素定位Output：若线性表中有给定元素，返回元素位置，否则：若线性表中有给定元素，返回元素位置，否则返回返回-172.1线性表线性表ADT线性表线性表InsertInput：被插入元素值及其位置：被插入元素值及其位置Process：将给定元素插入指定位置：将给定元素插入指定位置DeleteInput：被删除元素的位置：被删除元素的位置Process：若线性表中有给定元素，则删除它：若线性表中有给定元素，则删除它PriorInput：要求前驱的元素：要求前驱的元素Process：求给定元素的直接前驱：求给定元素的直接前驱NextInput：要求后继的元素：要求后继的元素Process：求给定元素的直接后继：求给定元素的直接后继/List82.1线性表线性表ADT线性表线性表例例4假设利用线性表假设利用线性表LA和和LB分别表示两个集合分别表示两个集合A和和B（线性表中的数据元素即为集合中的成员），现（线性表中的数据元素即为集合中的成员），现求一个新的集合求一个新的集合AB，并用，并用LA表示结果集合。表示结果集合。voidIntersection(ListLA,ListLB)inti=1;while(i=LA.size)x=LA.GetElem(i);/在在LA中取一元素中取一元素k=LB.Locate(x);/在在LB中搜索它中搜索它if(k=-1)/在在LB中未找到，则在中未找到，则在LA中删除它中删除它LA.Delete(i);LA.size-;elsei+;/Intersection92.1线性表线性表ADT线性表线性表例例5假设利用线性表假设利用线性表LA和和LB分别表示两个集合分别表示两个集合A和和B（线性表中的数据元素即为集合中的成员），现（线性表中的数据元素即为集合中的成员），现求一个新的集合求一个新的集合AB，并用，并用LA表示结果集合。表示结果集合。voidUnion(ListLA,ListLB)intn;for(inti=1;i=LB.size;i+)x=LB.GetElem(i);/在在LB中取一元素中取一元素k=LA.Locate(x);/在在LA中搜索它中搜索它if(k=-1)/在在LA中未找到，则在中未找到，则在LA中插入它中插入它n=LA.size;LA.Insert(n,i);LA.size+;/Intersection102.1线性表线性表线性表的顺序存储线性表的顺序存储顺序表顺序表定义定义u顺序存储的线性表顺序存储的线性表u把线性表的元素按逻辑顺序依次存放在一组地址把线性表的元素按逻辑顺序依次存放在一组地址连续的存储单元里连续的存储单元里存储要点存储要点用一段地址用一段地址连续连续的存储单元的存储单元依次依次存储线性表中的数据元素存储线性表中的数据元素a1a2ai-1aian112.1线性表线性表线性表的顺序存储线性表的顺序存储例：（例：（34,23,67,82）34236782存储空间的起始存储空间的起始地址地址基地址基地址用什么属性来描述顺序表？用什么属性来描述顺序表？顺序表的容量（最大长度）顺序表的容量（最大长度）顺序表的当前长度顺序表的当前长度4122.1线性表线性表线性表的顺序存储线性表的顺序存储存储结构与逻辑结构的关系存储结构与逻辑结构的关系 存储地址存储地址 内存状态内存状态线性表中线性表中的位序的位序LOC(a1)a11LOC(a1)+ma22LOC(a1)+(i-1) maiiLOC(a1)+(n-1) mann空闲空闲 顺序表存储结构示意图顺序表存储结构示意图LOC(ai)=LOC(a1)+(i-1)m基地址基地址LOC(ai)=LOC(ai-1)+m一个数据元素一个数据元素所占存储量所占存储量顺序表是一种顺序表是一种随机存取随机存取的存储结构的存储结构132.1线性表线性表线性表的顺序存储线性表的顺序存储u注意注意线性表的线性表的第第i个元素个元素ai存储在数组下标为存储在数组下标为i-1的位置的位置线性表的长度线性表的长度size与数组的长度与数组的长度MaxListSize是不同的是不同的lsize=n，大小可变，大小可变lMaxListSize是数组的长度，大小不变是数组的长度，大小不变lsize MaxListSize表的长度表的长度空闲空闲anaiai-1a2a1datan-1 MaxListSize-1sizeMaxListSizei-1i-210下标下标如何实现顺序表的内存分配？如何实现顺序表的内存分配？顺序表顺序表一维数组一维数组142.1线性表线性表线性表的顺序存储线性表的顺序存储constintMaxListSize=100;classSeqListDataTypedataMaxListSize;intsize;/元素的个数元素的个数public:List()size=0;/构造一个空线性表构造一个空线性表voidClear();/清空顺序表清空顺序表boolIsEmpty();/判断如果为空表，返回判断如果为空表，返回true，否则，否则返回返回falseDataTypeGetElem(intk)returndatak-1;/返回第返回第k个元素个元素intLocate(DataTypee);/返回第一个与元素返回第一个与元素e匹配的元素匹配的元素位序位序DataTypePrior(DataTypee);/返回元素返回元素e的前驱的前驱DataTypeNext(DataTypee);/返回元素返回元素e的后继的后继voidInsert(DataTypee,inti);/在表中第在表中第i个位置插入个位置插入eDataTypeDelete(inti);/删除第删除第i个元素，并返回其值个元素，并返回其值；/SeqList152.1线性表线性表线性表的顺序存储线性表的顺序存储基本操作在顺序表中的实现基本操作在顺序表中的实现定位操作定位操作算法算法2.4定位定位intLocate(DataTypee)inti=0;while(i=size)return-1;/没有找到没有找到elsereturni; /找到此元素，返回其下标找到此元素，返回其下标/Locate注意序号和下标之间的关系！注意序号和下标之间的关系！162.1线性表线性表线性表的顺序存储线性表的顺序存储定位成功定位成功定位不成功定位不成功e48e50172.1线性表线性表线性表的顺序存储线性表的顺序存储u定位算法的时间复杂度定位算法的时间复杂度基本操作：比较基本操作：比较成功时成功时l最好情况：最好情况：比较比较比较比较1 1次（次（次（次（i=0i=0），时间复杂度为），时间复杂度为），时间复杂度为），时间复杂度为O(1)O(1)l最坏情况：最坏情况：比较比较比较比较n n次（次（次（次（i=n-1i=n-1），时间复杂度为），时间复杂度为），时间复杂度为），时间复杂度为O(n)O(n)l l平均情况：设定位每个数据元素的概率相等，则平均情况：设定位每个数据元素的概率相等，则平均情况：设定位每个数据元素的概率相等，则平均情况：设定位每个数据元素的概率相等，则不成功时：比较不成功时：比较n次次182.1线性表线性表线性表的顺序存储线性表的顺序存储在在i=4处插入处插入下标下标数据数据元素元素012113221324456782528304277插入插入u在顺序表中的第在顺序表中的第i个位置上个位置上插入插入eai和和ai+1之间的逻辑之间的逻辑关系发生了变化关系发生了变化存储位置要反映这存储位置要反映这个变化个变化192.1线性表线性表线性表的顺序存储线性表的顺序存储算法算法2.2插入插入voidInsert(DataTypee,inti)if(isize|size=MaxListSize-1)exit;elsefor(j=size;ji;j-)dataj=dataj-1;datai=e;/插入成功插入成功size+;/Insert什么时候不能插入？什么时候不能插入？注意边界条件注意边界条件202.1线性表线性表线性表的顺序存储线性表的顺序存储u插入算法的时间复杂度插入算法的时间复杂度基本语句：移动元素基本语句：移动元素最好情况：不移动（最好情况：不移动（i=n），时间复杂度为），时间复杂度为O(1)最坏情况：移动最坏情况：移动n个元素（个元素（i=0），时间复杂度为），时间复杂度为O(n)平均情况：设插入每个数据元素的概率相等，则平均情况：设插入每个数据元素的概率相等，则212.1线性表线性表线性表的顺序存储线性表的顺序存储删除删除u删除顺序表中第删除顺序表中第i个位置上的元素个位置上的元素DataTypeDelete(inti)if(i=size)returnnulldata;/被删除的元素下标错被删除的元素下标错elsesize-;e=datai;for(intj=i;jnext=NULL);/判断是否判断是否为空链表为空链表DataTypePrior(DataTypee);/返回返回e的前驱结点元素的前驱结点元素DataTypeNext(DataTypee);/返回返回e的后继结点元素的后继结点元素voidInsert(DataTypex,inti);/在第在第i个结点之前插入元素个结点之前插入元素值为值为x的结点的结点DatatypeDelete(inti);/删除第删除第i个结点，并返回其元素值个结点，并返回其元素值voidClear();/清空链表清空链表;/nextList312.1线性表线性表线性表的链式存储线性表的链式存储u取元素取元素DataTypeGetElem(inti)if(head-next=NULL