数据结构C#版笔记--顺序表(SeqList)

时间：2014-05-30 00:58:21 阅读：464 评论：0 收藏：0 [点我收藏+]

线性结构(Linear Stucture)是数据结构(Data Structure)中最基本的结构，其特征用图形表示如下：

bubuko.com,布布扣

即：每个元素前面有且只有一个元素(称为“前驱”)，同样后面有且只有一个元素(称为"后继")--注：起始元素的前驱认为是空，末尾元素的后继认为也是空，这样在概念上就不冲突了。

线性表(List)是线性结构的一种典型实现，它又可以分为：顺序表(SeqList)和链表(LinkList)二大类.

顺序表（SeqList）的基本特征为：元素在内部存储时是一个接一个在存储单元中按顺序存储的，所以只要知道"起始元素的存储地址"-- 称为顺序表的基地址(Base Address)以及顺序表中任何元素的位置(即它是第几个元素)，就能直接定位到该元素的地址，从而直接访问到该元素的值。也就是说存储/读取每个元素所用的时间是相同的，即所谓的“随机存取”

C#语言中数组(Array)在内存中占用的就是一组连续的存储区域，所以用数组来实现顺序表再适用不过。

先来定义线性表的通用接口IListDS.cs(注：DS为DataStructure的缩写)

  
    
    namespace 
线性表
{
    public 
interface IListDS<T>
    {
        //取得线性表的实际元素个数
        int 
Count();
 
        //清空线性表
        void 
Clear();
 
        //判断线性表是否为空
        bool 
IsEmpty();
 
        //（在末端）追加元素
        void 
Append(T item);
 
        //在位置i“前面”插入元素item
        void 
InsertBefore(T item, int 
i);
 
        //在位置i“后面”插入元素item
        void 
InsertAfter(T item, int 
i);
 
        //删除索引i处的元素
        T RemoveAt(int 
i);
 
        //获得索引位置i处的元素
        T GetItemAt(int 
i);
 
        //返回元素value的索引
        int 
IndexOf(T value);
 
        //反转线性表的所有元素
        void 
Reverse();
    }
}

顺序表(SeqList)的实现：

  
    
    using 
System;
using 
System.Text;
 
