第二章 线性表.pptx

1 第二章 线性表 数据结构电子教案 殷人昆 王宏 2 第二章 线性表 线性表 顺序表 单链表 多项式 循环链表 双向链表 3 线性表 (Linear List) 线性表的定义 线性表是 n (≥0) 个数据元素的有限序列，记作 （a0, a1, …, an-1） ai 是表中数据元素，n 是表长度。 一般而言，线性表中表元素的数据类型可以不同。但采用的存储表示可能会对其有限制。 为简单起见，假定各元素类型相同。 4 线性表的特点 除第一个元素外，其它每个元素有且仅有一个直接前驱。 除最后一个元素外，其它每个元素有且仅有一个直接后继。 直接前驱和直接后继描述了结点之间的逻辑关系（即邻接关系）。 5 线性表的抽象基类 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; //在表中搜索给定值x virtual int Locate(int i) const = 0; //定位第i个元素 virtual bool getData(int i, T x) const = 0; //取第i个表项的值 virtual void setData(int i, T x)= 0; //修改第i个表项的值 6 virtual bool Insert(int i, T x) = 0; //在第i个表项后插入x virtual bool Remove(int i, T x) = 0; //删除第i个表项 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; //赋值 }; //在基类中预留函数名，具体功能由派生类根据需要去定义 线性表的存储表示有两种：顺序存储方式和链表存储方式。 顺序表——用顺序存储方式（数组）实现的线性表 7 顺序表 (Sequential List) 顺序表的定义 将线性表中的元素相继存放在一片连续的存储空间中（线性表基于数组的存储表示） 可利用一维数组描述存储结构 顺序表的特点 所有元素的逻辑顺序与其物理存放顺序一致 即第i个表项存储于第i个物理位置 既可顺序访问, 也可随机访问 8 顺序表的静态存储和动态存储 #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; //C++的方式,便于动态扩充 9 顺序表(SeqList)类的定义- 1 #include iostream.h //定义在“seqList.h”中 #include stdlib.h #include LinearList.h const int defaultSize = 100; template class T class SeqList: public LinearListT {