什么是数据结构

(一):数据结构的定义

      数据是描述客观事物的数和字符的集合。从计算机的角度看，数据是所有能被输入到计算机中，且能被计算机处理的符号的集合，它是计算机操作对象的总称，也是计算机所处理信息的某种特定的符号表示形式。

     人们通常以数据元素作为数据的基本单位。一个数据元素可以由若干个数据项组成。

     数据项是具有独立含义的数据最小单位，也称为字段或域。例如，一个班中的每个数据元素（即学生记录）是由学号，姓名，性别...等数据项组成的。

     数据对象是指性质相同的数据元素的集合，它是数据的一个子集。讨论的数据通常指的是数据对象。

     数据结构是指所有数据元素以及数据元素之间的关系，可以看作是相互之间存在着某种特定关系的数据元素的集合。因此我们可以把数据结构看成带结构的数据结构元素的集合。

数据结构通常包括：

(1).数据的逻辑结构：由数据元素之间的逻辑关系构成。

(2).数据的存储结构：数据元素及其关系在计算机存储器中的存储表示，也称为数据的物理结构。

(3).数据的运算：施加在该数据上的操作。

1.1逻辑结构

数据的逻辑结构是从数据元素的逻辑关系上描述数据的，是指数据元素之间的逻辑关系的整体，通常是从求解问题中提炼出来的

1.逻辑结构的表示

1).图标表示

逻辑结构的图表表示就是采用表格或者图形直接描述数据的逻辑关系。

2).二元组表示

一个二元组表示如下：

B=(D,R)             其中B是一种数据逻辑结构，它由数据元素的集合D以及D上二元关系的集合R所组成。

R中的一个关系r是序偶的集合，对于r中的任一序偶<x,y>   (x,y<D),表示元素x和y之间是相邻的，即x在y之前，y在x之后，x称为该序偶的第一元素，y称为该序偶的第二元素，而且x为y的直接前驱元素(前驱元素)。y为x的直接后驱元素(后驱元素)。

某个元素没有前驱元素，则称该元素为开始元素；若某个元素没有后继元素，则称该元素为终端元素。

对称偶序元素用不带箭头的连线表示。

例：City=(D,R)      D={010,021,027,029,025}      R={r}      r={<010,021>,<021,027>,<027,029>,<029,025>}

2.逻辑结构的类型

1).集合

集合是指数据元素之间除了“同属于一个集合”的关系以外别无其他关系。

2).线性结构

线性结构是指该结构中的数据元素之间存在一对一的关系。其特点是开始元素和终端元素都是唯一的，除了开始元素和终端元素之外，其余元素都有且仅有一个前驱元素，有且仅有一个后继元素，线性表就是一种典型的线性结构。

3).树形结构

树形结构是指该结构中的数据元素之间存在一对多的关系。其特点是除了开始元素以外，每个元素有且仅有一个前驱元素，除了终端元素以外，每个元素有一个或多个后继元素。二叉树就是一种典型的树形结构。

4).图形结构

图形结构是指该结构中的数据元素之间存在多对多的关系。

1.2存储结构

数据逻辑结构在计算存储器中的存储表示称为数据的存储结构(也称为映像)，也就是逻辑结构在计算机中的存储实现。

1).顺序存储结构

2).链式存储结构

3).索引存储结构

4).哈希(或散列)存储结构

1.3  数据运算

数据运算是指针对数据实施的操作。每个数据结构都有一组相应的运算，最常用的运算有检索，删除，更新，和排序等。数据运算最终需要在对应的存储结构上用算法实现，所以数据运算分为运算定义(运算描述)和运算实现两个层面。

运算定义是运算功能的描述，是抽象的，是基于逻辑结构的。运算实现是程序员完成运算的实现算法，是具体的，是基于存储结构的。

1.4  数据类型和抽象数据类型

1.数据类型

数据类型是一组性质相同的值的集合和定义在此集合上的一组操作的总称，是某种程序设计语言中已实现的数据结构。

1.C/C++语言中常用的数据类型

1).基本数据类型：int型，bool型(布尔型),float型，double 型和char 型。  int型可有3个修饰符，即short(短整型),long(长整型)和unsigned(无符号整数)。

2).C/C++语言中的指针类型。

直接对存放变量的地址进行操作。

例如：

#include<stdio.h>

int main()
{
    int i,*p;//定义i是整型变量,p是指针变量(它用于存放整个变量的地址)。
i=2;
    p=&i;//表达式&i表示变量i的地址，将p指向整形变量i的运算为p=&i;
    printf("%d\n",*p);//对于指针变量p，表达式*p是所指变量的值。
    return 0;
}

3).C/C++语言中的数据类型

数组是同一数据类型中一组数据元素的集合。

4).C/C++语言中的结构体类型

结构体类型是由一组称为结构体成员的数据项组成的，每个结构体成员都有自己的标识符，也称为数据域。一个

结构体类型中的数据类型可以不相同。

5).C/C++语言中的共用体类型

共用体是把不同的成员组织为一个整体，他们在内存中共享一段存储单元，但不同成员以不同的方式被解释。

2).存储空间的分配

在程序设计中，定义变量就是使用内存空间，而存储空间的分配主要有两种方式。

(1).静态存储空间分配方式

所谓静态存储空间分配方式是指在程序编译期间分配固定的存储方式。该存储分配方式通常是在定义时就分

配存储单元并一直保持不变，直至整个程序结束。

(2).动态存储空间方式

所谓动态存储空间分配方式是指在程序运行期间根据需要动态地分配存储空间的方式。在程序执行时动态分

配存储空间，如malloc()/free()函数对。

例：

char *p;
p=(char *)malloc(10 * sizeof(char));//动态分配10个连续的字符空间
strcpy(p,"China");//将“China”存放到p所指向的空间中
printf("%c\n",*p);
printf("%s\n",p);
free(p);//释放p所指向的空间

p为指针变量，(char *)转换为字符指针，”10“为分配的字符个数