有一个以及排好序的数组，要求输入一个数后，按原来排序的规律将它插入数组中

本是古典何须时尚 2023-07-17 15:59 16阅读 0赞

/*有一个已经排好序的数组，要求输入一个数后，按原来排序的规律将它插入数组中*/
    
    #include <stdio.h>
    #define N 10
    
    int main()
    { 
    	int i,j,t,n,min,max;
    	
    	int a[N]={ 2,4,8,11,20};
    	//printf("请输入数字：\n");
    	//for(i = 0;i < N;i ++)
    	//scanf("%d",&a[i]);
    	
    	//冒泡法排序 
    	/*for(i = 0;i < N-1;i++)//进行N-1次循环 { for(j = 0;j < N - i;j ++)//每次循环进行N-i次比较 { if(a[j] > a[j+1]) { t = a[j]; a[j] = a[j+1]; a[j+1] = t; } } }*/
    	
    	printf("请输入要插入的数字：\n");
    	scanf("%d",&n);
    	
    	for(i = 0;i < N;i ++)
    	{ 
    		if(a[i] < n && a[i + 1] > n)
    		{ 
    			j = i + 1;//找到位置 
    		    break;
    		}
    		if(a[0] > n)//第一个数字比要插入的数字要大 
    		{ 
    			j = 0;
    			break;
    		}
    		if(a[4] < n )//最后一个数字比要插入的数字要小 
    		{ 
    			j = 5;
    			break;
    		}
    		if(a[i] == n)
    		{ 
    			j = i;
    			break;
    		}	
    	}
    	
    	for(i = N - 2;i >= j;i --)
    	{ 
    		a[i+1] = a[i]; 
    	}
    	
    	a[j] = n;
    	
    	printf("输出数据是：\n");	
    	for(i = 0;i < 10;i ++)
    	{ 
    		if(a[i] != 0)
    		printf("%d,",a[i]);
    	}
    	printf("\b ");
    
     }

谭浩强C程序设计（第四版）  
复习：  
数组可以用\#define 初始化  
用数字数组可以实现这个操作，但是很麻烦，要考虑边界情况，而且不能随机输入数字

现在尝试用字符数组实现

/*有一个已经排好序的数组，要求输入一个数后，按原来排序的规律将它插入数组中*/
    
    #include <stdio.h>
    #include <string.h>
    #define N 100
    
    int main()
    { 
    	int i,j,k = 0;
    	char c[N],n = '1',t,m;
        
    	printf("请输入要插入的数字:");
    	scanf("%c",&n);
    	
        printf("请输入数字以井号键结束：");
        c[0] = getchar();//去除回车键这个字符
    	for(i = 0;i < N;i ++)
    	{ 
    		c[i] = getchar();
    		if(c[i] == '#')
    		break;
    	}
    	
    	//输出插入前的数组 
        for(i = 0;i < N;i++)
        { 	
    	    if(c[i] == '#')
    	    break;
        	printf("%c",c[i]);
        
    	}
    	
    	printf("\n");
    
    	//找到最后一个位置 
    	for(i = 0;c[i] != '#';i++)
    	{ 
    		k++;
    	}
    	
    	//找到插入位置 
    	for(i = 0;i != '#';i ++)
    	{ 
    		if(c[i] < n && c[i + 1] > n)
    		{ 
    			j = i + 1;//找到位置 
    		    break;
    		}
    		if(c[i] == n)
    		{ 
    			j = i;
    			break;
    		}	
    		if(c[0] > n)
    		{ 
    			j = 0;
    			break;
    		}
    		if(c[k-1] < n)
    		{ 
    			j = k;
    			break; 
    		}
    		
    	}
    	
    
    	
    	//插入 
    	for(i = k;i >= j;i --)
    	{ 
    		c[i+1] = c[i]; 
    	}
    	c[j] = n;
    	
        
    	for(i = 0;i < N;i++)
        { 	
    	    if(c[i] == '#')
    	    break;
        	printf("%c",c[i]);
        
    	}
    }

说明：  
1.解决了数字数组不能输入排好序数字的缺点  
2.回车键也算是字符，得要抵消掉  
3.要用到数组的下标时要想清楚到底代表几  
4.缺点是只能输入10以内的数字

下面用链表实现

/*有一个已经排好序的数组，要求输入一个数后，按原来排序的规律将它插入数组中*/
    
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct LNode{ 
    	int data;
    	struct LNode *next;
    }LNode,*LinkList;
    
    //尾插法建立链表 
    LinkList CreateList_L(LinkList &L)
    { 
    	LinkList p,q; 
    	int m;
    	
    	q = L;
    	
    	printf("请输入数组：\n");
    	scanf("%d",&m);
    	while(m > 0)
    	{ 
    		p = (LinkList)malloc(sizeof(LNode));
    	    p->data = m;
    	    p->next = NULL;
         	q->next = p;
    		q = q->next;
    		scanf("%d",&m);
    	}
    	
    	
    	return L;	
    }
    
    //输出数据
    int Output_L(LinkList &L)
    { 
    	LinkList p;
    	p = L->next;
    	
    	while(p)
    	{ 
    		printf("%d ",p->data);
    		p = p->next;
    	}
    		
    	 
    }
    
    //寻找合适位置插入
    LinkList Insert_L(LinkList &L,int n) 
    { 
    	LinkList p,q,k,t;
        k = p = q = L->next;
        t = (LinkList)malloc(sizeof(LNode));
        t->data = n;
    	
    	while(q->next != NULL)
    	q = q->next;
    	
    	if(p->data > n)//第一个数字比要插入的数字要大 
    	{ 
    		t->next = p;
    		L->next = t;
    	}
    	
    	if(q->data < n)//最后一个数字比要插入的数字小 
    	{ 
    		t->next = q->next;
    		q->next = t;
    	}
    	
    	while(k)//如果节点相等
    	{ 
    		if(k->data == n)
    		{ 
    			t->next = k->next;
    			k->next = t;
    			break;
    		}
    		k = k->next;
    	}
    	
    	while(p->next != NULL)//一般情况
    	{ 
    		
    		if(p->data < n && p->next->data > n)
    		{ 
    			t->next = p->next;
    		    p->next = t;
    		    break;
    		}
    		
    		p = p->next;
    	} 
    	
    	return L;
    }
    
    int main()
    { 
    	int n;
    	
    	LinkList L;//头结点 
    	L = (LinkList)malloc(sizeof(LNode));
    	L->data = 0;
    	L->next = NULL;
    	
    	CreateList_L(L);
    	printf("排序前：\n");
    	Output_L(L);
    	
    	printf("\n");
    	printf("请输入要插入的数字：\n");
    	scanf("%d",&n);
    	Insert_L(L,n);
    	printf("排序后：\n");
        Output_L(L);
    }

说明：  
1.链表实现了随机存取，也可以输入大于9的数字  
2.可以直接增加节点  
3.实现了模块化编程  
复习：  
1.寻找下一个节点用->next，不能单纯的+1，因为随机存取  
2.->next 在while循环中要谨慎使用要想清楚