艾伟_转载：C#版数据结构之--线性表的链式存储(单链表)

1.单链表的定义和由来:

　　链表是用一组地址可能连续也可能不连续的存储单元来存储线性表中的数据元素,在存储数据元素时,除了要存储数据元素本身之外,还要存储与它相邻的数据元素的地址信息,这两部分组成了线性表中一个数据元素的映像,称之为"结点",存储数据元素本身的部分称之为:数据域,存储相邻数据元素地址的部分称之为:地址域,所有节点通过地址域链接起来,像一个链条,故用此种方式存储的线性表称之为:链表.如果节点的地址域只存储了数据元素的直接后继的存储地址,则称这种链表为:单链表.

　　与数序表相比,链表由于是通过存储后继结点地址的方式来体现线性关系的,向链表中插入,删除数据元素要比顺序表要快(因为顺序表对数据元素的插入和删除操作时,大部分情况下,要对数据元素在存储单元中做移动);但是查找链表中的数据元素要比顺序表中的查找要慢,因为查找链表中的数据元素,需要遍历链表(而顺序表由于每个元素与第一个元素的地址相对固定,所以只要知道第一个数据元素的地址和数据元素的数据类型,很快就会直接定位到要查找的数据元素).

　　结点:    

　　　　　　

2.单链表的实现:

2.1结点:

Node
public class Node<T>
    {
        private T _data;

        public T Data
        {
            get { return _data; }
            set { _data = value; }
        }
        private Node<T> _next;

        public Node<T> Next
        {
            get { return _next; }
            set { _next = value; }
        }

        public Node()
        {
            _data = default(T);
            _next = null;
        }

        public Node(T data)
        {
            _data = data;
            _next = null;
        }

        public Node(Node<T> next)
        {
            _next = next;
        }

    }

2.2单链表:

