请教单链表的问题

superwujc

《大话数据结构》上的实现代码：
定义：

1. typedef int Status;
   
2. typedef char ElemType;
   
3. typedef struct Node
   
4. {
   
5.     ElemType data;
   
6.     struct Node *next;
   
7. }Node;
   
8. typedef struct Node *LinkList;

复制代码

插入指定位序的元素

1. Status InsertElem (LinkList *L, int i, ElemType e)
   
2. {
   
3.     int j = 1;
   
4.     LinkList p, s;
   
5.     p = *L;
   
6.     while (p && j < i)
   
7.     {   
   
8.         p = p->next;
   
9.         j++;
   
10.     }
    
11.     if (!p && j > i)
    
12.         return ERROR;
    
13.     s = (LinkList)malloc(sizeof(Node));
    
14.     p->data = e;
    
15.     s->next = p->next;
    
16.     p->next = s;
    
17.     return OK;
    
18. }

复制代码

删除指定位序的元素

1. Status DeleteElem (LinkList *L, int i, ElemType *e)
   
2. {
   
3.     int j = 1;
   
4.     LinkList p, q;
   
5.     p = *L;
   
6.     while (p->next && j < 1)
   
7.     {
   
8.         p = p->next;
   
9.         ++j;
   
10.     }
    
11.     if (!(p->next) || j > i)
    
12.         return ERROR;
    
13.     q = p->next;
    
14.     p->next = q->next;
    
15.     *e = q->data;
    
16.     free(q);
    
17.     return OK;
    
18. }

复制代码

有2个疑问：
为什么插入元素的时候是从p开始判断非NULL，而删除操作时直接从p->next判断非NULL？
在删除元素的操作中，为什么写成++j，而不是j++，这里有什么影响结果的区别吗？

请各位指点一下，谢谢。

twtyypmb

第一个问，我觉得代码有问题，举个例子，加入链表只有一个节点，i 是等于2的
while (p && j < i)

07.    {   

08.        p = p->next;

09.        j++;

10.    }
运行到这里，p = 0，j = 2，然后就分配内存了，但是p已经等于0了，后面肯定有问题了
第二个问题，没影响

superwujc

回复 2# twtyypmb
不好意思，写错了，应该是if (!p || j > i)

1. Status InsertElem (LinkList *L, int i, ElemType e)
   
2. {
   
3.     int j = 1;
   
4.     LinkList p, s;
   
5.     p = *L;
   
6.     while (p && j < i)
   
7.     {   
   
8.         p = p->next;
   
9.         j++;
   
10.     }   
    
11.     if (!p || j > i)
    
12.         return ERROR;
    
13.     s = (LinkList)malloc(sizeof(Node));
    
14.     s->data = e;
    
15.     s->next = p->next;
    
16.     p->next = s;
    
17.     return OK;
    
18. }

复制代码

twtyypmb

p->data = e;这句有问题吧怎么可能去修改p里面的数据呢

superwujc

回复 4# twtyypmb
改了
我就是想请教一下，第二段代码为什么不是从p开始判断是否为NULL，而是直接就判断p->next

   

superwujc

回复 5# superwujc
个人觉得这里假设了一种情况：没有头结点，而且删除的不是头结点之后的第一个元素

   

twtyypmb

先把程序注释写出来，比如说插入函数，是往第i个前插入，还是后插入，看不到完整代码

twtyypmb

感觉写的好不清晰，如果是我写删除第i个元素，我会这样写
if( i < 1 )
    return -1;

while( p != NULL )
{
    if( j == i )
    {
        break;
    }
    j++;
    p = p->next;
}

if( p == NULL && j != i )
{
    puts( "not found");
}

twtyypmb

总觉得有什么不对，仔细看后发现了，这个删除函数不能删除链表尾部，例如只有2个节点，进入函数，循环一次后p指向了链表尾，p->next == NULL，退出循环，接着就return ERROR了回复 6# superwujc


   

cfan0330

第一个问题：楼主的删除程序写错了，j<1 应该是j < i，如果取p,而不是p->next,有可能在free的时候，p->next为空，导致程序出错