网站首页 编程语言

C语言数据结构的线性表

发布时间:2016-11-28 16:20 Monday编辑:admin阅读(10656)

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

    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. }