免费发广告网站,做网站用c语言可以吗,北京做环评备案的网站,适合女生做的网站主题当我们写完通讯录后#xff0c;顺序表肯定难不倒你#xff0c;跟着小张一起来学习顺序表吧#xff01; 线性表 线性表#xff08;linear list#xff09;是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构#xff0c;常见的线性表#x… 当我们写完通讯录后顺序表肯定难不倒你跟着小张一起来学习顺序表吧 线性表 线性表linear list是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储。 顺序表
概念及结构
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组上完成数据的增删查改。 顺序表一般可以分为
静态顺序表使用定长数组存储元素。 动态顺序表使用动态开辟的数组存储。
接口实现
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了空间开多了浪费开少了不够用。所以现实中基本都是使用动态顺序表根据需要动态的分配空间大小所以下面我们实现动态顺序表。
typedef struct pro
{int* p;// 指向动态开辟的数组int size;// 有效数据个数int capcity;// 容量空间的大小}pro;
void SeqListInit(pro* ps );//初始化顺序表
void CheckCapacity(pro* ps);//判断是否空间不够进行扩容
void SeqListPushBack(pro* ps,int x);//尾插
void SeqListPushFront(pro* ps, int x);//头插
void SeqListPopBack(pro* ps);//尾删
void SeqListPopFront(pro* ps);//头删
void SeqListPrint(pro* ps);//打印顺序表
void SeqListInsert(pro* ps, int pos, int x);//随意插
void SeqListErase(pro* ps, int pos);//随意删
void SeqListFind(pro* ps, int pos);//查找
void SeqListmodify(pro* ps, int x,int y);//修改
void SeqListDestory(pro* ps);//销毁结构体定义和创建一个结构体变量
typedef struct pro
{int* p;// 指向动态开辟的数组int size;// 有效数据个数int capcity;// 容量空间的大小}pro;
int main()
{pro info;//定义一个结构体变量
}初始化顺序表
void SeqListInit(pro* ps )//初始化顺序表
{ps-p NULL;ps-size 0;ps-capcity 0;}初始化顺序表有效数据个数为0容量空间大小为0还未给数据动态开辟空间指向动态开辟空间的指针指向空地址 扩容顺序表
void CheckCapacity(pro* ps)//判断是否空间不够进行扩容
{if (ps-size ps-capcity){int newcapcity ps-capcity 0 ? 4 : (ps-capcity) * 2;int* tmp (int*)realloc(ps-p, sizeof(int) * newcapcity);if (tmp NULL){perror(realloc fail!!);}ps-p tmp;ps-capcity newcapcity;}}什么时候需要扩容顺序表呢当顺序表刚被初始化你要进行插入数据时发现容量空间已经满了此时必须要扩容空间当你要插入第一个数据时在此之前顺序表没有任何数据容量空间为0然后要插入数据的话也必须扩容。 条件判断如果有效数据个数等于容量大小时分两种情况第一种刚开始的时候有效数据个数和容量大小都为0的时候第二种当要插入数据时发现此时的有效数据个数和容量大小相等时且不等于0.对空间进行扩容 newcapcity变量是新的容量大小当需要扩容的时候直接新容量为原来的2倍刚开始他的容量是0采用三目运算符如果容量是0的话就给四个空间大小如果不是就开原来容量的2倍。将realloc来的空间的地址存放在tmp指针里面如果realloc失败就返回空指针打印错误信息realloc成功的话就将tmp中存放扩容的地址交给指针p,然后容量大小更新为newcapcity。 尾插
void SeqListPushBack(pro* ps,int x)//尾插
{CheckCapacity(ps);ps-p[ps-size] x;ps-size;}每次插入都要判断是否需要扩容 然后有效数据1. 头插
void SeqListPushFront(pro* ps, int x)//头插
{CheckCapacity(ps);int end ps-size - 1;while (end0){ps-p[end 1] ps-p[end];end--;}ps-p[0] x;ps-size;}头插一个数据必须将后面的数据向后面移动移动的过程中可能超过容量大小所以在插入时都需要进行扩容判断 如果按这个顺序移动数据当1挪到2的位置的时候2这个数据就会被覆盖所以我们必须从后往前面挪 当数据挪到后面之后然后在第一个位置填入x,第一个位置也就是下标为0的位置。 在下标为0的地方填入 插入的数据x,然后ps-size1;
尾删
void SeqListPopBack(pro* ps)//尾删
{assert(ps);assert(ps-size 0);ps-size--;}尾巴要删除一个数据的话我们需要将删除的数据改为0吗如果要删除的数据本来就是0呢所以我们只需要将ps-size–;因为打印的时候只打印到下标为ps-size-1的位置打印出来看起来就像 我们删除了这个数据注意这里用断言是因为在删除的时候ps-size–,当ps-size0的时候在添加数据时 ps-p[-1]x;这个是不合理的在ps-size0时直接报错第一个断言是为了防止空指针。 头删
void SeqListPopFront(pro* ps)//头删
{assert(ps-size 0);int begin 1;while (beginps-size){ps-p[begin - 1] ps-p[begin];begin;}ps-size--;}这里的断言和上面是一个道理然后相比尾删向后挪动数据头删是往前挪数据吸取尾删的教训我们可以直到移动的顺序是 定义一个变量begin1,首先是要将数据2移动到数据1的位置对应的操作是 ps-p[begin - 1] ps-p[begin];然后begin,依次将数据3挪到数据2的位置数据4挪到数据3的位置。循环最后一次是将数据5挪到数据4的位置也就是begin4,ps-size5.则循环判断条件为beginsize,循环结束后将 ps-size–;
顺序表的打印
void SeqListPrint(pro* ps)//打印顺序表
{for (int i 0; i ps-size; i){printf(%d , ps-p[i]);}}循环遍历顺序表将每个数据打印出来 随意插
void SeqListInsert(pro* ps, int pos, int x)//随意插
{CheckCapacity(ps);assert(pos0posps-size);int end ps-size - 1;while (endpos){ps-p[end 1] ps-p[end];end--;}ps-p[pos] x;ps-size;
}断言是为了检查插入的位置是否合理 当有5个数据时pos的可能取值如图所示推广到一般 就是pos0posps-size,如果我们想在pos2的位置插入一个x,我们应该怎么做呢 1.插入一个x,我们需要将345向后移动必须先移动5定义一个变量end, end变量的初值给ps-size-1也就是4要想将数据5向后挪动对应的操作是ps-p[end 1] ps-p[end];然后end–;循环分别将43向后挪动循环结束后将数据x插入到pos2的位置对应操作为ps-p[pos] x;然后有效数据大小ps-size 随意删
void SeqListErase(pro* ps, int pos)//随意删
{int begin pos;assert(pos 0 pos ps-size);while (beginps-size-1){ps-p[begin] ps-p[begin1];begin;}ps-size--;
}断言判断删除的数据的位置是否合理和随意插的那里一样 如果我们要删除数3然后数据3后面的数据向前挪动第一步就是将数据4移动到数据3的位置定义一个变量beginpos2;对应的操作为 ps-p[begin] ps-p[begin1];然后begin;将数据5移动到最开始数据4的地方。最后一次循环是将数据5移动到数据4的地方也就是begin最后等于3ps-size5则循环判断条件是begin ps-size-1,循环结束将ps-size–; 顺序表的查找
void SeqListFind(pro* ps, int pos)//查找
{assert(pos 0 pos ps-size);printf(你查找的下标是%d,对应的数据是%d, pos, ps-p[pos]);
}断言保证查找位置的合理性因为函数传参pos 刚好是要查找数据的下标直接打印出来 顺序表的修改
void SeqListmodify(pro* ps, int x,int y)//修改
{for (int i 0; i ps-size; i){if (x ps-p[i]){ps-p[i] y;}}}x为修改前的值y是修改之后的值循环遍历顺序表将顺序表中所有的x都修改成y 顺序表的销毁
void SeqListDestory(pro* ps)//销毁
{ps-capcity 0;ps-size 0;free(ps-p);ps-p NULL;}销毁一个顺序表将顺序表的容量置为0顺序表的有效数据个数置为0将p指针所指向的动态开辟的内存空间释放了由于释放了动态开辟的内存空间所有p指向的空间未初始化p成为野指针为了防止野指针将p置为空指针。 整体代码
#include stdio.h
#include stdlib.h
#include assert.h
typedef struct pro
{int* p;// 指向动态开辟的数组int size;// 有效数据个数int capcity;// 容量空间的大小}pro;
void SeqListInit(pro* ps )//初始化顺序表
{ps-p NULL;ps-size 0;ps-capcity 0;}
void CheckCapacity(pro* ps)//判断是否空间不够进行扩容
{if (ps-size ps-capcity){int newcapcity ps-capcity 0 ? 4 : (ps-capcity) * 2;int* tmp (int*)realloc(ps-p, sizeof(int) * newcapcity);if (tmp NULL){perror(realloc fail!!);}ps-p tmp;ps-capcity newcapcity;}}
void SeqListPushBack(pro* ps,int x)//尾插
{CheckCapacity(ps);ps-p[ps-size] x;ps-size;}
void SeqListPushFront(pro* ps, int x)//头插
{CheckCapacity(ps);int end ps-size - 1;while (end0){ps-p[end 1] ps-p[end];end--;}ps-p[0] x;ps-size;}
void SeqListPopBack(pro* ps)//尾删
{assert(ps);assert(ps-size 0);ps-size--;}
void SeqListPopFront(pro* ps)//头删
{assert(ps-size 0);int begin 1;while (beginps-size){ps-p[begin - 1] ps-p[begin];begin;}ps-size--;}
void SeqListPrint(pro* ps)//打印顺序表
{for (int i 0; i ps-size; i){printf(%d , ps-p[i]);}}
void SeqListInsert(pro* ps, int pos, int x)//随意插
{CheckCapacity(ps);assert(pos0posps-size);int end ps-size - 1;while (endpos){ps-p[end 1] ps-p[end];end--;}ps-p[pos] x;ps-size;
}
void SeqListErase(pro* ps, int pos)//随意删
{int begin pos;assert(pos 0 pos ps-size);while (beginps-size-1){ps-p[begin] ps-p[begin1];begin;}ps-size--;}
void SeqListFind(pro* ps, int pos)//查找
{assert(pos 0 pos ps-size);printf(你查找的下标是%d,对应的数据是%d, pos, ps-p[pos]);
}
void SeqListmodify(pro* ps, int x,int y)//修改
{for (int i 0; i ps-size; i){if (x ps-p[i]){ps-p[i] y;}}}
void SeqListDestory(pro* ps)//销毁
{ps-capcity 0;ps-size 0;free(ps-p);ps-p NULL;}
int main()
{pro info;SeqListInit(info);printf(尾插:);SeqListPushBack(info, 1);SeqListPushBack(info, 2);SeqListPushBack(info, 3);SeqListPushBack(info, 4);SeqListPrint(info);printf(\n);printf(头插:);SeqListPushFront(info, 7);SeqListPushFront(info, 6);SeqListPushFront(info, 5);SeqListPushFront(info, 5);SeqListPrint(info);printf(\n);printf(尾删:);SeqListPopBack(info);SeqListPrint(info);printf(\n);printf(头删:);SeqListPopFront(info);SeqListPrint(info);printf(\n);printf(随意插:);SeqListInsert(info, 1, 1);SeqListPrint(info);printf(\n);printf(随意删:);SeqListErase(info,1,1);SeqListPrint(info);printf(\n);printf(查找:);SeqListFind(info, 3);printf(\n);printf(修改:);SeqListmodify(info, 1, 2);SeqListPrint(info);printf(\n);printf(销毁:);SeqListDestory(info);SeqListPrint(info);
}
