第3章表结构

3.1数 据 结 构
3.1.1数据

数据就是指能够被计算机识别、存储和加工处理的信息的载体。数据元素是数据的基本单位，有时一个数据元素可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。如整数集合中，10这个数就可称为一个数据元素。又如在一个数据库(关系数据库)中，一个记录可称为一个数据元素，而这个元素中的某一字段就是一个数据项。
3.1.2数据类型
数据类型是一个值的集合以及在这些值上定义的一组操作的总称。
同一类数据的全体称为一个数据类型。在程序设计高级语言中，数据类型用来说明一个数据在数据分类中的归属。它是数据的一种属性。这个属性限定了该数据的变化范围。为了解题的需要，根据数据结构的种类，高级语言定义了一系列数据类型。不同的高级语言所定义的数据类型不尽相同。C++语言所定义的数据类型的种类如图31所示。



图31C++语言所定义的数据类型



其中，基本数据类型对应于简单的数据结构，非基本数据类型对应于复杂的数据结构。在复杂的数据结构中，允许成分数据本身具有复杂的数据结构，因而，非基本数据类型允许复合嵌套。指针类型对应于数据结构中成分数据之间的关系，表面上属基本数据类型，实际上都指向复杂的成分数据，即构造数据类型中的数据，因此这里没有把它划入基本数据类型，而是把它划入非基本数据类型。
3.1.3数据结构的定义
数据结构是在整个计算机科学与技术领域中被广泛使用的术语。它被用来反映一个数据的内部构成，即一个数据由哪些成分数据构成、以什么方式构成、呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系，物理上的数据结构反映成分数据在计算机内的存储安排。
数据结构是相互之间存在着一种或多种特定关系的数据元素的集合。数据结构的定义虽然没有标准，但是它包括逻辑结构、存储结构和数据操作三方面内容。
1. 逻辑结构




表31所示是一个班级学生成绩表，包括学生的学号、姓名、语文、数学、物理成绩等。这些形成了一个数据结构，它由很多记录(数据元素)组成，每个元素又由多个数据列(字段、数据项)组成。每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。分析数据结构都是从结点(其实也就是元素、记录、顶点，虽然在各种情况下所用名字不同，但说的是同一个东西)之间的关系来分析的，对于这个表中的任一个记录(结点)，它只有一个直接前趋，只有一个直接后继(前趋、后继就是前相邻、后相邻的意思)，整个表只有一个开始结点和一个终端结点。知道了这些关系就能明白这个表的逻辑结构，即逻辑结构就是数据元素之间的逻辑关系。


表31学生成绩表



学号姓名语文数学物理

021001王强879096
021002李一龙699189
021003张映月877971
021004何一端848868
……………

2. 存储结构
存储结构是指用计算机语言如何表示结点之间的这种关系，即数据的逻辑结构用计算机语言的实现。常用的数据存储结构有顺序存储方法、链式存储方法、索引存储方法和散列存储方法四种。
1) 顺序存储方法
例如将多个机器人分配到各个工位上，按工位号顺序分配机器人，机器人a1在一号工位、机器人a2在二号工位……。这种方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元中，结点间的逻辑关系由存储单元的邻接关系来体现，如图32所示。由此得到的存储表示称为顺序存储结构(sequential storage structure)，通常借助程序语言的数组描述。


图32顺序存储



顺序存储的优点是随机访问快，可以直接通过数据的地址访问; 缺点是插入、删除效率低，不利于动态增长。
该方法主要应用于线性的数据结构。非线性的数据结构也可通过某种线性化的方法实现顺序存储。
2) 链式存储方法
假设将多个机器人分配到各个工位上，机器人a1在一号工位同时知道机器人a2所在的工位号,机器人a2知道机器人a3的工位号……。这种分配方式，机器人的工位号不连续，只有找到第一个机器人才能找到后续一个机器人的工位号。该方法不要求逻辑上相邻的结点在物理位置上也相邻，结点间的逻辑关系由附加的指针字段表示，如图33所示。由此得到的存储表示称为链式存储结构(linked storage structure)，通常借助于程序语言的指针类型描述。


图33链式存储



链式存储的优点是便于插入、删除和动态增长; 缺点是不能直接得到相关数据的地址，随机访问慢，空间开销大，占用空间较多。
3) 索引存储方法
该方法通常在存储结点信息的同时，还建立附加的索引表。索引表由若干索引项组成，索引项的一般形式是： 

(关键字、地址)

关键字是能唯一标识一个结点的那些数据项。
若每个结点在索引表中都有一个索引项，则该索引表称为稠密索引(dense index)。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引(spare index)。稠密索引中索引项的地址指示结点所在的存储位置； 稀疏索引中索引项的地址指示一组结点的起始存储位置。
例如，对于下列结构City，将区号看成是关键字，其索引存储结构如图34所示。索引表由(区号，地址)组成，其中区号按递增次序排序。


