线性表
一 线性表特点
- 除第一个元素外，其他元素的前面都只有一个元素
- 除最后一个元素外，其他位置的数据后面都只有一个元素
- 线性表位置有先后关系，一个接着一个排列的结构
二 线性表类别
-
顺序表 : 顺序表是用地址连续的存储单元顺序存储线形表中的各个数据元素，逻辑上相邻的数据元素在物理上也是相邻的。缺点：在顺序表中查找任何一个位置上的数据元素非常方便，但是在删除和插入元素需要通过移动元素来操作，影响了运行效率
-
单链表： 链表不要求逻辑上相邻的数据元素在物理存储位置上也相邻，因此链表插入和删除元素都不需要移动数据元素，但同时也失去了顺序表可随机存储的优点
-
双向链表： 双向链表为单链表的扩展，结点当中多了一个数据项指向双亲结点
-
循环链表： 循环链表同样为单链表的扩展，最后一个结点指向下一个结点，开头结点指向最后结点
三 顺序表的实现
public interface IListDS<T>
{
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 GetElement(int index);//通过下标获取线性表中的数据
int Locate(T item);//查找数据项再线性表的位置
}
顺序表实现了线性表的接口
public class SeqList<T>:IListDS<T>
{
private T[] data;//整个线性表存放的数据
private int count = 0;//表示存放了多少个数据
public SeqList (int size)//size表示最大容量
{
data = new T[size];
count = 0;
}
//添加一个元素
public void Add(T item){
if (count == data.Length) {
Console.WriteLine ("容量已经增满不允许再存入");
} else {
//线性表不会溢出的时候则将数据添加到线性表中,并且count进行递增
data [count] = item;
count++;
}
}
//返回线性表的长度
public int GetLength(){
return count;
}
//获取集合当中某个元素
public T GetElement(int index){
//判断索引是否 存在
if (index >= 0 && index <= count - 1) {
return data [index];
} else {
Console.WriteLine ("索引bucunzai");
return default(T);//返回默认值
}
}
//通过索引器获取线性表中的元素
public T this [int index]{ get{ return GetElement(index);
}}
//是否为空
public bool IsEmpty(){
return count == 0;
}
//删除一个元素
public T Delete(int index){
T temp = data[index];
for(int i = index+1;i < count;i++){
data [i - 1] = data [i];
}
count--;
return temp;
}
//插入一个元素
public void Insert(T item,int index){
for(int i = count-1;i >= index;i--){
data [i + 1] = data [i];
}
data [index] = item;
count++;
}
// 获取某个元素的下标
public int Locate(T value){
for(int i = 0;i < count;i++){
if (data [i].Equals (value)) {
return i;
}
}
return -1;
}
//清除
public void Clear(){
for(int i = 0;i < count;i++){
data [i] = default(T);
}
count = 0;
}
}
三 单链表的实现
public class NodeLB<T>
{
//该结点存储的数据
private T data;
//指向下一个元素的指针
private NodeLB<T> next;
//构造方法
public NodeLB (T value)
{
data = value;
next = null;
}
public NodeLB(T value,NodeLB<T> next){
data = value;
this.next = next;
}
public NodeLB(NodeLB<T> next){
this.next = next;
}
public NodeLB(){
data = default(T);
next = null;
}
//属性
public T Data{
set{
data = value;
}
get{
return data;
}
}
public NodeLB<T> Next{
get{
return next;
}
set{
next = value;
}
}
}
//单链表类必须实现链表接口
public class LinkList<T>:IListDS<T>
{
private NodeLB<T> head;//存储链表的头节点
private int count;//单链表中元素个数
//默认构造
public LinkList ()
{
head = null;
}
//链表的长度
public int GetLength(){
//使用遍历整条链表直到结点指向下一个结点的指针为空，即链表结束
count = 0;
if (head == null) {
return count;
} else {
count = 1;
NodeLB<T> temp = head;
while (true) {
if (temp.Next != null) {
temp = temp.Next;
count++;
} else {
break;
}
}
}
return count;
}
//清空链表
public void Clear(){
//将链表头部置空则垃圾回收机制会依次回收链表每个结点
head = null;
}
// 判断该链表是否为空
public bool IsEmpty(){
return head == null;
}
//添加一个元素
public void Add(T item){
//根据这个数据创建一个节点
NodeLB<T> newNode = new NodeLB<T>(item);
//如果头节点为空，那么这个新的节点就是头节点
if (head == null) {
head = newNode;
} else {
//要把新节点放在链表的尾部
//要访问到链表的尾节点
NodeLB<T> temp = head;
while (true) {
if (temp.Next != null) {
temp = temp.Next;
} else {
break;
}
}
// 经过死循环while之后temp就是未添加的尾节点
//再将该节点指向下一个节点
temp.Next = newNode;
}
}
//插入元素
public void Insert(T item,int index){
NodeLB<T> newNode = new NodeLB<T>(item);
if (index == 0) {
newNode.Next = head;
head = newNode;
} else {
NodeLB<T> temp = head;
//0 1 2 (new) 3 4
NodeLB<T> preNode = new NodeLB<T>();
//让temp向后移动index个位置
for(int i = 0;i < index;i++){
preNode = temp;
temp = temp.Next;
}
//将新节点衔接进去链表当中
preNode.Next = newNode;
newNode.Next = temp;
}
}
//根据下标删除链表当中某个结点
public T Delete(int index){
T data = default(T);
//删除的是头节点
if (index == 0) {
data = head.Data;
NodeLB<T> headNext = head.Next;
head = headNext;
} else {
NodeLB<T> preNode = new NodeLB<T>();
NodeLB<T> temp = head;//index = 1
for (int i = 0; i <= index-1; i++) {
preNode = temp;
temp = temp.Next;
}
//返回将要被删除的节点数据
data = temp.Data;
NodeLB<T> nextNode = temp.Next;
//删除掉要删除的元素的链接
preNode.Next = nextNode;
}
return data;
}
//获取某个下标对应的元素数据
public T this [int index]{ get{
NodeLB<T> temp = head;
for(int i = 0;i < index;i++){
temp = temp.Next;
}
return temp.Data;
}}
//通过调用方法根据下标返回一个元素-normal
public T GetElement(int index){
NodeLB<T> temp = head;
for(int i = 0;i < index;i++){
temp = temp.Next;
}
return temp.Data;
}
//查找元素对应的下标
public int Locate(T item){
int index = 0;
NodeLB<T> temp = head;
while (true) {
// 0 1 2 3 4 ===3
if (!temp.Data.Equals (item)) {
index++;
if (temp.Next == null) {
Console.WriteLine ("链表当中不包含这个数据");
} else {
temp = temp.Next;
}
} else {
break;
}
}
return index;
}
}
