宜宾网站建设公司

算法与数据结构学习系列（二）：顺序表-创新互联

目录
  • 一.顺序表简介
  • 二.问题难点
    • 1.基本结构
    • 2.插入
    • 3.删除
    • 4.其它需注意的事项
  • 三.代码实现
    • 总代码
      • 1.头文件
      • 2.初始化函数
      • 3.头插函数
      • 4.尾插函数
      • 5.按位置插函数
      • 6.头删函数
      • 7.尾删函数
      • 8.按位置删函数
      • 9.按值删函数
      • 10.查找函数
      • 11.判满函数
      • 12.判空函数
      • 13.扩容函数
      • 14.清空函数
      • 15.销毁函数
      • 16.打印函数
    • 主程序测试

创新互联是一家专注于成都做网站、成都网站设计、成都外贸网站建设与策划设计,驿城网站建设哪家好?创新互联做网站,专注于网站建设10余年,网设计领域的专业建站公司;建站业务涵盖:驿城等地区。驿城做网站价格咨询:13518219792一.顺序表简介
  • 顺序表：简而言之，可以看作一个数组，把数据存储在一段连续的空间中，逻辑地址是连续的，物理地址也是连续的。可以通过下标方式直接访问到任意一个元素，适用于尾部操作（尾插或尾删），因为时间复杂度为O(1)，若在其余地方插入或删除，则需要挪动一次挪动元素，时间复杂度提升至O(n)。
二.问题难点 1.基本结构

在这里插入图片描述

2.插入
  • 插入就是先将所有元素向后挪动一个格子，再将值插到该插的地方
3.删除
  • 删除就是将待删除元素的后面元素向前覆盖
4.其它需注意的事项
  • 每次需判断函数传过来的指针是否为空，否则对NULL解引用会出错
  • 插入需判满，删除需判空
  • 尾删的时候，只需长度-1即可，判断该位置是否有元素，取决于length
三.代码实现 总代码
#include#include
#include#include#define LIST_INIT_SIZE 100

typedef int ELEM_TYPE;

typedef struct Sqlist
{ELEM_TYPE* elem;
	int length;
	int listsize;
}Sqlist, * PSqlist;

//初始化
void Init_Sqlist(PSqlist sq);

//头插
bool Insert_head(PSqlist sq, ELEM_TYPE val);

//尾插 
bool Insert_tail(PSqlist sq, ELEM_TYPE val);

//按位置插
bool Insert_pos(PSqlist sq, int pos, ELEM_TYPE val);

//头删
bool Del_head(PSqlist sq);

//尾删
bool Del_tail(PSqlist sq);

//按位置删
bool Del_pos(PSqlist sq, int pos);

//按值删
bool Del_val(PSqlist sq, ELEM_TYPE val);

//查找
int Search(PSqlist sq, ELEM_TYPE val);

//判满
bool IsFull(PSqlist sq);

//判空
bool IsEmpty(PSqlist sq);

//扩容
void Inc(PSqlist sq);

//清空
bool Clear(PSqlist sq);

//销毁
bool Destory(PSqlist sq);

//打印
void Show(PSqlist sq);

//初始化
void Init_Sqlist(PSqlist sq)
{assert(sq != NULL);
	sq->elem = (ELEM_TYPE*)malloc(sizeof(ELEM_TYPE) * LIST_INIT_SIZE);
	assert(sq->elem != NULL);
	memset(sq->elem, 0, sizeof(ELEM_TYPE) * LIST_INIT_SIZE);
	sq->length = 0;
	sq->listsize = LIST_INIT_SIZE;
}

//头插
bool Insert_head(PSqlist sq, ELEM_TYPE val)//不论头插尾插，插都要判满
{assert(sq != NULL);
	if (IsFull(sq))
	{Inc(sq);
	}
	for (int i = sq->length - 1; i >= 0; i--)  //头也要挪 别想当然
	{sq->elem[i + 1] = sq->elem[i];
	}
	sq->elem[0] = val;
	sq->length++;
	return true;
}

//尾插 
bool Insert_tail(PSqlist sq, ELEM_TYPE val)
{assert(sq != NULL);
	if (IsFull(sq))
	{Inc(sq);
	}
	sq->elem[sq->length++] = val;
	return true;
}

//按位置插
bool Insert_pos(PSqlist sq, int pos,ELEM_TYPE val)
{assert(sq != NULL);
	assert(0<= pos && pos< sq->length); //判断pos合法性
	if (IsFull(sq))
	{Inc(sq);
	}
	for (int i = sq->length - 1; i >= pos; i--)
	{sq->elem[i + 1] = sq->elem[i];
	}
	sq->elem[pos] = val;
	sq->length++;
	return true;
}

