线性表的插入运算(耿2.4)

线性表的插入运算

题目描述

已知顺序表L递增有序,编写程序,将X插入到线性表的适当位置上,以保持线性表的有序性。

输入

第一行输入顺序表元素个数elenum;(0<elenum<1000)
第二行输入顺序表L;
第三行输入插入值X。

输出

输出插入X后的有序顺序表

输入样例

7
2 3 4 5 6 7 8
1

输出样例

1 2 3 4 5 6 7 8

两种表示和实现

数组表示

#include <stdio.h>

int main()
{
    int elenum,L[1000],X,i;

    //输入
    scanf("%d",&elenum);
    for(i=0;i<elenum;i++)
        scanf("%d",&L[i]);
    scanf("%d",&X);

    //插入
    for(i=elenum-1;i>=0&&L[i]>=X;i--)
        L[i+1]=L[i];
    L[++i]=X;

    //输出
    for(i=0;i<=elenum;i++)
    {
        printf("%d ",L[i]);
    }

    return 0;
}

链表表示

  • 单链表的创建、遍历、插入、输出
#include <stdio.h>
#include <stdlib.h>

//tagLNode为单链表结点类型
typedef struct tagLNode
{
    int data;
    struct tagLNode *next;
}LNode,*Linklist; //LNode为单链表结构体类型,Linklist为单链表指针类型

void Create(Linklist *L,int n) //尾插法建立链表
{
    int i;
    Linklist p,s;
    p=*L=(Linklist)malloc(sizeof(LNode)); //创建头结点,p为当前结点

    for(i=1;i<=n;i++) //创建n个新结点
    {
        s=(Linklist)malloc(sizeof(LNode));
        scanf("%d",&s->data);
        p->next=s;
        p=s;
    }
    p->next=NULL; //尾结点为空
}

void Insert(Linklist *L,int X)
{
    Linklist p=*L,tmp; //p指向头结点,第一个存储信息的结点是p->next
    
    tmp=(Linklist)malloc(sizeof(LNode));
    tmp->data=X;
    tmp->next=NULL;

    while(p->next!=NULL) //若不是尾结点
    {
        if((p->next)->data<=X) //从前向后遍历,若X大于当前结点的元素值,p指向后一结点
            p=p->next;
        else //否则,插入X
        {
            tmp->next=p->next;
            p->next=tmp;
            return ;
        }
    }
}

void Output(Linklist L)
{
    Linklist p=L->next;
    while(p!=NULL)
    {
        printf("%d ",p->data);
        p=p->next;
    }
}

int main()
{
    int elenum,X;
    Linklist L;

    scanf("%d",&elenum); //输入顺序表元素个数
    Create(&L,elenum); //创建顺序表L
    scanf("%d",&X); //输入待插入元素X
    Insert(&L,X);
    Output(L);

    return 0;
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。