数据结构与算法第二章清华大学出版社赵玉兰

《数据结构与算法第二章清华大学出版社赵玉兰》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章基本数据结构2.1线性表2.2数组2.3字符串2.1线性表——ADT线性表线性表（LinearList）例126个大写英文字母组成的字母表（A，B，C，…，Z）例2某个学生宿舍学生姓名（“wan”，“li”，“zhao”，“ye”，“hao”，“jia”）例3学生信息情况登记表姓名学号性别年龄班级家庭住址陈燕060001女21计06内蒙古刘伟060002男21计06北京王树林060003男22计06山东………………2.1线性表——ADT线性表定义由n(n0)个性质相同的数据元素a1,a2,…,an组成的有限序列数据元素的个数n(n0)定义为表的长度，当n=0时称为空

2、表常常将非空的线性表（n>0）记作：L=(a1,a2,…,ai,…,an)注意：这里的数据元素ai(1in)只是一个抽象的符号，其具体含义在不同的情况下可以不同。2.1线性表——ADT线性表线性表的逻辑特征有限性：线性表中数据元素的个数是有穷的相同性：线性表中数据元素的类型是同一的顺序性有且仅有一个开始结点a1，它没有前趋，而仅有一个后继a2有且仅有一个终端结点an，它没有后继，而仅有一个前趋an-1其余的内部结点ai(2in-1)都有且仅有一个前趋ai-1和一个后继ai+1线性表的逻辑结构是一种典型的线性结构2.1线性表——ADT线性表抽象数据类型线性表的定义ADT

3、List{Data数据元素表size：数据元素的个数OperationConstructorProcess：创建空表ClearProcess：清空线性表IsEmptyProcess：判断线性表是否为空Output：若线性表为空，返回true，否则返回false2.1线性表——ADT线性表LengthProcess：求线性表中元素个数Output：返回线性表中元素个数GetElemInput：要取出的元素的位置Process：取出指定位置上的元素Output：返回取出的元素值LocateInput：要定位的元素Process：为指定元素定位Output：若线性表中有给定元素，返

4、回元素位置，否则返回-12.1线性表——ADT线性表InsertInput：被插入元素值及其位置Process：将给定元素插入指定位置DeleteInput：被删除元素的位置Process：若线性表中有给定元素，则删除它PriorInput：要求前驱的元素Process：求给定元素的直接前驱NextInput：要求后继的元素Process：求给定元素的直接后继}//List2.1线性表——ADT线性表例4假设利用线性表LA和LB分别表示两个集合A和B（线性表中的数据元素即为集合中的成员），现求一个新的集合A∩B，并用LA表示结果集合。voidIntersection(List

5、LA,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++;}}//Intersection2.1线性表——ADT线性表例5假设利用线性表LA和LB分别表示两个集合A和B（线性表中的数据元素即为集合中的成员），现求一个新的集合A∪B，并用LA表示结果集合。voidUnion(ListLA,ListLB){intn;for(inti=1;i<=LB.

6、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++;}}}//Intersection2.1线性表——线性表的顺序存储顺序表定义顺序存储的线性表把线性表的元素按逻辑顺序依次存放在一组地址连续的存储单元里存储要点用一段地址连续的存储单元依次存储线性表中的数据元素a1a2…ai-1ai…an2.1线性表——线性表的顺序存储例：（34,23,67,82）34236782存储空间的起始地址——

7、基地址用什么属性来描述顺序表？顺序表的容量（最大长度）顺序表的当前长度42.1线性表——线性表的顺序存储存储结构与逻辑结构的关系存储地址内存状态线性表中的位序LOC(a1)a11LOC(a1)+ma22…LOC(a1)+(i-1)maii…LOC(a1)+(n-1)mann空闲顺序表存储结构示意图LOC(ai)=LOC(a1)+(i-1)×m基地址LOC(ai)=LOC(ai-1)+m一个数据元素所占存储量顺序表是一种随机存取的存储结构2.1线性表——线性表的顺序存储注意线性表的第i个元素ai存储在