清华大学出版社 TSINGHUA UNIVERSITY PRESS 第2章线性表及其顺序存储结构 2.1线性表的基本概念 2.2栈及其应用 2.3队列及其应用 2.4字符串
第2章 线性表及其顺序存储结构 2.1 线性表的基本概念 2.2 栈及其应用 2.3 队列及其应用 2.4 字符串
清华大学出版社 TSINGHUA UNIVERSITY PRESS 2.1线性表的基本概念 2.1.1什么是线性表 2.1.2线性表的顺序存储结构 2.1.3线性表在顺序存储下的插入运算 2.1.4线性表在顺序存储下的删除运算
2.1 线性表的基本概念 2.1.1 什么是线性表 2.1.2 线性表的顺序存储结构 2.1.3 线性表在顺序存储下的插入运算 2.1.4 线性表在顺序存储下的删除运算
清华大学出版社 TSINGHUA UNIVERSITY PRESS 2.1线性表的基本概念 2.1.1什么是线性表( Linear list) ●n维向量(x1,x2,…,xn)是一个长度为n的 线性表 ●英文小写字母表(a,b,c,…,z)是一个长 度为26的线性表 年中的四个季节(春,夏,秋,冬)是一个 长度为4的线性表 ●矩阵是一个比较复杂的线性表
2.1 线性表的基本概念 2.1.1 什么是线性表(Linear List) ● n维向量(x1，x2，…，xn)是一个长度为n的 线性表 ●英文小写字母表(a，b，c，…，z)是一个长 度为26的线性表 ●一年中的四个季节(春，夏，秋，冬)是一个 长度为4的线性表 ●矩阵是一个比较复杂的线性表
清华大学出版社 TSINGHUA UNIVERSITY PRESS 2.1线性表的基本概念 ●学生情况登记表是一个复杂的线性表 由若干数据项组成的数据元素称为记录( record 由多个记录构成的线性表又称为文件(file) 学生情况登被表 姓名 学号性别年龄 健康状况 王强 800356 刘建平 800357 赵军 800361 男男女男 良好 般 19 良好 葛文华 800367 21 较差
2.1 线性表的基本概念 ●学生情况登记表是一个复杂的线性表 由若干数据项组成的数据元素称为记录(record) 由多个记录构成的线性表又称为文件(file)
清华大学出版社 TSINGHUA UNIVERSITY PRESS 2.1线性表的基本概念 线性表是由n(n≥0)个数据元素a1,a2,…,an 组成的一个有限序列,表中的每一个数据元素 除了第一个外,有且只有一个前件,除了最后 个外,有且只有一个后件。即线性表或是 个空表,或可以表示为 a1, a2, 其中a;(i=1,2,…,n)是属于数据对象的元 素,通常也称其为线性表中的一个结点
2.1 线性表的基本概念 线性表是由n(n≥0)个数据元素a1，a2，…，an 组成的一个有限序列，表中的每一个数据元素， 除了第一个外，有且只有一个前件，除了最后 一个外，有且只有一个后件。即线性表或是一 个空表，或可以表示为 (a1，a2，…，ai，…，an) 其中ai(i＝1，2，…，n)是属于数据对象的元 素，通常也称其为线性表中的一个结点
清华大学出版社 TSINGHUA UNIVERSITY PRESS 2.1线性表的基本概念 非空线性表结构特征: (1)有且只有一个根结点a1,它无前件 (2)有且只有一个终端结点an,它无后件; (3)除根结点与终端结点外,其它所有结 点有且只有一个前件,也有且只有一个 后件。 线性表中结点的个数n称为线性表的长度。 当n=0时,称为空表
2.1 线性表的基本概念 非空线性表结构特征： (1)有且只有一个根结点a1，它无前件； (2)有且只有一个终端结点an，它无后件； (3)除根结点与终端结点外，其它所有结 点有且只有一个前件，也有且只有一个 后件。 线性表中结点的个数n称为线性表的长度。 当n＝0时，称为空表
清华大学出版社 TSINGHUA UNIVERSITY PRESS 2.1线性表的基本概念 2.1.2线性表的顺序存储结构 线性表的顺序存储结构基本特点: (1)线性表中所有元素所占的存储空间是连续的; (2)线性表中各数据元素在存储空间中是按逻辑 顺序依次存放的。 线性表中第i个元素a;在计算机存储空间 中的存储地址为 aDR(ai)=adr(ai+(i-1k
2.1 线性表的基本概念 2.1.2 线性表的顺序存储结构 线性表的顺序存储结构基本特点： (1)线性表中所有元素所占的存储空间是连续的； (2)线性表中各数据元素在存储空间中是按逻辑 顺序依次存放的。 线性表中第i个元素ai在计算机存储空间 中的存储地址为 ADR(ai)＝ADR(a1)＋(i－1)k
清华大学出版社 TSINGHUA UNIVERSITY PRESS 1线性表的基本概念 长度为n的线性表 存储地址 a1, a2, a g an) ADR (a) 占k个字节 顺序存储结构 ADR(a,+k 占k个字节 ADR(a1)+(1-1)k 占k个字节 ADR(a,)+ (n-1)k 占k个宇节
2.1 线性表的基本概念 长度为n的线性表 (a1，a2，…，ai，…，an) 顺序存储结构
清华大学出版社 TSINGHUA UNIVERSITY PRESS 2.1线性表的基本概念 v(1:12) 整型一维数组存放 18 长度为8的线性表 56 (29,18,56,63,35,24,31,47) 23456789 63 35 24 31 47 10 11 12
2.1 线性表的基本概念 整型一维数组存放 长度为8的线性表 (29,18,56,63,35,24,31,47)
清华大学出版社 TSINGHUA UNIVERSITY PRESS 2.1线性表的基本概念 ●建立空线性表的顺序存储空间 (即初始化线性表的顺序存储空间) #includestdlib h void inital(v, m, n) ET*v;intm,米n; I v=malloc(m*sizeof (ET)) 米n=0; return: ●释放线性表的顺序存储空间free(v)
2.1 线性表的基本概念 ●建立空线性表的顺序存储空间 （即初始化线性表的顺序存储空间） #include "stdlib.h" void initsl(v，m，n) ET *v； int m， *n； { v＝malloc(m*sizeof(ET))； *n＝0； return； } ●释放线性表的顺序存储空间 free(v)；