数据架构

数据结构就是指按一定的逻辑结构组成的一批数据，使用某种存储结构将这批数据存储于计算机中，并在这些数据上定义了数据操作。对于城市信息表而言数据指的是各城市信息的纪录。

数据结构主要包含三方面内容:数据的逻辑结构、数据的存储结构和数据的操作。 数据的逻辑结构

数据的逻辑结构包含3种基本结构:线性结构，树结构和图结构，如表1 结构 线性结构 示意图 k1k2k3定义与特点 线性结构的定义是:除第一个和最后一个数据元 素外，每个数据元素只有一个前驱数据元素和一个后继数据元素，第一个数据元素没有前驱数据元素，.最后一个数据元素没有后继数据元素。 树结构的一般定义是:除根结点外。每个数据元素只有一个前驱数据元素，可有零个或若一若干个k3k5k6树结构 k1k2k4后继数据元素，根结点没有前驱数据元素。 图结构的一般定义是;每个数据元素可有零个或若干个前驱数据元素，可有零个或若干个后继数据元素 图结构 k1k2k3k4 示意图中，圆圈表示一个数据元素，圆圈中的字符表示数据元素的标记或值，连线表示数据元素间的关系。

通过表1的综述，我们知道线性结构特征是结构有且只有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前驱和一个直接后继。对于城市信息表而言，一个数据元素即一个城市记录，只有一个开始的城市记录结点和一个终端的城市记录结点，因此对于城市信息表采用线性结构的数据结构进行设计。

城市信息表数据的存储结构

对于一个数据结构，必须建立从结点集合到计算机某个存储区域的一个映象，这个映象要直接或间接地表达结点之间的关系。数据在计算机中的存储方式称为数据的存储结构。

数据的存储结构基本形式有两种： 顺序存储

顺序存储通常用于存储具有线性结构的数据。将逻辑上相邻的结点存储在连续存储区域的相邻的存储单元中，使得逻辑相邻的结点一定是物理位置相邻。 链式存储

链式存储方式是给每个结点附加一个指针段，一个结点的指针所指的是该结点的后继

的存储地址，因为一个结点可能有多个后继，所以指针段可以是一个指针，也可以是一个多个指针。

城市信息表数据的操作

对于一批数据，数据的操作是定义在数据的逻辑结构之上的，而操作的具体实现就依赖于数据的存储结构。

数据的操作要视情况而定，一般而言，数据的操作包括插入、删除、检索、输出、排序等。对于城市信息表，则包含以下数据操作： 插入：在城市信息表中增加一个城市信息记录。 删除：在城市信息表中删除一个城市信息记录。

查询：在一个城市信息表中查找满足条件的一个城市信息记录。 修改：在一个城市信息表中修改相应的一个城市信息记录。

计算相邻城市距离：在一个城市信息表中计算相应的两个相邻城市的距离。

城市信息表的ADT

抽象数据类型（ADT）是与表示无关的数据类型，是一个数据模型及定义在该模型上的一组操作。对一个抽象数据类型进行定义时，必须给出它的名字及各运算的运算符名，即函数名，并且规定这些函数的参数性质。一旦定义了一个抽象数据类型及具体实现，程序设计中就可以像使用基本数据类型那样，十分方便地使用抽象数据类型。

