C语言基础之——链表的基本操作

vlambda
2020-05-19

C语言基础之——链表的基本操作

前言

上节我们介绍了链表的创建以及初始化等操作实现，本节我们一起来学习链表的一些基本操作，包括对链表中数据的增加、删除、查找、遍历、修改等。

一

链表的增加

链表的增加，即向链表中插入一个结点，以位置为单位，插入的位置如果是1，则将此新增结点作为首元结点插入。

步骤：

1、将新增结点的next指针指向插入位置后的结点。

2、将插入位置前结点的next指针指向插入结点。

C语言基础之——链表的基本操作

代码如下：

link_t *InsertElem(link_t *p,int elem,int add_location) //p--original link;elem--insert elem;add_location---insert location { //create temp node link_t *temp = p; //find the insert location node's previous node temp. for(int i=1;i<add_location;i++) { if(temp == NULL) { printf("err insert location\r\n"); return p; } //move temp node temp = temp->next; } //create insert node link_t *c = (link_t *)malloc(sizeof(link_t)); c->data = elem; c->next = temp->next; temp->next = c; return p;}

链表插入元素的操作必须是先步骤 1，再步骤 2；反之，若先执行步骤 2，会导致插入位置后续的部分链表丢失，无法再实现步骤 1。

二

链表的删除

链表的删除，即将链表中指定位置的结点删除，由于结点在创建时，动态申请了内存，因此删除位置上的结点后，需要将此部分的内存回收，避免发生内存泄漏。

删除的步骤如下：

1、找到要删除结点的直接前驱结点temp，执行操作：

temp->next = temp->next->next

2、free删除结点申请的内存空间。

C语言基础之——链表的基本操作

代码如下：

link_t *DelElem(link_t *p,int del_location){ link_t *temp = p; //find the del node's previous node temp. for(int i=1;i<del_location;i++) { temp = temp->next;  } link_t *del_node = temp->next; //set one node point to the del node to avoid it lost. temp->next = temp->next->next; //move the del node's next node to the previous node. free(del_node); //remember free memory  return p;}

三

链表元素的查找

链表元素的查找，即在链表中查找该元素所处的位置。

在链表中查找指定数据元素，最常用的方法是：从表头依次遍历表中结点，用被查找元素与各结点数据域中存储的数据元素进行比对，直至比对成功或遍历至链表最末端的 NULL（比对失败的标志）。

代码如下：

int SelectElem(link_t *p,int elem){ //create a point ,init as the header point; link_t *t = p; int i = 1; //because of header_point exist,use while(t->next). while(t->next) { t = t->next; //set t as first node. if(t->data == elem) { return i; } i++; }  return -1;}

四

链表元素的更新

更新链表元素，即将链表中指定位置的元素，替换成想要的元素。

步骤：

1、遍历链表，找到结点位置。

2、替换结点数据。

代码如下：

link_t *update_link(link_t *p,int del,int NewElem){ link_t *temp = p; temp = temp->next; //temp point to the first node. for(int i=1;i<del;i++) //temp point to the del node. { temp = temp->next;  } temp->data = NewElem; return p;}

五

完整代码

#include "stdio.h"#include "stdlib.h"
typedef struct _link_t{ int data; struct _link_t *next;}link_t;
link_t *link_init(){ //create a header pointer link_t *header_p = NULL; //create a header node link_t *header_node = (link_t *)malloc(sizeof(link_t)); header_p = header_node; for(int i=1;i<5;i++) { //create other nodes link_t *temp = (link_t *)malloc(sizeof(link_t)); temp->data = i; temp->next = NULL; //establish contact with previous node. header_node->next = temp; //do not write header_p->next = temp!because header_p should always point to the header_node.  //move the precursor node to the next header_node = header_node->next; } return header_p;}link_t *InsertElem(link_t *p,int elem,int add_location) //p--original link;elem--insert elem;add_location---insert location { //create temp node link_t *temp = p; //find the insert location node's previous node temp. for(int i=1;i<add_location;i++) { if(temp == NULL) { printf("err insert location\r\n"); return p; } //move temp node temp = temp->next; } //create insert node link_t *c = (link_t *)malloc(sizeof(link_t)); c->data = elem; c->next = temp->next; temp->next = c; return p;} link_t *DelElem(link_t *p,int del_location){ link_t *temp = p; //find the del node's previous node temp. for(int i=1;i<del_location;i++) { temp = temp->next;  } link_t *del_node = temp->next; //set one node point to the del node to avoid it lost. temp->next = temp->next->next; //move the del node's next node to the previous node. free(del_node); //remember free memory return p; }int SelectElem(link_t *p,int elem){ //create a point ,init as the header point; link_t *t = p; int i = 1; //because of header_point exist,use while(t->next). while(t->next) { t = t->next; //set t as first node. if(t->data == elem) { return i; } i++; }  return -1;}link_t *update_link(link_t *p,int del,int NewElem){ link_t *temp = p; temp = temp->next; //temp point to the first node. for(int i=1;i<del;i++) //temp point to the del node. { temp = temp->next;  } temp->data = NewElem; return p;}void display(link_t *node){ while(node->next) //if the first node is not empty { node = node->next; printf("%d",node->data); } printf("\r\n");}int main(void){ int i = 0; link_t *p = NULL; p = link_init(); printf("Link elem is:\r\n"); display(p); InsertElem(p,6,1); display(p); DelElem(p,1); display(p); i = SelectElem(p,3); printf("%d\r\n",i); display(p); update_link(p,3,8); display(p);  return 0;}

六

运行

七

小结

QQ交流群：906015840 (备注：物联网项目交流)

静晨出品：静之所想，晨之所计

vlambda博客
学习文章列表