[原]第2章 线性表(4)

winston

C++实现一个单向链表://Node.h

2. #pragma once
3. #include "stdafx.h"
5. namespace Alexsoft
6. {
7.         template<class T>
8.         class Node
9.         {
10.         public:
11.                 T data;
12.                 Node<T> *next;
14.                 Node(T val,Node<T> *p){
15.                         data=val;
16.                         next=p;
17.                 }
18.                 Node(T val){
19.                         data=val;
20.                         next=0;
21.                 }
22.                 Node(){
23.                         data=0;
24.                         next=0;
25.                 }
26.         };
27. }//LinkNode.h
28. #pragma once
29. #include "stdafx.h"
30. #include "Node.h"
31. #include <iostream>
33. using std::cout;
35. namespace Alexsoft
36. {
37.         template<class T>
38.         class LinkList{
39.         public:
40.                 Node<T> *head;
42.                 LinkList(){
43.                         head=0;
44.                 }
46.                 LinkList(Node<T> &node){
47.                         head=&node;
48.                 }
50.                 int GetLength(){
51.                         Node<T> *p=head;
52.                         int len=0;
53.                         while(p!=0){
54.                                 ++len;
55.                                 p=p->next;
56.                         }
57.                         return len;
58.                 }
60.                 void Clear(){
61.                         head=0;
62.                 }
64.                 bool IsEmpty(){
65.                         if(head==0)
66.                                 return true;
67.                         else
68.                                 return false;
69.                 }
71.                 void Append(T item){
72.                         Node<T> *q=new Node<T>(item);
74.                         if(head==0)
75.                                 head=q;
76.                         else{
77.                                 Node<T> *p=head;
78.                                 while(p->next!=0){
79.                                         p=p->next;
80.                                 }
81.                                 p->next=q;
82.                         }
83.                 }
85.                 void Insert(T item, int i){
86.                         if(IsEmpty()||i<0)
87.                                 cout<<"List is empty or Position is error!";
89.                         Node<T> *q=new Node<T>(item);
91.                         if(i==0){
92.                                 q->next=head;
93.                                 head=q;
94.                                 return;
95.                         }
96.                         else{
97.                                 Node<T> *p=head;
98.                                 Node<T> *post=p;
99.                                 int index=0;
100.                                 while(index<i&&p!=0){
101.                                         post=p;
102.                                         p=p->next;
103.                                         ++index;
104.                                 }
106.                                 if(index==i){
107.                                         q->next=post->next;
108.                                         post->next=q;
109.                                 }
110.                         }
111.                 }
113.                 T Delete(int i){
114.                         if(IsEmpty()||i<0){
115.                                 cout<<"Link is empty or position is error!";
116.                                 return T();
117.                         }
118.                        
119.                         if(i==0){
120.                                 Node<T> *q=head;
121.                                 head=head->next;
122.                                 return q->data;
123.                         }
124.                         else{
125.                                 int index=0;
126.                                 Node<T> *p=head;
127.                                 Node<T> *post;
128.                                 while(p->next!=0&&index<i){
129.                                         ++index;
130.                                         post=p;
131.                                         p=p->next;
132.                                 }
134.                                 if(index==i){
135.                                         post->next=p->next;
136.                                         return p->data;
137.                                 }
138.                                 else{
139.                                         cout<<"The 1th node is not exist!";
140.                                         return T();
141.                                 }
142.                         }
143.                 }
145.                 T GetItem(int i){
146.                         if(IsEmpty()){
147.                                 cout<<"List is empty";
148.                                 return T();
149.                         }
151.                         Node<T> *p=head;
152.                         int j=0;
154.                         while(p->next!=0&&j<i){
155.                                 ++j;
156.                                 p=p->next;
157.                         }
159.                         if(j==i){
160.                                 return p->data;
161.                         }
162.                         else{
163.                                 cout<<"The target node is not exist!";
164.                                 return T();
165.                         }
166.                 }
168.                 int Locate(T value){
169.                         if(IsEmpty()){
170.                                 cout<<"List is Empty!";
171.                                 return -1;
172.                         }
174.                         Node<T> *p=head;
175.                         int i=0;
176.                         while(p->data!=value&&p->next!=0){
177.                                 p=p->next;
178.                                 ++i;
179.                         }
180.                         if(p->data==value){
181.                                 return i;
182.                         }
183.                         else{
184.                                 cout<<"Not found";
185.                                 return -1;
186.                         }
187.                 }
188.         };
189. }
192. Verify Codes:
193. // CCA.cpp : Defines the entry point for the console application.
194. //
196. #include "stdafx.h"
197. #include "Algri.h"
198. #include <iostream>
199. #include "LinkNode.h"
201. using namespace std;
202. using namespace Jeffery;
203. using namespace Alexsoft;
205. int _tmain(int argc, _TCHAR* argv[])
206. {
207.         LinkList<int> li= LinkList<int>();
208.         for(int i=0;i<8;i++)
209.         {
210.                 li.Append(i);
211.         }
213.         Node<int> *node=li.head;
214.         do
215.         {
216.                 cout<<node->data<<" ";
217.                 node=node->next;
218.         }while(node!=0);
219.         cout<<endl;
221.         li.Insert(100,5);
223.         node=li.head;
224.         do
225.         {
226.                 cout<<node->data<<" ";
227.                 node=node->next;
228.         }while(node!=0);
229.         cout<<endl;
231.         li.Insert(1000,9);
233.         node=li.head;
234.         do
235.         {
236.                 cout<<node->data<<" ";
237.                 node=node->next;
238.         }while(node!=0);
239.         cout<<endl;
241.         li.Delete(2);
243.         node=li.head;
244.         do
245.         {
246.                 cout<<node->data<<" ";
247.                 node=node->next;
248.         }while(node!=0);
249.         cout<<endl;
251.         cout<<li.GetItem(7)<<endl;
252.         cout<<li.Locate(4)<<endl;
253.         return 0;
254. }

复制代码

作者：xufei96 发表于2012-1-17 15:45:01 原文链接