数据结构——复杂度和顺序表

简介: 数据结构——复杂度和顺序表

在用代码实现算法前的时候就已经估算出时间复杂度和空间复杂度了

时间复杂度

只讲解如何计算

在计算时间复杂度的时候,只考虑程序或者算法中关键部分的大概运行次数。我们用大O表示法。

大O表示法

1.只保留高次项(增长速率最快的)并且高次项的系数改成1

2.所有常数项均为1

3.可以含有多个未知元,如:O(m+n)

4.最好运行次数与最差运行次数的平均次数。(一般只关注最差的情况)

log n其实是以2为底的对数,以其他为低的数都要写出来,比如log₃n

空间复杂度

完成某一个算法需要额外开辟的空间,也是用大O表示法。其求法和时间复杂度的求法类似。注意:递归使用的栈空间也属于额外的空间开销


顺序表

内存中开辟连续的储存单元存储数据用以实现增删查改。

创建

typedef int SLDataType;
//顺序表中数据的类型
typedef struct seqlist
{
  SLDataType* arr;//用于动态开辟数组
  int size;//有效个数
  int capacity;//空间
}SeqList;

初始化

void SeqListInit(SeqList* psql)
{
  psql->arr = NULL;
  psql->size = 0;
  psql->capacity = 0;
}

销毁

void SeqListDestroy(SeqList* psql)
{
  assert(psql);
  free(psql->arr);
  psql->arr = NULL;
  psql->capacity = psql->size = 0;
}

检查容量是否已满

如果满了,就进行扩容

void CheckCapacity(SeqList* psql)
{
  if (psql->size == psql->capacity)
  {
    psql->capacity += 10;
    SLDataType* temp = (SLDataType*)realloc(psql->arr, psql->capacity * sizeof(SLDataType));
    if (temp == NULL)
    {
      printf("扩容%s\n", strerror(errno));
      exit(-1);
    }
    psql->arr = temp;
  }
}

尾插

void SeqListPushBack(SeqList* psql, SLDataType x)
{
  CheckCapacity(psql);
  psql->arr[psql->size] = x;
  psql->size++;
}

尾删

注意没有有效数的时候,即psql->size等于0的时候

void SeqListPopBack(SeqList* psql)
{
  assert(psql);
  assert(psql->size);
  psql->size--;
}

头插

void SeqListPushFront(SeqList* psql, SLDataType x)
{
  CheckCapacity(psql);
  int i = 0;
  for (i = psql->size; i > 0; i--)
  {
    psql->arr[i] = psql->arr[i - 1];
  }
  psql->arr[i] = x;
  psql->size++;
}

头删

注意没有有效数的时候,即psql->size等于0的时候

void SeqListPopFront(SeqList* psql)
{
  assert(psql);
  assert(psql->size);
  int i = 0;
  while (i < psql->size-1)
  {
    psql->arr[i] = psql->arr[i + 1];
    i++;
  }
  psql->size--;
}

打印

void SeqListPrint(SeqList* psql)
{
  int i = 0;
  for (i = 0; i < psql->size; i++)
  {
    printf("%d ", psql->arr[i]);
  }
  printf("\n");
}

任意一个位置插入

void SeqListInsert(SeqList* psql, int Pos, SLDataType x)
{
  assert(psql);
  assert(Pos >= 0 && Pos <= psql->size);
  CheckCapacity(psql);
  int i = psql->size-1;
  while (i>=Pos)
  {
    psql->arr[i + 1] = psql->arr[i];
    i--;
  }
  psql->arr[Pos] = x;
  psql->size++;
}

任意位置删除

void SeqListErase(SeqList* psql, int Pos)
{
  assert(psql);
  assert(Pos >= 0 && Pos < psql->size);
  int i = Pos;
  while (i<psql->size-1)
  {
    psql->arr[i] = psql->arr[i + 1];
    i++;
  }
  psql->size--;
}

查找

找到返回下标,找不到返回-1。

int SeqListFind(SeqList* psql, SLDataType x)
{
  assert(psql);
  int pos = 0;
  while (pos < psql->size)
  {
    if (psql->arr[pos] == x)
      return pos;
    pos++;
  }
  return -1;
}
相关文章
|
1月前
|
存储 编译器 C语言
数据结构-顺序表详解(看这篇就足够了,哈哈哈)
数据结构-顺序表详解(看这篇就足够了,哈哈哈)
49 2
|
17天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找等具体详解步骤以及举例说明
|
17天前
|
存储 C语言
【数据结构】顺序表(c语言实现)(附源码)
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列,常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构,其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别,并重点介绍了动态顺序表的实现,包括初始化、销毁、打印、增删查改等操作。最后,文章总结了顺序表的时间复杂度和局限性,并预告了后续关于链表的内容。
49 3
|
17天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找习题精讲等具体详解步骤以及举例说明
|
1月前
|
存储 Java
数据结构第二篇【关于java线性表(顺序表)的基本操作】
数据结构第二篇【关于java线性表(顺序表)的基本操作】
30 6
|
1月前
|
存储 安全 Java
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
23 3
|
1月前
|
存储 C语言
探索C语言数据结构:利用顺序表完成通讯录的实现
本文介绍了如何使用C语言中的顺序表数据结构实现一个简单的通讯录,包括初始化、添加、删除、查找和保存联系人信息的操作,以及自定义结构体用于存储联系人详细信息。
19 2
|
1月前
|
存储 算法 索引
【数据结构】——顺序表
【数据结构】——顺序表
|
1月前
|
存储
【数据结构】线性表和顺序表
【数据结构】线性表和顺序表
22 1
|
1月前
|
存储
数据结构1——顺序表
数据结构1——顺序表
17 1