**
数据结构–顺序表
#顺序表的概念
顺序表的特点:在逻辑上是连续的,在物理存储空间商也是连续的。在这里我们可以将他理解为数组。顺序表中存储的数据元素必须从空间的首位置开始存储,而且必须连续存放,中间不能有空的位置。
顺序表的实现声明
- 结构声明
```c
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
typedef int Datatype;
typedef struct SqList
{
Datatype *data;//指向存储空间的指针
int length;//已经存储的元素个数
int size;//当前空间的大小,单位是元素的个数
}SqList;
//操作方法的声明
//初始化顺序表
bool InitSqList(SqList *sq,int init_size=10);
//头插入
bool InsertofFront(SqList *sq,Datatype value);
//特定位置的插入
bool InsertofPos(SqList *sq,Datatype value,int pos);
//尾插
bool InsertofRear(SqList *sq,Datatype value);
//求长度
int LengthSqList(SqList *sq);
//销毁
方法实现:
#include"SqList.h"
static bool Isfull(SqList *sq)
{
return sq->length=sq->size;
}
static bool AppendSpace(SqList *sq)//空间扩容
{
int size=sq->size==0?10:sq->size*2;
Datatype *new_space=(Datatype *)malloc(sizeof(Datatype)*size);
if(new_space==NULL) return false;
for(int i=0;i<sq->size;i++)
{
new_space[i]=sq->data[i];
}
free(sq->data);
sq->data=new_space;
sq->size=size;
return true;
}
bool InitSqList(SqList *sq,int init_size)
{
if(sq == NULL || init_size <= 0 ) return false;//确保该顺序表是否存在
sq->data = (Datatype* )malloc(init_size * sizeof(Datatype));
if(sq->data == NULL) return false;
sq->length = 0;
sq->size = init_size;
return true;
}
bool DestorySqList(SqList *sq)
{
if(sq == NULL) return false;
free(sq->data);
sq->data = NULL;//防止野指针出现
sq->length=sq->size=0;
return true;
}
bool insert(SqList *sq,Datatype value,int pos)
{
if(sq==NULL) return false;
if(pos<0||pos>sq->length)
return false;
if(Isfull(sq)&&!AppendSpace(sq)) return false;
for(int i=sq->length;i>pos;--i)
{
sq->data[i]=sq->data[i-1];
}
sq->data[pos]=value;
sq->length++;
return true;
}
bool InsertofFront(SqList *sq,Datatype value)
{
return InsertofPos(sq,value,0);
}
bool InsertofRear(SqList *sq,Datatype value)
{
if(sq==NULL) return false;
return InsertofPos(sq,value,sq->length);//调用函数的过程;1.压参2.调用3.返回
}
int LengthSqList(SqList *sq)
{
if(sq==NULL) return false;
return sq->length;
}
bool DeleteofPos(SqList *sq,int pos)
{
if(sq==NULL) return false;
for(int i=pos;i<sq->length-1;++i)
{
sq->data[i]=sq->data[i+1];
}
sq->length--;
return true;
}
bool DeleteofFront(SqList *sq)
{
return DeleteofPos(sq,0);
}
bool DeleteofRear(SqList *sq)
{
return DeleteofPos(sq,LengthSqList(sq)-1);
}
bool isEmpty(SqList *sq)
{
if(sq==NULL||sq->length==0)
return true;
return false;
}
注意:1.空间扩容规则,在处理问题时,最好能够分情况处理(初始以2被形式扩充)
2.static使用如果修饰我们的函数,则这个函数就只能在本文件中被调用,其他文件看不到此函数。如果static作为修饰局部变量,那么它的 生存期为整个源程序,其作用域的范围仍在该函数的内部,退出该函数后,尽管变量还继续存在,但是不能使用它。
`