第二章 链表 删除带头结点的单链表值为x的节点并释放其空间

#include <stdio.h>
#include <stdlib.h>

using namespace std;

int n=5;
int a[5]={1,2,3,5,5};

typedef struct LinkedList{
    int data;
    struct LinkedList *next;
}LinkedList,*List;//LinkedList使我们给这个结构体赋的变量名
//List是定义了一个指针作为头结点 

void build(List &L){
    L=(List)malloc (sizeof(LinkedList));//先给头结点分配空间第一个括号里是数据类型是定义的头指针类型
    //后一个是一个节点的大小 
    //List本来就是指针类型的所以我们在这条语句不用加* 
    LinkedList *s;//结构体指针 
    LinkedList *r=L;//临时指针当做头结点 
        for(int i=0;i<n;i++){//for循环建立链表 
            s=(LinkedList *)malloc(sizeof(LinkedList));//分配空间第一个括号中是数据类型是定义的结构体类型
            //后一个sizeof大小是一个节点的大小 
            s->data=a[i];
            r->next=s;
            r=r->next; 
        }
        //建立完毕后我们要把最后一个节点指向的next置NULL
        r->next=NULL; 
    
}

void show(List L){
    LinkedList *s=L->next;//我们传的是头结点所以s定义为指向头结点的后一个元素 
    while(s){
        printf("%d  ",s->data);
        s=s->next;
    }
}

void del(List &L,int x){//传头结点 
    LinkedList *r=L->next;//第一个元素 
    LinkedList *pre=L;//头结点也算是记录比较的前一个节点 
    LinkedList *temp;
    while(r){
        if(x==r->data){
            temp=r;//临时变量记录符合条件的节点 
            pre->next=r->next;//头结点指向
            //在这条语句中 pre不需要向后移动因为当前的pre就是我们不符合条件的最后一个节点
            //知道找出下一个不为x值得节点往后移动
            //更新最后一个不符合条件x的节点 
            r=r->next;//覆盖节点也相当于往后移动一个节点 
            free(temp);    //释放空间 
        }else{
            //两个指针都后移 
            pre=pre->next;
            r=r->next;    
        }    
    }

    
}
int main(){
    List L;//定义头指针 
    build(L);//传头指针 
    printf("原本的链表是:\n");
    show(L); 
    printf("\n");
    printf("修改之后的链表是:\n");
    del(L,5);
    show(L);
    return 0;

上一篇:二叉树的遍历


下一篇:第 14 章集合