/* 2005-03-04   -------------------------------------------------------
  實(shí)驗(yàn)內(nèi)容：
	  編寫程序建立順序存儲(chǔ)的線性表L，其數(shù)據(jù)元素按非遞減有序排列，插入一個(gè)
	  元素X后，該線性表L仍保持有序。
  實(shí)驗(yàn)要求：
	  L的存儲(chǔ)結(jié)構(gòu)為：
	  #define LIST_INIT_SIZE 100  // 順序表存儲(chǔ)空間的初分配量
	  #define LISTINCREMENT  10   // 順序表存儲(chǔ)空間的分配增量	  
		struct   //線性表的結(jié)構(gòu)
		{
			int *elem;    //存儲(chǔ)空間的基地址
			int length;   //當(dāng)前的長度
			int listsize; //當(dāng)前分配的容量
		};
  測試數(shù)據(jù)：
      建立： 1,3,5,7,9
	  插入： x=-1,6,10  
-----------------------------------------------------------------------*/		

#include<stdio.h>
#include<malloc.h>
#include<conio.h>
#include<string.h>

#define LIST_INIT_SIZE 100  // 順序表存儲(chǔ)空間的初分配量
#define LISTINCREMENT  10   // 順序表存儲(chǔ)空間的分配增量

typedef struct   //線性表的結(jié)構(gòu)
{
	int *elem;    //存儲(chǔ)空間的基地址
	int length;   //當(dāng)前的長度
	int listsize; //當(dāng)前分配的容量
}SQLIST;


void Create(SQLIST &L)      //建立線性表
{
	L.elem =(int*)malloc(LIST_INIT_SIZE* sizeof(int));
	if(!L.elem)
		printf("為線性表分配空間失敗!");

	L.length =0;
	L.listsize =LIST_INIT_SIZE;
}

 
void Insert(SQLIST &A,int x)     //實(shí)現(xiàn)有序的插入操作
{
	if(A.length ==A.listsize) printf("線性表錯(cuò)誤!");

	if(x > A.elem[A.length-1])
		A.elem[A.length]=x;   //與最大的元素進(jìn)行判斷，以決定是否插在最后
	else
	{
		int i=0;
		while(x >= A.elem[i]) 
			i++;   //從第一個(gè)元素起，尋找正確的插入位置

		for(int j=A.length; j>=i; j--)
			A.elem[j+1]=A.elem[j];  //將所找位置后面的所有數(shù)據(jù)都向右移動(dòng)一個(gè)位置

		A.elem[i]=x;  //插入新的數(shù)據(jù)
	}
	A.length++; //順序表的長度加1
}

void main()
{
	printf("程序說明:\n");
	printf("    建立順序存儲(chǔ)的單鏈表，其數(shù)據(jù)元素按元素值非遞減有序排列，插入一個(gè)數(shù)據(jù)元素后，該線性表仍保持有序\n\n");

	SQLIST s;
	Create(s);    //為線性表分配空間

	s.elem[0]=1;  //建表
	s.elem[1]=3;
	s.elem[2]=5;
	s.elem[3]=7;
	s.elem[4]=9;
	s.length=5;
	printf("\n\n已建立的順序表為：\n");
	for(int i=0; i<s.length; i++)
		printf("%d ",s.elem[i]);


	printf("\n\n請輸入要插入的數(shù)據(jù):\n ");
	int tmp;
	scanf("%d",&tmp);
	
	Insert(s,tmp);
  
	printf("\n\n插入數(shù)據(jù)后的順序表為：\n");
	for(i=0; i<s.length; i++)
		printf("%d ",s.elem[i]);

	_getch(); //如果不加如該句，則執(zhí)行用Visual C++編譯后的exe文件，控制臺(tái)窗口會(huì)一閃而過，看不請執(zhí)行結(jié)果:)
}