数据结构

第三章 线性表的定义与实现

定义

由同一类型的数据元素构成的有序序列的线性结构。

线性表中元素个数是线性表的长度。

顺序存储

指在内存中用地址连续的一块存储空间顺序存放线性表的各元素

初始化：

List MakeEmpty()
{
	
	List L;
	L=(List)malloc(sizeof(struct LNode));
	L->Last=-1;

	return L;
}

查找

与X在表中的位置有关，也与表长有关。平均查找长度(n+1)/2。

Position Find(List L, ElementType X)
{
	Position i = 0;
	while(i <= L->Last && L->Data[i] != X){
		i ++;
	}
	if(i > L->Last) return ERROR;
	else return i;
}

插入

将数据插入到第i个位置上(1<=i<=n+1)

1. 检查是不是满了
2. 插入位序的合法性
3. 数据移动的次序和方向：平均移动次数n/2

/*插入的位置i是1<=i<=n+1*/
bool Insert(List L, ElementType X, int i){
	Position j;

	if(L->Last == MAXSIZE-1){

		printf("装满");
		return false;
	}

	if(i<1 || i > L->Last+2){

		printf("位置不合法");
		return false;
	}

	for(j = L->Last; j >= i-1; j--){
		L->Data[j+1] = L->Data[j];
	}

	L->Data[i-1]=X;
	L->Last++;

	return true;
}

删除

平均移动次数(n-1)/2

bool Delete(List L, int i){ 
	Position j;

	if(i < 1 || i > L->Last+1){
		printf("位序%d不存在元素",i);
		return false;
	}

	for(j = i; j <= L->Last; j ++){
		L->Data[j-1] = L->Data[j];
	}
	L->Last--;

	return true;
}

链式存储

顺序表的存储特点是物理上的相邻实现了逻辑上的相邻。

求表长

需要将线性表从头到尾遍历一遍

查找

插入

bool Insert(List L, ELementType X, int i){
	Position tmp, pre;
	int cnt=0;

	pre = L;
	while(pre && cnt < i-1){
		pre = pre->Next;
		cnt ++;
	}
	if(pre==NULL || cnt != i-1){
		printf("插入位置参数错误！");
		return false;
	}
	else{
		tmp=(Position)malloc(sizeof(struct LNode));
		tmp->Data=X;
		tmp->Next=pre->Next;
		pre->Next=tmp;
		return true;
	}
}

删除

bool Delete(List L, int i){
	Position tmp, pre;
	int cnt = 0;

	pre = L;
	while(pre && cnt < i-1){
		pre=pre->Next;
		cnt++;
	}
	if(pre==NULL || cnt != i-1 || pre->Next==NULL){
		printf("删除位置参数错误");
		return false;
	}
	else{
		tmp=pre->Next;
		pre->Next=tmp->Next;
		free(tmp);
		return true;
	}
}

广义表与多重链表

赏

谢谢你请我吃糖果

支付宝

微信

• 本文作者： Doted Wood
• 本文链接： http://example.com/2022/01/12/数据结构/数据结构线性表/
• 版权声明： 版权归博主所有，转载请说明来源