数据结构

一、基础概念

问题：什么是数据结构？有什么用？

我的理解：首先，所谓的程序就是一系列计算机指令的集合，它的目的是为了实现某个特定的功能或解决特定的问题。算法是程序功能的具体实现方式，有了算法，就有了解决问题的思路和方式。另一方面，所有程序或者算法的处理对象都是数据，当我们的程序要处理的是某一类常见的问题时，往往这时候的数据都有一些典型的特点，因此数据结构就是为了更好地存储、处理某一类模型中的数据创建出来的特定结构，简单举例说明，银行流水排号的时候要求先领到号先处理，也就是先进先出，这就是队列的数据结构擅长的地方。

数据结构就是为了更好的存储和处理特定类型的数据而出现的特定结构

再通俗一点地讲：

有一个事情：到菜果市场买菜和水果

算法：

1. 拿钱
2、拿装蔬菜和水果的篮子
3、确定菜果市场的位置
4、出发到达菜果市场
5、跟小贩讨价还价
6、买到之后回家

数据结构：

蔬菜  放在  菜篮子
水果  放在  果篮子

上面的例子中，数据就是你买到的水果和蔬菜，而用来盛的就是数据结构，因为蔬菜和水果不一样，所以才有了适合放蔬菜的菜篮子和适合放水果的果篮子，菜篮子中菜容易放容易取，还可以排整齐来节约空间，就是因为它适合放菜，数据结构正是这个道理。

分类：

• 集合

• 线性结构

• 树形结构

• 图状结构或网状结构

二、线性表

线性表在python当然不需要自己去实现，使用list及内置的方法完全可以实现绝大部分功能，但是重要不是工具，而是人。工具的简化可以我们提高效率，但是对于细节也会更多的忽略。在学习线性表的时候，不要太注重有没有实现什么，而是去观察一个线性表应有的操作和功能，更好地去理解什么是一个线性表。

不要想自己能做什么，多想一下自己脑袋里面有什么

一、顺序实现

操作类型

InitList(&L)
//构造一个空的线性表 
DestroyList(&L)
//线性表存在了，消耗一个线性表
ClearList（&L ）
//清空线性表中的内容
ListEmpty（L）
//判断线性表是否为空
ListLength（L）
//返回线性表的长度
GetElem（L，i，&e）
//返回线性表i位置上的元素值，通过e返回     
PriorElem（L，cur_e,&pre_e）
//如果cur_e是线性表中的元素，而且不是第一个，那么我们就可以返回该元素前一个元素的值
NextElem（L，cur_e,&next_e）
//如果cur_e是线性表中的元素，而且不是最后一个，就返回它下一个元素的值
Listinsert(&L,i,e)
//如果线性表存在了，而且i符合条件，则在i位置插入一个元素
ListDelete（&L,i）
//删除i位置上的元素
ListDelete_data(&L,e,order)
//删除指定的元素e，order决定是删除一个，还是全部。
Connect_two_List(L_a,L_b,&L_c)
//连接两个线性表，除去重复的内容    
print(L)
//打印线性表

1、InitList函数：初始化线性表

//扩充容量的步伐
#define  sizestep 10
//开始的容量的大小
#define startsize 100

//为了便于扩展，我们这里使用类型别名，
//我们使用最简单的int型作为一个范例

typedef int Elemtype;
struct List {
    //数据
    Elemtype * data;
    //长度
    int length;
    //初始容量
    int size;
};
//创建一个空的线性表
void InitList(List &newList) {
    //初始容量为startsize
    newList.size = startsize;
    //首先开辟空间
    newList.data = new Elemtype[newList.size];
    //空表，长度是0
    newList.length = 0;
}

2、DestroyList函数：删除线性表

//线性表存在了，现在要销毁线性表
void DestroyList(List &newList) {
    newList.length = 0;
    newList.data = 0;
    //一定要先释放堆内存（赋值为0，就是释放内存了？）
    delete[] newList.data;
    //每次释放堆内存后，并将对应的指针赋予NULL是一个良好的习惯
    newList.data = NULL;
}

3、ClearList函数：清空线性表

//线性表存在了，但是现在想清空整个线性表
void ClearList(List &newList) {
    newList.length = 0;
    //一定要先释放堆内存
    delete[] newList.data;
    //没此释放堆内存后，并将对应的指针赋予NULL是一个良好的习惯
    newList.data = NULL;
    //重新为存放元素的变量开辟一个新的堆内存
    newList.data = new Elemtype[newList.size];

}

4、ListEmpty函数：判断线性表是否为空

//判读线性表是否为空
bool ListEmpty(List newList) {
    return newList.length;
}

5、ListLength函数：线性表的长度

//返回线性表的长度
int ListLength(List newList) {
    return newList.length;
}

6、GetElem函数：获取线性表中某个位置的值

//返回线性表上某个位置上的元素的值,记住我们的位置是从1开始计算的。？？？？
void GetElem(List newList, int i, Elemtype &e) {
    if (ListEmpty(newList)) {
        cout << "当前线性表是空表" << endl;
        return;
    }
    if (i<1 || i>newList.length) {
        cout << "当前位置超出了线性表的范围" << endl;
        return;
    }
    e = newList.data[i - 1];
}

7、PriorElem函数：

二、链式实现