数据结构(浙江工业大学).ppt

1
Main Index
Contents
Abstract Model of a List Obj.
position
Inserting at the Front of a LL
Deleting from the Front of a LL
Removing a Target Node
Handling the Back of the List
Inserting a Node at a specified Position
Lecture 3
– Linked Lists
1
2
Main Index
Contents
Linked List Nodes
Each Node is like a piece of a chain
To insert a new link, break the chain at the desired location and simply reconnect at both ends of the new piece.
2
3
Main Index
Contents
Linked List Nodes
Removal is like Insertion in reverse.
3
4
Main Index
Contents
position
An individual Node posed of two parts, 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.
4
Abstract Model of a List Object
data next
data next
data next
data null
first
2 0xbfffaa28
first
0xbfffaa20
0xbfffaa28
0xbfffaa60
0xbfffaa80
4 0xbfffaa60
6 0xbfffaa80
8 Null
first是指向node类型的指针:
node<int> *first;
first=new node<int>(2,NULL);
0xbfffaa20
5
6
Main Index
Contents
Node结点设计
Template <typename T>
class node
{
public:
T nodeValue; // data held by the node
node<T> *next; // next node in the list
node() : next(NULL)
{}
node(const T& item, node<T> *nextNode =
NULL) : nodeValue(item), next(nextNode)
{}
};
6
7
Main Index
Contents

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;
7
8
Main Index
Contents
将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;
}
2. Creating a Linked List
8
9
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