龙岗网站建设流程,选择seo网站排名优化,网站后缀意思,188建站系统源码3.3 链表的实现 3.3.1头插 原理图#xff1a; newnode为新创建的节点 实现#xff1a; //头插
//让新节点指向原来的头指针#xff08;节点#xff09;#xff0c;即新节点位于开头
newnode-next plist;
//再让头指针#xff08;节点#xff09;指向新节点#… 3.3 链表的实现 3.3.1头插 原理图 newnode为新创建的节点 实现 //头插
//让新节点指向原来的头指针节点即新节点位于开头
newnode-next plist;
//再让头指针节点指向新节点新节点就成为了头节点
plist newnode; 此操作在链表为空的情况下也能正常运行。 3.3.2尾插 原理创建一个新节点先通过局部变量 tail 遍历找到指向的下一个节点为空的节点即倒数第二个节点然后将该节点与新节点链接起来。 初步实现 // 单链表尾插
//第一个参数为头指针的拷贝形参
void SListPushBack(SLTNode* phead, SLTDataType x)
{SLTNode* tail phead;//创建要插入的新节点SLTNode* newnode BuySListNode(x);//遍历下一个节点指向为空的节点while (tail-next ! NULL){tail tail-next;}//将该节点与新节点链接起来tail-next newnode;
} phead,tail,newnode为局部变量出了作用域就会自动销毁而链表的节点存在于堆上不会自动销毁。 上面的步骤是在原有链表的前提下进行的如果链表为空呢 需要让新节点充当头节点也就是要让 plist结构体指针头指针 指向新节点,因此我们尝试将新创建的节点赋给头指针
if (phead NULL){phead newnode;}
但这个做法对吗显然不对形参是实参的一份临时拷贝改变形参不影响实参出了这个作用域这两个指针就销毁了plist也没有改变。
plist 是结构体类型的指针要改变它的值在函数中就需要传它的地址也就是指针的地址。
//第一个参数为头指针的拷贝形参
void SListPushBack(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode BuySListNode(x);//如果链表为空//*ppheadplistif (*pphead NULL){*pphead newnode;}else{SLTNode* tail *pphead;//创建要插入的新节点//遍历下一个节点指向为空的节点while (tail-next ! NULL){tail tail-next;}//将该节点与新节点链接起来tail-next newnode;}
} 总结 改变结构体用结构体指针 改变结构体指针用结构体二级指针 3.3.3头插
本篇开头已经在函数外实现过了现在在函数中实现一次。
每一次头插都要改变 plist 头指针因此也需要传二重指针 // 单链表的头插
void SListPushFront(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode BuySListNode(x);newnode-next *pphead;*pphead newnode;
}
3.3.4尾删
根据剩余节点的不同分3种情况
1.链表为空
这是一种异常的情况我们需要使用断言对参数加以限制以防传空指针情况的出现。 assert(*pphead); 2.链表只剩一个节点
再删掉就为空这时候就需要释放节点的空间并将头指针置空就涉及到了头指针的改变需要引用二级指针。 if ((*pphead)-next NULL) { free(*pphead); *pphead NULL; } 3.链表中包含1个节点
用 tail 找到末尾节点并将其删除将倒数第二个节点置空该情况下不需要二级指针。
原理图 SLTNode* tailPre NULL; SLTNode* tail *pphead; while (tail-next ! NULL) { tailPre tail; tail tail-next; } free(tail); tailPre-next NULL; 3.3.5头删
让头指针指向第二个节点将第一个节点释放。 // 单链表头删
void SListPopFront(SLTNode** pphead)
{assert(*pphead);//第二个节点SLTNode* newhead (*pphead)-next;//释放第一个节点free(*pphead);//让第二个节点成为新的头节点*pphead newhead;
}
3.3.6查找
在链表中查找值 x 从头遍历一遍即可遇到空节点停止。
// 单链表查找
SLTNode* SListFind(SLTNode* plist, SLTDataType x)
{SLTNode* cur plist;while (cur){//找到了就返回地址if (cur-data x){return cur;}cur cur-next;}//遍历完了还没找到return NULL;
}
3.3.7 在pos之前插入X,pos为节点的指针
根据插入的位置分在第一个节点之前插入头插和其余的正常插入
头插由于我们之前写过头插这里我们可以直接复用需要注意参数的传递和头插函数的参数保持一致即我们需要改变的是头指针 plist因此传它的地址二级指针
正常插入单链表的在某节点之前插入相对双链表是比较麻烦的我们需要先通过遍历找到 pos 之前节点的指针 prev即 prev-nextpos然后再将代插入的节点和 prev 以及 pos 链接起来。 //在pos之前插入X,pos为节点的指针
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{//pos不能为空assert(pos);//如果为头插if (pos *pphead){SLTPushFront(pphead, x);}else{SLTNode* prev *pphead;while (prev-next pos){prev prev-next;}//待插入的新节点SLTNode* newnode BuySLTNode(x);prev-next newnode;newnode-next pos;}
}
3.3.8 在pos之后插入X 相比在 pos 前插入就容易多了直接将待插入的新节点和 pos 以及 pos 后面的节点 pos-next 链接起来即可链接的时候需要注意顺序先链接后者再链接前者否则 pos-next 就被新节点覆盖找不到了。 //在pos之后插入X
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode BuySLTNode(x);//先链接新节点与pos之后的节点newnode-next pos-next;//再链接pos与新节点pos-next newnode;
} 3.3.9 删除pos位置的值
仅仅头删比较特别需要将目标节点释放掉让头指针指向下一个节点。
其余情况下先遍历找到上一个节点 prev然后释放掉 pos 节点让 prev 指向下一个节点。 //删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pos);//如果pos为头节点if (pos *pphead){//直接复用参数为二级指针SLTPopFront(pphead);}else{SLTNode* prev *pphead;while (prev-next pos){prev prev-next;}prev-next pos-next;free(pos);}
}
3.3.10 删除 pos 的下一个 这个方法不能删除头节点也不能删除尾节点。 //删除pos的后一个
void SLTEraseAfter(SLTNode* pos)
{assert(pos);//不能删尾assert(pos-next);//将pos的下一个节点保存下来SLTNode* posNext pos-next;//将pos和下下个节点链接起来pos-next posNext-next;//释放pos的下一个节点free(posNext);
}
3.3.11 顺序表的销毁
依旧使用一个 cur 指针来遍历在释放节点的时候有两种方式
创建一个 next 指针来指向下一个节点然后释放 cur再让 cur 指向 next 记录前一个节点 del cur 移动到后一个节点之后释放 del // 顺序表销毁
void SLTDestory(SLTNode** pphead)
{assert(pphead);SLTNode* cur *pphead;while (cur){SLTNode* next cur-next;free(cur);cur next;}//销毁完毕将头指针置空*pphead NULL;
}例题
给定一个无头单链表要求删除 pos 位置的节点该如何实现 常规的方法行不通我们需要另辟蹊径 即用替换法将 pos 下一个节点的值赋给 pos 然后删除下一个节点不过该方法存在一个缺陷是无法用来删除尾节点。 完整代码
头文件
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h
typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;
//打印链表
void SLTPrint(SLTNode* pahead);
//开辟一个节点并赋值
SLTNode* BuySLTNode(SLTDataType X);
// 单链表尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
// 单链表的头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);
// 单链表的尾删
void SLTPopBack(SLTNode** pphead);
// 单链表头删
void SLTPopFront(SLTNode** pphead);
//在pos之前插入X,pos为节点的指针
void SLTInsert(SLTNode** pphead, SLTNode* pos,SLTDataType x);
//在pos之后插入X
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos的后一个
void SLTEraseAfter(SLTNode* pos);
// 单链表查找
SLTNode* SLTFind(SLTNode* plist, SLTDataType x);
// 顺序表销毁
void SLTDestory(SLTNode** pphead); 测试文件
#define _CRT_SECURE_NO_WARNINGS 1
#includeSList.h
void TestSList1()
{int n 0;printf(请输入链表的长度\n);scanf(%d, n);printf(请依次输入每个节点的值\n);//创建头指针SLTNode* plist NULL;for (int i 0; i n; i){int val 0;scanf(%d, val);//开辟新节点SLTNode* newnode BuySLTNode(val);//头插//让新节点指向原来的头指针节点即新节点位于开头newnode-next plist;//再让头指针节点指向新节点新节点就成为了头节点plist newnode;}SLTPushBack(plist, 100);SLTPrint(plist);
}
void TestSList2()
{SLTNode* plist NULL;SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPushBack(plist, 5);SLTPrint(plist);SLTPushFront(plist, 10);SLTPushFront(plist, 20);SLTPushFront(plist, 30);SLTPushFront(plist, 40);SLTPrint(plist);
}
void TestSList3()
{SLTNode* plist NULL;SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPushBack(plist, 5);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);// SLTPopBack(plist);// SLTPrint(plist);
}
void TestSList4()
{SLTNode* plist NULL;SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPushBack(plist, 5);SLTPrint(plist);SLTPopFront(plist);SLTPrint(plist);SLTPopFront(plist);SLTPrint(plist);SLTPopFront(plist);SLTPrint(plist);SLTPopFront(plist);SLTPrint(plist);SLTPopFront(plist);//SLTPopFront(plist);SLTPrint(plist);
}
void TestSList5()
{SLTNode* plist NULL;SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPushBack(plist, 5);SLTPrint(plist);SLTNode* pos SLTFind(plist, 3);SLTInsert(plist, pos, 30);SLTPrint(plist);
}
void TestSList6()
{SLTNode* plist NULL;SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPushBack(plist, 5);SLTPrint(plist);int x;scanf(%d, x);SLTNode* pos SLTFind(plist, x);if (pos){SLTInsertAfter(pos, x * 10);}SLTPrint(plist);
}void TestSList7()
{SLTNode* plist NULL;SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPushBack(plist, 5);SLTPrint(plist);int x;scanf(%d, x);SLTNode* pos SLTFind(plist, x);if (pos){//SLTErase(plist, pos);SLTEraseAfter(pos);pos NULL;}SLTPrint(plist);SLTPopFront(plist);SLTPrint(plist);SLTPopFront(plist);SLTPrint(plist);SLTPopFront(plist);SLTPrint(plist);SLTPopFront(plist);SLTPrint(plist);}
int main()
{//TestSList1();//TestSList2();//TestSList3();//TestSList4();//TestSList5();//TestSList5();TestSList7();return 0;
}
实现文件
#define _CRT_SECURE_NO_WARNINGS 1
#includeSList.h
void SLTPrint(SLTNode* phead)
{SLTNode* cur phead;while (cur ! NULL){printf(%d-, cur-data);cur cur-next;}//结束打印空printf(NULL\n);
}
//开辟节点并赋值
SLTNode* BuySLTNode(SLTDataType X)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));if (newnode NULL){perror(malloc);exit(-1);}newnode-data X;newnode-next NULL;return newnode;
}
// 单链表尾插
//第一个参数为头指针的拷贝形参
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode BuySLTNode(x);//如果链表为空//*ppheadplistif (*pphead NULL){//改变结构体指针用结构体二级指针*pphead newnode;}else{SLTNode* tail *pphead;//创建要插入的新节点//遍历下一个节点指向为空的节点while (tail-next ! NULL){tail tail-next;}//改变结构体用结构体指针将该节点与新节点链接起来tail-next newnode;}
}
// 单链表的头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode BuySLTNode(x);newnode-next *pphead;*pphead newnode;
}
// 单链表的尾删
void SLTPopBack(SLTNode** pphead)
{//限制参数不为空assert(*pphead);//仅有一个节点的情况if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}//有两个及以上节点的情况else{//尾节点的前一个节点SLTNode* tailPre NULL;SLTNode* tail *pphead;while (tail-next ! NULL){tailPre tail;//tail往后走之前赋给前一个指针tail tail-next;}free(tail);tailPre-next NULL;}
}
// 单链表头删
void SLTPopFront(SLTNode** pphead)
{assert(*pphead);//第二个节点SLTNode* newhead (*pphead)-next;//释放第一个节点free(*pphead);//让第二个节点成为新的头节点*pphead newhead;
}
// 单链表查找
SLTNode* SLTFind(SLTNode* plist, SLTDataType x)
{SLTNode* cur plist;while (cur){//找到了就返回地址if (cur-data x){return cur;}cur cur-next;}//遍历完了还没找到return NULL;
}
//在pos之前插入X,pos为节点的指针
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{//pos不能为空assert(pos);//如果为头插if (pos *pphead){SLTPushFront(pphead, x);}else{SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}//待插入的新节点SLTNode* newnode BuySLTNode(x);prev-next newnode;newnode-next pos;}
}
//在pos之后插入X
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode BuySLTNode(x);//先链接新节点与pos之后的节点newnode-next pos-next;//再链接pos与新节点pos-next newnode;
}
//删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pos);//如果pos为头节点if (pos *pphead){//直接复用参数为二级指针SLTPopFront(pphead);}else{SLTNode* prev *pphead;while (prev-next pos){prev prev-next;}prev-next pos-next;free(pos);}
}
//删除pos的后一个
void SLTEraseAfter(SLTNode* pos)
{assert(pos);//不能删尾assert(pos-next);//将pos的下一个节点保存下来SLTNode* posNext pos-next;//将pos和下下个节点链接起来pos-next posNext-next;//释放pos的下一个节点free(posNext);
}
// 顺序表销毁
void SLTDestory(SLTNode** pphead)
{assert(pphead);SLTNode* cur *pphead;while (cur){SLTNode* next cur-next;free(cur);cur next;}//销毁完毕将头指针置空*pphead NULL;
}
