初学数据结构的入门过程

数据结构的简单基础入门知识，也是我当初入门时自己跑的代码，具体我的理解已注释。

可以通过跑一跑代码看看注释来理解理解。

写的不好仅供参考。

[TOC]

1、指针理解

#include<iostream>
using namespace std;

void fun(int **q)  //从右往左理解, q 为指针的地址，*q 为指针(地址)， **q为指针指向的值
{
    cout<<"----函数中查看-----"<<endl;//！！！指针本身即是地址！！！
    cout<<"指针的地址："<<q<<endl;//指针的地址
    cout<<"指针："<<*q<<endl;//指针（地址）
    cout<<"值："<<**q<<endl;//指针指向的值,因为没给指针赋值，所以它会乱指
    cout<<"----变化之后-----"<<endl;
    *q=new int;   //初始化指针，因为之前没跟指针赋地址，所以可能乱指，现在给指针一个特定的地址。
    **q=100;      //↑等同于 int* q=new int; --- q赋予地址
    cout<<"指针的地址："<<q<<endl;
    cout<<"指针："<<*q<<endl;//指针（地址）
    cout<<"值："<<**q<<endl;//指针指向的值，在main函数中也会改变为这值
}

int main()
{
    int *p;  //这里的 * 仅仅是为了说明该 p 为指针（地址），起定义作用。
    int i,j;
    cin>>i;
    p=&i;    //指针 p(地址) = 取地址 i , *p 等同于 i
    j=*p;    //这里的 * 则是为了取值p
    int *q;
    q=p;   //q的地址等于p的地址 ，q等于p
    i=90;   //i改变则*p改变，*q也改变
    cout<<"i:"<<i<<" j:"<<j<<" *p:"<<*p<<" *q"<<*q<<endl;
    *p=132;
    cout<<"i:"<<i<<" j:"<<j<<" *p:"<<*p<<" *q"<<*q<<endl;

    cout<<"------定义指针，但未初始化其地址-------"<<endl;

    int *pp;  //此时指针指向未知，指针也未知
    cout<<"指针的地址："<<&pp<<endl;//指针的地址
    cout<<"指针："<<pp<<endl;//指针（地址）
    cout<<"值："<<*pp<<endl;//指针指向的值,因为没给指针赋值，所以它会乱指
    int ii=99;
    pp=&ii;
    fun(&pp);  //指针本身也是有地址的，传入指针的地址，从而在函数调用里也能改变指针的值
    cout<<"-----函数调用之后-----"<<endl;
    cout<<"指针的地址："<<&pp<<endl;//指针的地址
    cout<<"指针："<<pp<<endl;//指针（地址）
    cout<<"值："<<*pp<<endl;//指针指向的值,因为没给指针赋值，所以它会乱指
 }

2、递归理解-汉诺塔、数列求和、阶乘

#include <iostream>

using namespace std;
int countt=0;

int sum(int n) //求1+2+...+100的和，递归可理解为套娃，直接或间接调用自己
{
    if(n==1)
    {
        return 1;
    }else
    {
        return sum(n-1)+n;
    }
}

int multi(int n) //求阶乘，即 n！
{
    if(n==1)
    {
        return 1;
    }else
    {
        return n*multi(n-1);
    }
}

void hannuota(int n,char A,char B,char C)  //A、B、C为三个柱子
{
    //if n==1
    //   直接将A的盘子给C
    //else
    //   先将A上的n-1的盘子通过C给B
    //   再将A的盘子(只剩下最下面一个)直接给C
    //   把B的n-1个盘子通过A给C

    if(n==1)
    {
        cout<<"将编号为1的盘子通过"<<A<<"给"<<C<<endl;
    }else
    {
        hannuota(n-1,A,C,B);
        cout<<"将编号为 "<<n<<" 的盘子通过"<<A<<"给"<<C<<endl;
        hannuota(n-1,B,A,C); //重新开始新的
    }
    countt++;
}

