长沙网站建设外贸手机软件编程

当前位置： 首页 > news >正文

长沙网站建设外贸,手机软件编程,品牌设计ppt案例,WordPress如何清空评论目录 一、线性表 二、顺序表 2.1概念及结构 2.2接口实现 2.3动态顺序表的创建 2.3动态顺序表的初始化 2.3.1传值初始化 2.3.2传址初始化 2.4动态顺序表的清空 2.5动态顺序表的扩容 2.6动态顺序表内容的打印 三、动态顺序表的使用 3.1尾插尾删 3.1.1尾插 3.1.2尾删…目录 一、线性表 二、顺序表 2.1概念及结构 2.2接口实现 2.3动态顺序表的创建 2.3动态顺序表的初始化 2.3.1传值初始化 2.3.2传址初始化 2.4动态顺序表的清空 2.5动态顺序表的扩容 2.6动态顺序表内容的打印 三、动态顺序表的使用 3.1尾插尾删 3.1.1尾插 3.1.2尾删 3.2头插头删 3.2.1头插 3.2.2头删 3.3在pos位置插入x 3.4删除pos位置的值 3.5修改某个位置的值 四、完整代码 一、线性表 线性表linear list是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的数据结构常见的线性表顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的 线性表在物理上存储时通常以数组和链式结构的形式存储。 二、顺序表 2.1概念及结构 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存 储。在数组上完成数据的增删查改。 顺序表一般分为 静态顺序表使用定长数组储存元素。 //静态顺序表 #define N 100 struct SeqList {int a[N];//定长数组int size;//有效数据的个数 }; 缺点不是很灵活 动态顺序表使用动态开辟的数组储存。 2.2接口实现 静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了空 间开多了浪费开少了不够用。所以现实中基本都是使用动态顺序表根据需要动态的分配空间 大小所以下面我们实现动态顺序表。 所谓动态其实指的这个结构体里的指针是动态内存开辟来的是可变的用的时候动态开辟不够的话继续开辟程序结束的时候释放。 2.3动态顺序表的创建 typedef int SLDatatype;//将int重命名为SLDatatype typedef struct SeqList {SLDatatype* a;//指向动态开辟的数组SLDatatype capacity;//容量SLDatatype size;//有效数据的个数}SL;//将结构体SeqList重命名为SL 2.3动态顺序表的初始化 2.3.1传值初始化 //传值初始化 void SLInit(SL s) {s.a NULL;s.size 0;s.capacity 0; } 函数那个章节我们学过形参只是实参的临时拷贝并没有实际作用生命周期短出了函数的作用域就会销毁我们不考虑这种初始化方式。 2.3.2传址初始化 //传址初始化 void SLInit(SL* ps) {ps-a 0;ps-capacity 0;ps-size 0; } void SLInit(SL* ps) {ps-a (SLDatatype*)malloc(sizeof(SLDatatype) * 4);//开辟了4个字节的空间if (ps-a NULL){perror(malloc failed);exit(-1);}ps-capacity 4;//开辟了空间就要给容量赋值ps-size 0; } 上面两种初始化方式都可以给予结构体成员变量赋值但是我们使用第二种因为第二种为我们开辟了空间。 2.4动态顺序表的清空 void SLDestr(SL* ps) {free(ps-a);ps-a NULL;ps-capacity 0;//内存释放容量清零ps-size 0;//内存释放有效数据清零 } 2.5动态顺序表的扩容 void SLCheckcapacity(SL* ps) {if (ps-size ps-capacity){SLDatatype* tmp (SLDatatype*)realloc(ps-a, ps-capacity * 2 *( sizeof(SLDatatype)));//扩容尾原来的倍数if (tmp NULL)//判断是否扩容失败{perror(realloc failed);exit(-1);}ps-a tmp;ps-capacity * 2;//扩容后修改原来的容量} } 这就是所谓的动态当我们空间不够时就需要开辟新的空间使用realloc函数要注意是否开辟成功定义一个中间指针当开辟成功时将这个指针赋值给动态数组中的指针。  2.6动态顺序表内容的打印 void SLprint(SL* ps) {int i 0;for (i 0; i ps-size; i){printf(%d , ps-a[i]);}printf(\n); } size为有效数据个数使用循环打印其中的有效数据。  三、动态顺序表的使用 3.1尾插尾删 3.1.1尾插 void SLPushBack(SL* ps, SLDatatype x) {SLCheckcapacity(ps);//检查空间是否足够插入ps-a[ps-size] x;//赋值ps-size;//插入一个有效数据有效数据个数加一 } 首先一定要检查规矩是否足够根据上面开辟的空间容量为4有效数据为size为0所以从第一个空间开始插入数据。 3.1.2尾删 //尾删 void SLPopBack(SL* ps) {assert(ps-size 0);//判断是否会造成越界if (ps-size 0){return;}ps-size–;//删除一个数据有效数据个数减一 } 插入数据后size的大小也会变化数组中最后一个数字的下标刚好和size的大小一样我们只需要将size减1就行。  3.2头插头删 3.2.1头插 void SLPushFront(SL* ps, SLDatatype x) {SLCheckcapacity(ps);//检查空间是否足够int end ps-size;while (end 0){ps-a[end] ps-a[end - 1];//将前一个数据后移动end–;}ps-a[0] x;//将x赋给初始位置ps-size;//加入一个数字有效数据个数加1 } 老规矩一定要检查空间是否足够头部插入数据我们只需要将原来的数据往后移动一格就将第一格的位置空出来再将数值插入就行插入一个数据有效数据加1即可。 3.2.2头删 void SLPopFront(SL* ps) {assert(ps-size 0);//防止越界访问if (ps-size0){return;}int begin 0;while (begin ps-size){ps-a[begin] ps-a[begin1];//将后一个数据往前移动begin;}ps-size–;//减少一个数字有效数据减1 } 这里的删除并不是真正意义上的删除我们只需要将原来的数据往前移动一位使后一位的数据覆盖在前一位这就做到了删除顺便再将有效数据减1就行。  3.3在pos位置插入x void SLInsert(SL* ps, int pos, int x) {assert(pos 0 pos ps-size);//防止越界访问SLCheckcapacity(ps);int end ps-size;while (end pos){ps-a[end] ps-a[end-1];//和头插的思想差不多将数据后移end–;}ps-a[pos] x;//将x赋值给pos位置ps-size;//有效数据加1 } 我们可以这样理解将pos看成初始位置是不是就转化为头插了按照头插的思想就可以完成在pos位置上插入x。  3.4删除pos位置的值 void SLErase(SL* ps, int pos) {assert(pos 0 pos ps-size);//防止越界访问SLCheckcapacity(ps);int begin pos;while (begin ps-size){ps-a[begin] ps-a[begin 1];//和头删的思想差不多将数据前移begin;}ps-size–;//有效数据减1 } 我们会发现3.4和3.5不仅可以做到某个位置值的插入和删除也可以做到尾插尾删和头插头删。  3.5修改某个位置的值 void SLModify(SL* ps, SLDatatype pos, SLDatatype x) {assert(pos 0 pos ps-size);//防止越界ps-a[pos] x; } 这样修改某个位置的值看起来是挺麻烦但是是为了安全考虑。 四、完整代码 #define _CRT_SECURE_NO_WARNINGS 67 #includestdio.h #includeassert.h #includestdlib.h //静态顺序表 //#define N 100 //struct SeqList //{ // int a[N];//定长数组 // int size;//有效数据的个数 //};//动态顺序表//创建 typedef int SLDatatype; typedef struct SeqList {SLDatatype* a;//指向动态开辟的数组SLDatatype capacity;//容量SLDatatype size;//有效数据的个数}SL; //传值初始化 //void SLInit(SL s) //{ // s.a NULL; // s.size 0; // s.capacity 0; //} //传址初始化 //void SLInit(SL* ps) //{ // ps-a 0; // ps-capacity 0; // ps-size 0; //} void SLInit(SL* ps) {ps-a (SLDatatype*)malloc(sizeof(SLDatatype) * 4);//开辟了4个字节的空间if (ps-a NULL){perror(malloc failed);exit(-1);}ps-capacity 4;ps-size 0; } //清空 void SLDestr(SL* ps) {free(ps-a);ps-a NULL;ps-capacity 0;ps-size 0; } //打印 void SLprint(SL* ps) {int i 0;for (i 0; i ps-size; i){printf(%d , ps-a[i]);}printf(\n); } //检查容量 void SLCheckcapacity(SL* ps) {if (ps-size ps-capacity){SLDatatype* tmp (SLDatatype*)realloc(ps-a, ps-capacity * 2 *( sizeof(SLDatatype)));//扩容尾原来的倍数if (tmp NULL){perror(realloc failed);exit(-1);}ps-a tmp;ps-capacity * 2;} } //尾插 void SLPushBack(SL* ps, SLDatatype x) {SLCheckcapacity(ps);ps-a[ps-size] x;ps-size; } //尾删 void SLPopBack(SL* ps) {assert(ps-size 0);if (ps-size 0){return;}ps-size–; } //头插 void SLPushFront(SL* ps, SLDatatype x) {SLCheckcapacity(ps);int end ps-size;while (end 0){ps-a[end] ps-a[end - 1];end–;}ps-a[0] x;ps-size; } //头删 void SLPopFront(SL* ps) {assert(ps-size 0);if (ps-size0){return;}int begin 0;while (begin ps-size){ps-a[begin] ps-a[begin1];begin;}ps-size–; } //在pos位置插入x void SLInsert(SL* ps, int pos, int x) {assert(pos 0 pos ps-size);SLCheckcapacity(ps);int end ps-size;while (end pos){ps-a[end] ps-a[end-1];end–;}ps-a[pos] x;ps-size; } //删除pos位置的值 void SLErase(SL* ps, int pos) {assert(pos 0 pos ps-size);SLCheckcapacity(ps);int begin pos;while (begin ps-size){ps-a[begin] ps-a[begin 1];begin;}ps-size–; } int SLFind(SL* ps, int x) {int i 0;for (i 0; i ps-size; i){if (ps-a[i] x)return i;}return -1; }void SLModify(SL* ps, SLDatatype pos, SLDatatype x) {assert(pos 0 pos ps-size);ps-a[pos] x; } int main() {SL s1;//传值初始化//SLInit(s1);//传址初始化SLInit(s1);//尾插SLPushBack(s1, 1);SLPushBack(s1, 2);SLPushBack(s1, 3);SLPushBack(s1, 4);SLPushBack(s1, 5);SLPushBack(s1, 6);SLPushBack(s1, 7);//尾插测试printf(尾插:\n);SLprint(s1);//尾删SLPopBack(s1);//尾删测试printf(尾删:\n);SLprint(s1);//头插SLPushFront(s1,10);//头插测试printf(头插:\n);SLprint(s1);//头删 SLPopFront(s1);//头删测试printf(头删:\n);SLprint(s1);//在pos位置插入xSLInsert(s1, 0, 100);//pos插入x测试printf(pos位置插入x\n);SLprint(s1);//删除pos位置的值SLErase(s1, 0);//测试printf(删除pos位置的值\n);SLprint(s1);//改SLModify(s1, 2, 1);printf(修改某个位置上的值:\n);//SLprint(s1);//清空SLDestr(s1);return 0; }