C#实现顺序表(线性表)完整实例

本文实例讲述了C#实现顺序表(线性表)的方法。分享给大家供大家参考,具体如下:

基本思想是使用数组作为盛放元素的容器,数组一开始的大小要实现确定,并使用一个Pointer指向顺序表中最后的元素。顺序表中的元素是数组中元素的子集。顺序表在内存中是连续的,优势是查找,弱势是插入元素和删除元素。

为避免装箱拆箱,这里使用泛型,代替object。使用object的例子可以参照本站这篇文章:http://www.jb51.net/article/87603.htm,这个链接中的例子实现的是队列,并没 有使用Pointer来标识 顺序表中最后一个元素,而是动态的调整数组的大小,这与本例明显不同,动态调整数组大小开销较大。使用object同样可以完成顺序表数据结构,但是频繁装箱拆箱造成较大的开销,应使用泛型代替。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace LinearList
{
  public interface IListDS<T>
  {
    int GetLength();
    void Insert(T item, int i);
    void Add(T item);
    bool IsEmpty();
    T GetElement(int i);
    void Delete(int i);
    void Clear();
    int LocateElement(T item);
    void Reverse();
  }
  //顺序表类
  class SequenceList<T>:IListDS<T>
  {
    private int intMaxSize;//最大容量事先确定,使用数组必须先确定容量
    private T[] tItems;//使用数组盛放元素
    private int intPointerLast;//始终指向最后一个元素的位置
    public int MaxSize
    {
      get { return this.intMaxSize; }
      set { this.intMaxSize = value; }
    }
    public T this[int i]//索引器方便返回
    {
      get { return this.tItems[i]; }
    }
    public int PointerLast
    {
      get { return this.intPointerLast; }
    }
    public SequenceList(int size)
    {
      this.intMaxSize = size;
      this.tItems = new T[size];//在这里初始化最合理
      this.intPointerLast = -1;//初始值设为-1,此时数组中元素个数为0
    }
    public bool IsFull()//判断是否超出容量
    {
      return this.intPointerLast+1 == this.intMaxSize;
    }
    #region IListDS<T> 成员
    public int GetLength()
    {
      return this.intPointerLast + 1;//不能返回tItems的长度
    }
    public void Insert(T item, int i)//设i为第i个元素,从1开始。该函数表示在第i个元素后面插入item
    {
      if (i < 1 || i > this.intPointerLast + 1)
      {
        Console.WriteLine("The inserting location is wrong!");
        return;
      }
      if (this.IsFull())
      {
        Console.WriteLine("This linear list is full! Can't insert any new items!");
        return;
      }
      //如果可以添加
      this.intPointerLast++;
      for(int j=this.intPointerLast;j>=i+1;j--)
      {
        this.tItems[j] = this.tItems[j - 1];
      }
      this.tItems[i] = item;
    }
    public void Add(T item)
    {
      if (this.IsFull())//如果超出最大容量,则无法添加新元素
      {
        Console.WriteLine("This linear list is full! Can't add any new items!");
      }
      else
      {
        this.tItems[++this.intPointerLast] = item;//表长+1
      }
    }
    public bool IsEmpty()
    {
      return this.intPointerLast == -1;
    }
    public T GetElement(int i)//设i最小从0开始
    {
      if(this.intPointerLast == -1)
      {
        Console.WriteLine("There are no elements in this linear list!");
        return default(T);
      }
      if (i > this.intPointerLast||i<0)
      {
        Console.WriteLine("Exceed the capability!");
        return default(T);
      }
      return this.tItems[i];
    }
    public void Delete(int i)//设i最小从0开始
    {
      if (this.intPointerLast == -1)
      {
        Console.WriteLine("There are no elements in this linear list!");
        return;
      }
      if (i > this.intPointerLast || i < 0)
      {
        Console.WriteLine("Deleting location is wrong!");
        return;
      }
      for (int j = i; j < this.intPointerLast; j++)
      {
        this.tItems[j] = this.tItems[j + 1];
      }
      this.intPointerLast--;//表长-1
    }
    public void Clear()
    {
      this.intPointerLast = -1;
    }
    public int LocateElement(T item)
    {
      if (this.intPointerLast == -1)
      {
        Console.WriteLine("There are no items in the list!");
        return -1;
      }
      for (int i = 0; i <= this.intPointerLast; i++)
      {
        if (this.tItems[i].Equals(item))//若是自定义类型,则T类必须把Equals函数override
        {
          return i;
        }
      }
      Console.WriteLine("Not found");
      return -1;
    }
    public void Reverse()
    {
      if (this.intPointerLast == -1)
      {
        Console.WriteLine("There are no items in the list!");
      }
      else
      {
        int i = 0;
        int j = this.GetLength() / 2;//结果为下界整数,正好用于循环
        while (i < j)
        {
          T tmp = this.tItems[i];
          this.tItems[i] = this.tItems[this.intPointerLast - i];
          this.tItems[this.intPointerLast - i] = tmp;
          i++;
        }
      }
    }
    #endregion
  }
  class Program
  {
    static void Main(string[] args)
    {
    }
  }
}

