石家庄城乡建设厅网站,wordpress 翻页错误,asp网站转手机站,wordpress html5 爱情#xff08;1#xff09;博客代码在数据结构代码---GitHub仓库#xff1b;线性表介绍线性表的基础概念#xff08;1#xff09;甲骨文表示#xff1a;线性表是零个或多个数据元素的有限序列。#xff08;2#xff09;线性表#xff0c;顾名思义#xff0c;就是说这个…1博客代码在数据结构代码---GitHub仓库线性表介绍线性表的基础概念1甲骨文表示线性表是零个或多个数据元素的有限序列。2线性表顾名思义就是说这个数据存储是线性的。而线性的东西具有什么特征呢1数据是一对一的排列的中间的数据都有且仅有一个前面数据前面的数据叫做前驱和一个后面的数据后面的数据叫做后继。而数据表的最前面的数据叫做表头最尾端的数据叫做表尾。表头无前驱表尾无后继。2线性表是有限的。因为计算机的存储空间是有限的所以线性表必然有限。3线性表中的元素必须是相同类型。这个就像是我们在定义数组一个数组中的元素要么都是int型数据要么都是char型数据不可能数组中第一个元素是int型数据第二个元素变成了char型数据了。3线性表的元素个数nn0表示线性表的长度当n0时我们将这个表称之为空表。4在非空表中每个数据元素都有一个确定的位置比如a1就是第一个数据元素a2就是第二个数据元素ai就是第i个数据元素。所以我们将i称为数据元素的位序。一个数据元素可以拥有多个数据项1我们上面看到一个数据元素只有一个数据项。在数据结构1前言中我说了一个数据元素可以有多个数据项在研究数据结构时我们都是着眼于数据元素。那有没有一个数据元素拥有多个数据项的线性表呢有我们常见的就是花名册。2我们看到如下花名册里面有姓名性别文化程度等等一些元素。这些元素就是数据项。而人具有这些元素所以人这个个体就是数据元素。我们将这些人进行按照顺序排列最后形成了花名册这也叫做线性表。线性表种类1常见的线性表有顺序存储说白了就是数组是链式存储栈队列。2链式存储中又分为四种单链表静态链表循环链表双向链表。线性表顺序存储介绍顺序存储定义定义1定义线性表的顺序存储结构指的是用一段地址连续的存储单元依次存储线性表的数据元素。2将上面这段话用白话文来说就是线性表的顺序存储就是一个数组不过与数组有些许不同数据结构中的顺序存储定义需要增加一个length用于显示线性表的当前长度。3这个时候可能会有人有疑惑了。为什么需要一个length呢假设我们在排队买东西由于空间的限制只能来20个人MAXSIZE。而这个时候排队的有5个人如果有第6个人也要来排队因为人很聪明知道排到第五个人后面就可以了但是在写程序的时候你怎么知道需要将新来的数据放在哪里呢如果不小心放在了第4个空间中那么数据会被覆盖出问题。放在第7位那么第6位空着浪费空间。4线性表的顺序存储就是一个排队的过程MAXSIZE用于定义这个队伍最大多长而length用于指示当前位置排到哪里了。如果中间一个人突然走了从这个人开始的后面所有人都要往前面移动同时length要马上自减一次。如果有一个人因为紧急事件不得不插队从插队的位置往后移动所有人都需要往后移动length需要马上自增一次。5因为按照编程习惯我们的数组首元素下标为0。所以当线性表为空的时候last为-1而last1时候线性表长度last11#define success 0
#define fail -1
#define MAXSIZE 20 /* 存储空间初始分配量 */typedef int ElemType; /* ElemType类型根据实际情况而定这里假设为int */typedef struct
{ElemType data[MAXSIZE]; /* 数组存储数据元素 */int last; /* 线性表当前位置last1length */
}SqList,*SqLink; /*SqList是定义线性表SqLink是定义线性表的结构体指针*/顺序存储方式和地址计算其实如果学了C语言数组了这部分没有什么可以说的。就是跟数组那样存储是连续的。不清楚的自行去重新学习数组的知识。数组长度与线性表长度区别1我们上面说了MAXSIZE是数组长度这个规定了能够放进来多少数据他的值是固定的。而length是线性表长度他的长度是会随着线性表的删除插入等操作发生改变是动态的。任意时刻lengthMAXSIZE。2至于为什么数组不改成动态分配是因为这会带来性能上的消耗。我查了一些资料以及问了bingAI剥去关于没有及时释放不用的内存以外更多的是malloc和free会造成资源消耗。顺序存储实操这里需要说的是如果是操作成功了返回0操作失败返回-1。#define success 0
#define fail -1
#define MAXSIZE 20 /* 存储空间初始分配量 */typedef int ElemType; /* ElemType类型根据实际情况而定这里假设为int */typedef struct
{ElemType data[MAXSIZE]; /* 数组存储数据元素 */int last; /* 线性表当前位置last1length */
}SqList,*SqLink; /*SqList是定义线性表SqLink是定义线性表的结构体指针*/创建顺序存储线性表1我们先申请一个结构体指针然后分配一个空间过来如果没有分配成功将会打印提示。2如果创建成功之后因为刚刚申请的空间中存放的值是未知的。所以按照习惯我们一般都会将其设置为0。3注意memset函数必须写在 L - length -1; 前面因为memset这一步会将 L - length 变成0。因为按照数组下标的习惯0表示首元素地址所以当线性表为空的时候length-1。可能在部分教材里面length0表示线性表为空所以下面关于length部分代码会有所差异需要注意/*作用: 创建线性表*传入参数无*返回参数创建失败打印错误报告创建成功返回创建线性表的结构体指针*/
SqLink list_create(void)
{//建立线性表SqLink L;L (SqLink)malloc(sizeof(SqList));//确认线性表是否存在if(L NULL){printf(list malloc failed!\n);return L;}//线性表存在将其内容清空//注意这两句别写反了否则last会变成0。memset(L , 0 , sizeof(SqList));L - last -1; //last表示线性表的指向位置因为在C语言中下标是从0开始所以当为空表是last-1//返回线性表return L;
}判断线性表是否存在判断线性表是否存在我们可以检测他指向的地址是否有问题。/*作用: 判断线性表是否存在*传入参数* L: 线性表的结构体指针*返回参数线性表不存在返回fail线性表存在返回success*/
int list_if_exist(SqLink L)
{if(LNULL){printf(list is not exist!\n);return fail;}return success;
}删除线性表1如果线性表为NULL表示传入线性表不存在打印提示。2如果线性表存在将释放内存同时将指针指向NULL。/*作用: 删除线性表*传入参数* L: 线性表的结构体指针*返回参数线性表不存在返回fail线性表成功删除返回success*/
int list_delete(SqLink L)
{if(LNULL){printf(list is not exist!\n);return fail;}free(L);LNULL;return success;
}清空线性表解析看创建顺序存储线性表。/*作用: 清空线性表*传入参数* L: 线性表的结构体指针*返回参数成功返回succes,失败返回fail*/
int list_clear(SqLink L)
{//确认线性表是否存在if(L NULL){printf(list is not exist!\n);return fail;}//线性表存在将其内容清空//注意这两句别写反了否则last会变成0。memset(L , 0 , sizeof(SqList));L - last -1; //last表示线性表的指向位置因为在C语言中下标是从0开始所以当为空表是last-1return success;
}判断线性表是否为空1先判断线性表是否存在2我们只需要判断length即可。如果对于length是什么依旧不清楚的看下图。/*作用: 判读线性表是否为空(因为使用者并不知道函数实现具体细节所以需要加上这个)*传入参数* L: 线性表的结构体指针*返回参数线性表为空返回succes,否则返回fail*/
int list_if_empty(SqLink L)
{//确认线性表是否存在if(LNULL){printf(list is not exist!\n);return fail;}if(L - last -1){printf(list is empty!\n);return success;}return fail;
}获取当前线性表长度获取线性表长度就看length1即可。/*作用: 查看当前线性表长度*传入参数* L: 线性表的结构体指针*返回参数返回当前线性表的长度*/
int list_get_length(SqLink L)
{//确认线性表是否存在if(LNULL){printf(list is not exist!\n);return fail;}return (L-last1);
}判断指定数值是否在线性表中1先判断线性表是否存在2我们只需要将线性表中的值一个一个的与value对比即可。/*作用: 判断value是否在线性表中*传入参数* L:线性表的结构体指针* value:需要查看线性表中是否存在的值* 可输入值范围受到ElemType决定*返回参数value在线性表中存在返回succes,value不在线性表中或线性表不存在返回fail*/
int list_value_if_locate(SqLink L,ElemType value)
{int i;//确认线性表是否存在if(LNULL){printf(list is not exist!\n);return fail;}//逐个判断线性表中的值for(i 0;iL-last;i){if(L-data[i]value){return success;}}return fail;
}在线性表指定位置插入数据1判断线性表是否存在2先判断线性表是否已经满了3判断插入位置是否合理4将要插入的位置元素都向后移动腾出空间让新数据插入5插入新数据last自增/*作用: 插入数据在线性表L的pos处插入数据value*传入参数* L: 线性表的结构体指针* value: 需要插入线性表的值* 可输入值范围受到ElemType决定* pos需要插入的位置* 插入位置范围受到MAXSIZE限制*返回参数返回当前线性表的长度*/
int list_insert(SqLink L,ElemType value,int pos)
{int i; //确认线性表是否存在if(LNULL){printf(list is not exist!\n);return fail;}//如果线性表满了if(L-last MAXSIZE-1){printf(list is full\n);return fail;}//判断插入的位置是否合法if(pos0 || pos L-last1){printf(pos is invaild\n);}//向后移动for(i L - last;i pos;i--){L-data[i1]L-data[i];}//更新last和插入部分数值L-data[pos]value;L-last;return success;
}删除指定位置元素1检查线性表是否存在2是否为空表4删除位置是否合理5将所有数据向前移动此时原来pos位置的数据会被pos1处覆盖6last自减/*作用: 删除指定位置的元素*传入参数* L: 线性表的结构体指针* pos 需要删除的数据的位置* 插入位置范围受到MAXSIZE限制*返回参数删除失败返回fail成功删除返回success*/
int list_delete_pos_value(SqLink L,int pos)
{int i;//确认线性表是否存在if(LNULL){printf(list is not exist!\n);return fail;}//检测是否为空表if(L-last-1){printf(list is empty!\n);return fail;}//检测删除位置是否合理if(pos 0 || pos L-last){printf(pos is invalid\n);return fail;}//向前移动for(ipos1;iL-last;i){L-data[i-1]L-data[i];}//更改lastL-last--;return success;
}获取两个线性表的并集1判断三个线性表是否存在2判断他们是否为空3先将L1的值存入L3中4然后将L2中拥有但是L1中没有的值存入L3中/*作用: L1和L2并集将并集值给到L3*传入参数* L1L2: 两个不同的线性表* L3 L1和L2并集*返回参数失败返回fail成功返回success*/
int list_merge(SqLink L1,SqLink L2,SqLink L3)
{int i;//判断L1L2L3是否存在list_if_exist(L1);list_if_exist(L2);list_if_exist(L3);//判断L1L2,是否为空list_if_empty(L1);list_if_empty(L2);//将L1中的所有元素存放到L3中for(i 0; i L1-last;i){list_insert(L3, L1-data[i],L3-last1);}for(i 0; i L2-last;i){//判读L2中的每一个元素是否在L1中,如果不在就存入到L3中if(list_value_if_locate(L1,L2-data[i])-1){//如果L3满了提前结束if(list_insert(L3,L2-data[i],L3-last1)fail){return fail;}}}return success;
}删除线性表中重复元素1判断线性表是否存在2如果只有一个元素就不需要判断3我们选择从第二个元素开始建立变量i判断i位置的元素是否与i前面元素有重复如果重复了那么就删除i位置的元素。此时可以跳出循环。4因为删除位置i的元素之后原来位置i1的元素会替补到位置i处。所以我们需要先将位置i自减一次然后在for语句中自增一次为了保持位置i不变所以我们需要i自减一次抵消。5如果没有重复元素那么i就自增。/*作用:删除线性表中重复元素*传入参数* L1 : 线性表的结构体指针*返回参数删除成功返回success*/
int list_purge(SqLink L)
{int i,j;//确认线性表是否存在if(LNULL){printf(list is not exist!\n);return fail;}//如果当前线性表只有一个元素就没有必要判断了if(L-last0){return success;}//让i不断向后移动for(i1;iL-last;i){//将位置i之前的元素与i处元素进行判断相同就删除for(ji-1;j0;j--){//如果发现前面有与位置i相同的元素删除保持i不动if(L-data[i]L-data[j]){//位置i与前面有重复就删除位置i的值list_delete_pos_value(L,i);//因为需要保持位置i不动而for语句中有i所以这里用i--抵消i--;break;}}}return success;
}获取指定位置元素1判断线性表是否存在2判断是否为空表3判断获取数据的位置是否合理4返回指定位置值/*作用: 返回指定位置的值*传入参数* L: 线性表的结构体指针* pos指定位置* 插入位置范围受到MAXSIZE限制*返回参数线性表为空返回fail。成功打印返回success*/
int list_pos_value(SqLink L,int pos)
{//判断线性表是否存在if(LNULL){printf(list is not exist!\n);return fail;}//判断是否为空表if(L-last-1){printf(list is empty!\n);}//判断获取数据的位置是否合法if(pos0 || pos L-last1){printf(pos is invaild\n);}//返回指定位置值return (L-data[pos]);
}显示线性表中的值1线性表是否存在2是否为空表3逐个打印线性表中的元素/*作用: 显示线性表中的值*传入参数* L: 线性表的结构体指针*返回参数线性表为空返回fail。成功打印返回success*/
int list_show(SqLink L)
{int i;//判断线性表是否存在if(LNULL){printf(list is not exist!\n);return fail;}//判断是否为空表if(L-last-1){printf(list is empty!\n);}//将线性表中的值打印出来for(i0;iL-last;i){printf(%d ,L-data[i]);}printf(\n);return success;
}线性表顺序结构优缺点优点1存储密度高2查找线性表中元素也方便缺点1需要提供一大片较大的连续存储空间。2插入删除等运算耗时存在元素在存储空间成片移动的现象总结如果我们需要插入删除操作比较多比如游戏开发中的装备经常会更换这个用线性存储就非常不合适链式存储就比较好。但是如果我们需要频繁查找元素比如查找游戏ID查看用户性别等等用顺序存储就很方便。
