分别用递归方式和非递归方式实现带头结点单链表的顺序检索问题是最后的反馈不正常 - C语言论坛

已结贴√ 问题点数：20 回复次数：2

分别用递归方式和非递归方式实现带头结点单链表的顺序检索问题是最后的反馈不正常

#include <stdlib.h>
#include <stdio.h>
typedef int datatype;
typedef struct node
{ datatype data;
  struct node *next;
}linknode,*linklist;

/*尾插法建立带头结点单链表*/
linklist creat()
{ linklist head,r,s;
  datatype x;
  head=r=(linklist)malloc(sizeof(linknode));
  head->next=NULL;
  printf("请输入一组整型数据，以空格分隔，以0结束输入:\n");  scanf("%d",&x);
  while(x!=0)
    { s=(linklist)malloc(sizeof(linknode));
      s->data=x;
      r->next=s;
      r=s;
      scanf("%d",&x);
     }
  r->next=NULL;
  return head;
}

/*输出带头结点单链表*/
void print(linklist head)
{ linklist p;
  p=head->next;
  printf("带头结点单链表为：");
  while(p)
   { printf("%5d",p->data);
     p=p->next;
    }
}

linklist linkSearch1(linklist head, datatype key)  /*带头结点单链表的非递归检索，将本函数补充完整。也可以不用我给的函数原型，自己写一个函数*/
{
linklist p=head->next;
while(p&&p->data!=key)
p=p->next;
return p;
}

linklist linkSearch2(linklist head, datatype key)  /*带头结点单链表的递归检索，将本函数补充完整。也可以不用我给的函数原型，自己写一个函数*/
{
linklist p=head;
if(p&&p->data!=key)
    linkSearch2(p->next,key);
return p;
}

void main()
{ linklist head,p;
  int key;

  head=creat();   /*尾插法建立带头结点单链表*/
  print(head);    /*输出带头结点单链表*/

  printf("\n请输入要查找的关键字：");  scanf("%d",&key);

  /*在此处完成对linkSearch1函数和linkSearch2函数的调用，并进行测试。如果是自己写的函数，同样完成函数的调用和测试*/
linklist k;
k=linkSearch1(head,key);
if(k->data==key)
puts("yes");
else puts("no");
linklist j;
j=linkSearch2(head,key);
if(j->data==key)
puts("yes");
else puts("no");
}

搜索更多相关主题的帖子: head　结点　函数　单链表　 key　

第 2 楼

得分:5

错误太多，你还不如将原始题目贴出来呐。否则别人不知道哪些允许改动

假如全部允许改动的话

程序代码：

#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>

typedef int slist_valuetype;
#define slist_valuetype_printformat "d"

struct slist_node
{
    slist_valuetype data;
    struct slist_node* next;
};

struct slist_node* slist_create( slist_valuetype first, ... )
{
    va_list args;
    va_start(args, first);

    struct slist_node* head = NULL;
    struct slist_node** last = &head;
    for( slist_valuetype v=first; v!=0; v=va_arg(args,slist_valuetype) )
    {
        (*last) = malloc( sizeof(struct slist_node) );
        (*last)->data = v;
        (*last)->next = NULL;
        last = &( (*last)->next );
    }

    va_end(args);
    return head;
}

void slist_print( const struct slist_node* head )
{
    printf( "slist [" );
    if( !head )
        printf( "]\n" );
    for( const struct slist_node* p=head; p; p=p->next )
        printf( "%" slist_valuetype_printformat "%s", p->data, p->next?", ":"]\n" );
}

struct slist_node* slist_find( const struct slist_node* head, slist_valuetype key )
{
    struct slist_node* p = (struct slist_node*)head;
    for( ; p && p->data!=key; p=p->next );
    return p;
}

struct slist_node* slist_find_recursive( const struct slist_node* head, slist_valuetype key )
{
    return (!head || head->data==key) ? (struct slist_node*)head : slist_find_recursive(head->next,key);
}

