开发编程 C#编程 C#数据结构【链表】 黄雨涵 2022-08-19 2022-08-19 前言 【此文章所有代码可在文章末尾下载查看源码 】
数据结构是计算机存储,组织数据的方式,同样也是相互之间存在一种或者多种特定关系的数据元素的集合
算法是一系列规定的计算步骤,为了实现特定的计算目的
基本数据结构一般有4类: (1)集合 (2)线性结构 (3)树形结构 (4)图形结构
集合:数据结构中的集合与数学中的集合类似,在集合中的 数据只是存在同一集合中,但其数据之间没有关系 。
线性结构:数据元素之间是一对一的关系
主要包括:线性表,栈,队列(三者的数据元素以及数据间的逻辑关系完全相同,差别就在于线性表的操作不受限制,而栈和队列的操作受到限制,栈的操作只能在表的一端进行,队列的插入操作在表的一端进行而其它操作在表的另一端进行,所以,把栈和队列称为操作受限的线性表)
树形结构:数据元素之间的层次关系是一对多
图形结构:**数据元素之间呈多对多的关系
线性表 List相关常用属性 增加/插入数据(常用): 1 2 *1.list.Add(T t)//T代表所存储的数据类型,将数据t存入链表末尾 *2.public void Insert(int index, T item);//插入数据,index代表下角标,item代表数据
查找数据(常用): 1 2 3 1.public bool Contains(T item)//查找是否包含 item 2.public T Find(Predicate<T> match); 返回满足条件的第一个值 3.public int IndexOf(T item, int index, int count);//index开始下标,count查找个数,item查找对象
删除/清除数据(常用): 1 2 3 4 5 *1.public void Clear();//清除所有数据 *2.public int RemoveAll(Predicate<T> match);//删除满足条件 *3.public bool Remove(T item);//移处数据 *4.public void RemoveAt(int index);//移除下角标为index的值 5.public void RemoveRange(int index, int count);//从下角标为index的值开始count个数
线性表的存储结构
线性表的实现方式:
顺序表 定义:线性表的顺序存储是指在内存中用一块地址连续的空间依次存放线性表的数据元素,简单说把表中的元素一个接一个地放进顺序的存储单元
顺序表要求数据要按照顺序进行存储,同理在内存中也同样是按照顺序进行存储。
顺序表的优点:用地址连续的存储单元顺序存储线性表中的各个数据元素,逻辑上相邻的数据元素在物理位置上也相邻,所以查找任何一个位置上的数据元素非常方便 ;
顺序表的缺点:进行插入和删除时,需要通过移动数据元素来实现,影响了运行效率
顺序表代码实现 【1】IListDS接口 1 2 3 4 5 6 7 8 9 10 11 12 13 public interface IListDS <T > { int GetLength () ; void Clear () ; bool IsEmpty () ; void Add (T item ) ; void Insert (T item, int i ) ; T Delete (int i ) ; T GetElem (int i ) ; T this [int index] { get ; } int Locate (T value ) ; }
【2】SeqList 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 class SeqList <T > : IListDS <T >{ public T[] data; private int count=0 ; public SeqList (int size ) { data = new T[size]; count = 0 ; } public SeqList () : this (10 ) { } public T this [int index] { get { return GetElem(index); } } public void Add (T item ) { if (count == data.Length){ Console.WriteLine("当前顺序表已经存满,不允许在存入数据" ); } else { data[count] = item; count++; } } public void Clear () { 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 T GetElem (int index ) { if (index >= 0 && index <= count - 1 ) { return data[index]; } else { Console.WriteLine("索引不存在" ); return default (T); } } public int GetLength () { return count; } 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 bool IsEmpty () { return count == 0 ; } public int Locate (T value ) { for (int i = 0 ; i < count; i++) { if (data[i].Equals(value )) { return i; } } return -1 ; } }
具体测试代码详见 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 SeqList<string > seqList = new SeqList<string >(); seqList.Add("计算机学院" ); seqList.Add("软件学院" ); seqList.Add("艺术学院" ); for (int i = 0 ; i < seqList.GetLength(); i++) { Console.WriteLine("数据{0}:{1}" , i, seqList[i]); } Console.WriteLine("顺序表长度:" +seqList.GetLength()); Console.WriteLine("顺序表中第一个数值:" + seqList.GetElem(0 )); Console.WriteLine("删除顺序表中第二个数据:" +seqList.Delete(2 )); Console.WriteLine("顺序表长度:" + seqList.GetLength()); seqList.Insert("工程学院" , 1 ); for (int i = 0 ; i < seqList.GetLength(); i++) { Console.WriteLine("添加完后的数据{0}个:{1}" , i, seqList[i]); } Console.WriteLine("顺序表长度:" + seqList.GetLength()); Console.WriteLine("数据所在位置:" +seqList.Locate("艺术学院" )+"【注:-1代表未查询到】" );
控制台输出效果 1 2 3 4 5 6 7 8 9 10 11 12 数据0:计算机学院 数据1:软件学院 数据2:艺术学院 顺序表长度:3 顺序表中第一个数值:计算机学院 删除顺序表中第二个数据:艺术学院 顺序表长度:2 添加完后的数据0个:计算机学院 添加完后的数据1个:工程学院 添加完后的数据2个:软件学院 顺序表长度:3 数据所在位置:-1【注:-1代表未查询到】
链表 优点:
一般数组都是需要一连串的内存空间来存储数据,但是链表结构不需要一连串的内存空间。此外,由于它具有的独特的结构,使得链表插入数据变得非常的快捷。因为它不需要移动后面的数据。List列表中间插入一个数据时,后面所有的数据都要进行移动。
缺点:
链表每个节点都是离散的,所以访问链表中数据只能一个接着一个访问,这需要较长的时间来查找位于链表中间或尾部的元素。访问数据效率就会变得低下。
单链表 定义:如果结点的引用域只存储该结点直接后继结点的存储地址,则该链表叫单链表
单向链表的每一个节点又包含两部分,一部分是存放数据的变量 data(值) ,另一部分是指向下一个节点的 next(下个位域)指针
单链表结点的结构如图所示
data 表示结点的数据域
next代表该引用域,即指向另一个结点
下图是线性表(a1,a2,a3,a4,a5,a6)对应的链式存储结构示意图
单链表插入某个数据时的执行效果 需要考虑插入的位置:(1)若插入的位置在头部为空时,只需将节点的next为head即可 (2)如果插入到其他部分(假设插入位置为n),则需将n-1和n位置next连接切断,将n-1的next指向新的n,新的n的next指向原本的n,即可完成单链表插入数据操作。
单链表添加某个数据时的执行效果 添加数据比插入数据较为简单,但是也需要判断head结点是否为空,如果为空的话,将新添加的结点设置为head即可,若head结点不是空的,则需要通过遍历结点,判断结点的next是否为空,如next为空,则将新的结点放到链表尾部,即可完成添加操作。
单链表移除某个数据时的执行效果 移除某个数据时,需要判断删除的位置,若删除的位置在于head,则需将head结点指向新的newNode,若删除的位置在于n个位置,则需通过for循环到所删除位置的n-1位置,将其定义为preNode,将n定义为currentNode,由于需要删除currentNode,所以要获取currentNode的next结点,也就是nextNode,将preNode的next更改为nextNode即可完成删除数据操作【这里无需考虑删除位置为末尾所导致的没有next,因为在Node构造方法中next可以】
单链表代码实现 【1】IListDS接口==>用于设定单链表所要实现的相关方法 1 2 3 4 5 6 7 8 9 10 11 public interface IListDS <T >{ int GetLength () ; void Clear () ; bool IsEmpty () ; void Add (T item ) ; void Insert (T item, int i ) ; T Delete (int i ) ; T GetElem (int i ) ; T this [int index] { get ; } int Locate (T value ) ; }
【2】Node 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Node <T >{ private T data; private Node<T> next; public T Data { get => data; set => data = value ; } internal Node<T> Next { get => next; set => next = value ; } public Node () { data=default (T); next=null ; } public Node (T value ) { data=value ; next=null ; } public Node (Node<T> next ) { this .next = next; } public Node (T data, Node<T> next ) { this .data = data; this .next = next; } }
【3】LinkList 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 class LinkList <T > : IListDS <T > { private Node<T> head; public LinkList () { head = null ; } public T this [int index] { get { Node<T> temp = head; for (int i = 1 ; i <= index; i++){ temp = temp.Next; } return temp.Data; } } public void Add (T item ) { Node<T> newNode = new Node<T>(item); if (head==null ) head = newNode; else { Node<T> temp = head; while (true ) { if (temp.Next != null ) { temp=temp.Next; } else { break ; } } temp.Next = newNode; } } public void Clear () { head=null ; } public T Delete (int index ) { T data = default (T); if (index==0 ){ data =head.Data; head=head.Next; } else { Node<T> temp = head; for (int i = 1 ; i <= index - 1 ; i++){ temp = temp.Next; } Node<T> preNode = temp; Node<T> currentNode = temp.Next; data = currentNode.Data; Node<T> nextNode = temp.Next.Next; preNode.Next = nextNode; } return data; } public T GetElem (int index ) { return this [index]; } public int GetLength () { if (head == null ) return 0 ; Node<T> temp = head; int count = 1 ; while (true ){ if (temp.Next != null ){ count++; temp = temp.Next; } else { break ; } } return count; } public void Insert (T item, int index ) { Node<T> newNode=new Node<T>(item); if (index == 0 ) { newNode.Next = head; head = newNode; } else { Node<T> temp = head; for (int i = 1 ;i<=index-1 ;i++){ temp=temp.Next; } Node<T> preNode = temp; Node<T> currentNode = temp.Next; preNode.Next = newNode; newNode.Next = currentNode; } } public bool IsEmpty () { return head == null ; } public int Locate (T value ) { Node<T> temp=head; if (temp == null ) return -1 ; else { int index = 0 ; while (true ) { if (temp.Data.Equals(value )){ return index; } else { if (temp.Next != null ) { temp = temp.Next; index++; } else { break ; } } } return -1 ; } } }
具体测试代码详见 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 nodeList.Add("计算机科学与技术" ); nodeList.Add("软件工程" ); nodeList.Add("自动化" ); for (int i = 0 ; i < nodeList.GetLength(); i++) { Console.WriteLine("数据{0}:{1}" , i, nodeList[i]); } Console.WriteLine("单链表长度:" + nodeList.GetLength()); Console.WriteLine("单链表中第一个数值:" + nodeList.GetElem(0 )); Console.WriteLine("删除单链表中第二个数据:" + nodeList.Delete(2 )); Console.WriteLine("单链表长度:" + nodeList.GetLength()); nodeList.Insert("艺术与实践" , 1 ); for (int i = 0 ; i < nodeList.GetLength(); i++) { Console.WriteLine("添加完后的数据{0}个:{1}" , i, nodeList[i]); } Console.WriteLine("单链表长度:" + nodeList.GetLength()); Console.WriteLine("数据所在位置:" + nodeList.Locate("软件工程" ) + "【注:-1代表未查询到】" );
控制台输出效果 1 2 3 4 5 6 7 8 9 10 11 12 数据0:计算机科学与技术 数据1:软件工程 数据2:自动化 单链表长度:3 单链表中第一个数值:计算机科学与技术 删除单链表中第二个数据:自动化 单链表长度:2 添加完后的数据0个:计算机科学与技术 添加完后的数据1个:艺术与实践 添加完后的数据2个:软件工程 单链表长度:3 数据所在位置:2【注:-1代表未查询到】
双链表 含义: 双向链表其元素指向它前面和后面的元素。它的每一个节点除了拥有 data 和 next 指针,还拥有指向前置节点的 prev (上个位域)指针
特性: 1)LinkedList 无法通过下标查找元素 ,在查找链表元素时,总是从头结点开始查找。
2)LinkedList 的容量是链表最大包含的元素数,会根据元素增减而动态调整容量 。
3)LinkedList 中的每个节点 都属于 LinkedListNode 类型 。
4)LinkedList 的值可以为 null,并允许重复值 。
5)LinkedList **不自带排序方法。