文章目录
静态顺序表和动态顺序表的异同
相同
:
内存空间连续,数据顺序存储
占用内存空间不同
:
静态顺序表是在栈上开辟的,随着函数调用的结束,系统会自动回收内存,不存在内存泄漏
动态顺序表是在堆区开辟内存,实现动态内存管理,根据你的需求去开辟
动态顺序表的实现
头文件
#include<stdio.h>
#include <string.h>
#include<stdlib.h>
#include<assert.h>
定义结构体
注意命名方式,采用驼峰法
结构体里包含要插入的数据,计数器,容量大小(开辟空间)
宏定义有利于管理代码
#define N 10
typedef int SQDataType;
struct SeqList
{
SQDataType* a;
int sz;
int capacity;
};
初始化
void SeqListInit(SL* s1)
{
s1->a = NULL;
s1->sz = 0;
s1->capacity = 0;//0*2还是0
}
打印顺序表
void SeqListPrint(SL* s1)
{
for (int i = 0; i < s1->sz; i++)
{
printf("%d ", s1->a[i]);
}
printf("\n");
}
在这里插入代码片
实现增删查改
尾插
void SeqListPushBack(SL* s1, SQDataType x)
{
SeqListCheckCapacity(s1);//判断是否需要扩容
s1->a[s1->sz] = x;
s1->sz++;
}
头插
void SeqListPushFront(SL* s1, SQDataType x)
{
SeqListCheckCapacity(s1);
int end = s1->sz - 1;
while (end >= 0)
{
s1->a[end + 1] = s1->a[end];
end--;
}
s1->a[0] = x;
s1->sz++;
}
尾删
void SeqListPopBack(SL* s1)
{
assert(s1->sz > 0);
s1->sz--;
}
头删
void SeqListPopFront(SL* s1)
{
assert(s1->sz > 0);
int start = 1;//计录
while (start < s1->sz)
{
s1->a[start - 1] = s1->a[start];
start++;
}
s1->sz--;
}
删掉某个位置的数据
void SeqListRemove(SL* s1, int pos)
{
assert(pos < s1->sz);
int start = pos + 1;
while (start < s1->sz)
{
s1->a[start - 1] = s1->a[start];
start++;
}
s1->sz--;
}
在某个位置插入数据
void SeqListInsert(SL* s1,int pos, SQDataType x)
{
assert(pos < s1->sz);
SeqListCheckCapacity(s1);
int end = s1->sz - 1;
while (end >= pos)
{
s1->a[end + 1] = s1->a[end];
--end;
}
s1->a[pos] = x;
s1->sz++;
}
查找某个位置的下标
int SeqListFind(SL* s1, SQDataType x)
{
for (int i = 0; i < s1->sz; i++)
{
if (s1->a[i] == x)
return i;
}
return -1;
}
修改某个位置的数据
void SeqListModity(SL* s1, int pos, SQDataType x)
{
assert(pos < s1->sz);
s1->a[pos] = x;
}
扩容
void SeqListCheckCapacity(SL* s1)
{
if (s1->sz == s1->capacity)
{
int newcapacity = s1->capacity == 0 ? 4 : s1->capacity * 2;
SQDataType* tmp = (SQDataType*)realloc(s1->a, newcapacity * sizeof(SQDataType));
if (tmp == NULL)
{
printf("realloc is fail\n");
exit(-1);
}
else
{
s1->a = tmp;
s1->capacity = newcapacity;
}
}
}
销毁顺序表
void SeqListDestory(SL* s1)
{
free(s1->a);
s1->sz = s1->capacity = 0;
s1->a = NULL;
}