B010 有序链表插入新节点 ★★

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

所属年份:2010.9;2011.3;2012.3

下列给定程序中已建立一个带头结点的单向链表,链表中的各结点按结点数据域中的数据递增有序链接。函数fun的功能是:把形参x的值放入一个新结点并插入链表中,使插入后各结点数据域中的数据仍保持递增有序。

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

#include    <stdio.h>
#include    <stdlib.h>
#define    N    8

typedef  struct list {
    int  data;
    struct list  *next;
} SLIST;

void fun( SLIST  *h, int  x)
{
    SLIST  *p, *q, *s;
    s=(SLIST *)malloc(sizeof(SLIST));
    /**********found**********/
    s->data=___1___;
    q=h;
    p=h->next;
    while(p!=NULL && x>p->data) {
        /**********found**********/
        q=___2___;
        p=p->next;
    }
    s->next=p;
    /**********found**********/
    q->next=___3___;
}

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

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

int main()
{
    SLIST  *head;
    int  x;
    int  a[N]= {11,12,15,18,19,22,25,29};
    head=creatlist(a);
    printf("\nThe list before inserting:\n");
    outlist(head);
    printf("\nEnter a number :  ");
    scanf("%d",&x);
    fun(head,x);
    printf("\nThe list after inserting:\n");
    outlist(head);
    return 0;
}

【参考答案】

(1)x  (2)p  (3)s

【考点分析】
本题考查: 链表的基本操作。了解链表的基本思想和相关算法,理解有关链表插入及删除时指针移动的先后顺序问题,注意指针的保存和归位。

【解题思路】
填空1:将形参x赋值给结点的数据域。
填空2和填空3:将新的结点和原有链表中结点进行比较。