c⻠:リニアメーター、チェーン、スタック、キュー
25017 ワード
、 、 。 ：30. (C# ).pdf ///
///
/// ：
/// 、
/// （ ）
///
///
public interface IListDS
{
int GetLength(); //
void Clear(); //
bool IsEmpty(); //
void Append(T item); //
void Insert(T item, int i); //
T Delete(int i); //
T GetElem(int i); //
int Locate(T value); //
}
///
/// SequenceList
///
///
public class SeqList : IListDS
{
private int maxsize; //
private T[] data; // ，
private int last; // ， last=-1 ///
///
///
///C# ， 。 ，
/// 。
/// ， ：
///[ ] this[ index]
///{
/// get{// }
/// set{ // }
///}
///
///
///
public T this[int index]
{
get { return data[index]; }
set { data[index] = value; }
} // ， last=-1
public int Last
{
get { return last; }
}
//
public int Maxsize
{
get { return maxsize; }
set { maxsize = value; }
}
//
public SeqList(int size)
{
data = new T[size];
maxsize = size;
last = -1;
} #region IListDS ///
///
///
///
public int GetLength()
{
return last + 1;
}
///
///
///
public void Clear()
{
last = -1;
}
///
///
///
///
public bool IsEmpty()
{
if (last == -1)
{
return true;
}
else
{
return false;
}
}
///
///
///
///
public void Append(T item)
{
if (IsFull())
{
Console.WriteLine("List is full");
return;
}
data[++last] = item;
} ///
/// i
/// ： i 1 0
///
///
/// 1<=i<=n+1
public void Insert(T item, int i)
{
if (IsFull())
{
Console.WriteLine("List is full");
return;
}
//
//i 1
//i last+2 2
// 1<=i<=n+1
if (i < 1 || i > last + 2)
{
Console.WriteLine("Position is error");
return;
}
if (i == last + 2) //
{
//data[last + 1] = item;
data[i - 1] = item;
}
else
{
for (int j = last; j >= i - 1; --j)// an...ai
{
data[j + 1] = data[j];
}
data[i - 1] = item;//
}
++last;// ， 1
}
///
/// i
///
///
///
public T Delete(int i)
{
T temp = default(T);
if (IsEmpty())
{
Console.WriteLine("List is empty");
return temp;
}
//
//i 1
//i last+1 1
// ：1<=i<=n
if (i < 1 || i > last + 1)
{
Console.WriteLine("Position is error");
return temp;
}
if (i == last + 1)//
{
temp = data[last--]; return temp;
}
else
{
temp = data[i - 1];
for (int j = i; j <= last; ++j)//An..Ai+1
{
data[j] = data[j + 1];
}
} --last;
return temp;
}
///
/// i
///
///
///
public T GetElem(int i)
{
if (IsEmpty() || (i < 1) || (i > last + 1))
{
Console.WriteLine("List is empty or Position is error");
return default(T);
}
return data[i - 1];
}
///
/// value
///
///
///
public int Locate(T value)
{
if (IsEmpty())
{
Console.WriteLine("List is empty");
return -1;
}
int i = 0;
for (; i <= last; ++i)
{
if (value.Equals(data[i]))
{
break;
}
}
if (i > last)//
{
return -1;
}
return i;
} #endregion ///
/// ，
///
///
public bool IsFull()
{
if (last == maxsize - 1)
{
return true;
}
else
{
return false;
}
} ///
/// L ，
/// ：
/// ， 。
/// ， i n-i ，i [0..n/2],n
///
///
public void ReversSeqList(SeqList L)
{
int temp;
int len = L.GetLength();
for (int i = 0; i <= len / 2; ++i)
{
temp = L[i];
L[i] = L[len - i];
L[len - i] = temp;
}
} ///
/// La Lc Lc
///
///
///
///
public SeqList Merge(SeqList La, SeqList Lb)
{
SeqList Lc = new SeqList(La.maxsize + Lb.maxsize);
int i = 0, j = 0;
//2
while (i<=La.GetLength()-1 && j<=Lb.GetLength()-1)
{
if (La[i] < Lb[j])
{
Lc.Append(La[i++]);
}
else
{
Lc.Append(Lb[j++]);
}
}
//a
while (i <= La.GetLength() - 1)
{
Lc.Append(La[i++]);
}
//b
while (j <= Lb.GetLength() - 1)
{
Lc.Append(Lb[j++]);
} return Lc;
} } ///
///
///
///
public class Node
{
private T data; //
private Node next; // public Node(T val, Node p)
{
data = val;
next = p;
}
public Node(T val)
{
data = val;
}
public Node(Node p)
{
next = p;
}
public Node()
{
data = default(T);
next = null;
}
public T Data
{
get { return data; }
set { data = value; }
}
public Node Next
{
get { return next; }
set { next = value; }
}
} ///
///
///
///
public class LinkList : IListDS
{
private Node head;// public Node Head
{
get { return head; }
set { head = value; }
}
public LinkList()
{
head = null;
} #region IListDS public int GetLength()
{
Node p = head;
int len = 0;
while (p != null)
{
++len;
p = p.Next;
}
return len;
} public void Clear()
{
head = null;
} public bool IsEmpty()
{
if (head == null) return true;
else return false;
} public void Append(T item)
{
Node q = new Node(item);//
Node p = new Node(); if (head == null)
{
head = q;
return;
} p = head;
while (p.Next != null)
{
p = p.Next;
} p.Next = q;
} // i item
//
public void Insert(T item, int i)
{
if (IsEmpty() || i < 1)
{
Console.WriteLine("List is empty or Position is error !");
return;
}
if (i == 1)
{
Node q = new Node(item);
q.Next = head;
head = q;
return;
} // i
Node p = head;
Node r = new Node();// i
int j = 1;
while (p.Next != null && j < i)
{
r = p;
p = p.Next;
++j;
} if (j == i)
{
Node q = new Node(item);
q.Next = p;
r.Next = q;
}
else
{
Console.WriteLine("Position is error !");
}
return;
} // i item
//
public void InsertPost(T item, int i)
{
if (IsEmpty() || i < 1)
{
Console.WriteLine("List is empty or Position is error !");
return;
}
if (i == 1)
{
Node q = new Node(item);
q.Next = head.Next ;
head.Next = q;
return;
} // i
Node p = head;
int j = 1;
while (p.Next != null && j < i)
{
p = p.Next;
++j;
} if (j == i)
{
Node q = new Node(item);
q.Next = p.Next ;
p.Next = q;
}
else
{
Console.WriteLine("Position is error !");
}
return;
} public T Delete(int i)
{
if (IsEmpty() || i < 0)
{
Console.WriteLine("List is empty or Position is error !");
return default (T);
} Node q = new Node();
if (i == 1)
{
q = head;
head = head.Next;
return q.Data ;
} Node p = head;
int j = 1;
while (p.Next != null && j < i)
{
q = p;//
p = p.Next;
++j; } if (j == i)
{
q.Next = p.Next;
return p.Data;
}
else
{
Console.WriteLine("The " + i + "th node is not exist !");
return default(T);
} } public T GetElem(int i)
{
if (IsEmpty())
{
Console.WriteLine("List is empty !");
return default(T);
} Node p = new Node();
p = head;
int j = 1;
while (p.Next != null && j < i)
{
p = p.Next;
++j;
} if (j == i)
{
return p.Data;
}
else
{
Console.WriteLine("The " + i + "th node is not exist !");
return default(T);
}
} public int Locate(T value)
{
if (IsEmpty())
{
Console.WriteLine("List is empty !");
return -1;
} Node p = new Node();
p = head;
int i = 1;
while (!p.Data .Equals(value ) && p.Next!=null )
{
p = p.Next;
++i;
}
return i;
} #endregion
} #region
///
///
///
///
public interface IStack
{
int GetLength();
bool IsEmpty();
void Clear();
void Push(T item);//
T Pop(); //
T GetTop(); //
} ///
///
///
///
public class SeqStack : IStack
{
private int maxsize;
private T[] data;
private int top; public T this[int index]
{
get { return data[index]; }
set { data[index] = value; }
}
public int Maxsize
{
get { return maxsize; }
set { maxsize = value; }
}
public int Top
{
get { return top; }
}
public SeqStack(int size)
{
data = new T[size];
maxsize = size;
top = -1;
} #region IStack
public int GetLength()
{
return top + 1;
}
public bool IsEmpty()
{
if (top == -1) return true;
else return false;
}
public bool IsFull()
{
if (top == maxsize -1) return true;
else return false;
}
public void Clear()
{
top = -1;
}
public void Push(T item)
{
if (IsFull())
{
Console.WriteLine("Stack is full!");
return;
}
data[++top] = item;
}
public T Pop()
{
T temp = default(T);
if (IsEmpty())
{
Console.WriteLine("Stack is empty!");
return temp;
}
temp = data[top];
--top;
return temp;
}
public T GetTop()
{
if (IsEmpty())
{
Console.WriteLine("Stack is empty!");
return default(T);
}
return data[top];
}
#endregion
} ///
///
///
///
public class LinkStack : IStack
{
private Node top; //
private int num; //
public Node Top
{
get { return top; }
set { top = value; }
}
public int Num
{
get { return num; }
set { num = value; }
} public LinkStack()
{
top = null;
num = 0;
} #region IStack public int GetLength()
{
return num;
} public bool IsEmpty()
{
if (top == null && num == 0) return true;
else return false;
} public void Clear()
{
top = null;
num = 0;
} public void Push(T item)
{
Node q = new Node(item);
if (top == null)
{
top = q;
}
else
{
q.Next = top;
top = q;
}
++num;
} public T Pop()
{
T temp = default(T);
if (IsEmpty())
{
Console.WriteLine("Stack is empty!");
return temp;
}
Node p = top;
top = top.Next;
--num;
return p.Data;
} public T GetTop()
{
T temp = default(T);
if (IsEmpty())
{
Console.WriteLine("Stack is empty!");
return temp;
}
return top.Data;
} #endregion
} #endregion ///
///
///
///
public interface IQueue
{
int GetLength();
bool IsEmpty();
void Clear();
void In(T item);//
T Out(); //
T GetFront(); // }
///
///
///
///
public class CSeqQueue : IQueue
{
private int maxsize;//
private T[] data; // ，
private int front; //
private int rear; // public int Maxsize
{
get { return maxsize; }
set { maxsize = value; }
}
public int Front
{
get { return front; }
set { front = value; }
}
public int Rear
{
get { return rear; }
set { rear = value; }
}
public T this[int index]
{
get { return data[index]; }
set { data[index] = value; }
}
public CSeqQueue(int size)
{
data = new T[size];
maxsize = size;
front = rear = -1;
} #region IQueue public int GetLength()
{
return (rear - front + maxsize) % maxsize;
} public bool IsEmpty()
{
if (front == rear) return true;
else return false;
}
// rear=front
//
public bool IsFull()
{
if ((rear + 1) % maxsize == front) return true;
else return false;
}
public void Clear()
{
front = rear = -1;
} public void In(T item)
{
if (IsFull())
{
Console.WriteLine("Queue is full!");
return;
}
data[++rear] = item;
} public T Out()
{
T temp = default(T);
if (IsEmpty())
{
Console.WriteLine("Queue is empty!");
return temp ;
}
temp = data[ ++front];
return temp;
} public T GetFront()
{
T temp = default(T);
if (IsEmpty())
{
Console.WriteLine("Queue is empty!");
return temp;
}
temp = data[front+1];
return temp;
} #endregion
} ///
///
///
///
public class LinkQueue : IQueue
{
private Node front; //
private Node rear; //
private int num;// public int Num
{
get { return num; }
set { num = value; }
}
public Node Front
{
get { return front; }
set { front = value; }
}
public Node Rear
{
get { return rear; }
set { rear = value; }
} public LinkQueue()
{
front = rear = null;
num = 0;
} #region IQueue public int GetLength()
{
return num ;
} public bool IsEmpty()
{
if (front == rear && num==0) return true;
else return false;
} public void Clear()
{
front = rear = null;
} public void In(T item)
{
Node q = new Node(item); if (rear == null)
{
rear = q;
}
else
{
rear.Next = q;
rear = q;
}
++num;
} public T Out()
{
if (IsEmpty())
{
Console.WriteLine("Queue is empty!");
return default(T);
}
Node p = front;//
front = front.Next;//
if (front == null)
{
rear = null;
}
--num;
return p.Data;
} public T GetFront()
{
if (IsEmpty())
{
Console.WriteLine("Queue is empty!");
return default(T);
}
return front.Data;
} #endregion
}