当前位置：首页 > news >正文

手搓单链表（无哨兵位）（C语言）

news 2025/7/2 6:02:35

SLT.h

SLT.c

SLTtest.c

测试示例

单链表优劣分析

SLT.h

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

SLT.c

#include "SLT.h"//打印单链表
void SLTPrint(SLTNode* phead)
{SLTNode* cur = phead;while (cur){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}//创建节点
SLTNode* BuySLTNode(SLTDataType x)
{SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));if (node == NULL){perror("SLTBuysNode");exit(-1);}node->data = x;node->next = NULL;return node;
}//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);if (*pphead == NULL){*pphead = BuySLTNode(x);}else{SLTNode* tail = *pphead;while (tail->next){tail = tail->next;}tail->next = BuySLTNode(x);}
}//尾删
void SLTPopBack(SLTNode** pphead)
{assert(pphead);assert(*pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* tail = *pphead;while (tail->next->next){tail = tail->next;}free(tail->next->next);tail->next = NULL;}
}//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuySLTNode(x);newnode->next = *pphead;*pphead = newnode;
}//头删
void SLTPopFront(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* newhead = (*pphead)->next;free(*pphead);*pphead = newhead;
}// 单链表查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;while (cur){if (cur->data == x){//找到了return cur;}cur = cur->next;}//找不到return NULL;
}//在pos之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);if (*pphead == pos){SLTNode* newnode = BuySLTNode(x);newnode->next = *pphead;*pphead = newnode;}else{SLTNode* cur = *pphead;while (cur->next != pos){cur = cur->next;}SLTNode* newnode = BuySLTNode(x);cur->next = newnode;newnode->next = pos;}}// 删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(*pphead && pos);if (*pphead == pos){SLTNode* newhead = (*pphead)->next;free(*pphead);*pphead = newhead;}else{SLTNode* cur = *pphead;while (cur->next != pos){cur = cur->next;}SLTNode* pos_next = pos->next;free(pos);cur->next = pos_next;}}// 单链表在pos位置之后插入x
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = BuySLTNode(x);newnode->next = pos->next;pos->next = newnode;
}// 单链表删除pos位置之后的值
void SListEraseAfter(SLTNode* pos)
{assert(pos && pos->next);SLTNode* pos_next_next = pos->next->next;free(pos->next);pos->next = pos_next_next;
}//销毁单链表
void SLTDestroy(SLTNode** pphead)
{assert(pphead);assert(*pphead);while (*pphead){SLTNode* newhead = (*pphead)->next;free(*pphead);*pphead = newhead;}
}

SLTtest.c

#include "SLT.h"void SLTtest1()
{SLTNode* phead = NULL;SLTPrint(phead);SLTPushBack(&phead, 1);SLTPushBack(&phead, 2);SLTPushBack(&phead, 3);SLTPushBack(&phead, 4);SLTPushBack(&phead, 5);SLTPrint(phead);SLTPopBack(&phead);SLTPrint(phead);SLTPopBack(&phead);SLTPrint(phead);SLTPopBack(&phead);SLTPrint(phead);SLTPopBack(&phead);SLTPrint(phead);SLTPopBack(&phead);SLTPrint(phead);/*SLTPopBack(&phead);SLTPrint(phead);*/
}
void SLTtest2()
{SLTNode* phead = NULL;SLTPrint(phead);SLTPushFront(&phead, 1);SLTPushFront(&phead, 2);SLTPushFront(&phead, 3);SLTPushFront(&phead, 4);SLTPushFront(&phead, 5);SLTPrint(phead);/*SLTDestroy(&phead);SLTPrint(phead);*//*SLTPopFront(&phead);SLTPrint(phead);SLTPopFront(&phead);SLTPrint(phead);SLTPopFront(&phead);SLTPrint(phead);SLTPopFront(&phead);SLTPrint(phead);SLTPopFront(&phead);SLTPrint(phead);*//*SLTPopFront(&phead);SLTPrint(phead);*/
}
void SLTtest3()
{SLTNode* phead = NULL;SLTPrint(phead);SLTPushFront(&phead, 1);SLTPushFront(&phead, 2);SLTPushFront(&phead, 3);SLTPushFront(&phead, 4);SLTPushFront(&phead, 5);SLTPrint(phead);//在pos位置之前插入删除SLTInsert(&phead, phead, 10);SLTPrint(phead);SLTInsert(&phead, NULL, 20);SLTPrint(phead);SLTNode* pos = SLTFind(phead, 3);SLTInsert(&phead, pos, 30);SLTPrint(phead);//删除pos位置的值SLTErase(&phead, phead);SLTPrint(phead);pos = SLTFind(phead, 3);SLTErase(&phead, pos);SLTPrint(phead);pos = SLTFind(phead, 20);SLTErase(&phead, pos);SLTPrint(phead);
}void SLTtest4()
{SLTNode* phead = NULL;SLTPrint(phead);SLTPushFront(&phead, 1);SLTPushFront(&phead, 2);SLTPushFront(&phead, 3);SLTPushFront(&phead, 4);SLTPushFront(&phead, 5);SLTPrint(phead);//在pos位置之后插入SListInsertAfter(phead, 10);SLTPrint(phead);SLTNode* pos = SLTFind(phead, 3);SListInsertAfter(pos, 30);SLTPrint(phead);pos = SLTFind(phead, 1);SListInsertAfter(pos, 10);SLTPrint(phead);//删除pos位置之后的值SListEraseAfter(phead);SLTPrint(phead);pos = SLTFind(phead, 4);SListEraseAfter(pos);SLTPrint(phead);}
int main()
{//测试尾插尾删//SLTtest1();//测试头插头删//SLTtest2();//在pos位置之前插入删除//SLTtest3();//在pos位置之后插入删除//SLTtest4();return 0;
}

测试示例

尾插尾删：

头插头删：

在pos位置之前插入：

删除pos位置的值：

在pos位置之后插入删除：

单链表优劣分析

单链表在逻辑上连续，在物理上不一定连续，用多少申请多少空间，因此不存在空间浪费且申请空间开销小；插入删除元素时无需挪动元素，只需要改变指向即可，但除头插头删，在pos位置之后插入删除外需要先遍历链表，效率低下；不支持随机访问；缓存利用率低。

总结：单链表具有较大的缺陷，相较于顺序表而言没有明显的优势，因此在实践中几乎没有应用场景。

查看全文

http://www.lryc.cn/news/362825.html