图34City的索引存储结构



索引存储结构采用顺序和链式结合的方式，数据检索速度快，能够保证数据的唯一性。但这种存储结构创建索引和维护索引需要时间，索引也会占用一定的物理空间，对数据增、删、查、改的同时也要对索引进行维护。
4) 散列存储方法
例如有一组数据dat={1023, 1074, 1077}，通过分析发现，各个元素后两位是变化的，其他两位数不变。那么地址取值可以是23、74、77。
这种存储方法是一种在数据元素的存储位置与关键字之间建立确定对应关系的存储技术，又称Hash存储。该方法的基本思想是： 根据结点的关键字通过一定的函数关系计算出该结点的存储地址。上面的例子中，能够对1023、1074、1077进行处理得到地址23、74、77的函数即为散列函数，又称为哈希(Hash函数)。这种存储结构利用数据的某一特征访问和存储，访问速度快； 缺点是好的散列很难，有时会产生冲突。
上述四种基本存储方法，既可单独使用，也可组合起来对数据结构进行存储映像。同一逻辑结构采用不同的存储方法，可以得到不同的存储结构。选择何种存储结构来表示相应的逻辑结构，视具体要求而定，主要考虑运算方便及算法的时空要求。
3. 数据操作
如一张表格，需要进行查找、增加、修改、删除、排序等工作，这就是数据的运算，它不仅仅是加、减、乘、除这些算术运算，在数据结构中，这些运算常常涉及算法问题。
数据结构反映数据内部的构成方式，它常常用一个结构图来描述： 数据中的每一项成分数据被看作一个结点，并用方框或圆圈表示，成分数据之间的关系用相应的结点之间带箭头的连线表示。如果成分数据本身又有它自身的结构，则结构出现嵌套。这里嵌套还允许是递归的嵌套。
3.1.4数据结构的分类
通常将数据的逻辑结构简称为数据结构。按数据结构中成分数据之间的关系，数据结构分为线性结构和非线性结构两大类。
1.  线性结构
如果结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。
2.  非线性结构
非线性结构的逻辑特征是该结构中一个数据元素可能有多个直接前趋和直接后继。非线性结构中最普遍的就是图的结构。在非线性数据结构中又有层次与网状之分。
3.2线性表
线性表(linear list)是一种最简单、最常用的数据结构。线性表的存储结构通常分为顺序存储结构和链式存储结构。前者是用顺序存储结构存放的线性表，称为顺序表； 后者是用链式结构存储的线性表，称为线性链表。
3.2.1线性表的定义和运算
1. 线性表的定义

线性表是一组类型相同的数据元素a0，a1，…，an-1的有限序列，记为(a0，a1，…，an-1)。在线性表中，数据元素的个数n定义为线性表的长度，n=0的表称为空表。
当表的长度n≥1时，a0是表的第一个元素，an-1是最后一个元素。除a0外，表中每一个数据元素ai(1≤i≤n-1)只有一个直接前趋(predecessor)ai-1，除ai-1外，表中每个数据元素ai(1≤i≤n-1)仅有一个直接后继(successor)ai+1。数据元素在表中的位置只取决于它自身的序号，数据元素间的相对位置是线性的，因此称线性表是一种线性结构。
例如,26个大写英文字母组成的字母表(A，B，C，D，…，Z)是一个线性表。其中,A是第一个数据元素，Z是最后一个数据元素，A是B的直接前趋，B是A的直接后继，线性表的长度是26。
线性表中的数据元素也称为结点。它可以是一个整数、一个实数、一个字符或一个字符串； 也可以由若干个数据项(item)组成，其中每个数据项可以是一般数据类型，也可以是构造类型。
表32的线性表用于记录最近一周每天的平均气温。每个结点有两个数据项： 一个是星期，它的数据类型是由三个字符组成的字符串； 另一个是温度，它的数据类型是实型数据。一般称多个数据项组成的数据元素为记录，称数据元素为记录的线性表为文件(file)。


表32一周内每天的平均气温记录表



MonTueWedThuFriSatSun

15.516.015.715.016.116.416.5

2. 线性表的运算
线性表的基本运算是插入、删除、查找、排序等。插入是指在表的两个确定的元素之间插入一个新的数据元素； 删除是指删掉表中某个数据元素； 查找是指查询表中满足某种条件的数据元素； 排序是指根据结点的某个字段值按升序(或降序)重新排列线性表。可以将几个线性表合并成一个线性表，或把一个线性表拆成几个线性表，求线性表的长度等。其中，查找、插入、删除是线性表常见的三种基本运算。
3.2.2顺序存储的线性表
1. 顺序表


