第二章线性表 线性结构特点:在数据元素的非空有限集中 ★存在唯一的一个被称作“第一个”的数据元素 ★存在唯一的一个被称作“最后一个”的数据元素 ★除第一个外,集合中的每个数据元素均只有一个 前驱 ★除最后一个外,集合中的每个数据元素均只有 个后继
第二章线性表 线性结构特点：在数据元素的非空有限集中 存在唯一的一个被称作“第一个”的数据元素 存在唯一的一个被称作“最后一个”的数据元素 除第一个外，集合中的每个数据元素均只有一个 前驱 除最后一个外，集合中的每个数据元素均只有一 个后继
§2.1线性表的逻辑结构 ★定义:一个线性表是n个数据元素的有限序列 如(a12c2 例英文字母表(A,BC2)是一个线性表 例 学号 姓名 年龄数 数据元素 001 张三 18 002 李四 19 ★特征 今元素个数n一表长度,n=0空表 1<i<n时 a的直接前驱是a1a1无直接前驱 ●a的直接后继是a1,an元直接后继 今元素同构,且不能出现缺项
§2.1 线性表的逻辑结构 定义：一个线性表是n个数据元素的有限序列 如(a1 ,a2,,ai , an ) 例 英文字母表（A,B,C,…..Z)是一个线性表 例 学号 姓名 年龄 001 张三 18 002 李四 19 …… …… …… 数据元素 特征： ❖元素个数n—表长度，n=0空表 ❖1<i<n时 ⚫ai的直接前驱是ai-1，a1无直接前驱 ⚫ai的直接后继是ai+1，an无直接后继 ❖元素同构，且不能出现缺项
§2.2线性表的顺序存储结构 ★顺序表: 今定义:用一组地址连续的存储单元存放一个线性表叫 今元素地址计算方法 o LOC(a)=LOC(a)+(i-1)*L ●Loc(ar)=Loc(a)+L ●其中 ◆L一一个元素占用的存储单元个数 ◆LOC(a)-线性表第个元素的地址 特点: ●实现逻辑上相邻—物理地址相邻 ●实现随机存取 实现:可用C语言的一维数组实现
§2.2 线性表的顺序存储结构 顺序表： ❖定义：用一组地址连续的存储单元存放一个线性表叫~ ❖元素地址计算方法： ⚫LOC(ai)=LOC(a1)+(i-1)*L ⚫LOC(ai+1)=LOC(ai)+L ⚫其中： ◆L—一个元素占用的存储单元个数 ◆LOC(ai)—线性表第i个元素的地址 ❖特点： ⚫实现逻辑上相邻—物理地址相邻 ⚫实现随机存取 ❖实现：可用C语言的一维数组实现
V数组下标 内存 元素序号 a typedef int DATATYPE a2 2 #define m 1000 DATATYPE data MI 例 typedef struct card int num n-1 char name 201 char author 101 备用空间 char publisher 30 float price SDATATYPE DATATYPE libraryIMI 或动态申请和释放内存 DATATYPE pData=(DATATYPE")malloc(M*sizeof(DATATYPE)) free(pData)
a1 a2 an 0 1 n-1 1 2 n V数组下标 内存 元素序号 M-1 typedef int DATATYPE; #define M 1000 DATATYPE data[M]; 例 typedef struct card { int num; char name[20]; char author[10]; char publisher[30]; float price; }DATATYPE; DATATYPE library[M]; 备 用 空 间 数据元素不是简单类型时,可定义结构体数组 或动态申请和释放内存 DATATYPE *pData = (DATATYPE *)malloc(M*sizeof(DATATYPE)); free(pData);
★插入 令定义:线性表的插入是指在第(1≤i≤n+1)个元素 之前插入一个新的数据元素X,使长度为∩的线性表 15c2 变成长度为n+1的线性表 需将第i至第n共(n-i+1)个元素后移 今算法 Ch2 1.txt Ch2 1.c
插入 ❖定义：线性表的插入是指在第I（1i n+1）个元素 之前插入一个新的数据元素x，使长度为n的线性表 (a1 ,a2,,ai−1 ,ai , an ) 变成长度为n+1的线性表 (a1 ,a2,,ai−1 , x,ai , an ) 需将第i至第n共（n-i+1)个元素后移 ❖算法 Ch2_1.c