链式线性表

2013-03-23 00:14:39

上学期的时候就大致看了数据结构与算法分析的了，但感觉收获比较少，总结原因是编程实践少了，所以今年趁着老师上课，就多进行一些代码的实践，也准备拿一些ACM的题目来练练。

中午的时候就将链式表的代码打了一遍，现在贴上来分享。

为了节省时间，我的注释也相对较少，有不懂得可以提问。

第一个是Link.head，这是一个节点类，是链表中的小单元

 1 #ifndef LINK
 2 #define LINK
 3 //Singly-linked list node
 4 
 5 template <class Elem> class Link{
 6     public:
 7     Elem element;
 8     Link *next;
 9     Link(const Elem& elemval,Link *nextval = NULL)
10     {
11         element = elemval;
12         next = nextval;
13     }
14     Link(Link *nextval = NULL)
15     {
16         next = nextval;
17     }
18 };
19 #endif

第一个，LList头文件，这就是链表的主体，由节点类组成。

  1 //List abstrat class
  2 #ifndef LIST
  3 #define LIST
  4 //Linked list implementation
  5 #include"Link.h"
  6 #include<iostream>
  7 template <class Elem> class LList {
  8     private:
  9     Link<Elem> *head;   //Pointer to list header
 10     Link<Elem> *tail;    //Pointer to list tail
 11     Link<Elem> *fence;   //Last element on the left side
 12     int leftcnt;      
 13     int rightcnt;
 14     void init()
 15     {
 16         fence = tail = head = new Link<Elem>;
 17         leftcnt = rightcnt = 0;
 18     }
 19     void removeall()
 20     {
 21         while(head != NULL)
 22         {
 23             fence = head;
 24             head = head->next;
 25             delete fence;
 26         }
 27     }
 28     public:
 29     LList(int size = 100)
 30     {
 31         init();
 32     }
 33     ~LList()
 34     {
 35         removeall();
 36     }
 37     void clear()
 38     {
 39         removeall();
 40         init();
 41     }
 42     bool insert(const Elem& item)
 43     {
 44         fence->next = new Link<Elem>(item , fence->next);
 45         if(tail == fence)
 46         tail = fence->next;
 47         rightcnt++;
 48         return true;
 49     }
 50     bool append(const Elem& item)
 51     {
 52         tail = tail->next = new Link<Elem>(item,NULL);
 53         rightcnt++;
 54         return true;
 55     }
 56     bool remove(Elem &item)
 57     {
 58         if(fence->next == NULL)
 59         return false;
 60         item = fence->next->element;
 61         Link<Elem> *ltemp = fence->next;
 62         fence->next = ltemp->next;
 63         if(tail == ltemp)
 64         tail = fence;
 65         delete ltemp;
 66         rightcnt--;
 67         return true;
 68     }
 69     void setStart()
 70     {
 71         fence = head;
 72         rightcnt += leftcnt;
 73         leftcnt = 0;
 74     }
 75     void setEnd()
 76     {
 77         fence = tail;
 78         leftcnt += rightcnt;
 79         rightcnt = 0;
 80     }
 81     //cost most time n
 82     void prev()
 83     {
 84         if(fence == head)
 85         return;
 86         Link<Elem> *ltemp = head;
 87         while(ltemp->next != fence)
 88         ltemp = ltemp->next;
 89         fence = ltemp;
 90         rightcnt++;
 91         leftcnt--;
 92     }
 93     void next()
 94     {
 95         if(fence == tail)
 96         return;
 97         fence = fence->next;
 98         rightcnt--;
 99         leftcnt++;
100     }
101     int leftLength()const
102     {
103         return leftcnt;
104     }
105     int rightLength()const
106     {
107         return rightcnt;
108     }
109     //set the size of left partition to pos
110     bool setPos(int pos)
111     {
112         if(pos < 0 || pos > rightcnt + leftcnt)
113         return false;
114         fence = head;
115         for(int i = 0;i < pos;i++)
116         fence = fence->next;
117         return true;
118     }
119     bool getValue(Elem &it)const
120     {
121         if(rightLength() == 0)
122         return false;
123         it = fence->next->element;
124         return true;
125     }
126     void print()const
127     {
128         Link<Elem> *ltemp = head;
129         std::cout << "< ";
130         while(fence != ltemp)
131         {
132             std::cout << ltemp->next->element << " ";
133             ltemp = ltemp->next;
134         }
135         std::cout << "| ";
136         while(ltemp->next != NULL)
137         {
138             std::cout << ltemp->next->element << " ";
139             ltemp = ltemp->next;
140         }
141         std::cout << ">\n";
142     }
143 };
144 
145 
146 
147 
148 
149 
150 #endif

今天还继续进行着算法的工作，等我总结了就跟大家分享。

set up a work routine and stick to it,your body will adapt.