B034 单向链表逆置 ★★★

01-程序填空题 软件121, 唐鼎威 814浏览

所属年份:2010.9;2012.3

给定程序中,函数fun的功能是将不带头结点的单向链表逆置,即若原链表中从头至尾结点数据域依次为 2、4、6、8、10。逆置后,从头至尾结点数据域依次为10、8、6、4、2。

请在程序的下画线处填入正确的内容并把下画线删除,使程序得出正确的结果。

#include  <stdio.h>
#include  <stdlib.h>
#define    N    5
typedef struct node {
    int  data;
    struct node  *next;
} NODE;

/**********found**********/
__1__ * fun(NODE *h)
{
    NODE  *p, *q, *r;
    p = h;
    if (p == NULL)
        return NULL;
    q = p->next;
    p->next = NULL;
    while (q) {
        /**********found**********/
        r = q->__2__;
        q->next = p;
        p = q;
        /**********found**********/
        q = __3__ ;
    }
    return  p;
}

NODE *creatlist(int  a[])
{
    NODE  *h,*p,*q;
    int  i;
    h=NULL;
    for(i=0; i<N; i++) {
        q=(NODE *)malloc(sizeof(NODE));
        q->data=a[i];
        q->next = NULL;
        if (h == NULL)  h = p = q;
        else    {
            p->next = q;
            p = q;
        }
    }
    return  h;
}

void outlist(NODE  *h)
{
    NODE  *p;
    p=h;
    if (p==NULL)  printf("The list is NULL!\n");
    else {
        printf("\nHead  ");
        do {
            printf("->%d", p->data);
            p=p->next;
        } while(p!=NULL);
        printf("->End\n");
    }
}

int main()
{
    NODE  *head;
    int  a[N]= {2,4,6,8,10};
    head=creatlist(a);
    printf("\nThe original list:\n");
    outlist(head);
    head=fun(head);
    printf("\nThe list after inverting :\n");
    outlist(head);
    return 0;
}

【参考答案】

(1)NODE(2)next (3)r

【解题思路】

填空1:本题考查了函数指针变量的函数返回值的类型,* fun(NODE *h)的返回值为p,而p的数据类型为NODE,因此本空应该填写NODE。
填空2:从此空的形式p->可知本空应该填写next。
填空3:本题要求将不带头结点的单向链表逆置,为了使q的指针向后移,此空应该填写r。