顺序表(sequential list)是用一组连续的存储单元依次存放等长数据元素的线性表，也称为线性表的顺序存储结构。这组连续的存储单元称为向量(vector)。在计算机中顺序存储结构是表示线性表的最简单方法。
1) 顺序表的存储地址


图35顺序表示意图


由于顺序表中所有结点的数据类型是相同的，因此每个结点在存储器中占用大小相同的空间。若一个数据元素仅占一个存储单元，

则这种存储方式如图35所示。由图35可见，顺序表第i个数据元素的存储地址为L(ai)=L(a0)+i，其中L(a0)是线性表第一个数据元素的存储地址。
若每个数据元素都占用k个存储单元，并以L(a0)为第一个数据元素存储单元地址(顺序表的首地址)，则第i个数据元素的存储位置为L(ai)=L(a0)+i×k。


2) 顺序表的特点
顺序表的特点是表中逻辑上相邻的数据元素存储在相邻的存储位置。换句话说，以数据元素在计算机内“物理位置相邻”来表示表中的数据元素间的逻辑关系。对于这种存储方式，访问第i个数据元素，就可以直接计算出ai的存储地址L（ai），因而能随机存取表中任一数据元素。换言之，数据元素在顺序表中的存储位置取决于该数据元素在顺序表中的顺序号。
顺序表可用C语言的一维数组实现。数组的类型随着数据元素的性质而定。描述方法为： 

# define M 1000;

int a［M］;

它表示数组名为a，该数组有M个数据元素(M=1000)，下标从0开始。设线性表为(a0，a1，…，an-1)，n<M，一个数组元素存放一个数据元素，数据元素的存储位置可用数组元素的下标值来表示。
2. 顺序表的插入
插入是指在具有n个结点的顺序表中，把新结点插在顺序表的第i(0≤i≤n)个结点位置上，使原来长度为n的顺序表变成长度为(n+1)的顺序表,如图36所示。
为了避免数据被覆盖而丢失，顺序表的插入从后往前数据依次向后移动，插入操作的具体方法是： 在把新结点放进长度为n的顺序表中的第i个结点的位置时，必须把原来序号为(n-1)至序号为i的结点依次往后移一个位置，然后把插入数据放在第i个结点位置上，此时共移动(n-i)个结点。对于i=n，只要把新结点插在第n个位置上，此时无须移动结点。在顺序表插入算法中，插入成功时函数返回值为0，否则函数返回值为-1。


图36顺序表插入



例如，欲在数组{1, 2, 5, 2, 3, 5}中第2个数据元素前插入一个数据，则需要第2个数据元素移动到第3个元素中，后面的元素依次向后移动一位，将新数据插入到原第2个数据元素的位置。在此过程中，为了避免数据覆盖造成的数据丢失，数据移动操作需要从最后一个元素开始，依次向前，直到空出第2个元素位置。在移动过程中，由于数据原来所在位置会被后续的数据更新，可以省略数据原来所在位置的清空操作。具体的操作步骤如图37所示，其中，弧线上方数字表示操作步骤序号。


图37顺序表插入操作数据移动步骤



上述顺序表插入操作过程的实现代码清单如程序31所示。注意，由于C语言数组游标是从0开始的，因此用户输入的数据位置序号与数组中的游标相差1。
程序31顺序表插入程序。

//显示列表

void showlist(int list［］,int n){

cout<<"＼t";

for(int i=0;i<n;i++){

cout<<list［i］;

if(i<n-1){

cout<<"＼t"; //制表位分隔

}else{

cout<<endl;

}

}

}

//线性表插入操作： 将数据x插入数组a中第pos个位置，数组长度为n

int insert(int pos, int x, int a［］,int n)

{

int j;

if(( pos<0)||( pos>n )){

return(-1);

}else{

for(j=n; j>=pos-1;j--){

a［j+1］=a［j］; //将插入点后的数据逐个向后移动

showlist(a,n+1);

}

a［pos-1］ = x;

return(0);

}

}


调用代码如下： 

void main(){

int pos, data, retflag;

static int a［7］ = {1, 2, 5, 2, 3, 5}; //插入操作数组中至少留一个空位

int n=7; //数组长度，数组元素个数

int n1=6; //当前有效数据个数

cout<<"当前数组： "<<endl;

showlist(a,n1);

cout<<"请输入要插入的结点的序号和要插入的数值: "<<endl;

scanf("%d %d", &pos, &data);

retflag=insert(pos, data, a,n1);

if (retflag == 0){

cout<<"插入成功后的数组是:"<<endl;

showlist(a,n);

}else{

cout<<"插入不成功!"<<endl;

}

}


运行结果： 

当前数组： 

1 2 5 2 3 5

请输入要插入的结点的序号和要插入的数值:

2 33

初始数组1 2 5 2 35 0

第6个元素向后移动1 2 5 23 55

第5个元素向后移动1 2 52 33 5

第4个元素向后移动1 25 22 3 5

第3个元素向后移动12 55 2 3 5

第2个元素向后移动1 22 5 2 3 5

插入成功后的数组是:

1 332 5 2 3 5


上面的结果中用加方框表示操作过程中发生变化的数据。
3. 顺序表的删除
删除是指在具有n个结点的顺序表中，删除第i(0≤i≤n-1)个位置上的结点，使原来长度为n的顺序表变成长度为(n-1)的顺序表，如图38所示。
同样为了避免数据覆盖丢失，顺序表的删除则从前往后依次向前移动。删除操作的具体方法是： 如果要删除长度为n的顺序表中的第i个结点，则要把位置号为(i+1)至位置号为(n-1)的结点中数据都依次向前移动一个位置，覆盖欲删除元素值，此时共需移动(n-i-1)个结点。表长为n-1。若删除成功，函数返回值为0； 否则，函数返回值为-1。

例如，欲删除数组{1, 2, 5, 2, 3, 5}中第2个数据，则要第3个数据元素移动到第2个元素中，后面的元素依次向前移动一位。在此过程中，为了避免数据覆盖造成的数据丢失，顺序表删除操作过程中的数据移动操作需要从第3个数据元素移动到第2个元素开始，依次向后，直到最后一个元素。最后一个元素移动后，需要对最后一个元素原来位置进行清空处理，设置为表示无数据的特征值(本章中为0)，如果是其他数据对象，需要考虑销毁无用对象避免内存泄漏。
具体的操作步骤如图39所示，其中，弧线上方数字表示操作步骤序号。


图38顺序表删除





图39顺序表删除操作数据移动步骤


上述顺序表删除操作过程的实现代码清单如程序32所示。
程序32顺序表删除程序。

/**

线性表删除操作： 删除数组a中第pos个位置的元素，数组长度为n

*/

int del(int pos, int a［］,int n)

{

int PosArr=pos-1;

int j;

if((PosArr<0)||(PosArr>n)){

return(-1);

}else{

for(j=PosArr;j<n-1;j++){

a［j］=a［j+1］;

a［j+1］=0; //为了突出显示操作过程，这里增加了以0补充空位

showlist(a,n);

}

return(0);

}

}



调用代码： 

void main(){

int retflag;

int delpos=-1;

static int a［6］ = {1, 2, 5, 2, 3, 5};

int n=6;

cout<<"当前数组； "<<endl;

showlist（a,n）;

cout<<"请输入要删除结点的序号: "<<endl;

scanf("%d",&delpos);

retflag=del(delpos,a,n);

if(retflag==0){

cout<<"删除成功后的数组是:"<<endl;

showlist(a,n-1);

}else{

cout<<"删除不成功!"<<endl;

}

}

运行结果： 

当前数组： 

1 2 5 2 3 5

请输入要删除结点的序号:

2

将第3位向前移动1位1 5 0 2 3 5

将第4位向前移动1位1 5 2 0 3 5

将第5位向前移动1位1 5 2 3 0 5

将第6位向前移动1位1 5 2 3 5 0

删除成功后的数组是:

1 5 2 3 5


从上述过程可以看出，0的位置是不断向后移动的，直到所有的数组元素向前调整完毕，实现了元素删除操作。
3.3栈
栈(stack)与队列(queue)是两种特殊结构的线性表，在进行程序设计时非常有用。与线性表相同，栈和队列的存储结构分为顺序存储结构和链式存储结构，本节将介绍顺序存储的栈。
3.3.1栈的定义及基本运算
栈是只能在表的一端进行插入和删除的特殊线性表。在栈中允许插入和删除的一端叫作栈顶(top)，而不允许插入和删除的另一

端叫作栈底(bottom)。

图310栈



插入一个新的栈顶元素叫进栈(又称压入)，删除栈顶元素叫出栈(又称弹出)。
图310所示的栈中，a0是栈底元素，an-1是栈顶元素。栈中元素按a0，a1，…，an-1的次序进栈，出栈的第一个元素应为栈顶元素an-1，也就是说最后一个进栈的数据元素最先出栈，即栈是后进先出的结构。因此，称栈为后进先出表(last in first out，LIFO)。
对栈的主要运算是插入和删除，只能在栈顶允许插入和删除操作，栈底不允许做插入和删除操作。
对栈进行的其他运算有： 
 设置一个空栈； 
 判定某个栈是否为空栈； 
 读取栈顶元素等。
栈是线性表的特例，所以栈可使用顺序存储结构。