[数据结构与算法]线性表的顺序表示和实现

线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。数据元素是一个抽象的符号，其具体含义在不同的情况下一般不同。

线性表具有以下特点：

1.简单 好实现

2.逻辑上相邻，物理上也相邻

3.插入的时间复杂度为o（n） 尾插的时候时间复杂度为o（1）

4.删除时间复杂度o（n) 尾删除的时间复杂度为o（1）

5.随机访问时间复杂度为o（1） 有数组下标帮忙

线性表结构体设计：

typedef int ELEM_TYPE;

#define INIT_SIZE 10 //默认开始时的空间个数


typedef struct DSQLlist
{
	ELEM_TYPE* data;//用来承接malloc申请的动态内存
	int length;//有效数据长度
	int listsize; //保存当前最大容量个数（以sizeof（ELEM_TYPE））为单位
}DSQlsit, * PDSQlist;

初始化

void Init_sqlist(PDSQlist plist)//struct Sqlist* plist
{
	assert(plist != NULL);
	plist->data = (ELEM_TYPE*)malloc(sizeof(ELEM_TYPE) * INIT_SIZE);
	if (plist == nullptr) {
		exit(EXIT_FAILURE);
	}
	plist->length = 0;
	plist->listsize = INIT_SIZE;
}

在堆区申请 10个初始ELEM_TYPE空间返回给 plist->data?

此时顺序表的长度为 0? ? ?容量大小为INIT_SIZE(10)

按位置插入?

bool Insert_Pos(PDSQlist plist, int pos, int val) {  //pos值为下标
	assert(plist != NULL);   //判满 扩容
    if (pos<0 || pos>plist->length) {
		return false;
	}
	if (IsFull(plist)) {
		Inc(plist);
	}
   
	for (int i = plist->length - 1; i >= pos; i--) {
		plist->data[i + 1] = plist->data[i];
	}
	plist->data[pos] = val;
	plist->length += 1;
	return true;
}

①插入操作需要对pos进行判断pos必须大于0且不能大于plist->length? 若大于length则不满足顺序表逻辑上相邻，物理上也相邻的特点

②进行判满，若顺序表已满则先扩容再进行后续操作

③进行插入操作，若要插入的位置已有数据则需要将pos后的数据整体向后移动一个位置

④插入数据 length+1

按位置删除

bool Del_pos(PDSQlist plist, int pos) {
    assert(plist!=NULL);
?? ?//不需要判满 断言已经对其合法性 进行判断
?? ?for (int i = pos ; i < plist->length - 1; i++) {
?? ??? ?plist->data[i] = plist->data[i + 1];
?? ?}
?? ?plist->length -= 1;
?? ?return true;
}

类比插入操作将

将pos后的所有数据向前移动一个单位覆盖pos位置的数据即可

查找值为val的节点? 找到等于val值的最小节点

int Search(PDSQlist plist, int val) {
    assert(plist!=NULL);
	for (int i = 0; i < plist->length; i++) {
		if (plist->data[i] == val) {
			return i;
		}
	}
	return -1;
}

对plist->data进行遍历 找到下标最小的节点 返回下标

按值删 ?删除这个值出现的第一次的位置

bool Del_val(PDSQlist plist, int val) {
	assert(plist != NULL);
	if (IsEmpty(plist)) {
		return false;
	}
	int pos = Search(plist, val);
	if (pos == -1) {
		return false;
	}
	Del_pos(plist, pos);
}

此处调用Search 返回要删除值的位置再调用 按位置删除Del_pos即可

扩容? 二倍扩容

bool Inc_list(PDSQlist plist) {
assert(plist != nullptr);
	ELEM_TYPE* newdata = NULL;
	newdata =(ELEM_TYPE*)realloc(plist->data, sizeof(ELEM_TYPE) * plist->listsize * 2);
	if (newdata == NULL) {
		return false;
	}
	plist->data = newdata;
	plist->listsize *=  2;
	return true;
}

先申请一个newdata 将realloc申请到的空间返回给newdata 若newdata不为空

则将plist->data指向newdata

realloc申请空间时如果失败则会返回NULL 会导致此前写入的数据丢失?

此时用newdata接收realloc的返回值即使空间申请失败数据值仍保存在plist->data中

其余

//判空
bool IsEmpty(PDSQlist plist) {
	return plist->length == 0;
}

//判满
bool IsFull(PDSQlist plist) {
	return plist->length == plist->listsize;
}

//清空
void Clear(PDSQlist plist) {
	plist->length = 0;
}

//销毁
void Destroy(PDSQlist plist) {
	Clear(plist);
	free(plist->data);
	plist->data = NULL;
}
//打印
void Print(PDSQlist plist) {
	assert(plist != NULL);
	for (int i = 0; i < plist->length; i++) {
		printf("%d ", plist->data[i]);
	}
	printf("\n");
}