数据结构第讲浙江工业大学详解演示文稿

node() : next(NULL) {}
node(const T& item, node<T> *nextNode = NULL) : nodeValue(item), next(nextNode)
{} };
7
Main Index
Contents
1.如何生成链表
node<int> *nodeptr1,*nodeptr2; nodeptr1=new node<int>(1,null); nodeptr2=new node<int>(2,null); 思考：如何连接两个结点？ nodeptr1->next=nodeptr2; nodeptr3=new node<int>(3,null); nodeptr2->next=nodeptr3;
3.4 Handling the Back of the List – with back pointer
front back
... //
//
item newNode
The initial list is empty: front=NULL, back=NULL.
15
Main Index
Contents
Disconnect
Reconnect
3
Main Index
Contents
Linked List Nodes Removal is like Insertion in reverse.
Disconnect
Reconnect
4
Main Index
Contents
Node Composition An individual Node is composed of two parts, a
5
Main Index
Contents
Abstract Model of a List Object
data next first
data next
data next
data null
0xbfffaa20
0xbfffaa28
0xbfffaa60
0xbfffaa80
2 0xbfffaa28
4 0xbfffaa60
Stack
front
D
C
B
A
Linked List
13
Main Index
Contents
3.3 Handling the Back of the List
node<T> *curr=front; while(curr!=null){
curr=curr->next; }
14
Main Index
Contents
数据结构第讲浙江工业大学详解演示文稿
（优选）数据结构第讲浙江工业大学
Linked List Nodes Each Node is like a piece of a chain
Individual Piece
Pop Chain
To insert a new link, break the chain at the desired location and simply reconnect at both ends of the new piece.
10
Main Index
Contents
2. Creating a Linked List
node<int> *front=Null, *newNode,*back;
int i=0;
while(i<5)
{
if(i==0){
front=new node<int>(i,NULL);
back=front;
}
else{
newNode=new node<int>(i,NULL);
back->next=newNode;
back=back->next;
}
i++;
}//不同的编程风格
11
Main Index
Contents
3. 1 Inserting at the Front of a Linked List
6 0xbfffaa80
8 Null
first 0xbfffaa20
first是指向node类型的指针： node<int> *first; first=new node<int>(2,NULL);
Node结点设计
Template <typename T> class node {
public: T nodeValue; // data held by the node node<T> *next; // next node in the list
Before
After front
front back item
Before
front
(a)
newNode
20
55
front
After
front
(b)
item
20
55
front
12
Main Index
Contents
3.2 Handling the Back of the List
top D
C B A
Data field containing the data stored by the node, and a Pointer field that marks the address of the next Node in the list.
nodeValue
next
nodeValue next
Main Index
Contents
2. Creating a Linked List
将1,2,3,4,5顺序插入链表（反向插入） node<int> *front=Null, *newNode; int i;
for(i=1;i<=5;i++) {
front=new node<int>(i,frontntents
2. Creating a Linked List
将1,2,3,4,5顺序插入链表（正向插入） node<int> *nodeptr1,*nodeptr2; for(int i=1;i<6;i++) {
nodeptr1=new node<int>(i,null); nodeptr1? } nodeptr1=new node<int>(1,null); for(int i=2;i<6;i++) { nodeptr2=new node<int>(i,null); nodeptr1->next=nodeptr2; nodeptr1=nodeptr1->next; }