基本数据结构——线性表要点.ppt

1.2 线性表 一、线性表概念与运算 二、线性表的顺序存储结构 三、线性表的链式存储结构 四、循环链表与双向链表 1.2 线性表 C={ ‘A’，’B’，...，’Z’ }。 1.2 线性表 一、线性表的概念与运算 一、线性表的概念与运算 1、线性表概念 定义 n(n≥0)个同类元素构成的有限线性序列，表示为L=（a1,a2,…,an）。 n为线性表L的表长 n=0,空表 线性表的逻辑结构特性 除第一个元素外，线性表中所有元素有且仅有一个直接前驱 除最后一个元素外，线性表中所有元素有且仅有一个直接后继 1.2 线性表 一、线性表的概念与运算 2、线性表运算 1)初始化 initiate ( L) 建立一个空线性表 2)求表长 length (L) 求表的数据元素个数 3)取结点 get(L, i) 给定元素 序号 i,.取元素内容(或结点地址指 针） 4)定位 locate(L, x) 给定元素内容x，取元素序号 i(或结点地址指针) 5)插入 insert(L , i, x)给定结点序号i，在其前(或其后)插入结点 1.2 线性表 一、线性表的概念与运算 3、线性表的分类 按存储方式分类 顺序表 链表 按可进行的操作的不同分类 栈 队列 串 数组 1.2 线性表 二、线性表的顺序存储结构 1、顺序表 用一组地址连续的存储单元依次存放线性表的数据元素，称为线性表的顺序存储结构，也称为向量式存储结构。 1.2 线性表 二、线性表的顺序存储结构 3、顺序表有关操作 1)顺序表初始化 ⑴操作: 建立一个长度为零的空表 ⑵接口： 入口和出口参数均为表指针 L ⑶算法描述：令表长度字段 L-length为零 ⑷函数实现： void initiatelist (listtype *L ) { L-length = 0; } 1.2 线性表 二、线性表的顺序存储结构 2)顺序表的插入(将一个新元素x插入位置i.1≤i≤n+1) 1.2 线性表 二、线性表的顺序存储结构 函数实现 #define true 1 #define false 0 int sqlistinsert(listtype * L,int i,elemtype x){ int j; if(L-lengthMAXSIZE) return(false); if(i0||iL-length) return(false); for(j=L-length-1;j=i;j--） L-data[j+1] = L-data[j]; L-data[i] = x; L-length ++ ; return(true);} 1.2 线性表 二、线性表的顺序存储结构 3）顺序表的删除 (删除顺序表中第i个元素, 1≤i≤n) 1.2 线性表 二、线性表的顺序存储结构 函数实现 #define true 1 #define fasle 0 int sqlistdelete(listtype * L,int i) { int j; if(i0||iL-length-1) return(false); for(j=i+1;jL-length;j++） L-data[j－1]=L-data[j]; L-length--; return (true); } 1.2 线性表 二、线性表的顺序存储结构 4.顺序表的特点 按序号访问结点，存取时间与位置无关，快 插入和删除结点要挪动大量元素，时间长短与位置有关 要求存放元素的存储单元连续； 有时会造成空间浪费或溢出。 适用范围 一旦建立，则插入、删除操作较少，经常进行查询操作的线性表 1.2 线性表 三、线性表的链式存储结构 1、线性链表 1)特点及分类 1.2 线性表 三、线性表的链式存储结构 2)结点构成及类型定义 结点构成 两部分：数据域，指针域 1.2 线性表 三、线性表的链式存储结构 例 画出26 个英文字母表的链式存储结构。 1.2 线性表 三、线性表的链式存储结构 2、线性链表的基本操作 1.2 线性表 三、线性表的链式存储结构 在链表L中q结点后插入结点s要涉及两个指针的修改： 新结点s的指针域指向原结点q的后继结点： s－next = q－next 原结点q的指针域指向新结点s： q－next = s 1.2 线性表 三、线性表的链式存储结构 算法：在线性链表中的q结点后面插入一个值为x的新结点 ⑴ 操作: ①动态分配一个新结点 ②新结点数据域赋值 x ③新结点指针域指向原