【数据结构】——顺序表与链表

简介: 【数据结构】——顺序表与链表

线性表

线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构。

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

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

顺序表

顺序表从开始连续存储size个

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

顺序表一般分为:

1.静态顺序表

缺点:保存数据的数组较小不够使用,较大浪费

//静态顺序表
typedef int SLDateType;
#define N 10
struct Seqlist
{
  SLDateType a[N];
  int size;
};

2.动态顺序表

可以实现按需申请

  • 此时,如果free出现问题,原因可能是指针为野指针,指针未从初始地址释放或者指针越界
//动态顺序表
typedef int SLDateType;
struct Seqlist
{
  SLDateType* a;
  int size;
  int capacity;
};
  • 使用顺序表完成增删查改

seqlist.h文件

#define  _CRT_SECURE_NO_WARNINGS 1  
//头文件
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
静态顺序表
//typedef int SLDateType;
//#define N 10
//struct Seqlist
//{
//  SLDateType a[N];
//  int size;
//};
//动态顺序表
//定义类型
typedef int SLDataType;
//设置初始容量
#define INIT_CAPACITY 5
typedef struct Seqlist
{
  SLDataType* a;
  //有效数据个数
  int size;
  //容量
  int capacity;
}SL;
//初始化顺序表
void SLInit(SL* ps);
//销毁顺序表
void SLDestroy(SL* ps);
//打印顺序表
void SLPrint(SL* ps);
//增
//后增
void SLPushBack(SL* ps, SLDataType X);
//前增
void SLPushFront(SL* ps, SLDataType X);
//插入
void SLInsert(SL* ps, int pos, SLDataType X);
//删
//后删
void SLPopBack(SL* ps);
//前删
void SLPopFront(SL* ps);
//中间删除
void SLErase(SL* ps, int pos);
//查
int SLFind(SL* ps, SLDataType X);
//改
int SLChange(SL* ps, SLDataType X,SLDataType Y);
//扩容
void SLCheckCap

seqlist.c文件

#include"seqlist.h"
//初始化顺序表
void SLInit(SL* ps)
{
  assert(ps->a);
  ps->a = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);
  if (ps->a == NULL)
  {
    perror("Malloc fail");
  }
  ps->size = 0;
  ps->capacity = INIT_CAPACITY;
}
//销毁顺序表
void SLDestroy(SL* ps)
{
  assert(ps->a);
  free(ps->a);
  ps->a = NULL;
  ps->size = ps->capacity = 0;
}
//打印顺序表
void SLPrint(SL* ps)
{
  assert(ps->a);
  int i = 0;
  for (i = 0; i < ps->size; i++)
  {
    printf("%d ",ps->a[i]);
  }
  printf("\n");
}
//后增
void SLPushBack(SL* ps, SLDataType X)
{
  assert(ps->a);
  SLCheckCapacity(ps);
  ps->a[ps->size] = X;
  ps->size++;
}
//后删
void SLPopBack(SL* ps)
{
  assert(ps->a);
  assert(ps->size>0);
  /*if (ps->size == 0)
  {
    return;
  }*/
  ps->size--;
}
//前增
void SLPushFront(SL* ps, SLDataType X)
{
  assert(ps->a);
  SLCheckCapacity(ps);
  int end = ps->size - 1;
  while (end >= 0)
  {
    ps->a[end+1] = ps->a[end];
    end--;
  }
  ps->a[0] = X;
  ps->size++;
}
//前删
void SLPopFront(SL* ps)
{
  assert(ps->a);
  int begin = 0;
  while (begin >= 0 && begin < ps->size)
  {
    ps->a[begin] = ps->a[begin + 1];
    begin++;
  }
  ps->size--;
}
//中间插入
void SLInsert(SL* ps, int pos, SLDataType X)
{
  assert(ps);
  assert(pos >= 0 && pos <= ps->size);
  SLCheckCapacity(ps);
  int end = ps->size - 1;
  while (end >= pos)
  {
    ps->a[end + 1] = ps->a[end];
    end--;
  }
  ps->a[pos] = X;
  ps->size++;
}
//中间删除
void SLErase(SL* ps, int pos)
{
  assert(ps->a);
  assert(pos >= 0 && pos <= ps->size);
  int begin = pos;
  while (begin >= pos && begin <= ps->size)
  {
    ps->a[begin] = ps->a[begin + 1];
    begin++;
  }
  ps->size--;
}
//查找
int SLFind(SL* ps, SLDataType X)
{
  assert(ps->a);
  int i = 0;
  for (i = 0; i < ps->size; i++)
  {
    if (ps->a[i] == X)
    {
      return i;
    }
  }
  return -1;
}
//改
int SLChange(SL* ps, SLDataType X , SLDataType Y)
{
  assert(ps->a);
  int i = 0;
  for (i = 0; i < ps->size; i++)
  {
    if (ps->a[i] == X)
    {
      ps->a[i] = Y;
      return 0;
    }
  }
  return -1;
}
//扩容
void SLCheckCapacity(SL* ps)
{
  if (ps->size == ps->capacity)
  {
    SLDataType* p = (SLDataType*)realloc((void*)ps->a, ps->capacity * sizeof(SLDataType)*2);
    if (p == NULL)
    {
      printf("Realloc fail");
      return;
    }
    ps->a = p;
    p = NULL;
    ps->capacity *= 2;
  }
}

