继续是链表

august

#include<stdio.h>
#include<stdlib.h>
struct list
{
    char data;
    struct list *next;
}*head;
setnull(struct list **p)   //置空
{
    *p=NULL;
}
int length(struct list **p) //求链表的长度
{
    int n=0;
    struct list *q=*p;
    while(q!=NULL)
    {
        n++;
        q=q->next;
    }
    return n;
}
void insert(struct list **p,char x,int i)//插入元素
{
    int j=1;
    struct list *s,*q;
    s=(struct list *)malloc(sizeof(struct list));
    s->data=x;
    s->next=NULL;
    q=*p;
    if(i==1)
    {
        s->next=q;
        *p=s;
    }
    else
    {
        while(j<i-1&&q->next!=NULL)
        {
            q=q->next;
            j++;
        }
        if(j==i-1)
        {
            if(q->next!=NULL)
            {
            s->next=q->next;
            q->next=s;
            }
            else
            {
                q->next=s;
            }
        }
        else
            printf("位置不正确.");
    }
}
void del(struct list **p,int i)//删除链表中的元素
{
    int j=1;
    struct list *t,*q;
    q=*p;
    if(i==1)
    {
        t=q;
        *p=q->next;
    }
    else
    {
        while(j<i-1&&q->next!=NULL)
        {
            q=q->next;
            j++;
        }
        if(j==i-1)
        {
            t=q->next;
            q->next=t->next;
        }
        else
            printf("位置不对.");
    }
        if(t!=NULL)
            free(t);
   
}
void display(struct list **p)//显示链表中的元素
{
    struct list *q;
    q=*p;
    printf("单链表显示:");
    if(q==NULL)
        printf("链表为空！");
    else if(q->next==NULL)
        printf("%c",q->data);
    else
    {
        while(q->next!=NULL)
        {    printf("%c-",q->data);
            q=q->next;
        }
        printf("%c",q->data);
    }
    printf("\n");

}
void main()
{
   
    setnull(&head);
   
   
    insert(&head,'a',1);
    insert(&head,'c',2);
    insert(&head,'b',2);
   
   
    display(&head);
    del(&head,1);
    display(&head);
}

在删除元素的这一个部分
void del(struct list **p,int i)//删除链表中的元素
{
    int j=1;
    struct list *t,*q;
    q=*p;
    if(i==1)
    {
        t=q;
        *p=q->next;
    }
    else
    {
        while(j<i-1&&q->next!=NULL)
        {
            q=q->next;
            j++;
        }
        if(j==i-1)
        {
            t=q->next;
            q->next=t->next;
        }
        else
            printf(\"位置不对.\");
    }
        if(t!=NULL)
            free(t);
   
}
为什么当删除一位置的这个元素时一定要写成这样
  if(i==1)
    {
        t=q;
        *p=q->next;
    }
其实删除位置是一的话,只需要这一句就行了, *p=q->next;   为什么还要加上一句 t=q;  呢?
把这句去掉了,就不行了,到底为什么会这样呢?这句 t=q; 又是什么意思呢?

duzhi5368

- -若是没有t=q的话,最后这句
   if(t!=NULL)
            free(t);
就不会执行,因为t仅仅声明没有赋值,默认是NULL,所以,头结点(也是唯一的结点)q没有释放.
反复的执行删除单结点链表最后将导致内存资源没有释放,内存溢出.

另PS句,这段代码不看也罢,写的水平实在一般,变量名标识极差.只能让原本郁闷的人更加郁闷摸不清头脑.另外方法过于简单,技巧性低...呃,不说了..若是新人练习之作的话可以理解,若是教材上的代码,可以说,这教材的实用性值得怀疑. [s:7]

duzhi5368

另外,请多注意双向链表,就个人所见,DoubleList明显使用几率远大于SingleList [s:2]

august

引用第1楼duzhi5368于2007-06-20 10:40发表的  :
- -若是没有t=q的话,最后这句
   if(t!=NULL)
            free(t);
就不会执行,因为t仅仅声明没有赋值,默认是NULL,所以,头结点(也是唯一的结点)q没有释放.
反复的执行删除单结点链表最后将导致内存资源没有释放,内存溢出.
.......

这确实是教材里抄下来的,而且是清华大学出版社出版的[s:4]
而你说的严蔚敏，吴伟民：《数据结构》又不知从何找,现在数据结构的书都不好找了[s:6]

coolpay64

這些都是網上找的，wiki也不錯