数据结构

数据结构与算法

发布日期: 2022-02-15

文章字数: 4.6k

数据结构

第一讲基本概念和术语

数据:

是信息的载，是描述客观事物的数，字符，以及所有能输入到计算机中被程序识别处理的符号集合
数据元素:
数据的个体，
数据项：

组成数据元素的有特定意义的最小单位

如：学生信息表中的学号，姓名
数据对象：

具有相同性质的数据集合
数据结构：

通过抽象方法研究一组有特定关系的数据的存储和处理

数据存储结构

哈希(散列)存储方式：

是专用于集合结构的数据存放方式，用一个哈希函数将数据元素按关键字的一个和唯一的存储位置关联起来
索引存储方式:

数据元素被排成序列，位序作为节点的索引存储在索引表中

第二讲算法以及算法分析

T(n)=C(fn)
时间复杂度：O(fn)

第三讲线性表

线性表:

具有相同数据类型的n个数据元素的有限序列

顺序表

采用顺序结构(一维数组)的线性表

顺序表表示

data//指向线性表元素类型的指针
  curlLength: //数组元素的个数(表长)
maxSize: //数组规模

初始化顺序表：

maxSize = initSize;
data = new elemType[maxSize];
curLength=0;

遍历:

if(curLength==0)cout<<"empty"<<endl;
else{
  cout<<"output elements:\n";
  for(int i=0;i<curLength;i++){ //依次访问元素
    cout<<data[i]<<" ";
  }
  cout<<endl;
}
//时间复杂度为O(n)，空间复杂度为O(1);

查找：

for(int i=0;i<curLength;i++){
  if(value==data[i])return i;
  return -1 //查找失败返回-1
}
//时间复杂度为O(n),空间复杂度为O(1)

插入：
1. 在合法位置才能插入[0~n];
2. 表已经满了是无法插入的;
3. 从最后一位元素开始移动,再插入;

if(i< 0|| i>curLength) throw outOfRange();//合法位置插入为[0....curLength]
if(curLength == maxSize) resize();//表满，报错或者扩大表
for(int j=curLength;j>i;j--){
  data[j] = data[j-1];  //[curLength-1....1]范围的元素后移
}
data[i] = value; //将value置入位序(位置)为i的位置
++curLength; //表的实际长度加1

//时间复杂度O(n),空间复杂度O(1)

删除：
1. 表为空无法删除
2. 注意合法位置

if(i< 0|| i>curLength) throw outOfRange();//合法位置删除为[0....curLength]
for(int j=i;j<curLength;j++)
  data[j] = data[j+1]; //范围[i+1.....curLength-1]范围的元素前移一步
--curLength; //表的实际长度减一

逆置：

elemType tmp;
for(int i=0;i<curLength/2;i++){//控制交换的次数
  tmp = data[i];//复制一个值
  data[i] = data[curLength-i-1];//将被复制的值覆盖
  data[curlLength-i-1]=tmp;//将复制的值赋值给对应位置
}
//时间复杂度为O(n),空间复杂度为O(1)

链表

用指针实现的变长的线性存储结构

包括: 单链表，双链表，循环链表

组成:
数据字段+指针字段

数据字段指针字段
节点类型定义:

template <class elemType>
struct Node{
public:
  elemType data; //数据域
  Node * next;//指针域
  Node(const elemType value,Node*p=NULL){//两参数的构造函数
    data=value;//值赋值给data域
    next = p;
  }
  Node(Node *p=NULL){
    next=p;
  }
}

遍历

Node *p = head->next; //工作指针指向首元节点
cout<<"traverse: ";
whil(p!=NULL){ //链表没有访问完
  cout<<p->data<<" ";//输出指针
  p = p->next; //向后移动指针
}
//时间复杂度:O(n);空间复杂度:O(1)

查找

