第2章+线性表_1_顺序表

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

1、第2章线性表2.1线性表的定义和运算一、线性表的定义：1、定义：线性表L是由n个元素a1，a2，…，an组成的有限序列。记作L=(a1,a2,…,an)注：（1）n>=0为表长；（2）n=0时为L空表；记作L=（）如：字母表{A,B,C,…,Z}数字表（0,1,2,3,…,9）（同一表中，元素类型相同。）2、特点：…,ai-1,ai,ai+1,…ai-1称为ai的直接前驱，ai+1称为ai的直接后继。除首元素外每个元素有且仅有一个直接前驱；除尾元素外每个元素有且仅有一个直接后继；二、线性表的基本运算（1）初始化initial_list（L）建空表；（2）求表长l

2、ist_length（L）（3）按序号取元素get_element（L，i）（4）按值查找list_locate（L，x）（5）插入list_insert（L，i，x）在表中第i个位置上插入元素x；1≤i≤n+1（6）删除list_delete（L，i）删除表中第i个元素;1≤i≤n2.2顺序表一、线性表的顺序存储结构1、定义：假设有一个足够大的连续的存储空间，将线性表中的元素按其逻辑次序依次存储到这一存储空间中，由此方式存储的线性表称为顺序表。顺序表示意图seqlista1a2a3a4…andatamaxlen-10123listlenn-12、类型描述#de

3、finemaxlen100typedefstruct{elementtypedata[maxlen]；intlistlen；}seqlist；变量定义，如：seqlistL，L1；注：a：data[maxlen]的下标是0到maxlen-1；b：listlen是线性表的长度，最后一个元素下标是listlen-1；3、顺序表的特点：逻辑上相邻的元素，其存储地址也相邻；即，可以随机存取元素。二、顺序表运算的实现1、初始化（建空表）：voidinitial_list（seqlist*L）{L->listlen=0;}2、求表长：intlist_length（seqli

4、stL）{returnL.listlen;}3、按序号取元素：voidget_element(seqlistL,inti,elementtype&x){if(i<1

5、

6、i>L.listlen)error(“序号错”);elsex=L.data[i-1];}4、按值查找：（找到则返回其序号，否则返回0）intlist_locate（seqlistL，elementtypex）{inti;for(i=0;i

7、stListlenmaxlen-1012i-1iana1a2a3…ai…dataseqlistListlenmaxlen-1012i-1x全部向后移一个位置分析：首先判断顺序表是否为满，以及i的取值；若可以插入，则执行下列操作：(1)将ai~an后移一位；(2)插入x；(3)表长+1voidlist_insert(seqlist*L,inti,elementtypex){intj;if(L->listlen==maxlen)error(“溢出”);elseif(i<1

8、

9、i>L->listlen+1)error(“序号错误”);else{for(j=L->lis

10、tlen-1;j>=i-1;j--)L->data[j+1]=L.data[j];L->data[i-1]=x;L->listlen++;}}插入算法的时间分析在i=1，2，…，n+1时，元素移动的次数分为n，n-1，…，0。平均移动次数（等概率情况下）：(0+1+…+n)/(n+1)=n/26、删除：maxlen-1…a1a2a3…ai-1ai+1dataanseqlistListlen012i-2i-1ai被删除maxlen-1…a1a2a3…aiai+1dataanseqlistListlen012i-1i全部向前移一个位置×分析：首先判断顺序表是否为空

11、以及i的取值；可以则删除：(1)ai+1~an往前移一位；(2)表长-1;voidlist_delete（seqlist*L，inti）{intj;if(L->listlen<=0)error(“下溢出”);elseif(i<1

12、

13、i>L->listlen)error(“序号错误”);else{for(j=i;j<=L->listlen-1;j++)L->data[j-1]=L->data[j];L->listlen--;}}删除算法的时间分析：在i=1，2，…，n时，元素移动的次数分别为n-1，n-2，…,0。平均移动次数：(0+1+…+(n-1))/n=(n

14、-1)/2三、顺序表的应