首页 > C语言教程 > C语言指针 阅读数:22

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