单链表是线性表中的一种，它由两部分组成，一个是数据域存储数据元素信息，另一个是引用域存储下一个结点的地址。那么单链表的优点是快速插入和删除，元素比较多时遍历的话速度比较慢。在具体开发中，怎么平衡效率那就具体分析吧。
具体在游戏中的应用，比如说<合金弹头>里的子弹，一般一把枪里有30到50发，打完就没了，遍历的话基本用不上，所以我们可以用单链表，当然用栈是不是更简单呢，后续讨论栈时再说
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace 数据结构Linked_List { class Node<T> { T data;// 数据域 public T Data { get { return data; } set { data = value; } } Node<T> next;// 引用域 internal Node<T> Next { get { return next; } set { next = value; } } // 构造器 public Node(T value, Node<T> p) { data = value; next = p; } // 构造器重载便于扩展 public Node(T value) { data = value; next = null; } public Node(Node<T> p) { next = p; } public Node() { data = default(T); next = null; } } }
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace 数据结构Linked_List { // 把单链表看作是一个类，类名叫LinkList<T>。 class LinkList<T> { // 方法一 这是一个动态数组 public int Count { get; private set; } static int capacity = 4; T[] num = new T[capacity]; T[] temp = new T[capacity]; // 这里说明一下这是T[]数组的索引器 public T this[int index] { get { return num[index]; } set { num[index] = value; } } //这里添加动态添加 T 类型的值 public void Add(T value) { if (Count < capacity) this.num[Count++] = value; else { capacity = capacity << 1; temp = new T[capacity]; for (int i = 0; i < Count; i++) { temp[i] = this.num[i]; } temp[Count] = value; num = temp; } } public void Display() { if (num != null) { foreach (T x in num) { Console.WriteLine(x); } } } // 方法2 Node<T> head; //单链表的头引用 internal Node<T> Head { get { return head; } set { head = value; } } //public Node<T> this[int index] //{ // get { return nodeNum[index]; } // set { nodeNum[index] = value; } //} public LinkList() { head = null; } // 单链表的长度 public int GetLength() { Node<T> p = head; int len = 0; while ( p != null ) { p = p.Next;// p指向下一个元素 len++; } return len; } public bool IsEmpty( ) { if ( null == head ) { return true; } return false; } public void Clear() { head = null; } public void AppEnd( T item) { Node<T> p = new Node<T>(item); Node<T> q = new Node<T>( ); // 是否为空链表 if ( IsEmpty() ) { head = p; } else { q = head; while ( q != null ) { q = q.Next; } q.Next = p;//将添加的元素放在最后 } }// 在单链表的第i个结点的位置前插入一个值为item的结点 public void Insert(T item, int i) { if ( IsEmpty() || i < 0 ) { Console.WriteLine("位置非法"); return; } // 判断i是不是第一个为置 if ( 1 == i ) { Node<T> q = new Node<T>(item); q.Next = head; head = q;// 将q设置为头结点 return; } Node<T> p = head; Node<T> r = new Node<T>();// 和p同步移动，保存p的位置 int nCount = 1; while (p != null) { r = p; p = p.Next; if (nCount++ == i) { Node<T> q = new Node<T>(item); q.Next = p; r.Next = q;// 确保q前面的数据时相连的 return; } } }
// 在单链表的第i个结点的位置后插入一个值为item的结点 public void InsertPost(T item, int i) { if (IsEmpty() || i < 1) { Console.WriteLine("链表为空或位置非法"); return; } if (i == 1) { Node<T> q = new Node<T>(item); q.Next = head.Next; head.Next = q; return; } Node<T> p = head; int nCount = 1; while (p.Next != null) { p = p.Next; if (++nCount == i) { Node<T> q = new Node<T>(item); q.Next = p.Next; p.Next = q; return; } } Console.WriteLine("i的位置非法"); } //删除单链表的第i个结点 public T Delete(int i) { if (IsEmpty()|| i < 0) { Console.WriteLine("链表为空或位置非法"); return default(T); } Node<T> q = new Node<T>(); if (i == 1) { q = head; head = head.Next; return q.Data; } Node<T> p = head; int nCount = 1; while (p.Next != null) { q = p; p = p.Next; if (++nCount == i) { q.Next = p.Next; return p.Data; } } Console.WriteLine("没有找到下标为i的结点"); return default(T); } //获得单链表的第i个数据元素 public T GetElem(int i) { if (IsEmpty()) { Console.WriteLine("链表为空"); return default(T); } Node<T> p = new Node<T>(); p = head; int nCount = 1; while ( p.Next != null ) { p = p.Next; if (++nCount == i) { return p.Data; } } Console.WriteLine("没有找到下标为i的结点"); return default(T); } //在单链表中查找值为value的结点 public int Locate(T value) { if( IsEmpty() ) { Console.WriteLine("链表为空"); return -1; } Node<T> p = new Node<T>(); p = head; int nCount = 0;// 下标 while (!p.Data.Equals(value)&& p.Next != null) { p = p.Next; ++nCount; } return nCount; } } }
下边是测试代码
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace 数据结构Linked_List { class Program { static void Main(string[] args) { Node<int> bullet = new Node<int>(1); LinkList<int> iList = new LinkList<int> (); LinkList<string> sList = new LinkList<string>(); //sList.Add("123"); //sList.Add("4"); //sList.Add("56"); //sList.Add("78"); //sList.Display( ); iList = CreateListTail(); iList.Insert(99, 3); iList.InsertPost(88,5); ShowList(iList); Console.WriteLine("找到数据下标是" + iList.Locate(99)); Console.ReadLine(); } public static LinkList<int> CreateListTail( ) { Node<int> R = new Node<int>(); int d; LinkList<int> L = new LinkList<int>(); R = L.Head; d = Int32.Parse(Console.ReadLine()); while (d != -1) { Node<int> p = new Node<int>(d); if (L.Head == null) { L.Head = p; } else { R.Next = p; } R = p; d = Int32.Parse(Console.ReadLine()); } if (R != null) { R.Next = null; } return L; } public static void ShowList( LinkList<int> _head ) { Node<int> p = _head.Head; while ( p != null ) { Console.WriteLine(p.Data); p = p.Next; } } } }
今天有点迟了，大家可以直接做一个子弹类，将其作为数据放入链表中，话说回来，可以直接使用c#写好的List<> 或者ArrayList，把子弹类放进去就可以。 双链表就不讲了，c#的LinkedList。看看使用函数。明天继续讲解栈和队列。