广州 环保 凡人网站建设,旅游网站建设成本核算,免费企业网站认证,一键登录目录 一、顺序表的初始定义
1.1新建头文件和源文件
1.2 SeqList.h 中的准备工作
二、顺序表的初始化与销毁
三、首尾插入元素
四、首尾删除元素
五、中间插入元素
六、中间删除元素 七、查找指定元素下标
八、源代码 一、顺序表的初始定义
1.1新建头文件和源文件
当我…目录 一、顺序表的初始定义
1.1新建头文件和源文件
1.2 SeqList.h 中的准备工作
二、顺序表的初始化与销毁
三、首尾插入元素
四、首尾删除元素
五、中间插入元素
六、中间删除元素 七、查找指定元素下标
八、源代码 一、顺序表的初始定义
1.1新建头文件和源文件
当我们要实现通讯录时我们会自定义一个 contact.h 文件来存储我们的各种声明自定义一个 contact.c 文件来存储实现声明的函数同时还会存在一个 test.c 来测试我们代码的可行性。
在这里我们学习顺序表时也要使用这种方式来分割我们的代码使程序更加简洁耐看
在 SeqList.h 中我们要声明我们需要的头文件、重新定义的类型、我们需要的函数......
1.2 SeqList.h 中的准备工作
为了方便我们修改顺序表中的数据类型我们把我们顺序表中的类型(int为例)重定义为SLDataType这样如果我们以后想修改数据类型的话可以直接来此处将 int 改为 double......
typedef int SLDataType; 其次我们定义的顺序表其实是一个结构体其包含了一个表头(一个指针)实际保存的数据以及表的容量这里我们并把结构体名称重定义为简称方便后续的使用。
typedef struct SeqList
{int* p;//表头int size;//实际存储的数据数量int capacity;//此时表中的容量
}SL;我们的顺序表要具有哪些特点呢 1.动态存储可以动态开辟使用空间 2.各种位置的增删查改分为头、尾、中间。 二、顺序表的初始化与销毁
初始化和销毁
首先用断言来保证传入的指针不为空其次我们需要用 SLInit 函数来将结构体中的数据一一赋初值其次在销毁数据时也要保证 free 函数的对象为非空指针接着将数据重新初始化。
void SLInit(SL* psl) //初始化顺序表
{assert(psl ! NULL);psl-p NULL;psl-size 0;psl-capacity 0;
}
void SLDestroy(SL* psl) //销毁顺序表
{assert(psl ! NULL);if (psl-p ! NULL){free(psl-p);psl-size 0;psl-capacity 0;}
}
因为我们的顺序表是动态开辟空间所以写一个检查实时容量的函数是必备的在此处我们使用二倍扩容的方法来开辟内存空间但是在初始化时我们把我们的 capacity 赋值为 0在进行二倍扩容时还是 0这时就可以用三目运算符完美规避这个问题。
检查并扩充容量
并且我们用新的临时变量来保存扩容后的空间在没有问题后再把值返回给原本的变量。
void SLCheckCapacity(SL* psl)
{assert(psl ! NULL);if (psl-size psl-capacity){//因为初始化时capacity为0所以我们按照二倍扩容后也是0这里运用三目运算符就能很好的解决SLDataType NewCapacity (psl-capacity 0) ? 4 : psl-capacity * 2;//动态开辟的空间是给顺序表的注意不要把改行上下两个数据颠倒//sizeof() 不要忘SLDataType* tmp (SLDataType*)realloc(psl-p, sizeof(SL) * NewCapacity);if (tmp NULL){perror(SLCheckCapacity - realloc);return;}psl-capacity NewCapacity;psl-p tmp;}
}
三、首尾插入元素
打印顺序表 为了更好的测试我们的代码我们可以先写一个打印函数来打印我们的顺序表。
void SLPrint(SL* psl)
{assert(psl ! NULL);int i 0;for (; i psl-size; i){printf(%d , psl-p[i]);}printf(\n);
}
尾部插入元素
void SLPushBack(SL* psl, SLDataType x)
{assert(psl ! NULL);SLCheckCapacity(psl);//检查是否需要扩容psl-p[psl-size] x;psl-size;
}
首部插入元素
首部插入元素就比尾部插入元素复杂一点啦我们需要让前面的元素覆盖后面的元素下图我们模拟顺序表中有 8 个元素(size 8)来看一下我们的代码应该如何写
我们让 i 从后面开始向前走才能保证有用的元素不会被覆盖同时我们根据首尾元素的覆盖下标推理出 i 的取值范围。
//第一种取值
void SLPushFront(SL* psl, SLDataType x)
{assert(psl ! NULL);SLCheckCapacity(psl);int i psl-size;for (; i 0; i--){psl-p[i] psl-p[i - 1];}psl-p[0] x;psl-size;
}//第二种取值
void SLPushFront(SL* ps, SLDateType x)//ʱ临Ӷ O(n) ; n O(n^2)
{assert(ps ! NULL);SLCheckCapacity(ps);int i ps-size - 1;for (; i 0; i--){ps-p[i 1] ps-p[i];}ps-p[0] x;ps-size;
}
四、首尾删除元素
尾部删除元素
这里我们采用 size-- 的方法让我们直接无法访问到最后一个元素下一次增添时又会被新的元素覆盖以实现删除的操作同时断言我们的实际元素个数必须多余 0
void SLPopBack(SL* psl)
{assert(psl ! NULL);assert(psl-size 0);psl-size--;
}
首部删除元素 void SLPopFront(SL* psl)
{assert(psl ! NULL);int i 1;for (; i psl-size; i){psl-p[i - 1] psl-p[i];}psl-size--;
}void SLPopFront(SL* ps)
{assert(ps ! NULL);assert(ps-size 0);int i 0;for (; i ps-size - 1; i){ps-p[i] ps-p[i 1];}ps-size--;
}
五、中间插入元素 void SLInsert(SL* psl, int num, SLDataType x)
{assert(psl ! NULL);assert(num 0 num psl-size);SLCheckCapacity(psl);int i psl-size - 1;for (; i num; i--){psl-p[i 1] psl-p[i];}psl-p[num] x;psl-size;
}
六、中间删除元素 void SLErase(SL* psl, int num)
{assert(psl ! NULL);assert(num 0 num psl-size);SLCheckCapacity(psl);int i num;for (; i psl-size - 1; i){psl-p[i] psl-p[i 1];}psl-size--;
} 七、查找指定元素下标
int SLFind(SL* ps, SLDataType x)
{assert(ps ! NULL);int i 0;for (; i ps-size; i){if (ps-p[i] x){return i;}}return -1;
}
八、源代码
欢迎光临我的Gitee - Gitee.comhttps://gitee.com/bright-and-sparkling-at-night/studying/commit/dd1f9978f81f9decce01805623b4708b7671f3e0
