[关闭]
@coder-pig 2019-05-31T06:01:56.000000Z 字数 4106 阅读 1091

小猪的数据结构辅助教程——2.1 线性表中的顺序表

数据结构


本节学习路线图与学习要点

学习要点

  • 1.抽象数据类型(ADT)的概念,三要素:数据,数据元素间的关系和数据的操作
  • 2.线性表的特点:按照一条线排列的数据集合,1对1,除了首元和尾元,其他元素都有直接前驱和直接后继
  • 3.牢记线性表的存储结构,要理解并熟悉12个基本操作的逻辑,最好能徒手撕出代码
  • 4.求并集,顺序表的经典例子,必须掌握!

1.抽象的数据类型

简单点说:

抽象:有点像我们面向对象语言中的类的思想,将事物的共性抽取出来,形成属性和对应的方法!
数据类型:比如我们C中学的整型,浮点型等这些就是数据类型,就是具有同一性质的集合;
另外定义浮点类型是为了避免一些麻烦,比如保存2这个整数用浮点型就有点大材小用了~


2.线性表介绍以及顺序表的引入

从上面的存储结构,不难知道顺序表的三个属性:
存储空间的其实位置;最大存储容量listsize;当前长度length;


3.12个基本操作的代码实现

PS:别去死记代码,把逻辑掌握就好,不清楚自己列几个数据,画画图!


线性表的存储结构

  1. #define MAXSIZE 20
  2. #define INCREMENT 10
  3. #define OK 1
  4. #define ERROR 0
  5. #define TRUE 1
  6. #define FALSE 0
  7. //定义一个int数据类型的别名
  8. //这里因为演示采用int,实际使用的通常是复合的数据类型
  9. typedef int ElemType;
  10. typedef int Status;
  11. typedef struct{
  12. ElemType *elem; //存储空间的起始地址
  13. int length; //表的当前长度
  14. int listsize; //表的总存储容量(以sizeof(ElemType)为单位)
  15. }SqList;

1.构造空表

  1. void InitList(SqList *L){
  2. L -> elem = (ElemType *)malloc(MAXSIZE * sizeof(ElemType));
  3. if(!L -> elem)exit(ERROR);
  4. L -> length = 0;
  5. L -> listsize = MAXSIZE;
  6. }

步骤:

  • Step 1:申请表的存储空间,将空间的起始地址赋值给elem,
    然后通过判断elem是否为空,从而知道内存是否分配成功
  • Step 2:将表的当前长度length设置为0,将表的大小listsize设置为MAXSIZE

2.将表置为空表

  1. void ClearList(SqList *L)
  2. {
  3. L ->length = 0;
  4. }

步骤:

只需将表长设置为空即可,很简单


3.判断表是否为空

  1. //3)判断表是否为空
  2. Status ListEmpty(SqList L)
  3. {
  4. return L.length == 0?TRUE:FALSE;
  5. }

步骤:

只需判断表长是否为0即可


4.销毁表

  1. //4)销毁表
  2. void DestoryList(SqList *L)
  3. {
  4. free(L ->elem);
  5. L ->elem = NULL;
  6. L ->length = 0;
  7. L ->listsize = 0;
  8. }

步骤:

  • Step 1:调用free方法释放L.elem所指向的内存空间
  • Step 2:将L.elem赋值为NULL
  • Step 3:将当前的表长以及表的存储容量设置为0

5.获得表中元素的数目

  1. int ListLength(SqList L)
  2. {
  3. return L.length;
  4. }

步骤:

直接返回当前表长度即可


6.获得表中第i个元素的值

  1. Status GetElem(SqList L,int i,ElemType *e)
  2. {
  3. if(i < 1||i > L.length)return ERROR;
  4. e = *(L.elem + i - 1);
  5. return OK;
  6. }

步骤:

Step 1:先判断第i个位置是否合法
Step 2:将对应位置的值赋给e,另外这里减1是因为数组下标是从0开始算的,而我们看表是
从1开始算的,所以需要减一


7.查找表中是否有满足要求的元素

  1. int LocateElem(SqList L,ElemType e,Status(*compare)(ElemType,ElemType))
  2. {
  3. int i = 1;
  4. ElemType *p = L.elem;
  5. while(i < L.length && !compare(*p++,e))
  6. i++;
  7. if(i <= L.length) return i;
  8. else return 0;
  9. }

步骤:

Step 1:定义变量i和指针p分别指向表中第1个元素和表的首地址
- Step 2:循环调用compare()函数与表中的元素进行比较
- Step 3:如果i <= length的话说明找到了,返回对应元素的序号
- Step 4:否则返回0,表示找不到满足要求的元素


8.返回某个节点的前驱

  1. Status PriorElem(SqList L,ElemType choose,ElemType &Before){
  2. int i = 2;
  3. ElemType *p = L.elem + 1;
  4. while(i < L.length && *p != choose)
  5. {
  6. p++;
  7. i++;
  8. }
  9. if(i > L.length)return ERROR;
  10. else
  11. {
  12. Before = *--p;
  13. return OK;
  14. }
  15. }

步骤:

