线性表的顺序存储方式之顺序表

线性表的基本操作

初始化表。构造空的线性表

void InitList(SeqList *L);

求表长，返回线性表L的长度，即L中数据元素的个数

int Length(SeqList L);

按值查找操作，在表L中查找具有给定关键字值的元素

int LocateElem(SeqList L,ElemType e);

按位查找操作，获取表L中第i个位置的元素的值

int GetElem(SeqList L,int i);

插入操作,在表L中的第i个位置上插入指定元素e

bool ListInsert(SeqList *L,int i,ElemType e);

删除操作，在删除表L中第i个位置的元素，并用e返回删除元素的值

bool ListDelete(SeqList *L,int i,ElemType *e);

输出操作，按前后顺序输出线性表L的所有元素值

void PrintList(SeqList L);

判空操作，若L为空表，则返回true，否则返回false

bool Empty(SeqList L);

静态分配

typedef struct{
	ElemType data[MAXSIZE]; //静态一维数组
	int length;
}SeqList;

动态分配

结构体内有一个ElemType类型的指针，指向动态开辟的空间；另外增加了一项最大容量Maxsize，用来动态扩容

typedef struct{
	ElemType *data; // 动态一维数组
	int Maxsize;	// 最大容量
	int length;	// 当前个数 
}SeqList;

新增动态扩容函数

void IncreaseSize(SeqList *L,int len);

void IncreaseSize(SeqList *L,int len)
{
    ElemType *p = L->data;
    L->data = (ElemType *)malloc(sizeof(int)*(L->Maxsize+len)); 
    for(int i=0;i<L->length;i++)
        L->data[i] =  p[i];
    L->Maxsize = L->Maxsize + len;
    free(p);
}

在InitList初始化函数中需要申请一片堆内存用来存储数据

void InitList(SeqList *L)
{
    L->data = (ElemType *)malloc(sizeof(ElemType)*InitSize); 
    L->length = 0;
    L->Maxsize = InitSize;
}

另外申请的堆内存需要手动释放，需添加销毁函数

void DestroyList(SeqList *L);

void DestroyList(SeqList *L)
{
    if(L!=NULL)
    {
        free(L);
        L = NULL;
    }
}

静态分配的完整实现

//顺序表的实现 - 静态方法
//by Ingran

#include <stdio.h>
#include <string.h>

#define ElemType int
#define MAXSIZE 10 //定义线性表的最大长度 
typedef struct{
	ElemType data[MAXSIZE];
	int length;
}SeqList;


// 初始化表。构造空的线性表 
void InitList(SeqList *L);

// 求表长，返回线性表L的长度，即L中数据元素的个数
int Length(SeqList L);

// 按值查找操作，在表L中查找具有给定关键字值的元素
int LocateElem(SeqList L,ElemType e);

// 按位查找操作，获取表L中第i个位置的元素的值
int GetElem(SeqList L,int i);

// 插入操作,在表L中的第i个位置上插入指定元素e
bool ListInsert(SeqList *L,int i,ElemType e);

// 删除操作，在删除表L中第i个位置的元素，并用e返回删除元素的值
bool ListDelete(SeqList *L,int i,ElemType *e);

// 输出操作，按前后顺序输出线性表L的所有元素值
void PrintList(SeqList L);

// 判空操作，若L为空表，则返回true，否则返回false
bool Empty(SeqList L); 


int main()
{
	SeqList L;
	InitList(&L);
	ListInsert(&L,1,1);
	ListInsert(&L,1,2);
	ListInsert(&L,1,3);
	ListInsert(&L,1,4);
	ListInsert(&L,9,5);
	PrintList(L);
	
	ElemType e=-1;
	bool sta = ListDelete(&L,0,&e);
	printf("%d\n",e);
	PrintList(L);
	
	int n = GetElem(L,1);
	printf("%d\n",n);
	
	return 0;
} 

void InitList(SeqList *L)
{
	memset(L->data,0x00,sizeof(int)*MAXSIZE);
	L->length=0;
}

int Length(SeqList L)
{
	return L.length;	
}

bool ListInsert(SeqList *L,int i,ElemType e)
{
	if(L->length >= MAXSIZE)
		return false;
	if(i < 1 || i > L->length+1)
		return false;
		
	
	//插入队尾时间复杂度为O(1)		插入队头时间复杂度为O(n)		平均时间复杂度为O(n/2)==O(n) 
	for(int j=L->length;j>=i;j--)
	{
		L->data[j] = L->data[j-1];
	}
	L->data[i-1] = e;
	L->length++;
	return true;
}

bool ListDelete(SeqList *L,int i,ElemType *e)
{
	if(i<1 || i>L->length)
		return false;
	
	//删除队尾时间复杂度为O(1)		删除队头时间复杂度为O(n)		平均时间复杂度为O(n) 
	*e = L->data[i-1];
	for(int j=i;j<L->length;j++)
		L->data[j-1] = L->data[j];
	L->length--;
	return true;
}

 
int LocateElem(SeqList L,ElemType e)
{
	//循环1次  最好时间复杂度O(1)	循环length-1次 最坏时间复杂度O(n)		平均时间复杂度为O(n)    
	for(int i=0;i<L.length;i++)
		if(L.data[i]==e)
			return i+1;
	return 0;
}

int GetElem(SeqList L,int i)
{
	if(i<1 || i>L.length)
		return -1;
	return L.data[i-1];
}

bool Empty(SeqList L)
{
	if(L.length==0)
		return true;
	return false;
}

void PrintList(SeqList L)
{
	for(int i=0;i<L.length;i++)
		printf("%d ",L.data[i]);
	printf("\n");
}