资源描述：
《数据结构与算法_北京大学2008_张铭_线性表》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、数据结构与算法第2章线性表本章由赵海燕主写http://db.pku.edu.cn/mzhang/DS/http://www.jpk.pku.edu.cn/pkujpk/course/sjjg张铭，王腾蛟，赵海燕高等教育出版社，2008.6。“十一五”国家级规划教材主要内容线性结构顺序表链表线性表实现方法的比较线性结构元素间满足线性关系“一对一”的关系按此关系结构中的所有元素排成一个线性序列二元组B=(K,R),K={a0,a1,…,an-1},R={r}：结点集K中有一个唯一的开始结点，它没有前驱，但有一个唯一
2、的后继；对于有限集K,它存在一个唯一的终止结点，该结点有一个唯一的前驱而没有后继；其它的结点皆称为内部结点，每一个内部结点都有且仅有一个唯一的前驱，也有一个唯一的后继；a0,a1,…,an-1ai是ai+1的前驱，ai+1是ai的后继线性结构特点：均匀性：虽然不同线性表的数据元素可以是各种各样的，但对于同一线性表的各数据元素必定具有相同的数据类型和长度有序性：各数据元素在线性表中都有自己的位置，且数据元素之间的相对位置是线性的线性结构包括：简单的线性表栈队列散列表高级的广义表多维数组文件……线性
3、结构分类按访问方式划分直接访问型(directaccess)顺序访问型(sequentialaccess)目录索引型(directoryaccess)线性结构分类按操作划分线性表所有表目都是同一类型结点的线性表不限制操作形式根据存储的不同分为：顺序表，链表栈(LIFO,LastInFirstOut)插入和删除操作都限制在表的同一端进行队列(FIFO,FirstInFirstOut)插入操作在表的一端，删除操作在另一端2.1线性表(linearlist)三个方面线性表的逻辑结构线性表的存储结构线性表运算分类线性表的
4、逻辑结构线性表：由称为元素（element）的数据项组成的一种有限且有序的序列，这些元素也可称为结点或表目二元组(K,r)：由结点集K，以及定义在结点集K上的线性关系r所组成的线性结构线性表所包含的结点个数称为线性表的长度，它是线性表的一个重要参数；长度为0的线性表称为空表；线性表的关系r，简称前驱/后继关系，具有反对称性和传递性线性表逻辑结构主要属性包括：线性表的长度表头(head)表尾(tail)当前位置(currentposition)线性表的存储结构定长的一维数组结构又称为向量型的顺序存储结构变长的线性表
5、存储结构链接式存储结构串结构、动态数组、以及顺序文件线性表的存储结构顺序表按索引值从小到大存放在一片相邻的连续区域紧凑结构，存储密度为1链表单链表双链表循环链表………..线性表运算分类创建线性表的一个实例list(-)清除线性表（即析构函数）~list()获取有关当前线性表的信息访问线性表并改变线性表的内容或结构线性表的辅助性管理操作线性表的运算建立线性表清除线性表插入一个新元素删除某个元素修改某个元素排序检索线性表类模板templateclassList{voidclear();//置空线性表b
6、oolisEmpty();//线性表为空时，返回trueboolappend(constTvalue);//在表尾添加一个元素value，表的长度增1boolinsert(constintp,constTvalue);//在位置p上插入一个元素value，表的长度增1booldelete(constintp);//删除位置p上的元素，表的长度减1boolgetPos(int&p,constTvalue)//查找值为value的元素并返回其位置boolgetValue(constintp,T&value);//把位
7、置p的元素值返回到变量value中boolsetValue(constintp,constTvalue);//用value修改位置p的元素值boolgetPos(int&p,constTvalue);//把值为value的元素所在位置返回到变量p中};2.2顺序表（array-basedlist）采用定长的一维数组存储结构也称向量主要特性:元素的类型相同元素顺序地存储在连续存储空间中，每一个元素有唯一的索引值使用常数作为向量长度顺序表数组存储读写其元素很方便，通过下标即可指定位置只要确定了首地址，线性表中任意数据
8、元素都可以随机存取。地址计算如下所示：loc(ki)=loc(k0)+c*ic=sizeof(ELEM)顺序表逻辑地址(下标)数据元素存储地址数据元素0k0Loc(k0)k01k1Loc(k0)+ck1…………ikiLoc(k0)+i*cki……n-1kn-1Loc(k0)+(n-1)*ckn-1顺序表类定义classarrList:publicList{//顺序表