SepLinkedList
  public class SepLinkedList<T>
    {
        
        private Node<T> _head;
        /// 
        /// 头指针
        /// 
        public Node<T> Head
        {
            get { return _head; }
            set { _head = value; }
        }

     
        /// 
        /// 获取单链表长度
        /// 
        /// 
        public int GetLength()
        {
            Node<T> p = _head;
            int length = 0;
            while (p != null)
            {
                length++;
                p = p.Next;
            }
            return length;
        }

        /// 
        /// 清空单链表
        /// 
        public void Clear()
        {
            _head = null;
        }

        public bool IsEmpty()
        {
            if (_head == null)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
        /// 
        /// 附件数据元素
        /// 
        /// 
        public void Append(T item)
        {
            Node<T> p = new Node<T>();
            Node<T> q = new Node<T>(item);
            if (_head == null)
            {
                _head = q;
                return;
            }
            p = _head;
            while (p.Next != null)
            {
                p = p.Next;
            }
            p.Next = q;
            
        }
        /// 
        /// 删除第i个数据元素
        /// 
        /// 
        /// 
        public T Delete(int i)
        {
            Node<T> q = new Node<T>();
            if (i == 1)
            {
                q = _head;
                _head = _head.Next;
                return q.Data;
            }
            Node<T> p = _head;
            int j = 1;
            while (p.Next != null && j < i)
            {
                j++;
                q = p;
                p = p.Next;
               
            }
            if (j == i)
            {
                q.Next = p.Next;
                return p.Data;
            }
            else
            {
                Console.WriteLine("该位置不存在结点");
                return default(T);

            }
        }
        /// 
        /// 在第i个位置前插入数据元素
        /// 
        /// 
        /// 
        public void Insert(T item, int i)
        {
            if (i == 1)
            {
                Node<T> q = new Node<T>(item);
                q.Next = _head;
                _head = q;
                return;
            }

            Node<T> p = _head;
            Node<T> r = new Node<T>();
            int j=1;
            while (p.Next != null && j < i)
            {
                r = p; 
                p = p.Next;
            }
            if (j == i)
            {
                Node<T> q = new Node<T>(item);
                q.Next = p;
                r.Next = q;
            }
        }

        /// 
        /// 在第i个位置后插入一个数据元素
        /// 
        /// 
        /// 
        public void InsertPost(T item, int i)
        {
            Node<T> p = _head;
            
            int j = 1;
            //找第i个元素
            while (p.Next != null && j < i)
            {
                p = p.Next; 
                j++;
            }

            if (j == i)
            {
                Node<T> q = new Node<T>(item);
                q.Next = p.Next;
                p.Next = q;
            }

        }

        /// 
        /// 取表元
        /// 
        /// 
        /// 
        public T GetElem(int i)
        {
            if (IsEmpty())
            {
                Console.WriteLine("链表为空");
                return default(T);
            }
            Node<T> p = new Node<T>();
            p = _head;
            int j = 1;
            while (p.Next != null && j < i)
            {
                p = p.Next;
                j++;
            }
            if (j == i)
            {
                return p.Data;
            }
            else
            {
                Console.WriteLine("未找到该序号的结点");
                return default(T);
            }

        }
        /// 
        /// 按值查找数据元素
        /// 
        /// 
        /// 
        public int Locate(T item)
        {
            if (IsEmpty())
            {
                Console.WriteLine("链表为空");
                return -1;
            }
            Node<T> p = new Node<T>();
            p = _head;
            int i = 1;
            while ( p != null && !item.Equals(p.Data))
            {
                p = p.Next;
                i++;
            }
            if (p != null)
            {
                return i;
            }
            else
            {
                Console.WriteLine("单链表中不存在指定数据元素");
                return -1;
            }
            

        }
}

 

　　2.2.1插入数据元素的图示:

　　　　

　　2.2.2删除数据元素的图示:

　　　　　　

　　2.2.3 单链表的建立:

　　第一种方式:(采用从尾部加入结点的方式)

CreateLinkedList
 /// 
        /// 建立单链表
        /// 
        /// 
        static SepLinkedList<int> CreateLinkedList()
        {
            SepLinkedList<int> result = new SepLinkedList<int>();
            Node<int> r = new Node<int>();
            r = result.Head;
            int elem = Int32.Parse(Console.ReadLine());
            while (elem != -1)//以-1做为结束标志
            {
                Node<int> p = new Node<int>(elem);
                if (result.Head == null)
                {
                    result.Head = p;
                }
                else
                {
                    r.Next = p;//加入链表
                }
                r = p; //记下最后一个结点
                elem = Int32.Parse(Console.ReadLine());
            }
            if (r != null)
            {
                r.Next = null;//最后一个节点地址域置空
            }
            return result;
        }

 　　第二种方式:(采用在头部加入结点的方式)

CreateLinkedList
  static SepLinkedList<int> CreateSepLinkedList()
        {
            SepLinkedList<int> result = new SepLinkedList<int>();

            int d = Int32.Parse(Console.ReadLine());
            while (d != -1)
            {
                Node<int> elem = new Node<int>(d);
                elem.Next = result.Head;
                result.Head = elem;
                d = Int32.Parse(Console.ReadLine());
            }
            return result;
        }

2.2.4关于单链表的操作:

Code        /// <summary>/// 将整形顺序表A中大于零的元素放入顺序表B中,把小于零的数据元素放入顺序表C中/// 算法思想:遍历单链表la,依次读取数据元素与0比较,将小于0的数据元素放入lc,将大于0的放入lb/// </summary>/// <param name="la"></param>        static void PurgeToTwo(SepLinkedList<int> la,SepLinkedList<int> lb,SepLinkedList<int> lc)        {            Node<int> p = la.Head;while (p != null)            {if (p.Data > 0)                    lb.Append(p.Data);else                    lc.Append(p.Data);                p = p.Next;            }        }/// <summary>/// 取单链表中最小值/// 算法思想:去取最大值相反/// </summary>/// <param name="la"></param>/// <returns></returns>        static int GetMin(SepLinkedList<int> la)        {            Node<int> p = la.Head;            Node<int> temp = p;while (p.Next != null)            {                 p = p.Next;if (temp.Data > p.Data)                {                     temp = p;                }            }return temp.Data;        }/// <summary>/// 取单链表中最大值/// 算法思想:取链表中的第一个数据元素,然后让这个元素与剩下的元素比较,将两者较小者存入结果中/// </summary>/// <param name="la"></param>/// <returns></returns>        static int GetMax(SepLinkedList<int> la)        {            Node<int> p = la.Head;            Node<int> temp = p;while (p.Next != null)            {                p = p.Next;if (temp.Data < p.Data)                {                    temp = p;                }            }return temp.Data;        }设一顺序表(单链表)中的元素值递增有序,将元素x插入到表中适当的位置,//并保持顺序表(单链表)的有序性//分析时间复杂度        static void Insert(SepLinkedList<int> la, int x)        {            Node<int> p = la.Head;            Node<int> q = new Node<int>();            Node<int> temp = new Node<int>(x);if (x < p.Data) //小于第一个元素            {                temp.Next = la.Head;                la.Head = temp;            }while (p.Next != null)             {                q = p;                p = p.Next;if (q.Data <= x && x <= p.Data)                {

temp.Next = p;                    q.Next = temp;return;                }            }if (p != null)            {                p.Next = temp;            }

}/// <summary>/// 提取单链表中不重复的数据元素/// </summary>/// <param name="l"></param>/// <returns></returns>        static SepLinkedList<int> Purge(SepLinkedList<int> l)        {            SepLinkedList<int> result = new SepLinkedList<int>();            Node<int> p = l.Head;            Node<int> q = new Node<int>();            Node<int> s = new Node<int>();

