广东省建设银行招聘网站,惠州市住房和城乡规划建设局官方网站,百度大搜推广和百度竞价,谷歌浏览器免费入口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;
}
完整代码
头文件
#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); 测试文件
#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);
//}
int main()
{//TestSList1();TestSList2();/*TestSList3();TestSList4();TestSList5();*/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;
}
