线性表顺序存储实现-动态数组

谁借莪１个温暖的怀抱￠ 2021-10-01 01:42 350阅读 0赞

1 // 2018-06-22
      2 // 线性表顺序存储实现-动态数组
      3 #include<stdio.h>
      4 #include<stdlib.h>
      5 
      6 #define LIST_INIT_SIZE 5  // 符号常量 ，线性表存储空间的初试分配量
      7 #define LIST_INCREMENT 10 // 符号常量 ，线性表存储空间的分配增量
      8 
      9 #define OK 1
     10 #define ERROR 0
     11 #define TRUE 1
     12 #define FALSE 0
     13 
     14 typedef int ElemType;
     15 typedef int Status;
     16 
     17 typedef struct sqList
     18 {
     19     ElemType *elem;    // 存储空间基地址
     20     int length;        // 线性表当前长度
     21     int listsize;    // 当前分配的存储容量
     22 }SqList;
     23 
     24 
     25 /*
     26 Status InitList(SqList *L);
     27 Status ListInsert(SqList *L,int i,ElemType e);
     28 Status ListTraverse(SqList L);
     29 Status ListEmpty(SqList L);
     30 Status ClearList(SqList *L);
     31 Status GetElem(SqList L,int i,ElemType *e);
     32 int LocateElem(SqList L,ElenType e);
     33 Status ListDelete(SqList *L,int i,ElemType *e);
     34 int ListLength(SqList L);
     35 void UnionL(SqList *La,SqList Lb);
     36 */
     37 
     38 // 初始化线性表
     39 Status InitList(SqList *L)
     40 {
     41     L->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
     42     if (!(L->elem))
     43         return ERROR;
     44     L->length = 0;                     // 空表长度为0
     45     L->listsize = LIST_INIT_SIZE;     // 初始化存储容量
     46 
     47     return OK;
     48 }
     49 
     50 // 在 L 中第 i 个位置插入新的数据元素 e ，L 的长度增加 1
     51 Status ListInsert(SqList *L, int i, ElemType e)
     52 {
     53     ElemType *newbase;
     54     int k;
     55 
     56     if (L->length == L->listsize)
     57     {
     58         // realloc(void *__ptr, size_t __size)
     59         // 更改已经配置的内存空间，即更改由malloc()函数分配的内存空间的大小
     60         newbase = (ElemType *)realloc(L->elem, (L->listsize + LIST_INCREMENT) * sizeof(ElemType));
     61         if (!newbase)
     62             return ERROR;
     63         L->elem = newbase;
     64         L->listsize += LIST_INCREMENT;
     65     }
     66 
     67     if (!(i >= 1 && i <= L->length + 1))
     68         return ERROR;
     69 
     70     if (i != L->length + 1)    // 插入的位置不在表尾
     71     {
     72         for (k = L->length - 1; k >= i - 1; k--)
     73             *(L->elem + k + 1) = *(L->elem + k);
     74     }
     75     *(L->elem + i - 1) = e;
     76     L->length++;
     77     return OK;
     78 }
     79 
     80 Status ListTraverse(SqList L)
     81 {
     82     int i;
     83     for (i = 0; i < L.length; i++)
     84     {
     85         printf("%d ", *(L.elem++));
     86     }
     87     printf("\n");
     88     return OK;
     89 }
     90 
     91 Status ListEmpty(SqList L)
     92 {
     93     if (L.length == 0)
     94         return OK;
     95     else
     96         return ERROR;
     97 }
     98 
     99 Status ClearList(SqList *L)
    100 {
    101     L->length = 0;
    102     return OK;
    103 }
    104 
    105 Status GetElem(SqList L, int i, ElemType *e)
    106 {
    107     if (L.length == 0) return ERROR;
    108     if (!(i >= 1 && i < L.length)) return ERROR;
    109     *e = *(L.elem + i - 1);
    110     return OK;
    111 }
    112 
    113 // 返回L中第1个与e满足关系的数据元素的位序
    114 int LocateElem(SqList L, ElemType e)
    115 {
    116     int i;
    117     if (L.length == 0)
    118         return 0;
    119     for (i = 0; i < L.length; i++)
    120     {
    121         if (*(L.elem + i) == e)
    122             return i + 1;
    123     }
    124     return 0;
    125 }
    126 
    127 Status ListDelete(SqList *L, int i, ElemType *e)
    128 {
    129     int k;
    130     if (L->length == 0) return ERROR;
    131     if (!(i >= 1 && i <= L->length)) return ERROR;
    132 
    133     *e = *(L->elem + i - 1);
    134     if (i != L->length)
    135     {
    136         for (k = i; k <= L->length - 1; k++)
    137         {
    138             *(L->elem + k - 1) = *(L->elem + k);
    139         }
    140     }
    141     L->length--;
    142     return OK;
    143 }
    144 
    145 int ListLength(SqList L)
    146 {
    147     return L.length;
    148 }
    149 
    150 void UnionL(SqList *La, SqList Lb)
    151 {
    152     int La_len, Lb_len, i;
    153     ElemType e;
    154 
    155     La_len = ListLength(*La);
    156     Lb_len = ListLength(Lb);
    157 
    158     for (i = 1; i <= Lb_len; i++)
    159     {
    160         GetElem(Lb, i, &e);
    161         if (!LocateElem(*La, e))
    162             ListInsert(La, ++La_len, e);
    163     }
    164 }
    165 
    166 int main()
    167 {
    168     SqList La, Lb;
    169     int i, j, k;
    170     ElemType e;
    171 
    172     i = InitList(&La);
    173 
    174     for (j = 1; j <= 5; j++)
    175         ListInsert(&La, 1, j);
    176     printf("在L的表头插入1~5后，L->data = ");
    177     ListTraverse(La);
    178     printf("\n");
    179 
    180     printf("L.length = %d\n", La.length);
    181     i = ListEmpty(La);
    182     printf("L是否为空：i = %d (1:是 0：否)\n",i);
    183     printf("\n");
    184 
    185     i = ClearList(&La);
    186     printf("清空L后，L.length = %d\n", La.length);
    187     i = ListEmpty(La);
    188     printf("L是否为空：i = %d (1:是 0：否)\n", i);
    189     printf("\n");
    190 
    191     for ( j = 0; j <= 10; j++)
    192         ListInsert(&La, j, j);
    193     printf("在L的表头插入1~10后，L->data = ");
    194     ListTraverse(La);
    195     printf("L.length = %d\n",La.length);
    196     printf("\n");
    197 
    198     i = ListInsert(&La, 1, 0);
    199     printf("在L的表头插入0后，L.data = ");
    200     ListTraverse(La);
    201     printf("L.length = %d\n", La.length);
    202     printf("\n");
    203 
    204     GetElem(La, 5, &e);
    205     printf("第 5 个元素的值为:%d\n", e);
    206     printf("\n");
    207 
    208     for ( j = 3; j <= 4; j++)
    209     {
    210         k = LocateElem(La, j); // 查找位序
    211         if (k)
    212             printf("元素%d的位序是%d\n", j, k);
    213         else
    214             printf("没有值为%d的元素\n", j);
    215     }
    216     j = 9;
    217     i = ListDelete(&La, j, &e);
    218     if (i == ERROR)
    219         printf("删除第%d个数据失败\n", j);
    220     else
    221         printf("删除第%d个元素的值为：%d\n", j, e);
    222     printf("L.length = %d\n", La.length);
    223     printf("L.data = ");
    224     ListTraverse(La);
    225     printf("\n");
    226 
    227     k = ListLength(La);
    228     j = k + 1; // 删除第length+1个元素
    229     i = ListDelete(&La, j, &e);
    230     if (i == ERROR)
    231         printf("删除第%d个数据失败\n", j);
    232     else
    233         printf("删除第%d个元素的值为%d\n", j, e);
    234     i = InitList(&Lb);
    235     for ( j = 8; j <= 15; j++)
    236         i = ListInsert(&Lb, 1, j);
    237     printf("依次输出Lb的元素:");
    238     ListTraverse(Lb);
    239     printf("\n");
    240     UnionL(&La, Lb);
    241     printf("L.length = %d\n", La.length);
    242     printf("依次输出合并之后的L.data = ");
    243     ListTraverse(La);
    244     printf("\n");
    245 
    246     getchar();
    247     return 0;
    248 }

转载于:https://www.cnblogs.com/IamJiangXiaoKun/p/9453249.html