链表的基本操作总和

Julia999 · 发表于 2019-9-5 19:59:54

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

对链表的操作有：增,删,改,查,初始化。这些操作书上都有，似乎也可以完全看得懂，但是真正写起代码来还是一卡一卡的，所以自己再重新敲了一遍，也发现了一点点小规律。

#include<stdio.h>
#include<stdlib.h>
/*定义结构体链表节点：
该结构体有两个属性，一个是int类型的数据域data，另一个是这个结构体本身类型的指针next；
最后给这个结构体定义了一个别名Node，一个指针别名pNode；*/
//节点结构体
struct Node
{
int data; //数据域
struct Node* pNext; //指针域
};
//头指针和尾指针定义
//为什么要写尾指针呢，方便操作（尾添加）
struct Node* pHead = NULL;
struct Node* pEnd = NULL;
//初始化头结点
void initListHead()
{
//pHead已经是一个全局变量了
pHead = (struct Node*)malloc(sizeof(struct Node));
if (NULL == pHead)
{
printf("内存不足！");
exit(0);
}
pHead->pNext = NULL;
pEnd = pHead;
}
//尾添加
void addListEnd(int a)
{
//创建一个新节点
struct Node* pTemp = (struct Node*)malloc(sizeof(struct Node));
if (NULL == pTemp)
{
printf("创建节点失败！");
exit(0);
}
//将新节点赋值
pTemp->data = a;
pTemp->pNext = NULL;
//将新节点链接到链表中
pEnd->pNext = pTemp;
pEnd = pTemp;
}
//头添加
void addListHead(int a)
{
//创建新的节点
struct Node* pTemp = (struct Node*)malloc(sizeof(struct Node));
if (NULL == pTemp)
{
printf("创建节点失败！");
exit(0);
}
//将新节点赋值
pTemp->data = a;
pTemp->pNext = NULL;
//链接先连后断
//(先让节点的指针指向头指针的下一个，再让头指针指向新的节点)
pTemp->pNext = pHead->pNext;
pHead->pNext = pTemp;
}
//遍历链表
void showList()
{
//遍历链表要写一个中间指针，方便我们的操作，不能直接将头指针后指，也不能将尾指针前指
struct Node *p = pHead->pNext;
while (NULL != p)
{
printf("%d ", p->data);
p = p->pNext;
}
printf("\n");
}
//查询指定元素是否存在,若存在则并返回节点地址
struct Node* SelectNode(int index)
{
//遍历整个链表
struct Node *p = pHead->pNext;
while (NULL != p)
{
if (index == p->data)
{
return p;
}
p = p->pNext;
}
return NULL;
}
//在任意位置插入元素
//在任意位置添加结点的时候需要注意的是：要判断这个链表是不是空链表，还要判断能不能找到这个位置
void addListRand(int index,int a)
{
//判断这个链表是不是空链表
if (pHead->pNext == NULL)
{
printf("此链表为空表！");
}
//进行插入
//找到插入位置所在的地方（可以在外面再写一个函数，专门找到下标位置)
struct Node *pTemp=SelectNode(index);
if (NULL == pTemp)
{
//说明没有找到
printf("找不到该节点");
return;
}
else
{
//创建一个新的节点
struct Node* pNode = (struct Node*)malloc(sizeof(struct Node));
pNode->data = a;
//链接(如果我当前要插入的地方刚好是尾巴）
if (pTemp == pEnd)
{
//尾插入
addListEnd(a);
}
else
{
pNode->pNext = pTemp->pNext;
pTemp->pNext = pNode;
}
}
}
//改
void changeList(int index,int a)
{
//遍历链表
struct Node*p = (struct Node*)malloc(sizeof(struct Node));
p = pHead->pNext;
while (NULL != p)
{
if (index == p->data)
{
p->data = a;
}
p = p->pNext;
}
}
//删除
//删除头
void deleteHead()
{
//步骤：1先定义一个变量去记住要删掉的节点
//2.将头结点指向要删除的下一个节点
//3.将记住的节点释放掉
//如果链表为空表，那么就没有必要删除了
if (pHead->pNext == NULL)
{
printf("此链表为空表！");
}
//删除记住
struct Node*pTemp = pHead->pNext;
pHead->pNext = pHead->pNext->pNext;
//释放
free(pTemp);
}
//删除尾
void deleteEnd()
{
//如果链表为空表，那么就没有必要删除了
if (pHead->pNext == NULL)
{
printf("此链表为空表！");
return;
}
//只有一个节点
if (pHead->pNext = pEnd)
{
free(pEnd);
pHead->pNext = NULL;
pHead = pEnd;
}
else
{
//不止一个节点
//找到尾节点的上一个节点
struct Node*p = pHead->pNext;
while (NULL != p)
{
if (p->pNext = pEnd)
{
break;
}
p = p->pNext;
}
//这个时候p就是尾节点的上一个节点
//删除
free(pEnd);
//变新的尾节点
p = pEnd;
pEnd = NULL;
}
}
//删除任意(删除元素为a的节点）
void deleteRand(int a)
{
//判断这个链表是否为空
if (pHead->pNext == NULL)
{
printf("此链表为空表！");
return;
}
//链表不为空,遍历找到要删除的那个节点的上一个节点
struct Node*p = pHead->pNext;
while (NULL != p)
{
if (p->pNext->data==a)
{
break;
}
p = p->pNext;
}
//这个时候p就是要删除的那一个节点的上一个节点了
//如果p这个时候已经是尾节点了
if (p->pNext == pEnd)
{
deleteEnd();
}
else
{
//先记住要删除的节点
struct Node* pTemp = p->pNext;
p->pNext = p->pNext->pNext;
free(pTemp);
}
}
//释放整个链表
void freeList()
{
//遍历整个链表（注意，删除的时候需要先记住要删除的节点）
struct Node* pTemp = pHead;
while (pTemp != NULL)
{
struct Node* pT = pTemp;
pTemp = pTemp->pNext;
free(pT);
}
pHead = NULL;
pEnd = NULL;
}
int main(void)
{
//在main函数中一定要对头节点进行初始化！！！！
//链表空头
//但是在后面的代码中，我们发现头结点的初始化是经常要写的，所以我们为了方便还是写一个函数专门初始化头结点
/*struct Node* pHead = (struct Node*)malloc(sizeof(struct Node));
pHead->pNext = NULL;
pEnd = pHead;*/
initListHead();
//操作
addListEnd(1);
addListEnd(2);
addListEnd(3);
addListEnd(4);
addListRand(2, 6);
changeList(3, 5);
//deleteHead();
//deleteEnd();
showList();
deleteRand(5);
showList();
printf("删除整个链表\n");
freeList();
showList();
system("pause");
return 0;
}

