DATA STRUCTURES 第2章线性表 线性表 顺序表 单链表 循环链表 双向链表 多项式 Department of Computer Science Technology, Nanjing University fall 2008
Department of Computer Science & Technology, Nanjing University fall 2008 DATA STRUCTURES 1 第2章 线性表 ◼线性表 ◼顺序表 ◼单链表 ◼循环链表 ◼双向链表 ◼多项式
DATA STRUCTURES 21线性表( Linear list 线性表的定义 g线性表是nC0)个数据元素的有限序列 19u29 a1是表中数据元素,n是表长度。 a原则上讲,线性表中表元素的数据类型可以不 相同。但采用的存储表示可能会对其有限制。 a为简单起见,假定各元素类型相同。 Department of Computer Science Technology, Nanjing University fall
Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES ◼ 线性表的定义 线性表是 n (≥0) 个数据元素的有限序列 （a1 , a2 , …, an） ai 是表中数据元素，n 是表长度。 原则上讲，线性表中表元素的数据类型可以不 相同。但采用的存储表示可能会对其有限制。 为简单起见，假定各元素类型相同。 2.1 线性表 (Linear List)
DATA STRUCTURES 线性表的特点 除第一个元素外,其他每一个元素有一个且 仅有一个直接前驱。 口除最后一个元素外,其他每一个元素有一个 且仅有一个直接后继。 →a2 直接前驱和直接后继描述了结点之间的逻辑关系 即邻接关系) Department of Computer Science Technology, Nanjing University fall
Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES 直接前驱和直接后继描述了结点之间的逻辑关系 （即邻接关系） a1 a2 a3 a4 a5 a6 ◼ 线性表的特点 除第一个元素外，其他每一个元素有一个且 仅有一个直接前驱。 除最后一个元素外，其他每一个元素有一个 且仅有一个直接后继
DATA STRUCTURES 线性表的抽象基类(ADT) template <class t, class e> class linearlist i public Linearlisto 1构造函数 w Linearlisto: 析构函数 virtual int size0 const=0,/求表最大体积 virtual int Length0 const=0;求表长度 virtual int search(Tx) const=0;搜索 virtual int locate(inti) const=0;定位 virtual E* getData(inti) const=0;/取值 Ⅵ irtual void setdata(inti,Ex)=0;∥赋值 Department of Computer Science Technology, Nanjing University fall
Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES 线性表的抽象基类(ADT) template <class T, class E> class LinearList { public: LinearList(); //构造函数 ～LinearList(); //析构函数 virtual int Size() const = 0; //求表最大体积 virtual int Length() const = 0; //求表长度 virtual int Search(T x) const = 0; //搜索 virtual int Locate(int i) const = 0; //定位 virtual E* getData(int i) const = 0; //取值 virtual void setData(int i, E x) = 0; //赋值
DATA STRUCTURES virtual bool Insert(int i,E x)=0 1插入 irtual bool remove(inti,E&x)=0;/删除 virtual bool Isempty0 const=0;判表空 virtual bool s fu0 const=0;判表满 virtual void Sorto=0 排序 virtual void input=0 入 virtual void output=0 i 出 virtual linearlist<t, e>operator= Linearlist'<T,E>&L=0,/复制 Department of Computer Science Technology, Nanjing University fall
Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES virtual bool Insert(int i, E x) = 0; //插入 virtual bool Remove(int i, E& x) = 0; //删除 virtual bool IsEmpty() const = 0; //判表空 virtual bool IsFull() const = 0; //判表满 virtual void Sort() = 0； //排序 virtual void input() = 0； //输入 virtual void output() = 0； //输出 virtual LinearList<T, E>operator= (LinearList<T, E>& L) = 0; //复制 };