MENU

不带头结点的单链表操作

• October 27, 2020 •

写不带头结点单链表的插入操作和删除操作算法


我们平常编写的单链表都是带头结点的,因为带头结点的单链表操作有两大好处:

1.无论在头部、中部还是尾部进行操作,头指针的值都不会被改变;

2.在头部、中部、尾部的操作都一样。


题目分析:

不带头结点的单链表就没有上诉两个特点,因此我们在考虑不带头结点操作算法时会复杂一点,既要考虑头指针的值何时改变,又要考虑在头部、中部、尾部的操作究竟有何异同。还记得我在2-15单链表的遍历画的那张图吗?点这里我帮你传送一下在图的右边我们可以看到不带头结点的单链表在中部和尾部插入删除数据时操作一样,而在头部进行操作时有所不同。


考点:

**1.不带头结点与带头结点区别
2.带头结点单链表的好处
3.不带头结点单链表头部操作与中部、尾部操作的算法**


代码实现:

#include<stdio.h>
#include<stdlib.h>
typedef int dataType;    //数据类型为int
//结点结构体
typedef struct node
{
    dataType data;      //数据域
    struct node *next;  //指针域
}Node;
//初始化结点
void listInitiate(Node **head)            //双星指针,地址的地址,在初始化时,我们要使地址的值改变,所以使用双星作为参数传入
{
    (*head) = NULL;
}
/*尾插法建立单链表——得到的链表是顺序的
利用数组的前n个数建立一条单链表*/
void listBuildRear(Node **head, dataType arr[], int n)
{
    Node *p = (*head);                       //新增一个指针,用来代替head指针
    for (int i = 0; i < n; i++)              //循环n次,每次循环都在链表尾部追加一个结点
    {
        Node *q = (Node*)malloc(sizeof(Node));//新建立结点,并为之分配内存空间
        q->data = arr[i];                 //数据域赋值,将数组的第i+1个数字赋给新结点q
        q->next = NULL;                   //单链表最后一个结点的指针域都为空
        if(*head==NULL)                 //建立第一个结点
        {
            *head= q;
        }
        else
             p->next = q;                      //将原始单链表最后一个结点指针域指向新结点q,从此q成为最后一个结点,原始最后一个结点变成倒数第二个结点
        p = q;                            //p又指向当前链表最后一个结点,为下一次尾部插入做准备
    }
}
//往链表里面插入数据data,成功返回1,否则返回0
int listInsert(Node* *head,dataType data)
{
    Node *q,*p = *head;
    q = (Node *)malloc(sizeof(Node));     //新建立结点
    q->data = data;
    q->next = NULL;
    if ((*head)->data >= data)            //在头部插入
    {
        q->next = *head;                  //新结点的指针指向原第一个节点
        *head = q;                        //头指针指向新建立的结点
        return 1;                         //结束插入操作
    }
    else                                  //在中部或者尾部插入
        while (p != NULL)                 //遍历单链表
        {
           if (p->next == NULL || p->next->data >= data)   //   在尾部插入||在中间插入
           {
                q->next = p->next;        //新结点的指针指向p的指针
                p->next = q;              //p的指针指向q
                return 1;
           }
           p = p->next;
        }
    return 0;
}
//从链表里面删除数据,成功返回1,否则0
int listDelete(Node* *head, dataType data)
{
    Node *p = *head;
    if ((*head)->data == data)     //头部删除
    {
        *head = (*head)->next;     //第二个结点成为第一个结点
        return 1;
    }
    else                           //中部或者尾部删除
    {
        while (*head != NULL)      //遍历链表
        {
            if (p->next->next != NULL&&p->next->data == data)   //中部删除
            {
                p->next = p->next->next;
                return 1;
            }
            if (p->next->next == NULL) //尾部删除
            {
                if( p->next->data == data)
                {
                    p->next = NULL;
                    return 1;
                }
                else
                    break;
            }
            p = p->next;
        }
    }
    return 0;
}
//遍历输出函数
void listPrint(Node *head)
{
    printf("单链表:");
    Node *p = head;                       //新增一个指针,用来代替head指针
    while (p != NULL)
    {
        printf("%d   ", p->data);
        p = p->next;                      //这一句不要忘了,不然会死循环的,我总是忘掉这一句
    }
    printf("\n");
}
int main()
{
    dataType arr[] = {15,26,36,59,488};
    Node link;
    Node *p = &link;
    listInitiate(&p);
    listBuildRear(&p,arr,5);           //利用数组arr的前5个数建立单链表
    printf("原");
    listPrint(p);                      //打印原链表
    dataType number;
    printf("请输入要插入的数:");
    scanf("%d",&number);
    if(listInsert(&p,number))          //判断是否插入成功
    {
        printf("插入成功!\n插入后的");
        listPrint(p);                  //插入成功就输出
    }
    else{
        printf("插入失败!\n");
    }
    printf("请输入要删除的数:");
    scanf("%d",&number);
    if(listDelete(&p,number))
    {
        printf("删除成功!\n删除后的");
        listPrint(p);
    }
    else{
        printf("删除失败!\n");
    }
    return 0;
}

运行结果:


(1)头部插入,尾部删除

img


(2)尾部插入,中部删除

img


(3)中部插入,头部删除

img


(4)删除链表中没有的数据

img


代码编译器:Dev-C++
ok

Archives QR Code Tip
QR Code for this page
Tipping QR Code