Node *p=head->next;//p指向首元节点
int count = 0;//首元节点的位置为0
while(p!=NULL&&p->data!=value){//没有找完且没有找到
  p = p->next; //移动p指针
  count++;//记录p指针的位置
}
if(p==NULL)return -1;//查找失败，这里的-1不是头节点
else return count;
//时间复杂度O(n),空间复杂度O(1);

插入：

在节点p之前插入元素为valued的节点

pre = head;
while(pre!=NULL&&pre->next!=p) 
  pre = pre->next; //找p的前驱
if(!pre){cout<<"不存在*p节点";exit(1);}
s = new Node<elem Type>();
s->data = value; //为新节点赋值
s->next=pre->next; //将s挂在p的前面
pre->next = s;//将s挂在pre的后面
//时间复杂度是O(n)，空间复杂度O(1);

删除：

删除第i个节点

if(i<0){cout<<"参数错误";exit(0);}
pre = head; count=1; //count的合法值i-1
while(pre->next&&cout<i){ //查找第i-1个节点(第i个节点的前驱节点)
  pre = pre->next;cout++;//移动节点pre
}
if(pre->next==NULL)
{cout<<"删除位置不正确";exit(0)}
q = pre->next; //将p节点赋给q
pre->next = q->next; //从链表中删除节点
delete q; //释放被删除的节点
//时间复杂度O(n);空间复杂度O(1);

逆置:

利用头插法遍历原链表中的每一个节点完成逆置

Node *p,*tmp;
p = head->next; //p为工作指针指向首元节点
head->next = NULL;//头节点的额指针域置空，构成空链表
while(p){
  tmp = p->next;//暂存p的后继
  p->next = head->next;
  head->next = p;//将p插入头节点的后面
  p = tmp; //继续处理下一个节点
}
//时间复杂度是O(n);空间复杂度O(1)

第四讲树和二叉树

二叉树的基本算法

二叉树的性质:
1. 一颗非空二叉树的第i层上最多有2^i-1次方个节点
2. 一颗高度为k的二叉树最多有z^k-1个节点
3. 任何一颗二叉树中，若叶子数为n0，度为2的节点数为n2,则n0=n2+1
```
-1+n=n0+n1+n2-1
  B = n-1
  B = n1*1+n2*2
  n0+n1+n2-1 = n1 + 2n2
```
1. 具有n个节点的完全二叉树的高度为k=[log2(n+1)]（向上取整）
二叉树的二叉链表的表示和实现

template <class elemType>
  class BinaryLinklist{
    private:
      struct Node{ //二叉链表节点
        Node *left,*right; //指向左右孩子的指针
        elemType data; //节点的数据域
        Node();left(NULL),right(NULL){}//无参构造函数
        NOde(elemType value,Node *l=NULL,Node *r=NULL){
          data=value;left=l;right=r;
        }
        -Node(){}
      };
  }

二叉树遍历:

前序递归:

template <class elemType>
void BinaryLinkList<elemType>::preOrder(Node *t) const{
  if(t){
    cout<<t->data<<''; //访问当前节点
    preOrder(t->left); //前序遍历左子树
    preOrder(t->right);//前序遍历右子树
  }
}

中序递归

template <class elemType>
void BinaryLinkList<elemType>::preOrder(Node *t) const{
  if(t){
    preOrder(t->left); //前序遍历左子树
    cout<<t->data<<''; //访问当前节点
    preOrder(t->right);//前序遍历右子树
  }
}

后序递归

template <class elemType>
void BinaryLinkList<elemType>::preOrder(Node *t) const{
  if(t){
    preOrder(t->left); //前序遍历左子树
    preOrder(t->right);//前序遍历右子树
    cout<<t->data<<''; //访问当前节点
  }
}

层次遍历(队列)

template <class elemType>
  void BinaryLinkList<elemType>::levelOrderTraverse()const{
    queue<Node *> que; //STL中的队列
    Node* p = root;
    if(p) que..push(p); //根节点入队列
    while(!que.empty()){ //对列非空
      p = que.front();//取队首元素
      que.pop();//出队
      cout<<p->data<<'';//访问当前节点
      if(p->left!=NULL)que.push(p->left);//左子树进队列
      if(p->right!=NULL)que.push(p->right);//右子树进队列
    }
  }

