C#数据结构之线性表

一:介绍

线性表是最基本,最简单也是应用最广的数据结构。线性表是线性数据的抽象,其特点是结构中的数据元素之间存在着一对一的线性关系,
是一种数据元素序列的数据结构。

线性表是由n>=0个相同的数据元素构成的有限序列,有限指的是线性表中的数据元素个数是有限的,并且每一个数据元素都有自己的位置。

二:代码实现

1.       线性表的一些通用操作,我们统一为接口:

public interface IListDS<T>
{
        int GetLength();

        void Clear();

        bool IsEmpty();

        void Append(T item);

        void Insert(T item, int i);

        T Delete(int i);

        T GetElem(int i);

        int Locate(T value);

        void Reverse();
}

2.       线性表中常见的有顺序表,单链表,双向链表,循环链表。

3.       顺序表

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text; 

namespace SeqDS

{

    public class SeqList<T>:IListDS<T>

    {

        private int maxsize;//顺序表的容量

        private T[] data;//数组,用于存储顺序表中的数据元素

        private int last;//指示顺序表最后一个元素的位置 

        //索引器

        public T this[int index]

        {

            get { return data[index]; }

            set { data[index] = value; }

        } 

        public int Last

        {

            get { return last; }

        } 

        public int Maxsize

        {

            get{return maxsize;}

            set { maxsize = value; }

        } 

        //构造器

        public SeqList(int size)

        {

            data = new T[size];

            maxsize = size;

            last = -1;

        } 

        //求顺序表的长度

        public int GetLength()

        {

            return last + 1;

        } 

        //清空顺序表

        public void Clear()

        {

            last = -1;

        } 

        //判断顺序表是否为空

        public bool IsEmpty()

        {

            if (last == -1)

                return true;

            else

                return false;

        } 

        //判断顺序表是否为满

        public bool IsFull()

        {

            if (last == maxsize - 1)

                return true;

            else

                return false;

        } 

        //在顺序表的末尾添加新元素

        public void Append(T item)

        {

            if (IsFull())

            {

                Console.WriteLine("List is full");

                return;

            }

            data[++last] = item;

        } 

        //在顺序表的第i个数据元素的位置插入一个数据元素

        public void Insert(T item, int i)

        {

            if (IsFull())

            {

                Console.WriteLine("List is full");

                return;

            }

            if (i < 1 || i > last + 2)

            {

                Console.WriteLine("Position is error!");

                return;

            }

            if (i == last + 2)

            {

                data[last + 1] = item;

            }

            else

            {

                for (int j = last; j > i - 1; --j)

                {

                    data[j + 1] = data[j];

                }

                data[i - 1] = item;

            }

            ++last;

        } 

        //删除顺序表的第i个数据元素

        public T Delete(int i)

        {

            T tmp = default(T);

            if (IsEmpty())

            {

                Console.WriteLine("List is empty!");

                return tmp;

            }

            if (i < 1 || i > last + 1)

            {

                Console.WriteLine("Position is error!");

                return tmp;

            }

            if (i == last + 1)

            {

                tmp = data[last--];

            }

            else

            {

                tmp = data[i - 1];

                for (int j = i; j <= last; ++j)

                {

                    data[j] = data[j + 1];

                }

            }

 

            --last;

            return tmp;

        } 

        //获得顺序表的第i个数据元素

        public T GetElem(int i)

        {

            if (IsEmpty() || (i < 1) || (i > last + 1))

            {

                Console.WriteLine("List is empty or Position is erroe!");

                return default(T);

            }

 

            return data[i - 1];

        } 

        //在顺序表中查找值为value的数据元素

        public int Locate(T value)

        {

            if (IsEmpty())

            {

                Console.WriteLine("List is Empty!");

                return -1;

            }

            int i = 0;

            for (i = 0; i <= last; ++i)

            {

                if (value.Equals(data[i]))

                    break;

            }

            if (i > last)

                return -1;

            return i;

        } 

        public void Reverse()

        {

            T tmp = default(T);

            int length = GetLength();

            for (var i = 0; i < length / 2; i++)

            {

                tmp = data[i];

                data[i] = data[length - i - 1];

                data[length - i - 1] = tmp; 

            }

        } 

    }

}

4.  单向链表 

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text; 

namespace SeqDS

{

    public class LinkList<T>:IListDS<T>

    {

        private Node<T> head;

        public Node<T> Head

        {

            get { return head; }

            set { head = value; }

        } 

        public LinkList()

        {

            head = null;

        } 

        public int GetLength()

        {

            Node<T> p = head;

            int len = 0;

            while (p != null)

            {

                ++len;

                p = p.Next;

            }

            return len;

        } 

        public bool IsEmpty()

        {

            if (head == null)

                return true;

            else

                return false;

        } 

        public void Clear()

        {

            head = null;

        } 

        public void Append(T item)

        {

            Node<T> q = new Node<T>(item);

            Node<T> p=new Node<T>();

            if(head==null)

            {

                head=p;

                return;

            }

            p=head;

            while(p.Next!=null)

            {

                p=p.Next;

            }

            p.Next=q;

        } 

        public void Insert(T item, int i)