//头删
bool Del_head(PSqlist sq)//删要判空
{assert(sq != NULL);
	if (IsEmpty(sq))
	{return false;
	}
	for (int i = 1; i< sq->length; i++)//注意是< 而不是<=，length不用往前走，要走的是length-1，它才是最后一个
	{ 
		sq->elem[i - 1] = sq->elem[i];    //注意虽然只有一个元素时，没有覆盖，但length--了，其实有没有都无所谓，
	}                                     //决定是否存在取决于length的大小
	sq->length--;
	return true;
}

//尾删
bool Del_tail(PSqlist sq)
{assert(sq != NULL);
	if (IsEmpty(sq))
	{return false;
	}
	sq->length--;   //取决于是否存在，在于length的大小，存在与否不是看你有没有值，况且本来就有值，也不是看值为0
	return true;    //那有些数据本身就是0，所以存在与否取决于length
}

//按位置删
bool Del_pos(PSqlist sq, int pos)
{assert(sq != NULL);
	assert(pos >= 0 && pos< sq->length);
	if (IsEmpty(sq))
	{return false;
	}
	for (int i = pos + 1; i< sq->length; i++)
	{sq->elem[i - 1] = sq->elem[i];
	}
	sq->length--;
	return true;
}

//按值删
bool Del_val(PSqlist sq, ELEM_TYPE val)
{assert(sq != NULL);
	int pos = Search(sq, val);
	if (pos == -1)
	{return false;
	}
	return Del_pos(sq, pos);
}

//查找
int Search(PSqlist sq, ELEM_TYPE val)
{assert(sq != NULL);
	for (int i = 0; i< sq->length; i++)
	{if (sq->elem[i] == val)
		{	return i;
		}
	}
	return -1;
}

//判满
bool IsFull(PSqlist sq)
{assert(sq != NULL);
	return sq->length == sq->listsize;
}

//判空
bool IsEmpty(PSqlist sq)
{assert(sq != NULL);
	return sq->length == 0;
}

//扩容 按2倍扩容
void Inc(PSqlist sq)
{assert(sq != NULL);
	ELEM_TYPE* new_elem = (ELEM_TYPE*)realloc(sq->elem,sizeof(ELEM_TYPE) * sq->listsize * 2);
	assert(new_elem != NULL);
	sq->elem = new_elem;
	sq->listsize *= 2;
}

//清空
bool Clear(PSqlist sq)
{assert(sq != NULL);
	sq->length = 0;
	return true;
}

//销毁
bool Destory(PSqlist sq)
{assert(sq != NULL);
	free(sq->elem);
	sq->elem = NULL;     //避免使用达不到效果，改变其它程序占有此内存的数据
	sq->length = sq->listsize = 0;
	return true;
}

//打印
void Show(PSqlist sq)
{assert(sq != NULL);
	for (int i = 0; i< sq->length; i++)
	{printf("%d ", sq->elem[i]);
	}
	printf("\n");
}

int main()
{Sqlist sq;
	Init_Sqlist(&sq);
	for (int i = 0; i< 10; i++)
	{Insert_tail(&sq, i + 1);
	}
	Show(&sq);// 1 2 3 4 5 6 7 8 9 10
	Insert_head(&sq, 100);
	Insert_pos(&sq, 0, 200);
	Show(&sq);//200 100 1 2 3 4 5 6 7 8 9 10
	Del_head(&sq);
	Del_tail(&sq);
	Del_pos(&sq, 0);
	Del_val(&sq, 4);
	Show(&sq);//1 2 3 5 6 7 8 9
	return 0;
}
1.头文件

我们是通过malloc函数动态开辟内存空间给到elem，然后可以通过下标访问到每一个空间。因为是动态开辟的，所以数组的长度等信息都是不断发生改变的，所以我们设计了这样的结构体，把数组的属性实时赋值给相应变量

#define LIST_INIT_SIZE 100     

typedef int ELEM_TYPE;

typedef struct Sqlist
{ELEM_TYPE* elem;
	int length；      //当前有效长度
	int listsize;     //总空间大小
}Sqlist,*PSqlist;
2.初始化函数

初始化就是开辟空间、赋初值

