基本操作:任一数据结构均有一组相应的基本操作, 有时操作不同,用途迥异(如栈和队列) 常用的基本操作有插入、删除、查找、 更新、排序等 算法:算法是为了解决给定的问题而规定的一个 有限长的操作步骤序列,则重于解决问题 的方法和步骤。当算法由计算机语言表示 时称为程序(代码) 算法设计目标:可维护性 可靠性(正确性、健壮行) 可读性 高效率(时间、空间) 2021222
2021/2/22 6 基本操作：任一数据结构均有一组相应的基本操作， 有时操作不同，用途迥异（如栈和队列） 常用的基本操作有插入、 删除、查找、 更新、排序等 算 法：算法是为了解决给定的问题而规定的一个 有限长的操作步骤序列，则重于解决问题 的方法和步骤。当算法由计算机语言表示 时称为程序（代码） 算法设计目标：可维护性 可靠性（正确性、健壮行） 可读性 高效率（时间、空间）
第二章线性表 2。1线性表的逻辑结构 定义:由相同种类的数据元素组成的一个有穷 序列称为一个线性表。“一个跟着一个” 符号表示法:L=(e,e2,en) 图形表示法: e e2 n 2021222
2021/2/22 7 第二章 线性表 2。1 线性表的逻辑结构 定义：由相同种类的数据元素组成的一个有穷 序列称为一个线性表。“一个跟着一个” 符号表示法：L＝（e1,e2,…en） 图形表示法： e1 e2 en
其中:ei—表示线性表L的第i个数据元素 表示线性表L的表长(n>=0) n=0时的线性表称为空表 ei1称为ei的前驱,ei+称为ei的后继 线性表的基本操作 (1)初始化(置空表)—可由构造函数实现 (2)求表长( Length (3)查找或定位(Find) (4)插入( Insert) (5)删除( Remove) (6)排序(Sort) (7)判空( IsEmpty) 2021222
2021/2/22 8 其中： ei ---表示线性表 L 的第 i 个数据元素 n ---表示线性表 L 的表长（n>=0） n=0 时的线性表称为空表 ei-1 称为 ei 的前驱，ei+1 称为 ei 的后继 线性表的基本操作： （1）初始化（置空表）——可由构造函数实现 （2）求表长（ Length ） （3）查找或定位（ Find ） （4）插入（ Insert ） （5）删除（ Remove ） （6）排序（ Sort ） （7）判空（ IsEmpty）
2.2线性表的顺序存储结构 要实现在计算机内表示一个数据结构,要解决两 种信息的存贮问题 数据元素本身的存贮 数据元素之间关系的存贮 定义:利用内存物理结构上的邻接特点,实现线性表 的“一个跟着—个”这一序列关系的存贮方式, 称为线性表的顺序存贮结构,其上的线性表称 为顺序表。 顶序表的类定义:利用数组作为顺序表的存储结构, 它被封装在类的私有域中 2021222
2021/2/22 9 2.2 线性表的顺序存储结构 要实现在计算机内表示一个数据结构，要解决两 种信息的存贮问题： 数据元素本身的存贮 数据元素之间关系的存贮 定义：利用内存物理结构上的邻接特点，实现线性表 的“一个跟着一个”这一序列关系的存贮方式， 称为线性表的顺序存贮结构，其上的线性表称 为顺序表。 顺序表的类定义：利用数组作为顺序表的存储结构， 它被封装在类的私有域中
template <class Type> class seqlist i Publica Seqlist(int Maxsize=defaultsize) Seqlistoidelete[] data; I int Length( const return last+1; i int Find(type x)const int Insert(Type x, int i) int Remove(Type x int IsEmpty return last int Isfull( return last==MaxSize-1: Type Get( int i)return i <0 i>last? NULL: data[1]; Private Tpe*data;∥/用数组存放线性表顺序存贮结构 int maxsize;∥数组大小,但顺序表的长度为last+1 int last;}∥/last为表中最后元素的下标,last=1时表示空表 2021222
2021/2/22 10 template <class Type> class SeqList { Public: SeqList(int MaxSize=defaultSize); ~SeqList( ) {delete [ ] data;} int Length( ) const {return last+1;} int Find(Type & x) const; int Insert(Type & x,int i); int Remove(Type & x); int IsEmpty( ) {return last = = - 1;} int Isfull( ) {return last = =MaxSize – 1 ;} Type & Get( int i ) {return i <0 || i >last ? NULL : data[i];} Private: Type * data; // 用数组存放线性表——顺序存贮结构 int Maxsize; // 数组大小，但顺序表的长度为last+1 int last; }// last 为表中最后元素的下标，last=-1 时表示空表