线性表的插入运算
题目描述
已知顺序表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;
}