【数据结构学习记录2】—— 线性表之顺序储存（顺序表）

顺序表

• 零.前言
• 一.原理
• • 1.简述
  • 2.分析
  • 3.思路图解
• 二.代码实现
• 三.测试
• 四.后记

零.前言

这内容可能和书上的代码不一样，因为我是加入了我的理解的，所以可能会有不合理的地方，如果出现问题，可以请大家斧正QAQ

一.原理

1.简述

一个数组是最简单的线性顺序储存结构，但是，当我们的数据成员比较多的时候，比如一个学生类型的数据结构，会有他的姓名、学号等信息，所以我们需要对这部分自定义一个结构体。当然，使用结构体数组就可以完成这个目的——把学生类组成一张线性表。
但是对于一个不定长的表，我们使用结构体数组的话，我们如果不能很好的预估长度的话，可能会浪费空间或者造成越界访问。
所以我们可以自己写一个顺序表，使用malloc来动态创建一个表。

2.分析

我们要实现一个表结构，我们肯定要存在以下几个函数：

1. 表的初始化(创建)
2. 表的销毁(节约空间)
3. 插入(增)
4. 删除(删)
5. 修改(改)
6. 查询(查)

3.思路图解

为了实现以上提到的几个函数，我们可以先大概考虑一下构建的思路：

1.3.0 初始化之前的思考

对于我们创建一个表，肯定我们先要创建一个表的基本储存元素：

1.3.1 表的创建

我们可以通过再创建一个结构体来作为我们表的结构，其中我们把它分为三块：

1. 学生类型的储存空间。通过malloc来创建一堆空间来储存，这个空间的首地址，就是我们学生类的开始地址。
2. 一个整型变量，用于存放当前已经存放了多少个“学生”
3. 一个整型变量，用于知道我们目前最大能存多少个“学生”
   我们结束地址的值实际上指向的是我们“可以使用”的第一个值，这个值我们一般称为尾后
   所以 这个表看起来像这样：
   

1.3.2 销毁

我们可以对储存空间使用free函数，这样，这个空间就会被销毁了。

1.3.3 插入

假设我们要向序号1插入一个节点，那么我们就把序号1及其以后的节点都依次往后移动一个位置，然后序号1的节点就空出来了，这样就可以把我们要插入位置的节点空出来，这样在把值赋值进去就行了。

1.3.4 删除

对于删除一个节点，我们只需要将删除的那个节点后面至结束的所有节点向前移动一个位置
，就可以了！

1.3.5 查找

对于查，我们可以从头到尾遍历一遍就可以查出某个值了。

二.代码实现

1.定义些常量

#define OK      1
#define ERROR   0
#define LIST_DEFAULT_LEN    50
#define LIST_NEW_LEN        8

2.定义节点(元素)

typedef struct elemType {
    int id;
    int sex;
}elemType;

为什么要这样写？
如果使用这种写法：

struct elemType {
    int id;
    int sex;
};

你只是申明了结构体elemType，如果要使用它作为类型，申请其他变量，还是需要：struct elemType name1；
如果使用这种：

struct elemType {
    int id;
    int sex;
}name;

那么你还只是申明了结构体elemType和一个该类型的变量name，如果要使用它作为类型，申请其他变量，还是需要：struct elemType name1；
而我们使用的这种方法：

typedef struct elemType {
    int id;
    int sex;
}elemType;

是创建了一个结构体elemType，并将这个结构体定义成elemType类型，以后申明变量就可以直接elemType name了

3.定义顺序表

typedef struct listType {
    elemType *data;
    int len;
    int MAX_LEN;
}listType;

4.创建函数

首先我们用malloc申请LIST_DEFAULT_LEN个elemType的储存空间。
然后再判断是否申请成功，并完成初始化。
提一句，按书上写的应该是int InitList(listType &list)，但是标准的C语言是不允许在函数里传递引用的，所以我们只能传递指针。如果想用int InitList(listType &list)方式，那就得使用C++
对于取指针指向元素的成员值应该用->
若想用.，需要先解指针：
listType llist = *list;
然后就可以llst.data了

int InitList(listType *list)
{
    list->data = (elemType *)malloc(LIST_DEFAULT_LEN * sizeof(elemType));
    if (list->data <= 0)
    {
        exit(1);
    }
    else
    {
        list->len = 0;
        list->MAX_LEN = LIST_DEFAULT_LEN;
    }
    
    return OK;
}

5.销毁函数

直接free掉申请的顺序表元素的储存空间

int DestroyList(listType *list)
{
    free(&list->data);
    list->len = -1;
    list->MAX_LEN = -1;
}

6.查看函数

