时间戳

首页 > 技术文章 > 第二章-线性表-链表（初始化、循环、插入、删除、查找、是否为空、清空链表）

第二章-线性表-链表（初始化、循环、插入、删除、查找、是否为空、清空链表）

zhouying1208 2021-11-21 15:25 原文

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 9
#define OK 1
#define FALSE 0
#define Size 5

typedef int LElemType;
typedef int Status;

typedef struct Lnode
{
    LElemType data;
    struct Lnode *next;
} LNode, *LinkNode;

//初始化
LinkNode init_link();
//循环链表
void foreach_link(LinkNode head);
//插入
LinkNode add_link(LinkNode head, int index, int val);
//删除
LinkNode del_link(LinkNode head, int index);
//根据内容查找
void find_link(LinkNode head, int value);
//根据索引查找
void findIndex_link(LinkNode head, int index);
//判断链表是否为空
Status static_link(LinkNode head);
//清空链表
LinkNode clear_link(LinkNode head);

int main()
{
    LinkNode header = init_link();

    // add_link(header, 50, 888);

    // del_link(header, 30);

    // find_link(header, 3);

    // findIndex_link(header, 3);

    header=clear_link(header);

    int a = static_link(header);
    printf("a=%d\n", a);

    //循环
    // foreach_link(header);

    return 0;
}

LinkNode init_link()
{
    LinkNode head = (LinkNode)malloc(sizeof(LNode));
    head->data = -1;
    head->next = NULL;

    LinkNode p = head;
    int val = -1;
    while (1)
    {
        printf("请输入数据");
        scanf("%d", &val);
        if (val == -1)
            break;

        LinkNode newNode = (LinkNode)malloc(sizeof(LNode));
        newNode->data = val;
        newNode->next = NULL;

        //TIPS: 构造一个空节点，这样head一直指向头部，p一直指向最后一个节点，新来的节点等于p的下一个就能连起来
        p->next = newNode;
        p = newNode;
    }

    return head;
}

void foreach_link(LinkNode head)
{
    if (head->next == NULL)
    {
        printf("空链表");
        exit(0);
    }
    LinkNode p = head->next;
    while (p != NULL)
    {
        printf("%d\n", p->data);
        p = p->next;
    }
}

LinkNode add_link(LinkNode head, int index, int val)
{
    if (head->next == NULL)
    {
        printf("空链表");
        exit(0);
    }
    LinkNode pPrev = head;
    LinkNode pNext = head->next;

    //TIPS:  要考虑找不到节点的位置
    while (pNext != NULL)
    {
        if (pNext->data == index)
            break;
        pPrev = pNext;
        pNext = pNext->next;
    }
    if (pNext == NULL)
    {
        printf("找不到节点");
        exit(0);
    }
    LinkNode newNode = (LinkNode)malloc(sizeof(LNode));
    newNode->data = val;
    newNode->next = NULL;

    newNode->next = pNext;
    pPrev->next = newNode;
    return head;
}

LinkNode del_link(LinkNode head, int index)
{
    if (head->next == NULL)
    {
        printf("链表为空");
        exit(0);
    }

    //创造两个辅助指针
    LinkNode pPrev = head;
    LinkNode pNext = pPrev->next;

    while (pNext != NULL)
    {
        if (pNext->data == index)
            break;
        pPrev = pNext;
        pNext = pNext->next;
    }
    if (pNext == NULL)
    {
        printf("删除节点不存在");
        exit(0);
    }
    pPrev->next = pNext->next;
    // printf("pPrev=====%p\n",pPrev->next);这里pPrev和pNext都指向同一个地方，都是选中值的下一个地址，经过free之后，pNext变成了指向 随意 地方的野指针，有大小，有pNext自己的地址不变，只是pNext里面的值和下一个指向的地方是 野 的
    // printf("pNext=====%p\n",pNext->next);

    // free 真正释放的是 pNext 指向的那一块用 malloc 申请的内存空间,因为各个节点都是molloc出来的，一般释放了之后我们会将 pNext = NULL;这样是为了防止 pNext 变成野指针。free并不会释放 pNext 在地址空间申请的本身字节的内存，pNext 还能正常使用，只不过 free 之后 pNext 指向了一个随机的内存地址。
    // free(pNext) 之后
    // 所指的malloc释放了
    // pNext->data为随意的值
    // sizeof(pNext)大小和释放前的一样
    // pNext地址也和原来的地址一样
    // pNext->next指向了随意的方向
    free(pNext);
    // printf("free(pNext)=====%d\n",pNext->data);//为乱值
    // printf("free(pNext)=====%d\n",sizeof(pNext));
    // printf("free(pNext)=====%p\n",pNext);
    // printf("free(pNext)=====%p\n",pNext->next);//指向随意的地方
    pNext = NULL;
    return head;
}

void find_link(LinkNode head, int value)
{
    if (head->next == NULL)
    {
        printf("空链表");
        exit(0);
    }
    LinkNode p = head->next;
    int count = 1;
    while (p != NULL)
    {
        if (p->data == value)
        {
            printf("%d\n", count);
            break;
        }
        p = p->next;
        count++;
    }
    if (p == NULL)
    {
        printf("找不到");
        exit(0);
    }
}

void findIndex_link(LinkNode head, int index)
{
    if (head->next == NULL)
    {
        printf("链表为空");
        exit(0);
    }
    LinkNode rear = head->next;
    int allLength = 1;
    while (rear != NULL)
    {
        rear = rear->next;
        allLength++;
    }
    if (index >= allLength || index < 1)
    {
        printf("查询位置有问题");
        exit(0);
    }
    LinkNode p = head->next;
    if (p == NULL)
    {
        printf("查找不到");
        exit(0);
    }
    for (int i = 0; i < index - 1; i++)
    {
        p = p->next;
    }
    printf("%d\n", p->data);
}

Status static_link(LinkNode head)
{
    //TIPS: 可能是初始化的时候给head赋值了-1，所以根据head==NULL判断不了为空，可以根据head->next是否为空
    if (head->next == NULL)
    {
        return FALSE;
    }
    else
    {
        printf("%d\n",head->next->data);
        return OK;
    }
}

LinkNode clear_link(LinkNode head)
{
    if(head->next == NULL)
    {
        printf("空链表");
        exit(0);
    }
    LinkNode pCurrent=head->next;
    while(pCurrent!=NULL){
        LinkNode p=pCurrent->next;
        free(pCurrent);
        pCurrent=p;
    }
    //TIPS: 最好给head一个交代，不然很多事情都是根据head来判断是否为空的
    head->next=NULL;
    return head;
}

 

推荐阅读