带头结点的单链表的 *** 作（C语言）

带头结点的单链表的 *** 作（C语言）

初始化

先了解头结点

头结点是一个特殊的结点，它的数据域不存储信息，通常情况下，头指针指向的结点为头结点，由于头结点不存储信息，所以不是数据结构中的实际结点，第一个实际结点其实是head->next指示的结点，也就是头节点的下一个结点

那么，头节点的作用是什么

不带头结点链表的插入

带头结点链表的插入

---

可以看到，有了头结点之后，无论是在链表的任何位置进行插入 *** 作都是一样的，所以，头结点的作用就是为了“统一 *** 作”，值得注意的是，链表不删除，头结点就会一直存在。

插入 *** 作也是同理

不带头结点链表的删除 *** 作

 带头结点链表的删除 *** 作

了解完头结点后，来看一下如何设置头结点，也就是初始化

不带头结点链表的初始化

代码

//初始化，创建头结点
note *initList(note *L)
{
    return NULL;
}

带头结点链表的初始化

代码

//初始化，创建头结点
note *initList(note *L)
{
    L = (note*) malloc(sizeof(note));//为头结点分配空间
    L->next = NULL;//头结点指针域置空
    return L;
}

创建链表

头插法创建链表代码

//尾插法创建不指定个数，带头结点单链表
note *createList()
{
    int i;
    datatype data ;
    note *L = initList(L), *n;//分别定义头指针、新指针
    data = getchar();
    while (data != '#')//以“#”作为结束符
    {   
        n = (note*) malloc(sizeof(note));//为新结点申请空间
        n->data = data ;
        n->next = L->next;//新指针指针域是头指针下一个结点地址，
        L->next = n;//将新指针链入头结点之后
        getchar();
        scanf("%c",&data);
    }
    return L;
}

尾插法创建链表代码

//尾插法创建不指定个数，带头结点单链表
note *createList()
{
    int i;
    datatype data ;
    note *L = initList(L), *r, *n;//分别定义头指针、尾指针、新指针
    r = L;//尾指针初始化为头指针
    data = getchar();
    while (data != '#')//以“#”作为结束符
    {   
        n = (note*) malloc(sizeof(note));//为新结点申请空间
        n->data = data ;
        n->next = NULL;//新指针指针域置空
        r->next = n;//将新指针链入单链表末尾
        r = r->next;//尾指针往后移
        getchar();
        scanf("%c",&data);
    }
    return L;
}

头插法和尾插法的区别

 

当然，有时要求指定结点个数创建链表，下面给出相应代码，读者可以自行比较

尾插法插法创建链表（指定结点个数）代码

//尾插法创建指定个数，带头结点单链表
note *createList()
{   
    int len;
    printf("元素个数");
    scanf("%d",&len);
    printf("请输入，用空格间隔");
    datatype data;
    note *L = initList(L), *r, *n;//分别定义头指针、尾指针、新指针
    r = L;//尾指针初始化为头指针
    for(int i = 0;i < len;i ++)
    {
        scanf("%d", &data);
        n = (note*) malloc(sizeof(note));//为新节点申请空间
        n->data = data;
        n->next = NULL;//新指针指针域置空
        r->next = n;//将新指针链入单链表末尾
        r = r->next;//尾指针往后移
    }
    return L;
}

查找

//查找单链表中第i个结点，并且返回该结点的地址
note *find(note *L,int i )
{
    int j = 0;
    note *p = L;
    if (i < 0)
    {
        printf("该结点不存在");
    }
    else if( i == 0)
    {
        return p ;//此时，p指向头结点
    }
    while ( p && i!=j)
    {
        p = p->next;
        j++;
    }
    return p ;
}

插入

//插入
note *insert(note *L)
{   
    int pos ;
    datatype x;
    printf("请输入插入的位置和元素(用空格间隔):");
    scanf("%d %c",&pos,&x);
    note *p;
    note *q;
    p = find(L,pos);
    if(p)
    {
        q = (note*)malloc(sizeof(note));//为要插入的结点申请空间
        q->data = x;
        q->next = p->next;
        p->next = q;
        return L;
    }
    else
    {
        printf("该结点不存在");
        return L;
    }
}

