鱼C论坛

 找回密码
 立即注册
查看: 1960|回复: 2

[技术交流] 静态顺序表的c实现

[复制链接]
发表于 2017-7-23 21:16:37 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
终于,自己从头到尾敲了一遍顺序表。虽然是静态顺序表,但还是挺满意的。在敲代码过程中,我对指针和结构体的了解更加深入了,还接触到了<merroy.h>,<assert.h>库函数。有时间,实现线性表有集合属性。

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <assert.h>
  4. #include <memory.h>

  5. #define MAXSIZE 50
  6. #define OK 1
  7. #define ERROR 0
  8. #define OVERFLOW -2

  9. typedef int Status;
  10. typedef int ElemType;

  11. //定义顺序表的静态数组表示
  12. typedef  struct{
  13. ElemType data[MAXSIZE];
  14. int length;
  15. }SqList,*pSqList;



  16. void Init_Sq(pSqList pSq);
  17. void InsertFirst(pSqList pSq, ElemType);
  18. void InsertLast(pSqList pSq, ElemType);
  19. void TraverseList(pSqList pSq);
  20. int ListLength(pSqList pSq);
  21. Status ListInsert(pSqList pSq, int i, ElemType e);
  22. Status ListDelete(pSqList pSq, int i, ElemType * e);
  23. int LocateElem_Sq(pSqList pSq, ElemType e);
  24. void GetElem(pSqList pSq, int i, ElemType * e);
  25. void Union_Sq(pSqList La, SqList Lb);

  26. int main()
  27. {
  28.     SqList list1;
  29.     Init_Sq(&list1);

  30.     int length1;
  31.     scanf("%d",&length1);
  32.     int i;
  33.     ElemType e;

  34.     for(i=0;i<length1;i++)
  35.     {
  36.         scanf("%d",&e);
  37.         InsertLast(&list1, e);
  38.     }

  39.     printf("创建好的线性表list1=");
  40.     TraverseList(&list1);

  41.     printf("像表头插入一个元素:");
  42.     scanf("%d",&e);
  43.     InsertFirst(&list1, e);

  44.     printf("插入一个头元素的list1=");
  45.     TraverseList(&list1);

  46.     printf("在线性表第i个位置前插入e,输入i(输q退出):");
  47.     while(scanf("%d", &i))
  48.     {
  49.         printf("输入元素e:");
  50.         scanf("%d", &e);
  51.         ListInsert(&list1, i, e);
  52.         printf("在线性表第i个位置前插入e,输入i(输q退出):");
  53.     }
  54.     printf("插入元素后的list1:");
  55.     TraverseList(&list1);

  56.     getchar();
  57.     printf("在顺序表中删除list1中删除第i个元素,输入i(输q退出):");
  58.     while(scanf("%d", &i))
  59.     {
  60.         int e;
  61.         ListDelete(&list1, i, &e);
  62.         printf("删除的元素是:%d\n", e);
  63.        printf("在顺序表中删除list1中删除第i个元素,输入i(输q退出):");
  64.     }
  65.     printf("删除元素后的list1:");
  66.     TraverseList(&list1);

  67.     getchar();
  68.     printf("\n");
  69.     SqList list2;
  70.     Init_Sq(&list2);

  71.     int length2;
  72.     scanf("%d", &length2);
  73.     for(i=0;i<length2;i++)
  74.     {
  75.         scanf("%d",&e);
  76.         InsertLast(&list2, e);
  77.     }
  78.     printf("创建好的线性表list2=");
  79.     TraverseList(&list2);

  80.     Union_Sq(&list1, list2);
  81.     printf("list1 U list1 =");
  82.     TraverseList(&list1);

  83.     return 0;
  84. }

  85. //初始化顺序表
  86. void Init_Sq(pSqList pSq)
  87. {
  88.     assert(pSq);  //判断是否开辟结构体空间

  89. //把线性表的每个元素初始化为0

  90. //方法1
  91. //  memset(pSq->data, 0, sizeof(ElemType)*MaxSize);

  92. //方法2
  93. //    for(i=0; i<sizeof(pSq->data)/sizeof(*pSq->data); i++)
  94. //    {
  95. //        pSq->data[i] = 0;
  96. //    }
  97.     pSq->length = 0;
  98. }

  99. //遍历顺序表
  100. void TraverseList(pSqList pSq)
  101. {
  102.     int i;

  103.     for(i=0; i<pSq->length; i++)
  104.     {
  105.         printf("%d", pSq->data[i]);
  106.     }
  107.     putchar('\n');
  108.     return;
  109. }

  110. //求表中元素个数
  111. int ListLength(pSqList pSq)
  112. {
  113.     return pSq->length;
  114. }

  115. //向表头插入一个元素
  116. void InsertFirst(pSqList pSq, ElemType e)
  117. {
  118.     int * p, * q;

  119.     if(pSq->length>=MAXSIZE)
  120.     {
  121.         exit(OVERFLOW);
  122.     }

  123.     q = &pSq->data[0];
  124.     for(p=&pSq->data[pSq->length-1];p>=q;p--) //不能用于首次插入
  125.     {
  126.         *(p + 1) = *p;
  127.     }
  128.     *q = e;
  129.     pSq->length++;
  130.     return;
  131. }

  132. //向表尾插入一个元素
  133. void InsertLast(pSqList pSq, ElemType e)
  134. {
  135.      if(pSq->length>=MAXSIZE)
  136.     {
  137.         exit(OVERFLOW);
  138.     }
  139.     pSq->data[pSq->length] = e;
  140.     pSq->length++;
  141.     return;
  142. }

  143. //在顺序表第i个位置之前插入新的元素e
  144. Status ListInsert(pSqList pSq, int i, ElemType e)
  145. {
  146.     int * q, * p;
  147.     if(i<1 || i>pSq->length+1) return ERROR;
  148.     if(pSq->length>=MAXSIZE)
  149.     {
  150.         exit(OVERFLOW);
  151.     }
  152.     q = &(pSq->data[i-1]);

  153.     for(p=&(pSq->data[pSq->length-1]);p>=q;p--)
  154.         * (p+1) = * p;

  155.     * q = e;
  156.     ++pSq->length;
  157.     return OK;
  158. }

  159. //删除第i个元素,并返回其值
  160. Status ListDelete(pSqList pSq, int i, ElemType * e)
  161. {
  162.     int * p, *q;
  163.     if((i<1) || (i>pSq->length)) return ERROR;
  164.     p = &(pSq->data[i-1]);
  165.     *e = *p;
  166.     q = pSq->data + pSq->length-1;
  167.     for(++p; p<=q; ++p) *(p-1) = *p;
  168.     --pSq->length;
  169.     return OK;
  170. }

  171. //定位一个指定的值在线性表中的具体位置
  172. //若找到,则返回其在顺序表中的位序
  173. int LocateElem_Sq(pSqList pSq, ElemType e)
  174. {
  175.     ElemType * p;
  176.     int i = 1;
  177.     p = pSq->data;

  178.     while(i<=pSq->length&&!(*p++==e)) i++;

  179.     if(i<=pSq->length) return i;
  180.     else return 0;
  181. }

  182. void GetElem(pSqList pSq, int i, ElemType* e)
  183. {
  184.     *e = pSq->data[i-1];
  185. }

  186. //求线性表La与线性表Lb的并集,
  187. //即将所有在线性表Lb中但不在线性表La中的元素插入到La中
  188. void Union_Sq(pSqList La, SqList Lb)
  189. {
  190.     int Lb_len;
  191.     Lb_len = ListLength(&Lb);

  192.     int i;
  193.     for(i=1; i<=Lb_len;i++){
  194.         int e;
  195.         GetElem(&Lb, i, &e);
  196.         if(!LocateElem_Sq(La, e)){
  197.             InsertLast(La, e);
  198.         }
  199.     }
  200. }
复制代码

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
小甲鱼 + 3 + 3 支持楼主!

查看全部评分

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-7-23 22:58:38 | 显示全部楼层
不错,再接再厉!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

 楼主| 发表于 2017-7-24 18:06:04 | 显示全部楼层
小甲鱼 发表于 2017-7-23 22:58
不错,再接再厉!

蟹蟹大佬鼓舞。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 01:19

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表