数据结构（未完）

前言

  有一种说法是程序是由数据结构和算法组成的，这很能体现出数据结构在编码中的重要性。而代码优化的能力也是区别有基础的程序员和码农的重要标准，所以对于这一块的学习一定要稳重与细致，每一个章节都要实打实敲出能够实现该种结构的代码才算完成。  

  数据结构的学习本质上是让我们能见到很多前辈在解决一些要求时间和空间的难点问题上设计出的一系列解决方法，我们可以在今后借鉴这些方法，也可以根据这些方法在遇到具体的新问题时提出自己的解决方法。（所以各种定义等字眼就不用过度深究啦，每个人的表达方式不一样而已）在此以下的所有代码都是仅供参考，绝对不是唯一的答案，任何一种 *** 作能达到相同的结果，只要逻辑上能行的通，复杂度上差不多，是无所谓怎么去实现最后的功能的。

目录

前言

一、抽象数据类型

二、线性结构

1.顺序表

2.单向链表

3.双向链表

总结

---

一、抽象数据类型

  在一开始学习数据结构的时候不用关注复杂度的问题，等到基础的数据结构学习完之后再去了解复杂度不迟。

  学习数据结构之前先了解什么是抽象数据类型。我们现在认识的数据类型就是一些类似整形字符型等表示数据取值范围的类型，而最初的程序员使用语言的是机器语言，即以0和1存储来实现功能，这样数据没有类型，我们每次在对他进行 *** 作的时候都不清楚这个数据可以做的具体 *** 作方式（是加减乘除还是合并），每次存储的时候也要去找相对于的空间。为了解决这个问题后来的程序员引入了数据类型的概念，这样我们再存储的时候我们就不需要再去寻找存储器的地址了，直接定义变量之后赋值就行。

  抽象数据类型的用途与普通的数据类型类似，他的本质就是一组数学模型，里面存放着这个模型的具体数值和这个模型能做的具体 *** 作。（比如int能实现加减乘除，字符串能实现字符串的拼接）。而他与数据类型的区别就是，数据类型是前人给我们定义好的，而抽象数据类型是我们自己定义的。

  这就可以引出下一章线性表，线性表的属性是什么， *** 作是什么，他的本质就是一个抽象数据类型。

二、线性结构

定义：除了第一个和最后一个元素，其他每个元素只有一个前和一个后的结构。

线性结构又分为两种：顺序表和链表。

1.顺序表

特性：一组地址连续的存储单元（数组）

主要用到的 *** 作：增删改查，初始化

以下是对应的抽象数据类型 ：

parr 用来存放数据  size  当前顺序表内数据个数  length 顺序表容量

typedef struct slist
{
    int* parr;//用来存放数据
    int size;//当前顺序表内数据个数
    int length;//当前顺序表的容量
}slist;

①在最后一位增加

这个 *** 作非常的简单，只要知道当前的顺序表内元素个数，然后在+1的位置执行插入 *** 作就好了。

void add_slist(slist* array, int key)
{
    if (array->size == array->length)//先判断是否需要空间
    {
        array->length += UNIT;
        int* newp = (int*)realloc(array->parr, sizeof(int) * (UNIT + array->length));//第二个数不得等于0
        if (!newp)//判断是否扩容失败
        {
            printf("顺序表扩容失败");
            system("pause");
        }
        array->parr = newp;
        array->length += 5;
    }
    array->parr[array->size] = key;
    array->size++;
}

  那么这里的扩容 *** 作是什么意思呢，这里我们通过数组去实现的顺序表，那众所周知数组的长度是固定的，那么一旦我们添加进去的数据超过了原来的容量，就只能扩容了，这里通过realloc来实现扩容。

 ②在最后一位之前插入

  从对这个数组的影响上来看，这一个 *** 作与1的增加都是往数组里赋值了一个数据。但从函数的 *** 作上和函数接口的设计上（这个具体看下面的代码）与增加是不同的。

  从 *** 作上看，这个数据插入的时候要把所有这个数据以后的数据都向后移动一位，来给这个要赋进去的数据腾出一个位置，然后再插入这个数据。从函数的接口设计上，因为与在最后一位增加的 *** 作不同，插入的 *** 作需要知道你插入的位置，所以还需要往函数里给一个位置的参数。这时候会不会觉得那干脆把增加的 *** 作想象成往最后一个位置做插入，把这两个 *** 作写成一个函数会不会更简单一些？在一些时间有限的竞赛中是推荐这么做的，但在开发项目里是不建议这么做的。（比如你只是想往里面一直放元素，难道你每次还要再指定你的位置吗？而且到后面我们接触的项目规模逐渐变大的时候，每一种非常细小差别的 *** 作都是需要分开的）