基于顺序表的合并排序:

//基于顺序表的合并排序
static private SequenceList<int> Merge(SequenceList<int> s1,SequenceList<int> s2)
{
  SequenceList<int> sList = new SequenceList<int>(20);
  int i = 0;
  int j = 0;
  while(i<=s1.PointerLast&&j<=s2.PointerLast)
  {
    if (s1[i] < s2[j])
    {
      sList.Add(s1[i]);
      i++;
    }
    else
    {
      sList.Add(s2[j]);
      j++;
    }
  }
  if (i > s1.PointerLast)
  {
    while (j <= s2.PointerLast)
    {
      sList.Add(s2[j]);
      j++;
    }
    return sList;
  }
  else//即j>s2.PointerLast
  {
    while (i <= s1.PointerLast)
    {
      sList.Add(s1[i]);
      i++;
    }
    return sList;
  }
}

更多关于C#相关内容感兴趣的读者可查看本站专题:《C#数据结构与算法教程》、《C#遍历算法与技巧总结》、《C#程序设计之线程使用技巧总结》、《C#操作Excel技巧总结》、《C#中XML文件操作技巧汇总》、《C#常见控件用法教程》、《WinForm控件用法总结》、《C#数组操作技巧总结》及《C#面向对象程序设计入门教程》

希望本文所述对大家C#程序设计有所帮助。

时间: 2016-06-27

C#常用数据结构和算法总结

1.数据 数据(Data)是外部世界信息的载体, 是能够被计算机识别,加工,存储的.在现实生活中也就是我们的产品原材料. 计算机中的数据包括数值数据,图片,影音资料等. 2. 数据元素和数据项 数据元素(Data Element)是数据的基本单位,在计算机处理的过程中通常是作为一个整体来作为处理的. 数据项(Data Item):一个数据元素通常由一个或多个数据项组成. 比如数据库表:(Student),它有Id,Name,Sex,Age,Address等字段,而这张表又有多行数据.我们通常将这

C#数据结构与算法揭秘二 线性结构

上文对数据结构与算法,有了一个简单的概述与介绍,这篇文章,我们介绍一中典型数据结构--线性结构. 什么是线性结构,线性结构是最简单.最基本.最常用的数据结构.线性表是线性结构的抽象(Abstract), 线性结构的特点是结构中的数据元素之间存在一对一的线性关系. 这 种一对一的关系指的是数据元素之间的位置关系,即: (1)除第一个位置的数据元素外,其它数据元素位置的前面都只有一个数据元素: (2)除最后一个位置的数据元素外,其它数据元素位置的后面都只有一个元素.也就是说,数据元素是一个接一个的排

C#数据结构与算法揭秘三 链表

上文我们讨论了一种最简单的线性结构--顺序表,这节我们要讨论另一种线性结构--链表. 什么是链表了,不要求逻辑上相邻的数据元素在物理存储位置上也相邻存储的线性结构称之为链表.举个现实中的例子吧,假如一个公司召开了视频会议的吧,能在北京总公司人看到上海分公司的人,他们就好比是逻辑上相邻的数据元素,而物理上不相连.这样就好比是个链表. 链表分为①单链表,②单向循环链表,③双向链表,④双向循环链表. 介绍各种各样链表之前,我们要明白这样一个概念.什么是结点.在存储数据元素时,除了存储数据元素本身的信息

C#数据结构与算法揭秘二

上文对数据结构与算法,有了一个简单的概述与介绍,这篇文章,我们介绍一中典型数据结构--线性结构. 什么是线性结构,线性结构是最简单.最基本.最常用的数据结构.线性表是线性结构的抽象(Abstract), 线性结构的特点是结构中的数据元素之间存在一对一的线性关系. 这 种一对一的关系指的是数据元素之间的位置关系,即: (1)除第一个位置的数据元素外,其它数据元素位置的前面都只有一个数据元素: (2)除最后一个位置的数据元素外,其它数据元素位置的后面都只有一个元素.也就是说,数据元素是一个接一个的排

C#数据结构之顺序表(SeqList)实例详解

