数据结构线性表.ppt

第2章线性表
线性表的类型定义
线性表的顺序表示和实现
线性表的链式表示和实现
线性链表
循环链表
双向链表
一元多项式的表示及相加
双向链表
每个结点中设置两个指针,一个指向后继,一个指向前驱。可直接确定一个结点的前驱和后继结点。从而可提高效率。
P
p=(p->prior)->next=(p->next)->prior
线性表的双向链表存储结构
typedef struct DuNode{
ElemType data;
struct DuNode *prior,*next;
}DuNode, * DulinkList;
双向链表的操作特点:
1、“查询”和单链表相同
2、“插入”和“删除”时需要同时修改两个方向上的指针。
ai
ai-1
e
s->next = p->next; p->next = s;
s->next->prior = s; s->prior = p;
p
s
ai-1
双向链表的插入(后插)
ai-1
ai
e
p
s
ai-1
ai
双向链表的插入(前插)
s—>prior=p—>prior; s—>next=p;
p—>prior—>next=s; p—>prior=s;
ai-1
双向链表的删除
ai
ai+1
p->next = p->next->next;
p->next->prior = p;
p
ai-1
双向循环链表
空表
非空表
a1
a2
an
用链表实现线性表的操作时,存在的问题:
;
,可能需遍历整个链表;
,元素的“位序”概念淡化,结点的“位置”概念加强。
改进链表结构:
Typedef struct LNode { //结点类型
ElemType data;
struct LNode *next;
} *Link, *Position;
Typedef struct LNode { //链表类型
Link head, tail;
int len;
} LinkList ;
基本操作……