void iadd_slist(slist* array, int key, int index)
{
    if (array->size == array->length)//先判断是否需要空间
    {
        array->length += UNIT;
        int* newp = (int*)realloc(array->parr, sizeof(int) * (UNIT + array->length));//第二个数不得等于0
        if (!newp)//判断是否扩容失败
        {
            printf("顺序表扩容失败");
            system("pause");
        }
        array->parr = newp;
        array->length += 5;
    }
    if (index > array->length)
    {
        printf("顺序表查找下标超出最大值");
        system("pause");
    }
    array->size++;
    for (int i = 0; i < array->size - index - 1; i++)
    {
        *(array->parr + array->size - i - 1) = *(array->parr + array->size - i - 2);
    }
    *(array->parr + index) = key;
}

③修改和查找一个数据 

  修改和查找的 *** 作非常的相似且简单，是给定一个下标返回对应该下标对应的值，或者是修改改下标里的值，那这里就只举一个查找的例子了。

int inquiry_slist(slist* array, int index)
{
    if (index > array->length)
    {
        printf("顺序表查找下标超出最大值");
        system("pause");
    }
    return(*(array->parr + index));
}

④删除一个数据

这里只要把该数据后面的全部数据一个一个前移就能实现删除的 *** 作了。那这里最后的4要不要清除掉呢？视具体情况而定，一般有统计当前元素个数的变量就不用清除最后4的数据了。

void delete_slist(slist* array, int index)
{
    if (index > array->size)
    {
        printf("顺序表删除下标超过最大值");
        system("pause");
    }
    else
    {
        for (int i = 0; i < array->size - 1 - index; i++)
        {
            *(array->parr + index + i) = *(array->parr + index + i + 1);
        }
    }
}

这里便能体现出一个顺序表的缺点，虽然进行了删除数据的 *** 作，但是在内存上我并没有减少内存的使用，我删除的那一个内存只是数据消失了但仍然是一个被占有的状态。

⑤初始化顺序表

当程序刚开始的时候是不存在这样的数据类型的，所以我们要创建该类型并完成初始化，具体代码如下。

slist init_slist()
{
    slist arr;
    arr.length = UNIT;
    arr.parr = (int*)malloc(sizeof(int) * UNIT);
    if (!arr.parr)//判断初始化分配内存失败  
    {
        printf("顺序表初始化失败");
        system("pause");
    }
    arr.size = 0;
    arr.length = UNIT;
    return arr;
}

⑥顺序表的其他 *** 作

其实顺序表主要的 *** 作在上面都已经实现完成了，写这一块的意义是想说明学习数据结构和写项目都一样，代码是死的人是活的，不要按照书上写的生搬硬套，哪个代码能更好的实现功能，哪个代码效率高，那他就是优秀的代码。学习数据结构的时候也是，主要功能写完之后为了测试或是为了提高熟练度，可以自行的增加或删除一些 *** 作（像上面的顺序表就没有写释放空间的 *** 作，因为学习顺序表不需要）。下面就是补充的一些 *** 作 清空顺序表（指数据）  销毁顺序表（指内存） 打印顺序表     还有测试以上所有功能的main函数。

#include 
#include 

void clear_slist(slist* array)//清空顺序表
{
    if (array->size == 0)
    {
        ;
    }
    else
    {
        for (int i = 0; i < array->size; i++)
        {
            *(array->parr + i) = NULL;
        }
    }
}

void destory_slist(slist* array)//销毁顺序表
{
    if (array->parr != NULL)
    {
        free(array->parr);
        array->parr = NULL;
    }
}

void print_slist(slist* array)//打印顺序表
{
    for (int i = 0; i < array->size; i++)
    {
        printf("%d", *(array->parr + i));
    }
}

int main()
{
    slist slist1 = init_slist();
    slist* pslist1 = &slist1;
    int a = 0;
    while (a < 10)
    {
        add_slist(pslist1, a);
        a++;
    }
    print_slist(pslist1);
    iadd_slist(pslist1, a, 2);
    print_slist(pslist1);
    clear_slist(pslist1);
    print_slist(pslist1);
    destory_slist(pslist1);

    system("pause");
    return 0;
}

⑦顺序表的优缺点

顺序表有一个特别明显的优点，就是知道下标之后查找和修改的 *** 作效率都非常的高。但同时他的缺点也比较明显，就是在中间插入数据和中间删除数据的时候需要把后面的所有数据全部移动一遍，虽然这次事例中的数据不多，但是在之后的项目里可能会遇到千万条的数据，这时候每一次添加和删除的代价就非常大了；还有一个缺点就是顺序表的长度是固定的，这就导致肯定会有浪费的空间和肯定需要扩容的 *** 作；再还有一个缺点就是对于无序的数组，他的搜索效率底的。

2.单向链表

特性：物理上不连续，逻辑上连续，大小不固定

主要的 *** 作：增（此章还增加了头插）删改查，初始化

在了解他的抽象数据类型之前，我们先要了解几个概念。头指针，就是一个指向链表第一个节点的指针。首元节点，是真正存放数据的第一个节点。带头节点单向链表和不带头节点单向链表，这是有一点区别的两种单向链表，具体的 *** 作区别和实用性后面会说。

这是以上概念的图示，上半部分是带头节点的，下半部分是不带头节点的。

接下来了解一个链表的具体组成。链表是怎么通过逻辑来让物理上不连续的内存变得连续的呢。答案是通过指针，我们在每一个数据的节点里在放一个变量来存储下一个节点所在的地址，就可以一个接着一个的去连接所有的数据了，具体组成如下。

