白亮吖雅黑丫の小站 - 数据结构
type: channel
link: https://www.520315.xyz/tag/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/
items: 数据结构之Dijkstra算法
items: 数据结构之Kruskal算法
items: 数据结构之Prim算法
items: 数据结构之无向图的遍历
items: 数据结构之排序算法的学习
items: 数据结构之二叉堆与优先队列
items: 数据结构之二叉树的遍历
items: 数据结构之单链表
items: 数据结构之顺序表

数据结构之Dijkstra算法
type: item
date: 2019-12-14T14:32:00+08:00
description: Dijkstra算法求最短生成路径简介最短路径：在网图中，两顶点之间经历的边上权值之和最少的路径。Dijkstra算法： 迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径。它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。基本思想：1.初始化数组dist,path和s2.while(s中的元素个数<n)在dist[n]中求最小值，其编号为k；输出dist[k]和path[k]修改数组dist和path将顶点k添加至数组s该有向图如下：求最短生成路径各分量的变化代码实现此处我采用邻接矩阵储存该有向图，为了省时间（其实是自己懒 ），此处省略邻接矩阵的构造过程，采用手动写入边集构建该有向图。MGraph类package Dijkstra; /** * @Author {zbl} * @Date: 2019/12/14/ 13:04 * @Description */ public class MGragh { public static final int INT_MAX= 0x7ffffff; //邻接矩阵，边集 public int[][] arc = { {INT_MAX,10,INT_MAX,30,100}, {INT_MAX,INT_MAX,50,INT_MAX,INT_MAX}, {INT_MAX,INT_MAX,INT_MAX,INT_MAX,10}, {INT_MAX,INT_MAX,20,INT_MAX,60}, {INT_MAX,INT_MAX,INT_MAX,INT_MAX,INT_MAX} }; //顶点数 public int vertexNum = 5; //空构造方法 public MGragh(){} } 主函数：package Dijkstra; import java.nio.file.attribute.DosFileAttributes; import java.util.ArrayList; import java.util.List; /** * @Author {zbl} * @Date: 2019/12/14/ 13:02 * @Description */ public class Main { /** * @Description: 主函数 * @Param: [args] * @return: void * @Author: {zbl} * @Date: 2019/12/14 */ public static void main(String[] args){ MGragh g = new MGragh(); Dijkstra(g,0); } /** * @Description: Dijkstra算法 * @Param: [mGragh, n] * @return: void * @Author: {zbl} * @Date: 2019/12/14 */ public static void Dijkstra(MGragh mGragh,int n){ //加入的顶点集 List<Integer> v = new ArrayList<>(); //路径 String[] path = new String[mGragh.vertexNum]; //边集权值 int[] dist = new int[mGragh.vertexNum]; //初始化dist,path for (int i = 0; i<mGragh.vertexNum; ++i){ dist[i] = mGragh.arc[n][i]; if(dist[i]!=MGragh.INT_MAX) path[i] = "V"+n+"V"+i; else path[i] = ""; } v.add(n); //点集中元素个数少于顶点数 while(v.size()<mGragh.vertexNum){ int k,i; //找到dist中最小的 for (k=0,i = 1; i<mGragh.vertexNum; ++i){ if(dist[i]!=0 && dist[i]<dist[k]) k=i; } //输出dist和path System.out.println(dist[k]+" "+path[k]); v.add(k); //更新dist和path数组 for (i = 0; i<mGragh.vertexNum; ++i){ if(dist[i]>dist[k] + mGragh.arc[k][i]){ dist[i] = dist[k] + mGragh.arc[k][i]; path[i] = path[k] + "V" + i…

数据结构之Kruskal算法
type: item
date: 2019-11-23T22:39:00+08:00
description: Kruskal算法求最小生成树简介上一篇博客介绍了用Prim算法求无向图的最小生成树，Prim算法适合用求稠密网的最小生成树，那么当网内的边较少时Prim算法显然就不适用了，于是Kruskal算法便随之诞生了。Kruskal算法是求最小生成树的一种方法，适用于求稀疏网的最小生成树。Kruskal算法的基本思想是：1、初始化：U=V； TE={}；2、重复下述操作直到T中的连通分量个数为1：2.1 在E中寻找最短边（u，v），且满足u∈U，v∈V；2.2 如果顶点u,v位于T的两个不同连通分量，则 2.2.1 将边（u，v）并入TE；2.2.2 将这两个连通分量合为一个；2.3 在E中标记边（u，v）,使得（u，v）不参加后续最短边的选取显然，实现Kruskal算法的关键之处在于：如何叛变被考察边的两个顶点是否位于两个连通分量（即是否与生成树中的 边形成回路）求最小生成树的步骤无向图如下图所示Kruskal算法求最小生成树的步骤：代码实现此处我采用邻接矩阵储存该无向图，边集储存该图中的边，为了省时间（其实是自己懒 ），此处省略邻接矩阵的构造过程，采用手动构建该无向图，通过无向图构建边集。Kruskal算法代码实现： /** * Kruskal算法 * @param G */ public static void Kruskal(EdgeGraph G){ int[] parent = new int[G.vertexNum]; //初始化parent数组 for (int i = 0; i<G.vertexNum;++i){ parent[i] = -1; } for (int num = 0,i = 0; i<G.edgeNum; ++i){ int vex1 = FindRoot(parent,G.edge[i].from); int vex2 = FindRoot(parent,G.edge[i].to); if(vex1 != vex2){ //输出加入的边 System.out.println("(" + G.edge[i].from + "," + G.edge[i].to + "),weight:" + G.edge[i].weight); //合并生成树 parent[vex2] = vex1; ++num; if (num == G.vertexNum-1) return; } } }完整代码无向图存储类EdgeGraphpackage Kruskal; /** * @Author zbl * @Date: 2019/11/23/ 17:33 * @Description */ public class EdgeGraph { int[] vertex = new int[7]; Edge[] edge = new Edge[9]; int vertexNum = 7; int edgeNum = 9; public EdgeGraph(){ //此处省略构造过程 for (int i = 0; i<vertexNum;++i) vertex[i] = i; int[][] arc ={ {0,5,6,0,0,0,0}, {5,0,0,2,0,3,0}, {6,0,0,0,2,0,0}, {0,2,0,0,0,6,3}, {0,0,2,0,0,0,9}, {0,3,0,6,0,0,8}, {0,0,0,3,9,8,0} }; int count = 0; for (int i = 0;i<7; ++i){ for (int j = i; j<7; ++j){ if(arc[i][j]!=0){ edge[count] = new Edge(); edge[count].from = i; edge[count].to = j; edge[count++].weight = arc[i][j]; } } } //记录最后一次交换的位置 int lastExchangeIndex = 0; //无序数列的边界，每次只需比较到这里为止 int sortBorder = edge.length - 1; for (int i = 0;i<edge.length - 1;++i){ boolean flag = true; for (int j = 0;j<sortBorder;++j){ if(edge[j].weight > edge[j+1].weight){ Edge tmp = edge[j]; edge[j] = edge[j+1]; edge[j+1] = tmp; //更新最后一次交换的位置 lastExchangeIndex = j; flag = false; } } //更新边界 sortBorde…

数据结构之Prim算法
type: item
date: 2019-11-22T16:58:00+08:00
description: Prim算法求最小生成树简介最小生成树： 一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边 （边的代价和最小）Prim算法是求最小生成树的一种方法，由于Prim算法的复杂度与边的数量无关，于是较适用于求稠密网的最小生成树。Prim算法的基本思想是：1、初始化：U={v0}； TE={}；2、重复下述操作直到U=V：2.1 在E中寻找最短边（u，v），且满足u∈U，v∈V；2.2 U=U+{v}；2.3 TE=TE+{ (u，v) }；求最小生成树的步骤无向图如下图所示Prim算法求最小生成树的步骤：代码实现此处我采用邻接矩阵储存该无向图，为了省时间（其实是自己懒 ），此处省略邻接矩阵的构造过程，采用手动写入边集和点集构建该无向图。Prim算法代码实现： /** * Prim算法 * @param G 无向图 * @param shortEdge 辅助边集 */ public static void Prim(MGraph G, ShortEdge[] shortEdge){ //初始化辅助数组 for (int i = 0;i<G.vertexNum;++i){ shortEdge[i].lowcast = G.arc[0][i]; shortEdge[i].adjvex = i; } //将顶点0加入集合U shortEdge[0].lowcast = 0; //建立辅助顶点集合 int[] verctor = new int[G.vertexNum]; verctor[0]++; for (int i = 1;i<G.vertexNum;++i){ //寻找最短边的邻接点k int k = MinEdge(shortEdge,G.vertexNum); //打印 System.out.println("(顶点：" + k + ",边的权值：" + shortEdge[k].lowcast + ")"); //将顶点k加入集合U shortEdge[k].lowcast = 0; verctor[k]++; for (int j = 0;j<G.vertexNum;++j){ //若该点已加入集合U,则跳过该点 if(verctor[j]>0) continue; //更新辅助数组,选取最新的邻接边更新至辅助数组 if ((G.arc[k][j]<shortEdge[j].lowcast || shortEdge[j].lowcast==0 )&& G.arc[k][j]!=0){ shortEdge[j].lowcast = G.arc[k][j]; shortEdge[j].adjvex = j; } } } }完整代码无向图存储类MGraphpackage Prim; /** * @Author zbl * @Date: 2019/11/21/ 10:52 * @Description */ public class MGraph { //边集 public int[][] arc ={ {0,5,6,0,0,0,0}, {5,0,0,2,0,3,0}, {6,0,0,0,2,0,0}, {0,2,0,0,0,6,3}, {0,0,2,0,0,0,9}, {0,3,0,6,0,0,8}, {0,0,0,3,9,8,0} }; //顶点数 public int vertexNum = 7; //空构造函数 public MGraph(){}; } 储存最短边的辅助类：package Prim; /** * @Author zbl * @Date: 2019/11/21/ 11:04 * @Description */ public class ShortEdge { //权值 public int lowcast; //邻接点 public int adjvex; }主要代码：package Prim; /** * @Author zbl * @Date: 2019/11/21/ 10:50 * @Description */ public class Main { //主函数 public static void main(String[] args) { //建立辅助数组 ShortEdge[] shortEdges = new ShortEdge[7]; for(int i = 0;i<7;++i){ shortEdges[i] = new ShortEdge(); } Prim(new MGraph(),shortEdges); } /** * Prim算法 * @param G 无向图 * @param shortEdge 辅助边集 */ pub…

数据结构之无向图的遍历
type: item
date: 2019-11-18T15:06:00+08:00
description: 欢迎移步博主CSDN：CSDN博客无向图的两种遍历算法的实现简介图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为$$ G = (V,E) $$如果图的任意两个顶点之间的边都是无向边，则称该图为无向图,否则称该图为有向图。图的两种遍历算法思想深度优先遍历算法思想 （1）访问顶点v； （2）从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历； （3）重复上述两步，直至图中所有和v有路径相通的顶点都被访问到广度优先遍历算法思想 （1）访问顶点v； （2）依次访问v的各个未被访问的邻接点v1，v2，v3...... （3）分别从v1，v2，v3......出发依次访问它们未被访问的邻接点，并使先被访问顶点的邻接点先于后被访问顶点的邻接点被访问。直至图中所有与顶点v有路径相通的顶点都被访问到。采用邻接矩阵存储图的邻接矩阵存储也称为数组表示法，其方法是用一个以为数组存储图中顶点的信息，用一个二维数组存储图中边的信息，存储顶点之间临界关系的二维数组称为邻接矩阵。以下面这个无向图为例进行实现该无向图的DFS访问顺序：V0->V1->V4->V5->V2->V3该无向图的BFS访问顺序：V0->V1->V2->V3->V4->V5为了省时间（其实是自己懒 ），此处省略邻接矩阵的构造过程，采用手动写入边集和点集构建该无向图。 //手动构造图的点集和边集 //点集 int[] vector = { 0,1,2,3,4,5 }; //边集 int[][] arc ={ {0,1,1,1,1,0}, {1,0,0,0,1,0}, {1,0,0,0,1,0}, {1,0,0,0,0,0}, {1,1,1,0,0,1}, {0,0,0,0,1,1} }; //记录是否访问 int[] visited = { 0,0,0,0,0,0 };深度优先遍历（递归实现） //图的深搜DFS,递归 public static void DFS(int[] vector, int[] visited, int[][] arc,int i){ //访问结点并标记 System.out.println(vector[i]); visited[i]=1; for (int j = 0;j<vector.length; ++j){ if (visited[j]==0 && arc[i][j]==1) DFS(vector,visited,arc,j); } } 深度优先遍历 （非递归实现）//图的深搜DFS ,非递归 public static void DFS(int[] vector, int[] visited, int[][] arc){ //访问第一个顶点并入栈 System.out.println(vector[0]); Stack<Integer> stack = new Stack<Integer>(); stack.push(0); visited[0] = 1; while(!stack.isEmpty()){ //获取栈顶元素 int x = stack.peek(); //标志位 boolean flag = false; for (int i = 0; i<vector.length;++i){ if (visited[i]==0 && arc[x][i]==1){ System.out.println(vector[i]); //入栈 stack.push(i); //更改访问位,标志位 visited[i] = 1; flag = true; break; } } //出栈 if (!flag) stack.pop(); } } 广度优先遍历//图的广搜BFS,非递归 public static void BFS(int[] vector, int[] visited, int[][] arc){ Queue<Integer> queue = new LinkedList<Integer>(); //第一个顶点入队 queue.offer(0); while (!queue.isEmpty()){ //出队 int x = queue.poll(); //访问结点并标记 System.out.println(vector[x]); visited[x] = 1; //寻找连通的结点并入队 for (int i = 0; i<vector.length;++i){ if (visited[i]==0 && arc[x][i]==1){ queue.offer(i); visited[i] = 1; } } } }采用邻接表存储图的邻接表存储是一种顺序存储与链接存储相结合的存储方法，类似于数的孩子链表表示法。对于图的每个顶点v，…

数据结构之排序算法的学习
type: item
date: 2019-11-15T13:09:00+08:00
description: 欢迎移步博主CSDN：CSDN博客数据结构之排序算法冒泡排序简介冒泡排序，又名起泡排序，顾名思义，就如同气泡从水中不断上浮一样。其算法思想为元素从数列头开始依次往数列尾进行比较，第一遍将最大的元素放置于数列尾的有序区，接着再从数列头的无序区中找到第二大的元素置于数列尾的有序区，如此进行下去，直至数列中所有元素有序。算法复杂度时间复杂度：O(n²)空间复杂度：O(1)代码实现Java代码实现：//冒泡排序 public static void sort(int[] array) { //记录最后一次交换的位置 int lastExchangeIndex = 0; //无序数列的边界，每次只需比较到这里为止 int sortBorder = array.length - 1; for (int i = 0; i < array.length - 1; ++i) { boolean flag = true; for (int j = 0; j < sortBorder; ++j) { if (array[j] > array[j + 1]) { array[j] = array[j] ^ array[j + 1]; array[j + 1] = array[j] ^ array[j + 1]; array[j] = array[j] ^ array[j + 1]; //更新最后一次交换的位置 lastExchangeIndex = j; flag = false; } } //更新边界 sortBorder = lastExchangeIndex; if (flag) break; } }冒泡改进之鸡尾酒排序简介由于冒泡排序每一轮都是从左至右来比较元素，只能单向的进行位置交换，在碰见{2,3,4,5,6,7,8,1}这样的数组时，使用冒泡排序还需进行7轮排序，效率比较低下。而我们当然是不希望这种情况的出现啦，由此鸡尾酒排序算法便诞生了!鸡尾酒排序算法和冒泡排序的不同之处在于遍历算法由单向遍历改为双向遍历，这样能避免出现前端基本有序的数列遍历时效率低下的问题，那么双向遍历究竟是怎样的呢？ 下面将为大家详细说明。鸡尾酒排序第一轮和冒泡排序一样，也是从左至右比较元素，而到了第二轮时，则反过来从右至左开始比较元素，这样往复，直至数列全部有序。鸡尾酒排序的过程就像钟摆一样，第一轮从左至右，第二轮从右往左，第三轮再从左至右······像{2,3,4,5,6,7,8,1}这样的数列，使用鸡尾酒排序只用3轮遍历就已经解决了！复杂度时间复杂度：O(n²)空间复杂度：O(1)代码实现Java代码实现//鸡尾酒排序 public static void jwSort(int[] array) { for (int i = 0; i < array.length / 2; ++i) { boolean flag = true; //奇数轮，从左往右 for (int j = i; j < array.length - 1; ++j) { if (array[j] > array[j + 1]) { array[j] = array[j] ^ array[j + 1]; array[j + 1] = array[j] ^ array[j + 1]; array[j] = array[j] ^ array[j + 1]; flag = false; } } if (flag) break; //重置标记 flag = true; //偶数轮，从右往左 for (int j = array.length - 1; j > i; --j) { if (array[j] < array[j - 1]) { array[j] = array[j] ^ array[j - 1]; array[j - 1] = array[j] ^ array[j - 1]; array[j] = array[j] ^ array[j - 1]; flag = false; } } if (flag) break; } }补充说明鸡尾酒排序的优点是能够在特定的条件下，减少排序的回合数；而缺点也很明显，就是代码量几乎增加了1倍。至于它能发挥出优势的场景，是大部分元素已经有序的情况。快速排序上面介绍的算法时间复杂度都为O(n²),那么有没有比它们更快的算法呢？现在我们介绍一种时间复杂度为O(nlogn)的算法---快速排序简介快速排序之所以快，是因为它使用了分治法，将大问题划分为小问题，分而治之。快速排序和冒泡排序一样，也属于交换排序，通过元素之间的比较和交换位置来达到排序的目的。不同的是，冒泡排序在每一轮中只把一个元素冒泡到数列的一端，而快速排序则在每一轮挑选一个基准元素，并让其他比它打的…

数据结构之二叉堆与优先队列
type: item
date: 2019-11-04T20:46:00+08:00
description: 欢迎移步博主CSDN：CSDN博客数据结构之二叉堆与优先队列的学习简介二叉堆本质上是一种完全二叉树，采用顺序结构进行存储，它分为两种类型最大堆最小堆最大堆的任何一个节点都大于或等于它的左右孩子节点最小堆的任何一个节点都小于或等于它的孩子节点二叉堆的用途与基本操作的实现二叉堆是实现堆排序和优先队列的基础。下面我们将用代码实现最小堆的上浮，下沉操作完整java代码二叉堆Heap类基本操作代码实现：package com.dataStructure.Heap; import java.lang.reflect.Array; import java.util.Arrays; /** * author zbl * * datetime 2019.11.4 * */ //二叉堆 public class Heap { //采用数组存储二叉堆 private int [] array; @Override public String toString() { return "Heap{" + "array=" + Arrays.toString(array) + '}'; } //构造函数 public Heap(int [] array , int length){ this.array = Arrays.copyOf(array,length); } //上浮调整 public void upAdjust(){ int childIndex = array.length - 1; int parentIndex = (childIndex - 1) / 2; //暂存最后一个节点数据 int tmp = array[childIndex]; //小顶堆 while(childIndex > 0 && tmp<array[parentIndex]){ array[childIndex] = array[parentIndex]; childIndex = parentIndex; parentIndex = (childIndex - 1) / 2; } array[childIndex] = tmp; } //下沉调整 public void downAdjust(int parentIndex){ int childIndex = parentIndex * 2 + 1; int tmp = array[parentIndex]; while(childIndex < array.length - 1){ //如果有右孩子，且右孩子小于左孩子，则定位到右孩子 if(childIndex + 1 < array.length && array[childIndex + 1] < array[childIndex]) childIndex++; //如果父节点最小，跳出 if(tmp <= array[childIndex]) break; //父节点下沉 array[parentIndex] = array[childIndex]; parentIndex = childIndex; childIndex = parentIndex * 2 + 1; } array[childIndex] = tmp; } } 主函数： package com.dataStructure; import com.dataStructure.Heap.Heap; /** * author zbl * * datetime 2019.11.4 * */ public class Main { public static void main(String[] args) { int[] array = new int[]{8,7,6,5,4,3,2,1}; Heap heap = new Heap(array,8); heap.upAdjust(); System.out.println(heap.toString()); } } 优先队列的实现最大优先队列,无论入队顺序如何,都是当前优先级最大的元素优先出队最小优先队列,无论入队顺序如何,都是当前优先级最小的元素优先出队下面是最小优先队列的实现代码二叉堆Heap类基本操作代码实现：package com.dataStructure.Heap; import java.lang.reflect.Array; import java.util.Arrays; /** * author zbl * * datetime 2019.11.5 * */ //二叉堆 public class Heap { //采用数组存储二叉堆 protected int [] array; //队列实际长度 protected in…

数据结构之二叉树的遍历
type: item
date: 2019-11-04T15:27:00+08:00
description: 欢迎移步博主CSDN：CSDN博客数据结构之树与二叉树的学习（一）简介本文主要对数据结构中的树与二叉树进行学习，之前我们学习了数据的线性结构(线性表),但数据之间不只有这种简单的一对一关系，更多时候是一对多，甚至多对多的结构，而树结构作为一种比线性结构更复杂的数据结构，比较适合于描述具有层次关系的数据，即数据间的一对多关系。树定义树中常常将数据元素称之为结点，树是n个结点的集合。当n=0时，称为空树；任意一颗非空树都满足一下几个条件:有且仅有一个特定的称为根的结点当n>1时，除根结点之外的其余结点被分为m个互不相交的有限集合，其中每一个集合又是一棵树基本术语结点的度与树的度叶子结点与分支结点孩子结点、双亲结点、兄弟结点路径、路径长度祖先、子孙结点的层数、树的深度(高度)层序编号有序树、无序树森林二叉树定义二叉树是n个结点的有限集合，该集合或者为空集，或者由一个根结点和2棵互不相交的、分别称为根节点的左子树和柚子乎上的二叉树构成。二叉树的特点每个结点最多有2棵子树二叉树是有序的，次序不能颠倒基本术语斜树满二叉树完全二叉树二叉树的遍历简介二叉树的存储可以采用顺序存储和连接存储两种方式，相应的代码实现也有些许区别，不过其思想都是一致的，下面我们针对链接存储结构来实现二叉树的几种遍历方式。二叉树的构造及其基本操作：package com.dataStructure; /** * author zbl * * datetime 2019.11.266666 * */ //结点类 public class TreeNode<T> { //指向下一个结点 public TreeNode leftChild; public TreeNode rightChild; public T data; TreeNode(T data){ this.data = data; } } 构架二叉树函数代码实现：此处采用迭代左子树实现，创建的是一棵左斜树//创建二叉树 private TreeNode creatBiTree(LinkedList<T> inputList){ TreeNode<T> tmp = null; //判空 if(inputList == null || inputList.isEmpty()){ return null; } //存数 T data = inputList.removeFirst(); if(data != null){ tmp = new TreeNode(data); tmp.leftChild = this.creatBiTree(inputList); tmp.rightChild = this.creatBiTree(inputList); } //返回根结点 return tmp; }前序遍历输出顺序：根节点、左子树、右子树递归代码实现：//前序遍历 递归实现 private void preOrder(TreeNode<T> node){ if (node != null){ System.out.println(node.data); preOrder(node.leftChild); preOrder(node.rightChild); } }非递归代码实现：//前序遍历 非递归 private void preOrder(TreeNode<T> node){ Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode<T> tmp = this.node; while(tmp != null || !stack.isEmpty()){ //迭代访问节点的左孩子，并入栈 while(tmp != null){ System.out.println(tmp.data); stack.push(tmp); tmp = tmp.leftChild; } //如果节点没有左孩子，则弹出栈顶，访问节点右孩子 if(!stack.isEmpty()){ tmp = stack.pop(); tmp = tmp.rightChild; } } } 中序遍历输出顺序：左子树、根节点、右子树递归代码实现：//中序遍历 递归实现 private void inOrder(TreeNode<T> node){ if (node != null){ inOrder(node.leftChild); System.out.println(node.data); inOrder(node.rightChild); } }非递归代码实现：//中序遍历 非递归 private void inOrder(TreeNode<T> node){ Stack<TreeNode> sta…

数据结构之单链表
type: item
date: 2019-11-01T20:00:00+08:00
description: 欢迎移步博主CSDN：CSDN博客数据结构----链表单链表单链表是用一组任意的存储单元存放线性表的元素，这组存储单元可以连续也可以不连续，甚至可以零散的分布在内存中的任意位置。简单来说就是在逻辑上连续，在物理上不连续的存储单元。代码实现：（以下代码起始位置为0）/* * @Author: zbl * @Date: 2019-11-01 16:03:37 * @Last Modified by: zbl * @Last Modified time: 2019-11-01 17:28:40 */ #include <iostream> using namespace std; //定义结点 template <class T> struct Node{ T data; Node<T>* next = NULL; }; //单链表的定义 template<class T> class LinkList{ private: //头结点 Node<T>* head; //链表长度 int length; public: //无参构造函数 LinkList(){} //有参构造函数 LinkList(T a[],int n); //析构函数 ~LinkList(); //定位元素x的位置 int locate(T x); //获取位置i的元素 T get(int i); //在i位置插入元素x void insert(int i , T x); //删除i位置的元素 T Delete(int i); //打印单链表 void display(); //获取单链表长度 int getLength(){return length;} }; //有参构造函数 template<class T> LinkList<T>::LinkList(T a[],int n){ length = n; Node<T>* tmp = new Node<T>(); head = tmp; int i = 0; while(i<n){ Node<T>* node = new Node<T>(); node->data = a[i++]; tmp->next = node; tmp = tmp->next; } delete tmp; //下标从0开始 head = head->next; } //析构函数 template <class T> LinkList<T>::~LinkList(){ length = 0; Node<T>* p = head; while(p->next != NULL){ Node<T>* tmp = p; p = p->next; tmp->next = NULL; delete tmp; } delete p; head = NULL; } //定位元素x的位置 template <class T> int LinkList<T>::locate(T x){ if(head == NULL) throw "链表为空!"; Node<T>* next = head; int i = 0; while(next != NULL){ if(next->data == x) return i; ++i; next = next->next; } //未找到 return -1; } //获取位置i的元素 template <class T> T LinkList<T>::get(int i){ if(i < 0) throw "下溢"; if(i > length - 1) throw "上溢"; Node<T>* next = head; while(i--){ next = next->next; } return next->data; } //在i位置插入元素x template <class T> void LinkList<T>::insert(int i , T x){ if(i < 0) throw "下溢"; if(i > length) throw "上溢"; //新建结点 Node<T>* node = new Node<T>(); node->data = x; //头插 if(i == 0){ node->next = head; head = node; } else{ Node<T>* tmp = head; while(--i){ tmp = tmp->next; } node->next = tmp->next; tmp->next = node; } length++; } //删除i位置的元素 template <class T> T LinkList<T>::Delete(int i){ if(i…

数据结构之顺序表
type: item
date: 2019-10-31T21:53:00+08:00
description: 欢迎移步博主CSDN：CSDN博客数据结构----顺序表简介线性表是一种最基本、最简单的数据结构，数据元素之间仅具有单一的前驱和后继关系。线性表是线性结构的典型代表。线性表的两种存储方式：顺序存储链接存储下面我们将分别对这两种方式进行学习并用代码实现。顺序表顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中，在计算机中一般采用数组进行存储(因为数组元素存放在一组地址连续的存储单元中)代码实现：#include <iostream> #define MAX_SIZE 100 using namespace std; /* * @Author: zbl * @Date: 2019-10-31 11:29:23 * @Last Modified by: zbl * @Last Modified time: 2019-10-31 11:33:51 */ template <class T> class SeqList { public: SeqList(T a[],int n); SeqList(); virtual ~SeqList(); int getLength(); T get(int i); int find(T x); void insert(int i,T x); T remove(int i); bool isEmpty(); void dispaly(); private: T data[MAX_SIZE]; int length; }; //构造函数 template <class T> SeqList<T>::SeqList(T a[], int n) { cout<<MAX_SIZE<<endl; if(n > MAX_SIZE) throw "参数非法!"; //初始化 for (int i = 0; i < n; ++i) { data[i] = a[i]; } length = n; } //无参构造函数 template <class T> SeqList<T>::SeqList(){ length = 0; //初始化 memset(data, 1, sizeof(data)); } //析构函数 template <class T> SeqList<T>::~SeqList() { //dtor } //获取长度 template <class T> int SeqList<T>::getLength(){ return length; } //获取i位置的元素 template <class T> T SeqList<T>::get(int i){ if(i < 0) throw "下溢"; else if(i > length - 1) throw "上溢"; else return data[i]; } //查找x元素的位置 template <class T> int SeqList<T>::find(T x){ for (int i = 0; i < length; ++i) { if(x == data[i]) return i; } //未找到 return -1; } //在i位置插入元素x template <class T> void SeqList<T>::insert(int i ,T x){ if(length == MAX_SIZE) throw "线性表已满!"; if(i<0||i>length) throw "参数非法!"; //头插 if(i==0){ for (int j = length; j > 0; --j) { data[j] = data[j-1]; } data[i] = x; } //尾插 else if(i==length){ data[i] = x; } //中间 else { for (int j = length; j > i; --j) { data[j] = data[j - 1]; } data[i] = x; } length++; } //删除位置为i的元素 template <class T> T SeqList<T>::remove(int i){ if(i<0||i>length-1) throw "参数非法!"; T x = data[i]; for (int j = i; i < length; ++i) { data[j] = data[j + 1]; } length--; return x; } //判断顺序表是否为空 template <class T> bool SeqList<T>::isEmpty() { return length==0?true:false; } //打印顺序表 temp…