2.2-算法设计（例2-1,2-2） 2.3线性表的链式表示和实现 基于顺序表的算法设计 ■单链表 例2-1和例2-2 ·循环链表 。基本操作在顺序表中的实现 。istLength(La) La.length ·静态链表 GetElem(Lb,I,e) e=Lb.elem[l-1]; ·静态链表V5.动态链表 LocateElem(La,e,equal) ListInsert(La,++La_len,e)La.elem[La.length++]=e; ·双向链表 ·基于顺序表实现例2-1和例2-2 善本操作的简单管换，针对例2-2得到P26算法2.7 ■其他表示 31V73 回 3划3 图 2.3.1单链表-定义 2.3.1单链表-定义 。单链表 。链表定义 ·质序映像的码点 ·蜡点表操元素的存储映德，包括数罐和潮罐（其信惠米为 指所或前) ,空间利用率不高（预先按最大空间分配） 头指针链表存取的开始，空NLL最后一个塘点的指 。表的容量不可扩充（针对顺序表的方案一） 春情地址 数操城烟针城 。即使表的客量可以扩充（针对顺序表的方案二），由于其 1 工 空间再分配和复制的开销，也不允许它频黛地使用 7 QIAN 13 。插入或副障时蓄移动大量元素 头指针 SUN :链表定义 31 19 WANG NULL WU 37 。特点 3 ZHAO 迎操上相邻的元章，物通上未必相邻，非题机存取 37 ZHENG 19 33/73 图 ZHOU 25 图 2.3.1单链表-定义和基本操作 2.3.1单链表-取第i个元素 ·能表定义 ,皇慕i个元意GetElem_L(LinkList L,intL,ElemType&e) typedef struct LNode{ 位量i、取得的第个元素&e ElemType data; /食船故 算法：带头结点的单能表中取第个元素 struct LNode*next//后向指针城 Status GetElem_L(LinkList L int i,ElemType &e){ >LNode,*LinkList; /川表示当前P所指向的元豪在线性表中的位序 p=出j=1y 。基本操作的实现 须欲录高的操作 while (j<i&&p!=NULL ,慕h元GetElem(UnkL,ntl,ElemType&e) 当1i表长n时 卫=P->next:计+/后移指针并计 ,插△排ListInsert_L(LinkList&L,lntl,ElemType e) 度为i-1； ,壁並山stDelete_L(LinkList&L,intl,ElemType&e) f(p==NULL IIj>)return ERROR;/第个元素不存在 e=p->data;/取第i个元素 ,创度差熊CreateL以(LinkLis过&L) return OK; 马清法 图 T(n)=0(n) 35/7 图31/73 2.2 –算法设计(例2-1,2-2) „ 基于顺序表的算法设计 例2-1和例2-2 „ 基本操作在顺序表中的实现 „ ListLength(La) La.length „ GetElem(Lb, i, e) e = Lb.elem[i-1]; „ LocateElem(La, e, equal) „ ListInsert(La, ++La_len, e) La.elem[La.length++] = e; „ 基于顺序表实现例2-1和例2-2 基本操作的简单替换，针对例2-2得到P26算法2.7 32/73 „ 单链表 „ 循环链表 „ 静态链表 „ 静态链表 vs. 动态链表 „ 双向链表 „ 其他表示 2.3 线性表的链式表示和实现 33/73 „ 单链表 „ 顺序映像的弱点 „ 空间利用率不高（预先按最大空间分配） „ 表的容量不可扩充（针对顺序表的方案一） „ 即使表的容量可以扩充（针对顺序表的方案二），由于其 空间再分配和复制的开销，也不允许它频繁地使用 „ 插入或删除时需移动大量元素 „ 链表定义 „ 特点 逻辑上相邻的元素，物理上未必相邻；非随机存取 2.3.1 单链表–定义 34/73 „ 链表定义 „ 结点-数据元素的存储映像，包括数据域和指针域（其信息称为 指针或链） „ 头指针-链表存取的开始 ；空(NULL)-最后一个结点的指针 2.3.1 单链表–定义 数据域 指针域 LI 43 QIAN 13 SUN 1 WANG NULL WU 37 ZHAO 7 ZHENG 19 ZHOU 25 存储地址 1 7 13 19 25 31 37 43 31 头指针 35/73 „ 链表定义 typedef struct LNode{ ElemType data; //数据域 struct LNode *next;//后向指针域 }LNode, *LinkList; „ 基本操作的实现 „ 取第i个元素 GetElem_L(LinkList L, int i, ElemType &e) „ 插入操作 ListInsert_L(LinkList &L, int i, ElemType e) „ 删除操作 ListDelete_L(LinkList &L, int i, ElemType &e) „ 创建单链表 CreateList_L(LinkList &L) „ 头插法 尾插法 2.3.1 单链表–定义和基本操作 36/73 „ 取第i个元素GetElem_L(LinkList L, int i, ElemType &e) 参数：链表L、位置i、取得的第i个元素&e 算法：带头结点的单链表中取第i个元素 Status GetElem_L( LinkList L, int i, ElemType &e) { // j表示当前p所指向的元素在线性表中的位序 p = L; j = 1; while ( j < i && p != NULL ){ p = p->next; j++; // 后移指针并计数j } if ( p == NULL || j > i) return ERROR;// 第i个元素不存在 e = p->data; // 取第i个元素 return OK; } 2.3.1 单链表–取第i个元素 T(n) =O(n) 频次最高的操作 当1≤i≤表长n时, 频度为i-1; 否则为n