pnext 指向下一个节点的地址     data 存放数据

typedef struct linklist
{
    linklist* pnext;//指向下一个节点的地址
    int date;//存放数据
}linklist;

①增加节点

那具体要怎么实现数据的插入呢，首先我们需要执行一个 *** 作，就是定位到我们需要插入的位置，这一步只要一直p = pnext直到到了想要的位置停止就行了。然后我们新建一块内存用来存放我们要插入的数据和pnext，pnext的值等于我们所要插入位置的前一个位置的pnext，然后我们再把前一个位置的pnext指向我插入的这个数据的地址就行了，要是觉得绕看图一下就懂了。

 

  接下来我以不带头节点来举例，增加数据的 *** 作会比带头结点的麻烦，为什么这么说呢？因为如果在不带头结点的第一个位置去插入数据，那头指针指向的位置就必须是新添加进来的这个节点，则需要我们再去改变头指针的值，而带头结点的链表在第一个位置插入数据也是在头节点的下一个位置插入节点，所以是不需要改变头指针的位置的。那么就说明一个正常的插入 *** 作，不带头结点的可能需要改变两个变量（新的节点和头指针），需要两种 *** 作才能实现，而带头结点的一种（新的节点）就行了，这也印证了为什么带头结点的链表使用率更高一点。（带头结点的头节点内存不能说是浪费，一个节点和庞大的项目里的数据比起来实在是太微小了）

void headadd_linklist(linklist** p, int key)
{
    linklist* head = (linklist*)malloc(sizeof(linklist));
    if (!head)
    {
        printf("链表初始化失败");
        system("pause");
    }
    else
    {
        head->pnext = (*p)->pnext;
        head->date = key;
        (*p)->pnext = head;
    }

}

void add_linklist(linklist* head, int key, int num)
{
    if (num == 0)
    {
        headadd_linklist(&head, key);
    }
    else
    {
        linklist* p = (linklist*)malloc(sizeof(linklist));
        if (!p)
        {
            printf("链表初始化失败");
            system("pause");
        }
        else
        {
            linklist* temp = head;
            for (int i = 0; i < num; i++)
            {
                if (!temp->pnext)
                {
                    printf("增加位置下标为空指针");
                    system("pause");
                }
                temp = temp->pnext;
            }
            p->pnext = temp->pnext;
            p->date = key;
            temp->pnext = p;
        }
    }
}

从这我们能发现链表的一个坏处，他不如顺序表能够一下到我们想要的位置，就比如如果我们要在链表的最后一个位置插入一个值，那就得先遍历前面全部的数据再去插入 *** 作。从这个方面来讲，如果我们要经常性的进行尾插的 *** 作，我们就可以再写一个尾指针（功能和头指针一样）。

②删除节点

删除 *** 作就更加简单了。我们要做的就是让这一组数据不会在链表中出现就好了。

 这里有一个要注意的地方，只改变了前一个节点指向的下一个节点后，要删除的节点的确不存在链表里了，但他在内存里还是处于被占用的状态，所以我们要提前记录要被删除节点的地址（因为不在链表里之后我们就找不到这个节点了），再通过这个地址去free那一块内存。

void deletenum_linklist(linklist* headp, int num)
{
    linklist* temp = headp;
    for (int i = 0; i < num; i++)
    {
        if (!temp->pnext)
        {
            printf("删除下标为空指针");
            system("pause");
        }
        temp = temp->pnext;
    }
    linklist* tempfree = temp->pnext;
    temp->pnext = (temp->pnext)->pnext;
    free(tempfree);
}

③初始化

这里因为举的是无头节点的例子，所以初始化的时候只要建一个头指针就够了，当然也可以提前创建一个第一个节点的内存。有头结点的则需要创建一个头指针和一个头节点。

void init_linklist(linklist** p)
{
    *p = (linklist*)malloc(sizeof(linklist));
    if (!(*p))
    {
        printf("链表初始化失败");
        system("pause");
    }
    (*p)->pnext = NULL;
}

这里有个小tip，c和c++里所有的指针，在初始化的时候如果没有具体指向的值，一定要指向null，如果什么都不指那他就是一个野指针，后面是有可能会用不了的。

④其他的 *** 作即测试main函数

改和查的 *** 作比较简单且相似，相信在逻辑理顺和上述代码有自己去敲过之后都能够写的出来的。这里就给一个打印列表和main函数。

void printf_linklist(linklist* p)
{
    linklist* temp = p->pnext;
    while (temp->pnext)
    {
        printf("%d", temp->date);
        temp = temp->pnext;
    }
    printf("%d", temp->date);
}

int main()
{
    linklist* t1;
    init_linklist(&t1);
    for (int i = 0; i < 13; i++)
    {
        add_linklist(t1, i, i);
    }
    printf_linklist(t1);

    deletenum_linklist(t1, 0);
    printf_linklist(t1);

    system("pause");
    return 0;
}

3.双向链表

---

总结

未完待续