Seqlist.h这个头文件中包含了顺序表的定义和对顺序表进行操作的所有函数,所有的函数只传递结构体指针以加快程序运行速度。
- #pragma once
-
-
- #include
- #include
- #include
-
-
- #define TYPE int//定义常量字符串类型进行替换,可以在顺序表内存储所有类型的变量
- struct SeqList
- {
- TYPE* SL;//维护动态开辟的内存的指针
- int volume;//当前的容量
- int size;//当前存储的有效数据的个数
- };
- typedef struct SeqList SList;//简化类型名
-
-
- //初始化
- void InitSeqlist(SList* p);
-
- //扩容
- void enlarge(SList* p);
-
- //打印
- void print(SList* p);
-
- //销毁
- void destory(SList* p);
- //对顺序表实现增删查改的函数
-
- //增加元素
- void Seqlist_front_push(SList* p, TYPE a);//前增
- void Seqlist_back_push(SList* p, TYPE a); //后增
- //减少元素
- void Seqlist_front_pop(SList* p); //前减
- void Seqlist_back_pop(SList* p);//后减
-
- //查找对应下标的元素,没有找到就返回-1
- int Seqlist_search_element(SList* p,TYPE a);
-
- //修改对应下标的元素
- void Seqlist_modify_element(SList* p, size_t pos, TYPE b);
-
- // 顺序表在pos位置插入a
- void SLInsert(SList* p, size_t pos, TYPE a);
-
- // 顺序表删除pos位置的值
- void SLErase(SList* p, size_t pos);
这些函数储存在一个function.c 文件中
void InitSeqlist(SList* p);
首先断言有没有创建相应的结构体,我们要逐步接受使用断言判断的写法,有利于C++的学习。然后整型值归零,指针置空。
- void InitSeqlist(SList* p)
- {
- assert(p);
- p->size = 0;
- p->volume = 0;
- p->SL = NULL;
- }
void enlarge(SList* p);
这个函数用于配合增加元素时在适当时扩大容量,在代码中就是当前的容量与当前存储的有效数据的个数相同时扩容
- void enlarge(SList* p)
- {
- if (p->size == p->volume)//容量与数据量相同扩容,每次扩容当前二倍大小的空间
- {
- assert(p);
- int newvolume = (p->volume == 0 ? 4 : 2 * p->volume);
- //定义一个变量保存新容量的大小,容量为0扩容4个,不为0扩容二倍
- TYPE* p1 = (TYPE*)realloc(p->SL, newvolume*sizeof(TYPE));
- //容量为0时,malloc与realloc效果相同
- if (p1 == NULL)
- {
- perror("realloc");
- return;
- }
- p->SL = p1;
- p->volume = newvolume;
- }
- }
void print(SList* p);
与数组的打印相同
- void print(SList* p)
- {
- assert(p);
- int i = 0;
- for (i = 0; i < p->size; i++)
- {
- printf("%d ", p->SL[i]);
- }
- printf("\n");
- }
void destory(SList* p);
释放指针管理的内容,但是此时指针依旧指向那个空间的头地址,指针需要置空以避免野指针。最后整型值归零
- void destory(SList* p)
- {
- assert(p);
- free(p->SL);
- p->size = 0;
- p->volume = 0;
- p->SL = NULL;
- }
void Seqlist_front_push(SList* p, TYPE a);
在头部增加,此时头部有内容,就需要从后向前的顺序一个一个向后挪一位,然后有效数据个数加一
1 2 3 4 5(原数据)
1 2 3 4 5 5(5后挪一位)
1 2 3 4 4 5(4后挪一位)
……
1 1 2 3 4 5(1后挪一位)
a 1 2 3 4 5(头插入数据)
顺序表的头插的时间复杂度为O(N),这是顺序表的缺点:头插复杂
- void Seqlist_front_push(SList* p, TYPE a)
- {
- assert(p);
- enlarge(p);//函数负责在适当时负责扩容
- int i = p->size;
- while (i >= 0)
- {
- p->SL[i] = p->SL[i - 1];//顺序表的头插需要将所有数据从后向前后挪一位
- i--;
- }
- *(p->SL) = a;//插入数据
- p->size++;//自增
- }
void Seqlist_back_push(SList* p, TYPE a);
后增就比较简单,直接在下标为size的所在的位置添加数据
- void Seqlist_back_push(SList* p, TYPE a)
- {
- assert(p);
- enlarge(p);//函数负责在适当时负责扩容
- *((p->SL) + (p->size)) = a;//此时size正好是应插入位置的下标
- p->size++;//size 自增
- }
void Seqlist_front_pop(SList* p);
在头部减少,此时尾部有内容,把后面的当作前面的,就需要从第二个开始按照从前向后的顺序一个一个向前挪一位,然后有效数据个数减一
1 2 3 4 5(原数据)
2 2 3 4 5(2前挪一位)
2 3 3 4 4 5(3前挪一位)
……
2 3 4 5 5(5前挪一位)
此时有效数据个数减一后,后面的5不在指针管理的范围内,注意我们减少数据时不需要缩容
- void Seqlist_front_pop(SList* p)
- {
- assert(p);
- int i = 0;
- for (i = 0; i < p->size - 1; i++)
- {
- p->SL[i] = p->SL[i + 1];//把每一个数据从前向后挪一位
- }
- p->size--;
- }
顺序表的头删的时间复杂度也为O(N),这也是顺序表的缺点:头删复杂
void Seqlist_back_pop(SList* p);
尾删直接有效数据个数减一,后面的数据就不在指针管理的内存内了
- void Seqlist_back_pop(SList* p)
- {
- assert(p);
- p->size--;//只需要减少有效数据的个数,自减即可
- }
int Seqlist_search_element(SList* p,TYPE a);
我们默认元素中没有-1,遍历数组寻找即可
- int Seqlist_search_element(SList* p, TYPE a)
- {
- assert(p);
- int i = 0;
- for (i = 0; i < p->size; i++)
- {
- if (p->SL[i] == a)
- {
- return i;//找到了返回下标
- }
- }
- return -1;//找不到返回-1
- }
void Seqlist_modify_element(SList* p, size_t pos, TYPE b);
这个函数就直接通过下标找到数据并修改。如果想要实现查找并修改,那么就在查找的基础上找到后修改对应的值就可以了。
- void Seqlist_modify_element(SList* p, size_t pos, TYPE b)
- {
- p->SL[pos] = b;//改变某个下标对应的数据
- }
void SLInsert(SList* p, size_t pos, TYPE a);
包括pos从后向前后挪一位再赋值
- void Seqlist_insert_element(SList* p, int pos, TYPE a)
- {
- assert(p);
- assert(pos < (p->size));
- enlarge(p);
- int i = pos;
- for (i = pos; i < p->size; i++)
- {
- p->SL[i + 1] = p->SL[i];
- }
- p->SL[pos] = a;
- p->size++;
- }
void SLErase(SList* p, size_t pos);
从前向后覆盖pos后的数据
- void Seqlist_delete_element(SList* p, int pos)
- {
- int i = 0;
- for (i = pos; i < p->size - 1;i++)
- {
- p->SL[i] = p->SL[i + 1];//从前向后覆盖pos后的数据
- }
- p->size--;//自减
- }
通过test.c来进行操作
- void test1(SList* p)
- {
- Seqlist_front_push(p, 2);
- Seqlist_front_push(p, 1);
- Seqlist_back_push(p, 3);
- Seqlist_back_push(p, 4);
- print(p);
- Seqlist_back_pop(p);
- Seqlist_front_pop(p);
- print(p);
- }
-
-
-
-
- void test2(SList* p)
- {
- Seqlist_back_push(p, 1);
- Seqlist_back_push(p, 2);
- Seqlist_back_push(p, 3);
- Seqlist_back_push(p, 4);
- Seqlist_back_push(p, 5);
- Seqlist_back_push(p, 6);
- print(p);
- Seqlist_modify_element(p, Seqlist_search_element(p, 4), 10);
- print(p);
- Seqlist_insert_element(p, 5, 15);
- print(p);
- Seqlist_delete_element(p, 2);
- print(p);
- }
-
-
-
-
- int main()
- {
- SList s;
- SList* p = &s;
- InitSeqlist(p);
- //test1(p);
- test2(p);
- destory(p);
- return 0;
- }