数据结构定义

  1. 数据的逻辑结构
  2. 数据的存储结构(物理结构)
  3. 数据的运算

逻辑结构

  • 表示
    • 图表表示
    • 二原组表示 B = (D, R)
  • 类型
    • 集合
    • 线性结构
    • 树形结构
    • 图形结构
1
2
3
4
5
6
7
8
9
10
# 树形结构
B = ( D, R )
D = {a, b, c, d}
R = { r } 
r = {<a, b>,<a, c>,<a, d>}
# 图形结构
B = ( D, R )
D = {a, b, c, d}
R = { r } 
r = {(a, b),(a, c),(b, c)}

存储结构

  • 顺序存储 (dict)
  • 链式存储 (*next)
  • 索引存储 (key, address，查找效率高，需建立索引表)
  • 哈希(散列)存储(哈希函数计算出存储地址，只对数据进行存储，不对逻辑关系存储)

数据运算

常用的运算有检索、插入、删除、更新和排序等。

运算定义运算实现
逻辑结构映射=>存储结构

数据类型和抽象类型

  • 数据类型
    • C/C++ 常用的数据类型
      • 基本数据类型(int, short int, long int, unsigned int, bool, float, double, char)
      • 指针类型(int i,*p; i 是整型变量，p 是指针变量。&i表示变量 i 的地址，将 p 指向 i 的运算为p=&i。*p是取 p 所指变量的值。)
      • 数组类型 (int a[10])
      • 结构体类型
      • 共用体类型(共享存储单元)
    • 存储空间分配
      • 静态分配方式(int a[10];)
      • 动态分配方式(用malloc()函数为指针变量分配连续的空间，不需要时用free(p)释放p所指向的空间。)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 结构体类型
struct Test
{
   int no;
   int age;
};
struct Test t;  
t.no=10;
# 共用体类型
union Test1
{
    short int n;
    char ch[2];
};
union Test1 u;
u.n = 12;
1
2
3
4
5
6
7
# 动态存储空间分配
char *p;
p = (char *)malloc(10 * sizeof(char)); // p 为指针变量属于自动变量由系统自动分配和释放，(char *) 转化为字符指针
strcpy(p,"China");
printf("%c\n",*p); //  输出C
printf("%s\n",p); //  输出China
free(p);
  • 抽象类型（Abstract Data Type）
    抽象类型有两个重要特征，数据抽象和数据封装。抽象类型由数据逻辑结构和运算定义两部分组成。
ADTADT的实现
运算定义运算实现
逻辑结构映射=>存储结构

示例

1
2
3
4
5
6
7
8
9
10
11
12
ADT 抽象数据类型名（例：Complex）
{	数据对象：
	D = {e1,e2|e1,e2 均为实数}
	数据关系：
	R = {<e1,e2>|e1 是实数部分，e2 是虚数部分}
	基本运算：
	AssingComplex(&z,v1,v2):构造复数 z,实部 v1 、虚部v2。
	DestoryComplex(&z):销毁复数
	GetReal(z,&real):用 real 返回 z 的实部
	GetImag(z,&imag):用 imag 返回 z 的虚部
	Add(z1,z2,&sum):用 sum 返回 z1,z2 相加的结果
}