线性表：相同类型，有限，序列
{///
/// 顺序表接口
///
///
interface IListDS
{
int GetLength();
void Clear();
bool IsEmpty();
void Add(T item);
void Insert(T item, int index);
T Delete(int index);
T this[int index] { get; }
T GetEle(int index);
int Locate(T value);
}
}
{
///
/// 顺序表
///
///
class SeqList
{
private T[] array;//存储数据
private int count = 0;//数据个数
public SeqList(int size)
{
if (size > 0)
array = new T[size];
}
public SeqList() : this(4)//调用自身构造方法
{
//array = new T[4];
}
public T this[int index]
{
get { return GetEle(index); }
}
public void Add(T item)
{
if(count == array .Length )
{
var newArray = new T[array.Length * 2];
Array.Copy(array, newArray, count);
array = newArray;
}
array[count] = item;
count++;
}
public void Clear()
{
count = 0;
}
public T Delete(int index)
{
if(index >=0&&index <=count-1)
{
T item = GetEle(index);
for (int i = index+1 ; i < count; i++)
{
array[i-1] = array[i];
}
count--;
return item;
}
else
{
Console.WriteLine("Index outof range");
throw new Exception("索引超出范围");
}
}
public T GetEle(int index)
{
if (index >= 0 && index <= count - 1)
{
return array[index];
}
else
{
Console.WriteLine("Index outof range");
throw new Exception("索引超出范围");
}
}
public int GetLength()
{
return count;
}
public void Insert(T item, int index)
{
if(index >=0&&index <=count -1)
{
if (count == array.Length)
{
var newArray = new T[array.Length * 2];
Array.Copy(array, newArray, count);
array = newArray;
}
for (int i = count -1; i >=index ; i--)
{
array[i + 1] = array[i];
}
array[index] = item;
count++;
}
else
{
Console.WriteLine("Index outof range");
throw new Exception("索引超出范围");
}
}
public bool IsEmpty()
{
return count == 0;
}
public int Locate(T value)
{
for (int i = 0; i < count; i++)
{
if (array[i].Equals(value))
{
return i;
}
}
return -1;
}
}
}
顺序表：线性表的顺序存储（静态数组（以分配默认大小），动态数组）
单链表：线性表链式存储（链式指针，非顺序存储[数据，地址]对形式）
判断单链表是否为空1，头结点head是否为空。2，头结点的指针head->next 是否为空
//节点类
using System;
using System.Collections.Generic;
using System.Text;
namespace 数据结构
{///
/// 线性表-节点类
///
class Node
{
private T date;
private Node
public T Date
{
get { return date; }
set { date = value; }
}
public Node <T> Next
{
get { return next; }
set { next = value; }
}
public Node()
{
date = default(T);
next = null;
}
public Node (T value)
{
date = value;
next = null;
}
public Node (T value,Node <T> next)
{
date = value;
this.next = next;
}
public Node(Node <T> next)
{
this.next = next;
}
}
}
///////////////////////////////////////////////////////////
using System;
using System.Collections.Generic;
using System.Text;
namespace 数据结构
{///
/// 单链表
///
///
class LinkList
{
private Node
public LinkList()
{
head = null;
}
public T this[int index]
{
get
{
Node<T> temp = head;
for (int i = 0; i < index; i++)
{
temp = temp.Next;
}
return temp.Date;
}
}
public void Add(T item)
{
Node<T> newNode = new Node<T>(item);//根据新的数据创建节点
//如果头结点为空则该节点作为头结点
if(head==null)
{
head = newNode;
}
else
{//把新的节点放到链表的末尾
//访问到链表的末尾点
Node<T> temp = head;
while (true)
{
if (temp.Next != null)
{
temp = temp.Next;
}else
{
break;
}
}
temp.Next = newNode;
}
}
public void Clear()
{
head = null;
}
public T Delete(int index)
{
T date = default(T);
if (index == 0)
{
date = head.Date;
head = head.Next;
}
else
{
Node<T> temp = head;
for (int i = 0; i < index - 1; i++)
{
temp = temp.Next;
}
Node<T> pr = temp;
Node<T> d = temp.Next;
date = d.Date;
Node<T> l = d.Next;
pr.Next = l;
}
return date;
}
public T GetEle(int index)
{
if (head == null)
{
Console.WriteLine("Index outof range");
throw new Exception("链表为空");
}
if (index == 0)
return head.Date;
Node<T> temp = head;
for (int i = 0; i < index ; i++)
{
temp = temp.Next;
}
return temp.Date;
}
public int GetLength()
{
if (head == null)
return 0;
else
{
int length = 1;
Node<T> temp = head;
while (true)
{
if (temp.Next != null)
{
length++;
temp = temp.Next;
}
else
break;
}
return length;
}
}
public void Insert(T item, int index)
{
Node<T> newNode = new Node<T>(item);
if (index ==0)
{
newNode.Next = head;
head = newNode;
}else
{
Node<T> temp = head;
for (int i = 0; i < index -1; i++)
{
temp = temp.Next;
}
Node<T> pr = temp;
Node<T> cu = temp.Next;
pr.Next = newNode;
newNode.Next = cu;
}
}
public bool IsEmpty()
{
if (head != null)
return false;
else
return true;
}
public int Locate(T value)
{
Node<T> temp = head;
if (temp == null)
return -1;
else
{
int index = 0;
while (true)
{
if (temp.Date.Equals(value))
{
return index;
}
else
{
if (temp.Next != null)
{
index++;
temp = temp.Next;
}
else break;
}
}
return -1;
}
}
}
}
栈：顺序栈，链栈。
1.1顺序栈
namespace 栈
{
interface IStackDS
{
int Count { get; }
int GetLength();
bool IsEmpty();
void Clear();
void Push(T item);
T Pop();
T Peek();
}
}
namespace 栈
{
class SeqStack
{
private T[] date;
private int top;
public SeqStack(int size)
{
date = new T[size];
top = -1;
}
public SeqStack ():this (10)
{
}
public int Count
{
get
{
return top+1;
}
}
public void Clear()
{
top = -1;
}
public int GetLength()
{
return Count;
}
public bool IsEmpty()
{
return Count == 0;
}
public T Peek()
{
return date[top];
}
public T Pop()
{
T temp = date[top];
top--;
return temp;
}
public void Push(T item)
{
date[top +1] = item;
top++;
}
}
}
2.链栈
{///
/// 链栈的节点类
///
///
class Node
{
private T date;
private Node
public T Date
{
get
{
return date;
}
set
{
date = value;
}
}
public Node <T> Next
{
get
{
return next;
}
set
{
next = value;
}
}
public Node ()
{
date = default(T);
next = null;
}
public Node (T date )
{
this.date = date;
this.next = null;
}
public Node (T date,Node <T> next)
{
this.date = date;
this.next = next;
}
public Node (Node<T> next)
{
this.next = next;
this.date = default(T);
}
}
}
队列：先进先出--常用方法：初始化队列，判断队列是否为空（首末指针相同时队列为空），队列长度为末指针-首指针。
入队，出队，读取队头元素，销毁队列。
namespace 队列
{///
/// 先入队先出后入队后出
///
class Program
{
static void Main(string[] args)
{
//声明队列
//SeqQueue
//使用链队列
LinkQueue
//入队
queue.Enqueue(23);
queue.Enqueue(45);
queue.Enqueue(66);
queue.Enqueue(89);
Console.WriteLine("添加数据之后队列的大小为："+queue.Count);
//出队：取得队首的数据，并删除
int i = queue.Dequeue();
Console.WriteLine("取得队首的数据："+i);
Console.WriteLine("取出队首数据后队列大小为："+queue.Count);
//取得队首数据，不删除
int j = queue.Peek();
Console.WriteLine("队首数据："+j);
Console.WriteLine( "队列大小："+queue .Count);
queue.Clear();
Console.WriteLine("清空队列后队列大小为："+queue.Count);
string str = Console.ReadLine();
Console.WriteLine("str是否为回文"+IsMirText(str));
}
//栈与队列引用，判断是否为回文“vowov”
public static bool IsMirText(string str)
{
Stack<char> stack = new Stack<char>();
Queue<char> queue = new Queue<char>();
for (int i = 0; i < str.Length; i++)
{
stack.Push(str[i]);
queue.Enqueue(str[i]);
}
bool isMt = true;
while (stack.Count > 0)
{
if (stack.Pop() != queue.Dequeue())
{
isMt = false;
break;
}
}
return isMt;
}
}
}
顺序队列，
using System;
using System.Collections.Generic;
using System.Text;
namespace 队列
{
class SeqQueue
{
private T[] date;
private int count;
private int front;//队首/队首元素索引减一
private int rear;//队尾/队尾元素索引
public SeqQueue(int size)
{
date = new T[size];
count = 0;
front = -1;
rear = - 1;
}
public SeqQueue ():this(10)
{
}
public int Count
{
get { return count; }
}
public void Clear()
{
count = 0;
front = rear = -1;
}
public T Dequeue()
{
if (count >0)
{
T temp = date[front + 1];
front++;
count--;
return temp;
}
else
{
Console.WriteLine("队列为空");
return default(T);
}
}
public void Enqueue(T item)
{
if (count == date.Length)
{
Console.WriteLine("队列已满");
}else
{
if(rear==date .Length-1)
{
date[0] = item;
rear = 0;
count++;
}
else
{
date[rear + 1] = item;
rear++;
count++;
}
}
}
public int GetLength()
{
return count;
}
public bool IsEmpty()
{
return count == 0;
}
public T Peek()
{
T temp = date[front + 1];
return temp;
}
}
}
循环队列。
namespace 队列
{///
/// 节点类
///
///
class Node
{
private T date;
private Node
public Node (T date)
{
this.date = date;
}
public T Date
{
get { return date; }
set { date = value; }
}
public Node <T> Next
{
get { return next; }
set { this.next = value; }
}
}
}
namespace 队列
{
class LinkQueue
{
private Node
private Node
private int count;
public LinkQueue()
{
front = null;
rear = null;
count = 0;
}
public int Count
{
get { return count; }
}
public void Clear()
{
count = 0;
front = null;
rear = null;
}
public T Dequeue()
{
if (count == 0)
{
Console.WriteLine("队列为空");
return default(T);
}
else if (count == 1)
{
T temp = front.Date;
//Clear();
front = rear = null;
count = 0;
return temp;
}
else
{
T temp = front.Date;
front = front.Next;
count--;
return temp;
}
}
public void Enqueue(T item)
{
Node<T> newNode = new Node<T>(item);
if (count ==0)
{
front = newNode;
rear = newNode;
count = 1;
}else
{
rear.Next = newNode;
rear = newNode;
count++;
}
}
public int GetLength()
{
return count;
}
public bool IsEmpty()
{
return count == 0;
}
public T Peek()
{
if (front !=null)
{
return front.Date;
}else
{
return default(T);
}
}
}
}