2.3线性表的链式表示与实现 顺序表示的优点是随机存取表中的任意元素 ■顺序表示的弱点是在作插入或删除操作时 需移动大量元素。 链式表示--没有顺序表示的弱点,也失去 了顺序表示的优点
2．3 线性表的链式表示与实现 ◼ 顺序表示的优点是随机存取表中的任意元素； ◼ 顺序表示的弱点是在作插入或删除操作时， 需移动大量元素。 ◼ 链式表示 ---- 没有顺序表示的弱点，也失去 了顺序表示的优点
2.3.1线性链表 线性表的链式表示--是可以用一组任 意的存储单元存储线性表的数据元素。 例:线性表 ■(赵,钱,孙,李,周,伍,张,王) 的链式表示
2．3．1 线性链表 ◼ 线性表的链式表示------是可以用一组任 意的存储单元存储线性表的数据元素。 ◼ 例： 线性表 ◼ （赵，钱，孙，李，周，伍，张，王） ◼ 的链式表示
(赵,钱,孙,李,周,伍,张,王) 的链式表示 头指针: 存储地址 匚数据域「指针域 31(赵的地址) 43 李钱孙王伍赵张周 13 13 25 37 31 37引 19 43 25 赵十钱线十-孙日李十周十“伍张十王
（赵，钱，孙，李，周，伍，张，王） 的链式表示 数据域 指针域 李 43 钱 13 孙 1 王 NULL 伍 37 赵 7 张 19 周 25 1 13 19 25 31 37 43 7 头指针： 31(赵的地址) 存储地址: 赵 钱 孙 李 周 伍 张 王 H
链表相关的名称 ■数据域、指针域 typedef struct Lnode& 结点、头结点 Elem Type data Struct lnode inext ■指针(链) iNode, * Linklist 链表、单链表(线性链表) aaa1-a--an∠
链表相关的名称 ◼ 数据域、指针域 ◼ 结点、头结点 ◼ 指针(链) ◼ 链表、单链表(线性链表) a1 a2 a3 L ai an typedef struct Lnode{ ElemType data; Struct Lnode *next; }Lnode, *Linklist;
线性表的单链表存储结构 Status GetElem L (LinkList L, int i, Elem Type &e) //L为带头结点的单链表的头指针;当第i个元素 //存在时,其值赋给e并返回OK,否则返回 ERROR Linklist p int J: p=L-next, j=1 while(p & jnext: ++j if(!p j>i) return ERROR p->data return OK 1// GetElem L
线性表的单链表存储结构 Status GetElem_L(LinkList L, int i, ElemType &e) { // L为带头结点的单链表的头指针;当第i个元素 //存在时，其值赋给e并返回OK, 否则返回ERROR. LinkList p; int j; p = L->next; j = 1; while (p && jnext; ++j; } if(!p || j>i) return ERROR; e = p->data; return OK; } // GetElem_L
插入结点: 指针p所指的结点后插入指针s所指的结点 s>next=p->next; p->next=s 插入前: 插入后: p a a十 >next=s s->next=p->next S
插入结点： 指针p所指的结点后插入指针s所指的结点 ◼ s->next = p->next; p->next = s; a1 a2 a3 a1 a3 s->next=p->next a2 p p s s p->next=s 插入前： 插入后：
插入结点程序 Status ListInsert L(LinkList &L, int i, ElemType e) I LinkList s, p int J p 0 while(p&&ji-1p=p->next; ++jl if(lpllj>i-1) return ERROR s=(Lnode *)malloc(sizeof (Lnode)) if(!s) return OVERFLOW s>data s->next= p>next, p>next =s return OK
插入结点程序 Status ListInsert_L(LinkList &L, int i, ElemType e) { LinkList s,p; int j; p = L; j = 0; while(p&&jnext;++j} if(!p||j>i-1) return ERROR; s = (Lnode *)malloc(sizeof(Lnode)); if(!s) return OVERFLOW; s->data = e; s->next = p->next; p->next = s; return OK; }
删除结点: 删除指针p所指的结点后的结点 p->next= p->next ->next p 删除前: a,afa+ p p 删除后: p->next= p->next ->next free(s) 释放结点后:
删除结点： 删除指针p所指的结点后的结点 ◼ p->next = p->next ->next; a1 a2 a3 p 删除前： 删除后： a1 a2 a3 p p->next = p->next ->next s s=p->next 释放结点后： a1 a3 p free(s)
删除结点程序 删除第i个元素,并由e返回其值 Status ListDlete L (LinkList L, int i, ElemType &e) I LinkList s, p int J p=L; j=0 while(p->next & jnext; ++j if(!(p->next)j>i-1) return ERROR s->next, p->next=s>next s->data free(s) return OK
删除结点程序 删除第i个元素，并由e返回其值 Status ListDlete_L(LinkList L, int i, ElemType &e) { LinkList s,p; int j; p = L; j = 0; while(p->next && jnext;++j} if(!(p->next)||j>i-1) return ERROR; s = p->next; p->next = s->next; e = s->data; free(s); return OK; }
2.3.2循环链表 循环链表的特点--表中的最后一个结 点的指针域指向头结点,整个链表形成 个环。 从表的任意结点出发可以找到表中其它 结点。 -a—一a|
◼ 循环链表的特点 ---- 表中的最后一个结 点的指针域指向头结点, 整个链表形成一 个环。 ◼ 从表的任意结点出发可以找到表中其它 结点。 2．3．2 循环链表 a1 a2 a3 L ai an