[题集]指针与链表

以上链表的第一个节点都不存放数据,如果head指向的节点也存放数据,则堆栈程序应该如何修改。

栈的实现:先进先出。删除和添加都在前端

程序思路:

添加:定义一个结构体,不初始化头结点,在添加结点的时候判断头指针是否为空,如果为空,则让头指针指向新添加的节点,节点的指针域为空,如果不为空,则让新结点的指针域链接头指针所指向的节点,头指针指向新结点。

删除:删除在前端,也就是回收头指针所指向的节点,先用一个结构体指针保存头节点的指针域,再释放头节点,再让头指针指向头节点的指针域

代码实现:

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<conio.h>
void Inser();
void Delete();
void Display();
void Quit();
struct student
{
    int id;
    int score;
    struct student* next;
};

typedef struct student ST;

ST* head, * p , * s;

int main()
{
    char a;
    while (1)
    {
        printf("请输入需要的功能: 1.增加  2.删除  3.遍历  4.退出\n");
        a = _getch();
        switch (a)
        {
        case'1':
            Inser();
            break;
        case'2':
            Delete();
            break;
        case'3':
            Display();
            break;
        case'4':
            Quit();
            break;
        }

    }
}

void Inser()
{
    p = (ST*)malloc(sizeof(ST));
    printf("请输入ID:");
    scanf("%d", &p->id);
    printf("请输入分数:");
    scanf("%d", &p->score);
    if (head == NULL)
    {
        head = p;
        head->next = NULL;
    }
    else
    {
        p->next = head;
        head = p;
        printf("\n添加成功\n");

    }
}
    
void Delete()
{
    if (head == NULL)
    {
        printf("\n未找到数据\n");
    }
    else
    {
        s = head->next;
        free(head);
        head = s;
        printf("\n删除成功\n");
    }
}
void Display()
{
    if (head == NULL)
    {
        printf("\n未找到数据\n");
    }
    else
    {
        s = head;
        while (s != NULL)
        {
            printf("\nID:%d\tScore:%d\n", s->id, s->score);
            s = s->next;
        }
    }
}
void Quit()
{
    exit(0);
}

定义结构体

img

程序定义了一个结构体,也定义了三个指针

  • head作为头指针,始终指向第一个节点
  • p作为分配指针,不断创建新的节点
  • s作为操作指针,用于实现各项功能,临时存放地址

添加功能

img

用p创建一个新的节点载入数据域,先判断头指针是否有指向,如果没有的话让头指针指向新创建的节点,作为头节点

如果有的话,先让新节点的指针域指向头指针内保存的地址,再让头指针指向新节点

删除功能

就完成了增加节点,我们看看如何删除节点,由于是栈实现,先进先出,则删除也是在前端

img

这儿用到了操作指针s,先判断头头指针是否指向节点,如果没有,则未添加数据

如果有,则先让s指向头节点的指针域,保存头节点后的节点地址,然后再释放头节点,最后将头指针指向s

就完成了删除工作。

不同之处

相比于头节点中不存放数据,头节点中存放数据很容易导致逻辑错误,头指针一不注意就会乱指。

头节点存放数据:头指针指向第一个节点,当需要添加和删除的时候,需要注意头指针的指向,和节点指针域的指向

头节点不存数据:在所有动作之前必须初始化头节点,头指针始终指向这一个节点,所有操作都在头节点后完成,只需要注意指针域的指向,不容易造成逻辑错误

当然,两种方式在进行所有操作之前,都要判断是否为空链表!

下一题:

有一链表添加和删除都在后端,请以head所指向的节点存放数据和未存放数据两种编写程序,并加以比较

添加和删除都在后端,头节点带数据

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<conio.h>
void Inser();
void Delete();
void Display();
void Quit();
struct student
{
    int id;
    int score;
    struct student* next;
};
typedef struct student ST;

ST* head, * p, * s, * s1;
int main()
{
    char a;
    while (1)
    {
        printf("请输入功能:1.添加  2.删除  3.显示  4.退出\n");
        a = _getch();
        switch (a)
        {
        case'1':
            Inser();
            break;
        case'2':
            Delete();
            break;
        case'3':
            Display();
            break;
        }
    }

    return 0;

    
}
void Inser()
{
    p = (ST*)malloc(sizeof(ST));
    printf("请输入ID:");
    scanf("%d", &p->id);
    printf("请输入分数:");
    scanf("%d", &p->score);

    if (head == NULL)
    {
        head = p;
        p->next = NULL;
    }
    else
    {
        s = head;
        s1 = head->next;
        while (s1 != NULL)
        {
            s = s1;
            s1 = s1->next;
        }
        s->next = p;
        p->next = NULL;
    }
}
void Delete()
{
    if (head == NULL)
    {
        printf("\n未存放数据\n");
    }
    else
    {
        s = head;
        s1 = head->next;
        if (s1 == NULL)
        {
            head = NULL;
            free(s);
        }
        else
        {
            while (s1->next != NULL)
            {
                s = s1;
                s1 = s1->next;
            }
            s->next = NULL;
            free(s1);
            
        }
        printf("\n删除成功\n");
    }
}
void Display()
{
    if (head == NULL)
    {
        printf("\n未找到数据\n");
    }
    else
    {
        s = head;
        while (s != NULL)
        {
            printf("\n%d\t%d\n", s->id, s->score);
            s = s->next;

        }
    }


}

