链表例题中的小错误

编程思想:编程时先搭好框架,比较难处理的部分用汉字表示,以后慢慢一步一步进行处理

空链的定义

#include<stdio.h>

typedef struct POINT{
    int row;
    int col;
    struct POINT *next;
}POINT; 


void main(void){
    POINT head1 = {0};  

//此为不完全赋初值,指针被赋值为NULL。若不赋值,则head1中的三个成员是有值的,其值为垃圾数据
//此链为一个空链(不关心数据域,只要指针域为空即可),空链是链表的起始点。
}

链表例题中的小错误

输出链表中的错误

void showPoints(POINT head){
    POINT *p;

 

    printf("\n输入的点坐标如下:\n");
    //for(p = head.next; p->next; p = p->next){   //错误形式     //分析:若终止条件写成p->next,则无法输出最后一个点
    for(p = head.next; p; p = p->next){              //正确形式      //小错误:for(p = head.next, p, p = p->next){
        if(p == head.next){                                  //只是为了让格式更好看
            showPoint(*p);
        }else{
            printf(",");                                         //只是为了让格式更好看
            showPoint(*p);
        }
    }
}
1)for循环终止条件的确定

2)for(  ;   ;)

3)格式问题

 

销毁链表中的错误

void destroyPointLink(POINT *head){
    POINT *p;

 

//正确形式
    while(head->next){
        p = head->next;                  
        head->next = p->next;
        free(p);
    }

 

/*  //错误形式2:

    //错误形式2分析:p = head->next; head->next = p->next; 这两条语句可以实现p的移位,所以不需要for循环进行移位
    while(head->next){
        for(p = head->next; p->next; p = p->next){  
            head->next = p->next;
            free(p);
        }
*/

 

/*     //错误形式1:
    while(head->next){
        for(p = head->next; p->next; p = p->next)  
            ;
        free(p);
    }
*/   
}

链表例题中的小错误

错误形式1分析如下:

一般人的思维都是从后往前释放,则:

1)第一次循环时,找到末节点,释放。灰色表示已经释放,但是释放之后,p节点的前一个节点的链域值并未受到任何改变,依然指向一个已经释放的空间
2)当下一个循环,从第一个节点开始,遍历到好像应该是最后一个节点(灰色前面的那个节点),它的链域值不为NULL,
还要继续向下移动,这样p指向一个已经释放的空间,指向没有关系,但是要进行访问就不可以了,这就是非法内存访问。

正确思路分析如下:

链表例题中的小错误

 

正确形式为从前往后释放,理解如上,终止条件理解如下:

链表例题中的小错误

插入链表中的分析

void insertPoint(POINT *head){
    /*
    1.输入新点坐标
    2.输入指定点坐标
    3.找与oldPoint的row和col相同的前驱节点
    4.完成插入
    */

 

    POINT *p;    //需要插入的新点
    POINT oldPoint; //需要插入新点的位置节点
    int row;
    int col;
    POINT *q;   //q表示oldPoint的前驱节点

 

    //1.输入新点坐标(newPoint)
    printf("请输入一个新点的坐标(例如:3 4),任意一个输入为0表示结束:");
    scanf("%d%d", &row, &col);

    p = (POINT *)malloc(sizeof(POINT));    //malloc()一定要记得加头文件
    p->row = row;
    p->col = col;
    p->next = NULL;

 

    //2.输入指定点坐标(oldPoint)
    printf("请输入指定插入的点(进行左插入,若指定点不存在,则新点追加到末尾)");
    scanf("%d%d", &oldPoint.row, &oldPoint.col);

 

    //3.找与oldPoint的row和col相同的前驱节点
    q = findPrePoint(*head, oldPoint);
        //1. q == NULL;                                  用户指定的点是第一个有效节点
         //2. q != NULL && q->next == NULL;  说明m指向末节点,表明用户所指定的点不存在;
        //3. q != NULL && q->next != NULL;  说明用户指定的点不但存在,而且不是第一个有效节点

 

    //4.完成插入

 

//自己代码
    if(q == NULL){
        p->next = head->next;
        head->next = p;
    }else if(q->next == NULL){
        q->next = p;
    }else{
        p->next = q->next;
        q->next = p;
    }

 

//老师代码(代码优化)
    /*
    if(q = NULL){
        q = head;
    }
    p->next = q->next;
    q->next = p;
*/
}

 

插入时分析如下:
 

链表例题中的小错误

排序时的分析

问题:为什么排序时还要继续交换指针域?

解答:见博客 https://blog.csdn.net/tennysonsky/article/details/51076340 非常详细

 

链表例题中的小错误

链表例题中的小错误