[新大纲]3线性表-Copy论述.pptx

第二部分 数据结构 主讲教师：王永波 ybwang@cumt.edu.cn 中国矿业大学环境与测绘学院 2017年4月11日 提纲 概述 线性表 栈与队 树与二叉树 图 查找 排序 二、线性表 1、线性表的逻辑结构 4 元素1 元素2 元素3 2、定义 定义 n（ ? 0）个数据元素的有限序列 存储结构 顺序表（向量），链表 特点 除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。 除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。 3、线性表的运算 基本运算 插入：在两个确定元素之间插入一个新元素 删除：删除线性表中某个元素 查找：按某种要求查找线性表中一个元素 排序：按给定要求对表中元素重新排序 4、顺序存储线性表 顺序存储结构/向量式存储结构 将线性表中的元素相继存放在 一个连续的存储空间中。 可利用一维数组描述存储结构 设：已知线性表中每个元素占l个单元，线性表内存首地址为：adr(a1)=b，则线性表中第i个元素的存储地址为 adr(ai)=adr(a1)+(i-1)l 4.1 顺序表类的定义 template class Type class CSeqList { //顺序表存储数组 Type *data; //最大允许长度 int MaxSize; //当前最后元素下标 int last; public: CSeqList ( int MaxSize = defaultSize ); ~CSeqList ( ) { delete [ ] data; } int Length ( ) const { return last+1; } // 查找 int Find ( Type x ) const; int Locate ( int i ) const; //定位 int Insert (int i, Type x); //插入 int Remove (int i); //删除 int Next ( Type x ) ; //后继 int Prior ( 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]; } } 8 4.1 顺序表（SeqList）类的定义 class CSeqList { //顺序表存储数组 int *data; //最大允许长度 int MaxSize; //当前最后元素下标 int last; public: CSeqList ( int MaxSize = defaultSize ); ~CSeqList ( ) { delete [ ] data; } int Length ( ) const { return last+1; } // 查找 int Find (int x ) const; int Locate (int i ) const; //定位 int Insert (int i, int x); //插入 int Remove (int i); //删除 int Next (int x ) ; //后继 int Prior (int x ) ; //前驱 int IsEmpty ( ) { return last ==-1; } int IsFull ( ) { return last == MaxSize-1; } int Get ( int i ) { //提取 return i 0 || i last？NULL : data[i]; } } 9 4.2 顺序存储结构的插入、删除 插入 线性表的插入是指在第i（1?i ? n+1）个元素之前插入一个新的数据元素x，使长度为n的线性表变成长度为n+1的线性表 操作：将第i至第n共（n-i+1)个元素后移 a1 a2 … ai-1 … an ai x 4.