文档介绍：算法和数据结构03
We have many PowerPoint templates that has been specifically to help anyone that is stepping into the world
ChainNode<T> *current = first->link;
int index = 1; // index of current
first->data = x; // put x in head node
// search for x
while (current->data != x) {
current = current->link;
index++; }
// are we at head?
return ((current == first) ? 0 : index);
}
2019-03
9
Doubly Linked Circular List With Header Node
a
b
c
e
headerNode
d
2019-03
15
Empty Doubly Linked Circular List With Header Node
headerNode
2019-03
16
Circular Doubly Linked List
(双向循环链表)
a) Node
b) Null List
c) Circular Doubly Linked List
L D R
2019-03
17
template<class T> class DoubleNode{
friend Double<T>;
private: T data; DoubleNode<T> *left, *right; };
template<class T> class Double{
public: Double() { LeftEnd=RightEnd=0; };
~Double();
int Length()const; bool Find (int k, T& x) const ;
int Search (const T& x) const ;
Double<T>& Delete (int k, T& x);
Double<T>& Insert (int k, const T& x);
void Output (ostream& out) const ;
private : DoubleNode<T> *LeftEnd, *RightEnd; };
Program Class definition for doubly linked lists
2019-03
18
(1)
(2)
Delete (k) 删除第k 个元素
e = p->data;
p->prior->next = p->next;
p->next->prior = p->prior;
= k
2019-03
19
insert (k, x) 在第k个元素之前插入x
(1)
(2)
(3)
(4)
s->data =x;
s->prior =p->prior; p->prior->next = s;
s->prior =p; p->prior = s;
S
= k
2019-03
20
Summary
Chain
Singly linked circular list
Head node
Doubly linked list
Circular doubly linked list
2019-03
21
Indirect Addressing
Representation
间接寻址的定义、引入的目的。
如何实现间接寻址？
2019-03
22
template<class T> class IndirectList{
public: IndirectList(int MaxListSize=10);
~IndirectList( );
bool IsEmpty( )const {return length==0;}
int Length(