计算机软件技术基础第三版

主讲人：岑鹏瑞 包胡斯楞 丁学东2013年4月16日

数据结构分为两大类：线性结构与非线性结构

如果一个非空的数据结构满足下列两个条件： 1.有且只有一个根节点； 2.每一个节点最多有一个前件，也最多有一个后件。 则称该数据结构为线性结构(线性表)。 线性表是最简单，最常用的一种数据结构。

非空线性表有如下一些结构特征： 1.有且只有一个根节点a1,它无前件； 2.有且只有一个终端节点an,它无后件； 3.除根节点与终端节点外，其他所有节点有且只有一个 前件，也有且只有一个后件，线性表中节点的个数n 称为线性表的长度。当n=0时，称为空表。

线性表的顺序存储结构 线性表的顺序存储结构具有以下两个基本特点： 1.线性表中所有元素所占的存储空间是连续的； 2.线性表中各数据元素在存储空间中是按逻辑顺序依次存放 的； 线性表中第i个元素ai在计算机存储空间中的存储地址为： ADR(ai)=ADR(a1)+(i-1)k 即在顺序存储结构中，线性表中每一个数据元素在计算机 存储空间中的存储地址由该元素在线性表中的位置序号唯 一确定。 在程序设计语言中，通常定义一个一维数组来表示线 性表的顺序存储空间。 在实际应用中，可以根据线性表动态变化过程中的一 般规模来决定开辟的存储空间量。

建立一个容量为m的空线性表的顺序存储空间(即初 始化线性表的顺序存储空间)的C++描述如下： //ch2_1.cpp template<typename T> //模板声明，T为类型参 数 void init_sq_LList(T*v,int m,int*n) { v=new T[m]; //动态申请存储空间 *n=0; //线性表长度置0 return; } 当要释放线性表的顺序存储空间时，可以用“delete v;”。

线性表在顺序存储下的插入运算

假设线性表的存储空间为V(1:m),线性表的 长度为n,插入的位置为i(i表示在第i个元素之前插入), 插入的新元素b。则插入的过程如下： 首先处理以下三种异常情况： 1.当存储空间已满(即n=m)时为“上溢”错误，不 能进行插入，算法结束； 2.当i>n时，认为在最后一个元素之后(即第n+1个元 素之前)插入； 3. 当i<1时，认为在第1个元素之前插入。 然后从最后一个元素开始，直到第i个元素，其中每 一个元素均往后移动位置。 最后将新元素插入到第i个位置，并且将线性表的长 度增加1

线性表在顺序存储结构下插入算法的C++描述如下： //ch2_2.cpp #include<stdio.h> template<typename T> //模板声明，T为类型参数 void ins_sq_LList(T*V,int m,int*n,int i,T b) {int k; If (*n==m) //存储空间已满，上溢错误 {printf(“overflow!\n”);return;} If (i>*n)i=*n+1; //默认为在最后一个元素之后插入 If(i<1)i=1; //默认为在第一个元素之前插入 for (k=*n;k>=i;k--) V[k]=v[k-1]; /

/从最后一个元素开始，知道第i个元素均往后移动 一个位置 V[i-1]=b; //插入新元素 *n=*n+1; //线性表长度增加1 Return; } 由于C++中数组的下标识从0开始的，即C++数组中的第一个元素的下表为 0

线性表在顺序存储下的删除运算 例2.6如图a所示为一个长度为8的线性表顺序存储在长度为10的存储空 间中。现在要求删除线性表中的第1个元素。其删除过程如下： 从第2个元素开始直到最后一个元素，将其中的每一个元素均依次往前 移动一个位置，此时线性表的长度变成了7,如图b。 如果再要删除线性表中的第6个元素，则采用类似的方法：将第7个元 素往前移动一个位置。此时线性表的长度变成了6,如图c。

假设线性表的存储空间为V(1:m),线性表的长 度为n,删除的位置为i(表示删除第i个元素)。删除 过程如下： 首先处理一下两种异常情况： 1.当线性表为空时为下溢错误，不能进行删除，算法结 束。 2.当i<1或i>n时，认为在最后一个元素之后(即第n+1个 元素之前)删除。 然后从第i+1个元素开始，直到最后一个元素，其中每 一个元素均依次往前移动一个位置。 最后将线性表的长度减1.

线性表在顺序存储结构下删除算法的C++描述如下： //ch2_3.cpp #include<stdio.h> Template<class T> //模板声明，T为类型参数 Void del_sq_LList(T*v,int m,int*n,int i) {int k; If (*n==0) //线性表为空，下溢错误 {printf(“underflow!\n”;return;)} If((i<1)||(i>*n)) //线性表中没有这个元素 {printf(“not this element in the list!\n”); Return; } for (k=i;k<*n;k++) v[k-1]=v[k]; //从第i个元素开始，知道最 后一个元素均往前移动一个位置 *n=*n-1; //线性表长度减1 return; } 线性表的顺序存储结构对于小线性表或者其中元素不常变动的线 性表来说是合适的。

顺序表类前面对一个顺序表的插入与删除是通过调用插入 或删除函数来实现的，插入函数与删除函数是普通函 数，他们对说有的顺序表是公开的。在这种机制中， 任何用户都可以通过插入函数与删除函数对任意一个 顺序表进行插入或删除操作，这是一种面向过程的程 序设计方法。 利用C++支持面向对象的机制，通过类结构将顺 序表这种数据结构和一些常用的基本运算封装在一起。

下面的描述是将顺序表的数据和基本操作封装成 一个sq_LLst类： //sq_LList.h #include<iostream> using namespace std; template<class T> //模板声明，数据元素虚拟类型为T class sq_LList //顺序表类 {private; //数据成员 int mm; //存储空间容量 int nn; //顺序表长度 T*v; //顺序表存储空间首地址 public: //成员函数 sq_LList(){mm=0;nn=0;return;} sq_LList(int); //建立空顺序表，申请 …… 此处隐藏：3942字，全部文档内容请下载后查看。喜欢就下载吧 ……