[工学]02 第2章 线性表.ppt

第二章 线性表 数据结构电子教案 第二章 线性表 2.1 线性表 2.2 顺序表 2.3 单链表 2.4 多项式 2.5 循环链表 2.6 双向链表 2.1 线性表 (Linear List) 线性表的定义 线性表是 n (≥0) 个数据元素的有限序列，记作 （a1, a2, …, an） ai 是表中数据元素，n 称为表长。 n=0表示空表。 线性表的抽象基类 template class T 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 T* getData(int i) const = 0; //取值 virtual void setData(int i, T x) = 0; //赋值 virtual bool Insert(int i, T x) = 0; //插入 virtual bool Remove(int i, T 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 LinearListToperator= (LinearListT L) = 0; //复制 }; 2.2 顺序表 (Sequential List) 1 顺序表的定义 用一组地址连续的存储单元存放线性表中的元素 可利用一维数组描述存储结构 元素地址计算方法： LOC(ai)=LOC(a1)+(i-1)*L LOC(ai+1)=LOC(ai)+L 其中： L——一个元素占用的存储单元个数 LOC(ai)——线性表第i个元素的地址 2 顺序表的静态存储和动态存储 #define maxSize 100 typedef int T; typedef struct { T data[maxSize]; //顺序表的静态存储表示 int n; } SeqList; typedef int T; typedef struct { T *data; //顺序表的动态存储表示 int maxSize, n; } SeqList; 3 顺序表(SeqList)类的定义 const int defaultSize = 100; template class T class SeqList: public LinearListT { protected: T *data; //存放数组 int maxSize; //最大可容纳表项的项数 int n; //当前已存表项数，即表长 void reSize(int newSize); //改变数组空间大小 public: SeqList(int sz = defaultSize); //构造函数 SeqList(SeqListT L); //复制构造函数 ～SeqList() {delete[ ] data;} //析构函数 int Size() const {return maxSize;} //求表最大容量 int Length() const {return n;} //计算表长度 int Search(T x) const; //有哪些信誉好的足球投注网站x在表中位置，函数返回表项序号 int Locate(int i) c