无头单向非循环单链表、带头双向循环链表

文章内容

1. 链表的概念及结构

2. 链表的分类

3.链表实现

4.代码

---

文章目录

1. 链表的概念及结构

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

 

 现实中 数据结构中

 链表和顺序表的区别

 

2. 链表的分类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

 2.1单向或者双向

 2.2 带头或者不带头

 2.3循环或者非循环

 虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

 1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结
构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都
是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带
来很多优势，实现反而简单了，后面我们代码实现了就知道了。

3.链表实现

3.1无头单向非循环单链表

1.主要功能

 2.接口实现

 

 

 

 

 

 

 

 

 

 

 

 

 以上就是链表每个接口的实现了！！！！

3.2带头双向循环链表

1.主要功能

在理解单链表的基础上，理解带头双向循环链表就简单很多了；

2.接口实现

 

 

 

 

 

 

 

 

 

 

 4.代码

 1.单链表

#pragma once#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int SLDataType;
typedef struct SListNode
{SLDataType data;struct SListNode* next;
}SLTNode;//打印链表
void SLTPrint(SLTNode* phead);//创建一个新节点
SLTNode* BuySListNode(SLDataType x);//尾插
void SLTPushBack(SLTNode** pphead, SLDataType x);//头插
void SLTPushFront(SLTNode** pphead, SLDataType x);//尾删
void SLTPopBack(SLTNode** pphead);//头删
void SLTPopFront(SLTNode** pphead);//寻找
SLTNode* SLTFind(SLTNode* phead, SLDataType x);// 在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDataType x);// 在pos以后插入x
void SLTInsertAfter(SLTNode* pos, SLDataType x);// 删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos);// 删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos);//销毁链表
void SLTDestroy(SLTNode** pphead);

#define _CRT_SECURE_NO_WARNINGS 1#include "SList.h"//打印链表
void SLTPrint(SLTNode* phead)
{SLTNode* cur = phead;while (cur){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}//创建一个新节点
SLTNode* BuySListNode(SLDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("BuySListNode fail");exit(-1);}newnode->data = x;newnode->next = NULL;return newnode;
}//尾插
void SLTPushBack(SLTNode** pphead, SLDataType x)
{SLTNode* newnode = BuySListNode(x);if (*pphead == NULL){//改变指向结构体的指针，所以要用二级指针*pphead = newnode;}else{SLTNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}//改变结构体，用结构体指针tail->next = newnode;}
}//头插
void SLTPushFront(SLTNode** pphead, SLDataType x)
{SLTNode* newnode = BuySListNode(x);newnode->next = *pphead;*pphead = newnode;}//尾删
void SLTPopBack(SLTNode** pphead)
{//空assert(*pphead);//一个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}//一个以上节点SLTNode* tail = *pphead;while (tail->next->next != NULL){tail = tail->next;}free(tail->next);tail->next = NULL;}//头删
void SLTPopFront(SLTNode** pphead)
{//kongassert(*pphead);//非空SLTNode* newnode = (*pphead)->next;free(*pphead);*pphead = newnode;}//寻找
SLTNode* SLTFind(SLTNode* phead, SLDataType x)
{assert(phead);while (phead){if (phead->data == x){return phead;}phead = phead->next;}return NULL;
}// 在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDataType x)
{assert(pphead);assert(pos);//头插if (*pphead == pos){SLTPushFront(pphead,x);return;}SLTNode* prev = *pphead;SLTNode* newnode = BuySListNode(x);while(prev){if (prev->next == pos){prev->next = newnode;newnode->next = pos;return;}else{prev = prev->next;}}
}// 在pos以后插入x
void SLTInsertAfter(SLTNode* pos, SLDataType x)
{assert(pos);SLTNode* newnode = BuySListNode(x);newnode->next = pos->next;pos->next = newnode;}//SLTNode*  posafter = pos->next;
//pos->next = newnode;
//newnode->next = posafter;// 删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(*pphead);assert(pos);if (*pphead == pos){SLTPopFront(pphead);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);}}// 删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos)
{assert(pos);//检查尾节点assert(pos->next);SLTNode* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;
}//销毁链表
void SLTDestroy(SLTNode** pphead)
{assert(pphead);SLTNode* cur = *pphead;while (cur){SLTNode* next = cur;next = cur->next;free(cur);cur = next;}*pphead = NULL;
}

 

2.双向链表

#pragma once#include <stdio.h>
#include <assert.h>
#include <stdlib.h>typedef int LTDataTpye;typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataTpye data;}LTNode;//创建新节点
LTNode* BuyLTnode(LTDataTpye x);//初始化
LTNode* LTInit();//打印链表
void LTPrint(LTNode* phead);//头插
void LTPushFront(LTNode* phead, LTDataTpye x);//头删
void LTPopFront(LTNode* phead);//尾插
void LTPushBack(LTNode* phead, LTDataTpye x);//尾删
void LTPopBack(LTNode* phead);//寻找
LTNode* LTFind(LTNode* phead, LTDataTpye x);//在pos之前插入
void LTInsert(LTNode* pos, LTDataTpye x);//消除pos位置的元素
void LTErase(LTNode* pos);//销毁链表
void LTDestroy(LTNode* phead);

#define _CRT_SECURE_NO_WARNINGS 1
#include "DList.h"//创建新节点
LTNode* BuyLTnode(LTDataTpye x)
{LTNode* node = (LTNode *)malloc(sizeof(LTNode));if (node == NULL){perror("BuyLTNode");exit(-1);}node->data = x;node->prev = NULL;node->next= NULL;return node;
}//初始化
LTNode* LTInit()
{LTNode* phead = BuyLTnode(0);phead->next = phead;phead->prev = phead;return phead;
}//打印链表
void LTPrint(LTNode* phead)
{assert(phead);printf("phead<=>");LTNode* cur = phead->next;while (cur!= phead){printf("%d<=>",cur->data);cur = cur->next;}printf("\n");
}//头插
void LTPushFront(LTNode* phead, LTDataTpye x)
{assert(phead);LTNode* newnode = BuyLTnode( x);LTNode* after = phead->next;phead->next = newnode;newnode->prev = phead;newnode->next = after;after->prev = newnode;}//头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(phead->next != phead);LTNode* first = phead->next;LTNode* second = first->next;free(first);phead->next = second;second->prev = phead;}//尾插
void LTPushBack(LTNode* phead, LTDataTpye x)
{assert(phead);LTNode* newnode = BuyLTnode(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* first = tail->prev;free(tail);first->next = phead;phead->prev = first;}//寻找
LTNode* LTFind(LTNode* phead, LTDataTpye x)
{assert(phead);LTNode* cur = phead->next;while (cur !=phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}//在pos之前插入
void LTInsert(LTNode* pos, LTDataTpye x)
{assert(pos);LTNode* first = pos->prev;LTNode* newnode = BuyLTnode(x);first->next = newnode;newnode->prev = first;pos->prev = newnode;newnode->next = pos;}//消除pos位置的元素
void LTErase(LTNode* pos)
{assert(pos);LTNode* posprev = pos->prev;LTNode* posafter = pos->next;free(pos);posprev->next = posafter;posafter->prev = posprev;}//销毁链表
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != (phead)){LTNode* cur1 = cur;cur = cur->next;free(cur1);}free(phead);phead == NULL;}