线性表L采用链式存储结构linklist,实现有序线性表中插入元素操作
【样例输入】
5
1 2 3 4 5
3
【样例输出】
1 2 3 3 4 5
6
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
#define error 0
#define ok 1
#define overflow -2
typedef int status;
typedef int elemtype;
typedef struct lnode{
elemtype data;//数据域
struct lnode *next;//指针域
}lnode, *linklist;
//带头结点单链表的3个基本函数及1个辅助函数:
status initlist(linklist &l) //初始化;
{
l=(linklist)malloc(sizeof(lnode));
l->next=NULL;
return ok;
}
status inputlist(linklist &l) //输入,尾插法 ;
{ int i,n ; linklist p,q;
//printf("please input the length of the linklist:");
scanf("%d",&n);
q=l;
//printf("please input the data of the linklist:");
for (i=n;i>=1;i--) {
p=(linklist)malloc(sizeof(lnode));
scanf("%d",&p->data);
p->next=NULL;
q->next=p;
q=p;
}
return ok;
}
status listtraverse(linklist l)// 输出,先输出数据元素、后输出长度;
{
int j; linklist p;
p=l->next; j=0;
//printf("the data of the linklist:");
p=l->next;
while (p!=NULL)
{ printf("%d ",p->data);
p=p->next;
j++;
}
printf("\n");
//printf("the length of the linklist:");
printf("%d\n",j);
return ok;
}
status destroylist(linklist &l) //撤销;
{ linklist p,q;
q=l;p=l->next;
while (p!=NULL)
{ q->next=p->next;
free(p);
p=q->next;
}
free(l);
return ok;
}
status orderlistinsert(linklist &l,elemtype e)
{
linklist p;
linklist s;
p=l->next;
while(p){
if(e<p->data){
s = (linklist)malloc(sizeof(lnode));//生成新结点
s->data = e;
s->next = p->next;
p->next = s;
return ok;
//s=p->data;
//p->data=e;
// p->next->data=s;
}
p=p->next;
}
return ok;
}
int main()
{
linklist l;elemtype e;
initlist(l);
inputlist(l);
scanf("%d",&e);
orderlistinsert(l,e);
listtraverse(l);
return 0;
}
修改如下,供参考:
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
#define error 0
#define ok 1
#define overflow -2
typedef int status;
typedef int elemtype;
typedef struct lnode{
elemtype data;//数据域
struct lnode *next;//指针域
}lnode, *linklist;
//带头结点单链表的3个基本函数及1个辅助函数:
status initlist(linklist &l) //初始化;
{
l=(linklist)malloc(sizeof(lnode));
l->next=NULL;
return ok;
}
status inputlist(linklist &l) //输入,尾插法 ;
{
int i,n ;
linklist p,q;
//printf("please input the length of the linklist:");
scanf("%d",&n);
q=l;
//printf("please input the data of the linklist:");
for (i=n;i>=1;i--) {
p=(linklist)malloc(sizeof(lnode));
scanf("%d",&p->data);
p->next=NULL;
q->next=p;
q=p;
}
return ok;
}
status listtraverse(linklist l)// 输出,先输出数据元素、后输出长度;
{
int j;
linklist p;
//p=l->next;
j=0;
//printf("the data of the linklist:");
p=l->next;
while (p!=NULL)
{
printf("%d ",p->data);
p=p->next;
j++;
}
printf("\n");
//printf("the length of the linklist:");
printf("%d\n",j);
return ok;
}
status destroylist(linklist &l) //撤销;
{
linklist p,q;
q=l;
p=l->next;
while (p!=NULL)
{
q->next=p->next;
free(p);
p=q->next;
}
free(l);
return ok;
}
status orderlistinsert(linklist &l,elemtype e)
{
linklist p,pr;
linklist s;
pr = l;
p=l->next;
while(p && p->data <e)
{
pr = p;
p = p->next;
}
s = (linklist)malloc(sizeof(lnode));//生成新结点
s->data = e;
s->next = pr->next;
pr->next = s;
return ok;
}
int main()
{
linklist l;
elemtype e;
initlist(l);
inputlist(l);
listtraverse(l);
scanf("%d",&e);
orderlistinsert(l,e);
listtraverse(l);
return 0;
}