求节点总数

template <class elemType>
int BinaryLinkList<elemType>::size(Node *t)const{
  if(t==NULL) return 0;
  return 1+size(t->left)+size(t->right);
}

求二叉树的高度:

template <class elemType>
  int Binarylist<elemType>::hight(Node *t)const{
    if(t==0)return 0;//子树为空子树
    else{ //子树非空
      int lh = height(t->left),rh=helight(t->right);
      return 1+(lh>rh?lh:rh); //树的高度为左右子树高度大者+1
    }
  }

求叶子树：

template <class elemType>
  int BinarLinkList<elemType>::leafNum(Node* t)const{
    if(t==NULL)return 0;//情况一：空子树
    else if(t->left==NULL&&t->right=NULL)
      return 1;//情况叶子节点
    else
      return LeafNum(t->left)+leatNm(t->right);
  }

树和森林

树的类型定义

template <class elemType>
  class childSiblingTree{
    private:
      struct Node{
        elemType data;//节点的数据域
        Node *fistchild,*nextSibling;//指向第一个孩子，下一个兄弟的指针
        Node():firstChild(NULL),nextSibling(NULL){}
        Node(elemType value,NOde *i=NULL,Node *r=NULL){
          data=value;
          firstChild=l;
          nextSibling=r;
        }
        -NOde(){}
      };
    Node* root;
  }

树转换成二叉树：
1. 将所有的兄弟节点之间连线(全部转换成右指针)
2. 将每个节点除与左孩子的连线外，与其他孩子的连线删除
3. 将图顺时针方向旋转45度
森林到二叉树的转换:
1. 将所有兄弟节点(包括根节点)相连
2. 将每个节点除与左孩子的连线外，与其他孩子的连线删除
3. 将图顺时针方向旋转45

树和森林的遍历

前序递归

template <class elemType>
  void childSiblingTree<elemType>::preOrder_1(Node *t)const{
    while(NULL!=t){
      cout<<t->data<<''; //访问当前结点
      preOrder_1(t->firstChild);//前序遍历t的各子树
      t = t->nextSibling; //遍历其他的树
    }
  }

后序遍历

template <class elemType>
  void childSiblingTree<elemType>::postOrder_1(Node *t)const{
    while(NULL!=t){
      postOrder_1(t->firstChild);//后序遍历t的各子树
      cout<<t->data<<''; //访问当前结点
      t = t->nextSibling; //遍历其他的树
    }
  }

层次遍历：

template <class elemType>
  void childSiblingTree<elemType>::levelOrderTraverse() const{
    queue<Node*> Q;//STL队列
    Node *p =root; //工作指针
    while(p){ //当前节点同一层的节点入队
      Q.push(p);//当前节点进入队列
      p = p->nextSibling; //指向当前节点的右兄弟
    }
    while(!Q.empty()){
      p = Q.front(); //取队列首节点指针
      Q.pop(); //出队
      cout<<p->data<<'';//访问当前节点
      p = p->firstChild;//找到当前节点的第一个孩子
      while(p){//当前节点的子节点进入队列
        Q.push(p);
        p = p->nextSibling;//沿最左孩子的右兄弟链可以找到所有的孩子
      }
    }
  }

求树的高度

template <class elemType>
  int childSiblingTree<elemType>::height(Node *t)const{
    if(t==NULL) return 0;
    else{ //子树非空
      int lh = height(t->firstChild),rh=height(t->nextSibling);
      return 1+lh>rh?lh:rh;//选取大者作为子树的高度
    }
  }

求树的节点总数

template <class elemType>
  int childSiblingTree<elemType>::size(Node *t)const{
    if(t==NULL)return 0;
    return 1+size(t->firstChild)+size(t->nextSibling);
  }

求叶子树：

