照着数据结构书敲的,内含快速插入排序算法

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define MaxSize 50
  4.  
  5. typedef int ElemType;
  6.  
  7. typedef struct
  8. {
  9. ElemType data[MaxSize];
  10. int length;
  11. }SqList;
  12.  
  13. /*
  14. * 创建一个线性表,使用了CreateList 后就不需要使用InitList来初始化
  15. * 线性表了
  16. *
  17. */
  18.  
  19. void CreateList(SqList * &L,ElemType a[],int n){
  20. int i;
  21. L = (SqList * )malloc(sizeof(SqList));
  22. for(i=0;i<n;i++)
  23. L->data[i]=a[i];
  24. L->length = n;
  25. }
  26.  
  27. /*
  28. * 初始化一个线性表,表中的数据是空的
  29. *
  30. */
  31. void InitList(SqList * &L){
  32. L = (SqList * )malloc(sizeof(SqList));
  33. L->length = 0;
  34. }
  35.  
  36. /*
  37. * 销毁线性表,释放线性表中的内存
  38. *
  39. */
  40.  
  41. void DestoryList(SqList * &L){
  42. free(L);
  43. }
  44.  
  45. /*
  46. * 判断线性表是否为空表,如果为空则返回真TRUE
  47. *
  48. */
  49.  
  50. bool ListEmpty(SqList * L){
  51. return(L -> length);
  52. }
  53.  
  54. /*
  55. * 返回当前线性表的长度Length
  56. *
  57. */
  58. int ListLength(SqList * L){
  59. return (L -> length);
  60. }
  61.  
  62. /*
  63. * 输出线性表,顺序显示L中个节点的值域
  64. *
  65. */
  66.  
  67. void DispList(SqList * L){
  68. int i;
  69. for(i=0;i<L->length;i++)
  70. printf(" %d \n",L ->data[i] );
  71. printf("\n");
  72. }
  73.  
  74. /*
  75. * 获取线性表中某个数据的元素值,用e返回
  76. *
  77. */
  78.  
  79. bool GetElem(SqList * L,int i,ElemType &e){
  80. if( i<1 || i>L->length )
  81. return false;
  82. e = L ->data[i-1];
  83. return true;
  84. }
  85.  
  86. /*
  87. * 按值查找线性表中出现的位置(序号)
  88. *
  89. */
  90.  
  91. int LocateElem(SqList * L,ElemType e){
  92. int i=0;
  93. while(i<L->length && L->data[i]!=e)
  94. i++;
  95. if(i>=L->length)
  96. return 0;
  97. else
  98. return i+1;
  99. }
  100.  
  101. /*
  102. * 插入数据元素
  103. *
  104. */
  105. bool ListInsert(SqList * &L,int i,ElemType e){
  106. int j;
  107. if(i<1 || i>L->length+1)
  108. return false;
  109. i--;
  110. for(j=L->length;j>i;j--)
  111. L -> data[j] = L->data[j-1];
  112. L->data[i] = e;
  113. L->length++;
  114. return true;
  115. }
  116.  
  117. /*
  118. * 删除数据元素
  119. *
  120. */
  121. bool ListDelete(SqList * &L,int i,ElemType &e){
  122. int j;
  123. if( i<1 || i>L->length)
  124. return false;
  125. i--;
  126. e = L->data[i];
  127. for(j=i;j<L->length-1;j++)
  128. L->data[j] = L->data[j+1];
  129. L->length--;
  130. return true;
  131. }
  132.  
  133. /*
  134. * 删除所有值等于x的元素
  135. * 书本 P35解法1
  136. */
  137. void delnode1(SqList * &L,ElemType x){
  138. int k = 0,i;
  139. for(i=0;i<L->length;i++)
  140. if(L -> data[i]!=x){
  141. L->data[k] = L->data[i];
  142. k++;
  143. }
  144. L ->length = k;
  145. }
  146.  
  147. /*
  148. * 插入排序算法
  149. * 书本 P36解法2
  150. */
  151. void move2(SqList * &L){
  152. int i = 0,j;
  153. j = L->length-1;
  154. ElemType pivot = L->data[0];
  155. while(i<j){
  156. while(j>i && L->data[j]>pivot)
  157. j--;
  158. L->data[i] = L->data[j];
  159. i++;
  160. while(i<j && L->data[i]<=pivot)
  161. i++;
  162. L->data[j]=L->data[i];
  163. j--;
  164. }
  165. L->data[i] = pivot;
  166. printf("i = %d\n", i);
  167. }
  168.  
  169.  
  170. int main(){
  171. int a[] = {3,8,2,7,1,5,3,4,6,0};
  172. SqList *L;
  173. CreateList(L,a,10);//数组a的长度为10
  174. DispList(L);
  175. move2(L);
  176. printf("排序后:\n");
  177. DispList(L);
  178. }

欢迎留言