目錄

鏈表的概念和結構

單鏈表的實現

申請新結點

打印

尾插

頭插

?尾刪

頭刪

??編輯

?查找

在pos位置前插入元素?

?在pos位置后插入元素

刪除pos位置的元素?

?刪除pos位置之后的位置的元素?編輯

完整代碼

SListNode.h

?

SListNode.c

---

鏈表的概念和結構

鏈表是一種物理存儲上非連續，非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的

鏈式結構邏輯連續，物理不一定連續

單鏈表的實現

無頭 單向 非循環鏈表

申請新結點

打印

尾插

?

頭插

?

?尾刪

?

頭刪

?

?

?查找

在pos位置前插入元素?

?????

?

?在pos位置后插入元素

刪除pos位置的元素?

?

?刪除pos位置之后的位置的元素

完整代碼

SListNode.h

?

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int SLTDataType;typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;SLTNode* BuySListNode(SLTDataType x);     //申請一個結點void SListNodePrint(SLTNode* plist);      //打印void SListPushBack(SLTNode** pplist, SLTDataType x);    //尾插void SListPushfront(SLTNode** pplist, SLTDataType x);    //頭插void SListPopBack(SLTNode** pplist);    //尾刪void SListPopfront(SLTNode** pplist);    //頭刪SLTNode* SListFind(SLTNode* plist, SLTDataType x);        //查找void SListInsert(SLTNode** pplist, SLTNode* pos, SLTDataType x);    //在pos位置前插入元素void SListInsertAfter(SLTNode* pos, SLTDataType x);   //在pos位置后插入元素void SListErase(SLTNode** pplist, SLTNode* pos);     //刪除pos位置前的元素void SListEraseAfter(SLTNode* pos);          //刪除pos位置之后的位置的元素

SListNode.c

#define _CRT_SECURE_NO_WARNINGS 1#include "SListNode.h"SLTNode* BuySListNode(SLTDataType x)            //申請一個新結點
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc failed");exit(-1);}newnode->data = x;newnode->next = NULL;return newnode;
}void SListNodePrint(SLTNode* plist)      //打印
{SLTNode* cur = plist;while (cur){printf(" %d ->", cur->data);cur = cur->next;}printf("NULL");printf("\n");
}void SListPushBack(SLTNode** pplist, SLTDataType x)    //尾插
{assert(pplist);SLTNode* newnode = BuySListNode(x);if (*pplist == NULL){*pplist = newnode;}else{SLTNode* tail = *pplist;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}void SListPushfront(SLTNode** pplist, SLTDataType x)    //頭插
{assert(pplist);SLTNode* newnode = BuySListNode(x);newnode->next = *pplist;*pplist = newnode;}void SListPopBack(SLTNode** pplist)    //尾刪
{assert(pplist);assert(*pplist);//空鏈表//一個結點if ((*pplist)->next == NULL){free(*pplist);*pplist = NULL;}//一個以上結點else{SLTNode* tail = *pplist;while (tail->next->next != NULL){tail = tail->next;}free(tail->next);tail->next = NULL;}
}void SListPopfront(SLTNode** pplist)    //頭刪
{assert(pplist);assert(*pplist);SLTNode* cur = *pplist;*pplist = (*pplist)->next;free(cur);
}SLTNode* SListFind(SLTNode* plist, SLTDataType x)        //查找
{SLTNode* cur = plist;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}void SListInsert(SLTNode** pplist, SLTNode* pos, SLTDataType x)    //在pos位置前插入元素
{assert(pplist);assert(pos);if (*pplist == pos){SListPopfront(pplist, x);}else{SLTNode* cur = *pplist;while (cur->next != pos){cur = cur->next;}SLTNode* newnode = BuySListNode(x);newnode->next = cur->next;cur->next = newnode;}
}void SListInsertAfter(SLTNode* pos, SLTDataType x)   //在pos位置后插入元素
{assert(pos);SLTNode* newnode = BuySListNode(x);newnode->next = pos->next;pos->next = newnode;
}void SListErase(SLTNode** pplist, SLTNode* pos)     //刪除pos位置的元素
{assert(pplist);assert(pos);if (*pplist == pos){SListPopfront(pplist);}else{SLTNode* cur = *pplist;while (cur->next->next = pos){cur = cur->next;}cur->next = pos->next;free(pos);pos = NULL;}
}void SListEraseAfter(SLTNode* pos)          //刪除pos位置之后的位置的元素
{assert(pos);assert(pos->next);SLTNode* cur = pos->next;pos->next = cur->next;free(cur);cur = NULL;
}