| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2994 人关注过本帖
标题:[求助]无头结点的动态单链表上INSERT算法,是否正确?
只看楼主 加入收藏
舞踏祭
Rank: 1
等 级:新手上路
帖 子:8
专家分:0
注 册:2005-9-26
收藏
 问题点数:0 回复次数:10 
[求助]无头结点的动态单链表上INSERT算法,是否正确?
试写一算法,在 无头结点 的动态单链表上实现线性表操作 INSERT(L, i, b)







见到有个人是这样写的:

Status Insert(LinkList &L,int i,int b)
{//在无头结点链表L的第i个元素之前插入元素b
  p = L;
  q = (LinkList)malloc(sizeof(LNode));
  q.data = b;
  if (i == 1)
  {
    q.next = p;
    L = q;                             //插入在链表头部
  }
  else
  {
    while(--i>1)
    {
       p=p->next;
    }
    q->next = p->next;
    p->next = q;                     //插入在第i个元素的位置
  }
}//Insert




看不明白,所以我写了一个:

Status Insert(LinkList &L,int i,int b)
{                                     //在无头结点链表L的第i个元素之前插入元素b
    if (i <= 0)                        //位置不合法
    {
        return ERROR;
    }
    label = L;
    new = (LinkList)malloc(sizeof(LNode));   //给新元素结点初始化
    new->data = b;
    new->next = NULL;
    if (i == 1)                          //当插入位置在第一个元素之前时
    {
        if (L == NULL)                    //如果L此时为空表(没有首元结点)
        {
           new->next = NULL;
           L = new;
        }
        else                              //如果L此时非空(有首元结点)
        {
            new->next = label->next;
            label->next = new;
        }
    }
    else                                 //当插入位置不在第一个元素前时
    {
        j = 0;                           //按照1楼的提醒,这儿作了修改
        while (lable->next != NULL && j<i-1)
        {
            label = label->next;
            j++;
        }
        if (j != i-1) return ERROR;
                                              //不存在第i个元素,则ERROR
        new->next = label->next;
        label->next = new;           //插入在第i个元素的位置,原结点变为第i+1个
    }
    return(OK);
}//Insert



其中,

typedef struct LNode
{
  Elemtype data;
  struct LNode *next;
}LNode, *LinkList;



不知道是否两个都正确?

另:
头指针是指向链表中第一个结点(或为头结点或为首元结点)的指针;
头结点是在链表的首元结点之前附设的一个结点;数据域内只放空表标志和表长等信息
首元结点是指链表中存储线性表中第一个数据元素a1的结点。


头指针本身没有数据域,只是一个指针,不具有LNode型结点构造.L是头指针.

[此贴子已经被作者于2005-10-4 2:08:17编辑过]


搜索更多相关主题的帖子: 结点 INSERT 单链 算法 动态 
2005-09-26 07:25
starrysky
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:华中科技大学EI -T0405
等 级:版主
威 望:11
帖 子:602
专家分:1
注 册:2005-9-12
收藏
得分:0 
楼主列出的两种算法都是正确的, 但第一种算法简洁一些, 不过没有考虑i 的出错情况, 楼主给出的第2种酸法考虑全面一些. 但语言不够简洁(比如i=1时的两种情况实际上可并成一种情况), 如果将两者结合起来就完美了. 建议楼主在看懂第一种算法后对其进行修改, 加入出错处理语句. 还有一点, 楼主第2 种算法没有考虑到空间分配失败时的出错处理,
new = (LinkList)malloc(sizeof(LNode));
if (!new)   exit(ERROR);
另外,  我好象记得头结点又叫首元结点, 楼主的注释似乎有点概念上的错误(也许是我记错了)

