用线性表直接插入的原则整理链表(线性表)

code

6 年前

时间： 1ms 内存：128M

描述：

（线性表）设L为单链表的头结点地址，其数据结点的数据都是正整数且无相同的，试设计利用直接插入的原则把该链表整理成数据递增的有序单链表的算法。

输入：

输入长度n：7

输入数据：4 5 1 6 8 2 3

输出：

1 2 3 4 5 6 8

示例输入：

7
6 8 5 9 4 15 31

示例输出：

4 5 6 8 9 15 31

提示：

参考答案（内存最优[752]）：

#include<stdio.h>  
#include<malloc.h>  
#define NULL 0  
#define LEN sizeof(struct date)  
    
int t;  
struct date  
{  
    int num;  
    struct date *next;  
};  
struct date * creat(int m)  
{  
    struct date *head;  
    struct date *p1,*p2;  
    t=0;  
    p1=p2=(struct date *)malloc(LEN);  
    head=NULL;  
    while(m--)  
    {  
          
        scanf("%d",&p1->num);  
        t++;  
        if(t==1)  
            head=p1;  
        else
            p2->next=p1;  
        p2=p1;  
  
  
  
        p1=(struct date *)malloc(LEN);  
    }  
    p2->next=NULL;  
    return (head);  
}  
    
    
void print(struct date *head)  
{  
    struct date *p;  
    p=head;  
    if(head!=NULL)  
        do
        {  
            printf("%d ",p->num);  
            p=p->next;  
        }while(p!=NULL);  
    printf("\n");  
} 
  
int main()  
{  
    struct date *p,*p1,*p2,*p3,*p4,*p5;  
    int m,t,s,k=0; 
    scanf("%d",&m); 
    p=creat(m); 
	
    p1=p2=p; 
    p3=p->next; 
loop:if(p2->num>p3->num) 
	 { 
		 p=p3; 
		 p2->next=p3->next; 
		 p3->next=p2; 
		 p4=p3; 
		 p3=p2; 
		 p2=p4; 
	 } 
	 p1=p; 
	 p2=p2->next; 
	 p3=p2->next; 
	 t=s=m; 
	 /*貌似一维数组的冒泡排序法*/
	 k++;
	 while(p3) 
	 { 
		 if(p2->num>p3->num) 
		 { 
			 p1->next=p3; 
			 p2->next=p3->next; 
			 p3->next=p2; 
			 p4=p3; 
			 p3=p2; 
			 p2=p4; 
			 p1=p1->next; 
			 p2=p2->next; 
			 p3=p2->next; 
		 } 
		 else
		 { 
			 p1=p1->next; 
			 p2=p2->next; 
			 p3=p2->next; 
		 } 
		 p5=p; 
		 t--; 
		 while(t--) 
			 p5=p5->next; 
		 p5->next=NULL; 
		 t=s; 
	 } 
	 p1=p; 
	 p2=p; 
	 p3=p->next; 
	 if(k==8)
		 print(p);
	 else
		 goto loop;
     return 0;  
}

参考答案（时间最优[0]）：

#include<stdio.h>  
#include<malloc.h>  
#define NULL 0  
#define LEN sizeof(struct date)  
    
int t;  
struct date  
{  
    int num;  
    struct date *next;  
};  
struct date * creat(int m)  
{  
    struct date *head;  
    struct date *p1,*p2;  
    t=0;  
    p1=p2=(struct date *)malloc(LEN);  
    head=NULL;  
    while(m--)  
    {  
          
        scanf("%d",&p1->num);  
        t++;  
        if(t==1)  
            head=p1;  
        else
            p2->next=p1;  
        p2=p1;  
  
  
  
        p1=(struct date *)malloc(LEN);  
    }  
    p2->next=NULL;  
    return (head);  
}  
    
    
void print(struct date *head)  
{  
    struct date *p;  
    p=head;  
    if(head!=NULL)  
        do
        {  
            printf("%d ",p->num);  
            p=p->next;  
        }while(p!=NULL);  
    printf("\n");  
} 
  
int main()  
{  
    struct date *p,*p1,*p2,*p3,*p4,*p5;  
    int m,t,s,k=0; 
    scanf("%d",&m); 
    p=creat(m); 
	
    p1=p2=p; 
    p3=p->next; 
loop:if(p2->num>p3->num) 
	 { 
		 p=p3; 
		 p2->next=p3->next; 
		 p3->next=p2; 
		 p4=p3; 
		 p3=p2; 
		 p2=p4; 
	 } 
	 p1=p; 
	 p2=p2->next; 
	 p3=p2->next; 
	 t=s=m; 
	 /*貌似一维数组的冒泡排序法*/
	 k++;
	 while(p3) 
	 { 
		 if(p2->num>p3->num) 
		 { 
			 p1->next=p3; 
			 p2->next=p3->next; 
			 p3->next=p2; 
			 p4=p3; 
			 p3=p2; 
			 p2=p4; 
			 p1=p1->next; 
			 p2=p2->next; 
			 p3=p2->next; 
		 } 
		 else
		 { 
			 p1=p1->next; 
			 p2=p2->next; 
			 p3=p2->next; 
		 } 
		 p5=p; 
		 t--; 
		 while(t--) 
			 p5=p5->next; 
		 p5->next=NULL; 
		 t=s; 
	 } 
	 p1=p; 
	 p2=p; 
	 p3=p->next; 
	 if(k==8)
		 print(p);
	 else
		 goto loop;
     return 0;  
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。