资源描述：
《数据结构C语言版第二章课件严蔚敏.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第2章线性表2.1线性表的概念及运算2.2线性表的顺序存储2.3线性表的链式存储2.4一元多项式的表示及相加2.1线性表的概念及运算4.线性表的逻辑结构1.线性表的定义一个线性表是具有n个数据元素的有限序列。记为(a1,…,ai-1,ai,ai+1,…,an)2.线性表的长度线性表中元素的个数n(n>=0),n=0时,称为空表。3.位序ai是第i个元素，称i为数据元素ai在线性表中的位序。例子：英文字母表(A,B,…,Z)；车辆登记表。5.线性表的特点同一性：线性表由同类数据元素组成，每一个ai必须属于同一数据对象。有穷性：线性表由有限个数据元素组成，表长度就是表
2、中数据元素的个数。有序性：线性表中相邻数据元素之间存在着序偶关系。6.线性表的基本运算初始化InitList（&L）建立一个空表。求表长ListLength（L）返回线性表的长度。读表元素GetElem（L,i,&e)用e返回L中第i个数据元素的值。定位LocateElem（L,e,compare()）返回满足关系的数据元素的位序。插入ListInsert（&L,i,e）在L中第i个位置之前插入新的数据元素e，线性表的长度增1。删除ListDelete（&L,i,&e）删除L的第i个位置上的数据元素e，线性表的长度减1。输出ListDisplay（L）按前
3、后次序输出线性表的所有元素。练习1：两个线性表LA和LB分别表示两个集合A和B，现求一个新的集合A=A∪B。voidunion(List&La,ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);if(!LocateElem(La,e,equal))ListInsert(La,++La_len,e);}}O(ListLength(La)×ListLength(Lb))练习2： 两个线性表LA和LB中的数据元素按值非递减有序排列，现将LA和LB归并为
4、一个新的线性表，LC中的数据元素仍按值非递减有序排列。LA=(3,5,8,11) LB=(2,6,8,9,11,15,20) LC=(2,3,5,6,8,8,9,11,11,15,20)voidMergeList(ListLa,ListLb,List&Lc){InitList(Lc);La_len=ListLength(La);Lb_len=ListLength(Lb);i=j=1;k=0;while((i<=La_len)&&(j<=Lb_len)){GetElem(La,i,a);GetElem(Lb,j,b);if(a<=b){ListInsert(Lc,++k,a);
5、++i;}else{ListInsert(Lc,++k,b);++j;}}while(i<=La_len){GetElem(La,i++,a);ListInsert(Lc,++k,a);}while(j<=Lb_len){GetElem(Lb,j++,b);ListInsert(Lc,++k,b);}}O(ListLength(La)+ListLength(Lb))例，La=(3,5,8)Lb=(2,6,8,9,15)构造Lc=(2,3,5,6,8,8,9,15)358La268Lb915Lcij2首先，La_len=3；Lb_len=5；3ijij5ij6ij88jij9j
6、15j算法结束！2.2线性表的顺序表示和实现顺序表：按顺序存储方式构造的线性表。假设线性表中有n个元素，每个元素占k个单元，第一个元素的地址为loc(a1)，则可以通过如下公式计算出第i个元素的地址loc(ai)：loc(ai)=loc(a1)+(i-1)×k其中loc(a1)称为基地址。2.顺序表的特点：逻辑结构中相邻的数据元素在存储结构中仍然相邻。线性表的顺序存储结构是一种随机存取的存储结构。3.顺序表的描述：typedefstruct{ElemType*elem；intlength;//当前长度intlistsize;//分配的存储容量}SqList
7、；//ElemTypeelem[MAXSIZE];typedef#ElemType;#为根据具体问题确定的数据类型typedefintStatus;4.顺序表上基本运算的实现初始化StatusInitList_Sq(SqList&L){L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;returnOK;}L.ele
