数据结构3—单链表（附源码）

1.概念与结构

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

结构：由一个个结点构成，每个结点是一个结构体（里面包含了数据域和指针域，其中指针域存储的是下一个结点的地址）

2.源代码

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>//定义链表(结点)的结构typedef int SLTDataType;typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;void SLTPrint(SLTNode* phead);//打印链表SLTNode* SLTBuyNode(SLTDataType x);//创建结点void SLTPushBack(SLTNode** pphead,SLTDataType x);//尾插法void SLTPushFront(SLTNode** pphead, SLTDataType x);//头插法void SLTPopBack(SLTNode** pphead);//尾删法void SLTPopFront(SLTNode** pphead);//头删法SLTNode* SLTFind(SLTNode* phead, SLTDataType x);//查找void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//在pos前插入数据void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x);//在pos后插入数据void SLTErase(SLTNode** pphead, SLTNode* pos);//删除pos结点void SLTEraseAfter(SLTNode* pos);//删除pos的下一个结点void SListDestroy(SLTNode** pphead);//销毁链表

void SLTPrint(SLTNode* phead)
{SLTNode* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL");
}

SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* Node = (SLTNode*)malloc(sizeof(SLTNode));if (Node == NULL){perror("malloc fail!");exit(1);}Node->data = x;Node->next = NULL;return Node;
}

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* NewNode=SLTBuyNode(x);if (*pphead == NULL){*pphead = NewNode;}else{SLTNode* pcur = *pphead;while (pcur->next){pcur = pcur->next;}pcur->next = NewNode;}
}

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* NewNode = SLTBuyNode(x);NewNode->next = *pphead;*pphead = NewNode;
}

void SLTPopBack(SLTNode** pphead)
{assert(pphead && *pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* ptail = *pphead;SLTNode* prev = *pphead;while (ptail->next){prev = ptail;ptail = ptail->next;}prev->next = NULL;free(ptail);ptail->next = NULL;}
}

void SLTPopFront(SLTNode** pphead)
{assert(pphead && *pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;}
}

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{assert(phead);SLTNode* pcur = phead;int count = 1;while (pcur){if (pcur->data == x){return pcur;}else {pcur = pcur->next;}}return NULL;
}

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);SLTNode* InsertData=SLTBuyNode(x);SLTNode* prev = *pphead;if (pos == *pphead){SLTPushFront(pphead,x);}else {while (prev->next != pos){prev = prev->next;}InsertData->next = pos;prev->next = InsertData;}
}

void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);SLTNode* InsertData = SLTBuyNode(x);SLTNode* prev = *pphead;if (pos == *pphead){SLTPushFront(pphead, x);}else{while (prev != pos){prev = prev->next;}prev = prev->next;pos->next = InsertData;InsertData->next = prev;}
}

void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && *pphead);assert(pos);SLTNode* prev = *pphead;if (pos == *pphead){SLTPopFront(pphead);}else{while (prev->next != pos){prev = prev->next;}prev->next = prev->next->next;free(pos);pos = NULL;}
}

void SLTEraseAfter(SLTNode* pos)
{assert(pos);SLTNode* del = pos->next;pos->next= del->next;free(del);del = NULL;
}

void SListDestroy(SLTNode** pphead)
{assert(*pphead && pphead);SLTNode* prev = *pphead;while (prev){SLTNode* next= prev->next;free(prev);prev=next;}*pphead = NULL;
}

3.测试部分

void CreatSList()
{//链表是由一个个的结点构成SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));node1->data = 1;SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));node2->data = 2;SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));node3->data = 3;SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));node4->data = 4;node1->next = node2;node2->next = node3;node3->next = node4;node4->next = NULL;SLTNode* pList = node1;SLTPushBack(&pList,5);SLTPushFront(&pList, 0);//SLTPopBack(&pList);//SLTPopFront(&pList);SLTInsert(&pList,node3,11);SLTInsertAfter(&pList, node3, 22);//查找SLTNode* find = SLTFind(pList, 3);SLTErase(&pList, find);//打印链表SLTPrint(pList);SListDestroy(&pList);
}int main()
{CreatSList();return 0;
}