Step 1:首元是没有直接前驱的,所以i应该从2开始,所以P从L.elem + 1开始;
Step 2:循环查看数据元素在表中的位置,如果i > 表长表示找不到,返回ERROR;
Step 3:找到的话,通过*--p获得该元素的前驱的值赋值给before;


9.返回某个节点的后继

  1. Status NextElem(SqList L,ElemType choose,ElemType *behind)
  2. {
  3. int i = 1;
  4. ElemType *p = L.elem;
  5. while(i < L.length && *p != choose)
  6. {
  7. p++;
  8. i++;
  9. }
  10. if(i == L.length)return ERROR;
  11. else{
  12. behind = * ++p;
  13. return OK;
  14. }
  15. }

步骤:

和前驱那个差不多,不过要注意i == L.length就到头了,因为尾元是没有后继的!


10.往表中第i个位置插入元素

  1. Status ListInsert(SqList *L,int i,ElemType e)
  2. {
  3. ElemType *p,*q,*newbase;
  4. //判断插入位置是否合法
  5. if(i < 1 || i > L -> length + 1)return ERROR;
  6. //假如表满了的话,增加分配的空间
  7. if(L -> length == L -> listsize)
  8. {
  9. newbase = (ElemType *)realloc(L -> elem,(L -> listsize + INCREMENT)*sizeof(ElemType));
  10. if(!newbase)exit(ERROR);
  11. L ->elem = newbase;
  12. L ->listsize += INCREMENT;
  13. }
  14. //插入位置
  15. q = L ->elem + i - 1;
  16. //向右移,先移动最后一个
  17. for(p = L ->elem + L->length - 1;p >= q;--p)
  18. {
  19. *(p + 1) = *p;
  20. }
  21. * q= e; //插入元素
  22. ++ L ->length; //表长 + 1
  23. return OK;
  24. }

步骤:


11.删除表中的第i个位置的元素

  1. Status ListDelete(SqList *L,int i,ElemType *e)
  2. {
  3. ElemType *p,*q;
  4. //判断删除的位置是否合法
  5. if(i < 1 || i > L ->length)return ERROR;
  6. //P指针指向删除位置,将要删除的元素赋值给e
  7. p = L ->elem + i - 1;
  8. e = *p;
  9. //q指针指向最后一个元素,从删除位置后的元素开始左移
  10. q = L ->elem + L ->length - 1;
  11. for(++p;p <= q;++p)
  12. {
  13. *(p - 1) = *p;
  14. }
  15. L ->length--; //表长-1
  16. return OK;
  17. }

步骤:


12.遍历表中的所有元素

  1. void ListTraverse(SqList L,void(* visit)(ElemType))
  2. {
  3. int i;
  4. ElemType *p = L.elem;
  5. for(i = 1;i < L.length;i++)
  6. {
  7. visit(*p++);
  8. printf("\n");
  9. }
  10. }

步骤:

很简单,就是从第一个元素开始,指针后移动,依次调用visit()函数
实现表中元素的遍历而已


4.应用小示例:

问题
已知A,B两个顺序表中的元素是按从小到大排列的;现在要你求两个的并集C;
而且C中的元素也要按从小到大排序;不改变A和B中的数据!
是并集哦,就是C中不能有重复的元素

  1. void UnionList(SqList La,SqList Lb,SqList *Lc)
  2. {
  3. //1.定义指向表A,B表头,表尾的指针
  4. ElemType *la,*la_end,*lb,*lb_end,*lc;
  5. la = La.elem;
  6. lb = Lb.elem;
  7. la_end = La.elem + La.length - 1;
  8. lb_end = Lb.elem + Lb.length - 1;
  9. //2.为表C分配内存空间,大小为表A长度 + 表B的长度
  10. Lc ->listsize = La.length + Lb.length;
  11. lc = Lc ->elem = (ElemType *)malloc(Lc ->listsize * sizeof(ElemType));
  12. if(!lc)exit(ERROR);
  13. //3.将表A和B中的元素进行合并,
  14. while(la <= la_end && lb <= lb_end)
  15. {
  16. if(*la <= *lb)*lc++ = *la++;
  17. else *lc++ = *lb++;
  18. }
  19. //4.假如有剩余的元素,要么是表A,要么是表B的
  20. while(la < la_end)*lc++ = *la++;
  21. while(lb < lb_end)*lc++ = *lb++;
  22. //5.接着要将C表中重复的元素删除掉,这里来两枚指针
  23. ElemType *p,*q;
  24. p = Lc ->elem;
  25. q = p;
  26. //6.循环,假如入指针p没有指向表尾
  27. while(p != (Lc ->elem + Lc ->length - 1))
  28. {
  29. //q指向p的后继元素,比较两数的值
  30. if(*p != *(++q))
  31. {
  32. p++;
  33. q = p;
  34. }
  35. //相等的话,删除q所指向的元素
  36. else
  37. {
  38. while(*p == *q);
  39. // ListDelete(Lc,(p - Lc ->elem),e);
  40. }
  41. }
  42. }

5.本节代码下载:

时间关系,明早回公司再贴出来哈~


添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注