24/07/08数据结构(2.1203)顺序表实现
size属于结构体的作用域
如果要访问一个结构体的指针用->
如果要访问一个结构体的变量用. 点操作
#include
#include
#include
#include"seqlist.h"
//typedef struct seqList{
// SLDataType* _data; //需要动态开辟的数组
// size_t _size; //有效元素的个数
// size_t _capacity; //挡枪可以存放的最大元素个数
//}seqList;
void initSeqList(seqList* sl){
sl->_data = NULL;
sl->_size = sl->_capacity = 0;
}
//尾插一个数据o(1)
void pushBack(seqList* sl, SLDataType val){
//检查容量
checkCapacity(sl);
sl->_data[sl->_size] = val;
++sl->_size;
}
void checkCapacity(seqList* sl){
//如果元素个数和容量相同,说明空间满了,需要扩容空间
if (sl->_size == sl->_capacity){
int newCapacity = sl->_capacity == 0 ? 1 : 2 * sl->_capacity;
//开一个更大的空间,拷贝已有数据,释放原有空间
SLDataType* tmp = (SLDataType*)malloc(sizeof(SLDataType)* newCapacity);
memcpy(tmp, sl->_data, sizeof(SLDataType)* sl->_size);
free(sl->_data);
//更新
sl->_data = tmp;
sl->_capacity = newCapacity;
}
}
void printSeList(seqList* sl){
for (int i = 0; i < sl->_size; ++i){
printf("%d", sl->_data[i]);
}
printf("\n");
}
void popBack(seqList* sl){
if (sl == NULL)
return;
if (sl->_size>0)
sl->_size--;
}
//头插 给顺序表的第一个位置插入元素o(n)
//一般不进行头插:效率低
void pushFront(seqList* sl, SLDataType val){
if (sl == NULL)
return;
//0.检查容量
checkCapacity(sl);
//1.移动元素:从后向前移动
int end = sl->_size;
while (end > 0){
sl->_data[end] = sl->_data[end - 1];
--end;
}
//2.头插
sl->_data[0] = val;
sl->_size++;
}
//头删: 移动元素:[1,size)全部向前移动一个位置
void popFront(seqList* sl){
if (sl == NULL || sl->_size == 0)
return;
int start = 1;
while (start < sl->_size){
sl->_data[start - 1] = sl->_data[start];
++start;
}
--sl->_size;
}
//插入
void insert(seqList* sl, int pos, SLDataType val){
//检查容量
if (sl == NULL)
return;
checkCapacity(sl);
//移动元素
int end = sl->_size;
while (end > pos){
sl->_data[end] = sl->_data[end - 1];
--end;
}
//插入数据
sl->_data[pos] = val;
//更新
sl->_size++;
}
void test(){
seqList sl;
initSeqList(&sl);
pushBack(&sl, 1);
pushBack(&sl, 2);
pushBack(&sl, 3);
pushBack(&sl, 4);
pushBack(&sl, 5);
insert(&sl, 1, 10);
insert(&sl, 2, 20);
printSeList(&sl);
insert(&sl, 0, -1);
printSeList(&sl);
insert(&sl, sl._size, 3);
printSeList(&sl);
}
int main(){
test();
system("pause");
return 0;
}
完整的代码:
.h头文件
typedef int SLDataType;
typedef struct seqList{
SLDataType* _data; //需要动态开辟的数组
size_t _size; //有效元素的个数
size_t _capacity; //当前可以存放的最大元素个数
}seqList;
void initSeqList(seqList* sl);
//尾插一个数据
void pushBack(seqList* sl, SLDataType val);
void checkCapacity(seqList* sl);
void printSeList(seqList* sl);
void popBack(seqList* sl);
.c文件
#include
#include
#include
#include"seqlist.h"
//typedef struct seqList{
// SLDataType* _data; //需要动态开辟的数组
// size_t _size; //有效元素的个数
// size_t _capacity; //挡枪可以存放的最大元素个数
//}seqList;
void initSeqList(seqList* sl){
sl->_data = NULL;
sl->_size = sl->_capacity = 0;
}
//尾插一个数据o(1)
void pushBack(seqList* sl, SLDataType val){
//检查容量
checkCapacity(sl);
sl->_data[sl->_size] = val;
++sl->_size;
}
void checkCapacity(seqList* sl){
//如果元素个数和容量相同,说明空间满了,需要扩容空间
if (sl->_size == sl->_capacity){
int newCapacity = sl->_capacity == 0 ? 1 : 2 * sl->_capacity;
//开一个更大的空间,拷贝已有数据,释放原有空间
SLDataType* tmp = (SLDataType*)malloc(sizeof(SLDataType)* newCapacity);
memcpy(tmp, sl->_data, sizeof(SLDataType)* sl->_size);
free(sl->_data);
//更新
sl->_data = tmp;
sl->_capacity = newCapacity;
}
}
void printSeList(seqList* sl){
for (int i = 0; i < sl->_size; ++i){
printf("%d", sl->_data[i]);
}
printf("\n");
}
void popBack(seqList* sl){
if (sl == NULL)
return;
if (sl->_size>0)
sl->_size--;
}
//头插 给顺序表的第一个位置插入元素o(n)
//一般不进行头插:效率低
void pushFront(seqList* sl, SLDataType val){
if (sl == NULL)
return;
//0.检查容量
checkCapacity(sl);
//1.移动元素:从后向前移动
int end = sl->_size;
while (end > 0){
sl->_data[end] = sl->_data[end - 1];
--end;
}
//2.头插
sl->_data[0] = val;
sl->_size++;
}
//头删: 移动元素:[1,size)全部向前移动一个位置
void popFront(seqList* sl){
if (sl == NULL || sl->_size == 0)
return;
int start = 1;
while (start < sl->_size){
sl->_data[start - 1] = sl->_data[start];
++start;
}
--sl->_size;
}
//插入
void insert(seqList* sl, int pos, SLDataType val){
//检查容量
if (sl == NULL)
return;
checkCapacity(sl);
//移动元素
int end = sl->_size;
while (end > pos){
sl->_data[end] = sl->_data[end - 1];
--end;
}
//插入数据
sl->_data[pos] = val;
//更新
sl->_size++;
}
//删除的操作
void erase(seqList* sl, int pos){
if (sl == NULL || sl->_size == 0)
return;
//有效位置:[0,size)
if (pos >= 0 && pos < sl->_size){
//1.移动元素:(pos,size),从pos + 1开始,从前往后依次移动
int start = pos + 1;
while (start < sl-> _size){
sl->_data[start - 1] = sl->_data[start];
++start;
}
--sl->_size;
}
}
int empty(seqList* sl){
if (sl = NULL || sl->_size == 0)
return 1;
else
return 0;
}
int size(seqList* sl){
if (sl == NULL)
return 0;
else
return sl->_size;
}
int findIdx(seqList* sl, SLDataType val){
int i = 0;
for (; i < sl->_size; ++i){
if (sl->_data[i] == val)
return i;
}
return -1;
}
SLDataType getIdx(seqList* sl, int pos){
return sl->_data[pos];
}
void destorySeqList(seqList* sl){
if (sl){
//释放堆上申请的空间
if (sl->_data){
free(sl->_data);
sl->_data = NULL;
}
}
}
void test(){
seqList sl;
initSeqList(&sl);
pushBack(&sl, 1 );
pushBack(&sl, 2 );
pushBack(&sl, 3 );
pushBack(&sl, 4 );
pushBack(&sl, 5 );
erase(&sl, 3);
erase(&sl, 2);
erase(&sl, 0);
printSeList(&sl);
}
//void test(){
// seqList sl;
// initSeqList(&sl);
// pushBack(&sl, 1);
// pushBack(&sl, 2);
// pushBack(&sl, 3);
// pushBack(&sl, 4);
// pushBack(&sl, 5);
// insert(&sl, 1, 10);
// insert(&sl, 2, 20);
// printSeList(&sl);
// insert(&sl, 0, -1);
// printSeList(&sl);
// insert(&sl, sl._size, 3);
// printSeList(&sl);
//
//
//}
int main(){
test();
system("pause");
return 0;
}
由此可以看出顺序表的一些特性:
1.空间联系
2.支持随机访问
3.尾插,尾删效率高:O(1)
4.空间利用率高,不容易造成内存碎片
5.其他位置插入,删除效率低:O(n) ---> 移动元素
6.增容代价比较大