数据结构之顺序表的初步认识以及增删改查使用

        顺序表是线性表的一种，还有一种是链表，顺序表特点是必须依次存放，不可以跳跃式存放，顺序表与链表不同之处在于顺序表在物理上相邻，可以简单的理解为它存放的数据地址相邻，而链表则不是它是数据结构中的重要组成部分，它由两部分元素构成，一种是保存的数据，另一种是数据的下表，这和我们以前学过的数组很相似，顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。使用它是需要用结构体进行定义：

-

typedef struct 
{
	int *elem;//指向动态内存的指针
	int length;//有效数据个数
	int listsize;//总单元个数
}DSeqList,*PDSeqList;

我们对顺序表使用时一般进行初始化，增加数据，删除数据，修改数据，查找数据，清空顺序表等几个操作，下面我给大家详细的讲一下这一系列操作。

首先是我们需要做的函数声明：

void InitDSeqList(PDSeqList ps)
{
	assert(ps != NULL);

	ps->elem = (int *)malloc(INITSIZE *sizeof(int));
	ps->length = 0;
	ps->listsize = INITSIZE;
}

static bool IsFull(PDSeqList ps)
{
	return ps->length == ps->listsize;
}

//将ps的容量扩大到原来的2倍
static void Inc(PDSeqList ps)
{
	ps->elem = (int *)realloc(ps->elem,ps->listsize*2*sizeof(int));
	ps->listsize *= 2;
}

//将val插入在ps表中的pos位置
bool Insert(PDSeqList ps,int val,int pos)//O(n)
{
	if(pos<0 || pos>ps->length)
	{
		return false;
	}
	if(IsFull(ps))
	{
		Inc(ps);
	}

	for(int i=ps->length-1;i>=pos;i--)
	{
		ps->elem[i+1] = ps->elem[i];
	}
	ps->elem[pos] = val;
	ps->length++;

	return true;
}

bool Insert_begin(PDSeqList ps,int val)//O(n)
{
	return Insert(ps,val,0);
}

bool Insert_end(PDSeqList ps,int val)//O(1)
{
	return Insert(ps,val,ps->length);
}

//查找ps中第一个key的下标
int Search(PDSeqList ps,int key)
{
	for(int i=0;i<ps->length;i++)
	{
		if(ps->elem[i] == key)
		{
			return i;
		}
	}
	return -1;
}

//删除ps中的第一个key
bool Delete(PDSeqList ps,int key)
{
	int index = Search(ps,key);
	return DeletePos(ps,index);
}

//删除ps中第pos位置的数据
bool DeletePos(PDSeqList ps,int pos)
{
	if(pos<0 || pos>=ps->length)
	{
		return false;
	}
	for(int i=pos;i<ps->length-1;i++)
	{
		ps->elem[i] = ps->elem[i+1];
	}
	ps->length--;

	return true;
}

bool IsEmpty(PDSeqList ps)
{
	return ps->length == 0;
}

//清空数据
void Clear(PDSeqList ps)
{
	ps->length = 0;//ps->length == (*ps).length
}

//销毁整个结构
void Destroy(PDSeqList ps)
{
	free(ps->elem);//1
	ps->elem = NULL;//2
	ps->length = 0;//3
	ps->listsize = 0;//4
	//ps = NULL;//5,没有意义
}

int GetLength(PDSeqList ps)
{
	return ps->length;
}

void Show(PDSeqList ps)
{
	for(int i=0;i<ps->length;i++)
	{
		printf("%d ",ps->elem[i]);
	}
	printf("\n");
}

以上就是顺序表的初步认识以及基本操作，顺序表相当对来说还是比较简单，了解基本结构以后可以轻松掌握。