单链表描述
链表在物理储存结构上是非连续的，它主要是通过指针指向下一个数据的。
节点都是动态开辟出来的。
我们把数据和指向下一个节点地址的指针叫做一个节点。
代码实现
创建节点
typedef int SLTypeDate; typedef struct SListNode { SLTypeDate date; struct SListNode* next; }SListNode;
增加节点
SListNode* BuySListNode(SLTypeDate x) { SListNode* NewNode = (SListNode*)malloc(sizeof(SListNode)); if (NewNode == NULL) exit(-1); NewNode->date = x; NewNode->next = NULL; return NewNode; }
链表数据的打印
void SListPrint(SListNode* phead) { while (phead) { printf("%d->", phead->date); phead = phead->next; } printf("NULL\n"); }
单链表的销毁
从头节点一个一个进行销毁
void SListDestory(SListNode** pphead) { assert(pphead); SListNode* cur =*pphead; while (cur) { cur = (*pphead)->next; free(*pphead); *pphead = cur; } }
头插
void SListPushFront(SListNode** pphead, SLTypeDate x) { assert(pphead); SListNode* NewNode=BuySListNode(x); SListNode* NewNode = (SListNode*)malloc(sizeof(SListNode)); if (NewNode == NULL) exit(-1); NewNode->date = x; NewNode->next = *pphead; *pphead = NewNode; }
尾插
尾插的时候也要注意没有节点的情况。
void SListPushBack(SListNode** pphead, SLTypeDate x) { assert(pphead); SListNode* NewNode = BuySListNode(x); if (*pphead == NULL) { *pphead = NewNode; } else { SListNode* tail = *pphead; while (tail->next) { tail = tail->next; } tail->next = NewNode; } }
尾删
需要判断节点为1，还有多个的情况
void SListPopBack(SListNode** pphead) { assert(*pphead); if ((*pphead)->next==NULL) { free(*pphead); *pphead = NULL; } else { SListNode* tail = *pphead; while (tail->next->next != NULL) { tail = tail->next; } free(tail->next); tail->next = NULL; } }
头删
先用临时变量储存起来头节点后面的节点
void SListPopFront(SListNode** pphead) { assert(*pphead); SListNode* cur = (*pphead)->next; free(*pphead); *pphead = cur; }
查找数据的位置
查找到返回改节点的地址，查找不到返回空指针
SListNode* SListFind(SListNode* phead, SLTypeDate x) { assert(phead); while (phead->date!=x) { phead = phead->next; if (phead == NULL) return NULL; } return phead; }
在查找位置之前插入
1.pos不能为空指针
2.注意在第一个节点前插的情况
void SListInsertPre(SListNode** pphead, SListNode* pos, SLTypeDate x) { assert(pphead); assert(pos); SListNode* NewNode = BuySListNode(x); if (pos==*pphead) { //NewNode->next = *pphead; //*pphead = NewNode; SListPushFront(pphead,x); } else { SListNode* cur = *pphead; while (cur->next != pos) { cur = cur->next; } NewNode->next = pos; cur->next = NewNode; } }
在查找位置之后插入
void SListInsertAfter(SListNode* pos, SLTypeDate x) { assert(pos); SListNode* NewNode = BuySListNode(x); NewNode->next = pos->next; pos->next = NewNode; }
删除查找位置的节点
void SListErase(SListNode** pphead, SListNode* pos) { assert(pphead); assert(pos); if (pos == *pphead) { //*pphead = (*pphead)->next; //free(pos); //pos = NULL; SListPopFront(pphead); } else { SListNode* cur = *pphead; while (cur->next != pos) { cur = cur->next; } cur->next = pos->next; free(pos); pos = NULL; } }
删除查找位置之后的节点
注意为最后一个节点的时候，不能进行删除
void SListEraseAfter(SListNode* pos) { assert(pos); if (pos->next == NULL) { return; } SListNode* cur = pos->next->next; free(pos->next); pos->next = cur; }
