数据结构考前复习

链表

插入

int Ins_(int i,int x)
{
    Node *p=NULL;
    int cnt=0;
    while(cntnxt;cnt++;
    }
    if(p==NULL)
        return -1;
    else
    {
        Node *s=new Node;
        s->data=x;
        s->nxt=p->nxt;
        p->nxt=s;
    }
}

删除

int del_(int i)
{
    Node *p;
    int cnt=0;
    while(p!=NULL&&cntnxt;cnt++;
    }
    if(p==NULL)
        return -1;
    else
    {
        Node *q=p->nxt;
        int x=q->data;
        p->nxt=q->nxt;
        delete q;
        return x;
    }
}

查找

int Locate(int x)
{
    Node *p=fs->nxt;
    int cnt=1;
    while(p!=NULL)
    {
        if(p->data==x)
            return cnt;
        else
            cnt++,p=p->nxt;
    }
    if(p==NULL)
        return -1;
}

栈和队列

//10进制转任意进制
void Change(int num,int r)
{
    int top=-1;
    while(num!=0)
    {
        d[++top]=num%r;
        num/=r;
    }
    while(top!=-1)
        coutnxt=re)
        re=NULL;
    else
    {
        Node *p=re->nxt;
        re->nxt=p->nxt;
        delete p;
    }
}

二叉树

层 次遍历

void Levelorder(Binode * root)
{
    int fr=-1,re=-1;
    Binode Q[N];
    if(root==NULL)
        return;
    Q[++re]=root;
    while(fr!=re)  
    {
        Binode *p=Q[++fr];
        coutrc!=NULL)
            Q[++re]=p->rc;
    }
}

后序遍历打印树的叶子节点

void Postleaf(Binode *root)
{
    if(root!=NULL)
    {
        Postleaf(root->lc);
        Postleaf(root->rc);
        if(root->lc==NULL&&root->rc==NULL)
        {
            coutlc=s->rc=NULL;
        bt=s;
        return bt;
    }
    if(bt->data>x)
        bt->lc=InsertBST(bt->lc,x); //要指向插入的结点
    else if(bt->datarc=InsertBST(bt->rc,x);
}

//二叉排序树的搜索
Binode SearchBST(Binode *bt,int x)
{
    if(bt==NULL) return;
    if(bt->data==x)
        return bt;
    if(bt->data>x)
        SearchBST(bt->lc,x);
    else if(bt->datarc,x);
}

排序技术

插入排序

int d[N];
int len;
//直接插入排序
void Insert()
{
    for(int i=1;i=0&&tmp=1;d/=2)
    {
        for(int i=d;i=0&&tmp