线性表之顺序存储结构

《线性表之顺序存储结构》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、线性表之顺序存储结构数据结构和算法是程序设计的灵魂。坦诚的说，我在这方面是弱的可以。虽然工作这么多年了，因为种种借口，这块知识一直是我的痛处。曾经在面试时大言不惭的说，这些知识在工作屮很少用到，所以当年学习的东西早就还给学校了。其实不然，失去了灵魂的程序员如我，总是要逆袭的。所以以后的学习中会有一些如孩童笔记般的文章出现在我的blog中，请大师们不要嘲笑，要提携。定义线性表可以说是最简单的数据结构，它的描述为：n个数据元素的有限序列。记为：L=(al,a2,...,an)按照存储结构它乂可以分为顺序存储结构和链式存储结构。而其中线性表的顺序存储结构是最简单最常用的数据

2、结构：用一段连续地址依次存储表中的数据元素。看到这里，我们会自然的联想到C语言中的数组。下而我要实现的是线性表中的元素为整型的顺序存储结构，及它的主要运算.•增删查。先来简单的定义一下这个线性表的顺序存储结构：^defineMAXLENGTH20structsequencelist{intdata[MAXLENGTH];intlength;}；其中data数组为这个线性表的主要部分，数据元素就存在于此数组中，而对这个线性表的操作都是基于这个数组。length是这个线性表的一个属性，表示这个线性表包含元素的个数。线性表的插入操作对线性表的插入就是对data数组的插入，然

3、后将其length增加。//insertoprationintinsert(structsequencelist氺list，intindex,intelement)intlength=list->lcngth;if(length==0

4、

5、index<0

6、

7、index〉length

8、

9、length>=MAXLENGTH)returnERROR;list~>data[index]=element;for(inti=length-1;i>index;i—){list—>data[i+l]=list—>data[i];}list~>length++;returnOK;}删：线

10、性表的删除操作类似增的相反操作。//Deleteoprationintdelete(structsequencelist氺list，intindex){intlength=list->length;if(length==0

11、

12、index<0

13、

14、index>length-1)returnERROR;for(inti=index;i〈length一1;i十十){list->data[i]=list->data[i+l];}list->data[length-1]=’’;//deletethelastelement.1ist->length—;returnOK;}查：线

15、性表的取元素操作用索引值查找元素的值。//getlistelements//makesureelemetisNOTNULLwhencalling.intgctElcmcnt(structscqucncclistlist,intindex,int氺element){printf(，zgetElement，z);intlength=list.length;printf(，zlengthis%d〃，length);if(length==0

16、

17、index<0

18、

19、index>=length)returnERROR;氺element=list.data[index];

20、returnOK;}从程序中可以看出增删操作的时间复杂度都是0(n)，所以这两项操作都是不是它的强项。而查找操作的时间复杂度是0(1),那么线性表的顺序存储结构的优势就是可以快速的取出任意位置的元素。上面的3种操作作为较为基本的操作，是本人的学笔记。如果人虾们发现哪里有不妥，请不吝赐教。而线性表的其他操作如求前驱元素、求后驱元素、判断表中是否存在某元素值、清空操作等等有意思的操作还待空闲时去完成。较为完整的调试例子：//2013.2//lincoln//linearlist//SequenceStorageStructure//^include^de

21、fineOK1ttdefineERROR-1^defineTURK1#dcfincFALSE0^defineMAXLENGTH20structsequencelist{intdata[MAXLENGTH];intlength;}；//getlistelements//makesureclcmctisNOTNULLwhencalling.intgetElement（structsequencelistlist,intindex,int氺element）{printf（〃getElement〃）；intlength=list.length;pri