| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 3269 人关注过本帖
标题:数据结构单链表的插入
只看楼主 加入收藏
星野
Rank: 2
来 自:河北
等 级:论坛游民
帖 子:73
专家分:26
注 册:2016-4-13
结帖率:82.35%
收藏
已结贴  问题点数:20 回复次数:7 
数据结构单链表的插入
程序代码:
void InsertList(LinkList L,int e)
{
    if(L==NULL)
    {
        printf("线性表为空");
        return ERROR;
    }
    int i=0;
    Node *s,*p,*ptr;
    s=(Node *)malloc(sizeof(Node));
    p=L;
    s->data=data;
    while((p->data<data)&&(p->next!=NULL))
    {
        ptr=p;
        p=p->next;
        i++;
    }
    if(p->data>=data)
    {
        if(p=L)
        {
            s->next=p;
            L->next=s;
        }
        else
        {
            s->next=p;
            ptr->next=s;
        }
    }
    else
    {
        p->next=s;
        s->next=NULL;
    }
    printf("插入成功");
}


这个是老师给的代码  我着实看不懂是什么意思!
1.while((p->data<data)&&(p->next!=NULL))中p->data<data是什么意思啊?
2.ptr=p;为什么要引入ptr啊?
4.if(p->data>=data)这个又是什么?
然后为什么又要分出来p=L的情况??

好蒙圈 啊  !!
2016-09-28 18:26
书生牛犊
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:星夜征程
等 级:贵宾
威 望:10
帖 子:1101
专家分:5265
注 册:2015-10-27
收藏
得分:20 
1.当L==NULL的时候是不能执行NULL->data、NULL->Next、等等的一系列的代码,因为NULL是个只读的地址,不允许写数据,碰到->运算符也会导致程序崩溃,所以所有代码如果涉及指针,他一定会在函数刚进来的地方就做检查,检查传进来的指针是不是NULL。在后续的代码中也要不断小心谨慎,任何类似于L->NEXT->NEXT的二级运算都是危险的,因为L不是NULL不代表L->NEXT不是NULL

2.一个void函数,居然能return ERROR,这是我始料未及的。我学编程才一年,见识的比较少,我一直以为void函数是不能返回任何元素的。。。我只知道可以Exit(-1)这样让程序显示异常终止,return ERROR没见过。有机会帮我请教一下。

