本课主题: 线性
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
的顺序表示和实现
教学目的: 掌握线性表的顺序表示和实现方法
教学重点: 线性表的顺序表示和实现方法
教学难点: 线性表的顺序存储的实现方法
授课内容:
复习
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
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
本文档为【数据结构教程_第六课_线性表的顺序表示和实现】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。