C语言顺序表的基本结构与实现思路详解

目录
  • 一、顺序表的概念与结构
    • 1.线性表的解释
    • 2.顺序表概念解释
  • 二、顺序表的思路及代码实现详解
    • 1.静态顺序表的实现
    • 2.动态顺序表思路及代码实现
      • 2.1 动态顺序表的整体思路
      • 2.2 定义结构体的实现
      • 2.3 初始化结构体
      • 2.4 结构体打印
      • 2.5 检查数组容量
      • 2.6 头插
      • 2.7 尾插
      • 2.8 头删
      • 2.9 尾删
      • 2.10 任意删除
      • 2.11 任意插入
      • 2.12 空间释放
  • 三、顺序表代码整合
    • SeqList.h
    • SeqList.c
    • test.c

一、顺序表的概念与结构

1.线性表的解释

首先我们在这里引入线性表的概念。线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构。

常见的线性表:顺序表、链表、栈、队列、字符串……

线性表在逻辑上是线性结构,也就是说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数据和链式结构的形式存储。

顺序表就是线性表的一种,我们在这里详细解释一下顺序表的实现,后续我们会更新链表等内容。

2.顺序表概念解释

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成增删查改。

而顺序表一般可分为:

  • 静态顺序表:使用定长数组存储。
  • 动态顺序表:使用动态开辟的数组存储。

二、顺序表的思路及代码实现详解

1.静态顺序表的实现

我们先想出来一个静态表整体的模板思路:

  • 定义一个结构体,该结构体包含一个可以存放数据的数组和记录数组中有效数字的变量。
  • 初始化结构体。
  • 打印结构体。
  • 头插。
  • 尾插。
  • 头删。
  • 尾删。
  • 任意位置插入。
  • 任意位置删除。

这里需要有一点注意的是,我们在定义结构体中的数组时,我们可以用typedef进行变量名简化,这也方便我们后期更改存储类型的时候直接更改typedef处就行。同时我们会想到数组的大小需要define定义一个宏,这样大大提高了代码后期的可维护性。

但是我们仔细想一下,假如我们存储的数据满了,我们想要继续存储的话还要找到源码进行更改大小。每次存储满了,都要更改。那是不是太麻烦了,且效率很低。这时候我们就联想到了动态的顺序表,可以自动开辟空间,从而大大提高效率。

这里我就给出大家静态顺序表定义及接口的代码,不再详细解释接口的实现了。我们这里详细解释一下动态顺序表的解释。静态顺序表接口的实现与动态顺序表接口实现大同小异,可参考动态顺序表接口的详解。

代码如下:

#define MAX_SIZE 10
typedef int SQDataType;
typedef struct SeqList
{
	SQDataType a[MAX_SIZE];
	int size;
}SL;
//typedef struct SeqList SL;
typedef struct SeqList SL;
//初始化结构体
void SeqListInit(SL* ps);
//打印
void SeqListPrint(SL s);
//尾插
void SeqListPushBack(SL* ps, SQDataType x);
//尾删
void SeqListPopBack(SL* ps);
//头插
void SeqListPushFrint(SL* ps, SQDataType x);
//头删
void SeqListPopFrint(SL* ps);
//查找位置
int SeqListFind(SL s, SQDataType x);
//任意插入
void SeqListInsert(SL* ps, int pos, SQDataType x);
//任意删
void SeqListErase(SL* ps, int pos);

2.动态顺序表思路及代码实现

2.1 动态顺序表的整体思路

动态顺序表的思路与静态大致相同,但也有所不同,我来给大家详细解释一下。我们先看动态顺序表的整体思路模板:

  • 定义一个结构体,该结构体包含一个可以存放数据的动态数组和记录数组中有效数据的变量,两外还需要一个变量记录当前数组的大小。
  • 初始化结构体。
  • 打印结构体。
  • 检查数组容量
  • 头插。
  • 尾插。
  • 头删。
  • 尾删。
  • 任意位置插入。
  • 任意位置删除。
  • 释放动态数组空间

