Wordpress网站调用代码,网站友情链接模板,哪个网站可做密丸,上海网站建设培训学校1、线性表的顺序存储表示定义#xff1a;
线性表#xff1a;是具有相同数据类型的n #xff08;n≥0#xff09;个数据元素的有限序列
顺序表#xff1a;用顺序存储的方式实现线性表
顺序存储#xff1a;把逻辑上相邻的元素存储在物理 位置上也相邻的存储单元中#…1、线性表的顺序存储表示定义
线性表是具有相同数据类型的n n≥0个数据元素的有限序列
顺序表用顺序存储的方式实现线性表
顺序存储把逻辑上相邻的元素存储在物理 位置上也相邻的存储单元中元素之间的关 系由存储单元的邻接关系来体现。
ElemType 就是你的顺序表中存放的数据元素类型 2、顺序表的存储结构
2.1、顺序表的实现——静态分配
给各个数据元素分配连续的存储空间大小为 MaxSize*sizeof(ElemType)
#include stdio.h
#define MaxSize 10 //定义最大长度typedef struct {int data[MaxSize]; //用静态的“数组”存放数据元素int length; //顺序表的当前长度
} SqList;// 初始化顺序表
void InitList(SqList L) {L.length 0; // 顺序表初始化长度为0
}int main(){SqList L; //声明一个顺序表InitList(L); //初始化顺序表//尝试 “违规 ” 打印整个 data 数组
// printf(data[%d]%d\n, L.data);for(int i0;iMaxSize;i)printf(data[%d]%d\n, i, L.data[i]);return 0;
}
2.2、顺序表的实现——动态分配 #include stdio.h
#include stdlib.h
#define MaxSize 10 //定义最大长度typedef struct {int *data; //指示动态分配数组的指针int length;//顺序表的当前长度int MaxSize; //顺序表的最大容量
} SqList;void InitList(SqList L){
//用 malloc 函数申请一片连续的存储空间
L.data(int *)malloc(InitSize*sizeof(int));
L.length0;
L.MaxSizeInitSize;
}//增加动态数组的长度
void IncreaseSize(SqList L,int len){int *pL.data;L.data(int *)malloc((L.MaxSizelen)*sizeof(int));for(int i0; iL.length; i){L.data[i]p[i];//顺序表最大长度增加 len,时间开销大}L.MaxSizeL.MaxSizelen;free(p);//释放原来的内存空间}int main(){SqList L; //声明一个顺序表InitList(L); //初始化顺序表IncreaseSize(L,5);free(L.data);return 0;
} 3、顺序表中基本操作的实现
3.1、初始化
顺序表的初始化操作就是构造一个空的顺序表。 为顺序表L动态分配一个预定义大小的数组空间使 elem 指向这段空间的基地址。 将表的当前长度设为0。 动态分配线性表的存储区域可以更有效地利用系统的资源 当不需要该线性表时 可以使用 销毁操作及时释放占用的存储空间。 【算法描述】 //构造一个空的顺序表L
Status Initlist(SqList L){L.elemnew Elemrype [MAXSIZE];//为顺序表分配一个大小为 MAXSI2E的数组空间if(!L.elem)exit(OVERFLON);//存储分配失败退出L.length0;//空表长度为 0return OK;
}
3.2、取值
取值操作是根据指定的位置序号i, 获取顺序表中第i个数据元素的值。 由于顺序存储结构具有随机存取的特点 可以直接通过数组下标定位得到elem[-1]单元存储第i个数据元素。顺序表取值算法的时间复杂度为0(1)。
Status GetElem(SqList L,int i, ElemType e
{if {ill liL.length) return ERROR; //判断i值是否合理若不合理 返回 ERROReL.elem[i-1]; //elem[i-1] 单元存储第i个数据元素return OK;
}i
3.3、查找 查找操作是根据指定的元素值e, 查找顺序表中第1个与e相等的元素。若查找成功则返回该元素在表中的位置序号若查找失败则返回0。 从第一个元素起依次和 e相比较若找到与 e相等的元素 L.elem[i], 则查找成功返回该元素的序号 i1。 若查遍整个顺序表都没有找到则查找失败 返回0。 顺序表按值查找算法的平均时间复杂度为 O(n)。
int LocateELem(SqList L,ElemType e){//在顺序表工中查找值为e的数据元素返回其序号for(i0; iL.length; i)if(L.elem[i]e)return il; //查找成功返回序号 i1
return 0; //查找失败返回 0}
3.4、插入 顺序表的插入算法步骤:
顺序表插入算法的平均时间复杂度为 O(n) Status Listinsert(SqList L, int i, ElemType e)
{//在顺序表 L 中第 i 个位置之前插入新的元素 e, i值的合法范围是 1iL.lengthlif ((i l) || (i L.length l)) return ERROR; //i值不合法if (L.length MAXSIZE) return ERROR; //当前存储空间已满for (j L.length - 1; j i - 1; j--)L.elem[j l] L.elem[j]; //插入位置及之后的元素后移L.elem[i - l] e; //将新元素e放入第l个位置L.length; //表长加1return OK;}3.5、删除
顺序表的删除算法步骤 判断删除位置 i 是否合法合法值为 1 ≤ i ≤n), 若不合法则返回 ERROR。 将第 i个至第n个的元素依次向前移动一个位置 (i n时无需移动 表长减 1 顺序表删除算法的平均时间复杂度为O(n)。
Status ListDelete(SqList l int i)
{//在顺序表工中删除第i个元素i.值的合法范闱是1≤i≤L.length
if((i1)|l(iL.length)) //i值不合法return ERROR;
for(ji;j-L.length-l;j)L.elem[j-1]L.elem[j];//被删除元素之后的元素前移
--L.length;//表长减 1
return OK;
}
