线性表及顺序存储.ppt

《线性表及顺序存储.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2.线性表上的运算置一个空表建一个线性表求表长查找某个元素插入一个元素删除一个元素拆分线性表合并排序…案例中顺序表的存储结构的C语言描述如下：#defineMAXSIZE100typedefintElementType;typedefstruct{ElementTypeData[MAXSIZE];intlast;}List;算法在表尾插入元素即在数组的Last位置插入元素，表长增1。算法实现：voidappend(List*lp,ElementTypex){if(lp->Last==MAXSIZE){printf(

2、"顺序表是满的!");exit(1);}lp->Data[lp->Last]=x;lp->Last++;}共Last个元素01……Last-1Last……x函数形参：指定顺序表的地址，插入元素x返回值：无算法判顺序表是否为空表判断表长是否为0。算法实现：intempty(List*lp){returnlp->Last==0;}函数形参：指定顺序表地址返回值：1表示空,0表示非空i的有效范围01……size-1……算法取得顺序表中序号为i的元素值ElementTypeget(List*lp,inti){if(i<0

3、

4、

5、i>=lp->Last)/*查找位置不正确*/{printf("指定位置的结点不存在!");exit(1);}elsereturnlp->Data[i];}函数形参：指定顺序表的地址，取元素值的序号返回值：序号为i的元素值（1）voidreverse(List*L)将顺序表L就地倒置，即借助于O（1）的辅助空间。（2）voidsplit(List*L1,List*L2,List*L3)将有序顺序表L1分裂成两个线性表L2与L3，L2由表中所奇数组成，L3由所有偶数组成。顺序表上的一些其它常见算法（3）void

6、merge(List*L1,List*L2,List*L3)将有序顺序表L1与L2合并成有序顺序表L3。优点：(1)逻辑结构上相邻的数据元素，其物理位置也是相邻的。(2)可方便地进行随机存取任一元素——O(1)。缺点：(1)插入和删除平均须移动一半元素——O(n)，效率低。(2)存储分配只能预先进行（静态），不易扩充。过大浪费过小溢出顺序表的优、缺点：应用举例设元素类型：typedefstruct{intnum;/*学号*/charname[20];/*姓名*/intscore;/*成绩*/}ElementTy

7、pe;要求：合并两个升序(依成绩)顺序表为一个升序的顺序表voidmerge(List*la,List*lb,List*lc){inti,j,k;i=j=k=0;while(iLast&&jLast)/*la和lb表都未取完元素*/if(la->Data[i].score<=lb->Data[j].score)lc->Data[k++]=la->Data[i++];elselc->Data[k++]=lb->Data[j++];while(iLast)/*la表未取完元素*/lc->D

8、ata[k++]=la->Data[i++];while(jLast)/*lb表未取完元素*/lc->Data[k++]=lb->Data[j++];lc->Last=la->Last+lb->Last;}应用举例：合并两个升序(依成绩)顺序表为一个升序的顺序表第3章线性结构1/17§3.1引子【分析】多项式的关键数据是：多项式项数n、每一项的系数ai（及相应指数i）。有3种不同的方法。一元多项式：主要运算：多项式相加、相减、相乘等方法1：采用顺序存储结构直接表示[例3.1]一元多项式及其运算。例如下标

9、i012345……a[i]10–3004……表示成方法2：采用顺序存储结构表示多项式的非零项。第3章线性结构§3.1引子每个非零项涉及两个信息：指数和系数，可以将一个多项式看成是一个(，)二元组的集合。例如：和数组下标i012……数组下标i0123……系数9153–系数26–4–1382–指数1282–指数19860–P1(x)(b)P2(x)2/17相加过程：最后得到的结果多项式是：((26,19),(9,12),(11,8),(–13,6),(3,2),(82,0))数组下标i0123456系数指数作业：P9

10、6:3.3给定一个顺序存储的线性表L，请设计一个算法删除所有值大于min而且小于max的元素。voiddelemm(List*lp,intmin,intmax);