首页 > C语言教程 > C语言指针

C语言单链表的基本操作（附带源码）

上一节
对于单向链表常见的操作有链表结点数据的查找、插入和删除。

单向链表的插入和删除操作
图 1：单向链表的插入和删除操作

1) 单链表节点的查找

在单向链表中，查找目标数据，只需从 head 指向的表头结点出发，沿着链表顺序遍历整个链表，并一一比较各个结点数值域中的数据即可。例如，从 head 为头指针的单向链表中查找数值域中成员 data 为 x 的结点，可以编写成以下函数 find( )： 
struct node{
    int data;
    struct node *next;
} *head;
void find(struct node *head, int x){
    int i=1;
    struct node *this;    //定义一个当前结点指针
    this = head;    //当前结点从头结点开始查找
    while((this != NULL) && !(this->data == x)){    //遍历链表
        this = this->next;    //不匹配，当前结点指针指向下一个结点
        i++;
    }
    if(this==NULL)
        printf("没有找到！\n");
    else
        printf("%d在链表的第%d个结点中！\n",x,i);
}

2) 单链表节点的插入

在数组的某个元素后面插入一个新的元素时，需要将该元素后面的所有元素都向后移动位置。而在链表的结点 p 后面插入一个新的结点，不必像数组那样移动后面的结点，只要将 p 的后继指针指向新的结点，并将新结点的后继指针指向 p 原来的后继结点即可（见图 1a) ）。例如，在单向链表的 p 结点后面插入一个数值域成员 data 的值为 x 的新结点，可以编写成以下函数 ins( )： 
void ins(struct node *p,int x){
    struct node *new;    //定义新结点
    new = malloc(sizeof(struct node));    //为新结点申请内存空间
    new->data = x;    //给新结点数值域成员赋值
    new->next = p->next;    //新结点后继指针指向 p 的后继结点
    p->next = new;    //p 的后继结点指向新结点
}

3) 单链表节点的删除

在单向链表中，要删除指针 p 指向的结点，只要将其前面一个结点（前驱结点）的后继指针指向 p 后面的结点（后继结点），并释放 p 所占用的内存即可（见图 1b) ）。例如，从 head 为头指针的单向链表中删除 p 指向结点，可以编写成以下函数 del( )： 
void del(struct node *p){
    struct node *this;    //定义一个当前结点指针
    this = head;    //当前结点从头结点开始查找
    if (this == p)    //p 为头结点时
        head = this->next;
    else{
        while(this->next !=p)    // 遍历链表，查找 p 的前驱结点
            this = this->next;    //不匹配，当前结点指针指向下一个结点
        this->next = p->next;    //当前结点 this 的后继指针指向 p 的后继结点
    }
    free(p);    //释放结点 p 占用的内存空间
}

完整示例+代码

1) 单链表节点的查找和插入

读入整数 n，建立一个单向链表，按顺序存储自然数 1 至 n，然后再在所有偶数后面插入 2。

C语言代码清单 1：在链表中查找、插入结点 
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
struct node{
    int data;
    struct node *next;
} *head, *q, *p;
void ins(struct node *p, int x)
{
    struct node *new;
    new = malloc(sizeof(struct node));
    new -> data = x;
    new -> next = p -> next;
    p -> next = new;
}
void print( )
{
    for(q = head; q != NULL; q = q -> next)
        printf("%d ",q -> data);
    printf("\n");
}
int main( )
{
    int i,n;
    printf("请输入一个正整数n：");    
    scanf("%d",&n);
    head = malloc(sizeof(struct node));   //创建初始链表
    head -> data = 1;    
    head -> next = NULL;
    q = head;
    for(i = 2; i <= n; i++){  //循环插入2~n
        ins(q,i);
        q = q -> next;
    }
    print();
    for(q = head; q != NULL; q = q -> next){  //查找偶数并在后面插入2
        if((q -> data) % 2 == 0){
            ins(q,2);
            q = q->next;
        }
    }
    print();
    system("pause");
    return 0;
}

运行结果为：

请输入一个正整数n：8
1 2 3 4 5 6 7 8
1 2 2 3 4 2 5 6 2 7 8 2

2) 单链表节点的删除

读入整数 n，建立一个单向链表，按顺序存储自然数 1 至 n，然后删除其中所有的奇数。

代码清单 2：在链表中删除结点 
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
struct node{
    int data;
    struct node *next;
} *head, *q, *p;
void ins(struct node *p, int x)
{
    struct node *new;
    new = malloc(sizeof(struct node));
    new -> data = x;
    new -> next = p -> next;
    p -> next = new;
}
void print( )
{
    for(q = head; q != NULL; q = q -> next)
        printf("%d ",q -> data);
    printf("\n");
}
int main( )
{
    int i,n;
    printf("请输入一个正整数n：");    
    scanf("%d",&n);
    head = malloc(sizeof(struct node));   //创建初始链表
    head -> data = 1;
    head -> next = NULL;
    q = head;
    for(i = 2; i <= n; i++){  //循环插入2~n
        ins(q,i);
        q = q -> next;
    }
    print();
    q = head;
    while(q -> next != NULL){  //查找并删除所有奇数
        if((q -> data) % 2 == 1) {
            q = head -> next;
            free(head);
            head = q;
        }
        else{
            p = q -> next;
            if((p -> data) % 2 == 1){
                q -> next = p -> next;
                free(p);
            }
            else 
                q = q -> next;
        }
    }
    print();
    system("pause");
    return 0;
}

运行结果为：

请输入一个正整数n：8
1 2 3 4 5 6 7 8
2 4 6 8

上一节