作业Day4: 链表函数封装；思维导图

作业：实现链表剩下的操作：

任意位置删除

按位置修改

按值查找返回地址

反转

销毁

运行结果

思维导图

作业：实现链表剩下的操作：

        1>任意位置删除

        2>按位置修改

        3>按值查找返回地址

        4>反转

        5>销毁

任意位置删除

思路：

遍历到将要删除的位置的前一个；

链接"本空间"与"下下个空间"；

释放下一个空间，并置空指针

代码：

/*
函数功能：删除指定位置数据
输入参数：链表（头节点）；删除位置
返回值：无
*/
void delData(linkListPtr H,int i)
{
    //判断地址是否合法
    //判断是否为空
    //判断删除位置是否合理:针对用户1~H->len
    if(NULL==H||ifEmpty(H)||i<=0||i>H->len)
    {
        printf("地址或插入位置不合法！\n");
        return;
    }
    //遍历到将要删除的位置的 前一个
    linkListPtr temp=H;
    i--;
    while(i--)
    {
        temp=temp->next;
    }
    //创建临时指针：指向将被"删除"的空间地址
    linkListPtr temp2=temp;
    temp2=temp2->next;
    //链接:将本节点指向下一个节点的下一个节点
    temp->next=temp->next->next;
    //释放内存 并指针置NULL
    free(temp2);
    temp2=NULL;
    //链表长度-1
    H->len--;
}

按位置修改

思路：略

代码

/*
函数功能：数据修改
参数列表：链表地址；修改位置，修改数据
返回值无
*/
void cortData(linkListPtr H,int i,DataType e)
{
    //判断地址是否合法
    //判断修改位置是否合理:针对用户1~H->len
    if(NULL==H||i<=0||i>H->len)
    {
        printf("地址或插入位置不合法！\n");
        return;
    }

    //遍历到将要修改的位置
    linkListPtr temp=H;
    while(i--)
    {
        temp=temp->next;
    }
    temp->data=e;
}

按值查找返回地址

思路：略

代码

//按值查找，返回地址
linkListPtr findData(linkListPtr H,DataType e)
{
    //判断是否合法
    //判断是否为空
    if(NULL==H||ifEmpty(H))
    {
        printf("地址或不合法！\n");
        return NULL;
    }
    linkListPtr temp=H;
    for(int i=0;i<H->len;i++)
    {
        temp=temp->next;
        if(temp->data==e)
        {
            return temp;
        }
    }
    return NULL;
}

反转

思路：

每次循环使倒数第一个、倒数第二个、倒数第三个......回头指向；

使原来的头节点指向原来的最后一位数据

使原来的首个节点置NULL

代码

void trap(linkListPtr H)
{
    //判断地址是否合法
    //判断是否为空
    if(NULL==H||ifEmpty(H))
    {
        printf("地址不合法或者链表数据为空！\n");
        return;
    }
    //创建(预备)头地址：指向最后一个元素;
    linkListPtr tempH=H;
    for(int i=0;i<H->len;i++)//定位到最后一个数据
    {
        //使（预备）头指针指向最后一个节点
        tempH=tempH->next;
    }
    
    //思路：多次循环：每次分别使最后一个、倒数第二个......回指
    linkListPtr temp=H;
    for(int i=0;i<H->len-1;i++)//决定循环总轮数
    {
        temp=H;
        for(int j=0;j<H->len-1-i;j++)//每次循环向后遍历的次数
        {
            temp=temp->next;
        }
        //回指：使下一个节点指向本节点
        temp->next->next=temp;
    }
    //当前temp所代表节点变为最后一个节点：需置空
    temp->next=NULL;
    //更新头地址
    H->next=tempH;
 
}

思路：

遍历链表:在遍历过程中，依次使遍历到的元素改变朝向：

销毁

思路

检查传入地址是否合法

释放传入地址所指向的空间

释放后，指针置空

代码

//销毁链表
void freeList(linkListPtr *HH)
{
    //判断地址是否合法
    if(NULL==*HH)
    {
        printf("地址不合法！\n");
        return;
    }
    //释放指针指向的堆区空间
    free(*HH);
    //修改传入地址的指向:将传入的指针置空
    *HH=NULL;
    //本指针也置空
    HH=NULL;
    printf("链表已销毁！\n");
}

修正：

链表地址并非连续；free不能一次性释放所有节点

//销毁链表
void freeList(linkListPtr *HH)
{
    //判断地址是否合法
    if(NULL==*HH)
    {
        printf("地址不合法！\n");
        return;
    }
    //思路:循环遍历:每次销毁最后一个
    linkListPtr temp=*HH;
    while((*HH)->next!=NULL)//循环条件:头指针指向的空间不为NULL
    {
        temp=*HH;
        while(temp->next->next!=NULL)//定位到最后一个节点   的前一个节点
        {
            temp=temp->next;
        }
        //释放指针指向的堆区空间(节点)
        free(temp->next);
        //本节点变为最后一个节点:指向置NULL
        temp->next=NULL;
    }
    //释放头节点
    free(*HH);
    //修改传入的地址指向:置NULL
    *HH=NULL;
    //本指针也置NULL
    HH=NULL;
    printf("链表已销毁！\n");
}