顺序表---C语言

基础概念

顺序表示

采用顺序存储是表示线性表最简单的方法

• 将线性表中的元素依次存储在一片相邻的存储区域中
• 元素之间逻辑上的相邻关系通过元素在计算机物理位置上的相邻关系来表示
• 逻辑上相邻 = 存储位置相邻
• 顺序表示的线性表也成 顺序表

存储结构

线性表的首地址或基地址

-顺序表中k0的存储位置 loc（k0）

顺序表的实现

以数组为基础实现线性表
考虑到线性表元素的变化，创建一个大数组，表示元素连续存在数组前一段：

• 需要记录表中实际元素个数
• 连续存放给删除操作带来不便
• 数组固定大小可能导致插入操作失败

顺序表的存储示意图

算法分析与评价

• 在有n个元素的线性表里下标为i的元素前插入一个元素需要移动n-i个元素，删除下标为i的元素需要移动n-i-1个元素
  

• 插入的平均移动次数：
  

• 删除的平均移动次数：
  

可以看出，在顺序表中进行一次插入或删除操作，平均需要移动大约一半的元素

顺序表插入和删除操作的平均时间代价和最坏时间代价都是O(n);

• 两种特殊情况：表后端插入/删除的时间代价为O(1)
• 定位：一次定位平均需要和n/2个元素比较，时间代价为O(n)
• 特殊情况：如果顺序表中的元素按照值得升序（降）序排列，则使用二分法使得定位操作的时间代价减少到O(log2n)

代码实现

#include <stdio.h>
#include <stdlib.h>

typedef int DataType;
struct SeqList
{
	int MAXNUM;			// 顺序表中最大元素的个数
	int n;				// 存放线性表中元素的个数 n<=MAXNUM
	DataType *element;	// element[0],element[1]...element[n-1] 存放线性表中的元素
};
typedef struct SeqList * PSeqList;

//创建空顺序表
PSeqList createNullList_seq(int m)
{
	PSeqList palist;
	palist = (PSeqList)malloc(sizeof(struct SeqList));
	if(palist != NULL){
		palist->element = (DataType*)malloc(sizeof(DataType)*m);
		if(palist->element != NULL){
			palist->MAXNUM = m;
			palist->n = 0;			// 空表长度为 0
			return palist;
		}else{
			free(palist);			// 存储分配失败
		}
	}
	printf("Out of space.\n");		// 存储分配失败
	return NULL;
}

// 判断线性表是否为空
// 若为空返回1，否则返回0
int isNull_seq(PSeqList palist)
{
	return (palist->n == 0);
}

// 查询顺序表中某元素的下标
int locate_seq(PSeqList palist, DataType x)
{
	for(int q=0;q<palist->n;q++)
	{
		if(palist->element[q] == x)
			return q;
	}
	return -1;
}

// 顺序表插入 指定下标 p 的后面
// p:下标  x: 插入的值
int insertPre_seq(PSeqList palist, int p, DataType x)
{
	int q;
	// 判断是否溢出（也就是是不是存满了）
	if(palist ->n >= palist->MAXNUM )	
	{
		printf("Overflow!");
		return 0;
	}

	// 下标 p 不存在判断
	if(p<0 || p>palist->n)
	{
		printf("Not Exist!\n");
		return 0;
	}

	for(q = palist->n-1;q>=p;q--)
		palist -> element[q+1] = palist ->element[q];
	palist->element[p] = x;
	palist->n = palist->n+1;
	return 1;
}

// 顺序表插入 指定下标p的后面
// p:下标  x: 插入的值
int insertPost_seq(PSeqList palist, int p, DataType x)
{
	int q;
	// 判断是否已经存满 满了则溢出
	if(palist->n >= palist->MAXNUM)
	{
		printf("Overflow!");
		return 0;
	}

	// 判断下标p是否存在
	if(p<0 || p>palist->n)
	{
		printf("Not Exist!\n");
		return 0;
	}

	for(q=palist->n-1;q>p;q--)
		palist->element[q+1]=palist->element[q];
	palist->element[p+1] = x;
	palist->n = palist->n+1;

	return 1;
}

// 删除指定下标的元素
int deleteP_seq(PSeqList palist,int p)
{
	int q;

	// 判断下标p是否有效
	if(p<0 || p>palist->n)
	{
		printf("Not Exist!\n");
		return 0;
	}
	
	for(q=p;q<palist->n-1;q++)
		palist->element[q] = palist->element[q+1];	// 删除元素之后的元素均向前移一个位置
	palist->n = palist->n-1;	// 元素个数减一

	return 1;
}

// 输出顺序表内容
void print_seq(PSeqList palist)
{
	printf("-----输出顺序表---------\n");
	printf("存储元素数量：%d\n",palist->n);
	printf("最多存储数量：%d\n",palist->MAXNUM);

	printf("\n");

	printf("下标  值\n");
	for(int i=0;i<palist->n;i++)
	{
		printf(" %d ",i);
		printf("   %d\n",palist->element[i]);
	}

}


int main(){
	PSeqList pList;
	// 创建空顺序表
	pList = createNullList_seq(1000);
	//判断是否为空
	if(isNull_seq(pList) == 1)
	{
		printf("Empty list.\n");
	}
	
	//插入数据
	insertPre_seq(pList, 0, 2);
	insertPre_seq(pList, 0, 666);
	insertPre_seq(pList, 1, 123);
	insertPost_seq(pList,0, 520);
	insertPost_seq(pList,2, 1314);
	
	// 输出顺序表
	print_seq(pList);

	// 打印指定值的下标
	printf("520的下标为：%d\n",locate_seq(pList, 520));

	// 删除下标为3的值
	deleteP_seq(pList, 3);

	// 输出顺序表
	print_seq(pList);

	return 0;
}