【学习笔记之数据结构】链表-阿里云开发者社区

【学习笔记之数据结构】链表

2023-04-25 157

版权

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

简介： 【学习笔记之数据结构】链表

链表基础介绍

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

链表在内存空间上不一定是连续的，也没必要是连续的，但是链表在逻辑上一定是连续的。通过找到指针建立逻辑顺序。

链表分类

单向、双向：

带头、不带头

循环、不循环

单向双向、带头不带头、循环不循环这三个可以相互组合，一个可以构成八种类型的链表。最常用链表是不带头单向不循环链表和带头双向循环链表。

不带头单向不循环链表：结构最简单，一般不会单独用来存数据。实际中多用来做其他数据结构的子结构。

带头双向循环链表：结构最复杂，一般单独用来存数据。该链表虽然结构复杂，但是具备很多优势，所以实际开发中使用的链表多是这种链表。

代码实例：

不带头单向不循环链表

#pragma once

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;
typedef struct SListNode {
  SLTDataType data;
  struct SListNode* next;
}SListNode;
//动态申请一个节点
SListNode* BuySListNode(SLTDataType x);
//创建单链表
SListNode* CreateSListNode(int x);
//单链表打印
void SListPrint(SListNode* plist);
//尾插尾删
void SListPushBack(SListNode** pplist, SLTDataType x);
void SListPopBack(SListNode** pplist);
//头插头删
void SListPushFront(SListNode** pplist, SLTDataType x);
void SListPopFront(SListNode** pplist);
//查找
SListNode* SlistFind(SListNode* pos, SLTDataType x);
//在pos位置插入删除
void SListInsertAfter(SListNode* pos, SLTDataType x);
void SListEraseAfter(SListNode* pos);
//单链表销毁
void SListDestroy(SListNode** pplist);

#include "SList.h"
void testSList() {
  SListNode* plist = CreateSListNode(5);
  SListPrint(plist);
  SListPushBack(&plist, 20);
  SListPushBack(&plist, 10);
  SListPrint(plist);
  SListPopBack(&plist);
  SListPrint(plist);
  SListPushFront(&plist, 7);
  SListPushFront(&plist, 7);
  SListPrint(plist);
  SListPopFront(&plist);
  SListPrint(plist);
  SListNode* p = SlistFind(plist, 3);
  SListInsertAfter(p, 50);
  SListPrint(plist);
  SListEraseAfter(p);
  SListPrint(plist);
  SListDestroy(&plist);
}
int main() {
  testSList();
  return 0;
}

