本文介绍链表一些基本操作,包括对链表中数据的
添加
、
删除
、
查找
(遍历)和
更改
。
都说没有链表初始化的操作都是耍流氓,那么这里先给出一个链表初始化。
//声明节点结构
typedef struct Link{
int elem;//存储整形元素
struct Link *next;//指向直接后继元素的指针
}link;
//创建链表的函数
link * initLink(){
link * p=(link*)malloc(sizeof(link));//创建一个头结点
link * temp=p;//声明一个指针指向头结点,用于遍历链表
//生成链表
for (int i=1; i<5; i++) {
//创建节点并初始化
link *a=(link*)malloc(sizeof(link));
a->elem=i;
a->next=NULL;
//建立新节点与直接前驱节点的逻辑关系
temp->next=a;
temp=temp->next;
}
return p;
}
添加
需做以下两步操作将新元素插入到指定的位置:
- 将新结点的 next 指针指向插入位置后的结点;
- 将插入位置前结点的 next 指针指向插入结点;
//p为原链表,elem表示新数据元素,add表示新元素要插入的位置
link * insertElem(link * p, int elem, int add) {
link * temp = p;//创建临时结点temp
//首先找到要插入位置的上一个结点
for (int i = 1; i < add; i++) {
temp = temp->next;
if (temp == NULL) {
printf("插入位置无效\n");
return p;
}
}
//创建插入结点c
link * c = (link*)malloc(sizeof(link));
c->elem = elem;
//向链表中插入结点
c->next = temp->next;
temp->next = c;
return p;
}
删除
从链表中删除数据元素需要进行以下 2 步操作:
- 将结点从链表中摘下来;
- 手动释放掉结点,回收被结点占用的存储空间;
//p为原链表,add为要删除元素的值
link * delElem(link * p, int add) {
link * temp = p;
//遍历到被删除结点的上一个结点
for (int i = 1; i < add; i++) {
temp = temp->next;
if (temp->next == NULL) {
printf("没有该结点\n");
return p;
}
}
link * del = temp->next;//单独设置一个指针指向被删除结点,以防丢失
temp->next = temp->next->next;//删除某个结点的方法就是更改前一个结点的指针域
free(del);//手动释放该结点,防止内存泄漏
return p;
}
查找
从表头依次遍历表中节点,用被查找元素与各节点数据域中存储的数据元素进行比对,直至比对成功或遍历至链表最末端的 NULL(比对失败的标志)。
//p为原链表,elem表示被查找元素、
int selectElem(link * p,int elem){
//新建一个指针t,初始化为头指针 p
link * t=p;
int i=1;
//由于头节点的存在,因此while中的判断为t->next
while (t->next) {
t=t->next;
if (t->elem==elem) {
return i;
}
i++;
}
//程序执行至此处,表示查找失败
return -1;
}
更改
只需通过遍历找到存储此元素的节点,对节点中的数据域做更改操作即可。
//更新函数,其中,add 表示更改结点在链表中的位置,newElem 为新的数据域的值
link *amendElem(link * p,int add,int newElem){
link * temp=p;
temp=temp->next;//在遍历之前,temp指向首元结点
//遍历到待更新结点
for (int i=1; i<add; i++) {
temp=temp->next;
}
temp->elem=newElem;
return p;
}
版权声明:本文为weixin_40401027原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。