线性表、栈队列.doc

《线性表、栈队列.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、顺序表基本操作的实现使用顺序存储结构，线性表的某些操作很容易实现。图2.1给出了采用顺序存储结构的线性表部分操作的实现。第1行定义了一个常数值MAXSIZE，表示线性表的最大长度，示例中将其设为999。第2行把ELEMTYPE设置为int的一个别名，这样，这个例子就可以使用一组整数了。第3行到第7行包含了线性表的说明。接下来从第8行到第70行是线性表操作函数的实现。第9到第12行完成将线性表置成空表操作。将线性表置成空表，只需简单地将线性表元素个数置成0（numinlist=0）即可。函数isEmpty（第14行到第17行）判断线性表是否为空，如果线性表为空（没

2、有元素），函数返回1，否则返回0。函数length（第19行到第22行）返回线性表中元素个数。由于线性表的长度已经记录在变量numinlist中，因此函数length只是简单返回numinlist的值。第24到第29行实现追加操作。函数append完成在线性表的表尾插入一个元素。函数首先检查线性表是否已满（第26行），如果线性表已满，程序结束，否则即可将新元素插入到表尾位置，并将线性表长度增1，插入位置由numinlist指示。第31行到第40行的函数insert完成线性表的插入操作。在线性表中第i位置插入一个新元素item时，函数首先判断插入位置是否合法，以及

3、表是否已满，如果插入位置不合法或表已满，程序结束。否则通过for循环将最后一个元素到第i个元素逐个向后移动，最后将item插入到第i个位置，且线性表的长度加1。第42行到第53行完成删除元素操作。函数首先判断删除位置i是否合法，或表中是否有元素，如果删除位置不合法或表为空表，程序结束。否则先将被删除元素的值保存在临时变量temp中，然后通过一个for循环将被删除元素到最后一个元素逐个向前移动，最后将表的长度减1，并将被删除元素的值返回。第55行到第62行的函数search在线性表中搜寻第一个出现的值为item的元素。如果值item找到了，函数返回元素item所在

4、位置，否则返回-1，表示线性表中不存在元素item。函数traversal（第64行到第70行）对线性表进行遍历。遍历操作只是通过一个for循环将表中元素逐个输出。第72行到第87行是main函数的一个例子，说明了线性表的顺序表实现。74行调用init函数将线性表清空，第75，76，77三行调用append函数追加三个元素。insert(2,15)（79行）在位置2插入一个元素15。81的search(15)在表中查找元素15。第85行调用del函数删除位置1的元素。1#defineMAXSIZE9992typedefintELEMTYPE;3structlis

5、t{4ELEMTYPEelement[MAXSIZE];5intnuminlist;6};7structlistl;89voidinit()10{11l.numinlist=0;12}1314intisEmpty()15{16return(l.numinlist==0);17}1819intlength()20{21returnl.numinlist;22}2324voidappend(ELEMTYPEitem)25{26if(l.numinlist>MAXSIZE)27exit(0);28l.element[l.numinlist++]=item;29}303

6、1voidinsert(inti,ELEMTYPEitem)32{33intj;34if(i<0

7、

8、i>l.numinlist

9、

10、l.numinlist>MAXSIZE)35exit(0);36for(j=l.numinlist;j>i;j--)37l.element[j]=l.element[j-1];38l.element[i]=item;39l.numinlist++;40}4142ELEMTYPEdel(inti)43{44intj;45ELEMTYPEtemp;46if(i<0

11、

12、i>=l.numinlist

13、

14、l.numinlist==0)47exi

15、t(0);48temp=l.element[i];49for(j=i;j

16、++)68printf(