主讲人：岑鹏瑞 包胡斯楞 丁学东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); //建立空顺序表，申请存储空间 void prt_ sq_LList() //顺序输出顺序表中的元素与顺

序表长 度 int flag_ sq_LList() //检测顺序表的状态 void ins_ sq_LList(int,T); //在表的指定元素前插入新元素 void del sq_LList(int); //在表中删除指定元素 };

//建立空顺序表 template<class T> sq_LList(T): :sq_LList(int m) {mm=m; //存储空间容量 v=new T[mm]; //动态申请存储空间 nn=0; //顺序表长度为0,即建立空顺序表 return; } //顺序输出顺序表中的元素与顺序表长度 template<class T> void sq_Llist<T>::prt_ sq_LList() {int i; cout<<”nn=”<<nn<<end1; for(i=0;i<nn;i++)cout<<v[i]<<end1; return; } //检测顺序表的状态 template<class T> int sq_Llist<T>::flag_ sq_LList() {if(nn==mm) return(-1); //存储空间已满，返回-1 if(nn==0) return(0); //顺序表为空，返回0 return(1) //正常返回1 }

//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; }

//在表的指定元素前插入新元素 template<class T> void sq_Llist<T>::ins_ sq_LList(int i,T b) {int k; if (nn==mm) //存储空间已满，上溢错误 {count<<”overflow”<<end1;return;} if (i>nn) i=nn+1; //默认在最后1个元素之后插入 if (i<1) i=1; //默认在第一个元素之前插入 for (k=nn;k>=i;k--) v[k]=v[k-1]; //从最后一个元素直到第i个元素 均 后移一个位置 v[i-1]=b; //插入新元素 nn=nn+1; //顺序表长度加1 return; }

//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; //插入新元素

//在顺序表中删除指定元素 template<class T> void sq_Llist<T>::del_ sq_LList(int i) {int k; if (nn==0) //顺序表为空，下溢错误 {count<<”underflow!”<<end1;return;} if ((i<1)||(i>nn)) //顺序表中没有这个元素 {cour <<”not this element in the list”<<end1; return; } for(k=I;k<nn;k++) v[k-1]=v[k]; //从第i个元素直到最后一 个元素均前移一个位置 nn=nn-1; //顺序表长度减1 return; }

//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; }

例2.7建立容量为100的空顺序表，然后输出该空顺序表。在该顺序表中依次 在第0个元素前插入1.5、在第1个元素前插

入2.5以及在第4个元素前插入3.5, 再输出该顺序表。依次删除该顺序表中的第0个元素以及删除该顺序表中 的第1个元素，再输出该顺序表。 //ch2_4.cpp #include”sq_LList.h” int main() { sq_LList<double>s1(100); //建立容量为100的空顺序表对象s1 cout<<”第1次输出顺序表对象s1:”<<end1; 上述程序的运行结果如下： s1.prt_ sq_LList(); 第1次输出顺序表对象s1: s1.int_ sq_LList(0,1.5); //在第0个元素前插入1.5 nn=0 第1次输出顺序表对象s1: s1.int_ sq_LList(1,2.5); //在第1个元素前插入2.5 s1.int_ sq_LList(4,3.5); //在第4个元素前插入3.5 nn=3 2.5 cout<<”第2次输出顺序表s1:”<<end1; 1.5 s1.prt_ sq_LList(); 3.5 s1.del_ sq_LList(0); //删除顺序表s1中的第0个元素 not this element in the list! s1.del_ sq_LList(2); //删除顺序表s1中的第1个元素 //指删除顺序表s1中的第0个 cout<<”第3次输出顺序表对象s1:”<<end1; 元素 s1.prt_ sq_LList(); 第3次输出顺序表对象s1: return 0; nn=2 2.5 }3.5

在顺序表中插入新元素时，建议采用如下方法： if(s.flag_sq_LList()!=-1) s.ins_sq_LList(3,25); //顺序表 非满进行插入操作 else {上溢处理}在顺序表中删除一个元素时，建议采用如下方法： if(s.flag_sq_LList()!=0) s.del_sq_LList(3); //顺序表非 空进行删除工作 else {下溢处理}

栈及其应用

1.什么是栈主程序与子程序之间的调用关系MAIN SUB1 SUB2 SUB3 SUB4 …… …… …… …… …… CALLSUB1 CALLSUB2 CALLSUB3 CALLSUB4 …… A:…… B:…… C:…… D:…… …… …… …… …… …… ……

END

RETURN

RETURN

RETURN

RETURN

栈(stack)是限定在一端进行插入与删除的线性表。

允许插入与删除的一端称为栈顶，不允许插入与删

除的另一端称为栈底。 栈是按照“先进后出” (FILO—First In Last Out) 或“后进先出” (LIFO—Last In First Out)的原 则组织数据的，因此，栈也被称为“先进后出”表 或“后进先出”表。 栈具有记忆作用。 用指针top来指示栈顶的位置，用指针bottom指向栈 底。 往栈中插入一个元素称为入栈运算，从栈中删除一 个元素(即删除栈顶元素)称为退栈运算。