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

本文涉及的产品
传统型负载均衡 CLB,每月750个小时 15LCU
网络型负载均衡 NLB,每月750个小时 15LCU
应用型负载均衡 ALB,每月750个小时 15LCU
简介: 1.单链表的定义和由来:  链表是用一组地址可能连续也可能不连续的存储单元来存储线性表中的数据元素,在存储数据元素时,除了要存储数据元素本身之外,还要存储与它相邻的数据元素的地址信息,这两部分组成了线性表中一个数据元素的映像,称之为"结点",存储数据元素本身的部分称之为:数据域,存储相邻数据元素地...

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;

}
相关实践学习
SLB负载均衡实践
本场景通过使用阿里云负载均衡 SLB 以及对负载均衡 SLB 后端服务器 ECS 的权重进行修改,快速解决服务器响应速度慢的问题
负载均衡入门与产品使用指南
负载均衡(Server Load Balancer)是对多台云服务器进行流量分发的负载均衡服务,可以通过流量分发扩展应用系统对外的服务能力,通过消除单点故障提升应用系统的可用性。 本课程主要介绍负载均衡的相关技术以及阿里云负载均衡产品的使用方法。
目录
相关文章
|
28天前
|
存储 算法
【数据结构和算法】--- 二叉树(4)--二叉树链式结构的实现(2)
【数据结构和算法】--- 二叉树(4)--二叉树链式结构的实现(2)
17 0
|
14天前
|
存储 DataX C语言
【数据结构】单链表
数据结构中的单链表
13 0
【数据结构】单链表
|
28天前
【数据结构】链式二叉树的层序遍历
【数据结构】链式二叉树的层序遍历
22 5
|
28天前
|
存储 测试技术
【数据结构】手把手分析:链式二叉树的实现
【数据结构】手把手分析:链式二叉树的实现
21 5
|
28天前
|
存储 测试技术
【数据结构】操作受限的线性表,栈的具体实现
【数据结构】操作受限的线性表,栈的具体实现
30 5
|
28天前
|
存储 测试技术
【数据结构】最最基础的链式结构——单链表,还不会你就吃大亏了!
【数据结构】最最基础的链式结构——单链表,还不会你就吃大亏了!
23 5
|
28天前
|
存储 测试技术
【数据结构】操作受限的线性表,队列的具体实现
【数据结构】操作受限的线性表,队列的具体实现
23 4
|
17天前
|
Dart 算法 JavaScript
C#数据结构与算法入门教程,值得收藏学习!
C#数据结构与算法入门教程,值得收藏学习!
|
27天前
|
算法 程序员 数据处理
【数据结构与算法】使用单链表实现队列:原理、步骤与应用
【数据结构与算法】使用单链表实现队列:原理、步骤与应用
|
27天前
|
算法 C语言
【数据结构与算法 经典例题】返回单链表的倒数第 k 个节点
【数据结构与算法 经典例题】返回单链表的倒数第 k 个节点