C语言遍历单链表,插入、删除…完整实现代码

2022-07-1711:42:48数据结构与算法Comments1,222 views字数 4891阅读模式

1.   遍历单链表(打印,修改)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25058.html

便利的概念想必大家都不会陌生,即就是从链表的头开始,逐步向后进行每一个元素的访问,这就是遍历,对于遍历操作,我们可以衍生出很多常用的数据操作,比如说查询元素,修改元素,获取元素个数,打印整个链表数据等等。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25058.html

进行遍历的思路极其简单,只需要建立一个指向链表L的结点,然后沿着链表L逐个向后搜索即可。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25058.html

对于遍历操作,以下是代码实现:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25058.html

//便利输出单链表
void printList(LinkedList L){
    Node *p=L->next;
    int i=0;
    while(p){
        printf("第%d个元素的值为:%d\n",++i,p->data);
        p=p->next;
    }
}

对于元素修改操作,以下是代码实现:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25058.html

//链表内容的修改,再链表中修改值为x的元素变为为k。
LinkedList LinkedListReplace(LinkedList L,int x,int k) {
    Node *p=L->next;
    int i=0;
    while(p){
        if(p->data==x){
            p->data=k;
        }
        p=p->next;
    }
    return L;
}

简单的遍历设计的函数只需要void无参即可,而当我们需要进行元素修等涉及到元素操作时,我们可以设计一个LinkedList类型的函数,使其返回一个修改后的新链表。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25058.html

以上的操作均用到了遍历的思维,针对于遍历还有非常多的用法供自主设计,请参考后文配套的习题进行练习。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25058.html

2.   插入操作文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25058.html

链表的增加结点操作主要分为查找到第i个位置,将该位置的next指针修改为指向我们新插入的结点,而新插入的结点next指针指向我们i+1个位置的结点。其操作方式可以设置一个前驱结点,利用循环找到第i个位置,再进行插入。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25058.html

如图,在DATA1和DATA2数据结点之中插入一个NEW_DATA数据结点:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25058.html

从原来的链表状态文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25058.html

C语言遍历单链表,插入、删除…完整实现代码文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25058.html

 文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25058.html

到新的链表状态:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25058.html

C语言遍历单链表,插入、删除…完整实现代码文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25058.html

 文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25058.html

以下是代码实现:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25058.html

//单链表的插入,在链表的第i个位置插入x的元素
 
LinkedList LinkedListInsert(LinkedList L,int i,int x) {
    Node *pre;                      //pre为前驱结点
    pre = L;
    int tempi = 0;
    for (tempi = 1; tempi < i; tempi++) {
        pre = pre->next;                 //查找第i个位置的前驱结点
    }
    Node *p;                                //插入的结点为p
    p = (Node *)malloc(sizeof(Node));
    p->data = x;
    p->next = pre->next;
    pre->next = p;
 
    return L;
}

3.  删除操作文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25058.html

删除元素要建立一个前驱结点和一个当前结点,当找到了我们需要删除的数据时,直接使用前驱结点跳过要删除的结点指向要删除结点的后一个结点,再将原有的结点通过free函数释放掉。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25058.html

参考如图文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25058.html

C语言遍历单链表,插入、删除…完整实现代码文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25058.html

 文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25058.html

以下是代码实现:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25058.html

//单链表的删除,在链表中删除值为x的元素
 
LinkedList LinkedListDelete(LinkedList L,int x) {
    Node *p,*pre;                   //pre为前驱结点,p为查找的结点。
    p = L->next;
    
    while(p->data != x) {              //查找值为x的元素
        pre = p;
        p = p->next;
    }
    pre->next = p->next;          //删除操作,将其前驱next指向其后继。
    free(p);
    
    return L;
}

 文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25058.html

4.  附:完整实现代码文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25058.html

