godson

单向链表的学习

      现在正在看数据结构,感觉清华大学出版的《数据结构与C++高级教程(第3版)》里翻译有很多逻辑上的错误,虽然如此,但书上还是有很多不错的地方的。今天看到链表,算是复习一下,先把代码帖出来,慢慢再总结:
listitem.h:

 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
72

listitem.cpp
Code

      链表的实现,有的有头指针,有的没有。但有头指针的时候会减少很多麻烦,在理解上也比没有头指针要简单的多。
再就是有头指针的时候,在对链表进行删除/插入操作的时候只有一个特殊点:头结点。

      删除结点时使用下面赋值语句,会减少很多灾难性的、难以理解的错误:
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;

复制链表时要使用深复制

posted on 2009-10-11 18:46 伴我闯天涯 阅读(140) 评论(0)  编辑 收藏 引用

My Links

Blog Stats

常用链接

留言簿

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