XIAOSUO 记录个人学习的足迹

摘要：一、概述 LIFO: Last In, First Out（后进先出） 受限的线性表，它插入和删除只能在表的一端进行 所有插入和删除操作都只能在表的一端进行，这一端叫栈顶。 最后进入栈中的数据最先被拿走。 二、栈的操作 1.初始化栈： 产生一个新的空栈。 2.入栈操作Push(T item)： 将指定类型元素data进到栈中。 3.出栈操作Pop()： 将栈中的栈顶元素取出来，并在栈中删除栈顶元素。 4.取栈顶元素GetTop()： 将栈中的顶元素取出来，栈中元素不变。 5.判断栈空IsEmpty()： 若栈为空，返回true，否则返回false。 6.清空操作Clear()： 从栈中清除所有的数据元素。 三、栈的顺序表示和实现 用一片连续的存储空间来存储栈中的数据元素，这样的栈称为顺序栈。类似与顺序表，用一维数组来存放顺序栈中的数据元素。栈顶指示器top设在数组下标为0的端，top随着插入和删除而变化，当栈为空时，top=-1。 基本运算在顺序栈上的实现如下： public class SeqStackT { private int maxsize; //顺序栈的容量 private T[] data; //数组，用于存储顺序栈中的数据元素 private int top; //指示顺序栈的栈顶 //索引器 public T this[int index] { get { return data[index]; } set { data[index] = value; } } public int Maxsize { get { return maxsize; } set { maxsize = value; } } public int Top { get { return top; } } public SeqStack(int size) { data = new T[size]; maxsize = size; top = -1; } public void Push(T elem) { if (IsFull()) { throw new Exception(容…… 阅读全文

摘要：一、结点为LinkedListNode对象 该对象的实现如下 //在LinkedListT中LinkedListNodeT相互之间构成双向环状链表 //该双向环状链表通过内部成员next、prev来实现，但对于外部不可见 //对于外部Next、Previous表现为双向链表，首尾不构成环 public sealed class LinkedListNodeT { internal LinkedListT list; internal LinkedListNodeT next; internal LinkedListNodeT prev; internal T item; public LinkedListNode(T value) { this.item = value; } internal LinkedListNode(LinkedListT list, T value) { this.list = list; this.item = value; } public LinkedListT List { get { return list; } } public LinkedListNodeT Next { get { return next == null || next == list.head ? null : next; } } public LinkedListNodeT Previous { get { return prev == null || this == list.head ? null : prev; } } public T Value { get { return item; } set { item = value; } } internal void Invalidate() { list = null; next = null; prev = null; } } 二、外部表现为双向线性链表，内部实现实际为双向环状链表 通过LinkedListNode的实现代码我们可以知道该对象对外通过Next,Previous对next，previous包装实现（Next,Previous均为只读），首尾不相接构成环。而对内next…… 阅读全文

摘要：一、采用数组保存数据 部分私有成员如下： public class ListT : IListT, System.Collections.IList { private const int _defaultCapacity = 4; //初始list大小 private T[] _items; //list数据项保存的数组 private int _size; //数据项的实际个数 private int _version; //数据项被修改过的次数,主要用户枚举过程中对于数据的修改 static T[] _emptyArray = new T[0]; //................其他部分 ｝ 数据项查找复杂度为O(n)； public int IndexOf(T item) { return Array.IndexOf(_items, item, 0, _size); } 下标查找复杂度为O(1)； 二、当数据空间不够时，扩大1倍空间 带来O(n)的数据复制开销。最坏可能带来sizeof(T)*(n-1)的空间浪费（可以使用TrimExcess来缩紧）。 //获取与设置保存数据项数组的长度，注意在设置长度时所带来的开销 public int Capacity { get { return _items.Length; } set { if (value != _items.Length) { if (value _size) { ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.value, ExceptionResource.ArgumentOutOfRange_SmallCapacity); } if (value 0) { //注意_size个元素复制开销,与原有对象丢弃后可引起cc启动的开销 T[] newItems = new T[value]; if (_size 0) { …… 阅读全文

摘要：这篇文章是一些与线性表相关的算法 1.如果顺序表中每个元素都是整数，设计用最少时间把所有值为负数的元素放在全部正数值元素的前面。 2.如果顺序表为非递减有序排列，试删除顺序表中多余的值相同的元素。 3.编写一个单链表逆置算法。 4.找出单链表的中间元素。 1.如果顺序表中每个元素都是整数，设计用最少时间把所有值为负数的元素放在全部正数值元素的前面。 分析：从左向右找到正数，从右到左找到负，将两者交换。循环直到 i 大于 j 为止。 public void Move(int[] list) { int i = 0, j = list.Length; int temp; while (i = j) { while (list[i] = 0) i++; while (list[j] = 0) j--; if (i j) { temp = list[i]; list[i] = list[j]; list[j] = temp; } } } 注意：①“用最少的时间”一词，②只要求将负数的元素移动到全部正数的前面。 2.如果顺序表为非递减有序排列，试删除顺序表中多余的值相同的元素。 分析：由于顺序表是非递减有序排序，值相同的元素必为相邻的元素，因此依次比较相邻两个元素，若值相等则删除其中一个，否则继续向后查找。 public void Delete(int[] list) { int i = 0, j, len = list.Length; while (i len - 1) { if (list[i] != list[i + 1]) { i++; } else { for (j = i; j len; j++) { list[j] = list[j + 1]; } } } } 注意：顺序表删除一个元素的实现方法。 3.编写一个单链表逆置算法。 分析：我们需要额外的两个变量来存储当前节点curr的下一个节点next、再下一个节点nextnext； public static Link Reverse(NodeT head) { NodeT curr = head.Next; NodeT next = null; NodeT nextnext = nu…… 阅读全文

摘要：一、双向链表的表示 双链表是结点有两个引用域的链表：一个指向直接后继结点，一个指向直接前驱结点。这种类型定义如下： public class DNodeT { private T data; private DNodeT prev; private DNodeT next; public DNode(T data, DNodeT next) { this.data = data; this.next = next; } public DNode(T data) { this.data = data; this.next = null; } public DNode(DNodeT next) { this.next = next; } public DNode() { this.data = default(T); this.next = null; } public T Data { get { return this.data; } set { this.data = value; } } public DNodeT Next { get { return this.next; } set { this.next = value; } } public DNodeT Prev { get { return this.prev; } set { this.prev = value; } } } 二、双向链表的实现 在双链表中，有些操作(如取元素、定位等)算法中仅涉及后继结点，此时双向链表的算法和单链表的算法均相同，但对插入、删除操作，双向链表需同时修改后继和前驱两个引用，比单链表要复杂一些，其操作如下： public class DLinkListT { private DNodeT start; private int length; public DLinkList() { start = null; } public int Length { get { return this.length; } } public void InsertNode(T data) { if (start == null) …… 阅读全文

摘要：一、链表概述 线性表的链式表示就是采用链表实现存储，即表中数据元素是用一组任意的存储单元存储，它不要求逻辑上相邻的元素在物理位置上也相邻。这种数据结构有以下优点：其一，在进行插入和删除操作时，无需移动大量元素；其二，给长度变化较大的线性表无需预先分配最大空间；其三，表容量容易扩充。链表的特点是用一组任意的存储单元存储线性表的数据元素。因此，为了表示每个数据元素ai与其直接后继数据元素ai+1间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需要存储一个指示其直接后继的信息。这两部分信息组成数据元素ai的存储映像，称为结点(Node)。 二、线性表的链式表示之单链表 由n个结点链接起来，且每个节点只包含一个引用域的链表称为单链表。 对单链表进行操作 1.初始化单链表 步骤： a.声明一个为结点类型的start变量，用来指向单链表的第一个结点。 b.在单链表的构造函数中将start变量的值赋为null。 2.插入操作 步骤： ①在单链表开头插入新的结点 a.为新结点分配内存并为数据字段分配值。 b.使新结点的next字段指向列表中的第一个结点。 c.是start指向新结点。 ②在单链表两个结点之间插入结点 a.为新结点分配内存并为数据字段分配值。 b.确定要在那两个结点之间插入新结点。将它们标记为前结点previous和当前结点current。找到前一个和当前结点，请执行步骤： ⑴.使previous指向null； ⑵使current指向第一个结点； ⑶如果新结点的序号大于当前结点的值，重复步骤⑷、⑸； ⑷使previous指向current； ⑸使current指向序列中的下一个结点。 c.使新结点的next字段指向当前结点。 d.使前一个结点的next字段指向新结点。 ③在单链表末尾插入一个新结点 a.为新结点分配内存并为数据字段分配值。 b.找到列表中的最后一个结点，将它标记为current。 c.是current的next字段指向新结点。 d.使新结点的next字段指向null，释放current空间。 3.删除操作 步骤： ①在单链表开头删除结点 a.将列表中的一个结点标记为当前结点。 b.使start指向单链表中的下一个结点。 c.释放标记为当前结点的内存。 ②在单链表两个结点之间删除结点 a.定位要删除的结点，请执行步骤： ⑴.将previ…… 阅读全文

摘要：一、线性表概念 一个线性表由有限且有序的数据项组成。数据项称为元素。 每个表元素有相同的类型。 空表不含任何元素。 线性表的长度定义为表中所含元素的个数。 表的第一个元素称为表头。 表的最后一个元素称为表尾。 有序表是指表中元素的值按位置顺序递增或递减。 无序表是指表中元素的值与位置没有关系。 表的表示: ( a0, a1, …, an-1) 二、线性表的操作 1.初始化操作 初始条件：线性表不存在。 操作结果：创建一个空的线性表。 2.插入操作：InsertNode(T a, int i) 初始条件：线性表存在，插入位置正确(i= i =n+1,n为插入前的表长)。 操作结果：在线性表的第i个位置上插入一个值为 a 的新元素，这样使得原序号为 i,i+1,...,n的数据元素的序号变为 i+1,i+2,...,n+1，插入后表长为 n+1。 3.删除操作：DeleteNode(int i) 初始条件：线性表存在且不为空，删除位置正确(1= i =n,n为删除前的表长)。 操作结果：在线性表中删除序号为 i 的数据元素，返回删除后的数据元素。删除后使得原序号为 i+1,i+2,...,n的数据元素的序号变为 i,i+1,...,n-1，插入后表长为 n-1。 4.取表元素：SearchNode(int i) 初始条件：线性表存在，所取数据元素位置正确(1= i =n,n为线性表的表长)。 操作结果：返回线性表中第 i 个数据元素。 5.定位元素：SearchNode(T value) 初始条件：线性表存在。 操作结果：在线性表中查找值为value的数据元素，其结果返回在线性表中首次出现的值为value的数据元素的序号，称为查找成功；否则，线性表中未找到值为value的数据元素，返回一个特殊值表示查找失败。 6.求表长：GetLength() 初始条件：线性表存在。 操作结果：返回线性表中所有数据元素的个数。 7.清空操作：Clear() 初始条件：线性表存在且有数据元素。 操作结果：从线性表中清除所有数据元素，线性表为空。 8.判断线性表是否为空：IsEmpty() 初始条件：线性表存在。 操作结果：如果线性表中不包含任何元素则返回true，否则返回false。 三、线性表的顺序表示 线性表的顺序表示指的是一组地址连续的存储单元依次存储线性表的数据元素。顺序表的…… 阅读全文

摘要：一天一个重构方法（1）：Extract Method 一天一个重构方法（2）：Inline Method 一天一个重构方法（3）：Switch to Strategy 一天一个重构方法（4）：Break Dependencies 一天一个重构方法（5）：Introduce Explaining Variable 一天一个重构方法（6）：Extract Method Object 一天一个重构方法（7）：Break Responsibilities 一天一个重构方法（8）：Encapsulate Conditional 一天一个重构方法（9）：Substitute Algorithm 一天一个重构方法（10）：Rename Method 一天一个重构方法（11）：Add Parameter 一天一个重构方法（12）：Remove Parameter 一天一个重构方法（13）：Remove Arrowhead Antipattern 一天一个重构方法（14）：Parameterize Method 一天一个重构方法（15）：Replace Parameter with Explicit Methods 一天一个重构方法（16）：Remove Double Negative 一天一个重构方法（17）：Return ASAP 一天一个重构方法（18）：Introduce Parameter Object 一天一个重构方法（19）：Replace Error Code with Exception 一天一个重构方法（20）：Replace Exception with Test 一天一个重构方法（21）：Replace Constructor with Factory Method 一天一个重构方法（22）：Encapsulate Downcast 一天一个重构方法（23）：Introduce Design By Contract 一天一个重构方法（24）：Extract class 一天一个重构方法（25）：Pull Up Field 一天一个重构方法（26）：Pull Up Mothod 一天一个重构方法（27）：Push Down Field 一天一个重构方法（28）：Push Down Method 一天一个重构方法（29）：Remove God Classes …… 阅读全文