Question

设顺序表VA中的数据元素递增有序。写一算法，将X插入到表的适当位置，从保持该表的有序性。

用数据结构（C语言）编写

Answer 1

//函数说明：
//先输入n，表示首先建立一个链表的元素个数
//然后输入n个元素，建立有序链表
//再输入要插入的元素，调用函数插入
//输出最终链表
#include <stdio.h>
#include <stdlib.h>

struct node
{
    int data;
    struct node *next;
};

void insert(struct node *head,int x)//链表的插入函数
{
    struct node *p = head->next,*q = head;
    struct node *r = (struct node *)malloc(sizeof(struct node));//给新链结开内存
    r->data = x;
    while(p)//当游动指针不为空时
    {
        if(r->data < p->data)//寻找应该插入的位置
        {
            q->next = r;
            r->next = p;
            break;//插入完成后跳出（必须要跳出）
        }
        q = p;
        p = p->next;//如果没找到合适的插入点，继续向后找
    }
    if(!p)//遍历完整个链表依然没找到插入点，那这个节点一定比所有元素都大
    {
        q->next = r;
        r->next = NULL;//插入到最后
    }
}

void show(struct node *head)
{
    struct node *p = head->next;
    while(p)
    {
        printf("%d",p->data);
        if(p->next)
            printf(" ");
        p = p->next;
    }
    printf("\n");
}

int main()
{
    struct node *head = (struct node *)malloc(sizeof(struct node));//给头结点开内存
    head->next = NULL;//当前无信息存储，头结点的下一个节点不存在，指针设为空
    int x,n,sr;
    printf("请输入要输入数的个数：\n");
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)//读入n个数，建立链表
    {
        printf("请输入第%d个数：\n",i);
        scanf("%d",&sr);
        insert(head,sr);
    }
    printf("当前链表的排列为：\n");
    show(head);//输出当前排列
    printf("请输入要插入的数：\n");
    scanf("%d",&x);//输入要插入的数
    insert(head,x);//插入
    printf("插入元素%d后的链表为：\n",x);
    show(head);//输出插入元素后的链表
    return 0;
}