重点在添加和删除哪儿,我选择了两个操作指针来控制,逻辑清晰一些,程序要求添加和删除都在尾端,则需要利用while找到指针域为NULL的节点,进行添加和删除

添加只需要将尾结点的指针域指向新结点,新结点的指针域再指向NULL即可

而删除则需要找到指针域为空的前一个节点,然后删除指针域为空的节点,再将前一个结点指向空

添加节点

img

先利用分配指针p新分配一个节点,再判断是否有头结点(头指针是否有数据)

如果有头节点,则利用一个while循环找到尾结点,从头结点开始,S控制当前节点,s1控制后置节点

找到尾端节点后,将尾结点的指针域指向新节点,将新节点的指针域指向NULL

删除功能

先看代码:

img

还是先判断头指针是否指向数据

如果有的话,则从头节点开始,让s管理当前节点,s1管理后置节点

直到后置节点的指针域为空的时候,找到了尾端结点

随即将当前节点的指针域为空,断开与尾结点的链接,这时s1管理着尾结点,最后回收s1的空间,完成了尾删的动作

头节点不带数据

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<conio.h>
void Inser();
void Delete();
void Display();
void Quit();
struct student
{
    int id;
    int score;
    struct student* next;
};
typedef struct student ST;

ST* head, * p, * s, * s1;
int main()
{
    head = (ST*)malloc(sizeof(ST));
    head->next = NULL;
    char a;
    while (1)
    {
        printf("请输入功能:1.添加  2.删除  3.显示  4.退出\n");
        a = _getch();
        switch (a)
        {
        case'1':
            Inser();
            break;
        case'2':
            Delete();
            break;
        case'3':
            Display();
            break;
        }
    }

    return 0;

    
}
void Inser()
{
    p = (ST*)malloc(sizeof(ST));
    printf("请输入ID:");
    scanf("%d", &p->id);
    printf("请输入学分:");
    scanf("%d", &p->score);
    
    s = head;
    s1 = head->next;

    while (s1 != NULL)
    {
        s = s1;
        s1 = s1->next;
    }
    s->next = p;
    p->next = s1;

    printf("\n添加成功\n");
}
void Delete()
{
    s = head;
    s1 = head->next;
    if (s1 == NULL)
    {
        printf("\n未找到数据\n");
    }
    else
    {
        while (s1->next != NULL)
        {
            s = s1;
            s1 = s1->next;
        }
        s->next = NULL;
        free(s1);
        printf("\n删除成功\n");
    }
}
void Display()
{
    s = head;
    s1 = head->next;
    if (s1 == NULL)
    {
        printf("\n未找到数据\n");
    }
    else
    {
        while (s1 != NULL)
        {
            
            s = s1;
            s1 = s1->next;
            printf("\nID:%d\t分数:%d\n", s->id, s->score);
        }
    }
}
void Quit()
{
    exit(0);
}

由于头节点中不存放数据,头指针始终指向头节点,所有操作均在头结点后完成

添加和删除并无很大的区别,只是不需要考虑头指针的指向,所有操作都是从头节点开始。

而头节点中存放数据,则需要考虑头指针的指向来进行操作

添加和删除与上述无太大区别,就不多做废话了。

到这里指针与链表的基础就学完了。

课时总结

链表是一种数据结构,它除了可用指针实现,也可以用数组实现,是一种思想,需要掌握的就是各个节点的链接。

指针域的指向,如何用操作指针来操作指针域,当然用指针实现的链式存储结构是需要从表头或表尾来进行操作的,它不能像数组一样指定下标来进行操作。

原因是数组的内存是固定的具有连续性的,通过下标能轻易的操作所属的内存区域,而链式存储所有内存都是不连续性的,只能通过头指针存储表头的地址,依次进行访问和操作

本文链接:

https://nullcode.fun/117.html
1 + 3 =
快来做第一个评论的人吧~