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

mzozm

如题
谢谢哦! :hug:

海上飞洪

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

1. 
   
2. 
   
3. int delPreByVal(int v){
   
4. /*特殊情况为要删的是头元素时*/
   
5.     TList *tmp,*ptr;
   
6.     printf("Enter del function!");
   
7.     ptr=head;
   
8.     tmp=ptr;
   
9.     while(ptr->next!=NULL){
   
10.         if(ptr->next->value==v){
    
11.             if(head->next==ptr){
    
12.                 head=ptr->next;
    
13.                 break;
    
14.             }else{
    
15.                 tmp->next=ptr->next;
    
16.                 free(ptr);
    
17.                 break;
    
18.             }
    
19.         }
    
20.         tmp=ptr;
    
21.         ptr=ptr->next;
    
22.     }
    
23. }
    

复制代码

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

iptton

完整例子：

1. 
   
2. /*  HELLO.C -- Hello, world */
   
3. 
   
4. #include "stdio.h"
   
5. #include "conio.h"
   
6. typedef struct list{
   
7.    int value;
   
8.    struct list * next;
   
9. }TList;
   
10. int  delPreByVal(int value);
    
11. TList * setRandomValue(int account);
    
12. void showAll();
    
13. TList * head;
    
14. main()
    
15. {
    
16.     int v;
    
17.     head = setRandomValue(10);
    
18.     printf("Befor del:");
    
19.     showAll();
    
20.     printf("Enter the value:");
    
21.     scanf("%d",&v);
    
22.     delPreByVal(v);
    
23.     printf("After del:");
    
24.     showAll();
    
25.     getch();
    
26. }
    
27. /*建立链表*/
    
28. TList * setRandomValue(int j){
    
29.     int tmp;
    
30.     TList *head=(TList *)malloc(sizeof(struct list));
    
31.     TList *ptr=head;
    
32.     if(j<1)return NULL;
    
33.     do{
    
34.         srand(j);
    
35.         tmp=rand();
    
36.         ptr->value=tmp;
    
37.         ptr->next=(TList *)malloc(sizeof(struct list));
    
38.         ptr=ptr->next;
    
39.         ptr->next=NULL;
    
40.     }while(j--);
    
41.     return head;
    
42. }
    
43. int delPreByVal(int v){
    
44. /*特殊情况为要删的是头元素时*/
    
45.     TList *tmp,*ptr;
    
46.     printf("Enter del function!");
    
47.     ptr=head;
    
48.     tmp=ptr;
    
49.     while(ptr->next!=NULL){
    
50.         if(ptr->next->value==v){
    
51.             if(head->next==ptr){
    
52.                 head=ptr->next;
    
53.                 break;
    
54.             }else{
    
55.                 tmp->next=ptr->next;
    
56.                 free(ptr);
    
57.                 break;
    
58.             }
    
59.         }
    
60.         tmp=ptr;
    
61.         ptr=ptr->next;
    
62.     }
    
63. }
    
64. void showAll(){
    
65.     TList *tmp=head->next;
    
66. 
    
67.     while(tmp!=NULL){
    
68.         printf("%d ",tmp->value);
    
69.         tmp=tmp->next;
    
70.     }
    
71. }
    

复制代码

在WIN TC 下测试通过

hjack

原帖由 海上飞洪 于 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

对于有头结点的链表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

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

powerwind

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

hjack

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

iptton

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

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

呵呵（看来要认真点把数据结构看上几次才行。。。）