第2章+线性表_1_顺序表

第2章+线性表_1_顺序表

ID:45724343

大小:443.00 KB

页数:25页

时间:2019-11-17

第2章+线性表_1_顺序表_第1页
第2章+线性表_1_顺序表_第2页
第2章+线性表_1_顺序表_第3页
第2章+线性表_1_顺序表_第4页
第2章+线性表_1_顺序表_第5页
资源描述:

《第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三、顺序表的应

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。