template <class elemType>
  int childSiblingTree<elemType>::leafNum(NOde*t)const{
    if(NULL==t) return 0;//空子树
    else{
      if(t->firstChild ==NULL)//当前节点是叶子
        return 1+leafNum(t->nextSibling);//1+兄弟子树的叶子节点数
      else
        return leafNum(t->firrstChild)+leafNum(t->nextSibling);//当前节点是非终端节点
    }
  }

第五讲图的基本算法

图的表示

邻接矩阵:

template <class VertexType,class EdgeType>
  //VertextType顶点的类型: Edge边(或弧)的类型
  class adjMatrix{
    private:
      VertextType *vertexs;//顶点向量
      EdgeType **edges;//邻接矩阵
      EdgeType noEdge;//无边标志
      void dfs(int start)const;//深度优先遍历图000
  }

邻接表类：

template <class VertexType,class EdgeType>
  class adjList{
    private:
      struct edgeNode{ //边表节点类型
        int to;//边的终点编号
        EdgeType weight;//边上的权值
        edgeNode *next;//指向下一个边表节点
        edgeNode(){} //无参构造函数
        edgeNode(int t,EdgeType w,edgeNode *n=NULL){
          to=t;
          weight=w;
          next=n;
        }
      };
    struct verNode{//顶点节点类型
      VertexTye vertex;//顶点信息
      edgeNode *firstEdge;//指向第一个邻接点的指针
      verNode(edgeNode *h=NULL){firstEdge=h}
    };
    verNode *verlist; //顶点表
    void dfs(int start)const; //从start号出发DFS
  }

图的遍历

图的深度优先遍历:

//伪代码说明
void dfsTraverse(){
  对每个节点v
    visted[v] = false //访问标志位设置为0
  while(v=尚未访问的节点)
    dfs(v);
}
//深度遍历图的接口函数
template <class VertexType,class EdgeType>
  void adjList<vertexType,EdgeType>::dfsTraverse()const{
    int i,count=0; //count用于统计无向图联通分量的个数
    for(i=0li<verNum;i++)
      visited[i]=false; //置访问标志位为false
    for(i = 0;i<verNnum;i++){
      if(!visited[i]){ //选取一个未访问过的节点调用dfs
        dfs(i);           //若该图是连通图则指调用dfs一次
        count++;
      }
    }count<<endl;
  }
//伪代码说明
void dfs(v){
  visited[t]=true;
  for 每个v的邻接点w
    if(!Visted[w])
      dfs(w);
}
//递归函数dfs访问从顶点start出发能够深度优先遍历到的所有顶点
template <class VertexType,class EdgeType>
  void adjlist<VertextType,EdgeType>::dfs(int start)const{
    edgeNode *p=verList[start].frstEdge;
    cout<<verlist[start].vertex<<''; //访问顶点v
    visited[start]=true; //置访问标志为true
    while(p!=NULL){
      if(visited[p->to]==false)//选取未被访问的邻接点
        dfs(p->to);  //选取start的未被访问的邻接点
      p = p->next;
    }
  }
//邻接表实现的时间复杂度为O(n+e)
//邻接矩阵实现的时间复杂度为O(n^2)

广度优先遍历：

template <class VertexType,class EdgeType>
  void adjList<vertexType,EdgeType>::bfsTraverse()const{
    int v,i,count=0; //count可统计练连通分量的个数
    queue<int>q;
    edgeNode *p;
    for(i = 0;i<verNum;i++)
      visited = false;
    for(i =0;i<verNum;i++){
      if(visited[i]==true)continue;
      count<<verList[i].vertex<<''; //访问顶点i
      visited[i] = true; //置访问标志为true
      q.push[i];//顶点入队
      count++;//统计连通分量
      while(!q.empty()){
      v = q.front();q.pop(); //顶点v队伍
      p = verList[v].firstEdge;
      while(p!=NULL){
        if(visited[p->to]==false){
          count<<verList[p->to].vertex<<''; //置访问顶点p->to
          visited[p->to] = true; //置访问标志为true
          q.push(p->to); //顶点p->to入队伍
        }
        p=p->next;
      }
    }
  }
    count<<endl;
}
//邻接表实现时间复杂度O(n^2)
//邻接矩阵实现时间复杂度O(n)

