一、单链表结构
图示
代码实现
//结构 typedef int SLTDataType; struct SListNode { SLTDataType data; struct SListNode* next; }; typedef struct SListNode SLTNode;
二、函数接口
动态申请一个节点 BuySListNode
//插入时--动态申请一个节点 SLTNode* BuySListNode(SLTDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); //创建一个新的节点newnode newnode->data = x; //将要插入的数据放入该节点 newnode->next = NULL; //初始化该节点的next为NULL，因为只是申请，还没有具体使用 return newnode; //将新开辟出的节点返回 }
单链表打印 SListPrint
//单链表打印 void SListPrint(SLTNode* phead) { SLTNode* cur = phead; //phead是头指针，在main函数种创建，指向该链表第一个节点 while (cur != NULL) //cur指针用于链表遍历 { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); }
尾插 SListPushBack
//尾插 void SListPushBack(SLTNode** pphead, SLTDataType x) //二级指针，理解为传址调用即可 //若不用二级指针而用一级指针，无法做到在该函数体内改变main函数中我们创建的单链表 { SLTNode* newnode = BuySListNode(x); if (*pphead == NULL) { *pphead = newnode; } else { // 找尾节点的指针 SLTNode* tail = *pphead; while (tail->next != NULL) { tail = tail->next; } // 尾节点，链接新节点 tail->next = newnode; } }
头插 SListPushFront
//头插 void SListPushFront(SLTNode** pphead, SLTDataType x) { SLTNode* newnode = BuySListNode(x); newnode->next = *pphead; *pphead = newnode; }
尾删 SListPopBack
void SListPopBack(SLTNode** pphead) { if (*pphead == NULL) // 1、空 { return; } else if ((*pphead)->next == NULL) // 2、链表中只有一个节点时 { free(*pphead); *pphead = NULL; } else // 3、有一个以上的节点 { SLTNode* prev = NULL; SLTNode* tail = *pphead; while (tail->next != NULL) { prev = tail; tail = tail->next; } free(tail); prev->next = NULL; } }
头删 SListPopFront
//头删 void SListPopFront(SLTNode** pphead) { SLTNode* next = (*pphead)->next; free(*pphead); *pphead = next; }
查找 SListFind
//查找 SLTNode* SListFind(SLTNode* phead, SLTDataType x) { SListNode* cur = phead; //while (cur != NULL) while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }
任意位置（pos）前插入 SListInsert
// 在pos的前面插入x void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { if (pos == *pphead) { SListPushFront(pphead, x); } else { SLTNode* newnode = BuySListNode(x); SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = newnode; newnode->next = pos; } }
任意位置（pos）值删除 SListErase
// 删除pos位置的值 void SListErase(SLTNode** pphead, SLTNode* pos) { if (pos == *pphead) { SListPopFront(pphead); } else { SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); } }
三、整体实现
头文件 Slist.h
//头文件 Slist.h #pragma once #include <stdio.h> #include <stdlib.h> //结构 typedef int SLTDataType; struct SListNode { SLTDataType data; struct SListNode* next; }; typedef struct SListNode SLTNode; //插入之前开辟一个新的节点 SLTNode* BuySListNode(SLTDataType x); // 不会改变链表的头指针，传一级指针 void SListPrint(SLTNode* phead); // 可能会改变链表的头指针，传二级指针 void SListPushBack(SLTNode** pphead, SLTDataType x); void SListPushFront(SLTNode** pphead, SLTDataType x); void SListPopFront(SLTNode** pphead); void SListPopBack(SLTNode** pphead); SLTNode* SListFind(SLTNode* phead, SLTDataType x); // 在pos的前面插入x void SListInsert(SLTNode** phead, SLTNode* pos, SLTDataType x); // 删除pos位置的值 void SListErase(SLTNode** phead, SLTNode* pos); // 有些地方也有这样的 在pos的前面插入x //void SListInsert(SLTNode** phead, int i, SLTDataType x); 删除pos位置的值 //void SListErase(SLTNode** phead, int i);
源文件 Slist.c
// Slist.c #include "SList.h" //单链表打印 void SListPrint(SLTNode* phead) { SLTNode* cur = phead; while (cur != NULL) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); } //插入时--动态申请一个节点 SLTNode* BuySListNode(SLTDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); //创建一个新的节点newnode newnode->data = x; //将要插入的数据放入该节点 newnode->next = NULL; //初始化该节点的next为NULL，因为只是申请，还没有具体使用 return newnode; //将新开辟出的节点返回 } //尾插 void SListPushBack(SLTNode** pphead, SLTDataType 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 SListPushFront(SLTNode** pphead, SLTDataType x) { SLTNode* newnode = BuySListNode(x); newnode->next = *pphead; *pphead = newnode; } //头删 void SListPopFront(SLTNode** pphead) { SLTNode* next = (*pphead)->next; free(*pphead); *pphead = next; } //尾删 void SListPopBack(SLTNode** pphead) { if (*pphead == NULL) // 1、空 { return; } else if ((*pphead)->next == NULL) // 2、链表中只有一个节点时 { free(*pphead); *pphead = NULL; } else // 3、有一个以上的节点 { SLTNode* prev = NULL; SLTNode* tail = *pphead; while (tail->next != NULL) { prev = tail; tail = tail->next; } free(tail); prev->next = NULL; } } //查找 SLTNode* SListFind(SLTNode* phead, SLTDataType x) { SListNode* cur = phead; //while (cur != NULL) while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } // 在pos的前面插入x void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { if (pos == *pphead) { SListPushFront(pphead, x); } else { SLTNode* newnode = BuySListNode(x); SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = newnode; newnode->next = pos; } } // 删除pos位置的值 void SListErase(SLTNode** pphead, SLTNode* pos) { if (pos == *pphead) { SListPopFront(pphead); } else { SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); } }
四、使用
源文件 test.c
// test.c #include "SList.h" void TestSList1() { SLTNode* plist = NULL; SListPushBack(&plist, 1); SListPushBack(&plist, 2); SListPushBack(&plist, 3); SListPushBack(&plist, 4); SListPushFront(&plist, 0); SListPrint(plist); SListPopFront(&plist); SListPopFront(&plist); SListPopFront(&plist); SListPrint(plist); SListPopFront(&plist); SListPopFront(&plist); SListPrint(plist); } void TestSList2() { SLTNode* plist = NULL; SListPushBack(&plist, 1); SListPushBack(&plist, 2); SListPushBack(&plist, 3); SListPushBack(&plist, 4); SListPrint(plist); SListPopBack(&plist); SListPopBack(&plist); SListPopBack(&plist); SListPopBack(&plist); SListPopBack(&plist); SListPrint(plist); } void TestSList3() { SLTNode* plist = NULL; SListPushBack(&plist, 1); SListPushBack(&plist, 2); SListPushBack(&plist, 3); SListPushBack(&plist, 4); SListPrint(plist); // 想在3的前面插入一个30 SLTNode* pos = SListFind(plist, 1); if (pos) { SListInsert(&plist, pos, 10); } SListPrint(plist); pos = SListFind(plist, 3); if (pos) { SListInsert(&plist, pos, 30); } SListPrint(plist); } void TestSList4() { SLTNode* plist = NULL; SListPushBack(&plist, 1); SListPushBack(&plist, 2); SListPushBack(&plist, 3); SListPushBack(&plist, 4); SListPrint(plist); SLTNode* pos = SListFind(plist, 1); if (pos) { SListErase(&plist, pos); } SListPrint(plist); pos = SListFind(plist, 4); if (pos) { SListErase(&plist, pos); } SListPrint(plist); pos = SListFind(plist, 3); if (pos) { SListErase(&plist, pos); } SListPrint(plist); pos = SListFind(plist, 2); if (pos) { SListErase(&plist, pos); } SListPrint(plist); } int main() { TestSList4(); return 0; }
