尾部插入
先建立一个新的节点
分为俩种情况，第一种头节点指向空，第二种头节点指向不为空
第一种情况：头节点为空，建立新的节点后，直接让头节点指向新节点
第二种情况，头节点不为空，创建一个跟节点类型相同的结构体变量，然后让这个变量指向头节点，之后检查后面的每个节点，若有一个节点为的next为空，则在此处插入新节点
tail发现这个节点的next指向为空，然后让这个节点的next指向下一个节点的地址，随着程序的结束tail也会随之消失
void SListpushback(SLTNode** pphead, SLTDataType x) { //pphead不可能为空，pphead是plist的地址，pphead永远不为空 //1.链表为空 SLTNode* newnode = BuySLTnode(x); if (*pphead == NULL) { *pphead = newnode; } //2.不为空 else { SLTNode* tail = *pphead; while (tail->next != NULL) { tail =tail->next; } tail->next = newnode; } }
频繁的malloc会使效率降低
头部节点删除
void SListpopfront(SLTNode** pphead)//头删 { SLTNode* del = *pphead; *pphead = (*pphead)->next; free(del);//删除第一个节点 del = NULL; }
当全部删完后，plist指向NULL，此时就不能再删了。程序会崩溃，此时plsit为空，（*pphead）->next也为空，del也为空，因此加一个检查条件
void SListpopfront(SLTNode** pphead)//头删 { if（*pphead==NULL） { return; } SLTNode* del = *pphead; *pphead = (*pphead)->next; free(del);//删除第一个节点 del = NULL; }
或
void SListpopfront(SLTNode** pphead)//头删 { assert(*pphead！=NULL)； SLTNode* del = *pphead; *pphead = (*pphead)->next; free(del);//删除第一个节点 del = NULL; }
尾部节点删除
要判断尾部有一个节点还是多个节点甚至没有节点
当tail->next为空，删除该节点，然后让前一个节点指向NULL
void SListpopback(SLTNode** pphead) { if(*pphead==NULL) return; if((*pphead)->next==NULL) { free(*pphead); *pphead=NULL; } else { SLTNode* prev = NULL; SLTNode* tail = *pphead; while (tail->next!= NULL) { prev = tail; tail = tail->next; } prev->next = NULL; free(tail); tail = NULL; } }
或
void SListpopback(SLTNode** pphead) { if(*pphead==NULL) return; if((*pphead)->next==NULL) { free(*pphead); *pphead=NULL; } else { SLTNode* tail = *pphead; while (tail->next->next!= NULL) { tail = tail->next; } free(tail->next); tail->next = NULL; } }
节点的销毁
释放掉cur,cur=next ，不断往下走，最后把头节点置空
void SListDestory(SLTNode** pphead)//用二级指针会更好 { SLTNode* cur = *pphead; while (cur) { SLTNode* next = cur->next; free(cur); cur = next; } *pphead = NULL; }
链表查找
SLTNode *SListFind(SLTNode** pphead, SLTDataType x) { SLTNode* cur = *pphead; while (cur != NULL) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }
挨个查找。
随即插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { assert(pos); if (pos == *pphead) { SListpushfront(pphead, x); } else { SLTNode* prve = *pphead; while (prve->next != pos) { prve = prve->next; assert(prve);//找不到 } SLTNode* newnode = BuySLTnode(x); prve->next = newnode; newnode->next = pos; } }
从一个数的前面插入，若果头插则用头插函数
后插
void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x) { SLTNode* newnode = BuySLTnode(x); newnode->next = pos->next; pos->next = newnode; }
删除某节点前面的节点
void SlistErase(SLTNode** pphead, SLTNode* pos) { assert(pos); if (*pphead == pos) { SListpopfront(pphead); }//如果是头删，用头删函数 else { SLTNode* prev = *pphead; if (prev->next != pos) { prev = prev->next; assert(prev);//判断pos是否属于本链表 } prev->next = pos->next; free(pos); pos = NULL; } }
删除某节点后面的节点
void SlistEraseAfter(SLTNode** pphead, SLTNode* pos) { assert(pos); if (pos->next == NULL) return; else { SLTNode* prev = *pphead; prev = pos->next; pos->next = prev->next; free(prev); prev = NULL; } }
单链表缺陷
单链表只适合头插头删，O(1)。
替换法删除节点
删除某个节点，要求是O(1)
把2所在节点删除，可采用以下方法， 我们把2，3进行交换
然后让3指向4
缺陷：所删节点不能是尾节点，尾节点后面是空的，无法交换
思路延申
在pos之前插入，要求是O(1)
我们不在之前插入，在之后进行插入
然后交换值