int main()
{
    int n;

    cout<<"汉诺塔上A柱子盘子的数量:";
    cin>>n;
    hannuota(n,'A','B','C');
    cout<<"次数："<<countt<<endl;
    cout<<endl;

    cout<<"请输入要 1+2+..+ 到的值：";
    cin>>n;
    cout<<"1+2+..+ "<<n<<" 的值为："<<sum(n)<<endl;
    cout<<endl;

    cout<<"请输入要阶乘的n的值：";
    cin>>n;
    cout<<n<<"！的值为："<<multi(n)<<endl;
    cout<<endl;

    return 0;
}

3、栈理解–链实现

#include <iostream>
using namespace std;  //栈是先进后出

typedef struct node
{
    int data;
    node *pnext;
}*pnode;

struct Stack
{
    pnode ptop;
    pnode pbottom;
}*pstack;

void init_stack(Stack *S)
{
    S->ptop=S->pbottom=NULL;
}

void traverse(Stack *S)  //遍历栈
{
    pnode p;
    p=S->ptop;
    while(p!=S->pbottom)
    {
        cout<<p->data<<" ";
        p=p->pnext;
    }
    cout<<endl;
}

bool isEmpty(Stack *S)
{
    if(S->ptop==S->pbottom)
    {
        return true;
    }else
    {
        return false;
    }
}

void push(Stack *S,int data)     //入栈
{
    pnode p=new node;
    p->data=data;
    p->pnext=S->ptop;
    S->ptop=p;
}

bool pop(Stack *S,int *temp)  //出栈
{
    if(isEmpty(S))
    {
        return false;
    }else
    {
        pnode p;
        p=S->ptop;
        *temp=p->data;
        S->ptop=S->ptop->pnext;
        delete p;
        return true;
    }
}


int length_stack(Stack *S)
{
    int length=0;
    pnode p=S->ptop;
    while(p!=NULL)
    {
        p=p->pnext;
        length++;
    }
    return length;
}

void Clear(Stack *S)
{
    if(isEmpty(S))
    {
        return;
    }
    pnode p;
    p=S->ptop;
    while(p!=S->pbottom)
    {
        pnode q;
        q=p->pnext;
        delete p;
        p=q;
    }
    S->ptop=S->pbottom;
}

int main()
{
    int temp;
    Stack S;
    init_stack(&S);
    int length,data;
    cout<<"请输入栈的大小: ";
    cin>>length;
    for(int i=0;i<length;i++)
    {
        cout<<"请输入进栈值: ";
        cin>>data;
        push(&S,data);
    }
    cout<<"栈：";
    traverse(&S);
    cout<<"栈的大小为： "<<length_stack(&S)<<endl;
    if(pop(&S,&temp))
    {
        cout<<"出栈成功，出栈的元素是：";
        cout<<temp<<endl;

    }else
    {
        cout<<"出栈失败！"<<endl;
    }
    if(pop(&S,&temp))
    {
        cout<<"出栈成功，出栈的元素是：";
        cout<<temp<<endl;

    }else
    {
        cout<<"出栈失败！"<<endl;
    }
    if(pop(&S,&temp))
    {
        cout<<"出栈成功，出栈的元素是：";
        cout<<temp<<endl;

    }else
    {
        cout<<"出栈失败！"<<endl;
    }
    cout<<"栈：";
    traverse(&S);
    cout<<"栈的大小为： "<<length_stack(&S)<<endl;
    cout<<"清空栈"<<endl;
    Clear(&S);
    cout<<"栈：";
    traverse(&S);
    cout<<"栈的大小为： "<<length_stack(&S)<<endl;
    return 0;
}

4、队列理解

#include <iostream>
using namespace std;

typedef struct queue
{
    int *pbase;  //数组循环，有利于减少内存浪费
    int frontt;  //队列头部
    int rear;  //队列尾部
}Q,*pQ;

void init_queue(pQ P)
{
    int i;
    i=6;
    P->pbase=new int (i);
    //cout<<sizeof(P->pbase)<<endl;
    P->frontt=P->rear=0;
}

bool full_queue(pQ p)
{
    if((p->rear+1)%6==p->frontt)  //多用一个数组值用于判断队列是否为满，
    {
        return true;
    }else
    {
        return false;
    }
}


bool en_queue(pQ p,int val)
{
    if(full_queue(p))
    {
        cout<<"队列已满，入队失败"<<endl;
        return false;
    }
    p->pbase[p->rear]=val;
    cout<<"入队元素: "<<val<<endl;
    p->rear=(p->rear+1)%6;  //循环队列需要取余
    return true;
}

