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