|
目录
1.何为顺序表？
顺序表的特性：
顺序表的定义
本质 区别：所占的内存位置不同，
静态顺序表
动态顺序表
?向顺序表中插入元素
1.何为顺序表？
在计算机内部存储一张线性表，（线性结构的数表），最方便简单的方法就是用一组连续地址的内存单元来存储整张线性表----存储结构叫做顺序存储结构----这种结构下的线性表就叫做顺序表
顺序表的特性：
- 有唯一的表名来标识该顺序表
- 连续地址内存
- 数据顺序存放，元素之间有先后
数组也具有其特性，所以数组也是顺序表
顺序表的定义
- ?静态顺序表
- 动态顺序表
本质 区别：所占的内存位置不同，
对于静态顺序表，内存开辟在静态区，也就是函数栈，这个区域的内存空间会随着函数调用的完成而被系统收回。
对于动态顺序表，其内存开辟在动态区，也就是堆区，不会被系统收回，需要程序主动释放? ? ? ??
静态顺序表
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
typedef int ElemType;//这样定义更方便修改类型
#define MaxSize 10
int main()
{
struct stu {
ElemType a[MaxSize];
int size;//元素个数，（顺序表长度）；
};
return 0;
}
动态顺序表
typedef int ElemType;
typedef struct stu {
ElemType* a;
int size;//顺序表长度
int capacity;//容量
}s,SeqList;
void InitSeqList(SeqList* s)//顺序表初始化
{
s->a =(ElemType*) malloc(sizeof(ElemType) * 4);
s->capacity = 4;
s->size = 0;
}
- 定义一个类型SeqList、它是一个结构体，其成员包括:指向顺序表的首地址a、顺序表中表的长度(表中元素个数)长度size、顺序表的存储空间容量(占据内存大小，以大小(ElemType)为单位
- 通过调用一个函数InitSeqList()实现动态生成一张顺序表。函数initSqlist()的参数是一个SeqList类型的指针变量，因此可以在函数InitSeqList()中直接对顺序表进行操作。
?向顺序表中插入元素
后面插入：
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<malloc.h>
typedef int ElemType;
#define MaxSize 10
//int main()
//{
// struct stu {
// ElemType a[MaxSize];
// int size;//元素个数，（顺序表长度）；
// };
//
// return 0;
//}
typedef struct SeqList {
ElemType* a;
int size;//顺序表长度
int capacity;//容量
}SeqList, SL;
void InitSeqList(SL* s)//初始化
{
s->a =(ElemType*) malloc(sizeof(ElemType) * 4);
s->capacity = 4;
s->size = 0;
}
void SeqListprint(SeqList* s)//打印
{
for (int i = 0; i < s->size; i++)
{
printf("%d ", s->a[i]);
}
printf("\n");
}
void SeqListCheckCapacity(SeqList* s)//检查容量是否不够
{
if (s->size >= s->capacity)
{
s->capacity *= 2;
s->a = (ElemType*)realloc(s->a, sizeof(ElemType) * s->capacity);
}
}
void SeqListInsert(SeqList* s,ElemType x)//后面插入
{
SeqListCheckCapacity(s);
s->a[s->size] = x;
s->size++;
}
test1()
{
SL m;
InitSeqList(&m);
SeqListInsert(&m, 2);
SeqListInsert(&m, 2);
SeqListInsert(&m, 2);
SeqListprint(&m);
}
int main()
{
test1();
return 0;
}
从中间插入：
void SeqListInsert(SeqList* s, int pos, ElemType x)
{
SeqListCheckCapacity(s);
int end = s->size - 1;
while (end >= pos)
{
s->a[end + 1] = s->a[end];
end--;
}
s->a[pos] = x;
s->size++;
}
顺序表中删除元素：
void SeqListErase(SeqList* s, int pos)
{
int start = pos;
while (start<s->size - 1)
{
s->a[start] = s->a[start + 1];
start++;
}
s->size--;
}
|