我们上面提到了动态的数组,需要用malloc或realloc动态开辟空间。由于是动态开辟的,我们这里多了一项释放动态开辟的空间。注意,记录数组的有效数据和数组大小并不相同。有效数据是已经存储的数据个数,而数组大小是指最能够存储数组的个数。我们为什么要记录数组的大小呢?这里是用来判断是否存储满了,满了话要开辟空间。

我们来详细看一下每个接口的实现。

2.2 定义结构体的实现

在定义结构体时,我们可以用typedef进行数组类型简化,同时方便我们后期更改存储类型的时候直接更改typedef处即可。同时我们也用typedef进行结构体类型简化,方便我们以后编辑代码。我们来看一下代码的实现:

typedef int SQDataType;
struct SeqList
{
	SQDataType* a;
	int size;
	int capacity;
};
typedef struct SeqList SL;

通过上面的代码我们可以发现,当我们不想存储int型数据时,我们只需把‘typedef int SQDataType’改为‘typedef doubleSQDataType’即可。极大的提高了代码的维护性。

2.3 初始化结构体

我们初始化结构体时,可以先将数组置空,我们后期插入数据时可再开辟空间。同时当然有效数据和数组大小都要初始化成零。我们看代码的实现。

void SeqListInit(SL* ps)
{
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

我们这里是改变了结构体的内容,所以需要传地址,用指针变量来接收。

2.4 结构体打印

结构体打印方便我们观察对动态数组的操作。打印的时数组的有效数据的内容。我们来看代码的实现。

void SeqListPrint(SL s)
{
	int i = 0;
	for (i = 0; i < s.size; i++)
	{
		printf("%d ", s.a[i]);
	}
	printf("\n");
}

2.5 检查数组容量

我们仔细想一想,是不是在插入每个数据之前都要检查数组是否已经满了。如果满了,则需要增容。如果没有满,就插入数据即可。在这里我们需要实现头插、尾插、任意插入三个接口,所以我们就把检查数组容量单独分装一个函数,这样提高代码的简洁性。我们看一下代码的实现。

void SQLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SQDataType* tmp =(SQDataType*)realloc(ps->a, sizeof(SQDataType) * newcapacity);
		if (tmp == NULL)
		{
			printf("realloc failed\n");
			exit(-1);
		}
		ps->capacity = newcapacity;
		ps->a = tmp;
	}
}

当我们检查增容时,我们还要判断一下之前的数组大小是否为零,如果是零的话,我们要给其赋一个值。因为我们刚开始初始化数组的时候把数组指针置空了。在动态顺序表中我们增容一般会扩大到原来的2倍。

2.6 头插

在插入之前要判断数组是否已经满了。头插的思想就是把数组的内容整体后移一位,我们把要插入的数据放在第一位。我们结合着代码一起理解。

void SeqListPushFrint(SL* ps, SQDataType x)
{
	SQLCheckCapacity(ps);
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->a[end+1] = ps->a[end];
		end--;
	}
	ps->a[0] = x;
	ps->size++;
}

2.7 尾插

同样, 在插入之前要判断数组是否已经满了。尾插的思想很简单。就是直接在数组尾部插入一个数据即可。我们看一下代码的实现。

void SeqListPushBack(SL* ps, SQDataType x)
{
	SQLCheckCapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;
}

2.8 头删

删除时我们也有要注意的一点,就是检查数组中是否有元素给我们删除。头删的思想就是除去数组的第一个元素,我们将后面的元素整体向前移动一位,将第一位给覆盖了。我们来看代码。