复制代码

要想真正搞清楚，不会混乱，其实也没有那么难，将大的化小，有时候就清楚明了了。
在上面代码中，定义了头指针和尾指针，那为什么要定义两个指针呢？只定义一个指针不行吗？其实定义两个指针也是为了后面的方便，能够更好的理解。

初始化：在main函数中，一般都是要写对头结点的初始化的。

增：向链表中添加元素...emmm，咋填？
   分解来看，有三种向链表中增加元素的方法：1.头插入 2.尾插入 3.给定位置插入
   注意了：不管是什么方式插入，都有一样的操作：step 1：创建一个新的节点用来存需要插入的数据 step 2：将数据放进新创建的节点中  step 3：链接到链表上去
   特别的，在任意给定位置插入新节点的时候，需要注意能不能找到这个位置。

删：删除要记住了：
   //步骤：1先定义一个变量去记住要删掉的节点
   //2.将头结点指向要删除的下一个节点
   //3.将记住的节点释放掉同样的，删除也可以分成三个方法来删除：1.删头  2.删尾  3.任意删
这三种删除方式都有一个必须要判断的是：这个链表是不是空链表（如果是链表，那删除个啥？？？）
删头：删头的方式很简单，记住之后之间将头指针指向被删节点的下一个节点，然后释放记住的节点。
删尾：删尾相比较于删头复杂了一点点，但是也是很好理解的：要分成只有一个节点的情况和有多个结点的情况。
特别的，有多个结点的情况的删除，要找到尾节点的上一个节点（只有找到了尾节点的上一个节点，才能重定义尾指针）
任意删：任意删除给定位置的节点的时候，同样需要注意这个链表是不是空链表，并且需要判断能不能找到这个要删除的节点，如果找到了，再进行删除。

改：改的操作就很简单了，遍历整一个链表，如果找到了需要修改的位置，直接将该节点的数据域改成需要修改的值就可以了（需要注意的是，要写出找不到需修改节点的情况）

查：与改类似，略

删除整个链表：删除整个链表的时候，需要定义一个新的节点来记住要删除的节点，然后不断的后移，释放。

emmm，总之，还是要自己亲自动手操作才能完全掌握和理解滴~~

账号		自动登录	找回密码
密码			立即注册

[学习笔记] 链表的基本操作总和

马上注册，结交更多好友，享用更多功能^_^