C++数据结构基础篇1-线性表（1）-顺序表

一、顺序表基础概念讲解

所谓的顺序表，也就是 $\color{red}{单元节点是按照顺序存储的方式进行存储的}$ ，想对于那种所谓的链表存储，我们可以从第一个节点，就可以通过地址的移动，访问到任何一个节点；
那么由这个定义，我们就有了两种开辟顺序表的方式；一种是栈内存，一种是堆内存；如果是栈内存的话，那么就是直接初始化的时候，在栈上开辟一块内存；如果是堆内存的话，那么就是初始化的时候，malloc一块内存；这两种方式；其实都是没有问题的；考虑到如果是栈内存，有可能会造成内存不足的情况，所以，我在总结的时候，还是以堆内存开辟为主；

二、顺序表基本操作

1、顺序表准备数据

我们现在假设是堆上去开辟内存的；那么上来的话，要进行基础的数据准备；

typedef struct DATA
{
    char key[10];
    char name[10];
    int age;
}DATA;

typedef struct SLTYPE
{
    DATA* Listdata;             //保存顺序表的结构数组
    int listlen;                //顺序列表已经存入的节点的数量
}SLTYPE;

既然我们是在堆上开辟内存的话，那么给到列表的自然就是一个地址；这个地址就是代表的是顺序表的初始地址；

2、初始化顺序表和析构和返回表长度

初始化就是开辟内存，对于析构就是释放内存；比较简单，没有什么可以说的；

//初始化
void SLInit(SLTYPE* SL)
{
    SL->Listdata = (DATA*)calloc(MAXLEN, sizeof(DATA));
    SL->listlen = 0;
}
//析构
void SLDistroy(SLTYPE* SL)
{
    free(SL->Listdata);
    SL->Listdata = NULL;
    SL->listlen = 0;
    free(SL);
    SL = NULL;
}

3、插入和删除操作和查找

//插入节点
//插入节点就是在第i个位置上插入新的节点；插入后的长度会变成i+1；
//所以插入节点最不太好的地方就是插入位置后面都需要移动
int SLInsert(SLTYPE *SL, int n, DATA data)
{
    int i;
    if (SL->listlen >= MAXLEN)
    {
        cout << "the list is full!!!" << endl;
        return -1;
    }
    if (n<1 || n>SL->listlen +1)
    {
        cout << "the location insert is error!" << endl;
        return -2;
    }
    for (i = SL->listlen; i > n; i --)
    {
        SL->Listdata[i] = SL->Listdata[i-1];

    }
    SL->Listdata[n-1] = data;
    SL->listlen++;
    return 1;
}
//删除第n个节点的内容
//说白了就是让后面的每一个去覆盖前面的即可；
int SLDelete(SLTYPE *SL, int n)
{
    int i;
    if (n<1 || n>SL->listlen)
    {
        cout << "the location delete is error" << endl;
        return -2;
    }
    for (i = n; i < SL->listlen; i++)
    {
        SL->Listdata[i-1] = SL->Listdata[i];
    }
    SL->listlen--;
    return 1;
}
//查找节点
//查找节点是最快的
DATA *SLFindByNum(SLTYPE *SL, int n)
{
    if (n<1 || n>SL->listlen + 1)
    {
        cout << "the location find is error!" << endl;
        return NULL;
    }
    //两种返回的方式；这两种返回的方式说明就是：如果是数组的方式，那么返回的不是地址；
    //或者用地址的方式返回；那么就是+n就是返回的地址；
    //return &(SL->Listdata[n]);
      return SL->Listdata+n-1;
}
//遍历
//遍历是比较简单的，这里就不写了，就是一个for循环就行了，没什么技术含量

4、main函数验证

int main()
{
    SLTYPE* SL = (SLTYPE*)calloc(1, sizeof(SLTYPE));
    SLInit(SL);
    int i = 0;
    for (; i < 10; i++)
    {
        DATA data;
        data.age = i;
        SLInsert(SL, SL->listlen + 1, data);
    }
    SLDelete(SL, 8);
    DATA* returndata = SLFindByNum(SL, 8);
    cout << "the age is " << returndata->age << endl;
    cout << "==================================" << endl;
    for (i = 0; i < SL->listlen; i++)
    {
        cout << "the age is " << SL->Listdata[i].age << endl;
    }
    SLDistroy(SL);

    return 0;
}

5、完整程序

#include<iostream>
#include<string>
#include<malloc.h>
using namespace std;

#define MAXLEN 100
typedef struct DATA
{
    char key[10];
    char name[10];
    int age;
}DATA;

typedef struct SLTYPE
{
    DATA* Listdata;             //保存顺序表的结构数组
    int listlen;                //顺序列表已经存入的节点的数量
}SLTYPE;
//初始化
void SLInit(SLTYPE* SL)
{
    SL->Listdata = (DATA*)calloc(MAXLEN, sizeof(DATA));
    SL->listlen = 0;
}
//析构
void SLDistroy(SLTYPE* SL)
{
    free(SL->Listdata);
    SL->Listdata = NULL;
    SL->listlen = 0;
    free(SL);
    SL = NULL;
}
//计算顺序表的长度
int SLLength(SLTYPE *SL)
{
    return (SL->listlen);
}
//插入节点
//插入节点就是在第i个位置上插入新的节点；插入后的长度会变成i+1；
//所以插入节点最不太好的地方就是插入位置后面都需要移动
int SLInsert(SLTYPE *SL, int n, DATA data)
{
    int i;
    if (SL->listlen >= MAXLEN)
    {
        cout << "the list is full!!!" << endl;
        return -1;
    }
    if (n<1 || n>SL->listlen +1)
    {
        cout << "the location insert is error!" << endl;
        return -2;
    }
    for (i = SL->listlen; i > n; i --)
    {
        SL->Listdata[i] = SL->Listdata[i-1];

    }
    SL->Listdata[n-1] = data;
    SL->listlen++;
    return 1;
}
//删除第n个节点的内容
//说白了就是让后面的每一个去覆盖前面的即可；
int SLDelete(SLTYPE *SL, int n)
{
    int i;
    if (n<1 || n>SL->listlen)
    {
        cout << "the location delete is error" << endl;
        return -2;
    }
    for (i = n; i < SL->listlen; i++)
    {
        SL->Listdata[i-1] = SL->Listdata[i];
    }
    SL->listlen--;
    return 1;
}
//查找节点
//查找节点是最快的
DATA *SLFindByNum(SLTYPE *SL, int n)
{
    if (n<1 || n>SL->listlen + 1)
    {
        cout << "the location find is error!" << endl;
        return NULL;
    }
    //两种返回的方式；这两种返回的方式说明就是：如果是数组的方式，那么返回的不是地址；
    //或者用地址的方式返回；那么就是+n就是返回的地址；
    //return &(SL->Listdata[n]);
      return SL->Listdata+n-1;
}
//遍历
//遍历是比较简单的，这里就不写了，就是一个for循环就行了，没什么技术含量

int main()
{
    SLTYPE* SL = (SLTYPE*)calloc(1, sizeof(SLTYPE));
    SLInit(SL);
    int i = 0;
    for (; i < 10; i++)
    {
        DATA data;
        data.age = i;
        SLInsert(SL, SL->listlen + 1, data);
    }
    SLDelete(SL, 8);
    DATA* returndata = SLFindByNum(SL, 8);
    cout << "the age is " << returndata->age << endl;
    cout << "==================================" << endl;
    for (i = 0; i < SL->listlen; i++)
    {
        cout << "the age is " << SL->Listdata[i].age << endl;
    }
    SLDistroy(SL);

    return 0;
}