`
pcajax
  • 浏览: 2174121 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

C#数据结构-链表

阅读更多

理论基础:

链表是用一组任意的存储单元来存储线性表中的数据元素。

如果结点的引用域只存储该结点直接后继结点的存储地址,则该链表叫单链表(Singly Linked List)。

单链表由头引用H唯一确定。头引用指向单链表的第一个结点,也就是把单链表第一个结点的地址放在H中。

C#实现:

1接口

引用线性表的接口IListDS<T>

2实现

<script language="JavaScript" src="http://book.book560.com/ads/ads728x15.js" type="text/javascript"></script>

首先,必须定义一个单链表的节点类
public class Node<T>
{
    private T data;        //数据域
    private Node<T> next;  //引用域

    public Node(T val)
    {
        data = val;
        next = null;
    }

    public Node()
    {
        data = default(T);
        next = null;
    }

    public T Data
    {
        get { return data; }
        set { data = value; }
    }
    public Node<T> Next
    {
        get { return next; }
        set { next = value; }
    }
}
实现主体类

<script language="JavaScript" src="http://book.book560.com/ads/ads728x15.js" type="text/javascript"></script>

Append,Insert,InsertBack三个方法实质上都是插入操作,可以考虑用overload或者override来实现,有兴趣的朋友试试。
public class LinkList<T> : IListDS<T>
{
    private Node<T> head;

    public Node<T> Head
    {

        get { return head; }
        set { head = value; }
    }
    public LinkList()
    {
        head = null;
    }

    /// <summary>
    /// 获取长度
    /// </summary>
    /// <returns></returns>
    public int GetLength()
    {
        Node<T> p = head;
        int len = 0;
        while (p != null)
        {
            ++len;
            p = p.Next;
        }
        return len;
    }

    /// <summary>
    /// 清空操作
    /// </summary>
    public void Clear()
    {
        head = null;
    }

    /// <summary>
    /// 判断线性表是否为空
    /// </summary>
    /// <returns></returns>
    public bool IsEmpty()
    {
        if (head == null)
        {
            return true;
        }
        else
        {
            return false;
        }
    }

    /// <summary>
    /// 附加操作,线性表未满,将值为item的新元素添加到末尾
    /// </summary>
    /// <param name="item"></param>
    public void Append(T item)
    {
        Node<T> newNode = new Node<T>(item);  //根据元素创建新的节点
        Node<T> node = new Node<T>();

        if (head == null)
        {
            head = newNode;
            return;
        }
        node = head;
        while (node.Next != null)
        {
            node = node.Next;
        }
        node.Next = newNode;
    }

    /// <summary>
    /// 寻找节点
    /// </summary>
    /// <param name="i"></param>
    /// <returns></returns>
    public Node<T> FindNode(int i)
    {
        if (IsEmpty())
        {
            Console.Write("List is empty");
            return null;
        }
        if (i < 1)
        {
            Console.Write("Index is error");
            return null;
        }
        Node<T> current = head;
        int j = 1;

        while (current.Next != null && j < i)
        {
            ++j;
            current = current.Next;
        }
        return current;
    }

    /// <summary>
    /// 插入操作,在第i个节点前面插入item
    /// </summary>
    /// <param name="item"></param>
    /// <param name="i"></param>
    public void Insert(T item, int i)
    {
        Node<T> newNode = new Node<T>(item);
        Node<T> node = new Node<T>();
        Node<T> current = FindNode(i);
        if (current != null)
        {
            node = current;       //对目标节点备份
            newNode.Next = current;
            node.Next = newNode;
        }
    }

    /// <summary>
    /// 插入操作,在第i个节点后面插入item
    /// </summary>
    /// <param name="item"></param>
    /// <param name="i"></param>
    public void InsertBack(T item, int i)
    {
        Node<T> newNode = new Node<T>(item);
        Node<T> current = FindNode(i);
        if (current != null)
        {
            newNode.Next = current.Next;
            current.Next = newNode;
        }
    }

    /// <summary>
    /// 删除操作
    /// </summary>
    /// <param name="i"></param>
    /// <returns></returns>
    public T Delete(int i)
    {
        Node<T> current = FindNode(i);
        Node<T> node = new Node<T>();
        if (current != null)
        {
            node = current;   //对目标节点备份
            node.Next = current.Next;
            return current.Data;
        }
        else
        {
            Console.Write("the node is not exist!");
            return default(T);
        }
    }

    /// <summary>
    /// 去表元
    /// </summary>
    /// <param name="i"></param>
    /// <returns></returns>
    public T GetElem(int i)
    {
        Node<T> current = FindNode(i);

        if (current != null)
        {
            return current.Data;
        }
        else
        {
            Console.Write("the node is not exist!");
            return default(T);
        }
    }

    /// <summary>
    /// 按值查找
    /// </summary>
    /// <param name="value"></param>
    /// <returns></returns>
    public int Locate(T value)
    {
        if (IsEmpty())
        {
            Console.WriteLine("List is Empty!");
            return -1;
        }
        Node<T> current = new Node<T>();
        current = head;
        int i = 1;
        while (current.Next != null && !current.Data.Equals(value))
        {
            current = current.Next;
            ++i;
        }
        return i;
    }
}

分享到:
评论

相关推荐

    第11章 动态数据结构-链表-21

    在本章中,我们探讨了如何使用C语言实现动态数据结构——单向链表。单向链表是一种线性数据结构,其中每个节点包含数据以及指向下一个节点的指针。以下是一些关于单向链表的关键知识点: 1. **节点定义**:在C语言...

    C#数据结构链表

    本篇文章将深入探讨C#中的链表数据结构及其应用。 链表不同于数组,它不依赖于物理位置来存储元素。每个链表节点包含两部分:数据域,用于存储实际数据;指针域,用于指向下一个节点的地址。这种设计使得插入和删除...

    数据结构之链表,C#链表;数据结构之链表,C#链表

    在C#中,System.Collections.Generic命名空间提供了一个名为LinkedList类,用于实现链表数据结构。LinkedList类包含节点(LinkedListNode)作为链表中的元素,每个节点存储一个值,并通过引用指向下一个节点。链表...

    C#数据结构--方法及其应用以及在.NET框架中相应的算法

    ### C# 数据结构——方法及其应用以及在 .NET 框架中相应的算法 #### 第1章:数据结构和算法的基础概念及C#基础知识 - **数据结构与算法概述**:介绍数据结构与算法的基本定义及其重要性。数据结构是指一组特定...

    数据结构_顺序表_单链表_循环链表C#

    在C#中,循环链表可以用于实现如循环队列等数据结构,使得在某些情况下遍历和操作更加高效。例如,在学生成绩管理系统中,如果需要定期返回到成绩列表的开头,循环链表会是一个好选择。 对于学生成绩管理,我们可以...

    c#实例教程-数据结构篇

    在本"C#实例教程-数据结构篇"中,我们将深入探讨C#编程语言中的核心概念,特别是与数据结构相关的部分。教程将通过一系列生动的实例,如递归、循环、委托,来帮助学习者理解这些关键概念。我们将涵盖以下几个主题: ...

    数据结构-代码(C#实现)

    本篇将详细探讨在C#中实现的数据结构,包括链表、栈、队列、二叉树、图、二分查找以及排序算法。 首先,链表是线性数据结构的一种,分为单链表、双向链表和循环链表。单链表每个节点仅包含指向下一个节点的指针;...

    C#数据结构实践项目源程序

    通过这个"C#数据结构实践项目源程序",你可以学习到如何在C#环境中设计、实现和优化各种数据结构,同时提升解决问题的能力。这个项目将帮助你更好地理解数据结构的内部工作原理,以及如何在实际项目中选择和使用合适...

    c#版数据结构-石家庄景点导航

    在本项目中,“c#版数据结构-石家庄景点导航”是一个使用C#编程语言实现的数据结构课程设计。这个设计的核心是应用迪杰斯特拉(Dijkstra)算法来解决实际问题,即为石家庄的景点提供最短路径导航。下面将详细讨论...

    C#数据结构课件--数据结构

    本C#数据结构课件将带你深入探讨这个主题。 首先,我们要了解基本的数据结构类型。数组是最基础的一种,它是一系列相同类型元素的集合,通过索引进行访问。在C#中,可以使用`int[]`或`List&lt;T&gt;`等类型来创建数组。...

    C#写的数据结构库(从链表到图)

    《C#数据结构库实践详解:从链表到图》 在编程领域,掌握高效的数据结构对于提升程序性能至关重要。本篇文章将详细解析一个由C#编写的自定义数据结构库,该库涵盖了从基本的链表到复杂的图结构,为开发者提供了丰富...

    算法大全-面试题-链表-栈-二叉树-数据结构

    #### 一、链表数据结构概述 链表是一种线性数据结构,由一系列节点组成,每个节点包含数据和指向下一个节点的引用。链表分为单链表、双链表和循环链表。单链表是最基本的形式,每个节点仅包含一个指向后继节点的...

    数据结构课设报告,城市链表

    数据结构课设报告——城市链表 1. 课程设计目标与任务 1.1 课程设计目标 本课程设计的目标是让学生深入理解和掌握数据结构中的链表概念,特别是单链表的操作。问题描述为创建一个带头结点的单链表,存储不同城市...

    C#数据结构教程 C#数据结构教程

    ### C# 数据结构教程...总之,《C#数据结构教程》不仅是一本教材,也是C#开发者深入学习数据结构与算法的重要参考资料。通过对本书的学习,开发者能够更加熟悉C#语言,并掌握在.NET框架中应用数据结构与算法的方法。

    C#版数据结构实验一数据及答案

    总之,这个C#数据结构实验将涵盖多种基本和高级数据结构,通过实践操作和解答,帮助我们掌握它们的原理、实现以及在实际问题中的应用。学习过程中,不仅要理解每个数据结构的特性,还要熟悉C#中的相关类库和数据类型...

    算法大全-面试题-链表-栈-二叉树-数据结构.docx

    链表是一种线性数据结构,其中元素以节点的形式存储,每个节点包含数据和指向下一个节点的引用。在单链表中,每个节点只有一个指向后继节点的指针,而链表的末尾节点指向null。在C#中,可以使用类`Link`来表示链表...

    C#版本的数据结构--第一课

    在C#编程中,理解数据结构是构建高效算法和程序的基础。本课将探讨C#版本的数据结构,同时也包含C语言的对应内容,帮助你从不同角度深入理解这些概念。 首先,我们来讨论C#中的基本数据结构。C#中的数据结构主要...

    C# 数据结构 链表 原代码

    C# 是一种面向对象的编程语言,提供了丰富的库和工具来实现各种数据结构,包括链表。在这个C#实现的链表示例中,我们将探讨链表的基本概念、它的内部工作原理以及如何在C#中创建和操作链表。 链表不同于数组,数组...

    数据结构(C#版)----剑桥大学出版社

    ### 数据结构与算法使用C#(剑桥大学出版社) #### 一、概述 《数据结构与算法使用C#》是一本面向C#程序员的专业书籍,由迈克尔·麦克米兰(Michael McMillan)撰写,并由剑桥大学出版社出版。本书以C#语言为基础,...

    C#链表操作

    在C#中,链表是一种重要的数据结构,它在处理动态数据集合时提供了高效的操作方式。本教程将深入探讨C#中的链表操作,包括其基本概念、常见操作以及如何在实际编程中应用。 链表不同于数组,它不连续存储元素,而是...

Global site tag (gtag.js) - Google Analytics