第二章 线性表及其顺序存储结构.ppt

数据结构 第二章 线性表及其顺序存储结构 第二章 知 识 点 线性数据结构的基本特征和基本运算 线性表的顺序存储结构 线性数据结构的简单应用 难 点 利用本章的基本知识，设计有效的算法，解决与线性相关的应用问题 线性表 要 求 熟练掌握以下内容： 线性表的基本运算 了解以下内容： 线性表运算时间复杂性分析 第二章 目录 2.1 线性表的基本概念 2.2 栈及其应用 2.5 队列及其应用 2.6 字符串 小 结 习题与练习 2.1.1 线性表的基本概念 线性表 是n个(n≥0)同类型数据元素的有限序列。 数据元素之间具有线性逻辑关系。 “线性” 体现在前后件关系上，记作： (a1，a2，…，an) 特点： 有且仅有一个根元素，它无前件； 有且仅有一个终端元素，它无后件； 除根元素外，每个元素只有一个前件； 除尾元素外，每个元素只有一个后件。 n＝0的线性表为空表。 线性表实例 英文字母表： (A，B，C，D，…，X，Y，Z) 某校1998-2003年计算机数量： (50，100，250，300，500，1200) 学生信息表： 线性表的基本运算 设：L-表，i-位序，x-数据元素 Length(L) //求表的长度 Get(1，i ) //在位置i处取出一个元素 Modify(L，i) //修改表L中位置i处的元素值 Delete(L，i) //删除表L中位置i处的元素 Insert(L，i，x) //在表L中位置i处插入元素x Sort(L，key) //对表L中所有元素按照key排序 Index(L，x) //求表L中元素x所在的位置 复杂运算： 线性表的合并 2.1.2 线性表的顺序存储结构 顺序存储结构(Sequential Mapping) 用内存中一组地址连续的单元，依次存放表中元素。每个元素的存储空间大小相同。 计算元素 ai 的地址 假设每个元素占k个字节，首元素的地址为ADR(a1)，则有: 顺序存储结构是一种随机存取结构。 在高级语言环境中，常用一维数组来存储线性表。 图： 顺序表 实现线性表 类模板 信息隐蔽、数据抽象、封装 template class T class sq_LList { public: sq_LList(){ m=n=0 } sq_LList( int ); int flag_sq_LList() const; bool Ins_sq_LList(int , T ,int ,T ); bool Del_sq_LList(int ) ; bool print_sq_LList() const; protected: int m , n ; T *v; //容量、长度、首指针 }; 建立一个容量为m的空顺序表 C++ 描述（使用函数模板） using namespace std; template class T void init_sq_LList( T *v , int m , int n) { v = new T[m]; // 动态申请存储空间 n = 0; // 顺序表长度为0。 } 2.1.3 线性表的运算 插入 删除 1.数据元素的插入(insert) 插入算法（新元素插入到位置 i 之后） 边界情况处理 若存储空间满，判为“上溢”，不能插入，返回false； 若 i = n-1 时，插到表尾元素之后； 若 i 0 时，插到首元素之前。 将尾元素至i+1元素逐一向后移动一个位置。 将新元素插入到第i＋1的位置上，并将顺序表长度增加1，返回true。 顺序表的插入(C++描述) template class T bool sq_LListT :: ins_sq_LList( int i, T x ) { if (n == m ) { coutOverFlowendl; retrun false; } if ( i 0 ) i = 0; if ( i n-1 ) i = n; for ( int j = n-1; ji; j-- )