bool empty_queue(pQ p)
{
    if(p->rear==p->frontt)
    {
        return true;
    }else
    {
        return false;
    }
}

void traverse_queue(pQ p)
{
    if(empty_queue(p))
    {
        cout<<"数组为空！"<<endl;
    }else
    {
        int i = p->frontt;
        cout<<"队列：";
        while(i!=p->rear)
        {
            cout<<p->pbase[i]<<" ";
            i=(i+1)%6;
        }
        cout<<" "<<endl;
    }
}

bool out_queue(pQ p)
{
    if(empty_queue(p))
    {
        cout<<"数组为空，出队失败"<<endl;
        return false;
    }else
    {
        cout<<"出队元素："<<p->pbase[p->frontt]<<endl;
        p->frontt=(p->frontt+1)%6;
        return true;
    }
}

int main()
{
    Q q;
    init_queue(&q);
    en_queue(&q,1);
    en_queue(&q,2);
    out_queue(&q);
    en_queue(&q,3);
    en_queue(&q,4);
    en_queue(&q,5);
    en_queue(&q,6);
    out_queue(&q);
    en_queue(&q,7);
    en_queue(&q,8);
    traverse_queue(&q);
    return 0;
}

5、链表理解-用冒泡实现链表

#include <iostream>

using namespace std;
typedef struct node
{
    int data;
    node *pnext;
}*pnode; // pnode 等价于 struct node *

pnode creat_list()   //返回地址
{
    int len;//链表长度
    cout<<"请输入链表长度:";cin>>len;
    pnode phead = new node; //创建头结点
    pnode ptail=phead;  //创建尾结点
    ptail->pnext=NULL;
    for(int i=0;i<len;i++)
    {
        int n;  //结点值
        cout<<"请输入第 "<<i+1<<" 结点的数值: ";
        cin>>n;
        pnode pnew = new node;
        pnew->data=n;
        ptail->pnext=pnew;  //pnext=NULL  ->  pnext-pnew
        pnew->pnext=NULL;
        ptail=pnew;    //这里的话可以理解为ptail来控制新的pnew结点，即ptail当作刚刚新生成的结点
    }
    return phead;
}

void traverse_list(pnode phead)
{
    cout<<"链表为: ";
    pnode p=phead->pnext;//首结点
    while(p!=NULL)
    {
        cout<<p->data<<" ";
        p=p->pnext;
    }
    cout<<endl;

}

bool isEmpty(pnode phead)
{
    if(phead->pnext==NULL)
        return true;
    else
    return false;
}

int length_list(pnode phead)
{
    int length=0;
    pnode p=phead->pnext;
    while(p!=NULL)
    {
        length++;
        p=p->pnext;
    }
    return length;
}