#include <stdio.h>
#include <stdlib.h>
//定义结点类型
typedef struct Node {
    int data;           //数据类型,你可以把int型的data换成任意数据类型,包括结构体struct等复合类型
    struct Node *next;          //单链表的指针域
} Node,*LinkedList;
//单链表的初始化
LinkedList LinkedListInit() {
    Node *L;
    L = (Node *)malloc(sizeof(Node));   //申请结点空间
    if(L==NULL){    //判断申请空间是否失败
        exit(0);    //如果失败则退出程序
    }
    L->next = NULL;          //将next设置为NULL,初始长度为0的单链表
    return L;
}
//单链表的建立1,头插法建立单链表
LinkedList LinkedListCreatH() {
    Node *L;
    L = (Node *)malloc(sizeof(Node));   //申请头结点空间
    L->next = NULL;                      //初始化一个空链表
    int x;                         //x为链表数据域中的数据
    while(scanf("%d",&x) != EOF) {
        Node *p;
        p = (Node *)malloc(sizeof(Node));   //申请新的结点
        p->data = x;                     //结点数据域赋值
        p->next = L->next;                    //将结点插入到表头L-->|2|-->|1|-->NULL
        L->next = p;
    }
    return L;
}
//单链表的建立2,尾插法建立单链表
LinkedList LinkedListCreatT() {
    Node *L;
    L = (Node *)malloc(sizeof(Node));   //申请头结点空间
    L->next = NULL;                  //初始化一个空链表
    Node *r;
    r = L;                          //r始终指向终端结点,开始时指向头结点
    int x;                         //x为链表数据域中的数据
    while(scanf("%d",&x) != EOF) {
        Node *p;
        p = (Node *)malloc(sizeof(Node));   //申请新的结点
        p->data = x;                     //结点数据域赋值
        r->next = p;                 //将结点插入到表头L-->|1|-->|2|-->NULL
        r = p;
    }
    r->next = NULL;
    return L;
}
//单链表的插入,在链表的第i个位置插入x的元素
LinkedList LinkedListInsert(LinkedList L,int i,int x) {
    Node *pre;                      //pre为前驱结点
    pre = L;
    int tempi = 0;
    for (tempi = 1; tempi < i; tempi++) {
        pre = pre->next;                 //查找第i个位置的前驱结点
    }
    Node *p;                                //插入的结点为p
    p = (Node *)malloc(sizeof(Node));
    p->data = x;
    p->next = pre->next;
    pre->next = p;
    return L;
}
//单链表的删除,在链表中删除值为x的元素
LinkedList LinkedListDelete(LinkedList L,int x) {
    Node *p,*pre;                   //pre为前驱结点,p为查找的结点。
    p = L->next;
    
    while(p->data != x) {              //查找值为x的元素
        pre = p;
        p = p->next;
    }
    pre->next = p->next;          //删除操作,将其前驱next指向其后继。
    free(p);
    
    return L;
}
//链表内容的修改,再链表中修改值为x的元素变为为k。
LinkedList LinkedListReplace(LinkedList L,int x,int k) {
    Node *p=L->next;
    int i=0;
    while(p){
        if(p->data==x){
            p->data=k;
        }
        p=p->next;
    }
    return L;
}
//便利输出单链表
void printList(LinkedList L){
    Node *p=L->next;
    int i=0;
    while(p){
        printf("第%d个元素的值为:%d\n",++i,p->data);
        p=p->next;
    }
int main() {
    //创建 
    LinkedList list;
    printf("请输入单链表的数据:以EOF结尾\n");
    list = LinkedListCreatT();
    //list=LinkedListCreatT();
    printList(list);
    
    //插入 
    int i;
    int x;
    printf("请输入插入数据的位置:");
    scanf("%d",&i);
    printf("请输入插入数据的值:");
    scanf("%d",&x);
    LinkedListInsert(list,i,x);
    printList(list);
    
    //修改
    printf("请输入修改的数据:");
    scanf("%d",&i);
    printf("请输入修改后的值:");
    scanf("%d",&x);
    LinkedListReplace(list,i,x);
    printList(list);
    
    //删除 
    printf("请输入要删除的元素的值:");
    scanf("%d",&x);
    LinkedListDelete(list,x);
    printList(list);
    return 0;
}
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25058.html
  • 本站内容整理自互联网,仅提供信息存储空间服务,以方便学习之用。如对文章、图片、字体等版权有疑问,请在下方留言,管理员看到后,将第一时间进行处理。
  • 转载请务必保留本文链接:https://www.cainiaoxueyuan.com/suanfa/25058.html

Comment

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定