删除

//查找单链表中第i个结点，并且返回该结点的地址
note *find(note *L,int i )
{
    int j = 0;
    note *p = L;
    if (i < 0)
    {
        printf("该结点不存在");
    }
    else if( i == 0)
    {
        return p ;//此时，p指向头结点
    }
    while ( p && i!=j)
    {
        p = p->next;
        j++;
    }
    return p ;
}

输出链表

void printlinkList(note *L)
{
    note *p;
    p = L->next;
    while(p)
    {
        printf("%d ",p->data);
        p = p->next;
    }
}

这里需要注意

输出链表肯定是要输出实际结点

对于无头节点的链表，从head指向的结点开始输出（p = L）

对于有头结点的链表，需要从head->next指向的结点开始输出(p=L->next)

完整代码

#include 
#include 
#include 


typedef char datatype;
//定义单链表结构
typedef struct note_list
{
    datatype data;//数据域
    struct note_list *next;//指针域，指向下一节点
}note;

//函数声明
note *initList();
note *createList();
note *find();
note *insert();
note *delete();
void printlinkList();

int main()
{
    note *L;
    printf("请输入元素，用空格间隔，用“ # ”结尾:");
    L = createList();
    insert(L);
    delete(L);
    printf("nL链表所有元素:");
    printlinkList(L);
    return 0;
}


//初始化，创建头结点
note *initList(note *L)
{
    L = (note*) malloc(sizeof(note));//为头结点分配空间
    L->next = NULL;//头结点指针域置空
    return L;
}

//尾插法创建不指定个数，带头结点单链表
//尾插法创建不指定个数，带头结点单链表
note *createList()
{
    int i;
    datatype data ;
    note *L = initList(L), *r, *n;//分别定义头指针、尾指针、新指针
    r = L;//尾指针初始化为头指针
    data = getchar();
    while (data != '#')//以“#”作为结束符
    {   
        n = (note*) malloc(sizeof(note));//为新结点申请空间
        n->data = data ;
        n->next = NULL;//新指针指针域置空
        r->next = n;//将新指针链入单链表末尾
        r = r->next;//尾指针往后移
        getchar();//吃掉空格
        scanf("%c",&data);
    }
    return L;
}

//查找单链表中第i个结点，并且返回该结点的地址
note *find(note *L,int pos )
{
    int j = 0;
    note *p = L;
    if (pos < 0)
    {
        printf("该结点不存在");
    }
    else if( pos == 0)
    {
        return p ;//此时，p指向头结点
    }
    while ( p && pos!=j)
    {
        p = p->next;
        j++;
    }
    return p ;
}

//插入
note *insert(note *L)
{   
    int pos ;
    datatype x;
    printf("请输入插入的位置和元素(用空格间隔):");
    scanf("%d %c",&pos,&x);
    note *p;
    note *q;
    p = find(L,pos);
    if(p)
    {
        q = (note*)malloc(sizeof(note));//为要插入的结点申请空间
        q->data = x;
        q->next = p->next;
        p->next = q;
        return L;
    }
    else
    {
        printf("该结点不存在");
        return L;
    }
}

//删除 *** 作
note *delete(note *L)
{   
    int pos;
    printf("请输入要删除元素的位置");
    scanf("%d",&pos);
    note *q;
    note *pre;//记录要删除结点的前一个结点
    datatype data;
    q = find(L,pos);
    if(!q)
    {
        printf("此链表不存在该结点，故不能删除");
        return L;
    }
    data = q->data;//记录要删除链结点的数据域
    pre = find(L,pos-1);//返回要删除结点的前一个结点的地址
    pre->next = q->next;
    free(q);//释放空间
    printf("%c已删除",data);
    return L;
}

//输出链表
void printlinkList(note *L)
{
    note *p;
    p = L->next;
    while(p)
    {
        printf("%c ",p->data);
        p = p->next;
    }
}

结果 

写在最后：

写这篇文章只是整理学习笔记，没有独到的见解，读者看到不合理之处还望批评指正