对于城市信息表我们设计了如下所示的ADT： ADT City {

数据元素：每条城市坐标记录N(i)为一数据元素，i=1，2，…..，n(n≥1)； N(i)包括Name(i), CityX(i),CityY(i),City(i),Population(i)数据项

逻辑结构：所有数据元素N(i)存在线性关系(N(i)，N(i+1) )，N(1)无前趋，N(n)无后继； 基本操作：

setData(String[] Name,int[] CityX,int[] CityY,String[] City,int[] Population); //设置城市信息表数据 setLength(int length); //设置城市信息表长度

getData(int i);

//获取城市信息表第i个数据元素 getLength();

//获取城市信息表长度

insert(int i, String N,int X,int Y,String A,int P) ; //插入数据到城市信息表

Ndelete(String N);

//删除城市名为N的城市信息数据元素 Xdelete(int X) ;

//删除横坐标为X的城市信息数据元素 Ydelete(int Y) ;

//删除纵坐标为Y的城市信息数据元素 Ninquires (String N);

//查询城市名为N的城市信息数据元素 Xinquires (int X);

//查询横坐标为X的城市信息数据元素 Yinquires (int Y);

//查询纵坐标为Y的城市信息数据元素 Output();

//输出的城市信息表数据元素 }

城市信息表类的定义与实现 在城市信息表的数据结构设计中，我们通过面向对象的方法，对表定义了LineList类： 名称 String[] Name; int[] CityX; int[] CityY; String[] City; int[] Population; int length; 成员函数 LineList() CityX,int[] CityY,String[] City,int[] Population) setLength(int length) getData(int i) public public void String boolean 访问类型 返回值定义 作用 protected protected protected protected protected protected public / / / / / / / void 存储城市名 存储X坐标 存储Y坐标 存储相邻城市名 存储城市人口 存储城市信息表长 新建空表 设置城市信息表数据，包含Name ，CityX ，CityY，City，Population数据项 设置城市信息表的表长 返回获取到的第i个城市信息数据元素 插入城市信息数据元素到第i行，包含Name ，CityX ，CityY，City，Population数据项 Ndelete(String N) Xdelete(int X) Ydelete(int Y) Ninquires (String N) Xinquires (int X) Yinquires (int Y) Output() LineListT子类（继承LineList类） public public public public public public public void void void int int int void 删除与城市名N相同的城市信息数据 删除与横坐标X相同的城市信息数据 删除与纵坐标Y相同的城市信息数据 查找与城市名N相同的城市信息数据 查找与横坐标X相同的城市信息数据 查找与纵坐标Y相同的城市信息数据 打印城市信息表数据 LineList类 类型 数据成员 setData(String[] Name,int[] public insert(int i, String N,int X,int public Y,String A,int P) 为了使功能更为完善，我们还相应的建立了LineList类的子类，LineListT子类的定义： 类型 数据成员 成员函数 名称 Scanner sc Edit (int i,int No) 访问类型 返回值定义 private public / void 作用 存储用户键盘输入 根据模式No（城市名修改，X坐标修改，Y坐标修改，相邻城市名修改，城市人口修改）修改第i行的Neighborhood(int C)

public void 城市信息数据 计算第C行的两个相邻城市的距离 在城市信息表的类设计中，我们采用java语言进行编写，具体实现如下：

类名数据成员成员函数

Java共有类包类名数据成员成员函数

城市信息表的数据操作java实现（顺序结构） 插入操作 插入操作中，主要通过函数insert()函数实现，通过参数i，N，X，Y，A，P将要插入的第几行，以及插入的新城市信息数据，传值到函数中进行插入的操作，具体算法实现如下：

删除操作

查询操作

打印操作

城市信息表的数据操作java实现（链式结构） 插入操作

删除操作

查询操作

打印操作

城市信息表的实现结果 插入操作

删除操作

查询操作

打印操作

修改操作

计算相邻城市距离操作

城市信息表的两种实现方式对比

根据两种的存储结构定义，我们进行以下对比： 类型 顺序存储 链式存储 时间的角度 在按位置查找数据，或在查找元素的前驱和后继等方面，顺序存储有着较大的优势 空间的角度 由于在链表中只要修改指针即可实现这些操作，在插入数据，删除数据时，链式存储就有较大优势 顺序表的存储空间是静态分配动态链表的存储空间是动态分配的，只的，在程序执行之前必须规定其要内存空间有空闲，就不会产生溢出 存储规模 顺序表中查找元素非常容易，但是要插入或删除一个元素却需要移动大量元素 链表中可以方便地插入或者删除元素，但在查找元素时需要进行遍历 数据操作 对于城市信息表，我们主要是对城市信息进行查询操作，在插入和删除以及修改方面的数据操作相对教少，因此，我们选择使用在查找操作较有优势的顺序结构对城市信息表的数据结构进行设计开发。 总结