        {

            if(IsEmpty()||i<1)

            {

                Console.WriteLine("List is empty or Position is error");

                return;

            } 

            if (i == 1)

            {

                Node<T> q = new Node<T>(item);

                q.Next = head;

                head = q;

                return;

            }

            Node<T> p = head;

            Node<T> r = new Node<T>();

            int j = 1;

            while (p.Next != null && j < i)

            {

                r = p;

                p = p.Next;

                ++j;

            } 

            if (j == i)

            {

                Node<T> q = new Node<T>(item);

                q.Next = p;

                r.Next = q;

            }

        } 

        public void InsertPost(T item, int i)

        {

            if (IsEmpty() || i < 1)

            {

                Console.WriteLine("List is empty or Position is error");

                return;

            }

            if (i == 1)

            {

                Node<T> q = new Node<T>(item);

                q.Next = head.Next;

                head.Next = q;

                return;

            }

            Node<T> p = head;

            int j = 1;

            while (p != null && j < i)

            {

                p = p.Next;

                ++j;

            }

            if (j == i)

            {

                Node<T> q = new Node<T>(item);

                q.Next = p.Next;

                p.Next = q;

            }

        } 

        public T Delete(int i)

        {

            if (IsEmpty() || i < 0)

            {

                Console.WriteLine("Link is empty or Positon is error");

                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 j = 1;

            while (p.Next != null && j < i)

            {

                ++j;

                q = p;

                p = p.Next;

            } 

            if (j == i)

            {

                q.Next = p.Next;

                return p.Data;

            }

            else

            {

                Console.WriteLine("The ith node is not exist!");

                return default(T);

            }

        } 

        public T GetElem(int i)

        {

            if (IsEmpty())

            {

                Console.WriteLine("List is empty");

                return default(T);

            } 

            Node<T> p = new Node<T>();

            p = head;

            int j = 1; 

            while (p.Next != null && j < i)

            {

                ++j;

                p = p.Next;

            }

            if (j == i)

            {

                return p.Data;

            }

            else

            {

                Console.WriteLine("the ith node is not exist!");

                return default(T);

            }

        } 

        public int Locate(T value)

        {

            if (IsEmpty())

            {

                Console.WriteLine("List is Empty");

                return -1;

            }

            Node<T> p = new Node<T>();

            p = head;

            int i = 1;

            while (!p.Data.Equals(value) && p.Next != null)

            {

                p = p.Next; ;

                ++i;

            }

            return i;

        } 

        public void Reverse()

        {

            Node<T> p = head.Next;

            Node<T> q = new Node<T>();

            head.Next = null;

            while (p != null)

            {

                q = p;

                p = p.Next;

                q.Next = head.Next;

                head.Next = q;

            }

        }

    } 

    public class Node<T>

    {

        private T data;//数据域

        private Node<T> next;//引用域

 

        public Node(T val, Node<T> p)

        {

            data = val;

            next = p;

        } 

        public Node(Node<T> p)

        {

            next=p;

        }

        public Node(T val)

        {

            data = val;

            next = null;

        }

        public Node()

        {

            data = default(T);

            next = null;

        } 

        public T Data

        {

            get { return data; }

            set { data = value; }

        }

        public Node<T> Next

        {

            get { return next; }

            set { next = value; }

        }       

    }

}

下面实现两个创建链表的函数如下:

//在头部插入结点建立单链表

        static LinkList<int> CreateListHead()

        {

            int d;

            LinkList<int> l = new LinkList<int>();

            d = Int32.Parse(Console.ReadLine());

            while (d != -1)

            {

                Node<int> p = new Node<int>(d);

                p.Next = l.Head;

                l.Head = p;

                d = Int32.Parse(Console.ReadLine());

            }

            return l;

        } 

        //在尾部插入节点建立单链表

        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;

        } 

5.       双向链表

5.1.双向链表的结点实现如下:

public class DbNode<T>

    {

        private T data;

        private DbNode<T> prev;

        private DbNode<T> next;

 

        public DbNode(T val, DbNode<T> p)

        {

            data = val;

            next = p;

        }

        public DbNode(DbNode<T> p)

        {           

            next = p;

        }

        public DbNode(T val)

        {

            data = val;

            next = null;

        }

        public DbNode()

        {

            data = default(T);

            next = null;

        } 

        public T Data

        {

            get { return data; }

            set { data = value; }

        }

        public DbNode<T> Prev

        {

            get { return prev; }

            set { prev = value; }

        }

        public DbNode<T> Next

        {

            get { return next; }

            set { next = value; }

        }

}

5.2. 插入

由于双向链表的结点有两个引用,所以在双向链表中插入和删除结点比单链表要复杂,双向链表中结点的插入也分前插和后插,例如:设p指向某一结点,即p存储的是结点的地址,现将s插入到p前面,插入过程如下图:

C#数据结构之线性表

对应的操作如下:

p.Next.Prev=s;

s.Prev=p;

s.Next=p.Next;

p.Next=s;

5.3.删除

我们以删除p结点的后面的结点为例,删除过程如下:

C#数据结构之线性表

操作如下:

p.Next=p.Next.Next;

P.Next.Prev=p.Prev;

双向链表的其他操作与单链表相似。


本文转自生鱼片博客园博客,原文链接http://www.cnblogs.com/carysun/archive/2009/09/13/ds-Seq.html,如需转载请自行联系原作者

上一篇:基于MVC4+EasyUI的Web开发框架形成之旅--总体介绍


下一篇:链表的创建和操作