数据结构讲解讲解.ppt
文本预览下载声明
第二章 线性表;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在内存中的存储映象(存储状态),称为结点。
每个结点都有两个域构成:一个是存
显示全部