数据结构之线性表 Bertha 。 2022-06-15 01:14 218阅读 0赞 ## 基本概念 ## 线性表(List):由零个或多个数据元素组成的有限序列。 特征: 1.线性表是一个序列。 2.0个元素构成的线性表是空表。 3.线性表中的第一个元素无前驱,最后一个元素无后继,其他元素有且只有一个前驱和后继。 4.线性表是有长度的,其长度就是元素个数,且线性表的元素个数是有限的,也就是说,线性表的长度是有限的。 # 线性表抽象数据类型 # 基于线性表的特征,线性表可以做如下操作: * InitList(\*L);//初始化操作,建立一个空的线性表 * ListEmpty(L);//若线性表为空,返回true,否则返回false * ClearList(\*L);//清空线性表 * GetElem(L,i,\*e);//查找线性表中的第i个位置的元素值,并赋值给e * LocateElem(L,e);//查找线性表L中与给定值e相等的元素,如果查找成功,则返回第一个相同的元素在L //中的下标;否则,返回0表示失败 * ListInsert(\*L,i,e);//在线性表L的第i个位置插入元素e * ListDelete(\*L,i,\*e);//删除线性表L中第i个位置元素,并用e返回其值 * ListLength();//返回线性表L的长度 线性表和线性表可以进行叠加操作,线性表La和线性表Lb的并集操作,结果保存在La中的伪代码如下: **\[java\]** [view plain][] [copy][view plain] [print][view plain] [?][view plain] 1. //实现线性表La和线性表Lb的并集操作,结果保存在La中 2. **void** UnionList(\*La,Lb) 3. \{ 4. //计算Lb长度 5. **int** lblength = ListLength(Lb); 6. //计算La长度 7. **int** laLength = ListLength(La); 8. **int** i ; 9. //便利Lb中所有元素,判断其是否在La中,若不在,则插入La中 10. **for** (i=0;i<length;i++) 11. \{ 12. ElemType temp = GetElem(Lb,i,\*e); 13. **if** (LocateElem(La,temp)==0) 14. \{ 15. ListInsert(La,++laLength,temp); 16. \} 17. \} 18. \} # 线性表的存储结构 # 根据其字面意思,线性表是顺序存储的,用一段地址连续的存储单元依次存储线性表的数据元素。 如: **\[objc\]** [view plain][] [copy][view plain] [print][view plain] [?][view plain] 1. \#define MAXSIZE 20;//存储空间初始分配量为20 2. **typedef** **int** ElemType;//数据类型为int 3. type **struct** 4. \{ 5. ElemType data\[MAXSIZE\];//数组存储数据元素 6. intlength;//线性表长度 7. \}; ### 关于线性表地址长度的计算 ### 由于顺序存储结构是按照顺序存储的,所以每个数据元素的地址都可以根据第一个元素的地址推算出来。其计算公司LOC(ai) = LOC(a1)+ (i-1)\*c ![20161209100626996][] # 线性表的基本操作 # 线性表基本操作包含基本的CRUD操作。 ## 插入操作 ## 插入操作算法的思路是: 1.如果插入位置不合理,抛出异常。 2.如果线性表长度大于等于数组长度,则抛出异常或者增加数组长度。 例如:在线性表L的第i个位置插入元素e **\[objc\]** [view plain][] [copy][view plain] [print][view plain] [?][view plain] 1. **int** ListInsert(**Sqlist** \*L, **int** i, ElemType e) \{ 2. //插入位置错误,返回0 3. **if** (i < 0 || i > L.Length) 4. \{ 5. **return** 0; 6. \} 7. 8. //线性表的长度大于等于数组的最大长度,返回0 9. **if** (L.Length >= MAXSIZE) 10. \{ 11. **return** 0; 12. \} 13. 14. **int** j = L.Length -1; 15. //从第i个元素到最后一个元素,每个元素后移一位 16. **while** (j >= i) 17. \{ 18. L.data\[j+1\] = L.data\[j\]; 19. j--; 20. \} 21. 22. //第i个元素的位置放入e 23. L.data\[i\] = e; 24. 25. //线性表长度加1 26. L.Length ++; 27. \} ## 删除操作 ## 删除操作的思路是: 1.如果删除位置不合理,抛出异常 2.取出删除元素 3.从删除位置开始遍历到最后一个元素,分别将她们都向前移动一个位置 4.表长减1 例如:我们要删除一个线性表的某一个元素 **\[objc\]** [view plain][] [copy][view plain] [print][view plain] [?][view plain] 1. **int** ListDelete(**SqList** \*L,**int** i,**ElemType** \*e) \{ 2. //如果删除的位置不对,则返回0 3. **if** (i < 0 || i > L.Length -1) 4. \{ 5. **return** 0; 6. \} 7. 8. \*e = L.data\[i-1\]; 9. 10. **for** (j = i-1;i <L.Length\-2;j++ ) 11. \{ 12. L.data\[j\] = L.data\[j+1\]; 13. \} 14. 15. L.Length --; 16. **return** 1; 17. \} ## 查询操作 ## 查询操作是比较简单的,例如:我们要在线性表中查询某个元素的位置。 **\[objc\]** [view plain][] [copy][view plain] [print][view plain] [?][view plain] 1. **int** GetElem(SqList L,**int** i, **ElemType** \* e) 2. \{ 3. //线性表长度等于0或者获取元素位置错误返回0 4. **if** (L.Length == 0 || i < 0 || i > L.Length) 5. \{ 6. **return** 0; 7. \} 8. 9. 返回第i个元素 10. \*e = L.data\[i-1\]; 11. **return** 1; 12. \} ### 线性表的缺点 ### ## 顺序表需要预分配一定长度的存储空间,不能动态增长,插入或删除比较麻烦。基于线性表的缺点,有了链式存储线性表。链式存储的特点: ## **\[objc\]** [view plain][] [copy][view plain] [print][view plain] [?][view plain] 1. **typedef** **struct** Node 2. \{ 3. ElemType data; 4. **struct** **Node** \*next; 5. \} Node; 6. **typedef** **struct** **Node** \*LinkList; ## 线性表查询 ## 算法思路是: 1.声明一个节点p指向链表第一个节点,初始化j从1开始 2.当j< i时,就遍历链表,让P的指针向后移动,不断指向下一个节点,j累加1 3.若到链表末尾p为空,则说明第i个元素不存在 4.否则查找成功,返回节点p的数据 **\[objc\]** [view plain][] [copy][view plain] [print][view plain] [?][view plain] 1. **int** GetElem(LinkList L,**int** i,**ElemType** \*e) 2. \{ 3. **int** j; 4. LinkList p; 5. p = L->next;//p指向链表第一个节点 6. **while** (p && j < i ) 7. \{ 8. p = p->next; 9. j++; 10. \} 11. 12. **if**(!p || count > i) 13. **return** 0; 14. 15. \*e = p->data; 16. **return** 1; 17. \} 18. [view plain]: http://blog.csdn.net/xiangzhihong8/article/details/53535160# [20161209100626996]: /images/20220615/59cf456f0e1d403980e8105bf804d4a1.png
还没有评论,来说两句吧...