云大数据结构课程教学课件线性表.ppt

* 线性链表插入操作算法 Status ListInsert_L(LinkList L,int i,ElemType e) { p=L;j=0; while(pji-1){p=p-next;++j} if(!p || ji-1) return ERROR; s = (LinkList)malloc(sizeof(LNode)); s-data = e;s-next = p-next; p-next = s; return OK; } * 线性链表元素删除操作 * 线性链表删除操作算法 Status ListDelete_L(LinkList L,int i,ElemType e) { p=L;j=0; while(p-next ji-1){p=p-next;++j} if(!(p-next) || ji-1) return ERROR; q= p-data;p-next = q-next; e =q-next; free(q); return OK; } * 线性表的静态单链表存储结构 线性表的静态单链表存储结构 静态链表 定位函数的算法 通过集合运算（A-B）∪（B-A） 讨论静态链表的算法 * 线性表的静态单链表存储结构 #define MAXSIZE 1000 Typedef struct{ ElemType data; int cur; }component,SLinkList[MAXSIZE]; SLinkList S; * 线性表的静态单链表存储结构 head ZHAO QIAN SUN LI ZHOU WU ZHENG WANG ^ * 定位函数的算法 int LocateEle_SL(SLinkList S,ElemType e) { i = S[0].cur; while(i S[i].data !=e) i = S[i].cur; return i; } * （A-B）∪（B-A） 将整个数组空间初始化成一个链表 从备用空间取得一个结点 将空闲结点连接到备用链表上 * 初始化成一个链表 void InitSpace_SL(SLinkList space){ for(i=0; iMAXSIZE-1;++i) space[i].cur = i; space[MAXSIZE-1].cur = 0; }// InitSpace_SL int Malloc_SL(SLinkList space){ i= space[0].cur ; if(i) space[0].cur = space[i].cur ; return i; }// Malloc_SL * 回收空闲结点到备用链表 void Free_SL(SLinkList space,int k){ space[k].cur = space[0].cur; space[0].cur = k; } * 循环链表 * 双向链表 线性表的双向链表存储结构 typedef struct DuLNode { ElemType data;　 struct DuLNode *prior; struct DuLNode *next;; } DuLNode , *DULinkList; DuLNode Node; DULinkList L; * 双向链表 a b x s p a b c p 实验2 一元多项式的表示和运算 * * * * * * * * * * * * * * * 单击此处编辑母版标题样式 单击此处编辑母版副标题样式 * 数据结构 (Data Structure) 第二章 线 性 表 * 本章重点 顺序表及其操作 线性链表及其操作 指针操作 ? 第一节 线性表的类型定义 * 线性表 同质的n个数据元素的有序序列 领先于 领先于 称 是 的直接前驱元素， 是 的直接 后继元素。 线性表中的元素个数n（n≥0）定义为线性表的长度， n = 0时称为空表。 是第i个元素，称i为数据元素 在线性表中的位序。 * 抽象数据类型线性表 见教材page19的定义。 线性表操作实例 Union , MergeList 算法操作 — page21。 算法复杂度分析。 第二节 线性表的顺序表示和实现 * 顺序表 将线性表中的元素一个接一个地存储在一片相邻的存储区域中，这种结构称为“顺序表”。以元素在计算机内存中的“物理位置相邻”来表示线性表中数据元素之间的逻辑相邻关系。 只要确定了首地址，线性表中任意数据元素都可以随机存取。地址计算如下所示： Loc( )