《数据结构》课件1第2章 线性表.pptx

第2章 线性表线性表的逻辑结构线性表的顺序表示和实现线性表的链式表示和实现顺序表和链表的比较线性表的应用 2.1 线性表的逻辑结构2线性表是由类型相同的数据元素组成的有限序列。线性表的数据元素可以是数字、字符或更复杂的信息。英语字母表：(’a’, ’b’, ’c’, ’d’,……, ’x’, ’y’, ’z’)一个人的一年的月收入：(5000,5200,4890,4890, ……, 5300)学生成绩表： 2.1 线性表的逻辑结构3? 线性表的定义 二元组表示? 逻辑关系图 2.1 线性表的逻辑结构4? 线性表的抽象数据类型定义GetElem(i, e)初始条件：线性表已存在，1≤i≤length。操作结果：用e返回第i个元素的值。SetElem(i, e)初始条件：线性表已存在，1≤i≤length。操作结果：将线性表的第i个位置的元素赋值为e。Search(e)初始条件：线性表已存在。操作结果：在线性表中查找值为e的元素，若查找成功，返回其所在的位置，否则返回0。Insert(i, e)初始条件：线性表已存在，1≤i≤ength+1。操作结果：在线性表的第i个元素前插入元素e，线性表长度加1。Delete(i, e)初始条件：线性表已存在，1≤i≤length。操作结果：删除线性表的第i个元素，并用e返回其值，线性表长度减1。} 2.2 线性表的顺序表示和实现1. 线性表的顺序存储结构——顺序表5? 2.2 线性表的顺序表示和实现2. 顺序表的实现6template typename Tclass SqList{private: int maxsize; //顺序表可能达到的最大长度 int length; //顺序表的长度 T *elem; //存储空间的基地址public: SqList(int size=DEFAULT_SIZE); //构造函数，DEFAULT_SIZE为符号常量 SqList(T a[], int n); //构造函数 SqList(SqListT sl); //复制构造函数 ~SqList(); //析构函数 int Length(); //求顺序表长度 bool Empty(); //判断表是否为空 void Clear(); //清空顺序表 void PrintList(); //输出表中的各个元素 bool GetElem(int i, T e); //获取指定位置的元素值 bool SetElem(int i, T e); //设置指定位置的元素值 int Search(T e); //查找元素 bool Insert(int i, T e); //插入元素 bool Delete(int i, T e); //删除元素};类模板定义 2.2 线性表的顺序表示和实现2. 顺序表的实现7基本操作//求顺序表的长度template typename Tint SqListT::Length(){ return length;}//判断顺序表是否为空template typename Tbool SqListT::Empty(){ if (length==0) return true; else return false;}//清空顺序表template typename Tvoid SqListT::Clear(){ length=0;}//读取元素的值template typename Tbool SqListT::GetElem(int i, T e){ if (i1 || ilength) return false; e=elem[i-1]; return true;}//设置元素的值template typename Tbool SqListT::SetElem(int i, T e){ if (i1 || ilength) return false; elem[i-1]=e; return true;}//查找操作template typename Tint SqListT::Search(T e){ int i; for (i=0; ilength; i++) if (e==elem[i]) return i+1; return 0;} 2.2 线性表的顺序表示和实现2. 顺序表的实现8插入操作template typename Tbool SqListT::Insert(int i, T e){ if (length==maxsize)