1.链表的分类
实际中链表的结构非常多样,以下情况组合起来就有8种链表结构:
(1)单向或者双向
(2)带头或者不带头
(3)循环或者非循环
虽然有这么多的链表的结构,但是我们实际中最常用还是两种结构:
1. 无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。
2. 带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。
2.无头单向非循环链表的实现
文章来源:https://www.toymoban.com/news/detail-638283.html
// 1、无头+单向+非循环链表增删查改实现
typedef int SLTDateType;
typedef struct SListNode
{
SLTDateType data;
struct SListNode* next;
}SListNode;
// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos);
// 1、无头+单向+非循环链表增删查改实现
SListNode* BuySListNode(SLTDateType x)
{
SListNode* tmp = (SListNode*)malloc(sizeof(SListNode));
if (tmp == NULL)
{
printf("无法给节点开辟空间\n");
return NULL;
}
else
{
tmp->data = x;
tmp->next = NULL;
return tmp;
}
}
// 单链表打印
void SListPrint(SListNode* plist)
{
SListNode* head = plist;
while (head != NULL)
{
printf("%d ", head->data);
head = head->next;
}
}
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
SListNode* newnode = BuySListNode(x);
if ( *pplist== NULL)
{
*pplist = newnode;
}
else
{
SListNode* tail = *pplist;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
// 单链表的尾删
void SListPopBack(SListNode** pplist)
{
assert(*pplist);
SListNode* cur = *pplist;
SListNode* prev = NULL;
if (cur->next == NULL)
{
free(cur);
*pplist = NULL;
}
else
{
while (cur->next != NULL)
{
prev = cur;
cur = cur->next;
}
free(cur);
prev->next = NULL;
}
}
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
SListNode* newnode = BuySListNode(x);
if (*pplist == NULL)
{
*pplist = newnode;
}
else
{
newnode->next = *pplist;
*pplist = newnode;
}
}
// 单链表头删
void SListPopFront(SListNode** pplist)
{
assert(*pplist);
SListNode* cur = *pplist;
if ((*pplist)->next == NULL)
{
free(*pplist);
*pplist = NULL;
}
else
{
cur = cur->next;
free(*pplist);
*pplist = cur;
}
}
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
assert(plist);
while (plist != NULL)
{
if (plist->data == x)
{
return plist;
}
plist = plist->next;
}
return NULL;
}
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
assert(pos);
SListNode* newnode = BuySListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos)
{
assert(pos);
if (pos->next == NULL)
{
printf("后面无数据\n");
return;
}
else
{
SListNode* prev = pos;
SListNode* cur = pos->next;
prev->next = cur->next;
free(cur);
cur = NULL;
}
}
3. 带头双向循环链表
文章来源地址https://www.toymoban.com/news/detail-638283.html
// 2、带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{
ListDateType val;
struct ListNode* prev;
struct ListNode* next;
}ListNode;
//初始化双向链表
ListNode* ListInit(ListNode* phead);
//双向链表打印
void ListPrint(ListNode* phead);
// 创建返回链表的头结点.
ListNode* BuyList(ListDateType x);
//双向链表尾插
void ListPushBack(ListNode* phead,ListDateType x);
//双向链表尾删
void ListPopBack(ListNode* phead);
//双向链表头插
void ListPushFront(ListNode* phead, ListDateType x);
//双向链表头删
void ListPopFront(ListNode* phead);
//双向链表查找
ListNode* ListFind(ListNode* pHead, ListDateType x);
//在pos之前插入
void ListInsert(ListNode* pos, ListDateType x);
//删除pos位置
void ListErase(ListNode* pos);
//初始化双向链表
ListNode* ListInit(ListNode* phead)
{
phead = BuyList(0);
phead->next = phead;
phead->prev = phead;
return phead;
}
//双向链表打印
void ListPrint(ListNode* phead)
{
ListNode* cur = phead->next;
while (cur != phead)
{
printf("%d ", cur->val);
cur = cur->next;
}
}
// 创建返回链表的头结点
ListNode* BuyList(ListDateType x)
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
if (newnode == NULL)
{
printf("BuyList fail\n");
exit(-1);
}
newnode->val = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
//双向链表尾插
void ListPushBack(ListNode* phead, ListDateType x)
{
assert(phead);
ListNode* newnode = BuyList(x);
ListNode* tail = phead->prev;
tail->next = newnode;
phead->prev = newnode;
newnode->next = phead;
newnode->prev = tail;
}
//双向链表尾删
void ListPopBack(ListNode* phead)
{
assert(phead->next != phead);
ListNode* tail = phead->prev;
ListNode* prev = tail->prev;
phead->prev = prev;
prev->next = phead;
free(tail);
tail = NULL;
}
//双向链表头插
void ListPushFront(ListNode* phead, ListDateType x)
{
assert(phead);
ListNode* newnode = BuyList(x);
ListNode* head = phead->next;
phead->next = newnode;
head->prev = newnode;
newnode->next = head;
newnode->prev = phead;
}
//双向链表头删
void ListPopFront(ListNode* phead)
{
assert(phead);
assert(phead->next != phead);
ListNode* head = phead->next;
ListNode* next = head->next;
phead->next = next;
next->prev = phead;
free(head);
head = NULL;
}
//双向链表查找
ListNode* ListFind(ListNode* phead, ListDateType x)
{
assert(phead);
assert(phead->next != phead);
ListNode* pos = phead->next;
while (pos != phead)
{
if (pos->val == x)
{
return pos;
}
pos = pos->next;
}
return NULL;
}
//在pos之前插入
void ListInsert(ListNode* pos, ListDateType x)
{
assert(pos);
ListNode* newnode = BuyList(x);
ListNode* prev = pos->prev;
prev->next = newnode;
pos->prev = newnode;
newnode->prev = prev;
newnode->next = pos;
}
//删除pos位置
void ListErase(ListNode* pos)
{
assert(pos);
ListNode* prev = pos->prev;
ListNode* next = pos->next;
prev->next = next;
next->prev = prev;
free(pos);
pos = NULL;
}
到了这里,关于链表(c语言实现)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!