void test_slist_find( const struct slist_node* head, slist_valuetype key );

int main( void )
{
    {
        struct slist_node* head = slist_create( 0 );
        slist_print( head );
    }
    {
        struct slist_node* head = slist_create( 1, 0 );
        slist_print( head );
    }
    {
        struct slist_node* head = slist_create( 1, 2, 0 );
        slist_print( head );
    }
    {
        struct slist_node* head = slist_create( 1, 2, 3, 0 );
        slist_print( head );
    }
    putchar( '\n' );

    ///////////////////////////////////////

    struct slist_node* head = slist_create( 1, 2, 3, 0 );
    slist_print( head );
    test_slist_find( head, 1 );
    test_slist_find( head, 2 );
    test_slist_find( head, 3 );
    test_slist_find( head, 4 );
}

void test_slist_find( const struct slist_node* head, slist_valuetype key )
{
    struct slist_node* p = slist_find( head, key );
    printf( "正经查找 %" slist_valuetype_printformat ": %s\n", key, p?"yes":"no" );

    struct slist_node* q = slist_find_recursive( head, key );
    printf( "递归查找 %" slist_valuetype_printformat ": %s\n", key, q?"yes":"no" );
}

输出

slist []
slist [1]
slist [1, 2]
slist [1, 2, 3]

slist [1, 2, 3]
正经查找 1: yes
递归查找 1: yes
正经查找 2: yes
递归查找 2: yes
正经查找 3: yes
递归查找 3: yes
正经查找 4: no
递归查找 4: no

第 3 楼

得分:15

修改如下，供参考：

程序代码：

#include <stdlib.h>
#include <stdio.h>
typedef int datatype;
typedef struct node
{
    datatype   data;
    struct node* next;
}linknode, * linklist;


/*尾插法建立带头结点单链表*/
linklist creat()
{
    linklist head, r, s;
    datatype x;
    head = r = (linklist)malloc(sizeof(linknode));
    head->next = NULL;
    printf("请输入一组整型数据，以空格分隔，以0结束输入:\n");  
    scanf("%d", &x);
    while (x != 0)
    {
        s = (linklist)malloc(sizeof(linknode));
        s->data = x;
        r->next = s;
        r = s;
        scanf("%d", &x);
    }
    r->next = NULL;
    return head;
}


/*输出带头结点单链表*/
void print(linklist head)
{
    linklist p = NULL;
    if (!head || !head->next)  // 修改
        printf("NULL");
    else {
        p = head->next;
        printf("带头结点单链表为：");
        while (p)
        {
            printf("%5d", p->data);
            p = p->next;
        }
    }
    printf("\n");
}

linklist linkSearch1(linklist head, datatype key)  /*带头结点单链表的非递归检索，将本函数补充完整。也可以不用我给的函数原型，自己写一个函数*/
{
    linklist p = NULL;
    if (!head || !head->next) // 修改
        p = NULL;
    else {
        p = head->next;
        while (p && p->data != key)
            p = p->next;
    }
    return p;
}

linklist linkSearch2(linklist head, datatype key)  /*带头结点单链表的递归检索，将本函数补充完整。也可以不用我给的函数原型，自己写一个函数*/
{
    if (!head || !head->next) // 修改
        return NULL;
    linklist p = head->next; // 修改 
    if (p && p->data != key)
        p = linkSearch2(p, key); // 修改
    return p;
}

void main()
{
    linklist head, p;
    int key;

    head = creat(); 
    print(head);   

    printf("\n请输入要查找的关键字：");  
    scanf("%d", &key);

    /*在此处完成对linkSearch1函数和linkSearch2函数的调用，并进行测试。如果是自己写的函数，同样完成函数的调用和测试*/
    linklist k;
    k = linkSearch1(head, key);
    if (k && k->data == key)  // 修改
        puts("yes");
    else 
        puts("no");
    linklist j;
    j = linkSearch2(head, key);
    if (j && j->data == key)  // 修改
        puts("yes");
    else 
        puts("no");
}