main.c文件

#include"seqlist.h"
//测试顺序表
void TestSeqlist1()
{
  //定义顺序表
  SL s;
  //初始化顺序表
  SLInit(&s);
  //后增
  SLPushBack(&s,1);
  SLPushBack(&s, 2);
  SLPushBack(&s, 3);
  SLPushBack(&s, 4);
  //后删
  SLPopBack(&s);
  //打印
  SLPrint(&s);
  //前增
  SLPushFront(&s, 10);
  SLPushFront(&s, 20);
  SLPushFront(&s, 40);
  //打印
  SLPrint(&s);
  //前删
  SLPopFront(&s);
  //打印
  SLPrint(&s);
  //中间插入
  SLInsert(&s, 1, 6);
  //打印
  SLPrint(&s);
  //中间删除
  SLErase(&s, 2);
  //打印
  SLPrint(&s);
  //改
  SLChange(&s, 2, 9);
  //打印
  SLPrint(&s);
  
  //销毁顺序表
  SLDestroy(&s);
}
int main(void)
{
  //测试顺序表
  TestSeqlist1();
  return 0;
}

链表

了解完顺序表之后,可以明显发现顺序的缺点:

  • 中间与头部的插入删除,时间复杂度为O(N)
  • 增容需要申请空间,拷贝数据,释放旧空间,会有不小的消耗
  • 增容一般是呈2倍增长,会有一定的空间浪费

链表的概念

链表是一种物理存储的结构上非连续,非顺序的存储结构,数据元素的逻辑是通过链表中的指针链接次序实现的

注意:

1.链式结构在逻辑上是连续的,但是在物理上不一定连续。

2.现实中的结点一边拿都是从堆上申请出来的

3.从堆上申请的空间是按照一定的策略来分配的,俩次申请的空间可能连续,也可能不连续

链表的分类

  • 链表的分类大致分为:
    1.单向或者双向

2.带头或者不带头

3.循环或者非循环

其中最常用的是不带头单向非循环链表带头双向循环链表

  • 不带头单向非循环链表:

结构简单,一般不会单独用来存数据,实际中更多是作为其他数据结构的子结构,如哈希桶,图的邻接表等等

  • 带头双向循环链表:

结构最复杂,一般用来单独存储数据,实际中使用的链表数据结构,都是双向循环链表

不带头单向非循环链表的实现

  • slist.h文件
#define  _CRT_SECURE_NO_WARNINGS 1  
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDatatype;
typedef struct SLinklistNode
{
  SLTDatatype date;
  struct SLinklistNode* next;
}SLTNode;
//增加结点
SLTNode* SLTNewNode(SLTDatatype X);
//打印
void SLTPrintf(SLTNode* phead);
//头插
void SLTPushFront(SLTNode** pphead, SLTDatatype X);
//头删 
void SLTPopFront(SLTNode** pphead);
//尾插
void SLTPushBack(SLTNode** pphead, SLTDatatype X);
//尾删
void SLTPopBack(SLTNode** pphead);
//查找
SLTNode* SLTFind(SLTNode* pphead,SLTDatatype X);
//前插
void SLTInsertBefore(SLTNode** pphead, SLTNode* pos ,SLTDatatype X);
//pos位置删
void SLTEraseBefore(SLTNode** pphead, SLTNode* pos);
//后插
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDatatype X);
//后删
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos);
//销毁
void SLTDestory(SLTNode** pphead);
  • slist.c文件
