营销型企业网站建设方案,济南网站建设小程序,深圳西乡地铁站,html网页设计结课作业目录 一.什么是顺序表
二.顺序表的基本操作 1.初始化
2.增容
3.尾插
4.头插
5.尾删
6.头删
7.指定位置插入
8.指定位置删除
9.打印
10.查找
11.销毁 一.什么是顺序表 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构#xff0c;一般情况下采用数组…目录 一.什么是顺序表
二.顺序表的基本操作 1.初始化
2.增容
3.尾插
4.头插
5.尾删
6.头删
7.指定位置插入
8.指定位置删除
9.打印
10.查找
11.销毁 一.什么是顺序表 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组上完成数据的增删查改。顺序表一般分为静态顺序表和动态顺序表静态顺序表一般是用定长数组存储而动态顺序表则是用动态内存管理函数进行动态分配空间当空间不够时可以进行增容静态顺序表#define MAX 100
typedef int SLDataType//对类型重定义方便适应不同的数据类型
struct SeqList
{SLDataType a[MAX];//定长数组int size; //当前数据个数
}; 动态顺序表 typedef int SLDataType;//对类型重定义方便适应不同的数据类型
typedef struct SeqList
{SLDataType *a;//定义指针指向动态开辟的空间int size; //当前存储的数据个数int capacity; //数据最大个数
}SL; 一般我们不太经常使用静态顺序表因为实际需求往往空间都是不定的因此我们只讨论动态顺序表 顺序表的本质还是对数组进行操作只是和数组有所不同的是顺序表的数据是连续存放的 二.顺序表的基本操作 一般地我们都是用结构体定义顺序表对顺序表的基本操作分为初始化插入删除打印查找增容等操作下面我们就来学习一下这些基本操作 1.初始化 顺序表的初始化我们只需要讲指针置为空指针然后将当前数据元素个数和最大数据元素个数置为0到插入时我们便会动态开辟空间给指针a void SLInit(SL * ps)
{assert(ps);//断言是否为空指针如传入空指针则报错防止函数被误用ps-a NULL;//置为空指针ps-size 0;//初始化为0ps-capacity 0;
} 2.增容 当当前数据元素个数等于最大数据元素个数时说明空间已满此时则需要我们进行扩容而扩容需要我们利用的动态内存管理函数开辟空间我们选择的是realloc函数打开cpp网站查看该函数有关信息 realloc函数的的两个参数分别为空间的地址和扩容后的空间大小返回值是指向扩容后空间的地址返回值void*,因此我们需要将其强制类型转换为我们需要的类型 当realloc函数的第一个指针为空指针时其作用相当于malloc第一次增容由于我们初始化时给了最大容量capacity为0因此需要给capacity赋一个初始值4后面再扩容时则最大容量翻倍 第一次调用realloc函数时由于我们初始化时将指针a赋为空指针故第一次调用realloc函数作用和malloc函数相当后面再次调用则实现扩容功能 void SLCheckCapacity(SL* ps)
{assert(ps);断言是否为空指针如传入空指针则报错防止函数被误用if (ps-size ps-capacity)//判断当前数据个数是否到达最大值是则增容{int newCapacity ps-capacity 0 ? 4 : ps-capacity * 2;//第一次给值为4后面则翻倍SLDataType* tmp (SLDataType*)realloc(ps-a, newCapacity * sizeof(SLDataType));//利用动态内存管理函数realloc开辟空间if (tmp NULL)//判断是否开辟成功如果返回空指针说明开辟失败则报错否则将空间的地址付给a指针{perror(realloc fail);return;}ps-a tmp;ps-capacity newCapacity;//最大容量更新为扩容之后的容量}
} 3.尾插 尾插先判断空间是否已满若空间已满则需要扩容然后再直接从尾部插入后将数据个数加1即可 void SLPushBack(SL* ps, SLDataType x)
{assert(ps);//断言是否为空指针如传入空指针则报错防止函数被误用SLCheckCapacity(ps);//检查是否需要增容ps-a[ps-size] x;//在尾部插入值ps-size; //数据个数加1
} 4.头插 头插也需要判断空间是否已满若空间已满则需要扩容然后再从头部插入插入过程先将顺序表里面已有的每一个元素往后挪动一个位置相当于头部就腾出了一个“空位”然后我们将需要插入的元素放到这个“空位”即可后将数据元素加1 void SLPushFront(SL* ps, SLDataType x)
{assert(ps);//断言是否为空指针如传入空指针则报错防止函数被误用SLCheckCapacity(ps);//检查是否需要增容int end ps-size - 1;while (end 0)//从尾部依次挪动元素{ps-a[end 1] ps-a[end];end--;}ps-a[0] x;//将值赋给第一个元素ps-size; //数据个数加1
} 5.尾删 尾删需要先判断当前顺序表是否有元素没有元素则直接报错如果有元素我们只需要将数据个数减1即达到删除效果而不需要对最后一个元素进行操作后续操作直接将它覆盖就行 void SLPopBack(SL* ps)
{assert(ps-size 0);//判断当前是否有元素ps-size--;//直接将数据个数减1即可
} 6.头删 头删也需要先判断当前顺序表是否有元素没有元素则直接报错如果有元素则删除的过程为以我们排队打饭为例当队伍的最前面一个人打完饭后面的每一个人就都会往前一个位置此时删除元素也是一样从第二个位置开始到最后一个元素每个元素都依次往前挪动一个元素即可后将数据个数减1 void SLPopFront(SL* ps)
{assert(ps);//断言是否为空指针如传入空指针则报错防止函数被误用assert(ps-size 0);//判断当前是否有元素int begin 0;while (begin ps-size - 1)//从尾部一次挪动元素{ps-a[begin] ps-a[begin1];begin;}ps-size--;//数据个数减1
} 7.指定位置插入 指定位置我们需要先判断指定位置是否合法如果小于0或者大于最大元素个数则直接报错再判断是否需要增容然后从指定位置开始到最后一个元素每个元素依次往后挪动一个位置然后再将所插入的元素放到指定位置即可后将数据元素个数加1 void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);//断言是否为空指针如传入空指针则报错防止函数被误用assert(pos 0 posps-size);//判断给定的位置是否合法SLCheckCapacity(ps);//检查是否需要增容int end ps-size - 1;while (end pos)//从尾部依次挪动元素直到到达给定位置{ps-a[end 1] ps-a[end];end--;}ps-a[pos] x;//将值赋给指定位置ps-size;//数据个数加1
} 8.指定位置删除 指定位置删除野需要先判断给定位置是否合法不合法则直接报错然后从指定位置到最后一个元素依次往前挪动一个位置即可后将数据元素减1 void SLErase(SL* ps, int pos)
{assert(ps);//断言是否为空指针如传入空指针则报错防止函数被误用assert(pos 0 pos ps-size);//判断给定的位置是否合法int begin pos;while (begin ps-size - 1)//从指定位置依次挪动元素直到到达尾部的前一个元素{ps-a[begin] ps-a[begin 1];begin;}ps-size--;//数据个数减1
} 9.打印 打印只需要定义一个循环变量以下标的形式遍历顺序表打印即可 void SLPrint(SL* ps)
{assert(ps);//断言是否为空指针如传入空指针则报错防止函数被误用int i 0;for (i 0; i ps-size; i)//依次遍历打印顺序表即可{printf(%d , ps-a[i]);}
} 10.查找 查找也是遍历顺序表将每一个元素与查找的元素比较若相等则返回元素下标若遍历完没有找到元素则返回-1证明找不到该元素 int SLFind(SL* ps, SLDataType x)
{assert(ps);//断言是否为空指针如传入空指针则报错防止函数被误用int i 0;for (i 0; i ps-size; i)//遍历数组比较是否相等相等则返回元素下标{if (ps-a[i] x)return i;}return -1;//如果遍历没有找到该元素则返回-1
} 11.销毁 由于我们前面开辟空间是利用动态内存管理函数realloc开辟的而该函数开辟的空间是由程序员自行开辟的空间位于堆上使用完空间后需要我们手动销毁否则会导致内存泄露 销毁空间我们需要用到free函数我们打开cpp网站查看该函数有关信息 freea函数的参数是一个指针即所需要销毁的空间的地址我们销毁顺序表只需要将指针a传给free函数即可后讲指针a赋为空指针防止其成为野指针 void SLDestroy(SL* ps)
{assert(ps);//断言是否为空指针如传入空指针则报错防止函数被误用if (ps-a){free(ps-a);//释放a指针指向的空间ps-a NULL;//将a指针置为空防止其成为野指针ps-size ps-capacity 0;//当前数据元素个数和最大数据元素个数全置为0}
} 可以看到上面的基本操作都是有相应的接口函数我们只需要调用相应的函数即可实现顺序表的一些基本操作 上面所有的接口函数都用到了assert函数且都位于函数体开头assert函数称之为断言函数当表达式为真是继续执行当表达式为假时则直接报错而这种报错可以让我们快速了解错误出在什么地方 我们打开cpp网站查看该函数有关信息 上面的所有接口函数调用assert函数传的参数时指针a当指针a为空指针时则直接报错可以防止函数被误用而导致一些未知的错误 上面就是顺序表的一些基本操作以下是全部代码 SeqList.c #includeSeqList.h
void SLCheckCapacity(SL* ps)
{assert(ps);断言是否为空指针如传入空指针则报错防止函数被误用if (ps-size ps-capacity)//判断当前数据个数是否到达最大值是则增容{int newCapacity ps-capacity 0 ? 4 : ps-capacity * 2;//第一次给值为4后面则翻倍SLDataType* tmp (SLDataType*)realloc(ps-a, newCapacity * sizeof(SLDataType));//利用动态内存管理函数realloc开辟空间if (tmp NULL)//判断是否开辟成功如果返回空指针说明开辟失败则报错否则将空间的地址付给a指针{perror(realloc fail);return;}ps-a tmp;ps-capacity newCapacity;//最大容量更新为扩容之后的容量}
}
void SLInit(SL * ps)
{assert(ps);//断言是否为空指针如传入空指针则报错防止函数被误用ps-a NULL;//置为空指针ps-size 0;//初始化为0ps-capacity 0;
}
void SLDestroy(SL* ps)
{assert(ps);//断言是否为空指针如传入空指针则报错防止函数被误用if (ps-a){free(ps-a);//释放a指针指向的空间ps-a NULL;//将a指针置为空防止其成为野指针ps-size ps-capacity 0;//当前数据元素个数和最大数据元素个数全置为0}
}
void SLPushBack(SL* ps, SLDataType x)
{assert(ps);//断言是否为空指针如传入空指针则报错防止函数被误用SLCheckCapacity(ps);//检查是否需要增容ps-a[ps-size] x;//在尾部插入值ps-size; //数据个数加1
}
void SLPrint(SL* ps)
{assert(ps);//断言是否为空指针如传入空指针则报错防止函数被误用int i 0;for (i 0; i ps-size; i)//依次遍历打印顺序表即可{printf(%d , ps-a[i]);}
}
void SLPopBack(SL* ps)
{assert(ps-size 0);//判断当前是否有元素ps-size--;//直接将数据个数减1即可
}
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);//断言是否为空指针如传入空指针则报错防止函数被误用SLCheckCapacity(ps);//检查是否需要增容int end ps-size - 1;while (end 0)//从尾部依次挪动元素{ps-a[end 1] ps-a[end];end--;}ps-a[0] x;//将值赋给第一个元素ps-size; //数据个数加1
}
void SLPopFront(SL* ps)
{assert(ps);//断言是否为空指针如传入空指针则报错防止函数被误用assert(ps-size 0);//判断当前是否有元素int begin 0;while (begin ps-size - 1)//从尾部一次挪动元素{ps-a[begin] ps-a[begin1];begin;}ps-size--;//数据个数减1
}
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);//断言是否为空指针如传入空指针则报错防止函数被误用assert(pos 0 posps-size);//判断给定的位置是否合法SLCheckCapacity(ps);//检查是否需要增容int end ps-size - 1;while (end pos)//从尾部依次挪动元素直到到达给定位置{ps-a[end 1] ps-a[end];end--;}ps-a[pos] x;//将值赋给指定位置ps-size;//数据个数加1
}
void SLErase(SL* ps, int pos)
{assert(ps);//断言是否为空指针如传入空指针则报错防止函数被误用assert(pos 0 pos ps-size);//判断给定的位置是否合法int begin pos;while (begin ps-size - 1)//从指定位置依次挪动元素直到到达尾部的前一个元素{ps-a[begin] ps-a[begin 1];begin;}ps-size--;//数据个数减1
}
int SLFind(SL* ps, SLDataType x)
{assert(ps);//断言是否为空指针如传入空指针则报错防止函数被误用int i 0;for (i 0; i ps-size; i)//遍历数组比较是否相等相等则返回元素下标{if (ps-a[i] x)return i;}return -1;//如果遍历没有找到该元素则返回-1
} SeqList.h #pragma once
#includestdio.h
#includestdlib.h
#includeassert.h
//动态顺序表
typedef int SLDataType;//对类型重定义方便适应不同的数据类型
typedef struct SeqList
{SLDataType *a;//定义指针指向动态开辟的空间int size; //当前存储的数据个数int capacity; //数据最大个数
}SL;
void SLCheckCapacity(SL *ps);
void SLInit(SL * ps);
void SLDestroy(SL* ps);
void SLPrint(SL* ps);void SLPushBack(SL * ps, SLDataType x);
void SLPopBack(SL * ps);void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);void SLInsert(SL* ps,int pos, SLDataType x);
void SLErase(SL* ps, int pos);int SLFind(SL* ps, SLDataType x);test.c #define _CRT_SECURE_NO_WARNINGS
#includeSeqList.h
void TestSeqList()
{SL sl;SLInit(sl);SLPushBack(sl, 1);SLPushBack(sl, 2);SLPushBack(sl, 3);SLPushBack(sl, 4);SLPushBack(sl, 5);SLPushFront(sl, 0);SLInsert(sl, 2, 9);SLErase(sl, 2);int pos SLFind(sl, 5);if (pos ! -1)SLErase(sl, pos);SLPrint(sl);SLDestroy(sl);
}
int main()
{TestSeqList();return 0;
} 输出结果 好啦顺序表我们就先学到这里如果喜欢我的文章欢迎动动手指一键三连~
