网站开发提供源代码,dedecms做网站教程,朝阳网站制作设计,北京建设工程交易中心网线性表
线性表是包含若干数据元素的一个线性序列 记为#xff1a; L(a0, ...... ai-1, ai, ai1 ...... an-1)
L为表名#xff0c;ai (0≤i≤n-1)为数据元素#xff1b;
n为表长,n0 时#xff0c;线性表L为非空表#xff0c;否则为空表。 线性表L可用二元组形式描述…线性表
线性表是包含若干数据元素的一个线性序列 记为 L(a0, ...... ai-1, ai, ai1 ...... an-1)
L为表名ai (0≤i≤n-1)为数据元素
n为表长,n0 时线性表L为非空表否则为空表。 线性表L可用二元组形式描述任何一种数据结构都能表示为二元组 L (D,R)
data、relation
即线性表L包含数据元素集合D和关系集合R D{ai | ai∈datatype ,i0,1,2, ∙∙∙∙∙∙∙∙∙n-1 ,n≥0} R{ai , ai1 | ai , ai1∈D, 0≤i≤n-2}
关系符ai, ai1在这里称为有序对
表示任意相邻的两个元素之间的一种先后次序关系
ai是ai1的直接前驱, ai1是ai的直接后继 设有一个顺序表L{1,2,3,4,5,6}; 他们的关系如图: 使用二元组描述L(D,R),则
D{1 , 2 , 3 , 4 , 5 , 6}(n6)
R{1,2 , 2,3 , 3,4 , 4,5 , 5,6} 线性表的特征
1) 对非空表,a0是表头,无前驱
2) an-1是表尾,无后继
3) 其它的每个元素ai有且仅有一个直接前驱ai-1和一个直接后继ai1。 顺序存储结构的表示
若将线性表L(a0,a1, ……,an-1)中的各元素依次存储于计算机一片连续的存储空间。
设Loc(ai)为ai的地址Loc(a0)b每个元素占d个单元 则Loc(ai)bi*d 顺序存储结构的特点
逻辑上相邻的元素 ai, ai1其存储位置也是相邻的
对数据元素ai的存取为随机存取或按地址存取
存储密度高 存储密度D(数据结构中元素所占存储空间)/整个数据结构所占空间 顺序存储结构的不足 对表的插入和删除等运算的时间复杂度较差。
所以对于查找较多、插入删除较少的实际问题可以用顺序存储。
对于顺序存储编程一般需要至少两个结构体一个存数据元素的各种信息一个存数据元素的集合。 一般至少要有sqlist.h定义运算、sqlist.c运算的实现、test.c主函数。这种程序结构就叫架构写程序前先想好架构。 在C语言中可借助于一维数组类型来描述线性表的顺序存储结构
#define N 100
typedef int data_t;
typedef struct
{ data_t data[N] //表的存储空间 int last;
} sqlist, *sqlink; 线性表的基本运算
设线性表 L(a0,a1, ……,an-1)对 L的基本运算有
1)建立一个空表list_create(L)
2)置空表list_clear(L)
3)判断表是否为空list_empty (L)。若表为空返回值为1 , 否则返回 0
4)求表长length (L)
5)取表中某个元素GetList(L , i ), 即ai。要求0≤i≤length(L)-1
6)定位运算Locate(L,x)。确定元素x在表L中的位置或序号 Locate(L,x) i 当元素xai∈L,且ai是第一个与x相等时 -1 x不属于L时。 基本运算的相关算法
定位确定给定元素x在表L中第一次出现的位置或序号。即实现Locate(L,x)。算法对应的存储结构如图所示。 7)插入
Insert(L,x,i)。将元素x插入到表L中第i个元素ai之前,且表长1。
插入前: (a0,a1,---,ai-1,ai,ai1-------,an-1) 0≤i≤n,in时,x插入表尾
插入后: (a0,a1,---,ai-1, x, ai,ai1-------,an-1) 基本运算的相关算法
算法思路若表存在空闲空间且参数i满足0≤i≤L-last1,则可进行正常插入。插入前将表中L-data[L-last]L-data[i]部分顺序下移一个位置然后将x插入L-data[i]处即可。算法对应的表结构。 8)删除
Delete(L,i)。删除表L中第i个元素ai且表长减1, 要求0≤i≤n-1。 删除前: (a0,a1,---,ai-1,ai,ai1-------,an-1) 删除后: (a0,a1,---,ai-1ai1-------,an) 删除将表中第i个元素ai从表中删除即实现DeleteSqlist(L, i)。 算法思路 若参数i满足0≤i≤L-last, 将表中L-data[i1]∽L-data[L-last] 部分顺序向上移动一个位置覆盖L-data[i]。 线性表的基本运算
设线性表La(a0a1, ……,am-1), Lb (b0b1, ……,bn-1)求La∪Lb La 算法思路依次取表Lb中的bi(i0,1,……,n-1)若bi不属于La,则将其插入表La中。 线性表
设计清除线性表L(a0,a1,---,ai,-------,an-1)中重复元素的算法。
算法思路对当前表L中的每个ai0≤i≤n-2依次与aj(i1≤j≤n-1)
比较若与ai相等则删除之。 线性表的顺序存储缺点 线性表的顺序存储结构有存储密度高及能够随机存取等优点但存在以下不足
(1)要求系统提供一片较大的连续存储空间。
(2)插入、删除等运算耗时且存在元素在存储器中成片移动的现象 vi编辑器底行模式下vsp 文件名可以让打开的文件和这个文件分屏显示。