#include"slist.h"
//打印
void SLTPrintf(SLTNode* phead)
{
  SLTNode* cur = phead;
  while (cur)
  {
    printf("%d->", cur->date);
    cur = cur->next;
  }
  printf("NULL\n");
}
//新增加一个结点
SLTNode* SLTNewNode( SLTDatatype X)
{
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    return NULL;
  }
  newnode->date = X;
  newnode->next = NULL;
  return newnode;
}
//头插
void SLTPushFront(SLTNode** pphead, SLTDatatype X)
{
  //动态增加一个结点
  SLTNode* newnode = SLTNewNode(X);
  newnode->next = *pphead;
  *pphead = newnode;
}
//头删
void SLTPopFront(SLTNode** pphead)
{
  //温柔
  /*if (*pphead == NULL)
  {
    return;
  }*/
  //断言
  assert(*pphead);
  
  SLTNode* first = *pphead;
  *pphead = first->next;
  free(first);
  first = NULL;
}
//尾删
void SLTPopBack(SLTNode** pphead)
{
  if (*pphead == NULL)
  {
    return;
  }
  assert(*pphead);
  if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  else
  {
    SLTNode* tail = *pphead;
    while (tail->next->next != NULL)
    {
      tail = tail->next;
    }
    free(tail->next);
    tail->next = NULL;
  }
}
//尾增
void SLTPushBack(SLTNode** pphead, SLTDatatype X)
{
  //新增一个结点
  SLTNode* newnode = SLTNewNode(X);
  SLTNode* tail = *pphead;
  if (*pphead == NULL)
  {
    *pphead = newnode;
  }
  else
  {
    while (tail->next != NULL)
    {
      tail = tail->next;
    }
    tail->next = newnode;
  }
}
//查找
SLTNode* SLTFind(SLTNode* pphead,SLTDatatype X)
{
  SLTNode* cur = pphead;
  while (cur)
  {
    if (cur->date == X)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}
//前插
void SLTInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDatatype X)
{
  assert(pos);
  assert(pphead);
  if (*pphead == pos)
  {
    SLTPushFront(pphead, X);
  }
  else
  {
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    SLTNode* newnode = SLTNewNode(X);
    prev->next = newnode;
    newnode->next = pos;
  }
}
//pos位置删
void SLTEraseBefore(SLTNode** pphead, SLTNode* pos)
{
  assert(pphead);
  assert(pos);
  assert(*pphead);
  if (*pphead == pos)
  {
    SLTPopFront(pphead);
  }
  SLTNode* prev = *pphead;
  while (prev->next != pos)
  {
    prev = prev->next;
  }
  prev->next = pos->next;
  free(pos);
}
//后插
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDatatype X)
{
  assert(pos);
  SLTNode* newnode = SLTNewNode(X);
  newnode->next = pos->next;
  pos->next = newnode;
}
//后删
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos)
{
  assert(pos);
  assert(pos->next);
  SLTNode* del = pos->next;
  pos->next = del->next;
  free(del);
  del = NULL;
}
//销毁
void SLTDestory(SLTNode** pphead)
{
  SLTNode* cur = *pphead;
  while(cur)
  {
    SLTNode* tmp = cur->NEXT;
    free(cur);
    cur = tmp;
  }
  *pphead = NULL;
}

带头双向循环链表的实现

Dlist.h文件

#define  _CRT_SECURE_NO_WARNINGS 1  
//带头双向循环链表的增删查改
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//定义类型
typedef int LTDataType;
//定义结构体
typedef struct ListNode
{
  LTDataType data;
  struct ListNode* prev;
  struct ListNode* next;
}ListNode;
//创建一个返回链表的头结点(哨兵)
ListNode* ListCreate();
//双向链表的销毁
void ListDestory(ListNode* phead);
//双向链表的打印
void ListPrintf(ListNode* phead);
//创造一个newnode
ListNode* ListNewNode(LTDataType x);
//双向链表的尾插
void ListPushBack(ListNode* phead, LTDataType x);
//双向链表的尾删
void ListPopBack(ListNode* phead);
//双向链表的头插
void ListPushFront(ListNode* phead, LTDataType x);
//双向链表的头删
void ListPopFront(ListNode* phead);
//双向链表的查找
ListNode* ListFind(ListNode* phead, LTDataType x);
//双向链表在pos前插入
void ListInsert(ListNode* phead, LTDataType x);
//双向链表在pos删除
void ListErase(ListNode* pos);