3.p->data 取p指针所指结构体的data成员  <data  和data比较大小(至于这个data哪来的,至少你给的这部分函数里是没有了,可能是个全局变量。但我在看到  //-4  的笔误之后意识到,你们老师估计又笔误了,因为这个Inset函数有个形参 e 他由始至终没用过。而通常在一个插入函数中,这个e就会是即将被插入的元素才是)  (p->next!=NULL)  这和我在1中提到的L->next->next讲的是一件事。就是确保p->next!=NULL了才允许执行p=p->next;再到下一个循环的p->data.

4.p=L这是个赋值语句,在if()里面做条件判断的话,他是先把L指针赋值给p指针,然后当p!=NULL就返回true,否则返回false.我赌1厘,这是你们老师的笔误,他肯定是要写p==L,因为当程序执行到那一行的时候,L本身就不可能是NULL,换句话说这个if()是永恒成立的。

撇开笔误,我们谈谈 p==L 它表示当前遍历到到的指针所指的元素和传递进来的链表表头是同一个元素,也就是说  // ->3 所标记的那个while循环必须从一开始就不成立,没执行过p=p->next p==L才是true。  L是什么,L是表头啊,这就表示旧的链表要链接到即将插入的元素之后。 处理链表头结点和处理链表中间的结点是不一样的嘛。这个你应该知道吧。。

程序代码:
void InsertList(LinkList L,int e)
{
    if(L==NULL)//  ->1.  当链表为空,输出提示并使程序错误终止
    {
        printf("线性表为空");
        return ERROR;//  ->2
    }
    int i=0;
    Node *s,*p,*ptr; //ptr指向即将被插入的元素的父节点
    s=(Node *)malloc(sizeof(Node)); //s创建生成一个新节点,这儿结点就是待会要用来插入的
    p=L; //p指针用于在L链表中遍历,寻找合适的插入位置
    s->data=data;
    while((p->data<data)&&(p->next!=NULL))// ->3.
    {
        ptr=p; // ptr保留被遍历到的元素的父节点,用于 //-5
        p=p->next;
        i++;
    }
    if(p->data>=data)// >=data  '>=' 和前面的 '>' 一样,是比较运算符,比大小的
    {
        if(p=L)//  ->4   将新插入的元素作为头结点,把旧的链表链接过来
        {
            s->next=p;
            L->next=s;
        }
        else //插入元素到链表中间某处或链表尾部
        {
            s->next=p;
            ptr->next=s; // ->5
        }
    }
    else 
    {
        p->next=s;
        s->next=NULL;
    }
    printf("插入成功");
}
   这是个跑不起来的程序,估计你们老师也是“纸上编程”,根本就没运行调试吧。当然,我没看到完整的一个程序代码,仅凭一个函数说这话,也是很不负责任的。原则上,如果你怀疑你老师有可能写错了,那么你可以把Insert函数的(int e)修改为(int data),
if(p=L)修改为if(p==L)
   这样的话,这个Insert函数所实现的就是根据读入的数据大小,每插入一个数据都保存该链表是非递减(从小到大)有序。不过,要求L本身带有数据,对于空链表,这个程序是不能正确执行的。


[此贴子已经被作者于2016-9-29 18:46编辑过]


φ(゜▽゜*)♪
2016-09-29 18:13
星野
Rank: 2
来 自:河北
等 级:论坛游民
帖 子:73
专家分:26
注 册:2016-4-13
收藏
得分:0 
回复 2楼 书生牛犊
为什么还要引入一个 ptr呢???这是什么意思啊??
2016-09-29 18:23
书生牛犊
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:星夜征程
等 级:贵宾
威 望:10
帖 子:1101
专家分:5265
注 册:2015-10-27
收藏
得分:0 
在调试代码,,没注意你的回复,我已经修改了上一楼的代码框部分注释,你看看
程序代码:
#include <iostream>
typedef struct node Node;
typedef struct node{
    int data;
    Node *next;
} *LinkList;

void InsertList(LinkList L,int data)  //修改

{
    if(L==NULL)
    {
        printf("线性表为空");
//        return ERROR;  //我的软甲报ERROR ,所以我删掉了修改为我懂的
        exit (1);

    }
    int i=0;
    Node *s,*p,*ptr;
    s=(Node *)malloc(sizeof(Node));
    p=L;
    s->data=data;
    while((p->data<data)&&(p->next!=NULL))
    {
        printf("*");//我加的标记输出,不影响代码运行,用于监测程序跑了几遍这个while循环
        ptr=p;
        p=p->next;
        i++;
    }
    if(p->data>=data)
    {     
        if(p==L)//修改

        {
            s->next=p;
            L->next=s;
        }
        else

        {
            s->next=p;
            ptr->next=s;
        }
    }
    else//此时p->next==NULL,

    {
        p->next=s;
        s->next=NULL;
    }
    printf("插入成功\n");
}

int main() {// 当前代码给你测试InsertList,如果你懂调试的话,不妨跟踪运行。

   

    Node L;
    L.data=-1;//头结点必须足够小。不能输入比头结点小的数据,当前这个函数还不够健壮。 这里写-1,你要是输入个-2的话程序就废了

    L.next=NULL;//至于一个可靠的插入函数该是什么样子的,你有需要我再另外写吧。   

         

    int temp;
    for(int i=0;i<3;i++){
        scanf("%d",&temp);
        InsertList(&L,temp);
    }
    Node* p=L.next;
    while(p){
        printf("(%d)",p->data);
        p=p->next;
    }

    return 0;
}



[此贴子已经被作者于2016-9-29 20:05编辑过]


φ(゜▽゜*)♪
2016-09-29 18:47
书生牛犊
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:星夜征程
等 级:贵宾
威 望:10
帖 子:1101
专家分:5265
注 册:2015-10-27
收藏
得分:0 
如果你测试的时候插入的数据都比我所初始化的L.data=-1 要大,程序是没问题的,
但是如果输入了“-2 ”这类比-1小的数字就不行了。程序不停地输出*,表示他在不停地执行while((p->data<data)&&(p->next!=NULL))
图片附件: 游客没有浏览图片的权限,请 登录注册

---------------
“为什么不能输入比-1小的数呢?,明明输入-2的时候程序还是输出“插入成功”但是下一次试图插入5,程序却一动不动

这算思考题,想通了。我觉得你对指针的理解程度就上了一个新台阶了。
至于怎么想,很简单,用脑子模拟程序,看看程序到底在插入一个比头结点小的数字的时候发生了什么。

φ(゜▽゜*)♪
2016-09-29 19:00
星野
Rank: 2
来 自:河北
等 级:论坛游民
帖 子:73
专家分:26
注 册:2016-4-13
收藏
得分:0 
回复 5楼 书生牛犊
   好的   我会继续努力的。谢谢版主!
2016-09-29 19:47
星野
Rank: 2
来 自:河北
等 级:论坛游民
帖 子:73
专家分:26
注 册:2016-4-13
收藏
得分:0 
以下是引用书生牛犊在2016-9-29 19:00:02的发言:

如果你测试的时候插入的数据都比我所初始化的L.data=-1 要大,程序是没问题的,
但是如果输入了“-2 ”这类比-1小的数字就不行了。程序不停地输出*,表示他在不停地执行while((p->data<data)&&(p->next!=NULL))

---------------
“为什么不能输入比-1小的数呢?,明明输入-2的时候程序还是输出“插入成功”但是下一次试图插入5,程序却一动不动

这算思考题,想通了。我觉得你对指针的理解程度就上了一个新台阶了。
至于怎么想,很简单,用脑子模拟程序,看看程序到底在插入一个比头结点小的数字的时候发生了什么。


版主这个if(p==L)的那一部分可以这样画图吗?这样画图对不对?
图片附件: 游客没有浏览图片的权限,请 登录注册
2016-10-06 17:22
书生牛犊
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:星夜征程
等 级:贵宾
威 望:10
帖 子:1101
专家分:5265
注 册:2015-10-27
收藏
得分:0 
回复 7楼 星野
if(p==L)的那一段应该是把新结点插入到旧链表的头部。

应该是  新结点->next=旧链表头结点 ;  将新结点写为链表的头结点。

我不是很明白你为什么要在下方画一个L指向新结点的箭头。。是在重设头结点吗?(我自己没画过这些东西,所以看不懂。。。)

φ(゜▽゜*)♪
2016-10-07 18:39
快速回复:数据结构单链表的插入
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.031319 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved