数据结构的练习与巩固
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
1 //结点定义
2 template <class T>
3 struct LinkNode
4 {
5 T data; //***可定义多个用来存储数据的变量
6 LinkNode<T>* link;
7
8 LinkNode(LinkNode<T>* ptr = NULL)
9 {link = ptr;}
10 LinkNode(const T& item, LinkNode<T> *ptr = NULL)
11 {data = item; link = ptr;}
12 };
1 //单链表定义
2 template <class T>
3 class List: public LinearList<T>
4 {
5 protected:
6 LinkNode<T>* first; //链表首项
7
8 public:
9 List()
10 { first = new LinkNode<T>; } //创建第一个结点，并将首项指针指向此结点
11 List(const T& x)
12 { first = new LinkNode<T>(x); } //带有数值的构造函数
13 List(List<T>& L); //复制构造函数
14 ~List() //析构函数
15 { makeEmpty(); }
16 void makeEmpty(); //删除链表
17 int Length()const; //得到长度
18
19 LinkNode<T>* getHead()const //得到首项结点
20 { return first; }
21 LinkNode<T>* Search(T x); //搜索数据为x的结点
22 LinkNode<T>* Locate(int i); //定位位置为i的结点
23 bool getData(int i, T& x); //得到位置为i的结点的数据
24 bool Insert (int i, T& x); //在位置i处插入数据为x的新结点
25 bool Remove (int i, T& x); //移除位置在i的结点，并获取该点数据
26 bool IsEmpty()const //判断是否是空指针，只要知道首项指针的link是否为空即可
27 {return first->link == NULL ? true : false;}
28 bool IsFull()const //判断链表是否满，默认不会满
29 {return false;}
30 void Sort(); //整理单链表
31 void Input(); //逐项创建单链表
32 void Output(); //逐项输出单链表
33 List<T>& opertator = (List<T> & L); //重构 =
34 }
35
36 template <class T>
37 void List<T>::makeEmpty()
38 {
39 LinkNode<T>* q;
40 while (first->link != NULL)
41 {
42 q = first->link; //从头开始逐项删除
43 first->link = q->link;
44 delete p;
45 }
46 }
47
48 template <class T>
49 int List<T>::Length()const
50 {
51 LinkNode<T>* p = first->link; //从头开始计数
52 int count = 0;
53 while (p != NULL) //当该节点为非空结点时
54 {
55 count++;
56 p = p->link; //p指向下一位
57 }
58 return count;
59 }
60
61 template <class T>
62 LinkNode<T>* List<T>::Search(T x)
63 {
64 LinkNode<T>* p = first->link; //从头开始找 所要找的结点
65 while (p != NULL) //当结点非空的时候
66 if (p->data == x)break; //当结点数据与所查找数据一致时
67 else p = p->link; //如果不一致，则移至下一位
68 return p; //当到结尾依旧没找到时，会指向空结点（最后一位是空结点）
69 }
70
71 template <class T>
72 LinkNode<T>* List<T>::Locate(int i)
73 {
74 if (i < 0)return NULL;
75 LinkNode<T>* p = first; //从头开始数
76 int j = 0; //创建一个用于计数的变量
77 while (p != NULL && j < i) //当没有到结尾的时候，继续向后移动
78 {
79 p = p->link;
80 j++;
81 }
82 return p; //当到结尾依旧没找到时，会指向空结点（最后一位是空结点）
83 }
84
85 template <class T>
86 bool List<T>::getData()
87 {
88 if (i <= 0)return NULL; //如果输入的位置不符合规范，则返回0值
89 LinkNode<T>* p = Locate(i); //定位i处
90 if (p == NULL) //如果该处是空结点，则返回0值
91 { return false; }
92 else
93 { x = p->data; return true; }
94 }
95
96 template <class T>
97 bool List<T>::Insert(int i, T&x)
98 {
99 LinkNode<T>* p = Locate(i);
100 if (p == NULL)return false;
101 else
102 {
103 New = new LinkNode<T>(x);
104 if (New == NULL)
105 { cerr << "错误：申请了空结点" << endl; exit(1); }
106 New->link = p->link; //插入新结点，前后关系变化
107 p->link = New;
108 return true;
109 }
110 }
111
112 template <class T>
113 bool List<T>::Remove(int i, T&x)
114 {
115 LinkNode<T>* p = Locate(i - 1); //定位所删节点的前一位
116 if (p == NULL || p->link == NULL) //如果此处或此处后一位，为空结点
117 return false;
118 LinkNode<T>* q = p->link; //令q指向所删节点
119 x = q->data; //提取所删节点数据
120 p->link = q->link; //前后关系变化
121 delete q; //删除该节点
122 return true;
123 }
124
125 template <class T>
126 List<T>& List<T>::Operator = (List<T> & L)
127 {
128 T value;
129 LinkNode<T>* srcptr = L.getHead(); //令源头指针指向源链表头部
130 LinkNode<T>* destptr = first = new LinkNode<T>; //创建新结点（新单链表）并让首相指针指向该结点
131 while (srcptr->link != NULL) //当源指针 仍未指向 源链表 的结尾空指针时
132 {
133 value = srcptr->link->data; //令value=该结点的值
134 destptr->link = new LinkNode<T>(value); //创建新结点并将value赋予
135 destptr = destptr->link; //向后移一位
136 srcptr = strpt->link; //向后移一位
137 }
138 destptr->link = NULL; //结尾指针指向空
139 return *this; //返回这个复制链表
140 }
141
142 //补充函数
143 template <class T>
144 void List<T>::inputFront(T endTag) //前插法建立单链表
145 {
146 LinkNode<T>* newNode; //创建新结点
147 T value;
148 makeEmpty(); //置空单链表
149 cin >> value;
150 while (value != endTag) //当没有输入停止符时
151 {
152 newNode = new LinkNode<T>(value); //创建新结点
153 if (newNode == NULL) //当创建了空结点时
154 {
155 cerr << "error" << endl; exit(1);
156 }
157 newNode->link = first->link; //前后关系变化
158 first->link = newNode;
159 cin >> value; //输入新value
160 }
161 }
162
163 template <class T>
164 void List<T>::inputRear(T endTag) //后插法建立单链表
165 {
166 LinkNode<T>* newNode, * last；
167 T value;
168 makeEmpty();
169 cin >> value;
170 last = first;
171 while (value != endTag) //当没有输入停止符时
172 {
173 newNode = new LinkNode<T>(value); //创建新结点
174 if(newNode==NULL) //当创建了空结点时
175 {
176 cerr << "error" << endl; exit(1);
177 }
178 last->link = newNode; //前后关系变化
179 last = newNode;
180 cin >> value; //输入新value
181 }
182 }