mzozm 发表于 2006-9-16 17:08

对给定的单链表L, 编写一个删除L中值为x的结点的直接前驱结点的算法

如题
谢谢哦! :hug:

海上飞洪 发表于 2006-9-16 17:29

delete(SqList &L)
{
SqList p,q;
p=L->next;
while(p->next->data!=x && p)
   p=p->next;
q=p->next;
p=q->next;
delete q;
}

iptton 发表于 2006-9-16 18:05



int delPreByVal(int v){
/*特殊情况为要删的是头元素时*/
    TList *tmp,*ptr;
    printf("Enter del function!");
    ptr=head;
    tmp=ptr;
    while(ptr->next!=NULL){
      if(ptr->next->value==v){
            if(head->next==ptr){
                head=ptr->next;
                break;
            }else{
                tmp->next=ptr->next;
                free(ptr);
                break;
            }
      }
      tmp=ptr;
      ptr=ptr->next;
    }
}


[ 本帖最后由 iptton 于 2006-9-16 18:12 编辑 ]

iptton 发表于 2006-9-16 18:13

完整例子：

/*HELLO.C -- Hello, world */

#include "stdio.h"
#include "conio.h"
typedef struct list{
   int value;
   struct list * next;
}TList;
intdelPreByVal(int value);
TList * setRandomValue(int account);
void showAll();
TList * head;
main()
{
    int v;
    head = setRandomValue(10);
    printf("Befor del:");
    showAll();
    printf("Enter the value:");
    scanf("%d",&v);
    delPreByVal(v);
    printf("After del:");
    showAll();
    getch();
}
/*建立链表*/
TList * setRandomValue(int j){
    int tmp;
    TList *head=(TList *)malloc(sizeof(struct list));
    TList *ptr=head;
    if(j<1)return NULL;
    do{
      srand(j);
      tmp=rand();
      ptr->value=tmp;
      ptr->next=(TList *)malloc(sizeof(struct list));
      ptr=ptr->next;
      ptr->next=NULL;
    }while(j--);
    return head;
}
int delPreByVal(int v){
/*特殊情况为要删的是头元素时*/
    TList *tmp,*ptr;
    printf("Enter del function!");
    ptr=head;
    tmp=ptr;
    while(ptr->next!=NULL){
      if(ptr->next->value==v){
            if(head->next==ptr){
                head=ptr->next;
                break;
            }else{
                tmp->next=ptr->next;
                free(ptr);
                break;
            }
      }
      tmp=ptr;
      ptr=ptr->next;
    }
}
void showAll(){
    TList *tmp=head->next;

    while(tmp!=NULL){
      printf("%d ",tmp->value);
      tmp=tmp->next;
    }
}


在WIN TC 下测试通过

hjack 发表于 2006-9-20 23:20

原帖由 海上飞洪 于 2006-9-16 17:29 发表
delete(SqList &L)
{
SqList p,q;
p=L->next;
while(p->next->data!=x && p)
   p=p->next;
q=p->next;
p=q->next;
delete q;
}
好像有错.
如果P指向null,p->next会指向野地址.
:time:

而且这里总会delete q的.但实际上有可能不存在这样的结点的.

[ 本帖最后由 hjack 于 2006-9-20 23:27 编辑 ]

hjack 发表于 2006-9-20 23:24

回复 #1 mzozm 的帖子

对于有头结点的链表L

p = q = L;
while( p->next && p->next->value!=x ){
q = p;
p = p->next;
}
if ( q!=L && p->next!=NULL ){
q->next = p->next;
delete p;
}

iptton 发表于 2006-9-20 23:44

为什么两位都直接把要删除头节点的情况跳过不做处理的？

powerwind 发表于 2006-9-21 01:43

其实头节点也可当作不是任何节点的直接前驱结点.
所以,当 head->next->value==v 时,可认为无直接前驱结点.
那两位可能是这样考虑的.

hjack 发表于 2006-9-22 00:51

为了回答IP,特翻了翻数据结构.
"有时我们在单链表的第一个结点之前附设一个结点.称之为头结点.头结点的数据域可以不存储任何信息,也可存表的长度等信息,头结点的指针域存储指向第一个结点的指针."
所以这个头结点是不删的.也就是说真正存数据的是第二个结点开始的.

iptton 发表于 2006-9-22 11:54

原来是基础知识没掌握。。。

书上对链表的定义与我脑中的定义有出入。。。。

呵呵（看来要认真点把数据结构看上几次才行。。。）
页: [1]
查看完整版本: 对给定的单链表L, 编写一个删除L中值为x的结点的直接前驱结点的算法