ACM刷题之路（十二）数据结构——顺序表
这周已经是第九周了，为了期末的时候能够兼顾其他课程的复习，所以提早对数据结构这门课进行回顾总结。
数据结构忽略前面两章的C语言基础(有机会以后再补)，直接从第三章最简单的线性表开始。
线性表的第一种结构是 顺序表 。
首先定义一个结构体，
#define MAXX 1000
typedef int lei;
struct ss
{
lei data[MAXX];
int len;
};之所以用#define 定义MAXX ，是因为 需要改变 这个线性表大小的时候 只需要在这个语句改变大小即可 不需要再从整段代码再逐一修改。
typedef的意思是取别名。把lei这个小名 给int，作用同上 修改线性表数据类型的时候可以直接改动
这个结构体里面有两部分，一部分是数据，第二部分是长度，初始化为-1.
（ps：为什么从-1开始，因为数组是从0开始的）
顺序表根据《数据结构》这本书 需要会写初始化、指定位置插入、查找、删除、取长度、判断是否为空的函数。
首先是初始化函数。
初始化一个顺序表，只要用c++的new函数 ，new一个顺序表就可以，把长度初始化为-1，然后返回首地址就行了。
ss *chushihua()
{
ss *L;
L=new ss;
L->len=-1;
return L;
}第二个是查找函数，查找函数只要按照o~len的顺序遍历过去，凡是找到就返回，找不到就返回一个负数，思路简单粗暴，时间复杂度是o(n)。
ps:不考虑有数据重复的情况.
int find(ss *L,lei X)
{
for(int i=0;i<=L->len;i++)
{
if(L->data[i]==X) return i;
}
return -1;
}第三个是插入函数。
插入只需要判断是否插入成功就可以，所以用bool类型作为返回值。
需要三个参数，顺序表的首地址、插入的数据、插入的位置。
需要考虑两种极端情况：第一种顺序表已经满了，第二种插入的位置越界。
否则就正常插入，把插入位置的后面元素往后移，再在插入的位置插入该插的数，然后让顺序表的长度+1即可。
bool charu(ss* L,lei shu,int weizhi)
{
if(L->len==MAXX-1)
{
cout<<"顺序表已满"<<endl;
return false;
}
if(weizhi<0||weizhi>L->len+1)
{
cout<<"插入位置错误"<<endl;
return false;
}
for(int i=L->len;i>=weizhi;i--)
{
L->data[i+1]=L->data[i];
}
L->data[weizhi]=shu;
L->len++;
return true;
}第四个是删除函数。
同上为bool类型，参数为顺序表的首地址和需要删除的位置。
考虑一种极端情况，如果需要删除的位置为空。
删除只需要把后面的元素往前移，覆盖掉前面的元素就可以，在把长度-1.
ps：此时L->[len]的数据还是存在，但是不用管。
bool shanchu(ss *L,int weizhi)
{
if(weizhi<0||weizhi>L->len)
{
cout<<"位置越界"<<endl;
return false;
}
for(int i=weizhi;i<=L->len;i++)
{
L->data[i]=L->data[i+1];
}
L->len--;
return true;
}最后一个最简单，就是判断是否为空。
只要判断他的长度是否为初始化的-1即可。
bool empty(ss *L)
{
if(L->len==-1) return true;
return false;
}所以给出总的代码：
#include<iostream>
#include<algorithm>
#include <cstring>
using namespace std;
#define MAXX 1000
typedef int lei;
struct ss
{
lei data[MAXX];
int len;
};
ss *chushihua()
{
ss *L;
L=new ss;
L->len=-1;
return L;
}
int find(ss *L,lei X)
{
for(int i=0;i<=L->len;i++)
{
if(L->data[i]==X) return i;
}
return -1;
}
bool charu(ss* L,lei shu,int weizhi)
{
if(L->len==MAXX-1)
{
cout<<"顺序表已满"<<endl;
return false;
}
if(weizhi<0||weizhi>L->len+1)
{
cout<<"插入位置错误"<<endl;
return false;
}
for(int i=L->len;i>=weizhi;i--)
{
L->data[i+1]=L->data[i];
}
L->data[weizhi]=shu;
L->len++;
return true;
}
bool shanchu(ss *L,int weizhi)
{
if(weizhi<0||weizhi>L->len)
{
cout<<"位置越界"<<endl;
return false;
}
for(int i=weizhi;i<=L->len;i++)
{
L->data[i]=L->data[i+1];
}
L->len--;
return true;
}
bool empty(ss *L)
{
if(L->len==-1) return true;
return false;
}
int main()
{
ss *L;
L=chushihua();
charu(L,1,0);
charu(L,2,1);
cout<<"1在第"<<find(L,1)<<"个位置"<<endl;
shanchu(L,1);
shanchu(L,0);
cout<<"下面判断是否为空，空为1"<<endl;
cout<<empty(L)<<endl;
return 0;
}顺序表不难，明天复习链表。
腾讯云开发者
