数据结构3线性表2.ppt

线性表的链式表示与实现
顺序表示的优点是随机存取表中的任意元素;
顺序表示的弱点是在作插入或删除操作时,需移动大量元素。
链式表示---- 没有顺序表示的弱点,也失去了顺序表示的优点。
线性链表
线性表的链式表示------是可以用一组任意的存储单元存储线性表的数据元素。
例: 线性表
(赵,钱,孙,李,周,伍,张,王)
的链式表示
(赵,钱,孙,李,周,伍,张,王)的链式表示
1
13
19
25
31
37
43
7
头指针:
31(赵的地址)
存储地址:
钱
孙
李
周
赵
伍
张
王
H
链表相关的名称
数据域、指针域
结点、头结点
指针(链)
链表、单链表(线性链表)
a1
a2
a3
L
ai
an
typedef struct Lnode{
ElemType data;
Struct Lnode *next;
}Lnode, *Linklist;
线性表的单链表存储结构
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 && j<i){
p = p->next; ++j;
}
if(!p || j>i) return ERROR;
e = p->data;
return OK;
} // GetElem_L
插入结点:指针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)
{ LinkList s,p;
int j;
p = L; j = 0;
while(p&&j<i-1){p=p->next;++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;
a1
a3
a2
p
删除前:
删除后:
a1
a3
a2
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)
{ LinkList s,p;
int j;
p = L; j = 0;
while(p->next && j<i-1){p=p->next;++j}
if(!(p->next)||j>i-1) return ERROR;
s = p->next;
p->next = s->next;
e = s->data;
free(s);
return OK;
}
循环链表的特点---- 表中的最后一个结点的指针域指向头结点, 整个链表形成一个环。
从表的任意结点出发可以找到表中其它结点。
循环链表
a1
a2
a3
L
ai
an