拓扑排序：

template <class VertextType,class EdgeType>
  bool adjList<VertexType,EdgeType>::topSort()const{
    queeue<int> q;
    edgeNode *p;
    int i,curNOde,count=0,*inDegreee=new int[verNum]//标记顶点入度;
    for(i = 0li<verNum;i++){
      inDegree[i]=0
    for(i = 0;i<verNUm;i++) //遍历边表，求顶点入度
    {
      for(p=verList[i].firstEdge;p!=NULL;p=p->next)
        ++inDegree[p->to];
    }
    for(i=0;i<verNum;i++)
      if(inDegree[i]==0) q.push(i); //入度为0的顶点入队列
    while(!q.empty()){
      curNode=q.front();
      q.pop(); //出队一个入度为0的顶点
      count<<verList[curNode].vertex<<''; //输出
      count++; //计数器加一
      for(p=verList[curNode].firstEdge;p!=NULL;p=p->next)
        if(--inDegree[p->to]==0) //邻接点入度减一
          q.push(p->to); //入度为0的顶点入对
    }
      cout<<endl;
      if(count==verNum)
        return true; //输出全部顶点，拓扑排序成功
      return false; //该有向图有环，拓扑排序失败
  }
//邻接表实现的时间复杂度O(n+e)
//邻接矩阵实现时间复杂度是O(n^2)

最短路径

floyd算法

template <class VertexType,class EdgeType>
  void adjMatrix<VertexType,EdgeType>::floyd()const{
    EdgeType **D=new EdgeType*[verNum];//指向数组的指针，数组元素也是指针
    int i,j,k;
    for(i = 0li<verNum;++i){
      D[i] = new EdgeType[verNum];//数组元素指向一个一位数组
      for(j=0;j<verNum;++j){
        D[i][j]=(i==j)?0:edges[i][j];//对D数组进行初始化
      }
    }
    for(k=0;k<verNum;k++)
      for(i=0;i<verNum;i++)
        for(j=0;j<verNum;++j)
          if(D[i][k]+D[k][j]<D[j][j]){ //从i经过k到j路径更短
            D[i][j]=D[i][k]+D[k][j];
          }
  }
//时间性能：三重for循环，复杂度是O(n^3);

第六讲检索

顺序查找无序表

template <class RecType>//使用STL的vector向量容器
  in t seqSearch(vector<RecType>&data,const RecType&k){
  int i;
  data[0]=k;//监视设置为k
  for(i=data.size()-1;k!=data[i];--i);
  return i;
}

折半查找

非递归:

template <class RecType>
  int binarySearch(const vector<RecType>&data,const RecType &k){
  int low =1,high =da ta.size()-1,mid;
  while(low<=high){
    mid=(low+high)/2; //计算中间位置
    if(k==data[mid]) return mid;//查找成功
    if(k<data[mid]) high = mid-1; //find in second half area continuly
    else low = mid+1; //find in first half area continuly
  }
  return 0 //find failed
}

尘落

http://39.105.134.199/2022/02/15/700.html

本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源尘落 !

数据结构

Java并发

2022-02-22 JAVA

JAVA

BUUCTF-roarCTF做题笔记

2022-02-11 JAVA

BUUCTF

数据结构大体

数据结构

第一讲 基本概念和术语

数据存储结构

第二讲 算法以及算法分析

第三讲 线性表

顺序表

链表

第四讲 树和二叉树

二叉树的基本算法

树和森林

第五讲 图的基本算法

图的表示

图的遍历

最短路径

第六讲 检索

你的赏识是我前进的动力

第一讲基本概念和术语

第二讲算法以及算法分析

第三讲线性表

第四讲树和二叉树

第五讲图的基本算法

第六讲检索