线性表

一 线性表特点

• 除第一个元素外，其他元素的前面都只有一个元素
• 除最后一个元素外，其他位置的数据后面都只有一个元素
• 线性表位置有先后关系，一个接着一个排列的结构

二 线性表类别

• 顺序表 : 顺序表是用地址连续的存储单元顺序存储线形表中的各个数据元素，逻辑上相邻的数据元素在物理上也是相邻的。缺点：在顺序表中查找任何一个位置上的数据元素非常方便，但是在删除和插入元素需要通过移动元素来操作，影响了运行效率
• 单链表： 链表不要求逻辑上相邻的数据元素在物理存储位置上也相邻，因此链表插入和删除元素都不需要移动数据元素，但同时也失去了顺序表可随机存储的优点
• 双向链表： 双向链表为单链表的扩展，结点当中多了一个数据项指向双亲结点
• 循环链表： 循环链表同样为单链表的扩展，最后一个结点指向下一个结点，开头结点指向最后结点

三 顺序表的实现

• 1 线性表接口

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);//查找数据项再线性表的位置
    }

• 2 顺序表类SeqList<T>

顺序表实现了线性表的接口
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;
        }
    }

三 单链表的实现

• 1 单链表结点类

    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;
            }
        }
    }

• 2 单链表类

    //单链表类必须实现链表接口
    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;
        }
    }