//将第一个元素加入结果链表            s = p;            p = p.Next;            s.Next = null;            result.Head = s;

while (p != null)            {                s = p;                p = p.Next;                q = result.Head;

while (q != null && q.Data != s.Data)                {                    q = q.Next;                }if (q == null)                {                    s.Next = result.Head;                    result.Head = s;                }            }return result;

}/// <summary>/// 将两个存储整型数据元素升序排列的单链表合并,并保持升序/// 算法思想:将la中的每个元素与lb的元素依次比较,并将每次比较中的小者加入结果链表中,最后将剩余的数据元素加入结果链表中/// </summary>/// <param name="la"></param>/// <param name="lb"></param>/// <returns></returns>        static SepLinkedList<int> Merge(SepLinkedList<int> la, SepLinkedList<int> lb)        {            Node<int> p = la.Head;            Node<int> q = lb.Head;int temp = 0;            SepLinkedList<int> result = new SepLinkedList<int>();while (p != null && q != null)            {if (p.Data < q.Data)                {                    temp = p.Data;                    p = p.Next;                }else                {                    temp = q.Data;                    q = q.Next;                }

}            result.Append(temp);if (p == null)            {                p = q;            }while (p != null)            {                temp = p.Data;                result.Append(temp);                p = p.Next;            }return result;

}
时间： 2024-07-31 02:20:57

艾伟_转载：C#版数据结构之--线性表的链式存储(单链表)的相关文章

C#版数据结构之--线性表的链式存储(单链表)

1.单链表的定义和由来: 链表是用一组地址可能连续也可能不连续的存储单元来存储线性表中的数据元素,在存储数据元素时,除了要存储数据元素本身之外,还要存储与它相邻的数据元素的地址信息,这两部分组成了线性表中一个数据元素的映像,称之为"结点",存储数据元素本身的部分称之为:数据域,存储相邻数据元素地址的部分称之为:地址域,所有节点通过地址域链接起来,像一个链条,故用此种方式存储的线性表称之为:链表.如果节点的地址域只存储了数据元素的直接后继的存储地址,则称这种链表为:单链表. 与数序表相比

大话数据结构二：线性表的链式存储结构（单链表）

1. 线性表的链式存储结构:指的是用一组任意的存储单元存储线性表的数据元素,这组存储单元可以是连续的,也可以是不连续的,这就意味着这些数据元素可以存在内存未被占用的任意位置. 2. 结点:结点由存放数据元素的数据域和存放后继结点地址的指针域组成. 1.)顺序存储结构中,每个数据元素只需要存数据元素的信息就可以了. 2.)链式存储结构中,除了要存储数据元素信息外,还要存储它的后继元素的存储地址. 3.)链表中第一个结点叫头结点,它的存储位置叫做头指针,它的数据域可以不存储任何信息,链表的最后一个结

大话数据结构五：线性表的链式存储结构（双向链表）

