数据结构实验十五 插入排序

1. #include <iostream>
2. using namespace std;
3. #define  MAXSIZE  20                     //顺序表的最大长度
4. typedef struct
5. {
6.  int key;
7.  char *otherinfo;
8. }ElemType;
9. //顺序表的存储结构                         
10. typedef struct
11. {
12.     ElemType *r;                      //存储空间的基地址
13.     int  length;                        //顺序表长度
14. }SqList;                      //顺序表类型
15. 
16. void InsertSort(SqList &L)
17. {
18.   int i,j; 
19. //对顺序表L做直接插入排序
20.   for(i=2;i<=L.length;++i)
21.   if(L.r[i].key<L.r[i-1].key)
22.   {
23.     L.r[0]=L.r[i];
24.     L.r[i]=L.r[i-1];
25.     for(j=i-2;L.r[0].key<L.r[j].key;--j)
26.     L.r[j+1]=L.r[j];
27.     L.r[j+1]=L.r[0];
28.     }}  //补充代码                                          
29. void Create_Sq(SqList &L)
30. {
31.   int i,n;
32.   cout<<"请输入数据个数，不超过"<<MAXSIZE<<"个。"<<endl;
33.   cin>>n;                     //输入个数
34.   cout<<"请输入待排序的数据:\n";
35.   while(n>MAXSIZE)
36.   {
37.     cout<<"个数超过上限，不能超过"<<MAXSIZE<<"，请重新输入"<<endl;
38.     cin>>n;
39.   }
40.   for(i=1;i<=n;i++)
41.   {
42.     cin>>L.r[i].key;
43.     L.length++;
44.   }
45. }
46. void show(SqList L)
47. {
48.   int i;
49.   for(i=1;i<=L.length;i++)
50.     cout<<L.r[i].key<<endl;
51. }
52. 
53. int  main()
54. {
55.   SqList L;
56.   L.r=new ElemType[MAXSIZE+1];
57.   L.length=0;
58.   Create_Sq(L);
59.   InsertSort(L);
60.   cout<<"排序后的结果为："<<endl;
61.   show(L);
62.   return 0;
63. }