文档介绍：《数据结构》 一元多项式的表示及相加2-3中国科大《数据结构》线性结构分类?直接访问型( direct access )?顺序访问型(sequential access) ?目录索引型(directory access) 2-4中国科大《数据结构》线性结构分类2-5中国科大《数据结构》 线性表的逻辑结构?定义:线性表(Linear List)是由n个数据元素的有限序列组成。其中数据元素的个数n 定义为表的长度。当n=0 时称为空表,常常将非空的线性表(n>0)记作:(a1,a2,…an)这里的数据元素ai(1≤i≤n)只是一个抽象的符号,其具体含义在不同的情况下可以不同。?性质:线性表(N , r):a)结点集N中有唯一的开始结点,它没有前驱,但有唯一的后继;b)有限集N它存在唯一的终止结点,该结点有唯一的前驱而没有后继;c)其它的结点皆称为内部结点,每一个内部结点既有一个唯一的前驱,也有一个唯一的后继;d)线性表所包含的结点个数称为线性表的长度,长度为0的线性表称为空表;e)线性表的关系r,简称前驱关系,应具有反对称性和传递性。2-6中国科大《数据结构》、26个英文字母组成的字母表(A,B,C、…、Z) 是一个线性表,其中的元素是单个字母字符。例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况,可以用线性表的形式给出:(6,17,28,50,92,188)更为复杂的线性表中,一个数据元素可以有若干个数据项(item)组成。在这种情况下,长把数据元素称为记录(record),含有大量记录的线性表又称为文件(file)。2-7中国科大《数据结构》…………………………、学生健康情况登记表如下表。表中每一个学生的情况为一个记录,它由姓名、学号、性别、年龄和班级等5个数据项组成。2-8中国科大《数据结构》,都满足线性表的性质。?线性表是一种典型的线性结构。?数据的运算是定义在逻辑结构上的,而运算的具体实现则是在存储结构上进行的。?抽象数据类型的定义为:P192-9中国科大《数据结构》线性表类模板template<class ELEM> class list //线性表类模板list,模板参数ELEM{//1. 线性表的取值类型://元素的类型为ELEM,是本list类模板的模板参数ELEM。//本线性表用的最大长度为Max_length;//2. 名字空间,使用变量访问线性表的方法://用curr ++或curr--控制线性表游标curr的前后游走。//用公共变量curr_len指示线性表的尾部,//并导出表的当前长度,…等。// 3. 运算集:请参看下面的成员函数private://私有变量,线性表的存储空间//Max_length线性表的最大长度public:intcurr_len; //线性表的当前长度intcurr; //线性表的当前指针list();// 创建一个空的新线性表~list(); //从计算机存储空间删去整个线性表//将该线性表的全部元素清除,成为空表void clear() ;// 尾附算子,在表的尾部添加一个新元素,参//数value作为元素内容(数据类型为//ELEM),表的长度加1void append(ELEM value) ;//插入算子,整数i指出第i号位置,参数value//作为元素内容(数据类型为T),该位置上//插入一个新结点,表的长度加1。第i号位置后//的元素后移void insert(int i, ELEM value) ;//删除算子,删去第i号元素,表的长度减1,其后元素前移void remove(int i);//读取,返回第i个元素的值ELEM fetch(int i); }2-10中国科大《数据结构》?-1 利用两个线性表LA和LB分别表示两个集合A和B,现要求一个新的集合A=A∪B。1.[初值]获取线性表LA和LB2.[合并线性表]对于LB中的每一个元素x做如下操作:若(x不属于LA)则将x插入到LA的末尾3.[算法结束]void union(List &La,List Lb) {La_len = Listlength(La);L