无头单向不循环链表和带头双向循环链表的创建

2023-08-07 41

版权

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

简介： 接下来我们将会了解最基础的链表--->单链表以及最方便也是最爽的链表--->带头双向循环链表。

前言：

接下来我们将会了解最基础的链表--->单链表

以及最方便也是最爽的链表--->带头双向循环链表。

若有看不懂之处，可画图或者借鉴这里：反转单链表，对于数据结构而言，无非就是增删查改，当我们能够熟练应用以及画图后，其OJ题和以下代码都是小卡拉米。

无头单向不循环链表

单链表图：

头文件：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int DataType;
typedef struct STLNode
{
  DataType data;
  struct STLNode* next;
}STLNode;
void STL_Print(STLNode* phead);
void STL_PushBack(STLNode** pphead, DataType x);
void STL_PushFront(STLNode** pphead, DataType x);
void STL_PopBack(STLNode** pphead);
void STL_PopFront(STLNode** pphead);
STLNode* STL_Find(STLNode* phead, DataType x);
void STL_InsertAfter(STLNode* pos, DataType x);
void STL_EraseAfter(STLNode* pos);
void STL_Destroy(STLNode** pphead);

Test文件：

#include "STLNode.h"
void Test1(STLNode* phead);
int main()
{
  STLNode* plist = NULL;
  Test1(plist);
  return 0;
}
void Test1(STLNode* phead)
{
  STL_PushBack(&phead, 1);
  STL_PushBack(&phead, 2);
  STL_PushBack(&phead, 3);
  STL_Print(phead);
  STL_PushFront(&phead, 11);
  STL_PushFront(&phead, 22);
  STL_PushFront(&phead, 33);
  STL_Print(phead);
  STLNode* ret = STL_Find(phead, 1);
  STL_InsertAfter(ret, 666);
  STL_Print(phead);
  STL_EraseAfter(ret);
  STL_Print(phead);
  STL_Destroy(&phead);
  STL_Print(phead);
  //STL_PopBack(&phead);
  //STL_PopBack(&phead);
  //STL_Print(phead);
  //STL_PopFront(&phead);
  //STL_PopFront(&phead);
  //STL_Print(phead);
}

函数源文件：

对于以下函数中部分有对phead和pphead的检查，部分没有，原因是这样的：

对于是否需要对其进行断言，我们是要看他为NULL时合不合理，合理就不断言，不合理就断言，例如STL_Printf函数中，当phead为NULL时，说明该链表是空的，直接打印NULL就可以，这是很合理的。而对于STL_PushBack函数来说，phead为NULL同样合理，因为phead为NULL我们尾插其实也就相当于头插，很合理，但是对于pphead来说，他作为plist的地址，就算plist为NULL，pphead是不应该为NULL的，所以他为NULL就非常不合理，我们要对其进行断言检查。

