chap2第二章线性表.ppt

第二章 线性表 2.1线性表的定义 定义： n（?0）个数据元素的有限序列，记作（a1, …ai-1, ai, ai+1,…, an） 其中,ai 是表中数据元素，n 是表长度。 特点: 同一线性表中元素具有相同特性。 相邻数据元素之间存在序偶关系。 除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。 除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。 线性表的主要操作 初始化 访问 查找 插入 删除 等 2.2线性表的顺序表示和实现 定义：将线性表中的元素相继存放在一个连续的存储空间中。 存储结构：数组。 特点：线性表的顺序存储方式。 存取方式：顺序存取 顺序存储结构示意图 顺序表的存储方式： (假设每个元素占L个存储单元) 顺序表（SeqList）的类型定义 #define ListSize 100 //最大允许长度 typedef int ElemType; typedef struct { ElemType * elem; //存储空间基址 int length; //当前元素个数 } SeqList; 顺序表基本运算 初始化 void InitList ( SeqList L ) { L.elem = ( ElemType * ) malloc ( ListSize * sizeof ( ElemType ) ); if ( L.elem == NULL ) { printf ( “存储分配失败!\n” ); exit (1); } L.length = 0; } 按值查找：找x在表中的位置，若查找成功，返回表项的位置，否则返回-1 int Find ( SeqList L, ElemType x ) { int i = 0; while ( i L.length L.elem[i] != x ) i++; if ( i L.length ) return i; else return -1; } 按值查找：判断x是否在表中 int IsIn ( SeqList L, ElemType x ) { int i = 0, found=0; while ( i L.length !found ) if(L.elem[i] != x ) i++; else found=1; return found; } 求表的长度 int Length ( SeqList L ) { return L.length; } 提取函数：在表中提取第 i 个元素的值 ElemType Getelem ( SeqList L, int i ) { if ( i = 0 i L.length ) return L.elem[i]; else printf ( “参数 i 不合理！\n” ); } 按值查找：寻找x的后继 int Next ( SeqList L, ElemType x ) { int i = Find(x); if ( i =0 i L.length-1 ) return Getelem(L,i+1); else return -1; } 寻找x的前驱 int Pre ( SeqList L, ElemType x ) { int i = Find(x); if ( i 0 i L.length ) return Getelem(L, i-1); else return -1; } 插入 顺序表的插入 int Insert ( SeqList L, ElemType x, int i ) { //在表中第 i 个位置插入新元素 x if (i 0 || i L.length || L.length == ListSize) return 0; //插入不成功 else { for ( int j = L.length; j i;