首页 / 软件开发 / 数据结构与算法 / 数据结构教程 第六课 线性表的顺序表示和实现

数据结构教程 第六课 线性表的顺序表示和实现2007-05-17本课主题： 线性表的顺序表示和实现

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

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

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

授课内容：

复习

1、存储结构

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

2、线性表的类型定义

一、线性表的顺序表示

用一组地址连续的存储单元依次存储线性表的数据元素。C语言中的数组即采用顺序存储方式。

2000:0001 2000:0003 2000:0005 2000:0007 2000:0009 2000:0011 2000:0013 2000:0015 2000:0017 ... 2000:1001 2000:1003

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1

a[9]

1 2 3 4 5 6 7 8 9

假设线性表的每个元素需占用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语言实现：

顺序表的插入与删除操作：

序号	数据元素		序号	数据元素		序号	数据元素		序号	数据元素
1 2 3 4 5 6 7 8 9	12 13 21 24 28 30 42 77	<-25	1 2 3 4 5 6 7 8 9	12 13 21 24 25 28 30 42 77		1 2 3 4 5 6 7 8 9	12 13 21 24 28 30 42 77	->24	1 2 3 4 5 6 7 8 9	12 13 21 28 30 42 77
插入前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语言源程序范例

四、总结

线性表的顺序表示

顺序表的插入算法顺序表的合并算法