文档详情

数据结构讲解讲解.ppt

发布:2017-04-18约5.88千字共71页下载文档
文本预览下载声明
第二章 线性表;2.1 线性表的类型定义;2.1 线性表的类型定义;2.1 线性表的类型定义;2.1 线性表的类型定义;2.1 线性表的类型定义;2.1 线性表的类型定义;2.1 线性表的类型定义;例:假设利用两个线性表LA和LB分别表示两个集合A和B,要求一个新的集合A=A∪B。 void union(List la,List lb) {//将所有在线性表lb中但不在la中的数据元素插入到la中 la_len=ListLength(la); lb_len=ListLength(lb);//求线性表的长度 for(i=1;i=lb_len;i++) { GetElem(lb,i,e);//取lb中第i个数据元素赋给e if(!(LocateElem(La,e,equal)) ListInsert(la,++la_len,e); //la中不存在和e相同的数据元素,则插入之 } } 时间复杂度O(la.length×lb.length);例:已知线性表LA和LB中的数据元素按值非递减有序排列,要求将LA和LB归并为一个新的线性表LC,且LC中的数据元素仍按值非递减有序排列。 void MergeList(List la,List lb,List lc) { //已知线性表la和lb中的数据元素按值非递减排列。 //归并la和lb得到新的线性表lc,lc的数据元素也按值非递减排列。 InitList(lc); i=j=1;k=0; la_len=ListLength(la); lb_len=ListLength(lb);//求线性表的长度 while((i=la_len)(j=lb_len))//la和lb均非空 { GetElem(la,i,ai); GetElem(lb,j,bj); if(ai=bj){ ListInsert(lc,++k,ai);++i;} else{ ListInsert(lc,++k,bj);++j;} } while(i=la_len){GetElem(la,i++,ai); ListInsert(lc,++k,ai);} while(j=lb_len){GetElem(lb,j++,bj); ListInsert(lc,++k,bj);} } 时间复杂度O(la.length+lb.length) ;2.2 线性表的顺序表示和实现;2.2 线性表的顺序表示和实现;2.2 线性表的顺序表示和实现;2.2 线性表的顺序表示和实现;2.2 线性表的顺序表示和实现;2.2 线性表的顺序表示和实现;2.2 线性表的顺序表示和实现;2.2 线性表的顺序表示和实现;2.2 线性表的顺序表示和实现;2.2 线性表的顺序表示和实现;2.2 线性表的顺序表示和实现;考虑移动元素的平均情况:;2.2 线性表的顺序表示和实现;考虑移动元素的平均情况:;2.2 线性表的顺序表示和实现;2.2 线性表的顺序表示和实现;2.2 线性表的顺序表示和实现;2.2 线性表的顺序表示和实现;2.2 线性表的顺序表示和实现;void MergeList_Sq(SqList la, SqList lb, SqList lc) { pa=la.elem;pb=lb.elem;lc.listsize=lc.length=la.length+lb.length; pc=lc.elem=(ElemType *)malloc(lc.listsize*sizeof(ElemType)); if(!lc.elem) exit(OVERFLOW); pa_last=la.elem+la.length-1; pb_last=lb.elem+lb.length-1; while(pa=pa_last pb=pb_last) { if(*pa=*pb) *pc++=*pa++; else *pc++=*pb++; } while(pa=pa_last) *pc++=*pa++; while(pb=pb_last) *pc++=*pb++; } 时间复杂度:O(la.length+lb.length);2.2 线性表的顺序表示和实现;2.3 线性表的链式表示和实现;一、单链表的定义 为了表示每个数据元素ai与其后继元素ai+1之间的逻辑关系,对数据元素ai来说,除了需要存储它本身的信息外,还需要存储它的直接后继元素的地址。这两部分信息组成了数据元素ai在内存中的存储映象(存储状态),称为结点。 每个结点都有两个域构成:一个是存
显示全部
相似文档