资源描述：
《数据结构C语言版第二章课件严蔚敏资料讲解.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构C语言版第二章课件严蔚敏例子：英文字母表(A,B,…,Z)；车辆登记表。5.线性表的特点同一性：线性表由同类数据元素组成，每一个ai必须属于同一数据对象。有穷性：线性表由有限个数据元素组成，表长度就是表中数据元素的个数。有序性：线性表中相邻数据元素之间存在着序偶关系。6.线性表的基本运算初始化InitList（&L）建立一个空表。求表长ListLength（L）返回线性表的长度。读表元素GetElem（L,i,&e)用e返回L中第i个数据元素的值。定位LocateElem（L,e,compa
2、re()）返回满足关系的数据元素的位序。插入ListInsert（&L,i,e）在L中第i个位置之前插入新的数据元素e，线性表的长度增1。删除ListDelete（&L,i,&e）删除L的第i个位置上的数据元素e，线性表的长度减1。输出ListDisplay（L）按前后次序输出线性表的所有元素。练习1：两个线性表LA和LB分别表示两个集合A和B，现求一个新的集合A=A∪B。voidunion(List&La,ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=
3、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归并为一个新的线性表，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)voidMergeL
4、ist(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);++i;}else{ListInsert(Lc,++k,b);++j;}}while(i<=La_len){GetElem(La,i++,a);List
5、Insert(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；3ijij5ij6ij88jij9j15j算法结束！2.2线性表的顺序表示和实现顺序表：按顺序存储方式构造的线性表。假设线性表中有n个
6、元素，每个元素占k个单元，第一个元素的地址为loc(a1)，则可以通过如下公式计算出第i个元素的地址loc(ai)：loc(ai)=loc(a1)+(i-1)×k其中loc(a1)称为基地址。2.顺序表的特点：逻辑结构中相邻的数据元素在存储结构中仍然相邻。线性表的顺序存储结构是一种随机存取的存储结构。3.顺序表的描述：typedefstruct{ElemType*elem；intlength;//当前长度intlistsize;//分配的存储容量}SqList；//ElemTypeelem[MAXSIZ
7、E];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.elem=newElemType[LIST_INIT_SIZE];顺序
8、表的插入：在表中第4个元素之前插入“21”。顺序表中插入元素插入StatusListInsert_Sq(SqList&L,inti,ElemTypee){if((i<1)
9、
10、(i>L.length+1))returnERROR;if(L.length>=L.listsize){realloc(…);….
