本文共 7344 字,大约阅读时间需要 24 分钟。
CSDN首页| 空间| 新闻| 论坛| 群组| BLOG| 文档| 下载| 读书| 网摘| 视频| 开源| 书店| 程序员| 项目交易| 培训 首页 随便看看 帮助
新手必读 站务公告及反馈投诉 诚邀高手做老师赵天武的笔记
赵天武的主页 | 查看全部笔记主页记录日志相册分享话题留言好友
查看笔记|返回笔记列表 实现堆栈、链表、队列 注释比较清楚的2009-08-17 11:40 1:定义线性表(Linear List)是具有相同特性的数据元素的一个有限序列。该序列中所含元素的个数称作线性表的长度。
堆实际上指的就是(满足堆性质的)优先队列的一种数据结构,第1个元素有最高的优先权
栈实际上就是满足先进后出的性质的数学或数据结构。
(虽然堆栈,堆栈的说法是连起来叫,但是他们还是有很大区别的,连着叫只是由于历史的原因。)
队列 是一种特殊的线性表,它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列。(队列具有先进先出(FIFO)的特点)
2:实现
Code
<!--Code highlighting produced by Actipro CodeHighlighter (freeware)
--> 1 定义结点#region 定义结点
2 public class ListNode 3 { 4 public ListNode(int NewValue) 5 { 6 Value = NewValue; 7 } 8 9 // 前一个 10 public ListNode Previous; 11 12 // 后一个 13 public ListNode Next; 14 15 // 值 16 public int Value; 17 } 18 #endregion 19 20 定义链表类#region 定义链表类 21 //定义结点之后,开始类线性表的操作编程了.在LIST 类中,采用了,Head ,Tail, Current,三个指针,使用Append ,MoveFrist,MovePrevious,MoveNext,MoveLast ,Delete,InsertAscending,InsertUnAscending ,Clear 实现移动,添加,删除,升序插入,降序插入,清空链表操作,GetCurrentValue() 方法取得当前的值。 22 public class Clist 23 { 24 // 头指针 25 private ListNode Head; 26 // 尾指针 27 private ListNode Tail; 28 // 当前指针 29 private ListNode Current; 30 // 链表数据的个数 31 private int ListCountValue; 32 33 public Clist() 34 { 35 ListCountValue = 0; 36 Head = null; 37 Tail = null; 38 } 39 40 // 尾部添加数据 41 public void Append(int DataValue) 42 { 43 ListNode NewNode = new ListNode(DataValue); 44 if (IsNull()) 45 //如果头指针为空 46 { 47 Head = NewNode; 48 Tail = NewNode; 49 } 50 else 51 { 52 Tail.Next = NewNode; 53 NewNode.Previous = Tail; 54 Tail = NewNode; 55 } 56 Current = NewNode; 57 //链表数据个数加一 58 ListCountValue += 1; 59 } 60 61 // 删除当前的数据 62 public void Delete() 63 { 64 //若为空链表 65 if (!IsNull()) 66 { 67 //若删除头 68 if (IsBof()) 69 { 70 Head = Current.Next; 71 Current = Head; 72 ListCountValue -= 1; 73 return; 74 } 75 //若删除尾 76 if (IsEof()) 77 { 78 Tail = Current.Previous; 79 Current = Tail; 80 ListCountValue -= 1; 81 return; 82 } 83 //若删除中间数据 84 Current.Previous.Next = Current.Next; 85 Current = Current.Previous; 86 ListCountValue -= 1; 87 return; 88 } 89 90 } 91 // 向后移动一个数据 92 public void MoveNext() 93 { 94 if (!IsEof()) Current = Current.Next; 95 } 96 // 向前移动一个数据 97 public void MovePrevious() 98 { 99 if (!IsBof()) Current = Current.Previous;100 }101 // 移动到第一个数据102 public void MoveFrist()103 { 104 Current = Head;105 }106 // 移动到最后一个数据107 public void MoveLast()108 { 109 Current = Tail;110 }111 // 判断是否为空链表112 public bool IsNull()113 { 114 if (ListCountValue == 0)115 return true;116 return false;117 }118 // 判断是否为到达尾部119 public bool IsEof()120 { 121 if (Current == Tail)122 return true;123 return false;124 }125 // 判断是否为到达头部126 public bool IsBof()127 { 128 if (Current == Head)129 return true;130 return false;131 }132 public int GetCurrentValue()133 { 134 return Current.Value;135 }136 // 取得链表的数据个数137 public int ListCount138 { 139 get { return ListCountValue; }140 }141142 // 清空链表143 public void Clear()144 { 145 MoveFrist();146 while (!IsNull())147 { 148 //若不为空链表,从尾部删除149 Delete();150 }151 }152 // 在当前位置前插入数据153 public void Insert(int DataValue)154 { 155 ListNode NewNode = new ListNode(DataValue);156 if (IsNull())157 { 158 //为空表,则添加159 Append(DataValue);160 return;161 }162 if (IsBof())163 { 164 //为头部插入165 NewNode.Next = Head;166 Head.Previous = NewNode;167 Head = NewNode;168 Current = Head;169 ListCountValue += 1;170 return;171 }172 //中间插入173 NewNode.Next = Current;174 NewNode.Previous = Current.Previous;175 Current.Previous.Next = NewNode;176 Current.Previous = NewNode;177 Current = NewNode;178 ListCountValue += 1;179 }180181 // 进行升序插入182 public void InsertAscending(int InsertValue)183 { 184 //参数:InsertValue 插入的数据185 //为空链表186 if (IsNull())187 { 188 //添加189 Append(InsertValue);190 return;191 }192 //移动到头193 MoveFrist();194 if ((InsertValue < GetCurrentValue()))195 { 196 //满足条件,则插入,退出197 Insert(InsertValue);198 return;199 }200 while (true)201 { 202 if (InsertValue < GetCurrentValue())203 { 204 //满族条件,则插入,退出205 Insert(InsertValue);206 break;207 }208 if (IsEof())209 { 210 //尾部添加211 Append(InsertValue);212 break;213 }214 //移动到下一个指针215 MoveNext();216 }217 }218 // 进行降序插入219 public void InsertUnAscending(int InsertValue)220 { 221 //参数:InsertValue 插入的数据222 //为空链表223 if (IsNull())224 { 225 //添加226 Append(InsertValue);227 return;228 }229 //移动到头230 MoveFrist();231 if (InsertValue > GetCurrentValue())232 { 233 //满足条件,则插入,退出234 Insert(InsertValue);235 return;236 }237 while (true)238 { 239 if (InsertValue > GetCurrentValue())240 { 241 //满族条件,则插入,退出242 Insert(InsertValue);243 break;244 }245 if (IsEof())246 { 247 //尾部添加248 Append(InsertValue);249 break;250 }251 //移动到下一个指针252 MoveNext();253 }254 }255 }256 #endregion257258 堆栈类#region 堆栈类259 public class CStack260 { 261 //调用链表类262 private Clist m_List;263264 public CStack()265 { 266 //构造函数267 m_List = new Clist();268 }269270 // 压入堆栈271 public void Push(int PushValue)272 { 273 //参数: int PushValue 压入堆栈的数据274 m_List.Append(PushValue);275 }276277 // 弹出堆栈数据,如果为空,则取得 2147483647 为 int 的最大值;278 public int Pop()279 { 280 //功能:弹出堆栈数据 281 int PopValue;282 if (!IsNullStack())283 { 284 //不为空堆栈285 //移动到顶286 MoveTop();287 //取得弹出的数据288 PopValue = GetCurrentValue();289 //删除290 Delete();291 return PopValue;292 }293 // 空的时候为 int 类型的最大值294 return 2147483647;295 }296297 // 判断是否为空的堆栈298 public bool IsNullStack()299 { 300 if (m_List.IsNull())301 return true;302 return false;303 }304305 // 堆栈的个数306 public int StackListCount307 { 308 get{return m_List.ListCount;}309 }310 311 // 移动到堆栈的底部312 public void MoveBottom()313 { 314 m_List.MoveFrist();315 }316 317 // 移动到堆栈的Top318 public void MoveTop()319 { 320 m_List.MoveLast();321 }322323 // 向上移动324 public void MoveUp()325 { 326 m_List.MoveNext();327 }328 329 // 向下移动330 public void MoveDown()331 { 332 m_List.MovePrevious();333 }334 335 // 取得当前的值336 public int GetCurrentValue()337 { 338 return m_List.GetCurrentValue();339 }340 341 // 删除取得当前的结点342 public void Delete()343 { 344 m_List.Delete();345 }346 347 // 清空堆栈348 public void Clear()349 { 350 m_List.Clear();351 }352 }353 #endregion354355 队列类#region 队列类356 public class CQueue357 { 358 private Clist m_List;359 public CQueue()360 { 361 //构造函数362 //这里使用到前面编写的List 363 m_List = new Clist();364 }365366 // 入队367 public void EnQueue(int DataValue)368 { 369 //功能:加入队列,这里使用List 类的Append 方法:370 //尾部添加数据,数据个数加1371 m_List.Append(DataValue);372 }373374 // 出队375 public int DeQueue()376 { 377 //功 能:出队378 //返回值: 2147483647 表示为空队列无返回379 int QueValue;380 if (!IsNull())381 { 382 //不为空的队列383 //移动到队列的头384 m_List.MoveFrist();385 //取得当前的值386 QueValue = m_List.GetCurrentValue();387 //删除出队的数据388 m_List.Delete();389 return QueValue;390 }391 return 2147483647;392 }393394 // 判断队列是否为空395 public bool IsNull()396 { 397 //功能:判断是否为空的队列398 return m_List.IsNull();399 }400401 // 清空队列402 public void Clear()403 { 404 //清空链表405 m_List.Clear();406 }407408 // 取得队列的数据个数409 public int QueueCount410 { 411 get412 { 413 //取得队列的个数414 return m_List.ListCount;415 }416 }417 }418 #endregion分享 举报| 171 次阅读 | 1 个评论 上一篇:堆栈与队列的实际应用 下一篇:我是一只灰太狼^_^ CSDN学生大本营 - 联系我们 Powered by UCenter Home 1.5 © 2001-2009 Comsenz Inc.转载地址:http://vxuli.baihongyu.com/