咸阳企业做网站,如何设计一个网页登录窗口,电影模板哪个网站好,北京建工集团有限公司官网线性表及其实现多项式的表示什么是线性表线性表的抽象数据类型描述线性表的顺序存储实现线性表的链式存储实现 线性表及其实现
多项式的表示
[例] 一元多项式及其运算 一元多项式 #xff1a; 主要运算#xff1a;多项式相加、相减、相乘等 【分析】如何表示多项式?…线性表及其实现多项式的表示什么是线性表线性表的抽象数据类型描述线性表的顺序存储实现线性表的链式存储实现 线性表及其实现
多项式的表示
[例] 一元多项式及其运算 一元多项式 主要运算多项式相加、相减、相乘等 【分析】如何表示多项式? 多项式的关键数据 多项式项数n 各项系数ai 及指数 i 方法1顺序存储结构直接表示 数组各分量对应多项式各项 a[i]: 项xi的系数ai 方法2顺序存储结构表示非零项 按指数大小有序存储 相加过程从头开始比较两个多项式当前对应项的指数
方法3链表结构存储非零项
什么是线性表
多项式表示问题的启示 1. 同一个问题可以有不同的表示存储方法 2. 有一类共性问题有序线性序列的组织和管理 线性表(Linear List) : 由同类型数据元素构成有序序列的线性结构 1.表中元素个数称为线性表的长度 2.线性表没有元素时称为空表 3.表起始位置称表头表结束位置称表尾
线性表的抽象数据类型描述
类型名称线性表List
数据对象集线性表是 n (≥0)个元素构成的有序序列( a1, a2,… ,an )
操作集线性表L属于 List整数i表示位置元素X 属于 ElementType 线性表基本操作主要有
1、List MakeEmpty()初始化一个空线性表L 2、ElementType FindKth( int K, List L )根据位序K返回相应元素 3、int Find( ElementType X, List L )在线性表L中查找X的第一次出现位置 5、void Delete( int i, List L )删除指定位序i的元素 6、int Length( List L )返回线性表L的长度n。
线性表的顺序存储实现
利用数组的连续存储空间顺序存放线性表的各元素 主要操作的实现
typedef int Position;
typedef struct LNode *List;
struct LNode {ElementType Data[MAXSIZE];Position Last;
};/* 初始化 */
List MakeEmpty()
{List L;L (List)malloc(sizeof(struct LNode));L-Last -1;return L;
}/* 查找 */
#define ERROR -1Position Find( List L, ElementType X )
{Position i 0;while( i L-Last L-Data[i]! X )i;if ( i L-Last ) return ERROR; /* 如果没找到返回错误信息 */else return i; /* 找到后返回的是存储位置 */
}/* 插入 */
/*注意:这里P是存储下标位置从0开始*/
bool Insert( List L, ElementType X, Position P )
{ /* 在L的指定位置P前插入一个新元素X */Position i;if ( L-Last MAXSIZE-1) {/* 表空间已满不能插入 */printf(表满); return false; } if ( P0 || PL-Last1 ) { /* 检查插入位置的合法性 */printf(位置不合法);return false; } for( iL-Last; iP; i-- )L-Data[i1] L-Data[i]; /* 将位置P及以后的元素顺序向后移动 */L-Data[P] X; /* 新元素插入 */L-Last; /* Last仍指向最后元素 */return true;
} /* 删除 */
/*注意:这里P是存储下标位置从0开始/
bool Delete( List L, Position P )
{ /* 从L中删除指定位置P的元素 */Position i;if( P0 || PL-Last ) { /* 检查空表及删除位置的合法性 */printf(位置%d不存在元素, P ); return false; }for( iP1; iL-Last; i )L-Data[i-1] L-Data[i]; /* 将位置P1及以后的元素顺序向前移动 */L-Last--; /* Last仍指向最后元素 */return true;
}
线性表的链式存储实现
不要求逻辑上相邻的两个元素物理上也相邻通过“链”建 立起数据元素之间的逻辑关系。 插入、删除不需要移动数据元素只需要修改“链”。 访问序号为 i 的元素 求线性表的长度
int Length ( List PtrL ) { List p PtrL; /* p指向表的第一个结点*/ int j 0; while ( p ) { p p-Next; j; /* 当前p指向的是第 j 个结点*/ } return j;
}
typedef struct LNode *PtrToLNode;
struct LNode {ElementType Data;PtrToLNode Next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;/* 查找 */
#define ERROR NULLPosition Find( List L, ElementType X )
{Position p L; /* p指向L的第1个结点 */while ( p p-Data!X )p p-Next;/* 下列语句可以用 return p; 替换 */if ( p )return p;elsereturn ERROR;
}/* 带头结点的插入 */
/*注意:这里P是链表结点指针在P之前插入新结点 */
bool Insert( List L, ElementType X, Position P )
{ /* 这里默认L有头结点 */Position tmp, pre;/* 查找P的前一个结点 */ for ( preL; prepre-Next!P; prepre-Next ) ; if ( preNULL ) { /* P所指的结点不在L中 */printf(插入位置参数错误\n);return false;}else { /* 找到了P的前一个结点pre *//* 在P前插入新结点 */tmp (Position)malloc(sizeof(struct LNode)); /* 申请、填装结点 */tmp-Data X; tmp-Next P;pre-Next tmp;return true;}
}/* 带头结点的删除 */
/*注意:在删除位置参数P上与课程视频有所不同课程视频中i是序列位序从1开始这里P是拟删除结点指针 */
bool Delete( List L, Position P )
{ /* 这里默认L有头结点 */Position tmp, pre;/* 查找P的前一个结点 */ for ( preL; prepre-Next!P; prepre-Next ) ; if ( preNULL || PNULL) { /* P所指的结点不在L中 */printf(删除位置参数错误\n);return false;}else { /* 找到了P的前一个结点pre *//* 将P位置的结点删除 */pre-Next P-Next;free(P);return true;}
}
广义表(Generalized List) 广义表是线性表的推广 对于线性表而言 n个元素都是基本的单元素 广义表中这些元素不仅可以是单元素也可以是另一个广义表 多重链表 链表中的节点可能同时隶属于多个链 多重链表中结点的指针域会有多个如前面例子包含了Next和 SubList两个指针域但包含两个指针域的链表并不一定是多重链表比如在双向链表 不是多重链表。 多重链表有广泛的用途 基本上如树、图这样相对 复杂的数据结构都可以采 用多重链表方式实现存储。 矩阵可以用二维数组表示但二维数组表示有两个缺陷 数组的大小需要事先确定对于“稀疏矩阵 ”将造成大量的存储空间浪费 采用一种典型的多重链表——十字链表来存储稀疏矩阵 只存储矩阵非0元素项结点的数据域行坐标Row、列坐标Col、数值Value 每个结点通过两个指针域把同行、同列串起来; 行指针(或称为向右指针)Right 列指针或称为向下指针Down 用一个标识域Tag来区分头结点和非0元素结点 头节点的标识值为“Head”矩阵非0元素结点的标识值为“Term”。
