有一个有序单链表(从小到大排序),表头指针为head,编写一个函数向该单链表中插入一个元素为x的结点,使插入后该链表仍然有序。
有一个有序单链表(从小到大排序),表头指针为head,编写一个函数向该单链表中插入一个元素为x的结点,使插入后该链表仍然有序。
输入长度n:5
输入数据:1 6 8 9 10
输入插入数据:7
输出:1 6 7 8 9 10
4 1 2 3 4 6
1 2 3 4 6
#include <iostream> #define NULL 0 using namespace std; struct student { int num; student *next; }; int n; student *creat(int m) { student *head,*p1,*p2; p1=p2=new student; cin>>p1->num; head=NULL; n=0; while(p1->num!=NULL) { n=n+1; if(n==1)head=p1; else p2->next=p1; p2=p1; p1=new student; if(n==m) {break;} else cin>>p1->num; } p2->next=NULL; return(head); } void print(student *head) { student *p; p=head; if(head!=NULL) do { cout<<p->num<<" "; p=p->next; }while(p!=NULL); } student *intset(student *head,student *stud) { student *p0,*p1,*p2; p1=head;//使p1指向第一个结点 p0=stud;//p0指向要插入的数值 if(head==NULL)//原链表为空时 { head=p0; p0->next=NULL; } else { while((p0->num>p1->num)&&(p1->next!=NULL)) { p2=p1;//p2指向刚才的结点 p1=p1->next;//p1指向下一结点 } if(p0->num<=p1->num) { if(head==p1)//插入到第一个结点之前 head=p0; else p2->next=p0;//将p0插入到结点之后 p0->next=p1; } else//插到最后一个结点之后 { p1->next=p0; p0->next=NULL; } } return (head); } int main() { int m,num; cin>>m; student *head,*stud; student *creat(int); void print(student *); student *intset(student *,student *); head=creat(m); stud=new student;//开辟新的空间 cin>>stud->num; intset(head,stud); print(head); return 0; }
原文:http://blog.csdn.net/u013629228/article/details/21867253