#include "SList.h"
SListNode* BuySListNode(SLTDataType x) {
  SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
  if (newnode == NULL) {
    perror("malloc fail");
    exit(-1);
  }
  newnode->data = x;
  newnode->next = NULL; 
  return newnode;
}
SListNode* CreateSListNode(int x) {
  SListNode* phead = NULL, * ptail = NULL;
  for (int i = 0; i < x; i++) {
    SListNode* newnode = BuySListNode(i);
    if (phead == NULL) {
      ptail = phead = newnode;
    }
    else {
      ptail->next = newnode;
      ptail = newnode;
    }
  }
  return phead;
}
void SListPrint(SListNode* phead) {
  SListNode* cur = phead;
  while (cur != NULL) {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}
void SListPushBack(SListNode** pplist, SLTDataType x) {
  SListNode* newnode = BuySListNode(x);
  if (*pplist == NULL) {
    *pplist = newnode;
  }
  else {
    SListNode* ptail = *pplist;
    while (ptail->next != NULL) {
      ptail = ptail->next;
    }
    ptail->next = newnode;
  }
}
void SListPopBack(SListNode** pplist) {
  assert(*pplist);
  SListNode* ptail = *pplist;
  while (ptail->next->next != NULL) {
    ptail = ptail->next;
  }
  free(ptail->next);
  ptail->next = NULL;
}
void SListPushFront(SListNode** pplist, SLTDataType x) {
  SListNode* newnode = BuySListNode(x);
  newnode->next = *pplist;
  *pplist = newnode;
}
void SListPopFront(SListNode** pplist) {
  assert(*pplist);
  SListNode* next = (*pplist)->next;
  free(*pplist);
  *pplist = next;
}
SListNode* SlistFind(SListNode* pos, SLTDataType x) {
  SListNode* cur = pos;
  while (cur) {
    if (cur->data == x) {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}
void SListInsertAfter(SListNode* pos, SLTDataType x) {
  assert(pos);
  /*if(pos->next){
    SListNode* newnode = BuySListNode(x);
    SListNode* cur = pos->next;
    pos->next = newnode;
    newnode->next = cur;
  }
  else {
    SListNode* newnode = BuySListNode(x);
    pos->next = newnode;
  }*/
  SListNode* newnode = BuySListNode(x);
  newnode->next = pos->next;
  pos->next = newnode;
}
void SListEraseAfter(SListNode* pos) {
  assert(pos);
  SListNode* cur = pos->next->next;
  pos->next = cur;
}
void SListDestroy(SListNode** pplist) {
  SListNode* cur = *pplist;
  while (cur) {
    SListNode* next = cur->next;
    free(cur);
    cur = next;
  }
  *pplist = NULL;
}

带头双向循环链表

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
//带头双向循环链表
typedef int LTDataType;
typedef struct DoubleListNode
{
  struct DoubleListNode* next;
  struct DoubleListNode* prev;
  LTDataType data;
}DLTNode;
DLTNode* BuyListNode(LTDataType x);
//创建返回链表的头结点
DLTNode* ListCreate();
//双向链表打印
void ListPrint(DLTNode* plist);
//双向链表销毁
void ListDestory(DLTNode* plist);
//双向链表尾插
void ListPushBack(DLTNode* plist, LTDataType x);
//双向链表尾删
void ListPopBack(DLTNode* plist);
//双向链表头插
void ListPushFront(DLTNode* plist, LTDataType x);
//双向链表头删
void ListPopFront(DLTNode* plist);
//双向链表查找
DLTNode* ListFint(DLTNode* plist, LTDataType x);
//双向链表在pos前插入
void ListInsert(DLTNode* pos, LTDataType x);
//双向链表删除pos位置结点
void ListErase(DLTNode* pos);
//判空
bool LTEmpty(DLTNode* plist);
//计数
size_t LTSize(DLTNode* plist);

#include "DSList.h"
DLTNode* BuyListNode(LTDataType x) 
{
  DLTNode* node = (DLTNode*)malloc(sizeof(DLTNode));
  if (node == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  node->data = x;
  node->next = NULL;
  node->prev = NULL;
  return node;
}
DLTNode* ListCreate()
{
  DLTNode* phead = BuyListNode(-1);
  phead->next = phead;
  phead->prev = phead;
  return phead;
}
void ListPrint(DLTNode* plist)
{
  assert(plist);
  DLTNode* cur = plist->next;
  while (cur != plist)
  {
    printf("%d ", cur->data);
    cur = cur->next;
  }
  printf("\n");
}
void ListPushBack(DLTNode* plist, LTDataType x)
{
  assert(plist);
  DLTNode* newnode = BuyListNode(x);
  DLTNode* tail = plist->prev;
  tail->next = newnode;
  newnode->prev = tail;
  plist->prev = newnode;
  newnode->next = plist;
}
void ListPopBack(DLTNode* plist)
{
  assert(plist);
  assert(plist->next != plist);
  DLTNode* tail = plist->prev;
  plist->prev = tail->prev;
  tail->prev->next = plist;
  free(tail);
}
void ListPushFront(DLTNode* plist, LTDataType x)
{
  assert(plist);
  DLTNode* newnode = BuyListNode(x);
  DLTNode* head = plist->next;
  plist->next = newnode;
  newnode->prev = plist;
  head->prev = newnode;
  newnode->next = head;
}
void ListPopFront(DLTNode* plist)
{
  assert(plist);
  assert(plist->next != plist);
  DLTNode* head = plist->next;
  plist->next = head->next;
  head->next->prev = plist;
  free(head);
}
DLTNode* ListFint(DLTNode* plist, LTDataType x)
{
  assert(plist);
  DLTNode* cur = plist->next;
  while (cur != plist)
  {
    if (cur->data == x)
      return cur;
    cur = cur->next;
  }
  return NULL;
}
void ListInsert(DLTNode* pos, LTDataType x)
{
  assert(pos);
  DLTNode* newnode = BuyListNode(x);
  DLTNode* cur = pos->prev;
  pos->prev = newnode;
  newnode->next = pos;
  cur->next = newnode;
  newnode->prev = cur;
}
void ListErase(DLTNode* pos)
{
  assert(pos);
  DLTNode* cur = pos;
  cur->prev->next = cur->next;
  cur->next->prev = cur->prev;
  free(pos);
}
void ListDestory(DLTNode* plist)
{
  assert(plist);
  DLTNode* cur = plist->next;
  while (cur != plist)
  {
    DLTNode* next = cur->next;
    free(cur);
    cur = next;
  }
  free(plist);
}
bool LTEmpty(DLTNode* plist)
{
  assert(plist);
  return plist->next == plist;
}
size_t LTSize(DLTNode* plist)
{
  assert(plist);
  size_t size = 0;
  DLTNode* cur = plist->next;
  while (cur != plist) {
    size++;
    cur = cur->next;
  }
  return size;
}

#include "DSList.h"
int main() 
{
  DLTNode* plist = ListCreate();
  ListPushBack(plist, 1);
  ListPushBack(plist, 2);
  ListPushBack(plist, 3);
  ListPrint(plist);
  ListPopBack(plist);
  ListPrint(plist);
  ListPushFront(plist, 30);
  ListPushFront(plist, 20);
  ListPushFront(plist, 10);
  ListPrint(plist);
  ListPopFront(plist);
  ListPrint(plist);
  printf("%d\n", ListFint(plist, 1)->data);
  DLTNode* pos = ListFint(plist, 1);
  ListInsert(pos, 7);
  ListPrint(plist);
  ListErase(pos);
  ListPrint(plist);
  ListDestory(plist);
  return 0;
}

【学习笔记之数据结构】链表

链表基础介绍

链表分类

代码实例：

热门文章

最新文章

相关课程

相关电子书

探索云世界

热门

云计算

大数据

云原生

人工智能

数据库

开发与运维

活动广场

任务中心

训练营

直播

乘风者计划

下载

镜像站

技术资料

【学习笔记之数据结构】链表

链表基础介绍

链表分类

代码实例：

热门文章

最新文章

相关课程

相关电子书