曲阳网站建设,网站开发竞争性谈判,安阳网红,centos 6.5 wordpress目录 1.线性表
2.顺序表概念 3.实现顺序表
(1)声明结构体
(2)初始化
(3)打印数据
(4) 销毁
(5)尾插头插
尾插
判断是否扩容 头插
(6)尾删头删
尾删
头删
(7)指定位置插入元素
(8)删除指定位置元素
(9)查找指定元素位置
(10)修改指定位置元素 完整版…目录 1.线性表
2.顺序表概念 3.实现顺序表
(1)声明结构体
(2)初始化
(3)打印数据
(4) 销毁
(5)尾插头插
尾插
判断是否扩容 头插
(6)尾删头删
尾删
头删
(7)指定位置插入元素
(8)删除指定位置元素
(9)查找指定元素位置
(10)修改指定位置元素 完整版附上
Seqlist.h
text.c
Seqlist.c 1.线性表 线性表是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列、字符串...线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的 线性表在物理上存储时通常以数组和链式结构的形式存储。 2.顺序表概念 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组上完成数据的增删查改。 顺序表一般可以分为 1. 静态顺序表使用定长数组存储元素。 2. 动态顺序表使用动态开辟的数组存储。 3.实现顺序表 静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了空间开多了浪费开少了不够用。所以现实中基本都是使用 动态顺序表 根据需要动态的分配空间大小所以下面我们实现动态顺序表。 我们创建三个文件
Seqlist.h用于存放头文件、结构体和函数的声明text.c作为主程序进行运行和测试Seqlist.c存放函数主体
(1)声明结构体
#include stdio.htypedef int SLDatatype;
typedef struct SeqList
{SLDatatype* a;int size;int capacity;
}SL;
在头文件中声明结构体struct SeqList由于名字太长我们用typedef自定义结构体名称的别名为SL。将顺序表的数据类型用SLDatatype这个别名代替int以后程序中使用到元素数据类型时都替换成SLDatatype方便日后修改顺序表数据类型。定义size存储当前元素个数capacity存储顺序表容量。
(2)初始化
void SLInit(SL* psl)
{assert(psl);psl-a (SLDatatype*)malloc(sizeof(SLDatatype) * 4);if (psl-a NULL) {perror(malloc fail);return;}psl-size 0;psl-capacity 4;
}
需要改变结构体变量则将其地址传入函数。assert检测传参顺序表指针是否合法如果传入参数为空则报错具体哪行出错。然后为结构体成员a分配4个成员类型空间顺便检查是否分配成功。对成员size和capacity分别复制为0当前元素个数和4顺序表容量。
(3)打印数据
void SLPrint(SL* psl)
{assert(psl);for (int i 0; i psl-size; i) {printf(%d , psl-a[i]);}
}
assert检测传参顺序表指针是否合法然后循环遍历输出。
(4) 销毁
void SLDestroy(SL* psl)
{assert(psl);free(psl-a);psl-a NULL;psl-size 0;psl-capacity 0;
}
assert检测传参顺序表指针是否合法。释放动态开辟a的空间同时赋值为空不置空可能会造成野指针的访问。size和capacity分别赋值为0。
(5)尾插头插
尾插
void SLPushBack(SL* psl, SLDatatype x)
{assert(psl);SLCheckCapacity(psl);psl-a[psl-size] x;psl-size;
}
assert检测传参顺序表指针是否合法。判断数组是否已经装满如果装满则进行扩容这些操作我们在函数SLCheckCapacity内进行。将 x 赋值给 psl-a 数组中下一个可用的位置即 psl-size 索引处。递增 psl-size以便记录新元素的加入。 接下来我们来讲解函数SLCheckCapacity
判断是否扩容
void SLCheckCapacity(SL* psl)
{if (psl-size psl-capacity) {SLDatatype* tmp (SLDatatype*)realloc(psl-a, sizeof(SLDatatype) * psl-capacity * 2);if (tmp NULL) {perror(realloc fail);return;}psl-a tmp;psl-capacity * 2;}
} 判断当前元素个数size与顺序表容量capacity是否相等相等则对结构体成员指针a进行扩容。通过realloc函数对a的内存进行扩容每次增加一倍容量并将reallocd的返回值新空间的起始地址赋值给SLDatatype类型指针 tmp这样避免直接对a开辟空间时发生错误丢失数据。检测是否成功扩容。最后将存放新空间地址的tmp赋值给a。顺序表的容量也随之扩大为原来的两倍。
我们还可以优化一下尾插函数具体如下
void SLPushBack(SL* psl, SLDatatype x)//尾插
{SLCheckCapacity(psl);psl-a[psl-size] x;
} 头插
void SLPushFront(SL* psl, SLDatatype x)
{assert(psl);SLCheckCapacity(psl);int end psl-size - 1;while (end 0) {psl-a[end 1] psl-a[end];end--;}psl-a[0] x;psl-size;
}
assert检测传参顺序表指针是否合法。判断数组是否已经装满如果装满则进行扩容这些操作在函数SLCheckCapacity内进行。定义end表示当前顺序表中最后一个元素的下标。while循环用于从后向前将顺序表中的元素依次向后移动一个位置为新元素 x 腾出空间将新元素 x 插入到顺序表的开头顺序表元素个数 size 增加1
(6)尾删头删
尾删
void SLPopBack(SL* psl)
{assert(psl);//暴力判断assert(psl-size 0);//常规判断//if (psl-size 0)// return;psl-a[psl-size - 1] 0;psl-size--;
}
第一个assert检测传参顺序表指针是否合法。第二个assert检测顺序表是否为空为空没有元素则不需要删除程序报错。我们还可以通过顺序表元素个数判断if语句判断size为0时函数停止运行。顺序表大小不为空则对最后一个元素进行删除赋值为0。顺序表大小size减1.
头删
void SLPopFront(SL* psl)
{assert(psl);assert(psl-size 0);int start 0;while (start psl-size) {psl-a[start] psl-a[start 1];start;}psl-size--;
}
第一个assert检测传参顺序表指针是否合法。第二个assert检测顺序表是否为空为空没有元素则不需要删除程序报错。定义变量start为首元素下标.头删不用赋值为0直接从第一个元素开始后项赋值给前项。
(7)指定位置插入元素
void SLInsert(SL* psl, int pos, SLDatatype x)
{assert(psl);assert(0 pos pos psl-size);SLCheckCapacity(psl);int end psl-size - 1;while (end 0) {psl-a[end 1] psl-a[end];end--;}psl-size;psl-a[pos] x;
}
参数pos为要在第几个元素后插入。第一个assert检测传参顺序表指针是否合法。第二个assert检测传参pos的位置是否合法。判断数组是否已经装满如果装满则进行扩容这些操作在函数SLCheckCapacity内进行。定义end表示当前顺序表中最后一个元素的下标。while循环用于从后向前将顺序表中的元素依次向后移动一个位置为新元素 x 腾出空间顺序表元素个数 size 增加1。将新元素 x 插入到顺序表指定元素位置之后。 SLInsert这个函数可以代替头插尾插函数进行顺序表元素的增加。 (8)删除指定位置元素
void SLErase(SL* psl, int pos)
{assert(psl);assert(0 pos pos psl-size);int start pos 1;while (start psl-size) {psl-a[start - 1] psl-a[start];start;}psl-size--;
}
第一个assert检测传参顺序表指针是否合法。第二个assert检测传参pos的位置是否合法。定义变量start存储pos位置后一项的下标。将删除元素后一项位置的值开始从pos1向后依次前移一位顶替pos位置。顺序表元素个数减一。 这个函数就可以完全代替头删尾删了。 (9)查找指定元素位置
int SLFind(SL* psl, SLDatatype x)
{assert(psl);for (int i 0; i psl-size; i) {if (psl-a[i] x)return i1;}return -1;
} assert检测传参顺序表指针是否合法。循环遍历顺序表找出于x相等的元素返回其下标。找不到返回-1。
(10)修改指定位置元素
void SLModify(SL* psl, int pos, SLDatatype x)
{assert(psl);assert(0 pos pos psl-size);psl-a[pos] x;
} 第一个assert检测传参顺序表指针是否合法。第二个assert检测传参pos的位置是否合法。 将pos位置的值修改为x。
完整版附上
Seqlist.h
#include stdio.h
#include stdlib.h
#include assert.h
typedef int SLDatatype;
typedef struct SeqList
{SLDatatype* a;int size;int capacity;
}SL;void SLInit(SL* psl);
void SLDestroy(SL* psl);
void SLPrint(SL* psl);
void SLPushBack(SL* psl, SLDatatype x);
void SLPushFront(SL* psl, SLDatatype x);
void SLPopBack(SL* psl);
void SLPopFront(SL* psl);
void SLInsert(SL* psl, int pos, SLDatatype x);
void SLErase(SL* psl, int pos);
int SLFind(SL* psl, SLDatatype x);
void SLModify(SL* psl, int pos, SLDatatype x);
text.c 这里大家可以自行发挥 #define _CRT_SECURE_NO_WARNINGS 1
#include Seqlist.hvoid test1()
{SL s;SLInit(s);SLPushBack(s, 5);SLPushBack(s, 9);SLPushBack(s, 50);SLPushFront(s, 1);SLPushFront(s, 15);SLPushFront(s, 0);SLPopBack(s, 50);SLPopFront(s, 0);SLInsert(s, 2, 555);SLErase(s, 4);SLPrint(s);int aSLFind(s, 15);printf(\n%d\n, a);if (a ! -1)SLErase(s, a);SLPrint(s);SLDestroy(s);
}int main()
{test1();return 0;
}
Seqlist.c
#define _CRT_SECURE_NO_WARNINGS 1
#include Seqlist.hvoid SLInit(SL* psl)//初始化
{assert(psl);psl-a (SLDatatype*)malloc(sizeof(SLDatatype) * 4);if (psl-a NULL) {perror(malloc fail);return;}psl-size 0;psl-capacity 4;//每次开辟的容量为四个
}void SLPrint(SL* psl)//打印数据
{assert(psl);for (int i 0; i psl-size; i) {printf(%d , psl-a[i]);}
}void SLDestroy(SL* psl)//结束使用需要销毁
{assert(psl);free(psl-a);psl-a NULL;psl-size 0;psl-capacity 0;
}void SLCheckCapacity(SL* psl)
{if (psl-size psl-capacity) {//增加一倍容量SLDatatype* tmp (SLDatatype*)realloc(psl-a, sizeof(SLDatatype) * psl-capacity * 2);if (tmp NULL) {perror(realloc fail);return;}psl-a tmp;psl-capacity * 2;}}void SLPushBack(SL* psl, SLDatatype x)//尾插
{assert(psl);//psl-a[psl-size] x;//psl-size;//插入需要判断a是否已满已满需要扩容SLCheckCapacity(psl);//或者写成一句psl-a[psl-size] x;//后置自增
}void SLPushFront(SL* psl, SLDatatype x)//头插
{assert(psl);SLCheckCapacity(psl);int end psl-size - 1;while (end 0) {psl-a[end 1] psl-a[end];end--;}psl-a[0] x;psl-size;
}
void SLPopBack(SL* psl)
{assert(psl);//尾删//暴力判断//assert(psl-size 0);//常规判断if (psl-size 0)return;psl-a[psl-size - 1] 0;psl-size--;
}void SLPopFront(SL* psl)//头删
{assert(psl);assert(psl-size 0);int start 0;while (start psl-size) {psl-a[start] psl-a[start 1];start;}psl-size--;
}void SLInsert(SL* psl, int pos, SLDatatype x)//指定位置插入元素,可代替头插尾插
{assert(psl);assert(0 pos pos psl-size);//判读插入位置是否合法SLCheckCapacity(psl);int end psl-size - 1;while (end 0) {psl-a[end 1] psl-a[end];end--;}psl-size;psl-a[pos] x;
}void SLErase(SL* psl, int pos)//删除指定位置元素代替头删尾删
{assert(psl);assert(0 pos pos psl-size);int start pos 1;while (start psl-size) {psl-a[start - 1] psl-a[start];start;}psl-size--;
}int SLFind(SL* psl, SLDatatype x)//查找指定元素位置
{assert(psl);for (int i 0; i psl-size; i) {if (psl-a[i] x)return i1;}return -1;//找不到返回-1
}void SLModify(SL* psl, int pos, SLDatatype x)//修改指定位置元素
{assert(psl);assert(0 pos pos psl-size);psl-a[pos] x;
}
