第2章 线性表

《第2章 线性表》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章线性表一、线性表的基本概念1、定义线性表（LinearList）：是由n(n>0)个性质相同的数据元素组成的有限序列，记为(a1,a2,a3,…,an)。表中数据元素的个数n定义为线性表的长度。n=0的表称为空表，即该线性表不包含任何数据元素。这里的数据元素ai(1≦i≦n)只是一个抽象的符号，其具体含义在不同的情况下可以不同。例1、26个英文字母组成的字母表（A，B，C、…、Z）是一个线性表。例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况表也是一个线性表。（6，17，28，50，9

2、2，188）2、线性表的逻辑特征从以上的定义及例子可以看出，线性表具有以下逻辑特征：1）在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2；2）有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋an-1；其余的内部结点ai(2≦i≦n-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1。线性表是一种典型的线性结构。二、线性表的存储结构（一）顺序存储结构1、概念及特点顺序表：即用一组连续的存储单元依次存放线性表的数据元素。若每个数据元素占用k个存储单元，并以所占的第

3、一个存储单元地址作为这个数据元素的存储位置，则表中任一元素ai的存储地址为：LOC(ai)=LOC(a1)+(i-1)*k　　　　(n为结点总数，1≤i≤n)Loc(a1)Loc(a2)=Loc(a1)+kLoc(ai)=Loc(a1)+(i-1)*kLoc(an)=Loc(a1)+(n-1)*k┇a1a2┇ai┇an┇顺序表的特点：表中相邻的元素ai和ai+1有相邻的存储位置LOC(ai)和LOC(ai+1)。即顺序表中各数据元素在存储空间中是按逻辑顺序依次存放的，如下图：2、顺序表的结构类型定义/*顺序表

4、的定义：*/#defineListSize100/*表空间大小可根据实际需要而定，这里假设为100*/typedefintDataType;/*DataType可以是任何相应的数据类型如int,float或char*/typedefstruct{DataTypedata[ListSize];/*向量data用于存放表结点*/intlength;/*当前的表长度*/}SeqList;3、顺序表的基本运算主要包括：顺序表的查找、插入及删除。1）顺序表的建立及打印算法/*顺序表的建立：*/voidCreateLis

5、t(SeqList*L,intn){inti;for(i=0;idata[i]);L->length=n;}/*顺序表的打印：*/voidPrintList(SeqListL,intn){inti;for(i=0;i

6、data[i]!=x)++i;if(i

7、,inti){/*将新结点x插入L所指的顺序表的第i个结点的位置上*/intj;if(i<1

8、

9、i>L->length+1){printf("插入位置非法");exit(0);}if(L->length>=ListSize){printf("表空间溢出，退出运行");exit(0);}for(j=L->length-1;j>=i-1;j--)L->data[j+1]=L->data[j];/*从表尾元素到第i个元素逐个后移*/L->data[i-1]=x;/*新元素插入*/L->length++;/*

10、修正表长*/}插入过程可以参看“线性表的插入.swf”动画文件。4）顺序表的删除算法线性表的删除运算是指将表的第i(1≦i≦n)结点删除，使长度为n的线性表：(a1，…ai-1，ai，ai+1…，an)变成长度为n-1的线性表(a1，…ai-1，ai+1，…，an)算法如下：/*顺序表的删除：*/voidDeleteList(SeqList*L,inti){/*从L所指的顺序表中删除第i个结点*/i