敬业的IT人 >> 编程开发 >> 数据结构&算法分析 >> 数据结构教程第六课线性表的顺序表示和实现

数据结构教程第六课线性表的顺序表示和实现

敬业的IT人互联网佚名 2008-1-4 15:29:35

本课主题： 线性表的顺序表示和实现

教学目的： 掌握线性表的顺序表示和实现方法

教学重点： 线性表的顺序表示和实现方法

教学难点： 线性表的顺序存储的实现方法

授课内容：

复习

1、存储结构
逻辑结构 “数据结构”定义中的“关系”指数据间的逻辑关系，故也称数据结构为逻辑结构。存储结构数据结构在计算机中的表示称为物理结构。又称存储结构。顺序存储结构链式存储结构
2、线性表的类型定义

一、线性表的顺序表示

用一组地址连续的存储单元依次存储线性表的数据元素。C语言中的数组即采用顺序存储方式。
2000:00012000:00032000:00052000:00072000:00092000:00112000:00132000:00152000:0017...2000:10012000:1003000000000000000100000000000000100000000000000011000000000000010000000000000001010000000000000110000000000000011100000000000010000000000000001001 a[9]123456789
假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则存在如下关系：
LOC(ai 1)=LOC(ai) l
LOC(ai)=LOC(a1) (i-1)*l
式中LOC(a1)是线性表的第一个数据元素的存储位置，通常称做线性表的起始位置或基地址。常用b表示。
线性表的这种机内表示称做线性表的顺序存储结构或顺序映象。
称顺序存储结构的线性表为顺序表。顺序表的特点是以元素在计算机内物理位置相邻来表示线性表中数据元素之间的逻辑关系。

二、顺序存储结构的线性表类C语言表示：

线性表的动态分配顺序存储结构
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10

typedef struct{
ElemType *elem; //存储空间基址
int length; //当前长度
int listsize; //当前分配的存储容量以一数据元素存储长度为单位
}SqList;

三、顺序存储结构的线性表操作及C语言实现：

顺序表的插入与删除操作：
序号数据元素序号数据元素序号数据元素序号数据元素123456789 1213212428304277

<-25

123456789 121321242528304277 123456789 1213212428304277

->24
123456789 12132128304277 插入前n=8;插入后n=9; 删除前n=8;删除后n=7;
顺序表的插入算法
status ListInsert(List *L,int i,ElemType e) {
struct STU *p,*q;
if (i<1||i>L->length 1) return ERROR;
q=&(L->elem[i-1]);
for(p=&L->elem[L->length-1];p>=q;--p)
*(p 1)=*p;
*q=e;
L->length;
return OK;
}/*ListInsert Before i */
顺序表的合并算法
void MergeList(List *La,List *Lb,List *Lc) {
ElemType *pa,*pb,*pc,*pa_last,*pb_last;
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(Less_EqualList(pa,pb)) *pC =*pa ;
else *pC =*pb ;
}
while(pa<=pa_last) *pC =*pa ;
while(pb<=pb_last) *pC =*pb ;
}
顺序表的查找算法
int LocateElem(List *La,ElemType e,int type) {
int i;
switch (type) {
case EQUAL:
for(i=0;i<length;i )
if(EqualList(&La->elem[i],&e))
return 1;
break;
default:
break;
}
return 0;
}
顺序表的联合算法
void UnionList(List *La, List *Lb) {
int La_len,Lb_len; int i; ElemType e;
La_len=ListLength(La); Lb_len=ListLength(Lb);
for(i=0;i<Lb_len;i ) {
GetElem(*Lb,i,&e);
if(!LocateElem(La,e,EQUAL))
ListInsert(La, La_len,e);
}
}

三、C语言源程序范例

四、总结

线性表的顺序表示
顺序表的插入算法
顺序表的合并算法

最新文章: 数据结构教程第八课线性表的链式表示与实现[01-04]; 数据结构教程第七课实验一线性表的顺序存储实验[01-04]; 数据结构教程第九课循环链表与双向链表[01-04]; 数据结构教程第十课栈的表示与实现[01-04]; 数据结构教程第十一课栈的应用[01-04]; 数据结构教程第十三课队列[01-04]

相关文章