首页 > 其他分享 >数据结构学习

数据结构学习

时间：2024-11-07 16:08:38浏览次数：1  
标签：node 结点 return temp int 学习 数据结构 节点

computer

数据结构

第一章

算法

  1. 一个有限指令集
  2. 接受一些输入
  3. 产生输出
  4. 一定要在有限的步骤之后终止
  5. 每一条指令必须有明确色目标，不可以有歧义，计算机能处理的范围之内，不依赖任何语言和描述。
    alt text

什么是好算法

  1. 时间复杂度
  2. 空间复杂度

复杂度的渐进表示法

alt text

输入规模 n

alt text

每十亿

`

最大子列和的问题

算法一

int MaxSubeqSum1(int A[],int N)  
{
int ThisSum ,MaxSum = 0;  
int i,j,k;  
for (i =0;i<N;i++){
   for(j=i;j<N;j++){
    ThisSum = 0;
    for(k=0 ;k<=j;j++)
    ThisSum += A[k];
    if(ThisSum > MaxSum)
    MaxSum = ThisSum;
    
    }
}
return MaxSum;

}

算法二 分而治之

在线处理

int MaxSubseqSum4(int A[],int N){
int ThisSum,MaxSum;
int i;
ThisSum = MaxSum =0;
for(int i = 0;i<N;i++){  
ThisSum +=A[i];
if(ThisSum>MaxSum){
    MaxSum = ThisSum;
   }else if(ThisSum<0)
   ThisSum = 0;
}
return MaxSum;
}

线性表

如何表示多项式

  1. 多项式的各项系数n
  2. 各项系数以及指数

方法一 顺序存储结直接表示
方法二 顺序存储结构表示非零项

  1. 用结构数组来表示
  2. 链表结构存储非零项

什么是线性表（数组）

主要操作的实现

List MakeEmpty(){
List PtrL;
PtriL = (List )alloc (sizeof(struct  Lnode));
PtrL-> = -1;
return PtrL;
}


 int Find(ElementType X,List PtrL){
 int i =0;
 while(i<=PtrL->Last&&PtrL->data[i]!=X){
    i++；
    }
    if(i>PtrL->Last)return -1;
    else return i;
    }
  1. 插入

链式存储结构（链表）





循环单列表代码

#include<stdlib.h>
typedef struct list{
    int data;
    struct list *next;
}list;
//data为存储的数据，next指针为指向下一个结点
 
//初始结点
list *initlist(){
    list *head=(list*)malloc(sizeof(list));
    if(head==NULL){
        printf("创建失败，退出程序");
        exit(0);
    }else{
        head->next=NULL;
        return head;
    }
}
 
//创建--插入数据
int create_list(list *head){
    int data;   //插入的数据类型
    printf("请输入要插入的元素：");
    scanf("%d",&data);
 
    list *node=initlist();
    node->data=data;
    //初始化一个新的结点，准备进行链接
 
    if(head!=NULL){
        list *p=head;
        //找到最后一个数据
        while(p->next!=head){
            p=p->next;
        }
        p->next=node;
        node->next=head;
        return 1;
    }else{
        printf("头结点已无元素\n");
        return 0;
    }
 
}
 
//插入元素
list *insert_list(list *head,int pos,int data){
    //三个参数分别是链表，位置，参数
    list *node=initlist();  //新建结点
    list *p=head;       //p表示新的链表
    list *t;
    t=p;
    node->data=data;
    if(head!=NULL){
        for(int i=1;i<=pos;i++){
            t=t->next;
        }
        node->next=t->next;
        t->next=node;
        return p;
    }
    return p;
}
 
//删除元素
int delete_list(list *head) {
    if(head == NULL) {
        printf("链表为空！\n");
        return 0;
    }
    //建立零时结点存储头结点信息（目的为了找到退出点）
    //如果不这么建立的化需要使用一个数据进行计数标记，计数达到链表长度时自动退出
    //循环链表当找到最后一个元素的时候会自动指向头元素，这是我们不想让他发生的
    list *temp = head;          
    list *ptr = head->next;
 
    int del;
    printf("请输入你要删除的元素：");
    scanf("%d",&del);
 
    while(ptr != head) {
        if(ptr->data == del) {
            if(ptr->next == head) { //循环结束的条件换成ptr->next == head
                temp->next = head;
                free(ptr);
                return 1;
            }
            temp->next = ptr->next;
            free(ptr);
            //printf("元素删除成功！\n");
            return 1;
        }
        temp = temp->next;
        ptr = ptr->next;
    }
    printf("没有找到要删除的元素\n");
    return 0;
}
 
 
//遍历元素
int display(list *head) {
    if(head != NULL) {
        list *p  = head;
        //遍历头节点到，最后一个数据
        while(p->next != head ) {
            printf("%d   ",p->next->data);
            p = p->next;
        }
        printf("\n");   //习惯性换行 ( o=^•ェ•)o　┏━┓
        //把最后一个节点赋新的节点过去
        return 1;
    } else {
        printf("头结点为空!\n");
        return 0;
    }
}
 
int main(){
    //////////初始化头结点//////////////
    list *head=initlist();
    head->next=head;
    ////////通过插入元素完善链表/////////
    for(int i=0;i<5;i++){   //只是演示使用，不具体提供输入
        create_list(head);
    }
    display(head);
    ////////////插入元素////////////////
    head=insert_list(head,1,10);
    display(head);
    ////////////删除元素////////////////
    delete_list(head);
    display(head);
    return 0;
}

广义表

  1. 广义表是线性表的推广
  2. 对于线性表而言，n个元素都是基本的单元素
  3. 广义表中，这些元素不仅可以是单元素也可以是另外一个广义表

多重链表

多重链表：链表中的节点可能同时隶属于多个链

  1. 多重链表中的节点的指针域会有多个
  2. 但包含两个指针域的链表并不一定是多重链表，比如再双向链表不是多重链表
    几个典型的多重链表：
  3. 十字链表
    只存储矩阵的非零项，每个节点通过两个指针，把行和列串连起来

堆栈

后缀表达式

中缀表达式：运算符号在两个运算数之间
后缀表达式：运算符号在两个运算数之后

堆栈的数据描述

栈是一种先进后出的数据结构，栈是一个线性的数据结构，规定这个数据结构只允许在其中一端进行操作，并禁止直接访问除这一端以外的数据
栈分为数组栈和链表栈，其区别是数组栈使用数组进行功能的模拟，实现较为快速和便利，而链表栈使用链表的思路去设计，实现较为麻烦，但是其稳定不易出错；在链表栈中又分为静态链表栈和动态链表栈，静态链表栈给定栈的空间大小，不允许超过存储超过给定数据大小的元素，而动态栈使用的是自动创建空间的方法进行创建，只要符合机器的硬件要求以及编译器的控制，其理论上是极大的。
堆栈（stack）：具有一定约束的线性表，只在一端做（栈顶）做插入，删除

  1. 插入元素：入栈 （Push）
  2. 删除元素：出栈（pop）
  3. 后入显出
    4.

栈的顺序存储实现

栈的定义

#define MaxSise;
typedef struct Snode*Stack;
struct SNode{
    ElementType Data[MaxSise];
    int top;
}

入栈

void Push (Stack PtrlS,ElementType item){
    if(PtrlS->Top == MaxSize-1){
        printf("堆栈满了")；
        return;
    }else{
        PtrlS->Data[++(PtrlS->Top)] = item;
        renturn;
    }
}

出栈

    if(PtrS-> == -1){
        printf("堆栈空")；
    }else
    return (PtrS->Data[(PtrS->top)--]);
}

例子：请用一个数组实现两个堆栈，要求最大地利用数组空间，使数组只要有空间入栈操作就可以成功。
分析：一种比较聪明的方法是使这两个栈分别从数组的两头开始向中间生长；当两个栈的栈顶指针相遇时，表示这两个栈都满了

#define MaxSize
struct DStack{
    ElementType Data[MaxSize];
    int top1;
    int top2;
}S;
s.top1 = -1;
s.top2 = MaxSize;
void Push (struct DStack *PtrS,ElementType item,int tag){
    if(PtrS->top2-PtrS->Top1 == 1){
        prtinf("堆栈满")；
        return；
    }
    if(Tag == 1)
        PtrS->Data[++(PtrS->Top1)] = item;
    else
        PtrS->Data[--(PtrS->Top2)] = item;  
ElementType Pop(struct DStack *PtrS,int Tag){
        if(Tag == 1){  
             if(PtrS ->Top1 == -1){
                printf("堆栈空");
                return NULL;
             }esle
             return PtrS->Data[(PtrS->Top1)--];
        }
    }esle{
        if(PtrS->Top2 == MaxSize){
            printf("堆栈2空");
            return NULL;
        }else 
            return PtrS->Data[(PtrS ->Top2)++];
    }
}

堆栈的链式存储实现

栈的链式存储结构实际上就是一个单链表，叫做链栈。插入和删除操作只能在链栈的栈顶进行。

typedef struct SNode*Stack;
sturct SNode{
    ElementType Data; 
    struct SNode *Next;
};
Stack CreatStack(){
    Stack S;
    S = (Stack)malloc(sizeof(Struct SNode));
    S ->Next =NULL;
    return S;
}

int IsEmpty(Stack S){
    return (S->Next == NULL);
}

编解码的问题

堆栈应用，表达式求值

队列

什么是队列
队列：具有一定操作约束的线性表
1. 插入和删除操作 ：只能在一端插入，而在另一端删除
数据插入 ： 入队列
数据删除 ： 出队列
先来后服务
先进先出

队列的顺序存储实现

队列的顺序存储结构通常是由一个一维数组和一个记录队列头元素位置的变量front以及一个记录队列尾元素位置的变量rear组成

为什么会出现空满不分的情况？
解决方案：

  1. 使用额外标记：size 或者tag
  2. 仅使用n-个数组空间

队列的操作

队列的链式存储实现


栈的代码实现

#include <stdio.h>
#include <stdlib.h>
//栈的结点设计
//单个结点设计，数据和下一个指针
typedef struct node     
{
    int data; 
    struct node *next;
} Node;
//利用上面的结点创建栈，分为指向头结点的top指针和计数用的count
typedef struct stack    
{
    Node *top;
    int count;
} Link_Stack;
 
//创建栈
Link_Stack *Creat_stack()
{
    Link_Stack *p;
    //p = new Link_Stack;
    p=(Link_Stack*)malloc(sizeof(Link_Stack));
    if(p==NULL){
        printf("创建失败，即将退出程序");
        exit(0);
    }
    p->count = 0;
    p->top = NULL;
    return p;
}
 
//入栈 push
Link_Stack *Push_stack(Link_Stack *p, int elem)
{
    if (p == NULL)
        return NULL;
    Node *temp;
    temp=(Node*)malloc(sizeof(Node));
    //temp = new Node;
    temp->data = elem;
    temp->next = p->top;
    p->top = temp;
    p->count++;
    return p;
}
 
//出栈 pop
Link_Stack *Pop_stack(Link_Stack *p)
{
    Node *temp;
    temp = p->top;
    if (p->top == NULL)
    {
        printf("错误：栈为空");
        return p;
    }
    else
    {
        p->top = p->top->next;
        free(temp);
        //delete temp;
        p->count--;
        return p;
    }
}
 
//遍历栈：输出栈中所有元素
int show_stack(Link_Stack *p)
{
    Node *temp;
    temp = p->top;
    if (p->top == NULL)
    {
        printf("");
        printf("错误：栈为空");
        return 0;
    }
    while (temp != NULL)
    {
        printf("%d\t", temp->data);
        temp = temp->next;
    }
    printf("\n");
    return 0;
}
 
int main()
{ //用主函数测试一下功能
    Link_Stack *p;
    p = Creat_stack();
    int n = 5;
    int input[6] = {10,20,30,40,50,60};
    /////////////以依次入栈的方式创建整个栈//////////////
    for(int i=0;i<n;i++){
        Push_stack(p, input[i]);
    }
    show_stack(p);
    ////////////////////出栈///////////////////////
    Pop_stack(p);
    show_stack(p);
    return 0;
}

树

什么是树

树是数据结构中的一种，其属于非线性数据结构结构的一种，我们前文所提到的数据结构多数都是线性的，这也是较为简单的数据结构，而接下来的树与图均属于非线性数据结构，也是概念极多的一类。

树是由结点或顶点和边组成的(可能是非线性的)且不存在着任何环的一种数据结构。没有结点的树称为空(null或empty)树。一棵非空的树包括一个根结点，还(很可能)有多个附加结点，所有结点构成一个多级分层结构。

树的定义：n个节点组成的有限集合。n=0，空树；n>0,1个根节点，m个互不相交的有限集，每个子集为根的子树

树的基本术语

  • 节点的度：树中某个节点的子树的个数。
  • 树的度：树中各节点的度的最大值。
  • 分支节点：度不为零的节点。
  • 叶子节点：度为零的节点
  • 路径：i->j；路径长度：路径经过节点数目减1。
  • 孩子节点：某节点的后继节点；双亲节点：该节点为其孩子节点的双亲节点（父母节点）；兄弟节点：同一双亲的孩子节点；子孙节点：某节点所有子树中的节点；祖先节点：从树节点到该节点的路径上的节点。
  • 节点的层次：根节点为第一层（以此类推）；树的高度：树中节点的最大层次。
  • 有序树：树中节点子树按次序从左向右安排，次序不能改变；无序树：与之相反
  • 森林：互不相交的树的集合。

二叉树简介

二叉树是n(n>=0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成

二叉树的特点

  • 每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点。
  • 左子树和右子树是有顺序的，次序不能任意颠倒
  • 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

二叉树的性质

  1. 二叉树第i层上的结点数目最多为 2的(i-1)次方个节点(i≥1)
  2. 深度为k的二叉树至多有2的k次方-1个结点(k≥1)
  3. 包含n个结点的二叉树的高度至少为log2 (n+1)。
  4. 在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1。

几种特殊的二叉树

斜树
斜树：所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树

满二叉树
满二叉树：在一棵二叉树中。如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

满二叉树的特点有：

  1. 叶子只能出现在最下一层。出现在其它层就不可能达成平衡
  2. 非叶子结点的度一定是2
  3. 在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。

完全二叉树
完全二叉树：对一颗具有n个结点的二叉树按层编号，如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。

#include <cstdlib>
#include <stdio.h>
#include <iostream>
  
using namespace std;
  
//树的结点
typedef struct node{
    int data;
    struct node* left;
    struct node* right;
} Node;
  
//树根
typedef struct {
    Node* root;
} Tree;
  
//创建树--插入数据
void insert(Tree* tree, int value){
    //创建一个节点，让左右指针全部指向空，数据为value
    Node* node=(Node*)malloc(sizeof(Node));
    node->data = value;
    node->left = NULL;
    node->right = NULL;
  
    //判断树是不是空树，如果是，直接让树根指向这一个结点即可
    if (tree->root == NULL){
        tree->root = node;
    } else {//不是空树
        Node* temp = tree->root;//从树根开始
        while (temp != NULL){
            if (value < temp->data){ //小于就进左儿子
                if (temp->left == NULL){
                    temp->left = node;
                    return;
                } else {//继续往下搜寻
                    temp = temp->left;
                }
            } else { //否则进右儿子
                if (temp->right == NULL){
                    temp->right = node;
                    return;
                }
                else {//继续往下搜寻
                    temp = temp->right;
                }
            }
        }
    }
    return;
}
  
//树的中序遍历 In-order traversal
void inorder(Node* node){
    if (node != NULL)
    {
        inorder(node->left);
        printf("%d ",node->data);
        inorder(node->right);
    }
}
  
int main(){
    Tree tree;
    tree.root = NULL;//创建一个空树
    int n;
    scanf("%d",&n);
  
    //输入n个数并创建这个树
    for (int i = 0; i < n; i++){
        int temp;
        scanf("%d",&temp);
        insert(&tree, temp);
    }
  
    inorder(tree.root);//中序遍历
  
    return 0;
}

树的遍历之中序遍历二叉树

  1. 简介
    先序遍历：根左右

中序遍历：左根右

后序遍历：左右根
在上文我们接触到了先序遍历，本文我们开始学习中序遍历，中序遍历采用左根右的遍历方式，如图，就一个最简单的二叉树遍历而言，中序遍历的遍历访问过程是先B再A再C。

实际上的二叉树并没有这么简单，其应该是由多个结点构成的，如图所示，进行第一次访问的时候，我们在ABC中进行遍历，由左根右的顺序，我们遍历访问到B，这时候先别急，B同时又作为BDG的根结点，因此需要继续向下进行遍历，此时我们遍历到DEF，这时E属于这一组之中的左结点，因此我们根据根左右的先后顺序得到了最先的遍历效果，EDF，这EDF同时作为BDG中的左节点（把EDF看作一个整体）进行回溯，此时的访问的结点顺序为EDFBG同理, EDFBG作为ABC的左结点根据左根右的顺序EDFBGAC，左半部分访问完毕接着访问右半部分，我们将CH（表示空）看作一组左中右，而C就是由EDFBGAC组合而成，因此最终的遍历顺序为：EDFBGACH

2. 代码实现

     if(node != NULL){
        inorder(node->left);
        printf("%d",node->data);
        inorder(node->right);
     }   
    }

树的遍历之后序遍历二叉树

  1. 后序遍历就是在访问二叉树的结点的时候采用，先左，再右，再根的方式，对于一个最简单的访问而言如图，先访问左节点B，之后访问右结点C，最后访问根节点A，后序遍历的访问顺序就是BCA

    然而实际上的遍历访问并没有那么简单，往往是多个结点相互嵌套构成的二叉树，如图所示，在访问遍历一开始的时候，先访问左节点B再访问右结点C最后访问A，但由于B结点其中也包含了新的结点，就犹如之前介绍的那样，在面对处理的结点后还存在有与之相联的结点的时候，需要优先处理其的子结点，这也是“递归”的基本思路，因此，由于B属于DG的根结点，我们相较于B，应该先访问D结点，而又由于D结点属于EF的根结点，我们就又变成先访问E结点，E属于最末端了，根据后序遍历左右根的访问顺序，依次生成EFDGB作为一个整体，接着我们需要访问C，由于C又是^HC之中的根结点，我们先访问这个空结点，又因为其是一个空的结点，我们会跳过，就变成了HC的访问顺序，那么最后在汇总的时候EFDGB作为左节点，HC作为右结点，A作为根结点，完成我们最终的遍历顺序EFDGBHCA。
  2. 代码实现
        if(node!= NULL){
            inorder(node -> left);
            inorder(node ->right);
            printf("%d",node->data);
        }    
    }

标签：node,结点,return,temp,int,学习,数据结构,节点
From： https://www.cnblogs.com/haholp-blog/p/18532533

相关文章

  • AI预测足球比赛结果基于深度数据分析与机器学习SoccerPredictor
    在科技日新月异的今天，人工智能已经渗透到我们生活的方方面面，从智能家居到自动驾驶汽车，从虚拟助手到医疗诊断。而现在，AI甚至开始涉足体育领域，尤其是在预测足球比赛结果这一领域展现出了惊人的能力。那么，AI是如何做到预测足球比赛结果的呢？让我们一起揭开这项技术的神秘面纱。......
  • C语言 联合体（共用体）学习笔记
    一、联合体（共用体）的定义       联合体是一种特殊的自定义类型，这种类型定义的变量也包含一系列的成员，特征是这些成员共用一块空间（所以联合体也叫共用体）。       联合体的声明格式：unionUn//去掉联合体名即为匿名联合{ charc; inti;};二、联合体的特......
  • VTK知识学习（1）-概述
    图像显示是一个重要的知识，其中VTK就是一个医学上常用的图像显示开发包。1、总述 从结构上看，VTK程序段落主要包含两个部分。     一是数据和管道部分，     二是角色和渲染部分。2、工作流程 工作的基本流程是“数据源Souce”--“过滤器Filter”--......
  • AI人工智能学习-Day2
    人工智能应用范畴脑科学认知科学心理学语言学逻辑学哲学计算机科学人工智能包含领域机器学习MachineLearning数据挖掘Databases模式识别神经计算NeurocompatingAI、机器学习、深度学习的关系人工智能包含机器学习，机器......
  • SpringBoot Java教学辅助平台：构建高效学习环境
    1系统概述1.1研究背景随着计算机技术的发展以及计算机网络的逐渐普及，互联网成为人们查找信息的重要场所，二十一世纪是信息的时代，所以信息的管理显得特别重要。因此，使用计算机来管理教学辅助平台的相关信息成为必然。开发合适的教学辅助平台，可以方便管理人员对教学辅助平台......
  • 计算机基础学习（非常详细）零基础入门到精通，收藏这篇就够了
    一、计算机概述计算机历史与发展：了解计算机的起源、发展简史，包括第一台电子计算机ENIAC的诞生、冯·诺依曼提出的“存储程序”原理等。计算机分类：巨型计算机、大中型计算机、小型计算机、微型计算机（如PC）、工作站等。计算机特点与应用：指令周期快、运算精度高、可靠性高......
  • 2024-2025-1 20241401 《计算机基础与程序设计》 第七周学习总结
    班级链接2024计算机基础与程序设计作业要求第七周作业作业目标①数组与链表②基于数组和基于链表实现数据结构③无序表与有序表④树⑤图⑥子程序与参数教材学习内容总结《计算机科学概论》第八章抽象数据类型：用于定义数据和对数据的操作，而不需要具体实......
  • 机器学习入门
    机器学习入门指南随着数据的爆炸式增长，机器学习（MachineLearning）逐渐成为了推动科技进步的重要力量。无论是在智能推荐、图像识别，还是自然语言处理领域，机器学习都展现出了强大的应用潜力。本文将为初学者提供一个机器学习的入门指南，包括基本概念、常用算法及实际案例。什么是......
  • 应届小白从0学习CANoe（3）
    第三章CANoe的开发环境3.1CANoe的主界面在CANoe下载完成之后用户需要选择：开始-所有程序-vectorCANoe11.0（我是用的是CANoe16PS4）-即可以启动CANoe单击左上角file然后选择new建立新的项目，在其中选择CAN500k单通道建立工程双击进行确认3.2CANoe选项卡和功能区......
  • 21天全面掌握：小白如何高效学习AI绘画SD和MJ，StableDiffusion零基础入门到精通教程！快速
    今天给大家分享一些我长期以来总结的AI绘画教程和各种AI绘画工具、模型插件，还包含有视频教程AI工具，免费送......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99