山东师大信息学院.ppt

山东师大信息学院 Zheng Zhihua 第二章 线 性 表 第二章 线性表 集合 线性结构 树型结构 图型结构 2.1 线性表的逻辑结构 形式定义 2.2 线性表的顺序表示和存储 顺序 存储方式 链式 2.顺序存储结构的地址计算方法 Loc(ai+1) = Loc(ai) + l l为长度结点 例 一个向量的第一个存储地址是100，每个元素的长度为2，则第5个元素的地址是多少？ 解： Loc(5) = Loc(a1) + （i-1）*l  = 100 + （5-1）*2 = 108 3.操作 建立一个向量（初始化） 线性表的查找 在线性表的第i个元素前插入一个元素 删除第i个元素或删除值为x的元素 排序 InitList(L,n) // 结构初始化 void InitList( Sqlist L, int n) { int i; for ( i=0; in ; i++) Scanf(%d, A[i]); } 例 在向量A中的第 i 个元素前插入一个元素x 例 在向量A中的第 i 个元素前插入一个元素x void Insert ( Sqlist A, int i, int n) { int j; if (i1||in) printf(i值错！\n); else } 例 在n个元素的向量A中删除第 i 个元素 void Delet ( Sqlist A, int i, int n) { int j; if (i1 || in) printf(i值溢出！\n); else } 顺序表的数据类型描述如下： #define DATATYPE int #define MAXSIZE 100 typedef struct { DATATYPE datas［MAXSIZE］; int last; }SQlist; 4、算法分析 设?是随机变量 随着试验的结果而变化的量 对于每次试验取值不可预测 但对每个取值其概率是固定的 一个随机变量可用一个“概率分布表”刻划 一个随机变量可用一个“概率分布表”刻划 一个随机变量可用一个“概率分布表”刻划 求例1 扔硬币的数学期望E 求例2 的数学期望E 对于线性表的顺序结构 向表中插入一个元素， 需要移动元素的次数?是一个随机变量，对 n个元素的表来说，共有n+1个位置可插入。 所以每个位置的概率是 在第i个元素之前插入元素需要移动n-i+1次 可见 2.3 线性表的链式存储结构的表示和实现 2.3.1 线性链表 一、单链表——每个结点只含一个指针域的链式结构称为单链表。 单链表中获取一个元素  GetElem(L, i, e) 2. 结点的产生和回收 ——是在程序执行期间，通过调用动态存储分配函数malloc()动态产生。 例 # include malloc.h main(){ …… p=(Linklist)malloc(sizeof(100)); p=(Linklist)malloc(sizeof(snode)); p=(snode*)malloc(sizeof(snode)); …… } 为简单起见 # include malloc.h # define Newnode() (prt) malloc(sizeof(snode)) main(){ …… p = Newnode();//申请一个新结点 …… } free(p) 3、插入一个结点的操作 在单链表中的第i个元素前插入元素eListInsert(head , i, e) 4、删除一个结点的操作 例 ListDelete (head, i, e) 2.3.2 循环单链表 带头结点的循环单链表 不带头结点的循环单链表 2.3.3 双链表 形式 三、静态单链表 静态链表的插入和删除 将一维数组A[n]中的各分量链成一个备用链表 向备用链表申请一个结点 向备用链表释放一个结点 一、多项式的存储 一元多项式 释放一个结点 ai-1 有序序列 a1 … ai-1, ai，… 改变为 a1 … ai-1, e，ai… e ai ai-1 q p q-next = p-next; p-next = q; hea