void SeqListPopFrint(SL* ps)
{
	assert(ps->size > 0);
	int i = 0;
	for (i = 0; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}

2.9 尾删

同样,在尾删之前,我们要检查数组中是否有元素给我们删除。尾删的思想十分简单,就是把数组的有效数据减一即可。我们看一下代码的实现。

void SeqListPopBack(SL* ps)
{
	assert(ps->size > 0);
	ps->size--;
}

2.10 任意删除

在任意删除时,我们首先要判断删除的位置是否合理,不能违背顺序表的规则。同样,在尾删之前,我们要检查数组中是否有元素给我们删除。任意删除就是我们指出删除位置的下标进行删除。当然,我们想要删除数组中指定元素时,我们可以先查出元素下标在进行删除。这个相对来说较复杂一点,我们结合着代码理解一下。

//查找位置
int SeqListFind(SL s, SQDataType x)
{
	int i = 0;
	for (i = 0; i < s.size; i++)
	{
		if (s.a[i] == x)
		{
			return i;
		}
	}
	return -1;
}
void SeqListErase(SL* ps, int pos)
{
	assert(pos >= 0 && pos < ps->size);
	int begin = pos + 1;
	while (begin < ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		begin++;
	}
	ps->size--;
}

2.11 任意插入

在任意插入时时,我们也要判断插入的位置是否合理,不能违背顺序表的规则。插入时,我们不能忘记检查数组是否满了。任意插入的思想与任意删除的思想基本相同。任意插入的思想就是在我们指出删除位置的下标进行插入。我们看一下代码实现。

void SeqListInsert(SL* ps, int pos, SQDataType x)
{
	assert(pos >= 0 && pos <= ps->size);
	SQLCheckCapacity(ps);
	int end = ps->size-1;
	while (end >= pos)
	{
		ps->a[end+1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
}

2.12 空间释放

由于我们的数组是动态开辟的,所以当我们不用时,我们要及时释放掉动态开辟的空间,避免内存泄漏。同时我们要把数组指针再次置空,避免产生野指针。我们看代码实现。

void SeqListDestory(SL* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

三、顺序表代码整合

由于代码量相对来说有一点多,所以我们就将函数的声明的定义分开,这样有利于提高代码的可读性,同时会保持一个良好的思路,且方便编写代码。

我们将函数的声明放在单独的一个SeqList.h的头文件,函数的实现放在一个单独的SeqList.c源文件,函数的主方法及调用放在另一个单独的test.c源文件。

SeqList.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SQDataType;
struct SeqList
{
	SQDataType* a;
	int size;
	int capacity;
};
typedef struct SeqList SL;
//初始化结构体
void SeqListInit(SL* ps);
//打印
void SeqListPrint(SL s);
//尾插
void SeqListPushBack(SL* ps, SQDataType x);
//尾删
void SeqListPopBack(SL* ps);
//头插
void SeqListPushFrint(SL* ps, SQDataType x);
//头删
void SeqListPopFrint(SL* ps);
//查找位置
int SeqListFind(SL s, SQDataType x);
//任意插入
void SeqListInsert(SL* ps, int pos, SQDataType x);
//任意删
void SeqListErase(SL* ps, int pos);
//销毁空间
void SeqListDestory(SL* ps);

SeqList.c

#include"SeqList.h"
//初始化结构体
void SeqListInit(SL* ps)
{
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}
//打印
void SeqListPrint(SL s)
{
	int i = 0;
	for (i = 0; i < s.size; i++)
	{
		printf("%d ", s.a[i]);
	}
	printf("\n");
}
//查容增容
void SQLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SQDataType* tmp =(SQDataType*)realloc(ps->a, sizeof(SQDataType) * newcapacity);
		if (tmp == NULL)
		{
			printf("realloc failed\n");
			exit(-1);
		}
		ps->capacity = newcapacity;
		ps->a = tmp;
	}
}
//尾插
void SeqListPushBack(SL* ps, SQDataType x)
{
	SQLCheckCapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;
}
//尾删
void SeqListPopBack(SL* ps)
{
	assert(ps->size > 0);
	ps->size--;
}
//头插
void SeqListPushFrint(SL* ps, SQDataType x)
{
	SQLCheckCapacity(ps);
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->a[end+1] = ps->a[end];
		end--;
	}
	ps->a[0] = x;
	ps->size++;
}
//头删
void SeqListPopFrint(SL* ps)
{
	assert(ps->size > 0);
	int i = 0;
	for (i = 0; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}
//查找位置
int SeqListFind(SL s, SQDataType x)
{
	int i = 0;
	for (i = 0; i < s.size; i++)
	{
		if (s.a[i] == x)
		{
			return i;
		}
	}
	return -1;
}
//任意插——在下标为pos的位置插入数据
void SeqListInsert(SL* ps, int pos, SQDataType x)
{
	assert(pos >= 0 && pos <= ps->size);
	SQLCheckCapacity(ps);
	int end = ps->size-1;
	while (end >= pos)
	{
		ps->a[end+1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
}
//任意删——删除下标为pos的数据
void SeqListErase(SL* ps, int pos)
{
	assert(pos >= 0 && pos < ps->size);
	int begin = pos + 1;
	while (begin < ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		begin++;
	}
	ps->size--;
}
//销毁空间
void SeqListDestory(SL* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

test.c

#include"SeqList.h"
void test()
{
	SL s1;
	SeqListInit(&s1);
	SeqListPushBack(&s1, 1);
	SeqListPushFrint(&s1, 1);
	SeqListPushFrint(&s1, 2);
	SeqListPushFrint(&s1, 3);
	SeqListPushFrint(&s1, 4);
	SeqListPushBack(&s1, 5);
	SeqListPrint(s1);
	SeqListPopFrint(&s1);
	SeqListPrint(s1);
	int pos = SeqListFind(s1, 1);
	SeqListInsert(&s1, pos, 10);
	SeqListInsert(&s1, 0, 20);
	SeqListPrint(s1);
	SeqListErase(&s1, 0);
	SeqListPrint(s1);
	SeqListDestory(&s1);
}
int main()
{
	test();
	return 0;
}

到此这篇关于C语言顺序表的基本结构与实现思路详解的文章就介绍到这了,更多相关C语言顺序表内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C语言实现顺序表的全操作详解

    目录 线性表 顺序表 顺序表接口实现 1.顺序表初始化 2.顺序表空间增容 3.顺序表打印 4.尾插数据 5.尾删数据 6.头插数据 7.头删数据 8.在pos下标处插入数据 9.删除pos下标处数据 10.数据查找 11.顺序表摧毁 线性表 线性表(linear list)是n个具有相同特性的数据元素的有限序列.线性表是一种在实际中广泛使用的数据结构,常见的线性表有:顺序表.链表.栈.队列.字符串等. 线性表在逻辑上是线性结构,也就是连续的一条直线.但在物理结构上并不一定是连续的,线性表在物理

  • C语言全面讲解顺序表使用操作

    目录 一.顺序表的结构定义 二.顺序表的结构操作 1.初始化 2.插入操作 3.删除操作 4.扩容操作 5.释放操作 6.输出 三.示例 编程环境为 ubuntu 18.04. 顺序表需要连续一片存储空间,存储任意类型的元素,这里以存储 int 类型数据为例. 一.顺序表的结构定义 size 为容量,length 为当前已知数据表元素的个数 typedef struct Vector{ int *data; //该顺序表这片连续空间的首地址 int size, length; } Vec; 二.

  • C语言实现动态顺序表的示例代码

    目录 顺序表概念及结构 基本操作 功能实现 程序运行 顺序表概念及结构 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储.在数组上完成数据的增删查改. 分类: 一般分为静态顺序表和动态顺序表: 静态顺序表:数组大小是固定的用完了无法增容:同时我们无法控制给数组开多少空间合适,开少了,空间不够:开多了,有回会存在空间浪费: 动态顺序表:空间是可以变动的,空间满了我们就增容:解决了静态顺序表的空间不足问题,同时也在一定程度上减少了空间浪费: 因此本篇博客主要实现

  • C语言线性表顺序表示及实现

    目录 准备工作 实现线性表 线性表的动态分配顺序存储结构 构造一个空的线性表 对线性表进行赋值 对线性表进行销毁 对线性表进行重置 判断线性表是否为空 获取线性表的长度 获取线性表某一位置对应的元素 在线性表某一位置插入元素 删除线性表某一位置的元素 求线性表某一元素的前驱 求线性表某一元素的后继 打印线性表 运行结果演示: 源码 线性表是最常用且最简单的一种数据结构.简而言之,一个线性表是n个数据元素的有限序列 线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素. 实现工具

  • C语言超详细讲解顺序表的各种操作

    目录 顺序表是什么 顺序表的结构体 顺序表的接口函数 顺序表相关操作的菜单 顺序表的初始化 添加元素 陈列元素 往最后加元素 往前面加元素 任意位置加元素 删除最后元素 删除前面元素 删除任意元素 整体代码(fun.h部分) 整体代码(fun.cpp部分) 整体代码(主函数部分) 结果展示 顺序表是什么 顺序表是在计算机内存中以数组的形式保存的线性表,线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素.使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中,即通过数

  • C语言实现顺序表的基本操作的示例详解

    目录 一.认识顺序表 1.线性表 2.顺序表的概念及结构 二.顺序表的基本操作(接口实现) 1.初始化顺序表 2.打印顺序表 3.尾插 4.尾删 5.扩容 6.头插 7.头删 8.任意位置插入 9.任意位置删除 10.查找某个数的位置 三.顺序表演示及代码(含源码) 1.演示效果 2.完整源代码 一.认识顺序表 1.线性表 线性表是n个具有相同特性的数据元素的有限序列,线性表是一种在实际中广泛使用的数据结构,常见的线性表有顺序表.链表.栈.队列.字符串……线性表在逻辑上是线性结构,也就是说是一条

  • C语言深入浅出讲解顺序表的实现

    目录 1.线性表 2.顺序表 2.1 概念及结构 2.2 提供接口 2.3 接口实现 今天起开始编写数据结构中的各种数据结构及算法的实现,说到顺序表,我们首先得了解下线性表. 1.线性表 线性表(linear list)是n个具有相同特性的数据元素的有限序列. 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表.链表.栈.队列.字符串… 线性表在逻辑上是线性结构,也就说是连续的一条直线.但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储. 2.顺序表

  • C语言顺序表的基本结构与实现思路详解

    目录 一.顺序表的概念与结构 1.线性表的解释 2.顺序表概念解释 二.顺序表的思路及代码实现详解 1.静态顺序表的实现 2.动态顺序表思路及代码实现 2.1 动态顺序表的整体思路 2.2 定义结构体的实现 2.3 初始化结构体 2.4 结构体打印 2.5 检查数组容量 2.6 头插 2.7 尾插 2.8 头删 2.9 尾删 2.10 任意删除 2.11 任意插入 2.12 空间释放 三.顺序表代码整合 SeqList.h SeqList.c test.c 一.顺序表的概念与结构 1.线性表的解

  • C语言线性表的链式表示及实现详解

    目录 前言 代码实现 1. 单链表的结点构造 2. 构造一个空的头结点 3. 对线性表进行赋值 4.对线性表进行销毁 5.对线性表进行重置 6.判断线性表是否为空 7.获取线性表的长度 8.获取线性表某一位置对应的元素 9.在线性表某一位置插入元素 10.删除线性表某一位置的元素 11.求线性表某一元素的前驱 12.求线性表某一元素的后继 13.打印线性表 运行结果演示 源码 前言 线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素,而线性表的链式存储特点则是用一组任意的存储

  • 对python 树状嵌套结构的实现思路详解

    原始数据 原始数据大致是这样子的: 每条数据中的四个数据分别是 当前节点名称,节点描述(指代一些需要的节点属性),源节点(即最顶层节点),父节点(当前节点上一层节点). datas = [ ["root", "根节点", "root", None], ["node1", "一级节点1", "root", "root"], ["node2", &qu

  • Java实现顺序表和链表结构

    目录 前言: 顺序表 定义: 实现方法: 代码实现: 链表 定义: 分类: 实现方法: 代码实现: 顺序表 & 链表 总结 前言: 线性表(linear list)是n个具有相同特性的数据元素的有限序列. 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表.链表.栈.队列.字符串. 顺序表 定义: 用一段物理地址连续的存储单元依次存储数据元素的线性结构(逻辑上连续,物理上也连续) (1)静态顺序表:使用定长数组存储. (2)动态顺序表:使用动态开辟的数组存储 [注意]静态顺序表的定长数

  • Go语言基础语法之结构体及方法详解

    结构体类型可以用来保存不同类型的数据,也可以通过方法的形式来声明它的行为.本文将介绍go语言中的结构体和方法,以及"继承"的实现方法. 结构体类型 结构体类型(struct)在go语言中具有重要地位,它是实现go语言面向对象编程的重要工具.go语言中没有类的概念,可以使用结构体实现类似的功能,传统的OOP(Object-Oriented Programming)思想中的继承在go中可以通过嵌入字段的方式实现. 结构体的声明与定义: // 使用关键字 type 和 struct 定义名字

  • Go语言学习教程之结构体的示例详解

    目录 前言 可导出的标识符 嵌入字段 提升 标签 结构体与JSON相互转换 结构体转JSON JSON转结构体 练习代码步骤 前言 结构体是一个序列,包含一些被命名的元素,这些被命名的元素称为字段(field),每个字段有一个名字和一个类型. 结构体用得比较多的地方是声明与数据库交互时需要用到的Model类型,以及与JSON数据进行相互转换.(当然,项目中任何需要多种数据结构组合在一起使用的地方,都可以选择用结构体) 代码段1:声明一个待办事项的Model类型: type Todo struct

  • C语言结构体指针引用详解

    目录 指向结构体变量的指针 指向结构体数组的指针 结构体指针,可细分为指向结构体变量的指针和指向结构体数组的指针. 指向结构体变量的指针 前面我们通过"结构体变量名.成员名"的方式引用结构体变量中的成员,除了这种方法之外还可以使用指针. 前面讲过,&student1 表示结构体变量 student1 的首地址,即 student1 第一个项的地址.如果定义一个指针变量 p 指向这个地址的话,p 就可以指向结构体变量 student1 中的任意一个成员. 那么,这个指针变量定义成

  • C语言结构体内存对齐详解

    目录 实例一: 分析:存储结构图如下 实例二: 分析:存储结构如下 实例三: 分析:存储结构如下 实例四: 分析:存储结构图如下 总结 1.结构体内存对齐是指当我们创建一个结构体变量时,会向内存申请所需的空间,用来存储结构体成员的内容.我们可以将其理解为结构体成员会按照特定的规则来存储数据内容. 2.结构体的对齐规则 (1)第一个成员在相比于结构体变量存储起始位置偏移量为0的地址处. (2)从第二个成员开始,在其自身对齐数的整数倍开始存储(对齐数=编译器默认对齐数和成员字节大小的最小值,VS编译

  • C语言堆结构处理TopK问题详解

    目录 问题 分析 代码实现 问题 在一百万个数据中,求出最大的k个数字,怎么效率高. 1. 将一百万个数据排序,承接上一篇的堆排序,时间复杂度为O(N * LogN).但是显然这并不是最优解. 2. 一百万个数据放入一个数组中,将其视为一个完全二叉树,并用向下调整算法将其调整为一个大堆/小堆,然后Top/Popk次,即可求出前K个最大/最小的数字,时间复杂度为:O(N + K*LogN) 3. 用正确的堆处理TopK算法: 先假设求最大的K个数字,则建立大小为K的小根堆,然后在一百万-k个数据中

  • Go语言同步等待组sync.WaitGroup结构体对象方法详解

    目录 sync.WaitGroup结构体对象 WaitGroup的结构体 Add()方法 Done()方法 Wait()方法 Add().Done().Wait()三者对比 sync.WaitGroup使用示例 sync.WaitGroup结构体对象 在Go语言中,sync.WaitGroup结构体对象用于等待一组线程的结束:WaitGroup是go并发中最常用的工具,我们可以通过WaitGroup来表达这一组协程的任务是否完成,以决定是否继续往下走,或者取任务结果: WaitGroup的结构体

随机推荐