本文实例讲述了C#数据结构之顺序表(SeqList)实现方法.分享给大家供大家参考,具体如下: 线性结构(Linear Stucture)是数据结构(Data Structure)中最基本的结构,其特征用图形表示如下: 即:每个元素前面有且只有一个元素(称为"前驱"),同样后面有且只有一个元素(称为"后继")--注:起始元素的前驱认为是空,末尾元素的后继认为也是空,这样在概念上就不冲突了. 线性表(List)是线性结构的一种典型实现,它又可以分为:顺序表(SeqLi

C#数据结构与算法揭秘一

这里,我们 来说一说C#的数据结构了. ①什么是数据结构.数据结构,字面意思就是研究数据的方法,就是研究数据如何在程序中组织的一种方法.数据结构就是相互之间存在一种或多种特定关系的数据元素的集合. 程序界有一点很经典的话,程序设计=数据结构+算法.用源代码来体现,数据结构,就是编程.他有哪些具体的关系了, (1) 集合(Set):如图 1.1(a)所示,该结构中的数据元素除了存在"同属于一个集合"的关系外,不存在任何其它关系. 集合与数学的集合类似,有无序性,唯一性,确定性. (2)

c#泛型学习详解 创建线性链表

术语表 generics:泛型type-safe:类型安全collection: 集合compiler:编译器run time:程序运行时object: 对象.NET library:.Net类库value type: 值类型box: 装箱unbox: 拆箱implicity: 隐式explicity: 显式linked list: 线性链表node: 结点indexer: 索引器 泛型是什么? 很多人觉得泛型很难理解.我相信这是因为他们通常在了解泛型是用来解决什么问题之前,就被灌输了大量的理论

C#数据结构与算法揭秘四 双向链表

首先,明白什么是双向链表.所谓双向链表是如果希望找直接前驱结点和直接后继结点的时间复杂度都是 O(1),那么,需要在结点中设两个引用域,一个保存直接前驱结点的地址,叫 prev,一个直接后继结点的地址,叫 next,这样的链表就是双向链表(Doubly Linked List).双向链表的结点结构示意图如图所示. 双向链表结点的定义与单链表的结点的定义很相似, ,只是双向链表多了一个字段 prev.其实,双向链表更像是一根链条一样,你连我,我连你,不清楚,请看图. 双向链表结点类的实现如下所示

C#模拟链表数据结构的实例解析

