C# 線性表之順序存儲結構

2019-11-08 18:36:53

字體：大中小

來源：轉載

供稿：網友

前言

畢業大半年了，發現自己在數據結構與算法這一塊的知識不扎實，所以重新回顧一下大學學的知識并且做一些筆記。謝謝大家。

舉例

白羊座，金牛座，雙子座，巨蟹座，獅子座，處女座，天秤座，天蝎座，射手座，摩羯座，水瓶座，雙魚座，12個星座是按順序排列的，都有自己固定的位置，除了第一個白羊座沒有前驅，和最后一個雙魚座沒有后驅，其他的都有前驅和后驅。

定義

線性表可以說是最簡單的數據結構，它的描述為：n個數據元素的有限序列。記為：L=(a1,a2,…,an)，順序存儲結構是用一段連續地址依次存儲線性表中的數據元素。

interface

我們先來定義一個線性表接口，

namespace 線性表{ public interface IListDS<T> { int GetLength();//去長度 void Clear();//清空 bool IsEmpty();//是否為空 bool IsFull();//是否越界 void Append(T item);//添加 void Insert(T item, int index);//插入 T Delete(int index);//刪除 T GetElem(int index);//通過索引獲取值 int Locate(T value); //按值查找。 void Reverse(); //倒置 }}

順序存儲結構

namespace 線性表{ public class SeqList<T>:IListDS<T> { PRivate int maxSize; //數組大小 private T[] date; //數組 private int last; //最后一個索引 } }

添加

public void Append(T item) { if (IsFull()) { Console.WriteLine("List is full!"); return; } date[last++] = item; }

插入

public void Insert(T item, int index) { if (IsFull()) { Console.WriteLine("List is full"); return; } if (index < 0 || index > last) { Console.WriteLine("Position is error!"); return; } for (int i = last; i >= index; i--) { date[i + 1] = date[i]; } date[index] = item; last++; }

刪除

public T Delete(int index) { T temp = default(T); if (IsEmpty()) { Console.WriteLine("List is empty!"); return temp; } if (index < 0 || index > last) { Console.WriteLine("Position is error!"); return temp; } for (int i = index; i < last; i++) { date[i] = date[i + 1]; } last--; return temp; }

獲取元素

public T GetElem(int index) { if (IsEmpty() || index > last || index < 0) { Console.WriteLine("List is empty or Position is error!"); return default(T); } return date[index]; }

更多詳細代碼

using System;namespace 線性表{ public class SeqList<T>:IListDS<T> { private int maxSize; private T[] date; private int last; /// <summary> /// 索引器 /// </summary> /// <param name="index"></param> /// <returns></returns> public T this[int index] { get { return date[index]; } set { date[index] = value; } } public int Last { get { return last; } } public int MaxSize { get { return maxSize; } set { maxSize = value; } } public SeqList(int size) { date = new T[size]; maxSize = size; last = 0; } public int GetLength() { return last; } public void Clear() { last = 0; } public bool IsEmpty() { bool _isEmpty = last == 0 ? true : false; return _isEmpty; } public bool IsFull() { bool _isFull = last == maxSize ? true : false; return _isFull; } public void Append(T item) { if (IsFull()) { Console.WriteLine("List is full!"); return; } date[last++] = item; } public void Insert(T item, int index) { if (IsFull()) { Console.WriteLine("List is full"); return; } if (index < 0 || index > last) { Console.WriteLine("Position is error!"); return; } for (int i = last; i >= index; i--) { date[i + 1] = date[i]; } date[index] = item; last++; } public T Delete(int index) { T temp = default(T); if (IsEmpty()) { Console.WriteLine("List is empty!"); return temp; } if (index < 0 || index > last) { Console.WriteLine("Position is error!"); return temp; } for (int i = index; i < last; i++) { date[i] = date[i + 1]; } last--; return temp; } public T GetElem(int index) { if (IsEmpty() || index > last || index < 0) { Console.WriteLine("List is empty or Position is error!"); return default(T); } return date[index]; } public int Locate(T value) { if (IsEmpty()) { Console.WriteLine("List is empty!"); return -1; } int i; for (i = 0; i < last; i++) { if(value.Equals(date[i])) break; } if (i >= last) return -1; return i; } public void Reverse() { T temp = default(T); int _len = GetLength() - 1; for (int i = 0; i <= _len/2; i++) { temp = date[i]; date[i] = date[_len - i]; date[_len - i] = temp; } } }}

上一篇：二分查找算法

下一篇：bfs