前言
线性表的顺序存储是指用一组连续的存储单元依次存储线性表中的各个元素，使得线性表中在逻辑上相邻的数据元素存储在连续的物理存储单元中，即通过数据元素物理存储的连续性来反映数据元素之间逻辑上的相邻关系。
通常我们简称为：顺序表
可以将上面的话归纳为：
- 关系线性化
- 节点顺序存
示意图
SequenceList.png
从图中可以看出，在顺序表中，每个节点ai的存储地址是该节点在表中的逻辑位置i的线性函数，只要知道线性表中第一个元素的存储地址（基地址）和表中每个元素所占储存单元的多少，就可以计算出线性表中任意一个数据元素的存储地址，从而实现对顺序表的随机存取。
地址的计算
假设线性表中有n个元素，每个元素占k个单元，第一个元素的地址为Loc(a1)，则可以通过如下公式计算出第i个元素的地址Loc(ai):
Loc(ai) = Loc(a1) + (i-1)*k
其中，Loc(a1)称为基地址
线性表顺序存储的表示
顺序存储就是类似于C中的一维数组，一维数组的下标与元素在线性表中的序号相对应。举例步骤如下：
1、定义一个节点（使用结构体）
SequenceList.h
#ifndef _SEQUENCELIST_H_
#define _SEQUENCELIST_H_
typedef struct
{
int element[100];
int last;
}Node,*SequenceList;
SequenceList init(SequenceList L); //初始化表
int length(SequenceList L); //得到总长度
int get_int(SequenceList L,int loc); //根据下标得到存储的值
void get_all(SequenceList L); //得到所有存储的值
void add(SequenceList L,int element); //新增
bool del(SequenceList L,int loc); //根据下标删除
bool update(SequenceList L,int loc,int new_element); //更新
bool empty(SequenceList L); //判断是否为空
bool clear(SequenceList L); //清空表
SequenceList destory(SequenceList L); //销毁表
#endif
这里面我们首先定义了一个结构体作为节点，表示每个位置前面图中的a，这里有两个内容，数组是用来表示顺序存储的，last表示当前存储的位置，下面那些是我们需要完成的方法。
2、完成相应的方法
SequenceList.cpp
#include <stdio.h>
#include "SequenceList.h"
#include <malloc.h>
bool checkList(SequenceList L,int loc)
{
if(L == NULL)
{
printf("SequenceList isn't Exists!! \n");
return false;
}
if(loc < 0 || loc >= L->last)
{
printf("loc don't Exists!! \n");
return false;
}
if(L->last == 0)
{
printf("the list is empty!! \n");
return false;
}
return true;
}
bool empty(SequenceList L) //判断是否为空
{
if(L == NULL)
{
printf("SequenceList isn't Exists!! \n");
return false;
}
if(L->last == 0)
{
return true;
}
return false;
}
SequenceList init(SequenceList L) //初始化表
{
if(L != NULL)
{
printf("the List already init!!\n");
return L;
}
L = (SequenceList)malloc(sizeof(Node));
L->last = 0;
printf("init Successed!\n");
return L;
}
int length(SequenceList L) //得到总长度
{
if(L != NULL)
return L->last;
else
{
printf("SequenceList isn't Exists!! \n");
return -1;
}
}
int get_int(SequenceList L,int loc) //根据下标得到存储的值
{
if(!checkList(L,loc))
{
return -1;
}
return L->element[loc];
}
void get_all(SequenceList L)
{
int sum = L->last;
for(int i=0;i<sum;i++)
{
printf("%4d",L->element[i]);
}
printf("\n");
}
void add(SequenceList L,int element) //新增
{
if(L == NULL)
{
printf("SequenceList isn't Exists!! \n");
}
L->element[L->last] = element;
L->last++;
printf("add Successed!!\n");
}
bool del(SequenceList L,int loc) //根据下标删除
{
if(!checkList(L,loc))
{
return false;
}
for(int i=loc;i<L->last;i++)
{
L->element[i] = L->element[i];
}
L->element[L->last-1] = NULL;
L->last--;
printf("del Successed!!\n");
return true;
}
bool update(SequenceList L,int loc,int new_element) //更新
{
if(!checkList(L,loc))
{
return false;
}
L->element[loc] = new_element;
printf("update Successed!!\n");
return true;
}
bool clear(SequenceList L) //清空表
{
int sum = L->last;
for(int i=0;i<sum;i++)
{
L->element[i] = NULL;
L->last--;
}
printf("clear Successed!! \n");
return true;
}
SequenceList destory(SequenceList L) //销毁表
{
clear(L);
L = NULL;
printf("destory Successed!! \n");
return L;
}
3、运行查看结果
SequenceListMain.cpp
#include <stdio.h>
#include "SequenceList.cpp"
int main()
{
SequenceList L = NULL;
L = init(L);
L = init(L);
if(empty(L))
{
printf("List is empty!! \n");
}
for(int i=0;i<5;i++)
{
add(L,3);
}
printf("length is %d \n",length(L));
printf("get_int value is %d \n",get_int(L,3));
del(L,3);
printf("length is %d \n",length(L));
update(L,2,19);
printf("get_int value is %d \n",get_int(L,2));
get_all(L);
clear(L);
printf("length is %d \n",length(L));
L = destory(L);
if(empty(L))
{
printf("List is empty!! \n");
}
}
运行结果：
init Successed!
the List already init!!
List is empty!!
add Successed!!
add Successed!!
add Successed!!
add Successed!!
add Successed!!
length is 5
get_int value is 3
del Successed!!
length is 4
update Successed!!
get_int value is 19
3 3 19 3
clear Successed!!
length is 0
clear Successed!!
destory Successed!!
SequenceList isn't Exists!!
--------------------------------
Process exited with return value 0
Press any key to continue . . .
顺序表的优缺点
- 优点：查找和修改效率高
- 缺点：新增和删除效率低下
这样，线性表的顺序存储就了解完了，我们用自己写的这个来完成各小任务吧
题目1
有两个顺序表LA和LB，其元素均为非递减有序排列，编写算法，将它们合并成一个顺序表LC，要求LC也是非递减有序排列。例如，LA=(2,2,3)，LB=(1,3,3,4)，则LC=(1,2,2,3,3,4)。
算法分析
1、原来的两个都是非递减有序排列，也就是不需要我们排序了。
2、我们将下标从0开始，将LA[0]和LB[0]进行比较，小的先放入LC
，大的与另外的下一位比较，小的放入，依次进行下去。
3、最后将LA或者LB中多的放入LC中即可
实现
void mergeList(LinearList La,LinearList Lb,LinearList Lc) {
int i,j,k;
i=0,j=0,k=0;
while(i<La->last && j<Lb->last){
if(La->elem[i] <= Lb->elem[j]){
Lc->elem[k] = La->elem[i];
i++;k++;
}
else{
Lc->elem[k] = Lb->elem[j];
j++;k++;
}
}
while(i <= La->last){
Lc->elem[k] = La->elem[i];
i++;k++;
}
while(j <= Lb->last){
Lc->elem[k] = Lb->elem[j];
j++;k++;
}
Lc->last = La->last + Lb->last + 1;
}
算法性能分析
时间复杂度为：O(n)，空间复杂度不考虑，题目有前提条件
网友评论