数据结构-顺序表的大小

一、固定大小的顺序表的缺陷：

1、不能随着数据的增多而增大

2、收到栈空间的限制

栈的大小：window下是1M

二、可变大小的顺序表的设计

1、什么是存储单元

cpu访问内存（通过地址）

8个二进制位称为一个存储单元（一个字节）

2、内存的划分

代码区、数据区、mallocfree堆、栈区（从上到下）

栈区：凡是函数内定义的变量都在栈区（除了静态局部变量在数据区）

数据区：在函数之外定义的变量还有静态变量都在数据区

代码区：存放代码的

堆区：通过内存管理函数，动态（在程序运行的过程中）的申请? ?（申请空间malloc? ?calloc? ? realloc 释放空间：free）

3、初始化线性表

申请为可改变大小的内存空间

注意：

形参无法改变实参的大小（使用指针/或者别名）

申请空间=元素类型的大小*元素个数

使用指针一定要判空

如果申请的内存空间为空，申请失败，退出程序

4、顺序表的打印和查询

void Printfseqlist(SeqList *p)
{
	assert(p != NULL);
	for (int i = 0; i < p->rongliang; i++)
	{
		printf("%5d", p->date[i]);
	}
	printf("\n");
}

int FindValue(SeqList* p, int val)
{
	assert(p != NULL);
	int q = -1;
	for (int i = 0; i < p->daxiao ; i++)
	{
		if (p->date[i] == val)
		{
			q=i;
			break;
		}
	}
	return q;

}

5、按指定位置在顺序表中插入数据

需要的元素：顺序表、位置、val（插入的值）

bool InsertTtem(SeqList*p,int post,int val)
{
	assert(p != NULL);
	if (post<0 || post > p->daxiao)
	{
		return false;
	}
	for (int i = p->daxiao-1; i >= post; --i)
	{
		p->date[i + 1] = p->date[i];
	}
	p->date[post] = val;
	p->daxiao += 1;
	return true;

}
bool Push_back(SeqList* p, int val)
{
	assert(p != NULL);
	InsertTtem(p, p->daxiao, val);

}
bool Push_front(SeqList* p, int val)
{
	assert(p != NULL);
	InsertTtem(p, 0, val);

}

6、顺序表增容

1）申请原来空间的二倍malloc

2)将原来的数据拷贝过来

3）释放原有空间

4）将原来的date指向新开辟的空间

5）改变容量（p->rongliang）大小

//为当前顺序表增容
bool Inc_Capacity(SeqList* p)
{
	assert(p != NULL);
	ElemType*newdate = (ElemType*)malloc(SEQ_INC_SIZE * sizeof(int)* p->rongliang);
	if (NULL == newdate)
	{
		return false;
	}
	for (int i = 0; i < p->daxiao; ++i)
	{
		newdate[i] = p->date[i];
	}
    //使用移动函数
	//memmove(newdate, p->date, sizeof(ElemType) * p->daxiao);
	free(p->date);
	p->date = newdate;
	p->rongliang *= 2;
}

realloc的操作步骤

int *p=(int *)malloc(sizeof(int)*5);

for(int i=0;i<5;i++)

{p[i]=i}

p=(int*)realloc(p,sizeof(int)*10);

free(p);? ?

1）、开辟新空间

2）、把p所指向的内容转移到新空间

3）、free p

4）、把新的空间给p

7、顺序表中删除数据

//删除指定位置的数据
bool EraseItem(SeqList* p, int post)
{
	assert(p != NULL);
	if (post<0 || post>p->daxiao-1)
	{
		return false;
	}
	for (int i = post; i < p->daxiao; ++i)
	{
		p->date[i] = p->date[i + 1];
	}
	p->daxiao -=1;
	return true;
}
//尾删
void Pop_Back(SeqList* p)
{
	assert(p != NULL);
	EraseItem(p, p->daxiao-1);
}
//头删
void Pop_Frond(SeqList* p)
{
	assert(p != NULL);
	EraseItem(p, 0);
}
//删除数据表中的元素

bool Remove(SeqList* p, int val)
{
	assert(p != NULL);
	return EraseItem(p, FindValue(p, val));
}

删除表中元素步骤：

1）、先找到数据所在位置

2）、删除所在位置的顺序

8、销毁函数和重置为空

重置为空：

p->daxiao为0，就是空表，原有数据可能会残留在堆中，再次调用，数据会被覆盖