QQ登录

只需一步,快速开始

登录 | 立即注册 | 找回密码

主题

帖子

荣誉

VIP至尊会员

Rank: 15Rank: 15Rank: 15

积分
89
查看: 140|回复: 0

[学习笔记] 线性表的顺序表示和c实现

[复制链接]
最佳答案
0 
累计签到:26 天
连续签到:1 天
威斯布鲁特 发表于 2017-9-9 12:44:40 1400 | 显示全部楼层 |阅读模式

马上注册加入鱼C,享用更多服务吧^_^

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

x
通过这次的练习,虽然自己的自控力一般,容易被游戏,动漫吸引,但我发现数据结构和算法的学习是一个长期的过程。为了完成这次的练习,我复习了函数指针与指针函数的区别,也学习了插入排序算法。

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

  3. //------线性表的动态分配顺序存储结构------
  4. #define LIST_INIT_SIZE 100  //线性表存储空间的初始分配量
  5. #define LISTINCREMENT 10
  6. #define OK 1
  7. #define ERROR 0
  8. #define OVERFLOW -2

  9. typedef int elemType;  //考虑到可扩展性,定义数据元素类型
  10. typedef int Status;
  11. typedef struct {
  12.     elemType * elem;  //存储空间基址
  13.     int length;  //当前长度
  14.     int listsize;  //当前分配的存储容量(以sizeof(elemType)为单位)
  15. }SqList;

  16. Status InitList_Sq(SqList * L);
  17. void InsertLast(SqList * L, elemType e);
  18. Status ListInsert_Sq(SqList * L, int i, elemType);
  19. Status ListDelete_Sq(SqList * L, int i, elemType *e);
  20. Status AgainMalloc(SqList * L);
  21. void TraverseList(SqList * L);
  22. int LocateElem_Sq(SqList L, elemType e,
  23.                   Status (* compare)(elemType, elemType));
  24. Status compare(elemType a, elemType b);
  25. void InsertSort(SqList L);
  26. void MergeList_Sq(SqList La, SqList Lb, SqList* Lc);

  27. int main()
  28. {
  29.     int i;
  30.     int tmp;
  31.     SqList list1;
  32.     InitList_Sq(&list1);

  33.     //向线性表插入元素
  34.    printf("尾插法插入e,输入e(输q退出):");
  35.     while(scanf("%d",&tmp))
  36.     {
  37.         InsertLast(&list1, tmp);
  38.         printf("头插法插入e,输入e(输q退出):");
  39.     }
  40.     printf("插入元素后的list1:");
  41.     TraverseList(&list1);

  42.     getchar();
  43.     //在顺序表中第i个位置之前插入新的元素e
  44.     printf("输入i(输q退出):");
  45.     while(scanf("%d", &i))
  46.     {
  47.         printf("输入元素e:");
  48.         scanf("%d", &tmp);
  49.         ListInsert_Sq(&list1, i, tmp);
  50.         printf("输入i(输q退出):");
  51.     }
  52.     printf("插入元素后的list1:");
  53.     TraverseList(&list1);

  54.     getchar(); //为了缓冲
  55.     printf("删除一个元素\n");
  56.     printf("输入i:");
  57.     scanf("%d", &i);
  58.     ListDelete_Sq(&list1, i, &tmp);
  59.     printf("删除一个元素后的线性表list1=");
  60.     TraverseList(&list1);
  61.     printf("删除的元素e: %d\n", tmp);


  62.     SqList list2;
  63.     InitList_Sq(&list2);

  64.      //向线性表插入元素
  65.    printf("尾插法插入e,输入e(输q退出):");
  66.     while(scanf("%d",&tmp))
  67.     {
  68.         InsertLast(&list2, tmp);
  69.         printf("头插法插入e,输入e(输q退出):");
  70.     }
  71.     printf("插入元素后的list2:");
  72.     TraverseList(&list2);

  73.     printf("排序线性表:\n");
  74.     InsertSort(list1);
  75.     printf("排序后的线性表list1:");
  76.     TraverseList(&list1);

  77.     InsertSort(list2);
  78.     printf("排序后的线性表list2:");
  79.     TraverseList(&list2);

  80.     SqList list3;
  81.     InitList_Sq(&list3);
  82.     MergeList_Sq(list1, list2, &list3);
  83.     printf("list1和list2的合集list3=");
  84.     TraverseList(&list3);
  85. }

  86. // 构造一个空的线性表L。
  87. Status InitList_Sq(SqList * L)
  88. {
  89.     L->elem = (elemType * )malloc(LIST_INIT_SIZE*sizeof(elemType));
  90.     if(!L->elem) exit(OVERFLOW);
  91.     L->length = 0;
  92.     L->listsize = LIST_INIT_SIZE;
  93.     return OK;
  94. }

  95. //向表尾插入元素
  96. void InsertLast(SqList * L, elemType e)
  97. {
  98.     if(L->length >= L->listsize)
  99.         AgainMalloc(L);
  100.     L->elem[L->length] = e;
  101.     L->length++;
  102.     return;
  103. }

  104. // 在顺序线性表L中第i个位置之前插入新的元素e,
  105. // i的合法值为1=<i<=ListLength_Sq(L)+1
  106. Status ListInsert_Sq(SqList * L, int i, elemType e)
  107. {
  108.     elemType * q, * p;
  109.     if(i<1 || i>L->length+1) return ERROR;
  110.     if(L->length >= L->listsize) //当前存储空间已满,增加分配
  111.     AgainMalloc(L);

  112.     q = &(L->elem[i-1]); //q为插入位置
  113.     for(p=&(L->elem[L->length-1]); p>=q; --p) *(p+1) = *p;
  114.                                     //插入位置及之后的元素右移
  115.     *q = e;
  116.     ++L->length;
  117.     return OK;
  118. }

  119. Status AgainMalloc(SqList * L) //空间不够时重新分配空间的函数
  120. {
  121.     elemType * newbase; //分配一个临时基址
  122.     newbase = (elemType *)realloc(L->elem, (L->listsize+LISTINCREMENT)*sizeof(elemType));
  123.     if(!newbase) exit(OVERFLOW);
  124.     L->elem = newbase; //新基址
  125.     L->listsize += LISTINCREMENT;
  126.     return OK;
  127. }

  128. void TraverseList(SqList * L)
  129. {
  130.     int i;
  131.     for(i=0; i<L->length; i++)
  132.         printf("%d ", L->elem[i]);
  133.     printf("\n");
  134.     return;
  135. }

  136. Status ListDelete_Sq(SqList * L, int i, elemType * e)
  137. {
  138.     //在顺序表L中删除第i个元素,并用e返回其值
  139.     //i的合法值为1=<i<=ListLength_Sq(L)
  140.     if((i<1) || (i>L->length)) return ERROR; //i值不合法

  141.     *e = L->elem[i-1]; //被删除元素的值赋给e

  142.     for(; i<L->length; i++)
  143.     {
  144.         L->elem[i-1] = L->elem[i];
  145.     }
  146.     L->length--;

  147.     return OK;
  148. }

  149. int LocateElem_Sq(SqList L, elemType e,
  150.                   Status (* compare)(elemType, elemType))
  151. {
  152.     //在顺序表L中查找第1个值与e满足compare()的元素的位符
  153.     //若找到,则返回其在L中的位序,否则返回0
  154.     int i = 1;
  155.     elemType * p = L.elem;
  156.     while(i<=L.length && !compare(*(p++), e)) ++i; //(*compare)
  157.     if(i<=L.length) return i;
  158.     else return 0;
  159. }

  160. Status compare(elemType a, elemType b)
  161. {
  162.     if(a==b) return OK;
  163.     else return ERROR;
  164. }

  165. void InsertSort(SqList L)
  166. {
  167.     //递增排序线性表
  168.     for(int i=1; i<L.length; i++){
  169.         if(L.elem[i] < L.elem[i-1]){               //若第i个元素大于i-1元素,直接插入。小于的话,移动有序表后插入
  170.             int j= i-1;
  171.             int x = L.elem[i];        //复制为哨兵,即存储待排序元素
  172.             L.elem[i] = L.elem[i-1];           //先后移一个元素
  173.             while(j > -1 && x < L.elem[j]){  //查找在有序表的插入位置
  174.                 L.elem[j+1] = L.elem[j];
  175.                 j--;         //元素后移
  176.             }
  177.             L.elem[j+1] = x;      //插入到正确位置
  178.         }
  179.     }

  180. }

  181. void MergeList_Sq(SqList La, SqList Lb, SqList* Lc)
  182. {
  183. //已知顺序线性表La和Lb的元素按值非递减排列
  184. //归并La和Lb得到新的顺序线性表Lc,Lc的元素也按值非递减排列
  185. elemType * pa, * pb, *pc;
  186. pa = La.elem; pb = Lb.elem;
  187. Lc->listsize = Lc->length = La.length+Lb.length;
  188. pc = Lc->elem = (elemType *)malloc(Lc->listsize*sizeof(elemType)); //可以两次调用malloc
  189. if(!Lc->elem) exit(OVERFLOW);  //存储分配失败
  190. elemType * pa_last, * pb_last;
  191. pa_last = La.elem + La.length - 1;
  192. pb_last = Lb.elem + Lb.length - 1;
  193. while(pa<=pa_last && pb<=pb_last)
  194. {
  195.     if(*pa <= *pb) *(pc++) = *(pa++);
  196.     else *(pc++) = *(pb++);
  197. }
  198. while(pa<=pa_last) *(pc++) = *(pa++);
  199. while(pb<=pb_last) *(pc++) = *(pb++);
  200. }

复制代码


参考资料:
排序算法
函数指针和指针函数

本帖被以下淘专辑推荐:

楼层
跳转到指定楼层

发表回复

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

本版积分规则

关闭

小甲鱼强烈推荐 上一条 /3 下一条

    移动客户端下载(未启用)
    微信公众号

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备11014136号

Copyright 2018 鱼C论坛 版权所有 All Rights Reserved.

Powered by Discuz! X3.1 Copyright
© 2001-2018 Comsenz Inc.    All Rights Reserved.

小黑屋|手机版|Archiver|鱼C工作室 ( 粤公网安备 44051102000370号 | 粤ICP备11014136号

GMT+8, 2017-11-22 15:39

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