题目描述
本题只需要提交填写部分的代码
（线性表）已知一单向链表，从第二个结点至表尾递增有序，（设a1<x<an）如下图(“第二个结点至表尾”指a1..an )。试编写程序，将第一个结点删除并插入表中适当位置，使整个链表递增有序。
代码：
#include <iostream>
using namespace std;
struct Node
{
int data;
Node *next;
};
Node *createlist(Node *head,int n) //建立链表
{
Node *previous; //前驱结点
Node *current; //当前结点
if(n<1)
{
return NULL; //建立空链表
}
previous=head=new Node; //建立首结点
cin>>head->data; //输入数据
while(–n)
{
current=new Node; //建立新结点
cin>>current->data; //输入数据
previous->next=current; //将新结点挂在表尾
previous=current;
}
previous->next=NULL; //置表尾结束标志
return head; //返回首结点指针
}
Node *insertsortlist(Node *head)
{
Node *previous; //前驱结点
Node *current; //当前结点
Node *key; //记录首结点
/* 特殊情况处理 链表为空或只有一个结点或初始升序*/
if(head==NULL||head->next==NULL||head->data<=head->next->data)
return head;
previous=key=head; //记录插入结点
current=head->next; //当前结点
head=current; //首结点后移
/* 查找第一个比key大的结点 */
while(current!=NULL&¤t->data<=key->data)
{
previous=current; //记录前驱结点
current=current->next; //当前结点后移
}
if(current==NULL) //链表结点均不大于首结点
{
previous->next= key; //将插入结点挂在表尾
key->next = NULL;
}
else //将key插入在previous和next之间
{
/*
请在该部分填写缺少的代码
*/
}
return head;
}
void output(Node *head)
{
Node *current=head;
while(current!=NULL)
{
cout<<current->data<<" ";
current=current->next;
}
}
int main()
{
int n;
Node *head=NULL;
cin>>n;
head=createlist(head,n);
if(head==NULL)
return 0;
head=insertsortlist(head);
output(head);
return 0;
}
输入
输入长度n：7
输入数据：4 1 2 3 6 8 9
输出
1 2 3 4 6 8 9
样例输入
5
11 7 8 9 10
样例输出
7 8 9 10 11
参考代码
#include<stdio.h>
int main()
{
int n,i,j,a[80],t;
scanf("%d",&n);
for (i=0;i<n;i++)
scanf("%d",&a[i]);
for (i=0;i<n;i++)
for (j=i+1;j<n;j++)
{
if(a[i]>a[j])
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
for (i=0;i<n;i++)
printf("%d ",a[i]);
return 0;
}
解析
暂无