写这个函数的目的就是为了像这样，查看目前表的结构。

先判断一下这个表是否存在，如果存在我们用一个for把0~len - 1的所有元素数据输出来即可。

int ShowList(listType *list)
{
    int i = 0;

    if (list->MAX_LEN <= 0)
    {
        return ERROR;
    }
    else
    {
        for (i = 0; i < list->len; ++i)
        {
            printf("No.%d id=%d sex=%d\n", i, list->data[i].id, list->data[i].sex);
        }
    }

    return OK;
}

7.插入函数

int InsertElem(listType *list, int index, elemType elem)
{
    int i = 0;

    if (index > list->MAX_LEN || index < 0)
    {
        return ERROR;
    }
    else if (list->len < index)
    {
        index = list->len;
    }
    else
    {
        for (i = list->len; i > index; --i)
        {
            list->data[i] = list->data[i-1];
        }
    }
    
    list->data[index] = elem;
    
    if (list->len >= list->MAX_LEN)
    {
        list->data = (elemType *)realloc(&list->data, (list->MAX_LEN + LIST_NEW_LEN) * sizeof(elemType));
    }
    
    ++list->len;

    return OK;
}

我们分块儿来看：

    if (index > list->MAX_LEN || index < 0)
    {
        return ERROR;
    }
    else if (list->len < index)
    {
        index = list->len;
    }
    else
    {
        for (i = list->len; i > index; --i)
        {
            list->data[i] = list->data[i-1];
        }
    }

这一组，我们是先判断:
如果插入的位置，大于了最大的长度或者小于0，那么输入肯定无效。
如果比len大但小于最大长度，那么我们就把index等于len的值，也就是插入到末尾。
如果len在已有的数据的表内。那么我们把len 到 index + 1的所有值，都赋值为它前面的那个值。需要从大到小进行遍历，因为是往后，如果从小开始，后面的值就会被覆盖。

list->data[index] = elem;

然后对其他的元素操作好了之后，data[index]这个地方的值已经可以使用了，我们赋值即可。

    if (list->len >= list->MAX_LEN)
    {
        list->data = (elemType *)realloc(&list->data, (list->MAX_LEN + LIST_NEW_LEN) * sizeof(elemType));
    }

然后我们看看现在len是否已经达到了最大的长度，如果达到了，我们就再多申请几个位置，为下一次赋值做好准备。这样，就不需要在每次操作之前，对长度的合法性进行校验，毕竟我们时刻准备着存储数据。预处理一般总是比临时处理好很多。

++list->len;

然后，我们的len应该是指向我们能用的元素，也就是最后一个元素的下一个位置，所以需要+1

8.删除函数

删除函数就比较简单了，只要参数合法，直接向前移动一个位置即可。
所以我们直接将len-1，然后判断修改合法性，再依次向前移动。

int DeletElem(listType *list, int index)
{
    int i = 0;
    
    list->len -= 1;
    
    if (index < 0 || index > list->MAX_LEN)
    {
        return ERROR;
    }
    else if(index > list->len)
    {
        index = list->len;
    }

    for (i = index; i < list->len; ++i)
    {
        list->data[i] = list->data[i + 1];
    }

    return OK;
}

9.查询函数

参数填要查询的值，若非关键字，就填-1，然后遍历一下表，并查询复合要求的数，一旦达到目标返回它的索引值index，找不到就返回-1

int QueryElem(listType *list, int id, int sex)
{
    int i = 0;
    int mark = 0;

    for (i = 0; i < list->len; ++i)
    {
        mark = 0;
        if (id == -1 || id == list->data[i].id)
        {
            ++mark;
        }
        if (sex == -1 || sex == list->data[i].sex)
        {
            ++mark;
        }
        if (mark == 2)
        {
            return i;
        }
    }

    return -1;
}

三.测试

我们写个主函数，并看看效果：

int main()
{
    listType list;
    elemType elem;

    elem.id = 456;
    elem.sex = 1;

    InitList(&list);
    InsertElem(&list, 0, elem);
    elem.id = 123;
    InsertElem(&list, 0, elem);
    elem.id = 789;
    InsertElem(&list, 7, elem);
    elem.id = 666;
    InsertElem(&list, 8, elem);
    ShowList(&list);
    DeletElem(&list, 3);
    printf("-------\n");
    ShowList(&list);
    printf("index is %d", QueryElem(&list, 456, -1));
    
    return 0;
}

完美！

四.后记

我不贴完整的代码，免得伸手党白x。
如果是真的仔细看了文章，可以手动复制创建程序。
如果要完整的代码，我贴个下载地址，关注我后，就可以免费下载。
下载地址：https://download.csdn.net/download/u011017694/13001582