Teenits 2008-5-14 20:01
数据结构教程 第六课 线性表的顺序表示和实现
[size=5]
本课主题： 线性表的顺序表示和实现
教学目的： 掌握线性表的顺序表示和实现方法
教学重点： 线性表的顺序表示和实现方法
教学难点： 线性表的顺序存储的实现方法
授课内容：
复习
1、存储结构
逻辑结构 “数据结构”定义中的“关系”指数据间的逻辑关系，故也称数据结构为逻辑结构。
存储结构 数据结构在计算机中的表示称为物理结构。又称存储结构。
顺序存储结构
链式存储结构
2、线性表的类型定义
[/size][size=5]一、线性表的顺序表示[/size]
[indent][size=5]用一组地址连续的存储单元依次存储线性表的数据元素。C语言中的数组即采用顺序存储方式。[/size]
[table=473] [tr] [td=1,1,90] [table=87] [tr] [td][size=5]2000:0001[/size][/td] [/tr] [tr] [td][size=5]2000:0003[/size][/td] [/tr] [tr] [td][size=5]2000:0005[/size][/td] [/tr] [tr] [td][size=5]2000:0007[/size][/td] [/tr] [tr] [td][size=5]2000:0009[/size][/td] [/tr] [tr] [td][size=5]2000:0011[/size][/td] [/tr] [tr] [td][size=5]2000:0013[/size][/td] [/tr] [tr] [td][size=5]2000:0015[/size][/td] [/tr] [tr] [td][size=5]2000:0017[/size][/td] [/tr] [tr] [td][size=5]...[/size][/td] [/tr] [tr] [td][size=5]2000:1001[/size][/td] [/tr] [tr] [td][size=5]2000:1003[/size][/td] [/tr] [/table] [/td] [td] [table=275] [tr] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]1[/size][/td] [/tr] [tr] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]1[/size][/td] [td][size=5]0[/size][/td] [/tr] [tr] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]1[/size][/td] [td][size=5]1[/size][/td] [/tr] [tr] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]1[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [/tr] [tr] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]1[/size][/td] [td][size=5]0[/size][/td] [td][size=5]1[/size][/td] [/tr] [tr] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]1[/size][/td] [td][size=5]1[/size][/td] [td][size=5]0[/size][/td] [/tr] [tr] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]1[/size][/td] [td][size=5]1[/size][/td] [td][size=5]1[/size][/td] [/tr] [tr] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]1[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [/tr] [tr] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]1[/size][/td] [td][size=5]0[/size][/td] [td][size=5]0[/size][/td] [td][size=5]1[/size][/td] [/tr] [tr] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [/tr] [tr] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [/tr] [tr] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [td][size=5] [/size][/td] [/tr] [/table] [/td] [td=1,1,47][size=5]a[9][/size][/td] [td] [table=45] [tr=#ffcccc] [td][size=5]1[/size][/td] [/tr] [tr=#ffcccc] [td][size=5]2[/size][/td] [/tr] [tr=#ffcccc] [td][size=5]3[/size][/td] [/tr] [tr=#ffcccc] [td][size=5]4[/size][/td] [/tr] [tr=#ffcccc] [td][size=5]5[/size][/td] [/tr] [tr=#ffcccc] [td][size=5]6[/size][/td] [/tr] [tr=#ffcccc] [td][size=5]7[/size][/td] [/tr] [tr=#ffcccc] [td][size=5]8[/size][/td] [/tr] [tr=#ffcccc] [td][size=5]9[/size][/td] [/tr] [tr] [td][size=5] [/size][/td] [/tr] [tr] [td][size=5] [/size][/td] [/tr] [tr] [td][size=5] [/size][/td] [/tr] [/table] [/td] [/tr] [/table][size=5]假设线性表的每个元素需占用[i]l[/i]个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则存在如下关系：[/size]
[indent][align=center][size=5]LOC(ai+1)=LOC(ai)+[i]l[/i][/size][/align][align=center][size=5]LOC(ai)=LOC(a1)+([i]i[/i]-1)*[i]l[/i][/size][/align][/indent][size=5]式中LOC(a1)是线性表的第一个数据元素的存储位置，通常称做线性表的起始位置或基地址。常用[i]b[/i]表示。[/size]
[size=5]线性表的这种机内表示称做线性表的顺序存储结构或顺序映象。[/size]
[size=5]称顺序存储结构的线性表为顺序表。顺序表的特点是以元素在计算机内物理位置相邻来表示线性表中数据元素之间的逻辑关系。[/size]
[/indent][size=5]二、顺序存储结构的线性表类C语言表示：[/size]
[indent][table=557] [tr] [td][size=5]线性表的动态分配顺序存储结构[/size][/td] [/tr] [tr] [td] [size=5]#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef struct{[/size]
[size=5]ElemType *elem; //存储空间基址[/size]
[size=5]int length; //当前长度[/size]
[size=5]int listsize; //当前分配的存储容量以一数据元素存储长度为单位[/size]
[size=5]}SqList; [/size]
[/td] [/tr] [/table][/indent][size=5]三、顺序存储结构的线性表操作及C语言实现：[/size]
[indent][size=5]顺序表的插入与删除操作：[/size]
[table=523] [tr] [td=1,1,33][size=5]序号[/size][/td] [td=2,1][size=5]数据元素[/size][/td] [td=1,1,33][size=5]序号[/size][/td] [td][size=5]数据元素[/size][/td] [td=1,1,62][size=5] [/size][/td] [td][size=5]序号[/size][/td] [td=2,1][size=5]数据元素[/size][/td] [td=1,1,34][size=5]序号[/size][/td] [td][size=5]数据元素[/size][/td] [/tr] [tr] [td=1,1,33] [table=33] [tr] [td][size=5]1[/size][/td] [/tr] [tr] [td][size=5]2[/size][/td] [/tr] [tr] [td][size=5]3[/size][/td] [/tr] [tr] [td][size=5]4[/size][/td] [/tr] [tr] [td][size=5]5[/size][/td] [/tr] [tr] [td][size=5]6[/size][/td] [/tr] [tr] [td][size=5]7[/size][/td] [/tr] [tr] [td][size=5]8[/size][/td] [/tr] [tr] [td][size=5]9[/size][/td] [/tr] [tr] [td][size=5] [/size][/td] [/tr] [tr] [td][size=5] [/size][/td] [/tr] [tr] [td][size=5] [/size][/td] [/tr] [/table] [/td] [td] [table=33] [tr] [td][size=5]12[/size][/td] [/tr] [tr] [td][size=5]13[/size][/td] [/tr] [tr] [td][size=5]21[/size][/td] [/tr] [tr] [td][size=5]24[/size][/td] [/tr] [tr] [td][size=5]28[/size][/td] [/tr] [tr] [td][size=5]30[/size][/td] [/tr] [tr] [td][size=5]42[/size][/td] [/tr] [tr] [td][size=5]77[/size][/td] [/tr] [tr] [td][size=5] [/size][/td] [/tr] [tr] [td][size=5] [/size][/td] [/tr] [tr] [td][size=5] [/size][/td] [/tr] [tr] [td][size=5] [/size][/td] [/tr] [/table] [/td] [td=1,1,40] [size=5]
<-25 [/size]
[/td] [td] [table=33] [tr=#ffffff] [td][size=5]1[/size][/td] [/tr] [tr=#ffffff] [td][size=5]2[/size][/td] [/tr] [tr=#ffffff] [td][size=5]3[/size][/td] [/tr] [tr=#ffffff] [td][size=5]4[/size][/td] [/tr] [tr=#ffffff] [td][size=5]5[/size][/td] [/tr] [tr=#ffffff] [td][size=5]6[/size][/td] [/tr] [tr=#ffffff] [td][size=5]7[/size][/td] [/tr] [tr=#ffffff] [td][size=5]8[/size][/td] [/tr] [tr=#ffffff] [td][size=5]9[/size][/td] [/tr] [tr] [td][size=5] [/size][/td] [/tr] [tr] [td][size=5] [/size][/td] [/tr] [tr] [td][size=5] [/size][/td] [/tr] [/table] [/td] [td=1,1,64] [table=33] [tr] [td][size=5]12[/size][/td] [/tr] [tr] [td][size=5]13[/size][/td] [/tr] [tr] [td][size=5]21[/size][/td] [/tr] [tr] [td][size=5]24[/size][/td] [/tr] [tr] [td][size=5]25[/size][/td] [/tr] [tr=#ccccff] [td][size=5]28[/size][/td] [/tr] [tr=#ccccff] [td][size=5]30[/size][/td] [/tr] [tr=#ccccff] [td][size=5]42[/size][/td] [/tr] [tr=#ccccff] [td][size=5]77[/size][/td] [/tr] [tr] [td][size=5] [/size][/td] [/tr] [tr] [td][size=5] [/size][/td] [/tr] [tr] [td][size=5] [/size][/td] [/tr] [/table] [/td] [td][size=5] [/size][/td] [td=1,1,33] [table=33] [tr] [td][size=5]1[/size][/td] [/tr] [tr] [td][size=5]2[/size][/td] [/tr] [tr] [td][size=5]3[/size][/td] [/tr] [tr] [td][size=5]4[/size][/td] [/tr] [tr] [td][size=5]5[/size][/td] [/tr] [tr] [td][size=5]6[/size][/td] [/tr] [tr] [td][size=5]7[/size][/td] [/tr] [tr] [td][size=5]8[/size][/td] [/tr] [tr] [td][size=5]9[/size][/td] [/tr] [tr] [td][size=5] [/size][/td] [/tr] [tr] [td][size=5] [/size][/td] [/tr] [tr] [td][size=5] [/size][/td] [/tr] [/table] [/td] [td] [table=40] [tr] [td][size=5]12[/size][/td] [/tr] [tr] [td][size=5]13[/size][/td] [/tr] [tr] [td][size=5]21[/size][/td] [/tr] [tr] [td][size=5]24[/size][/td] [/tr] [tr] [td][size=5]28[/size][/td] [/tr] [tr] [td][size=5]30[/size][/td] [/tr] [tr] [td][size=5]42[/size][/td] [/tr] [tr] [td][size=5]77[/size][/td] [/tr] [tr] [td][size=5] [/size][/td] [/tr] [tr] [td][size=5] [/size][/td] [/tr] [tr] [td][size=5] [/size][/td] [/tr] [tr] [td][size=5] [/size][/td] [/tr] [/table] [/td] [td=1,1,33] [size=5]->24[/size]
[/td] [td] [table=33] [tr] [td][size=5]1[/size][/td] [/tr] [tr] [td][size=5]2[/size][/td] [/tr] [tr] [td][size=5]3[/size][/td] [/tr] [tr] [td][size=5]4[/size][/td] [/tr] [tr] [td][size=5]5[/size][/td] [/tr] [tr] [td][size=5]6[/size][/td] [/tr] [tr] [td][size=5]7[/size][/td] [/tr] [tr] [td][size=5]8[/size][/td] [/tr] [tr] [td][size=5]9[/size][/td] [/tr] [tr] [td][size=5] [/size][/td] [/tr] [tr] [td][size=5] [/size][/td] [/tr] [tr] [td][size=5] [/size][/td] [/tr] [/table] [/td] [td=1,1,87] [table=33] [tr] [td][size=5]12[/size][/td] [/tr] [tr] [td][size=5]13[/size][/td] [/tr] [tr] [td][size=5]21[/size][/td] [/tr] [tr] [td][size=5]28[/size][/td] [/tr] [tr] [td][size=5]30[/size][/td] [/tr] [tr] [td][size=5]42[/size][/td] [/tr] [tr] [td][size=5]77[/size][/td] [/tr] [tr] [td][size=5] [/size][/td] [/tr] [tr] [td][size=5] [/size][/td] [/tr] [tr] [td][size=5] [/size][/td] [/tr] [tr] [td][size=5] [/size][/td] [/tr] [tr] [td][size=5] [/size][/td] [/tr] [/table] [/td] [/tr] [tr] [td=5,1][size=5]插入前n=8;插入后n=9;[/size][/td] [td=1,1,62][size=5] [/size][/td] [td=5,1][size=5]删除前n=8;删除后n=7;[/size][/td] [/tr] [/table][size=5]
[/size][table=537] [tr] [td][size=5]顺序表的插入算法[/size][/td] [/tr] [tr] [td] [size=5]status ListInsert(List *L,int i,ElemType e) {[/size]
[size=5]struct STU *p,*q; [/size]
[size=5]if (i<1||i>L->length+1) return ERROR; [/size]
[size=5]q=&(L->elem[i-1]); [/size]
[size=5]for(p=&L->elem[L->length-1];p>=q;--p) [/size]
[indent] [size=5]*(p+1)=*p; [/size]
[/indent] [size=5]*q=e; [/size]
[size=5]++L->length; [/size]
[size=5]return OK; [/size]
[size=5]}/*ListInsert Before i */ [/size]
[/td] [/tr] [tr] [td][size=5]顺序表的合并算法[/size][/td] [/tr] [tr] [td] [size=5]void MergeList(List *La,List *Lb,List *Lc) {[/size]
[size=5]ElemType *pa,*pb,*pc,*pa_last,*pb_last; [/size]
[size=5]pa=La->elem;pb=Lb->elem; [/size]
[size=5]Lc->listsize = Lc->length = La->length + Lb->length; [/size]
[size=5]pc = Lc->elem = [/size]
[indent] [size=5](ElemType *)malloc(Lc->listsize * sizeof(ElemType)); [/size]
[/indent] [size=5]if(!Lc->elem) exit(OVERFLOW); [/size]
[size=5]pa_last = La->elem + La->length - 1; [/size]
[size=5]pb_last = Lb->elem + Lb->length - 1; [/size]
[size=5]while(pa<=pa_last && pb<=pb_last) { [/size]
[indent] [size=5]if(Less_EqualList(pa,pb)) *pc++=*pa++; [/size]
[size=5]else *pc++=*pb++; [/size]
[/indent] [size=5]} [/size]
[size=5]while(pa<=pa_last) *pc++=*pa++; [/size]
[size=5]while(pb<=pb_last) *pc++=*pb++; [/size]
[size=5]}[/size]
[/td] [/tr] [tr] [td][size=5]顺序表的查找算法[/size][/td] [/tr] [tr] [td] [size=5]int LocateElem(List *La,ElemType e,int type) { [/size]
[size=5]int i; [/size]
[size=5]switch (type) { [/size]
[indent] [size=5]case EQUAL: [/size]
[indent] [size=5]for(i=0;i<length;i++) [/size]
[size=5]if(EqualList(&La->elem[i],&e)) [/size]
[indent] [size=5]return 1; [/size]
[/indent] [size=5]break; [/size]
[/indent] [size=5]default: [/size]
[indent] [size=5]break; [/size]
[/indent] [size=5]} [/size]
[/indent] [size=5]return 0; [/size]
[size=5]}[/size]
[/td] [/tr] [tr] [td][size=5]顺序表的联合算法[/size][/td] [/tr] [tr] [td] [size=5]void UnionList(List *La, List *Lb) {[/size]
[size=5]int La_len,Lb_len; int i; ElemType e; [/size]
[size=5]La_len=ListLength(La); Lb_len=ListLength(Lb); [/size]
[size=5]for(i=0;i<Lb_len;i++) { [/size]
[indent] [size=5]GetElem(*Lb,i,&e); [/size]
[size=5]if(!LocateElem(La,e,EQUAL))[/size]
[indent] [size=5]ListInsert(La,++La_len,e); [/size]
[/indent] [size=5]}[/size]
[/indent] [size=5]}[/size]
[/td] [/tr] [/table][/indent][size=5]三、C语言源程序范例[/size]
[size=5]四、总结[/size]
[indent][size=5]线性表的顺序表示[/size]
[size=5]顺序表的插入算法[/size][size=5]顺序表的合并算法[/size]
[/indent][size=5]
[/size]