1. 双向链表:在单链表的每个结点中,再设置一个指向其前驱结点的指针域,那么在双向链表中的结点都有两个指针域,一个指向直接后继,另一个指向直接前驱. 2. 单链表和双向链表比较: 单链表:总是要从头到尾找结点,只能正遍历,不能反遍历. 双向链表: 可以从头找到尾,也可以从尾找到头,即正反遍历都可以,可以有效提高算法的时间性能,但由于每个结点需要记录两份指针,所以在空间占用上略多一点,这就是通过空间来换时间. 3. Java实现双向链表: // 双向链表 public class DoubleLi

大话数据结构四：线性表的链式存储结构（单向循环链表）

1. 单向循环链表:将单链表尾结点的指针端由空指针改为指向头结点,使整个单链表形成一个环,这种头尾相接的单链表称为单向循环链表.   2. 单向循环链表和单链表实现的区别: 1.)添加一个结点到单向循环链表末尾时,必须使其最后一个结点的指针指向表头结点,而不是象单链表那样置为null. 2.)判断是否到达表尾时,单向循环链表可以判断该结点是否指向头结点,单链表只需要知道是否为null.   3.Java实现单向循环链表: // 单向循环链表 public class CircularLinked

大话数据结构三：线性表的链式存储结构（静态链表）

1. 静态链表:用数组描述的链表叫静态链表,通常为方便数据插入,我们会把数组建的大一些. 2. 数组元素(node):由两个数据域组成(data,cursor).数据域data用来存放数据元素,也就是通常我们要处理的数据:而cursor相当于单链表中的指针,存放该元素的后继在数组中的下标. 3. Java实现静态链表: // 静态链表 class StaticLinkedList { private int size; private Node[] node = new Node[100]; /

线性表的链式表示

以下为操作链表的算法,该链表为动态单链表. 链表以头指针为索引,头指针指向头节点,头节点指向首节点,以此类推,直到尾节点. 头节点中不存放数据,只存放指向首节点的指针, 设置头节点的目的是为了方便对链表的操作,如果不设置头节点,而是直接由头指针指向首节点, 这样在对头指针后的节点进行插入删除操作时就会与其他节点进行该操作时有所不同,便要作为一种特殊情况来分析 操作系统:ubuntu 编译软件:gcc 结果截图: 源代码: #include<stdio.h> #include<stdlib

《数据结构与算法 C语言版》—— 2.3线性表的链式表示与实现

2.3线性表的链式表示与实现 线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻,因此可以随机存取表中任一元素,它的存储位置可用一个简单.直观的公式来表示.然而,从另一方面来看,这个特点也造成了这种存储结构的弱点:在作插入或删除操作时,需移动大量元素.本节我们将讨论线性表的另一种表示方法--链式存储结构,其特点是用一组地址任意的存储单元存储线性表中的数据元素.由于它不要求逻辑上相邻的元素在物理位置上也相邻,因此它没有顺序存储结构所具有的弱点,但同时也失去了顺序表随机存取的特点

数据结构教程 第八课 线性表的链式表示与实现

本课主题: 线性表的链式表示与实现 教学目的: 掌握线性链表.单链表.静态链表的概念.表示及实现方法 教学重点: 线性链表之单链表的表示及实现方法. 教学难点: 线性链表的概念. 授课内容: 一.复习顺序表的定义. 二.线性链表的概念: 以链式结构存储的线性表称之为线性链表. 特点是该线性表中的数据元素可以用任意的存储单元来存储.线性表中逻辑相邻的两元素的存储空间可以是不连续的.为表示逻辑上的顺序关系,对表的每个数据元素除存储本身的信息之外,还需存储一个指示其直接衙继的信息.这两部分信息组成数据

线性表的链式表示和实现

一.前言     线性表的顺序存储结构特点是:逻辑关系上相邻的两个元素在物理位置上也相邻,因此可以随机存取表中的任何一个元素.    缺点:在作插入删除操作时,需要移动大量元素. 二.链式存储结构     概念:它不要求逻辑上相邻的元素在物理位置上也相邻,因此它没有顺序存储结构所具有的弱点,但同时也失去顺序表可随机存取的优点. 三.线性链表     存储空间可以连续也可以不连续.为了表示ai和ai+1的逻辑关系,对数据元素ai来说,除了存储其本身的信息之外,还需存储一个指示其直接后继的信息(即直