C Implementation Sequence Table of Linear Table Complete Example

  • 2021-10-24 23:35:44
  • OfStack

In this paper, an example is given to describe the method of implementing sequential table (linear table) in C #. Share it for your reference, as follows:

The basic idea is to use an array as a container for the elements, determine the size of Array 1 at the beginning, and point to the last element in the order table with an Pointer. Elements in a sequential table are subsets of elements in an array. Sequence tables are continuous in memory, with the advantage of finding and the disadvantage of inserting and deleting elements.

To avoid packing and unpacking, generics are used here instead of object. The example of using object can refer to this article on this site: https://www. ofstack. com/article/87603. htm. The example in this link implements the queue, and does not use Pointer to identify the last element in the sequence table, but dynamically adjusts the size of the array, which is obviously different from this example, and dynamically adjusts the size of the array. Sequential table data structures can also be accomplished using object, but frequent packing and unpacking is costly and should be replaced by generics.


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();
  }
  // Sequential table class 
  class SequenceList<T>:IListDS<T>
  {
    private int intMaxSize;// The maximum capacity is determined in advance, and the capacity must be determined before using arrays 
    private T[] tItems;// Use arrays to hold elements 
    private int intPointerLast;// Always point to the last 1 Position of elements 
    public int MaxSize
    {
      get { return this.intMaxSize; }
      set { this.intMaxSize = value; }
    }
    public T this[int i]// The indexer is easy to return 
    {
      get { return this.tItems[i]; }
    }
    public int PointerLast
    {
      get { return this.intPointerLast; }
    }
    public SequenceList(int size)
    {
      this.intMaxSize = size;
      this.tItems = new T[size];// Initialization is the most reasonable here 
      this.intPointerLast = -1;// The initial value is set to -1 When the number of elements in the array is 0
    }
    public bool IsFull()// Determine whether the capacity is exceeded 
    {
      return this.intPointerLast+1 == this.intMaxSize;
    }
    #region IListDS<T>  Member 
    public int GetLength()
    {
      return this.intPointerLast + 1;// Cannot return tItems The length of 
    }
    public void Insert(T item, int i)// Set i Be the first i Elements from the 1 Here we go. This function is represented in the first i Insert after the element 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;
      }
      // If you can add 
      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())// If the maximum capacity is exceeded, new elements cannot be added 
      {
        Console.WriteLine("This linear list is full! Can't add any new items!");
      }
      else
      {
        this.tItems[++this.intPointerLast] = item;// Watch length +1
      }
    }
    public bool IsEmpty()
    {
      return this.intPointerLast == -1;
    }
    public T GetElement(int i)// Set i Minimum slave 0 Begin 
    {
      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)// Set i Minimum slave 0 Begin 
    {
      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--;// Watch length -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))// If it is a custom type, the T Class must put Equals Function 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;// The result is a lower bound integer, which is exactly used for loop 
        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)
    {
    }
  }
}

Merge sorting based on sequence table:


// Merge Sorting Based on Sequence Table 
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// I.e. j>s2.PointerLast
  {
    while (i <= s1.PointerLast)
    {
      sList.Add(s1[i]);
      i++;
    }
    return sList;
  }
}

More readers interested in C # can check the topic of this site: "C # data structure and algorithm tutorial", "C # traversal algorithm and skills summary", "C # programming thread use skills summary", "C # operation Excel skills summary", "C # XML file operation skills summary", "C # common control usage tutorial", "WinForm control usage summary", "C # array operation skills summary" and "C # object-oriented programming introduction tutorial"

I hope this article is helpful to everyone's C # programming.


Related articles: