赞
踩
首先,学习历程重重困难,文章一定会难以避免的冗长,所以在前面先附上我制作的思维导图,这个是线性表总的思维导图hh(包括链表),大家可以先点进去看,思维导图是用的知犀思维导图,不过我觉得好像不用下载那个点开链接输入密码后也可以看,我觉得思维导图的表现力应该比文字更好hh,所以大家可以先看这个思维导图,有个大致的思路hh
思维导图在这里!密码:1836
线性表是一种最常见的结构,其中,由数组或动态数组组成的叫做线性表或静态数组,有指针指向的叫单链表,循环链表或双向链表
这里我们先说线性表~
从名字上你就可以感觉到,线性表就是有像线一样性质的表就比如说排列有序的小朋友一样。
故而我们可以得到线性表的定义:零个或多个数据元素的有限序列
这里需要强调几个地方:
现在,大家想一下,线性表可以有什么操作呢?
利用数组的连续存储空间顺序存放线性表的各元素
访问下标为i的元素:L.Date[i]或ptrl->Date[i]
线性表的长度:L.Last+1或ptrl->Last+1
#define MAXSIZE 20//存储空间初始分配量
typedef int ElemType//ElemType类型根据实际情况而定,这里为int
typedef struct
{
ElemType date[MAXSIZE];//数组,存储当前元素
int length;//线性表当前长度
}SqList;
这里就发现了描述顺序存储结构需要的三个属性
存储器中每个存储单元都有自己的编号,这个编号称为地址
我们可以发现,在数组中,每两个相邻的元素的地址差异是它的数据类型所占用的存储单元空间,故而我们要算出线性表中的任意位置的地址,只需要套入公式即可(中间差了几个数据类型的存储单元的距离就是它离第一个数组元素的距离)这样只需要O(1)就可以算出来地址的存储结构,我们称它为随机存储结构
在线性表的存储结构当中,要实现查找操作其实是非常简单的,就程序而言,只需要i的值在数组下标范围内,将数组第i-1下标的值返回即可,来看代码
#define OK 1
#define ERROR 0
//Status是函数的类型,其值是函数结果状态代码,如ok等
typedef int Status;
//初始条件:顺序线性表L已存在,1<=i<=ListLength(l)
//操作结果:用e返回L中第i个数据元素的值,注意i是指位置,第1个位置的数组是从0开始的
Status GetElem(SqList L,int i,ElemType *e)
{
if(L.length==0||i<1||i>L.length)return ERROR;
*e=L.data[i-1];
return OK;
}
在这里,插入操作其实很好理解,就是插入一个元素,然后将插入位置后的所有元素都向后排一位就可以。
故而我们可以写出插入算法的思路:
/* 初始条件:顺序线性表L已存在,1≤i≤ListLength(L), */ /* 操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1 */ Status ListInsert(SqList *L,int i,ElemType e) { int k; if (L->length==MAXSIZE) /* 顺序线性表已经满 */ return ERROR; if (i<1 || i>L->length+1) /* 当i比第一位置小或者比最后一位置后一位置还要大时 */ return ERROR; if (i<=L->length) /* 若插入数据位置不在表尾 */ { for(k=L->length-1;k>=i-1;k--) /* 将要插入位置后的元素向后移一位 */ L->data[k+1]=L->data[k]; } L->data[i-1]=e; /* 将新元素插入 */ L->length++; return OK; }
所谓删除,就是指删除数组中的某一元素,然后将该位置后面的剩余的元素分别向后移动一格。
故而我们就有了删除算法的思路:
/* 初始条件:顺序线性表L已存在,1≤i≤ListLength(L) */ /* 操作结果:删除L的第i个数据元素,并用e返回其值,L的长度减1 */ Status ListDelete(SqList *L,int i,ElemType *e) { int k; if (L->length==0) /* 线性表为空 */ return ERROR; if (i<1 || i>L->length) /* 删除位置不正确 */ return ERROR; *e=L->data[i-1]; if (i<L->length) /* 如果删除不是最后位置 */ { for(k=i;k<L->length;k++)/* 将删除位置后继元素前移 */ L->data[k-1]=L->data[k]; } L->length--; return OK; }
线性表顺序存储结构是一个以数组为存储单元的一种常见的结构,其中可以做初始化,插入,删除等操作,在操作函数中,如果需要改动则传递指向这个参数的指针,如果不需要改动,则可以直接传递这个参数,可以快速读取任意位置的元素,但是插入删除需要大量的时间。
赞
踩
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。