目录
顺序表的基本实现
顺序表结构
顺序表的初始化
检查顺序表容量空间
顺序表的头插
顺序表的打印
顺序表的头删
顺序表的尾插
顺序表的尾删
顺序表的查找
编辑指定位置之前插入数据
指定位置删除数据
顺序表的销毁
顺序表的基本实现
顺序表结构
对顺序表的数据类型进行重命名,方便以后给顺序表进行修改数据类型
size 记录顺序表中有多少个数据
capacity 采用动态开辟空间
typedef int SLDateType;//顺序表结构
typedef struct SeqList
{SLDateType* arr;int size;int capacity;
}SL;顺序表的初始化
//顺序表的初始化
void SLInit(SL* ps)
{ps->arr = NULL;ps->size = ps->capacity = 0;
}测试:
void test1()
{SL s1;SLInit(&s1);
}int main()
{test1();return 0;
}预期结果:对顺序表s1进行初始化成功
实际结果:
检查顺序表容量空间
使用顺序表的头插前 应该先扩容,我们把扩容的代码包装了成了一个函数
判断顺序表数据的个数是否和容量相等,如果相等则 进行二倍扩容,第一次进入 分配四个空间
这段代码要添加在增加顺序表数据代码的前面,或者添加一个声明
//检查顺序表容量
void CheckCapacity(SL* ps)
{if (ps->size == ps->capacity){int newcapacity = ps->capacity > 0 ? 4 : ps->capacity * 2;SLDateType* tmp = (SLDateType*)realloc(ps->arr, newcapacity * sizeof(SLDateType));if (tmp == NULL){perror("realloc is fail!");exit(1);}ps->arr = tmp;ps->capacity = newcapacity;}
}
顺序表的头插
思路:让元素依次往后挪动,留下首元素的空间进行插入
先检查顺序表的容量是否够插入数据,不够则扩容,
void SLPushFront(SL* ps, SLDateType x)
{CheckCapacity(ps);assert(ps->arr);for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[0] = x;ps->size++;
}测试代码:
void test1()
{SL s1;SLInit(&s1);SLPushFront(&s1, 1);SLPushFront(&s1, 2);SLPushFront(&s1, 3);SLPushFront(&s1, 4);SLPushFront(&s1, 5);SLPrint(&s1);
}int main()
{test1();return 0;
}预期结果:
插入4 3 2 1 之后,进行扩容,顺序表容量翻倍,在头部添加5
5 4 3 2 1
实际结果:
顺序表的打印
//顺序表的打印
void SLPrint(SL* ps)
{for (int i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}
}
预期结果:
打印顺序表
实际结果:
如上,已经进行打印
顺序表的头删
思路:让后一个数据依次覆盖前一个数据
如果顺序表没有元素的话,要判断一下
最简单直接有效的办法就是断言一下
//顺序表的头删
void SLPopFront(SL* ps)
{assert(ps->arr);assert(ps->size > 0);for (int i = 0; i < ps->size-1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
} 测试代码:
void test1()
{SL s1;SLInit(&s1);SLPushFront(&s1, 1);SLPushFront(&s1, 2);SLPushFront(&s1, 3);SLPushFront(&s1, 4);SLPushFront(&s1, 5);SLPopFront(&s1);SLPopFront(&s1);SLPopFront(&s1);SLPrint(&s1);
}int main()
{test1();return 0;
}预期结果:
依次删除 5 4 3 输出 2 1
实际结果:
顺序表的尾插
思路:依次插入数据,每插入完一个顺序表数据,顺序表大小+1
//顺序表的尾插
void SLPushBack(SL* ps, SLDateType x)
{CheckCapacity(ps);assert(ps->arr);ps->arr[ps->size] = x;ps->size++;
}测试代码:
void test2()
{SL s2;SLInit(&s2);SLPushBack(&s2, 1);SLPushBack(&s2, 2);SLPushBack(&s2, 3);SLPushBack(&s2, 4);SLPushBack(&s2, 5);SLPrint(&s2);
}
int main()
{test2();return 0;
}预期结果
依次插入 1 2 3 4 5
实际结果:
顺序表的尾删
//顺序表的尾删
void SLPushBack(SL* ps)
{assert(ps->arr);assert(ps->size > 0);ps->size--;
}测试代码:
void test2()
{SL s2;SLInit(&s2);SLPushBack(&s2, 1);SLPushBack(&s2, 2);SLPushBack(&s2, 3);SLPushBack(&s2, 4);SLPushBack(&s2, 5);SLPopBack(&s2);SLPopBack(&s2);SLPopBack(&s2);SLPopBack(&s2);SLPrint(&s2);
}
int main()
{test2();return 0;
}预期结果
依次删除5 4 3 2 输出结果为1
实际结果:
顺序表的查找
//顺序表查找
int SLFind(SL* ps, SLDateType x)
{assert(ps->arr);for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x){return i;}}return -1;
}顺序表查找不到元素的情况:
测试代码:
void test2()
{SL s2;SLInit(&s2);SLInsert(&s2,5,s2.size);SLInsert(&s2,6,s2.size);SLInsert(&s2,10,0);SLInsert(&s2,7,s2.size);SLInsert(&s2,8,s2.size);SLPrint(&s2);int ret = SLFind(&s2, 6);printf("\n");if (ret == -1)printf("该顺序表无元素\n");elseprintf("找到了,该元素的位置在顺序表下标%d\n",ret);}
int main()
{test2();return 0;
}预期结果:
找到了,该元素的位置下在顺序表下表2
实际结果
指定位置之前插入数据
//指定位置之前插入数据
void SLInsert(SL* ps, SLDateType x, int pos)
{CheckCapacity(ps);assert(ps->arr);assert(pos >= 0 && pos <= ps->size);for (int i = ps->size; i > pos; i--){ps->arr[i] = ps->arr[i - 1];//ps->arr[1] = ps->arr[0]}ps->arr[pos] = x; ps->size++;
}可以模拟头插和尾插
测试代码:
void test2()
{SL s2;SLInit(&s2);SLInsert(&s2,5,s2.size);SLInsert(&s2,6,s2.size);SLInsert(&s2,10,0);SLInsert(&s2,7,s2.size);SLInsert(&s2,8,s2.size);SLPrint(&s2);
}
int main()
{test2();return 0;
}
预期结果:先模拟进行尾插 插入5 6 模拟进行头插 插入10 后进行头插
输出结果为 10 5 6 7 8
实际结果:
指定位置删除数据
//指定位置删除数据
void SLErase(SL* ps, int pos)
{assert(ps->arr);assert(ps->size != 0);assert(pos >= 0 && pos < ps->size);for (int i = pos; i<ps->size-1;i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}测试代码:
void test2()
{SL s2;SLInit(&s2);SLInsert(&s2,5,s2.size);SLInsert(&s2,6,s2.size);SLInsert(&s2,10,0);SLInsert(&s2,7,s2.size);SLInsert(&s2,8,s2.size);SLErase(&s2, 1);SLErase(&s2, 2);SLErase(&s2, 0);SLPrint(&s2);}
int main()
{test2();return 0;
}预期输出
先删除下标位置为1的数据,接着删除下标为2的数据,再模拟进行头删
输出为6 8
实际输出:
顺序表的销毁
void SLDestory(SL* ps)
{assert(ps->arr);free(ps->arr);ps->arr = NULL;ps->size = ps->capacity = 0;
}个人水平不足 如果代码中有错误，可以多多在评论区指出，一定会及时修改！
谢谢大家看到这里 觉得有收获的话可以三连一下 大家一起加油！
