003数据描述 - 1.ppt

* * 数据描述 第三章 * * 引言 线性表 公式化描述 链式描述 间接寻址 模拟指针 本章内容 * * 公式化描述、链表、间接寻址（查找、插入、删除）。 箱子排序、基数排序。 本章重点 * * 数据不同的描述形式。 最常见的数据描述方法： 公式化描述 链接描述 间接寻址 模拟指针 3.1 引言-数据描述 * * 在公式化描述中，元素地址是由数学公式来确定的； 在链接描述中，元素地址分布在每一个表元素中； 在间接寻址方式下，元素地址则被收集在一张表中。 3.1 引言-数据描述 * * 实例形式为 (e1,e2,...en)，其中n 是有穷自然数。 ei 是表中的元素 e1是第一个元素，en是最后一个元素 n 是表的长度 当n=0 时，表为空 当n0时，el优先于e2，e2 优先于e3 除了这种优先关系之外，在线性表中不再有其他的结构 元素本身的结构与线性表的结构无关。 3.2 线性表 * * ? 创建一个线性表。 ? 确定线性表是否为空。 ? 确定线性表的长度。 ? 查找第k个元素。 ? 查找指定的元素。 ? 删除第k个元素。 ? 在第k个元素之后插入一个新元素。 线性表上的操作 抽象数据类型 ( Abstract Data Type— ADT) ADT 给出了实例及相关操作的描述 . 抽象数据类型说明独立于任何描述方法。抽象数据类型的描述方法必须满足抽象数据类型说明 * * * * 抽象数据类型LinearList{ 实例 0或多个元素的有序集合 操作 Create():创建一个空线性表 Destroy():删除表 IsEmpty():如果表为空则返回true，否则返回false Length():返回表的大小(即表中元素个数) Find(k,x):寻找表中第k个元素，并把它保存到x中；如果不存在，则返回false Search(x):返回元素x在表中的位置；如果x不在表中，则返回0 Delete(k,x):删除表中第k个元素，并把它保存到x中；函数返回修改后的线性表 Insert(k,x):在第k个元素之后插入x；函数返回修改后的线性表 Output(out):把线性表放入输出流out之中 } ADT 3-1 线性表的抽象数据类型描述 * * 公式化描述（Formula-based） 借助数学公式来确定元素表中的每个元素分别存储在何处（如存储器地址）。 链接描述（Linked list） 元素表中的每个元素可以存储在存储器的不同区域中 每个元素都包含一个指向下一个元素的指针。 间接寻址方式（Indirect addressing） 元素表中的每个元素也可以存储在存储器的不同区域中 元素地址则被收集在一张表中，该表的第i项指向元素表中的第i个元素，所以这张表是一个用来存储元素地址的表。 模拟指针（Simulated pointer） 类似于链接描述，区别在于它用整数代替了C++指针。 线性表的描述 * * 采用数组来表示一个对象的实例 .(数组存储/顺序存储) 实例中每个元素在数组中的位置用一个数学公式来指明。 一个典型的映射公式： location(i) = i–1 ?第i 个元素（如果存在的话）位于数组中i-1位置处 。 (5,2,4,8,1) 3.3 公式化描述 * * 线性表的顺序存储结构示意图 逻辑地址 数据元素 存储地址 数据元素 0 k0 Loc(k0) k0 1 k1 Loc(k0)+c k1 … … … … i ki Loc(k0)+i*c ki … … n-1 kn-1 Loc(k0)+(n-1)*c kn-1 * * templateclass T Class LinearList{ public: LinearList(int MaxListSize=10);//构造函数(Create) ~LinearList(){delete []element;}//析构函数(Destroy) bool IsEmpty()const{return length==0;} 复杂性 O(?) int Length()const{return length;} 复杂性 O(?) bool Find(int k,T x)const;//返回第k个元素至x中 int Search(const T x)const;//返回x所在位置 LinearListT Delete(int k,T x);//删除第k个元素并将它返回至x中 LinearListT Insert(int k,constT x);//在第k个元素之后插入x void Output(ostream out)const; private: int length; int MaxSize;