//初始化
void Init_Sqlist(PSqlist sq)
{assert(sq != NULL);
	sq->elem = (ELEM_TYPE*)malloc(sizeof(ELEM_TYPE) * LIST_INIT_SIZE);
	assert(sq->elem != NULL);
	memset(sq->elem, 0, sizeof(ELEM_TYPE) * LIST_INIT_SIZE);
	sq->length = 0;
	sq->listsize = LIST_INIT_SIZE;
}
3.头插函数
//头插
bool Insert_head(PSqlist sq, ELEM_TYPE val)//不论头插尾插，插都要判满
{assert(sq != NULL);
	if (IsFull(sq))
	{Inc(sq);
	}
	for (int i = sq->length - 1; i >= 0; i--)  //头也要挪 别想当然
	{sq->elem[i + 1] = sq->elem[i];
	}
	sq->elem[0] = val;
	sq->length++;
	return true;
}
4.尾插函数
//尾插 
bool Insert_tail(PSqlist sq, ELEM_TYPE val)
{assert(sq != NULL);
	if (IsFull(sq))
	{Inc(sq);
	}
	sq->elem[sq->length++] = val;
	return true;
}
5.按位置插函数
//按位置插
bool Insert_pos(PSqlist sq, int pos,ELEM_TYPE val)
{assert(sq != NULL);
	assert(0<= pos && pos< sq->length); //判断pos合法性
	if (IsFull(sq))
	{Inc(sq);
	}
	for (int i = sq->length - 1; i >= pos; i--)
	{sq->elem[i + 1] = sq->elem[i];
	}
	sq->elem[pos] = val;
	sq->length++;
	return true;
}
6.头删函数
//头删
bool Del_head(PSqlist sq)//删要判空
{assert(sq != NULL);
	if (IsEmpty(sq))
	{return false;
	}
	for (int i = 1; i< sq->length; i++)//注意是< 而不是<=，length不用往前走，要走的是length-1，它才是最后一个
	{ 
		sq->elem[i - 1] = sq->elem[i];    //注意虽然只有一个元素时，没有覆盖，但length--了，其实有没有都无所谓，
	}                                     //决定是否存在取决于length的大小
	sq->length--;
	return true;
}
7.尾删函数
//尾删
bool Del_tail(PSqlist sq)
{assert(sq != NULL);
	if (IsEmpty(sq))
	{return false;
	}
	sq->length--;   //取决于是否存在，在于length的大小，存在与否不是看你有没有值，况且本来就有值，也不是看值为0
	return true;    //那有些数据本身就是0，所以存在与否取决于length
}
8.按位置删函数
//按位置删
bool Del_pos(PSqlist sq, int pos)
{assert(sq != NULL);
	assert(pos >= 0 && pos< sq->length);
	if (IsEmpty(sq))
	{return false;
	}
	for (int i = pos + 1; i< sq->length; i++)
	{sq->elem[i - 1] = sq->elem[i];
	}
	sq->length--;
	return true;
}
9.按值删函数
//按值删
bool Del_val(PSqlist sq, ELEM_TYPE val)
{assert(sq != NULL);
	int pos = Search(sq, val);
	if (pos == -1)
	{return false;
	}
	return Del_pos(sq, pos);
}
10.查找函数
//查找
int Search(PSqlist sq, ELEM_TYPE val)
{assert(sq != NULL);
	for (int i = 0; i< sq->length; i++)
	{if (sq->elem[i] == val)
		{	return i;
		}
	}
	return -1;
}
11.判满函数
//判满
bool IsFull(PSqlist sq)
{assert(sq != NULL);
	return sq->length == sq->listsize;
}
12.判空函数
//判空
bool IsEmpty(PSqlist sq)
{assert(sq != NULL);
	return sq->length == 0;
}
13.扩容函数
//扩容 按2倍扩容
void Inc(PSqlist sq)
{assert(sq != NULL);
	ELEM_TYPE* new_elem = (ELEM_TYPE*)realloc(sq->elem,sizeof(ELEM_TYPE) * sq->listsize * 2);
	assert(new_elem != NULL);
	sq->elem = new_elem;
	sq->listsize *= 2;
}
14.清空函数
//清空
bool Clear(PSqlist sq)
{assert(sq != NULL);
	sq->length = 0;//长度为0，意味着没有元素了，如果要赋值为0，也没有必要，因为有些元素的值就是0，所以不能当成判别标准
	return true;
}
15.销毁函数
//销毁
bool Destory(PSqlist sq)
{assert(sq != NULL);
	free(sq->elem);
	sq->elem = NULL;     //避免使用达不到效果，改变其它程序占有此内存的数据
	sq->length = sq->listsize = 0;
	return true;
}
16.打印函数
//打印
void Show(PSqlist sq)
{assert(sq != NULL);
	for (int i = 0; i< sq->length; i++)
	{printf("%d ", sq->elem[i]);
	}
	printf("\n");
}
主程序测试
int main()
{Sqlist sq;
	Init_Sqlist(&sq);
	for (int i = 0; i< 10; i++)
	{Insert_tail(&sq, i + 1);
	}
	Show(&sq);// 1 2 3 4 5 6 7 8 9 10
	Insert_head(&sq, 100);
	Insert_pos(&sq, 0, 200);
	Show(&sq);//200 100 1 2 3 4 5 6 7 8 9 10
	Del_head(&sq);
	Del_tail(&sq);
	Del_pos(&sq, 0);
	Del_val(&sq, 4);
	Show(&sq);//1 2 3 5 6 7 8 9
	return 0;
}

测试结果
在这里插入图片描述

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


网站栏目：算法与数据结构学习系列（二）：顺序表-创新互联
网页URL：http://ybzwz.com/article/dhjcgi.html

其他资讯