学习

数据结构入门

数据结构入门

什么是数据结构？（绪论）

定义

数据结构是指所涉及的数据元素的集合以及数据元素之间的关系。
数据结构包含三方面：数据逻辑结构、数据存储结构、数据运算。

数据的逻辑结构

数据结构的对象关系是一对一的、呈线性关系的就称作线性表。
数据结构的 对象关系是非线性的、一对多的关系 称作树。
操作对象之间呈现多对多的关系，称作图。

数据、数据项、数据元素

数据就是输入的东西，比方说各个学生的姓名成绩。
数据项是具有独立含义的数据最小单位。
就比方说一个表，里面有学生姓名学号什么的，然后“姓名”这玩意就叫数据项。
数据元素是组成数据的基本单位，就是比方说姓名+学号+成绩，这样一整个叫数据元素。

逻辑结构

数据元素的逻辑关系称作逻辑结构。
逻辑结构分为四类：集合、线性结构、树结构、图结构。

存储结构

数据元素及其关系在计算机存储器中的存储方式就是存储结构
（就是把逻辑结构映射到内存上）
要求：存储所有元素，存储元素间的关系。
分四种 ：顺序存储结构、链式存储结构、索引存储结构、散列存储结构。

模板

C++提供了两种模板机制，即函数模板和类模板。

函数模板

声明函数模板一般格式如下：

1
2
3
4
5
template 类型参数表
返回类型 函数名（形参表）
{
    函数体；
}

例如，以下是一个求绝对值的函数模板，其中T为参数类型：

1
2
3
4
5
6
template <typename T>
T abs(T x)
{
    if(x < 0) return -x;
    return x;
}

类模板

template 类型参数表
class 类模板名
{
类模板实现语句；
···
}；

线性表

概念

线性表是具有相同类型的n个数据元素组成的有限序列（相同类型表明每个数据元素所占的空间相同）
除了第一个元素，其他元素都有直接前驱。
除了最后一个元素，其他元素都有直接后继。

操作

初始化，销毁，插入元素，删除元素，按值查找，按位查找。
什么时候要传入参数的引用？
对参数修改的结果需要带回来。
就比方说我定义了一个函数test(int x)然后我调用了这个函数，实际上我是把main函数中的x复制了一份给test中的x，也就是说main中的x不变。
而我test(int & x)的话，就是直接对于main中的x的值进行修改，因此x的值会改变。
所以呀，我在使用线性表的插入或者删除函数的时候，要调用线性表的引用，因为是对线性表本身进行修改。

顺序表

顺序存储，把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中。

顺序表的实现——静态分配

通过静态数组来实现

1
2
3
4
5
6
#define MaxSize 10
typedef struct{
    ElemType data[MaxSize];//ElemType是指元素类型
    int length;
}Sqlist;//sq指的是sequence（顺序）