我的征途是星辰大海
2005-10-02 16:55
fire77
Rank: 1
等 级:新手上路
帖 子:43
专家分:0
注 册:2005-9-19
收藏
得分:0 
Status Insert(LinkList &L,int i,int b) {//在无头结点链表L的第i个元素之前插入元素b listnode *p,*q;------------定义两个结点型指针 p = L;--------链表头节点地址给p int j=0; while(p->next&&j<i-1)-----------找第i-1个节点 { p=p->next; j++; } if( i-1==j ) ----------那么p就是找到的i-1I个节点 { if(p==NULL) cout<<" i position error";------------i位置出错 q = (LinkList)malloc(sizeof(LNode)); q.data = b; q->next=p->next; p->next=q; } else return error;

[此贴子已经被作者于2005-10-8 10:33:05编辑过]


2005-10-02 17:44
fire77
Rank: 1
等 级:新手上路
帖 子:43
专家分:0
注 册:2005-9-19
收藏
得分:0 
整个题目的思路应该是这样的:
如果表是空表,那么进行插入就等价于头插法或尾插发建表,那么应用头插法中的程序简单些,并且i值只能为0
如果表不空,那么就按我上面写的这个程序,先找出i 位置上的节点,做插入运算。这部分的难点在于找i 节点,一般都是用个查找函数*getnode(linklist L,int i){略},在这个函数里做i值合法否的判断
以上程序已经把这个函数内容写进去了,你可以自己再琢磨琢磨。
欢迎大家一起来讨论

2005-10-02 17:59
fire77
Rank: 1
等 级:新手上路
帖 子:43
专家分:0
注 册:2005-9-19
收藏
得分:0 
本题说无头节点,实际上对于非空表且i 值不为0的情况根本就没有影响,所以说本题的难度就在于表为空时怎么写进行头插或尾插的程序,以及当表不空但i值为0的写法。
搞清楚思路,不难写出。

2005-10-02 18:02
fire77
Rank: 1
等 级:新手上路
帖 子:43
专家分:0
注 册:2005-9-19
收藏
得分:0 
Status Insert(LinkList &L,int i,int b) {//在无头结点链表L的第i个元素之前插入元素b listnode *p,*q;------------定义两个节点 p = L;--------链表头节点地址给P if(L==NULL&&i==0)------------如果表空那么i值也只有0时才有意义 { /*无头节点的头插法*/ q = (LinkList)malloc(sizeof(LNode)); q->data = b; q->next=L; L=q; return L; } else ----------------------非空表插入,为了节省时间把GETNODE 函数写在里面了,所以结构不够清晰 { int j=0; while(p->next&&j<i)-------找第i个节点 { p=p->next; j++; } if(i==j) ----------那么P就是找到的第I个节点 { if(p==NULL) { cout<<" i position error"; return 0;}------------i位置出错 q = (LinkList)malloc(sizeof(LNode)); q.data = b; q->next=p->next; p->next=q; }
} }

2005-10-02 18:12
starrysky
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:华中科技大学EI -T0405
等 级:版主
威 望:11
帖 子:602
专家分:1
注 册:2005-9-12
收藏
得分:0 
第3楼给出的算法好象有问题, 比如i=1时, 要插入的结点实际上插在了第1个结点后面, 即第2个结点前面.
我认为j的初值应该为1, 即int j = 1.

我的征途是星辰大海
2005-10-03 11:29
starrysky
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:华中科技大学EI -T0405
等 级:版主
威 望:11
帖 子:602
专家分:1
注 册:2005-9-12
收藏
得分:0 
实际上楼主给出的第1种"看不太明白"的算法已经很完善了, 包括了链表为空的情况, 只是没有考虑 i 的出错,
不知道3楼的看懂了那种算法没有.

我的征途是星辰大海
2005-10-03 11:38
fire77
Rank: 1
等 级:新手上路
帖 子:43
专家分:0
注 册:2005-9-19
收藏
得分:0 
你可以将我写的程序运行下啊,绝对无错!标准答案!

2005-10-03 15:16
舞踏祭
Rank: 1
等 级:新手上路
帖 子:8
专家分:0
注 册:2005-9-26
收藏
得分:0 

2005-10-04 02:11
快速回复:[求助]无头结点的动态单链表上INSERT算法,是否正确?
数据加载中...
 
   



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

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