假期连载之一
关于本连载的说明请查阅http://www.hanyi.name/blog/?p=118
一、常用数据结构分析(概念、ADT、ADT实现、线性表的顺序存储)
一） 数据即是指描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。数据元素是指组成数据的基本单位，是数据集合的个体。相应的，数据结构就是性质相同的数据元素的集合，是数据的一个子集。
数据结构的内容大概包括以下三个方面：
1、 逻辑结构（通常）
① 集合结构，结构中的数据元素除了同属于一个集合的关系外，无其他关系。
② 线性结构，结构中的数据元素之间存在一对一的线性关系。
③ 数型结构，结构中的数据元素之间存在着一对多的层次关系。
④ 图状结构或网状结构，结构中的数据元素之间存在着多对多的任意关系。
2、 存储结构
① 顺序映像，即顺序存储结构。
② 非顺序映像，即非顺序存储结构。
3、 运算集合
数据结构另一个重要内容即是对一类数据的相关运算操作。
二） 抽象数据类型(Abstract Data Type，通常称ADT)，即包括一个相应的数学模型以及该模型上应用的各种运算，它集中体现了程序设计过程中的分解、抽象和信息隐藏等原则。
对于如何实现抽象数据类型，一般有三种方法，这也是目前程序设计的三个重要方法。
1、面向过程的程序设计，根据逻辑结构选择适当的存储结构，并按要求设计出相应的子程序或子函数，一般使用C语言、Pascal语言描述。
2、“包”、“模型”的设计方法，是面向模块结构的表示和实现，一般是指DOD的Ada语言、module-2语言和Pascal语言所支持的方法。
3、面向对象程序设计，借助对象描述数据类型，存储结构和操作函数被放在一个整体结构中，例如C++、Java等语言提供了此功能的支持。
在今后的连载内容中，我们将采用面向过程与面向对象相结合的方法，即给出两种描述，分别使用C语言和C++语言实现，方便大家在各方面的理解。高级算法部分主要以伪码形式给出，适当利用高级程序设计语言加以说明。
三) 分别用C、C++抽象数据类型实现的举例。
ADT<ADT名>{
数据对象：数据对象的定义。
结构关系：结构关系的定义。
基本操作：基本操作的定义。
}ADT<ADT名>
1、 C语言实现
在C语言中我们通常使用typedef自定义类型和结构体实现数据类型的集合。例如关于一个“学生”的集合：
typedef struct node{
char Name[20];
char Sex;
int Age;
float Money;
}Employee,*EmpPtr;
值得说明的是,typedef同时定义了两个新的数据类型名，Employee指struct node结构体类型名，而EmpPtr指结构体指针类型，通常代替struct node *类型名。
2、 C++语言实现
C++由于其特殊的特性对ADT有多种表示方法，通常使用自定义抽象类、自定义模版和void struct *三种方法，其中void struct *由于模版类的使用已经很少再使用，如有需要读者可以参考C语言的方法使用。
① 自定义抽象类，与Java不同，C++中并不提供abstract关键字声明抽象类，在确需要使用到抽象类时，须采用例如virtual void draw() = 0;的函数声明方法，称为“纯虚函数”，拥有“纯虚函数”的类自动为抽象类。
② 自定义模版template，目的是使抽象出的对象并不依赖于抽象类的数据类型。下面给出一个抽象类的声明和使用方法：
template<class T>
class Point{
private:
T x;
T y;
public:
Point(T,T);
Point(Point p);
T get_x();
T get_y();
virtual void draw() = 0;
}
int main()
{
Point<int> a;
return 0;
}
四) 线性表
线性表Linear List是指n个类型相同的数据元素的有限序列，对n>0，除第一个元素无直接前驱、最后一个元素无直接后继外，其余每个元素只有一个直接前驱和直接后继，线性表的抽象数据类型定义如下：
ADT LinearList{
数据元素：D={ai| ai ∈D0,i=0,1,2,…,n,n>=0, D0为某一数据对象};
结构关系：R={<ai ,ai+1>| ai , ai+1∈D0,i=0,1,2,…,n-1};
基本操作:
InitList(L); //初始化L为空表
DestroyList(L); //将L销毁
ClearList(L); //将L置为空表
EmptyList(L); //如果L为空则返回TRUE，否则返回FALSE
ListLength(L); //如果L为空返回0,否则返回FALSE
Locate(L,e); //如果L中存在元素e,则将当前指针指向元素e的所在位置，并返回TRUE,否则返回FALSE
GetData(L,i); //返回L中第i个元素的值
InsList(L,i,e); //在L中第i个位置之前插入新的数据元素e，L的长度加1
DelList(L,i,e); //删除L中第i个数据元素，并用e返回其值,L的长度减1
}ADT LinearList
1、 线性表的顺序存储(Sequential List)，其实就是指线性表基于一维数组的存储表示，数组占用了内存中一段连续空间，其元素的地址映像计算公式为：
Loc(ai)= Loc(a1)+(i-1)*k
注：上式表示在一个具有n个元素的线性表中，每个元素占k个单元，第一个元素的地址为Loc(a1)，则可通过上述公式计算第i个元素的地址Loc(ai)。
用C语言定义线性表的顺序存储结构的静态存储表示如下：
#define MAXSIZE 100
typedef struct
{
ElemType elem[MAXSIZE];
int last;
}SeqList;
相应地，其动态存储表示如下：
typedef struct
{
ElemType *elem;
int last,maxSize; //利用maxSize可方便控制数组空间的大小
}SeqList;
同时，我们也给出C++定义的线性表的顺序存储结构的动态存储模版类表示如下：
#include <iostream.h>
#include <stdlib.h>
#include “LinearList.h”
const int defaultSize = 100; //这里的const指静态常量，在C++定义中，const成员函数不能调用非const成员函数
template <class T>
class SeqList:public LinearList<T>
{
protected:
T *data;
int maxSize;
int last;
void resize(int newSize) //改变data数组空间的大小
public:
…… //方法函数
}
……
值得注意的是，在顺序表动态存储表示中，由于数组本身不可能被动态改变其大小，因而实际上是通过创建新数组并加以复制的方法实现的，复制的方法涉及到了C++中数组指针的内容，其和指针数组有明显区别，指针数组的定义方式int *p[10]代表p数组中每一个元素都是一个指针，即*p[0]、*p[1]…..数组指针一般定义为int (*p)[10]，这里仅表示一个指向数组的指针，它们访问内部元素的形式为而这里小结如下：
提前说明，数组指针与指针数组在C语言和C++之间也存在一些不同，但由于该名词是由C++中率先提出的，因此一般会按照C++标准来定义这些概念，并解释相关问题。例如在指针数组中，一般读取其中元素的方法是：
int *p=new int[maxSize];
cout<<*(p+n)<<endl; //输出第n+1个元素的值
而在数组指针中，我们一般用以下方式读取数组元素：
int (*q)[maxSize]={1,2,3,…,maxSize};
cout<<*(*q+n)<<endl; //同上
下面给出C++线性表的顺序存储结构的动态存储模版类中重置大小函数reSize()的方法定义：
template <class T>
void SeqList<T>::resize(int newSize)
{
if(newSize <= 0)
{ cerr << ”无效的数组大小” <<endl;
return;
}
if(newSize != maxSize)
{
T* newarray = new T[newSize];
if(newarray == NULL)
{
cerr << “存储分配错误!” <<endl;
exit(1);
}
int n = last+1;
T* srcptr = data;
T* destptr = newarray;
while(n–)
*destptr++ = *srcptr++;
delete []data;
data = newarray;
maxSize = newSize;
}
}
在顺序存储结构中，由于动态存储和静态存储的区别，其内部定义的基本运算也不尽相同，我们将给出部分运算的伪码表示：
Locate(L,e) //线性表的查找
i=0;
while i<=L.last && L.elem[i]!=e
do i++;
if i<=L.last
then return i+1;
else
then return -1;
InsList(L,i,e) //线性表的插入
if i<1 || i>L.last+2
Then error “插入位置不合法”
if L.last >= maxSize-1
Then error “线性表已满!”
for k=L-last k>= i-1 k— //从线性表尾部开始移动所有L.last+2-i个元素后继一位
L.elem[k+1]=L.elem[k];
L.elem[i-1]=e;
L.last++;
return OK
DelList(L,i,e) //线性表的删除
if i<1 || i>L.last+1;
Then error “删除位置不合法”
*e=L.elem[i-1];
for k=i i<=L.last k++
L.elem[k-1] = L.elem[k];
L.last–;
return OK;
Merge(LA,LB,LC) //线性表的合并，按非递减有序序列合并
while i<=LA.last && j<=LB.last
do if LA.elem[i] <=LB.elem[j]
then LC.elem[k]=LA.elem[i];
i++;k++;
else then LC.elem[k] = LB.elem[j];
j++;k++;
while i<LA.last
do LC.elem[k]=LA.elem[i];
i++;k++;
while j<= LB.last
do LC.elem[k] = LB.elem[j];
j++;k++;
LC.last=LA.last+1+LB.last+1;
(未完待续)