数据结构——顺序表-创新互联

数据结构——顺序表
  • 顺序表类型定义
  • 数组定义
  • C++的动态存储分配
  • C++中的参数传递
  • 操作算法中补充内容
  • 顺序表基本操作
    • 算法1 线性表L的初始化
    • 算法2 顺序表的取值
    • 算法3 顺序表的查找
    • 算法4 顺序表的插入(时间复杂度为O(n))
    • 算法5 顺序表的删除(时间复杂度为O(n))
  • 顺序存储分析

成都创新互联公司致力于互联网网站建设与网站营销,提供成都网站建设、网站制作、网站开发、seo优化、网站排名、互联网营销、小程序开发、公众号商城、等建站开发,成都创新互联公司网站建设策划专家,为不同类型的客户提供良好的互联网应用定制解决方案,帮助客户在新的全球化互联网环境中保持优势。顺序表类型定义
typedef char ElemType; //定义为char

typedef struct{ElemType data[];
	int length;
}SqList;	// 顺序表类型
数组定义
// 数组静态分配
typedef struct{ElemType data[MaxSize];
	int length;
}SqList;	//顺序表类型


// 数组动态分配
typedef struct{ElemType *data;
	int length;
}SqList;	//顺序表类型

SqList L;
L.data = (ElemType*)malloc(sizeof(ElemType)*MaxSize);

内存分配函数(需要加载头文件

  1. malloc(m)函数,开辟m字节长度的地址空间,并返回这段空间的首地址。
  2. sizeof(x)运算,计算变量x的长度。
  3. free(p),释放指针p所指变量的存储空间,即彻底删除一个变量。
C++的动态存储分配
new 类型名T (初值列表)
// 功能:申请用于存放T类型对象的内存空间,并依初值列表赋初值
// 结果值:
//   成功:T类型的指针,指向新分配的内存
//   失败:0 (NULL)

delete 指针P
// 功能:释放指针p所指向的内存,p必须是new操作的返回值。
C++中的参数传递
  1. 函数调用时传送给形参表的实参必须与形参的类型、个数、顺序一致。
  2. 参数传递的两种方式:传值&传地址。
操作算法中补充内容
// 函数结果状态代码
# define OK		1
# define ERROR	0
# define INFEASIBLE	-1
# define OVERFLOW 	-2

// Status是函数的类型,其值是函数结果状态代码
typedef int Status;
typedef char ElemType;

// 销毁线性表L
void DestroyList(SqList &L){if(L.elem) delete L.elem;
}
// 清空线性表L
void ClearList(SqList &L){L.length = 0;
}
// 求线性表的长度
int GetLength(SqList L){return(L.length);
}
// 判断线性表L是否为空
int IsEmpty(SqList L){if(L.length==0) return 1;
	else return 0;
}
顺序表基本操作 算法1 线性表L的初始化
Status IniList Sq(sqList &L){L.elem = new ElemType[MAXSIZE];		// 分配空间
	if(!L.elem) exit(OVERFLOW);			// 分配失败
	L.length = 0;						// 空表长度为0
	return OK;
算法2 顺序表的取值
int GetElem(SqList L, int i, ElemType &e){if(i<1||i>L.length) return ERROR;	// 判断是否合理
	e = L.elem[i-1];	// i-1的单元存储着第i个数据
	return OK;
算法3 顺序表的查找

平均查找长度ASL(Average Search Length):为确定记录在表中的位置,需要与给定值进行比较的关键字的个数的期望值。对含有n个记录的表,查找成功时:
A S L = ∑ i = 1 n P i C i ASL = \sum_{i=1}^{n}P_iC_i ASL=i=1∑n​Pi​Ci​

// 在L中查找与指定值e相同的数据元素的位置
int LocateElem(SqList L, ElemType e){for(i=0; i
算法4 顺序表的插入(时间复杂度为O(n))
Status ListInsert_Sq(SqList &L, int i, ElemType e){if(i<1||i>L.length+1) return ERROR;		// i值不合法
	if(L.length == MAXSIZE) return ERROR;	// 存储空间已满
	for(j=L.length-1; j>=i-1; j--)
		L.elem[j+1] = L.elem[j];			// 插入位置及之后的元素后移
	L.elem[i-1] = e;
	L.length++;
	return OK;
算法5 顺序表的删除(时间复杂度为O(n))
Status ListDelete_Sq(SqList &L, int i){if(i<1||i>L.length) return ERROR;		// i值不合法
	if(L.length == MAXSIZE) return ERROR;	// 存储空间已满
	for(j=i; j>=L.length-1; j++)
		L.elem[j-1] = L.elem[j];			// 插入位置及之后的元素后移
	L.length--;
	return OK;
顺序存储分析
  1. 查找、插入、删除算法的平均时间复杂度:O(n)
  2. 查找、插入、删除算法的空间复杂度:O(1),没有用辅助空间
  3. 优点:存储密度大(结点本身所占存储量/结点结构所占存储量);随机存取。
  4. 缺点:插入、删除元素时需要移动大量数据;浪费存储空间;静态存储不能自由扩充数据元素的个数。

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


当前标题:数据结构——顺序表-创新互联
分享路径:http://scyanting.com/article/djsish.html