当前位置:   article > 正文

数据结构学习笔记3——顺序表_顺序表基本运算思维导图

顺序表基本运算思维导图

数据结构学习笔记3——顺序表

以下笔记为笔者复习使用,仅供参考.

顺序表的逻辑结构

逻辑结构
顺序表的逻辑结构

存储结构:逻辑上相邻的数据元素,在内存中也是一块连续的存储空间。

连续的存储空间

顺序表的实现方式

静态分配

使用静态数组实现,顺序表的大小一旦确定以后无法更改

  • 数据结构
typedef struct  
{//顺序表的静态分配 	
elem_t data[MaxSize];//静态数组 	
int  len;//顺序表长度 
}Sqlist;
  • 1
  • 2
  • 3
  • 4
  • 5
  • 静态分配的顺序表——基本操作

初始化

void InitList(Sqlist *L)
{
	int i;
	for ( i = 0; i < MaxSize; i++)
	{
		L->data[i] = 0;//将顺序表的每一个值赋0
	}
	L->len = 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

插入

bool List_insert(Sqlist* L, int i, int e)
{//在L的位序i插入元素e
	if (isFull(L))
	{
		fprintf(stderr, "Error:The List is Full!\n");
		return false;
	}
	else if (i<1 || i>MaxSize + 1)
	{
		fprintf(stderr, "Error:The extent is illegal!\n");
		return false;
	}
	else
	{
		//采用后移的思想(插入排序的思路)
		for (size_t j = L->len; j >= i; j--)
		{//在i之后的元素后移
			L->data[j] = L->data[j - 1];
		}
		L->data[i - 1] = e;
		L->len++;
		return true;
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

删除

bool List_delete(Sqlist* L, int i, int* e)
{
	if (i<1 || i>L->len)
	{
		return false;
	}
	else
	{
		*e = L->data[i - 1];
		for (size_t j = i; j < L->len; j++)
		{
			L->data[j - 1] = L->data[j];
		}
		L->len--;
		return true;
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

查找

  • 按位查找
int List_find(Sqlist* L, int i)
{//顺序表中第i个元素位置的值——按位查找
	return L->data[i - 1];//动态表相同
}
  • 1
  • 2
  • 3
  • 4
  • 按值查找
int List_find_locate(Sqlist* L, int e)
{//按照值查找
	for (size_t i = 0; i < L->len; i++)
	{
		if (e == L->data[i])
		{
			return i + 1;//返回数组下标
		}
	}
	return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

判断表满

bool isFull(Sqlist* L)
{//判断顺序表是否满
	return L->len >= MaxSize ? true : false;
}
  • 1
  • 2
  • 3
  • 4

动态分配

使用动态数组实现,内存满时可再次申请内存空间

初始化

void InitList(Sqlist* L)
{
	L->data = (elem_t*)malloc(MaxSize * sizeof(int));//申请一片连续的存储空间
	L->len = MaxSize;
	L->Max = MaxSize;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

增加新的存储空间

void AddSize(Sqlist* L, int len)
{
	int* p = L->data;
	L->data = (int*)malloc((L->Max + len) * sizeof(int));//改变指针的位置
	for (size_t i = 0; i < L->len; i++)
	{
		L->data[i] = p[i];//将数据转移到新的存储空间
	}
	L->Max = L->Max + len;
	L->len += len;
	free(p);
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

顺序表思维导图

顺序表

声明:本文内容由网友自发贡献,转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号