namespace 
线性表
{
    /// <summary>
    /// 顺序表
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public 
class SeqList<T> : IListDS<T>
    {
        private 
int maxsize;
        private 
T[] data;
        private 
int last;
 
        //类索引器
        public 
T this[int 
index]
        {
            get
            {
                return 
this.GetItemAt(index);
            }
            set
            {
                if 
(index < 0 || index > last + 1)
                {
                    Console.WriteLine("Position is error");
                    return;
                }
                data[index] = value;
            }
        }
 
        //最后一个元素的下标
        public 
int Last
        {
            get 
{ return 
last; }
        }
 
        //最大容量
        public 
int Maxsize
        {
            get 
{ return 
this.maxsize; }
            set 
{ this.maxsize = value; }
        }
 
        //构造函数
        public 
SeqList(int 
size)
        {
            data = new 
T[size];
            maxsize = size;
            last = -1;
        }
 
        //返回链表的实际长度
        public 
int Count()
        {
            return 
last + 1;
        }
 
        //清空
        public 
void Clear()
        {
            last = -1;
        }
 
        //是否空
        public 
bool IsEmpty()
        {
            return 
last == -1;
        }
 
        //是否满
        public 
bool IsFull()
        {
            return 
last == maxsize - 1;
        }
 
        //(在最后位置)追加元素
        public 
void Append(T item)
        {
            if 
(IsFull())
            {
                Console.WriteLine("List is full");
                return;
            }
            data[++last] = item;
        }
 
        /// <summary>
        ///前插
        /// </summary>
        /// <param name="item">要插入的元素</param>
        /// <param name="i">要插入的位置索引</param>
        public 
void InsertBefore(T item, int 
i)
        {
            if 
(IsFull())
            {
                Console.WriteLine("List is full");
                return;
            }
 
            if 
(i < 0 || i > last + 1)
            {
                Console.WriteLine("Position is error");
                return;
            }
 
            if 
(i == last + 1)
            {
                data[last + 1] = item;
            }
            else
            {
                //位置i及i以后的元素，全部后移
                for 
(int 
j = last; j >= i; j--)
                {
                    data[j + 1] = data[j];
                }
                data[i] = item;
            }
            ++last;
        }
 
        /// <summary>
        /// 后插
        /// </summary>
        /// <param name="item"></param>
        /// <param name="i"></param>
        public 
void InsertAfter(T item, int 
i) 
        {
            if 
(IsFull())
            {
                Console.WriteLine("List is full");
                return;
            }
 
            if 
(i < 0 || i > last)
            {
                Console.WriteLine("Position is error");
                return;
            }
 
            if 
(i == last)
            {
                data[last + 1] = item;
            }
            else
            {
                //位置i以后的元素(不含位置i)，全部后移
                for 
(int 
j = last; j > i; j--)
                {
                    data[j + 1] = data[j];
                }
                data[i+1] = item;
            }
            ++last;
        }
 
        /// <summary>
        /// 删除元素
        /// </summary>
        /// <param name="i">要删除的元素索引</param>
        /// <returns></returns>
        public 
T RemoveAt(int 
i)
        {
            T tmp = default(T);
            if 
(IsEmpty())
            {
                Console.WriteLine("List is empty");
                return 
tmp;
            }
 
            if 
(i < 0 || i > last)
            {
                Console.WriteLine("Position is error!");
                return 
tmp;
            }
 
            if 
(i == last)
            {
                tmp = data[last];
            }
            else
            {
                tmp = data[i];
                //位置i以及i以后的元素前移
                for 
(int 
j = i; j <= last; j++)
                {
                    data[j] = data[j + 1];
                }
            }
            --last;
            return 
tmp;
        }
 
        /// <summary>
        /// 获取第几个位置的元素
        /// </summary>
        /// <param name="i">第几个位置</param>
        /// <returns></returns>
        public 
T GetItemAt(int 
i)
        {
            if 
(IsEmpty() || (i < 0) || (i > last))
            {
                Console.WriteLine("List is empty or Position is error!");
                return 
default(T);
            }
            return 
data[i];
        }
 
        /// <summary>
        /// 定位元素的下标索引
        /// </summary>
        /// <param name="value"></param>
        /// <returns></returns>
        public 
int IndexOf(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;
        }
 
        /// <summary>
        /// 元素反转
        /// </summary>
        public 
void Reverse()
        {
            T tmp = default(T);
            for 
(int 
i = 0; i <= last / 2; i++)
            {
                tmp = data[i];
                data[i] = data[last-i];
                data[last-i] = tmp;
            }
        }
 
        public 
override string ToString()
        {
            StringBuilder sb = new 
StringBuilder();
            for 
(int 
i = 0; i <= last; i++)
            {
                sb.Append(data[i].ToString() + "，");
            }
            return 
sb.ToString().TrimEnd(‘，‘);
        }
    }
}

测试代码片段：

  
    
    Console.WriteLine("顺序表测试开始...");
SeqList<string> seq = new 
SeqList<string>(10);
 
seq.Append("x");
seq.InsertBefore("w", 0);
seq.InsertBefore("v", 0);
seq.Append("y");
seq.InsertBefore("z", seq.Count());
Console.WriteLine(seq.Count());//5
Console.WriteLine(seq.ToString());//v,w,x,y,z
Console.WriteLine(seq[1]);//w
Console.WriteLine(seq[0]);//v
Console.WriteLine(seq[4]);//z
Console.WriteLine(seq.IndexOf("z"));//4
Console.WriteLine(seq.RemoveAt(2));//x
Console.WriteLine(seq.ToString());//v,w,y,z
seq.InsertBefore("x", 2);           
Console.WriteLine(seq.ToString());//v,w,x,y,z
Console.WriteLine(seq.GetItemAt(2));//x
seq.Reverse();
Console.WriteLine(seq.ToString());//z,y,x,w,v
 
seq.InsertAfter("z_1", 0);
seq.InsertAfter("y_1", 2);
seq.InsertAfter("v_1", seq.Count()-1);
Console.WriteLine(seq.ToString());//z，z_1，y，y_1，x，w，v，v_1

顺序表的优点：读取元素时可直接定位，所以在某些操作(比如将顺序表元素反转合围)中，不需要完全遍历，循环次数(即时间复杂度)相对完全遍历而言能减少一半。

顺序表的优点：插入/删除元素，因为要保持其顺序性，所以后续元素需要移动，增加了时间开销。

最后指出：.Net命名空间System.Collections.Generic中的List<T>就是一个内置的顺序表.

数据结构C#版笔记--顺序表(SeqList),布布扣,bubuko.com

数据结构C#版笔记--顺序表(SeqList)

原文：http://www.cnblogs.com/lxclqy/p/3758003.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)