欢迎来到天天文库
浏览记录
ID:45724343
大小:443.00 KB
页数:25页
时间:2019-11-17
《第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;i7、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<18、9、i>L->listlen+1)error(“序号错误”);else{for(j=L->lis10、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<112、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=(n14、-1)/2三、顺序表的应
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三、顺序表的应
此文档下载收益归作者所有