现在正在看数据结构，感觉清华大学出版的《数据结构与C++高级教程(第3版)》里翻译有很多逻辑上的错误，虽然如此，但书上还是有很多不错的地方的。今天看到链表，算是复习一下，先把代码帖出来，慢慢再总结：
listitem.h:
Code
1
#ifndef _LISTITEM_H_
2#define _LISTITEM_H_
3
4#include <iostream>
5#include "listindexoutofrangeexception.h"
6#include "listexception.h"
7
8using namespace std;
9
10typedef int DataType;
11
12class List 
{
13
14public:
15 List();
16 //Default constructor
17 List(const List &);
18 //Copy constructor
19
20 ~List();
21 //Destructor
22
23 bool isEmpty() const;
24 //Determines whether a list is empty.
25 //Precondition:None.
26 //Postcondition:Return ture if the list is empty;
27 //Otherwise return false.
28
29 int getLength() const;
30 //Determines the length of the list
31 //Precondition:None
32 //Postcondition: Return the number of items that are currently in the list.
33
34 void insert(int position, DataType newItem);
35 //throw(ListIndexOutOfRangeException, ListException);
36 //Inserts an item into the list at position index.
37 //Precondition:the position indicates the item should be inserted in the list.
38 //Postcondition:if 1 <= position <= getLength()+1, the newItem will be inserted
39 //at the given position.
40 //Otherwise it will be thrown a exception.
41
42 void remove(int position);
43 //throw(ListIndexOutOfRangeException);
44 //Deletes an item from the list at a given position.
45 //Precondition:position indicates where the deletion should occur.
46 //Postcondition: if 1 <= position <= getLength(),
47 //the item at position index in the list is deleted, other throw a excepetion.
48
49 void retrieve(int position, DataType &dataItem) const;
50 //throw(ListIndexOutOfRangeException);
51 //Retrieves a list item by position.
52 //Precondition:position is the number of the item to be retrieved.
53 //Postcondition: if 1 <= position <= getLength(),
54 //dataItem is the value of the desired item.
55 //Otherwise throw a excepetion.
56
57private:
58
59
struct Node {
60 DataType data;
61 Node *next;
62
};
63
64 int size;
65 Node *head;
66private:
67 Node *find(int position) const;
68 //Return the node pointer given the position index.
69
};
70
71#endif
72listitem.cpp
Code
1#include <iostream>
2#include "ListItem.h"
3
4List::List(): size(0),head(NULL) {
5
6}
7
8List::List(const List &list) {
9
10}
11
12List::~List() {
13 while(!isEmpty())
14 remove(1);
15
16}
17
18bool List::isEmpty() const {
19
20 return size ? false : true;
21}
22
23int List::getLength() const {
24 return size;
25}
26
27List::Node* List::find( int position ) const {
28 if(position < 1 || position > getLength() )
29 return NULL;
30 else {
31 Node *cur = head;
32 for(int skin = 1; skin < position; ++skin)
33 cur = cur->next;
34 return cur;
35 }
36}
37
38
39void List::insert(int position , DataType data) {
40 if( position < 1 || position > getLength() + 1)
41 return;
42 //throw ListIndexOutOfRangeException("ListOutOfRangeException : insert position out of range");
43 else {
44 Node *newItem = new Node;
45 if( newItem == NULL)
46 return;
47 //throw ListException( "ListException : insert cannot allocate memory");
48 else {
49 ++size;
50 newItem->data = data;
51 if( position == 1) {
52 newItem->next = head;
53 head = newItem;
54 } else {
55 Node *prev = find( position - 1);
56 newItem->next = prev->next;
57 prev->next = newItem;
58 }
59 }
60 }
61}
62
63void List::retrieve( int position, DataType &data ) const {
64 if( position < 1 || position > getLength() )
65 return;
66 //throw ListIndexOutOfRangeException("ListOutOfRangeException : retrieve index out of range");
67 else {
68 Node *cur = find(position);
69 data = cur->data;
70 }
71}
72
73void List::remove(int position) {
74 Node *cur;
75
76 if(position < 1 || position > getLength())
77 return;
78 //throw ListIndexOutOfRangeException("ListOutOfRangeException : remove index out of range");
79 else {
80 --size;
81 if(position == 1) {
82 cur = head;
83 head = cur->next;
84 //head = head -> next; //Is different?
85 } else {
86 Node *prev = find(position - 1);
87 cur = prev->next;
88 prev->next = cur->next;
89 }
90 cur->next = NULL;
91 delete cur;
92 cur = NULL;
93 }
94}
95
链表的实现，有的有头指针，有的没有。但有头指针的时候会减少很多麻烦，在理解上也比没有头指针要简单的多。
再就是有头指针的时候，在对链表进行删除/插入操作的时候只有一个特殊点：头结点。
删除结点时使用下面赋值语句，会减少很多灾难性的、难以理解的错误：
cur->next = NULL;
delete cur;
cur = NULL;
删除非头结点：
prev -> next = cur -> next;
cur->next = NULL;
delete cur;
cur = NULL;
特别地，删除头结点：
head = head -> next;
cur->next = NULL;
delete cur;
cur = NULL;
插入非头结点：
newItem -> next = cur;
prev->next = newItem;
特别地，插入头结点：
newItem -> next = head;
head = newItem;
复制链表时要使用深复制