void sort_list(pnode phead)  //冒泡排序
{
    //数组的冒泡排序，链表可类似
    int a[5] = { 199,3,9,2,5 };
    int len = 5;
    for (int i = 0; i < len - 1; i++)
    {
        for (int j = i + 1; j < len; j++)
        {
            if (a[i] > a[j])
            {
                int t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
        }
    }
    cout<<"链表冒泡排序后：";
    pnode q,p;
    int i, j;
    int length=length_list(phead);
    for (i = 0, q = phead->pnext; i < length - 1; i++, q = q->pnext) //这里发现以前一直不知道的知识点
    {                                                                //如果是for(int i=0,q=phead->pnext)会报错，这里int定义也会定义到q，都定义
        for (j = i + 1, p = q->pnext; j < length; j++, p = p->pnext)
        {
            if (q->data > p->data)
            {
                int t = q->data;
                q->data = p->data;
                p->data = t;
            }
        }
    }
    q=phead->pnext;
    for(int i=0;i<length;i++)
    {
        cout<<q->data<<" ";
        q=q->pnext;
    }
    cout<<endl;
}

bool insert_list(pnode phead,int pos,int data) //pos为插入节点位置
{
    int i=1;
    pnode p=phead;
    while(p!=NULL&&i<pos)
    {
        p=p->pnext;      //让p跳到目标结点的前一个结点
        i++;
    }
    if(p==NULL||i>pos)
    {
        return false;
    }
    pnode temp=new node;
    temp->data=data;
    temp->pnext=p->pnext;
    p->pnext=temp;
    return true;
}

bool delete_list(pnode phead,int pos)  //dos为要删除结点位置
{
    int i=1;
    pnode p=phead;
    while(p->pnext!=NULL&&i<pos) //注意得判断要删除的结点是否为空，空则说明无法删除
    {
        p=p->pnext;      //让p跳到目标结点的前一个结点
        i++;
    }
    if(p->pnext==NULL||i>pos)
    {
        return false;
    }
    pnode temp=p->pnext;
    p->pnext=p->pnext->pnext;
    delete temp;
    return true;
}

int main()
{
    int length;
    pnode phead=NULL;      //等价于struct node * phead = NULL
    phead=creat_list();    //创建链表
    if(isEmpty(phead))
    {
        cout<<"链表为空"<<endl;
        return 0;
    }
    traverse_list(phead);  //查看链表
    sort_list(phead);
    int pos,data;
    cout<<"插入结点,请输入要插入结点位置及值：";
    cin>>pos>>data;
    if(insert_list(phead,pos,data))
    {
        cout<<"插入成功!"<<endl;
        traverse_list(phead);  //查看链表
        cout<<"链表长度："<<length_list(phead)<<endl;
    }else
    {
        cout<<"插入失败"<<endl;
    }

    cout<<"删除结点,请输入要删除结点位置：";
    cin>>pos;
    if(delete_list(phead,pos))
    {
        cout<<"删除成功!"<<endl;
        traverse_list(phead);  //查看链表
        cout<<"链表长度："<<length_list(phead)<<endl;
    }else
    {
        cout<<"删除失败，你删除的结点不存在！"<<endl;
    }
    return 0;
}

6、树理解

#include <iostream>

using namespace std;

//树基本也是用到了递归的思想---  2021/2/16 23:51

struct pnode
{
    char data;
    pnode * lchild;
    pnode * rchild;
};

pnode * creat_tree();
void pre_traversal(pnode * );//先序遍历 ---先访问根结点，再先序遍历左子树，最后先序遍历右子树
void in_traversal(pnode * );//中序遍历 --- 先中序遍历左子树，再访问根结点，最后中序遍历右子树
void post_traversal(pnode * );//后序遍历 --- 先后序遍历左子树，再后序遍历右子树，最后访问根结点

int main()
{
    pnode * pT = creat_tree();
    cout<<"先序遍历: ";
    pre_traversal(pT);
    cout<<endl;

    cout<<"中序遍历: ";
    in_traversal(pT);
    cout<<endl;

    cout<<"后序遍历: ";
    post_traversal(pT);
    cout<<endl;
    return 0;
}


pnode * creat_tree()
{
    pnode * pA = new pnode;  //这里要分配地址别忘了!!!!!
    pnode * pB = new pnode;
    pnode * pC = new pnode;
    pnode * pD = new pnode;
    pnode * pE = new pnode;
    pA->data='A';
    pB->data='B';
    pC->data='C';
    pD->data='D';
    pE->data='E';
    pA->lchild=pB;
    pA->rchild=pC;
    pB->lchild=pB->rchild=NULL;
    pC->lchild=pD;
    pC->rchild=NULL;
    pD->lchild=NULL;
    pD->rchild=pE;
    pE->lchild=pE->rchild=NULL;
    return pA;
}

void pre_traversal(pnode * p)
{
    cout<<p->data<<" ";
    if(p->lchild!=NULL)
    pre_traversal(p->lchild);
    if(p->rchild!=NULL)
    pre_traversal(p->rchild);
}

void in_traversal(pnode * p)
{
    if(p->lchild!=NULL)
    in_traversal(p->lchild);
    cout<<p->data<<" ";
    if(p->rchild!=NULL)
    in_traversal(p->rchild);
}

void post_traversal(pnode * p)
{
    if(p->lchild!=NULL)
    post_traversal(p->lchild);
    if(p->rchild!=NULL)
    post_traversal(p->rchild);
    cout<<p->data<<" ";
}