Dlist.c文件

#include"DList.h"
//创建一个返回链表的头结点(哨兵)
ListNode* ListCreate()
{
  ListNode* phead = ListNewNode(-1);
  phead->next = phead;
  phead->prev = phead;
  return phead;
}
//双向链表的销毁(需自行释放哨兵头)
void ListDestory(ListNode* phead)
{
  assert(phead);
  ListNode* cur = phead->next;
  while (cur != phead)
  {
    ListNode* tail = cur;
    cur = cur->next;
    free(tail);
    tail = NULL;
  }
}
//双向链表的打印
void ListPrintf(ListNode* phead)
{
  assert(phead);
  ListNode* cur = phead->next;
  printf("->NULL->");
  while (cur != phead)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("\n");
}
//创造一个newnode
ListNode* ListNewNode(LTDataType x)
{
  ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    return NULL;
  }
  newnode->data = x;
  newnode->next = NULL;
  newnode->prev = NULL;
  return newnode;
}
//双向链表的尾插
void ListPushBack(ListNode* phead, LTDataType x)
{
  assert(phead);
  ListNode* newnode = ListNewNode(x);
  newnode->next = phead;
  newnode->prev = phead->prev;
  phead->prev->next = newnode;
  phead->prev = newnode;
}
//双向链表的尾删
void ListPopBack(ListNode* phead)
{
  assert(phead);
  assert(phead->next != phead);
  ListNode* tail = phead->prev;
  phead->prev = tail->prev;
  tail->prev->next = phead;
  free(tail);
  tail = NULL;
}
//双向链表的头插
void ListPushFront(ListNode* phead, LTDataType x)
{
  assert(phead);
  ListNode* newnode = ListNewNode(x);
  newnode->next = phead->next;
  newnode->prev = phead;
  phead->next->prev = newnode;
  phead->next = newnode;
}
//双向链表的头删
void ListPopFront(ListNode* phead)
{
  assert(phead);
  assert(phead->next != phead);
  ListNode* first = phead->next;
  phead->next = first->next;
  first->next->prev = phead;
  free(first);
  first = NULL;
}
//双向链表的查找
ListNode* ListFind(ListNode* phead, LTDataType x)
{
  assert(phead);
  ListNode* cur = phead->next;
  while (cur != phead)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}
//双向链表在pos前插入
void ListInsert(ListNode* pos, LTDataType x)
{
  assert(pos);
  ListNode* newnode = ListNewNode(x);
  ListNode* front = pos->prev;
  newnode->prev = front;
  newnode->next = pos;
  front->next = newnode;
  pos->prev = newnode;
}
//双向链表在pos删除(自行释放指针)
void ListErase(ListNode* pos)
{
  assert(pos);
  pos->prev->next = pos->next;
  pos->next->prev = pos->prev;
  free(pos);
}

顺序表与链表的区别

不同点 顺序表 链表
存储空间上 物理上连续 逻辑上连续,物理上不一定连续
随机访问 支持:O(1) 不支持:O(N)
任意位置插入或者删除元素 可能需要移动元素,效率低O(N) 只需要修改指针指向
插入 动态顺序表,空间不够需要扩容 没有容量的概念
应用场景 元素高效访问,频繁访问 任意位置插入和删除频繁
缓存利用率


相关文章
|
15天前
|
存储
顺序表和链表(2)
【10月更文挑战第23天】
顺序表和链表(2)
|
16天前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
44 4
|
17天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找等具体详解步骤以及举例说明
|
17天前
|
存储 C语言
【数据结构】顺序表(c语言实现)(附源码)
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列,常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构,其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别,并重点介绍了动态顺序表的实现,包括初始化、销毁、打印、增删查改等操作。最后,文章总结了顺序表的时间复杂度和局限性,并预告了后续关于链表的内容。
49 3
|
16天前
|
存储 算法 数据管理
顺序表和链表(1)
【10月更文挑战第22天】
|
17天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
17天前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
17天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找习题精讲等具体详解步骤以及举例说明
|
16天前
|
C语言
【数据结构】双向带头循环链表(c语言)(附源码)
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1),提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现,包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
37 0
|
30天前
|
存储
[数据结构] -- 双向循环链表
[数据结构] -- 双向循环链表
21 0

热门文章

最新文章