数据结构之线性表(顺序表）

2458阅读　0评论2013-01-06　
分类：C/C++


1.1 线性表的定义

   线性表（List）：零个或多个数据元素的有限序列。

  在数据元素的非空有限集中，线性结构的特点：

 （1）存在唯一的一个被称为“第一个”的数据元素；

 （2）存在唯一的一个称为“最后一个”的数据元素；

 （3）除第一个之外，集合中的每个数据元素均只有一个前驱；

 （4）除最后一个之外，集合中的每个数据元素只有一个后继；

  优点：可以随机访问元素

  缺点：对于插入和删除元素，需要大量的位置移动


1.2 线性表的顺序表示

   线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

   来看线性表的动态分配的存储结构。    


  1. typedef ElemType int; //假设为int

  3. #define LIST_INIT_SIZE 100 //线性表存储空间初始分配值
  4. #define LISTINCREMENT 10 //线性表存储空间分配增量

  6. typedef struct
  7. {
  8.     ElemType *elem; //存储基地址
  9.     int listsize; //当前线性表存储空间分配大小
  10.     int length; //当前线性表大小
  11. }SqList;



1.3 线性表顺序结构代码实现


  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>

  5. //宏定义
  6. #define TRUE 1
  7. #define FALSE 0
  8. #define OK 1
  9. #define ERROR 0
  10. #define INFEASIBLE -1
  11. #define OVERFLOW -2

  13. #define LIST_INIT_SIZE 100         //线性表存储空间的初始分配量
  14. #define LISTINCREMENT 10           //线性表存储空间的分配增量

  16. typedef int ElemType;

  18. typedef struct LNode
  19. {
  20.     ElemType *elem;                //存储空间基地址
  21.     int length;                    //线性表当前长度
  22.     int listsize;                  //线性表存储空间实际分配大小
  23. }SqList;


  26. /* 函数名称：InitList
  27.  * 函数功能：构造空的线性表
  28.  * 返回值：
  29.  *        ERROR：malloc() error
  30.  *        OK   : 构造成功
  31. */
  32. int InitList(SqList *L, int length)
  33. {
  34.     if( 0 == length )
  35.     {
  36.         length = LIST_INIT_SIZE;                    //默认分配LIST_INIT_SIZE
  37.     }
  38.     L->elem = (ElemType *)malloc(sizeof(length));
  39.     if(NULL == L->elem)                             //空间分配失败
  40.     {
  41.         fprintf(stderr, "malloc() error.\n");
  42.         return ERROR;
  43.     }
  44.     L->listsize = length;                         
  45.     L->length = 0;                                

  47.     return OK;
  48. }

  50. /* 函数名称：InsertList
  51.  * 函数功能：在线性表的第i个位置插入元素e.(第i个位置，即为线性表中第i-1个元素)
  52.  * 返回值：
  53.  *        ERROR：i不合法或realloc失败
  54.  *        OK   ：插入成功
  55. */
  56. int InsertList(SqList *L, ElemType e, int i)
  57. {
  58.     if(i < 0 || i > L->length + 1)         //i不合法
  59.     {
  60.         return ERROR;
  61.     }

  63.     if(L->length >= L->listsize)            //空间不足
  64.     {
  65.         ElemType *newbase = (ElemType *)realloc(L->elem, (L->listsize + LISTINCREMENT) * sizeof(ElemType));
  66.         if(!newbase)
  67.         {
  68.             return ERROR;                   //realloc error
  69.         }
  70.         L->elem = newbase;
  71.         L->listsize = L->listsize + LISTINCREMENT;
  72.     }
  73.     
  74.     ElemType *q = &(L->elem[i]);        
  75.     ElemType *p = NULL;
  76.     for(p = &(L->elem[L->length - 1]); p >= q; --p)
  77.     {
  78.         *(p + 1) = *p;
  79.     }
  80.     *q = e;
  81.     
  82.     L->length++;
  83.     
  84.     return OK;
  85. }

  87. /* 函数名称：DeleteList
  88.  * 函数功能：删除线性表第i个元素，并将其保存到e中返回
  89.  * 返回值：
  90.  *        ERROR：i不合法
  91.  *        OK   ：删除成功
  92. */
  93. int DeleteList(SqList *L, int i, ElemType *e)
  94. {
  95.     if(i < 0 || i > L->length)            //i不合法
  96.     {
  97.         fprintf(stderr, "i不合法\n");
  98.         return ERROR;
  99.     }

  101.     ElemType *q = &(L->elem[i]);    
  102.     *e = *q;                              //获得第i个元素的值
  103.     
  104.     ElemType *p = L->elem + L->length - 1;
  105.     
  106.     for( ; q < p; q++)                    //循环左移
  107.     {
  108.         *q = *(q + 1);
  109.     }
  110.     
  111.     L->length--;                          //当前长度减1

  113.     return OK;
  114. }


  117. //快速排序
  118. int partition(SqList *L, ElemType low, ElemType high)
  119. {
  120.     ElemType key = L->elem[low];
  121.     
  122.     while(low < high)                                //
  123.     {
  124.         while(low < high && L->elem[high] >= key)    //
  125.         {
  126.             high--;
  127.         }
  128.         L->elem[low] = L->elem[high];                //
  129.         L->elem[high] = key;

  131.         while(low < high && L->elem[low] <= key)    //
  132.         {
  133.             low++;
  134.         }
  135.         L->elem[high] = L->elem[low];                //
  136.         L->elem[low] = key;
  137.     }
  138.     
  139.     return low;
  140. }

  142. void quickSort(SqList *L, ElemType low, ElemType high)
  143. {
  144.     ElemType key;
  145.     if(low < high)
  146.     {
  147.         key = partition(L, low, high);
  148.         quickSort(L, low, key - 1);
  149.         quickSort(L, key + 1, high);
  150.     }
  151. }

  153. /* 函数名称：MergeList
  154.  * 函数功能：将线性表La和线性表Lb合并到Lc中，并不删除元素
  155. */
  156. int MergeList(SqList La, SqList Lb, SqList *Lc)
  157. {
  158.     //线性表La和Lb中的元素均不递减，合并后的Lc也不递减
  159.     
  160.     ElemType *pa, *pb, *pc;
  161.     Lc->listsize = La.length + Lb.length;

  163.     InitList(Lc, Lc->listsize);

  165.     Lc->length = Lc->listsize;

  167.     pa = La.elem;
  168.     pb = Lb.elem;
  169.     pc = Lc->elem;

  171.     while(pa <= &(La.elem[La.length - 1]) && pb <= &(Lb.elem[Lb.length - 1]))
  172.     {
  173.         if(*pa <= *pb)
  174.         {
  175.             *pc++ = *pa++;
  176.         }
  177.         else
  178.         {
  179.             *pc++ = *pb++;
  180.         }
  181.     }
  182.     while(pa <= &(La.elem[La.length - 1]))
  183.     {
  184.         *pc++ = *pa++;
  185.     }
  186.     while(pb <= &(Lb.elem[Lb.length - 1]))
  187.     {
  188.         *pc++ = *pb++;
  189.     }
  190.     
  191.     return OK;
  192. }

  194. //打印线性表中元素
  195. void printList(SqList L)
  196. {
  197.     int i = 0;
  198.     for(i = 0; i < L.length; i++)
  199.     {
  200.         printf("%d ",L.elem[i]);
  201.     }
  202.     printf("\n");
  203. }

  205. int main(int argc, char **argv)
  206. {
  207.     SqList La, Lb, Lc;
  208.     ElemType e;
  209.     int ret;
  210.     
  211.     ret = InitList(&La, LIST_INIT_SIZE);
  212.     if(ret == ERROR)
  213.     {
  214.         fprintf(stderr, "InitList() error.\n");
  215.         exit(EXIT_FAILURE);
  216.     }

  218.     int data[6] = {6, 5, 8, 3, 9, 4};
  219.     int i = 0;
  220.     for(i = 0; i < 6; i++)
  221.     {
  222.          ret = InsertList(&La, data[i], i);    
  223.          if(ret != OK)
  224.          {
  225.                  fprintf(stderr, "插入元素失败.\n");
  226.                  exit(EXIT_FAILURE);
  227.          }
  228.     }

  230.     printf("初始化后的La:\n");
  231.     printList(La);

  233.     ret = DeleteList(&La, 3, &e);                     
  234.     if(ret != OK)
  235.     {
  236.         fprintf(stderr, "删除元素失败.\n");
  237.         exit(EXIT_FAILURE);
  238.     }
  239.     printf("删除第3个元素后的La:\n");
  240.     printList(La);

  242.     ret = InsertList(&La, e, 3);                
  243.     if(ret != OK)
  244.     {
  245.         fprintf(stderr, "插入元素失败.\n");
  246.         exit(EXIT_FAILURE);
  247.     }
  248.     printf("插入e后的La:\n");
  249.     printList(La);

  251.     //快速排序
  252.     quickSort(&La, 0, La.length - 1);
  253.     printf("排序后的La:\n");
  254.     printList(La);

  256.     printf("\n");
  257.     InitList(&Lb, LIST_INIT_SIZE);

  259.     int bdata[5] = {1, 3, 2, 4, 6};
  260.     for(i = 0; i < 5; i++)
  261.     {
  262.         InsertList(&Lb, bdata[i], i);
  263.     }
  264.     printf("初始化后的Lb:\n");
  265.     printList(Lb);

  267.     //快速排序
  268.     quickSort(&Lb, 0, Lb.length - 1);
  269.     printf("排序后的Lb:\n");
  270.     printList(Lb);

  272.     MergeList(La, Lb, &Lc);
  273.     printf("La与Lb合并后的Lc:\n");
  274.     printList(Lc);

  276.     return 0;
  277. }
 


       

    参考：严蔚敏老师之《数据结构》

                       

                                                        梦醒潇湘love

                                                       2013-01-06 22:06


上一篇：每日杂乱
下一篇：数据结构之线性表(单链表）