写在前面 模块化编程是大多数初学者必经之路,然后可能你走向了结构化编程,链表是一种典型结构模式,它的出现克服了数组必须预先知道大小的缺陷,听不懂?你只需要记住,链表结构非常牛叉就可以了,学习这种结构对我们的逻辑思维有很大提升. 什么是链表结构呢? 链表是一种物理存储单元上非连续.非顺序的存储结构.比如A->B->C,这种结构,我们可以理解为A连接着B,B连接C,像这种结构我们就叫做链表结构.对了,火车的车厢,其实就是链表的结构的最好说明 为什么要有链表结构呢? 学过计算机的都知道数组(Arra

C#数据结构与算法揭秘五 栈和队列

这节我们讨论了两种好玩的数据结构,栈和队列. 老样子,什么是栈, 所谓的栈是栈(Stack)是操作限定在表的尾端进行的线性表.表尾由于要进行插入.删除等操作,所以,它具有特殊的含义,把表尾称为栈顶(Top) ,另一端是固定的,叫栈底(Bottom) .当栈中没有数据元素时叫空栈(Empty Stack).这个类似于送饭的饭盒子,上层放的是红烧肉,中层放的水煮鱼,下层放的鸡腿.你要把这些菜取出来,这就引出来了栈的特点先进后出(First in last out).   具体叙述,加下图. 栈通常记

C#数据结构之双向链表(DbLinkList)实例详解

本文实例讲述了C#数据结构之双向链表(DbLinkList).分享给大家供大家参考,具体如下: 这是继上一篇<C#数据结构之单链表(LinkList)实例详解>的继续,对于双向链接,节点上除了Next属性外,还要有Prev属性用来指向前一个节点,DbNode定义如下: namespace 线性表 { public class DbNode<T> { private T data; private DbNode<T> prev; private DbNode<T&g

C#数据结构之循环链表的实例代码

复制代码 代码如下: public class Node    {        public object Element;        public Node Link; public Node()        {            Element = null;            Link = null;        } public Node(object theElement)        {            Element = theElement;      

C#数据结构之单链表(LinkList)实例详解

本文实例讲述了C#数据结构之单链表(LinkList)实现方法.分享给大家供大家参考,具体如下: 这里我们来看下"单链表(LinkList)".在上一篇<C#数据结构之顺序表(SeqList)实例详解>的最后,我们指出了:顺序表要求开辟一组连续的内存空间,而且插入/删除元素时,为了保证元素的顺序性,必须对后面的元素进行移动.如果你的应用中需要频繁对元素进行插入/删除,那么开销会很大. 而链表结构正好相反,先来看下结构: 每个元素至少具有二个属性:data和next.data

javascript数据结构之双链表插入排序实例详解

本文实例讲述了javascript数据结构之双链表插入排序实现方法.分享给大家供大家参考,具体如下: 数组存储前提下,插入排序算法,在最坏情况下,前面的元素需要不断向后移,以便在插入点留出空位,让目标元素插入. 换成链表时,显然无需做这种大量移动,根据每个节点的前驱节点"指针",向前找到插入点后,直接把目标值从原链表上摘下,然后在插入点把链表断成二截,然后跟目标点重新接起来即可. <!doctype html> <html> <head> <t

C++ 单链表的基本操作(详解)

链表一直是面试的高频题,今天先总结一下单链表的使用,下节再总结双向链表的.本文主要有单链表的创建.插入.删除节点等. 1.概念 单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素. 链表中的数据是以结点来表示的,每个结点的构成:元素 + 指针,元素就是存储数据的存储单元,指针就是连接每个结点的地址数据.如下图: 2.链表的基本操作 SingleList.cpp: #include "stdafx.h" #include "SingleList.h&

jQuery表单插件ajaxForm实例详解

前端时间写项目用到了ajaxForm这个插件,可以用它提交表单和上传图片,听起来和正常的form表单提交没什么区别,只不过是ajax提交,无需刷新页面,如此可以增加用户体验度. 引入两个文件,PS:必须 <script type="text/javascript" src="http://img9.tongzhuo100.com/js/jquery-1.7.2.min.js"></script> <script type="t

java 设计模式之单例的实例详解

java 设计模式之单例的实例详解 设计模式思想 什么是设计模式:我作为初学者,今天第一次正式学习设计模式,我觉得对与理解什么是设计模式很重要,那么什么是设计模式呢? 设计模式:解决问题的一种行之有效的思想. 设计模式:用于解决特定环境下.重复出现的特定问题的解决方案 我的理解是前人在软件设计的时候碰到了一类问题,他们总结出了一套行之有效,并且经过验证的解决方案. 设计模式的优点: 1.设计模式都是一些相对优秀的解决方案,很多问题都是典型的.有代表性的问题,学习设计模式,我们就不用自己从头来解决

C语言数据结构之图的遍历实例详解

C语言数据结构之图的遍历实例详解 输入一组顶点,建立无向图的邻接矩阵.输入一组顶点,建立有向图的邻接表.分别对无向图和有向图进行DFS(深度优先遍历)和BFS(广度优先遍历).写出深度优先遍历的递归和非递归算法.根据建立的有向图,判断该图是否是有向无环图,若是,则输出其一种拓扑有序序列. 实现代码: #include <stdio.h> #include <stdlib.h> #define MAX 20 typedef struct ArcNode{ int adjvex; st

JAVA 静态的单例的实例详解

JAVA  静态的单例的实例详解 实现代码: public class Printer { private Printer(){ } public static Printer newInstance(){ return CreatePrinter.mPrinter; } private static class CreatePrinter{ private final static Printer mPrinter = new Printer(); } } 因为静态的单例对象没有作为类的成员变

深入单链表的快速排序详解

单链表的快排序和数组的快排序基本思想相同,同样是基于划分,但是又有很大的不同:单链表不支持基于下标的访问.故书中把待排序的链表拆分为2个子链表.为了简单起见,选择链表的第一个节点作为基准,然后进行比较,比基准小得节点放入左面的子链表,比基准大的放入右边的子链表.在对待排序链表扫描一遍之后,左边子链表的节点值都小于基准的值,右边子链表的值都大于基准的值,然后把基准插入到链表中,并作为连接两个子链表的桥梁.然后分别对左.右两个子链表进行递归快速排序,以提高性能.但是,由于单链表不能像数组那样随机存储

AngularJS学习笔记之表单验证功能实例详解

本文实例讲述了AngularJS学习笔记之表单验证功能.分享给大家供大家参考,具体如下: 一.执行基本的表单验证 <!DOCTYPE html> <html ng-app='exampleApp'> <head> <meta charset="UTF-8"> <title>表单</title> <script src="../../js/angular.min.js" type="