#include "STLNode.h"
void STL_Print(STLNode* phead)
{
  while (phead)
  {
    printf("%d->", phead->data);
    phead = phead->next;
  }
  printf("NULL\n");
}
STLNode* Malloc(DataType x)
{
  STLNode* temp = (STLNode*)malloc(sizeof(STLNode));
  if (temp == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  temp->data = x;
  temp->next = NULL;
  return temp;
}
void STL_PushBack(STLNode** pphead, DataType x)
{
  assert(pphead);
  STLNode* temp = Malloc(x);
  if (*pphead == NULL)
  {
    *pphead = temp;
  }
  else
  {
    STLNode* cur = *pphead;
    while (cur->next != NULL)
    {
      cur = cur->next;
    }
    cur->next = temp;
  }
}
void STL_PushFront(STLNode** pphead, DataType x)
{
  assert(pphead);
  STLNode* temp = Malloc(x);
  temp->next = *pphead;
  *pphead = temp;
}
void STL_PopBack(STLNode** pphead)
{
  assert(pphead);
  assert(*pphead);
  STLNode* cur = *pphead;
  STLNode* temp = *pphead;
  if (cur->next == NULL)
  {
    free(cur);
    *pphead = NULL;
  }
  else
  {
    while (cur->next)
    {
      temp = cur;
      cur = cur->next;
    }
    free(cur);
    temp->next = NULL;
  }
}
void STL_PopFront(STLNode** pphead)
{
  assert(pphead);
  assert(*pphead);
  STLNode* cur = *pphead;
  *pphead = (*pphead)->next;
  free(cur);
}
STLNode* STL_Find(STLNode* phead, DataType x)
{
  if (phead == NULL)
  {
    printf("NULL\n");
    return;
  }
  while (phead != NULL)
  {
    if (phead->data == x)
    {
      return phead;
    }
    phead = phead->next;
  }
  printf("Can not find\n");
  return;
}
void STL_InsertAfter(STLNode* pos, DataType x)
{
  assert(pos);
  STLNode* temp = Malloc(x);
  temp->next = pos->next;
  pos->next = temp;
}
void STL_EraseAfter(STLNode* pos)
{
  assert(pos);
  assert(pos->next);
  STLNode* cur = pos->next;
  pos->next = pos->next->next;
  free(cur);
}
void STL_Destroy(STLNode** pphead)
{
  assert(pphead);
  if (*pphead == NULL)
  {
    return;
  }
  STLNode* temp = *pphead;
  STLNode* cur = *pphead;
  while (temp)
  {
    cur = temp->next;
    free(temp);
    temp = cur;
  }
  *pphead = NULL;
}

带头双向循环链表

图：

头文件：

这个链表最爽的地方在于，他可以很轻松地找到尾，不管是尾插还是头插都非常爽，非常方便，如果我们想在半小时内写完这个链表，那么就可以对尾插和头插复用LTInsert函数，对于尾删和头删复用LTErase函数,也就是说，这两个函数是核心函数，有了他们，迅速写完该链表成为现实。

尾插的复用：LTInsert(phead,x);

头插的复用：LTInsert(phead->next,x);

尾删的复用：LTErase(phead->prev);

头删的复用：LTErase(phead->next);

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int DataType;
typedef struct LTNode
{
  DataType data;
  struct LTNode* prev;
  struct LTNode* next;
}LTNode;
LTNode* Init();
LTNode* Malloc(DataType x);
LTNode* LTFind(LTNode* phead, DataType x);
void LTPrintf(LTNode* phead);
void LTPushBack(LTNode* phead, DataType x);
void LTPopBack(LTNode* phead);
void LTPushFront(LTNode* phead, DataType x);
void LTPopFront(LTNode* phead);
void LTInsert(LTNode* pos, DataType x);   //在pos位置前插入节点
void LTErase(LTNode* pos);                //删除pos位置节点
void LTDestroy(LTNode* phead);

Test文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include "LTNode.h"
void Test1();
int main()
{
  Test1();
  return 0;
}
void Test1()
{
  LTNode* plist = NULL;
  plist = Init();
  LTPushBack(plist, 1);
  LTPushBack(plist, 2);
  LTPushBack(plist, 3);
  LTPushBack(plist, 4);
  LTPushBack(plist, 5);
  LTPushBack(plist, 6);
  LTPrintf(plist);
  LTPopBack(plist);
  LTPopBack(plist);
  LTPopBack(plist);
  LTPrintf(plist);
  LTPushFront(plist, 10);
  LTPushFront(plist, 20);
  LTPushFront(plist, 30);
  LTPrintf(plist);
  LTPopFront(plist);
  LTPrintf(plist);
  LTNode *pos = LTFind(plist, 10);
  LTInsert(pos, 66);
  LTPrintf(plist);
  LTErase(pos);
  LTPrintf(plist);
  LTDestroy(plist);
  plist = NULL;
}

函数源文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include "LTNode.h"
LTNode* Malloc(DataType x)
{
  LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  newnode->data = x;
  return newnode;
}
LTNode* Init()
{
  LTNode* newnode = Malloc(0);
  newnode->next = newnode;
  newnode->prev = newnode;
  return newnode;
}
void LTPrintf(LTNode* phead)
{
  assert(phead);
  printf("phead<=>");
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    printf("%d<=>", cur->data);
    cur = cur->next;
  }
  putchar('\n');
}
void LTPushBack(LTNode* phead, DataType x)
{
  assert(phead);
  LTNode *newnode = Malloc(x);
  LTNode* tail = phead->prev;
  tail->next = newnode;
  newnode->prev = tail;
  newnode->next = phead;
  phead->prev = newnode;
}
void LTPopBack(LTNode* phead)
{
  assert(phead);
  assert(phead->next != phead);
  LTNode* tail = phead->prev;
  LTNode* newtail = tail->prev;
  newtail->next = phead;
  phead->prev = newtail;
  free(tail);
}
void LTPushFront(LTNode* phead, DataType x)
{
  assert(phead);
  LTNode* newnode = Malloc(x);
  LTNode* old_next = phead->next;
  phead->next = newnode;
  newnode->prev = phead;
  newnode->next = old_next;
  old_next->prev = newnode;
}
void LTPopFront(LTNode* phead)
{
  assert(phead);
  assert(phead->next != phead);
  LTNode* del = phead->next;
  phead->next = del->next;
  del->next->prev = phead;
  free(del);
}
LTNode* LTFind(LTNode* phead, DataType x)
{
  assert(phead);
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  printf("nothing!\n");
  return NULL;
}
void LTInsert(LTNode* pos, DataType x)
{
  assert(pos);
  LTNode* newnode = Malloc(x);
  LTNode* posprev = pos->prev;
  posprev->next = newnode;
  newnode->prev = posprev;
  newnode->next = pos;
  pos->prev = newnode;
}
void LTErase(LTNode* pos)
{
  assert(pos);
  LTNode* posprev = pos->prev;
  LTNode* posnext = pos->next;
  posprev->next = posnext;
  posnext->prev = posprev;
  free(pos);
}
void LTDestroy(LTNode* phead)
{
  assert(phead);
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    LTNode* next = cur->next;
    free(cur);
    cur = next;
  }
  free(cur);
}

无头单向不循环链表和带头双向循环链表的创建

前言：

无头单向不循环链表

头文件：

Test文件：

函数源文件：

带头双向循环链表

头文件：

Test文件：

函数源文件：

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

无头单向不循环链表和带头双向循环链表的创建

前言：

无头单向不循环链表

头文件：

Test文件：

函数源文件：

带头双向循环链表

头文件：

Test文件：

函数源文件：

热门文章

最新文章

相关电子书