数据结构————带头结点单链表讲解

单链表分为带头结点的和不带头结点的，两者的根本区别在于是否有不存储元素的头结点。头结点的存在可以让链表为空的时候不销毁，操作也更方便，不用附带二级指针。

表示形式

每一个结点都有指针域和数据域，指针域用来指向下一个结点，数据域用来存放该结点的元素。

基本操作

单链表的基本操作有初始化、前插、后插、前删、后删等。后面我们将讲述基于这些基本操作上更复杂的操作。

1.初始化

typedef int LNdataType;
typedef struct ListNode{
    struct ListNode*next;
    LNdataType data;
}LT,*Link;
void InitList(Link phead){
    if(phead==NULL)
         return;
    else
        phead->next=NULL;
}

2.前插

void InsertListfront(Link phead,LNdataType x){
     LN*newnode=(LN*)malloc(sizeof(LN));
     if(newnode==NULL)
        exit(-1);
     else{
        newnode->data=x;
        newnode->next=phead->next;
        phead->next=newnode;
    }
}

3.后插

void InsertListback(Link phead,LNdataType x){
     LN*newnode=(LN*)malloc(sizeof(LN));
     if(newnode==NULL){      
        exit(-1);
     else{
        newnode->data=x;
        newnode->next=NULL;
        LN*tail=phead;
        while(tail->next)
            tail=tail->next;
        tail->next=newnode;
    }
}

4.前删

void DeleteListfront(Link phead){
     if(phead->next==NULL)
        printf("没有元素可删除\n");
     else{
        LT*cur=phead->next;
        phead->next=cur->next;
        free(cur);
        cur=NULL;
    }
}
     

5.后删

void DeleteListback(Link phead){
     LN*tail=phead->next,*head=phead;
     if(phead->next==NULL)
        printf("没有元素可删除\n");
     else{
        while(tail){
            tail=tail->next;
            head=head->next;
        }
    head->next=NULL;
    free(tail);
    tail=NULL;
     }
}
        

6.插入

void InsertList(Link phead,int pos,LNdataTYpe x){
     LN*newnode=(LN*)malloc(sizeof(LN));
     LN*p=phead->next;
     newnode->data=x;
     if(newnode==NULL)
        exit(-1);
     else{
        for(int i=0;i<pos;i++)
            p=p->next;
        newnode->next=p->next;
        p->next=newnode;
    }
}

7.删除

void DeleteList(Link phead,LNdataType x){
     LN*cur=phead->next;
     LN*prev=phead;
     while(cur){
        if(cur->data==x){
            prev->next=cur->next;
            free(cur);
            cur=NULL;
        }
        else{
            cur=cur->next;
            prev=prev->next;
        }
      }
}