数据结构 2_线性表课件.ppt

第二章 线性表;2.1 线性表的类型定义;2.1 线性表的类型定义;2.1 线性表的类型定义;线性表的定义;线性结构的基本特征为:;线性表举例;*;*;*;*;*;Empty (L ) 前置条件：线性表已存在 输入：无 功能：判断线性表是否为空表 输出：若是空表，返回1；否则返回0 后置条件：线性表不变 Full (L ) 前置条件：线性表已存在 输入：无 功能：判断线性表是否为满 输出：若是表满，返回1；否则返回0 后置条件：线性表不变;Clear (L ) 前置条件：线性表已存在 输入：无 功能：将表清空 输出：无 后置条件：线性表变为空表 ListDisplay (L ) 前置条件：线性表已存在 输入：无 功能：按位置的先后次序输出线性表中的元素 输出：线性表的各个数据元素 后置条件：线性表不变 endADT;关于基本操作集;2.2 线性表的顺序存储及其实现;*; 0 … i-2 i-1 … n-1 Max-1 ;顺序表;*;*;构造函数的作用是初始化一个对象的成员变量。 构造函数的特点: 1. 构造函数必须与类名相同； 2. 必须声明为类的公有成员函数； 3. 不可以有返回值也不得指明返回类型； 4. 构造函数可以重载。;析构函数用于在一个对象被撤消时删除其成员变量，其标志是在类的名字前面加上“~”。 析构函数特点: 1.析构函数没有参数和返回值; 2.一个类只能有一个析构函数; 3. 析构函数不允许重载。 ;模板类示例;顺序表初始化;*;C++通过下列语句实现异常处理机制： throw——抛出一个异常，供try捕获； try——检测/捕获异常； catch——处理try所捕获的异常。;*;*; (a1, …, ai-1, ai, …, an) 改变为 (a1, …, ai-1, e, ai, …, an);算法2. 3 顺序表插入操作步骤 ;顺序表插入操作步骤;*;算法2. 3 顺序表插入; (a1, …, ai-1, ai, ai+1, …, an) 改变为 (a1, …, ai-1, ai+1, …, an);顺序表删除元素操作步骤;算法2.4;*;*;2.3 线性表的链式存储及其实现;*;*;*;*;void Insert(int i,T e)；//在表中第i个位置插入元素 T Delete(int i)；//删除表中第i个元素 T GetElem(int i)；//按位查找，获取第i个元素的值 int Locate(T e)；//在链表中查找值为e的元素 T prior(T e)；//返回元素e的前驱 int Empty()；//测表空 int Length()；//测表长 void CLear()；//清空表 void ListDisplay()；//遍历输出表元素 }；;基本操作实现举例与分析;*;*;*;续;ai-1;NodeT *s； s=new NodeT；s-data=e； s-next=p-next； p-next=s；// 结点S链接到p结点之后;算法2.9 单链表插入元素操作步骤;算法2.9 单链表插入元素类;续;ai-1;ai-1;算法2.10 单链表删除元素; ; 续;方法一： 头插法 头插法指每次将新申请的结点插在头结点的后面。;类C++语言描述： templateclass T void LinkListT：：CreateList(int n) {//头插法(逆位序)创建具有n个元素的线性表 for(int i=1；i=n；i++) { s=new NodeT；//新建元素结点 cins-data；//输入新建数据元素值 s-next=Head-next；//新结点插入头结点之后 head-next=s； } };尾插法指每次将新申请的结点插在尾结点的后面;templateclass T void LinkListT：：CreateList(int n) { //尾插法(正位序)创建具有n个元素的线性表 NodeT *p,*s；//设置工作指针，p指向尾结点 p=Head； for(int i=1；i=n；i++) { s=new NodeT；//新建元素结点 cins-data；//输入新建数据元素值 s-next=p-next；//新结点链入表尾