一、顺序表基础概念讲解
所谓的顺序表，也就是，想对于那种所谓的链表存储，我们可以从第一个节点，就可以通过地址的移动，访问到任何一个节点；
那么由这个定义，我们就有了两种开辟顺序表的方式；一种是栈内存，一种是堆内存；如果是栈内存的话，那么就是直接初始化的时候，在栈上开辟一块内存；如果是堆内存的话，那么就是初始化的时候，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;
}
