线性表的顺序和实现:线性表的顺序表示和实现

本课主题:线性表顺序表示和实现
教学目:掌握线性表顺序表示和实现思路方法
教学重点:线性表顺序表示和实现思路方法
教学难点:线性表顺序存储实现思路方法
授课内容:
复习
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表示
线性表这种机内表示称做线性表顺序存储结构或顺序映象
称顺序存储结构线性表为顺序表顺序表特点是以元素在计算机内物理位置相邻来表示线性表中数据元素的间逻辑关系
2、顺序存储结构线性表类C语言表示:
线性表动态分配顺序存储结构
#LIST_INIT_SIZE100
#LISTINCREMENT10

typedefstruct{
ElemType*elem;//存储空间基址
length;//当前长度
listsize;//当前分配存储容量以数据元素存储长度为单位
}SqList;
3、顺序存储结构线性表操作及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;


顺序表插入算法
statusListInsert(List*L,i,ElemTypee){
structSTU*p,*q;
(i<1||i>L->length+1)ERROR;
q=&(L->elem[i-1]);
for(p=&L->elem[L->length-1];p>=q;--p)
*(p+1)=*p;
*q=e;
L->length;
OK;
}/*ListInsertBeforei*/
顺序表合并算法
voidMergeList(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*(ElemType));
(!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){
(Less_EqualList(pa,pb))*pc+*pa;
*pc+*pb;
}
while(pa<=pa_last)*pc+*pa;
while(pb<=pb_last)*pc+*pb;
}
顺序表查找算法
LocateElem(List*La,ElemTypee,type){
i;
switch(type){
EQUAL:


for(i=0;i<length;i)
(EqualList(&La->elem[i],&e))
1;
;
default:
;
}
0;
}
顺序表联合算法
voidUnionList(List*La,List*Lb){
La_len,Lb_len;i;ElemTypee;
La_len=ListLength(La);Lb_len=ListLength(Lb);
for(i=0;i<Lb_len;i){
GetElem(*Lb,i,&e);
(!LocateElem(La,e,EQUAL))
ListInsert(La,La_len,e);
}
}
3、C语言源范例
4、整理总结
线性表顺序表示
顺序表插入算法
顺序表合并算法

延伸阅读

• 2010-11-24-- 单链表实现线性表,C#版数据结构之--线性表的链式存储（单链表）
• 2010-12-16-- c语言实现线性表,线性表的顺序实现(C++)
• 2008-11-27-- 数据结构线性表:数据结构——模拟线性表
• 2008-12-10-- 线性表的顺序存储:数据结构教程 第七课 实验一 线性表的顺序存储实验