数据结构——顺序表和链表（上）

2022-12-09 82

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 笔记

线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储

链表

顺序表

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

1. 静态顺序表：使用定长数组存储元素。

2. 动态顺序表：使用动态开辟的数组存储。

typedef struct SeqList
{
SLDataType* array; // 指向动态开辟的数组
size_t size ; // 有效数据个数
size_t capicity ; // 容量空间的大小
}SeqList;

顺序表的使用

结构体的定义

typedef int SLDatatype;
typedef struct Sqelist
{
  SLDatatype* a;//存储数据
  int size;//当前存储个数
  int capacity;//当前容量
}SL;

数据的初始化

void SLInit(SL *psl)
{
  assert(psl);
  psl->a = NULL;
  psl->capacity = psl->size = 0;
}

数据容量的检查

void Checkcapacity(SL* psl)
{
  if (psl->capacity == psl->size)
  {
  int newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
  SLDatatype* tmp = (SLDatatype*)realloc(psl->a, sizeof(SLDatatype) * newcapacity);
  if (tmp == NULL)
  {
    perror("realloc fail");
    return;
  }
  psl->a = tmp;
  psl->capacity = newcapacity;
  }
}

头部插入数据

void SLPpushfront(SL* psl, SLDatatype x)
{
  assert(psl);
  Checkcapacity(psl);
  int end = psl->size - 1;
  while (end >= 0)
  {
  psl->a[end + 1] = psl->a[end];
  end--;
  }
  psl->a[0] = x;
  psl->size++;
}

头部删除数据

void SLPpopfront(SL* psl)//头删
{
  assert(psl);
  if (psl->size == 0)
  return;
  int i = 0;
  for (i = 0; i < psl->size -1; i++)
  {
  psl->a[i] = psl->a[i + 1];
  }
  psl->size--;
}//这里不能进行所任，缩容是需要代价的，缩容分俩种，一种原地缩，第二种异地找个新空间大小为缩后的大小，若后期要插入元素，则又要开辟空间，比较麻烦

尾部插入数据

void SLPpopback(SL* psl)
{
  assert(psl);
  if (psl->size == 0)
  return;
  psl->size--;
}

尾部删除数据

void SLPpopback(SL* psl)
{
  assert(psl);
  if (psl->size == 0)
  return;
  psl->size--;
}

任意数据删除

void SLErase(SL* psl, size_t pos)
{
  assert(psl);
  assert(pos < psl->size);
  int i = 0;
  for (i = pos; i < psl->size - 1; i++)
  {
  psl->a[i] = psl->a[i + 1];
  }
  psl->size--;
}

随机数据插入

void SLInsert(SL* psl, int pos, SLDatatype x)
{
  assert(psl);
  assert(pos <= psl->size);
  int i = 0;
  Checkcapacity(psl);
  for (i = psl->size; i >= pos; i--)
  {
  if (i == pos)
    psl->a[i] = x;
  else
    psl->a[i] = psl->a[i - 1];
  }
  psl->size++;
}
/*size_t end=pls->size-1;
  * while(end>=pos)
  * {
  * psl->a[end+1]=psl->a[end];
  * --end;
  * }
  * psl->a[pos]=x;
  * ++psl->size;
  * 这种写法 pos会隐式提升为size_t（unsigned int）类型
  * end 和 pos都为0之后，再--end，此时end变为一个非常大的数字
  * 注意这里的隐式提升
  * end和pos，俩个不能有一个是size_t类型，不然程序会出现错误
  */

数据查找

int SLPfine(SL* psl, SLDatatype x)
{
  assert(psl);
  int i = 0;
  for (i = 0; i < psl->size; i++)
  {
  if (psl->a[i] == x)
    return i;
  }
  return -1;
}

数据打印

void SLPprint(SL* psl)
{
  assert(psl);
  int i = 0;
  for (i = 0; i < psl->size; i++)
  {
  printf("%d ", psl->a[i]);
  }
}

数据修改

void SLModify(SL* psl, size_t pos, SLDatatype x)
{
  assert(psl);
  assert(pos < psl->size);
  psl->a[pos] = x;
}

顺序表缺点

1. 中间/头部的插入删除，时间复杂度为O(N)

2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。

3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到 200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

链表

链表：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。单链表不需要初始化

结构体的创建

正确写法

typedef  int SLTDataType;
typedef struct SlistNode
{
  SLTDataType data;
  struct SlistNode* next;
}SLTNode;

错误写法

typedef struct SlistNode
{
  SLTDataType data;
  struct SlistNode* next;
  //SLTNode*next;     错误写法，先有蛋还是先有鸡？
  // SlistNode* next; 错误写法，
}SLTNode;
typedef struct SlistNode
{
  SLTDataType data;
  struct SlistNode* next;
}SLTNode，*PSLNode;
SLTNode*= PSLNode= struct SlistNode*,这三个等价

打印链表

void SListprint(SLTNode* phead)
{
  //phead可能会为空这里不需要断言
  SLTNode* cur = phead; 
  while (cur != NULL)
  {
  printf("%d->", cur->data);
  cur = cur->next;
  }
}

新节点的建立

SLTNode* BuySLTnode(SLTDataType x)
{
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newnode == NULL)
  {
  perror("malloc fail");
  exit(-1);
  }
  newnode->data = x;
  newnode->next = NULL;
return newnode；
}

需要新节点的地方会很多，建立一个新的函数专门建立节点

头部插入

创建新节点前，phead指向第一个节点

创建新节点：先让newnode->next指向phead, phead指向第一个节点的地址，也就是说新节点通过phead拿到了原来第一个节点的地址

然后让phead指向新节点地址

void SListpushfront(SLTNode* phead, SLTDataType x)
{
SLTNode newnode;//错误写法
  SLTNode* newnode =(SLTNode*) malloc(sizeof(SLTNode));
}

上面为错误代码不能用是因为：不能用局部节点，不然一出该函数就会被销毁，因此我们要用上面的函数来创建节点

方式1：

void SListpushfront(SLTNode* phead, SLTDataType x)
{
  SLTNode* newnode = BuySLTnode(x);
  newnode->next = phead;
  phead = newnode;
}

运行后无法打印，这是因为我们在传参的时候没有传地址，因此在出建立节点的函数的时候会对形参销毁

方式二，传地址

SLTNode* plist=NULL;
  SListpushfront(&plist, 5);
void SListpushfront(SLTNode**pphead, SLTDataType x)
{
  SLTNode* newnode = BuySLTnode(x);
  newnode->next =*pphead;
  *pphead = newnode;
}

pphea存的是plist的地址，*pphead的plist=等号右边的值，可参考下图，此时能正常打印。