博主在2017年上半年学了数据结构,以下是总结的代码。欢迎小伙伴们阅读!
timg.jpeg

1.以下仅仅是使用C++实现的一些数据结构算法。如果说我们学技术的,我并不喜欢算法,我更喜欢花时间去编码实践,如写一个网站、写一个APP。

2.码编译与测试的环境:Linux、G++

1.顺序表的基本操作

//Test1,顺序表的基本操作
#include <iostream>            //引入IO流
#include <stdlib.h>            //引入stdlib函数库
using namespace std;            //使用命名空间
#define LIST_INIT_SIZE 100    //线性表存储空间的初始分配量为100
#define LISTINCREMENT 10        //线性表存储空间的分配增量为10(当存储空间不够时使用到)
typedef int ElemType;        //定义int类型的ElemType

//1.首先声明一个结构体,作为线性表
typedef struct{
    ElemType *elem;    //存储空间的基地址
    int length;    //当前线性表的长度
    int listSize;    //当前分配的存储容量
}SqList;

//2.创建线性表
int InitList(SqList &L){
    L.elem = (ElemType *) malloc(LIST_INIT_SIZE * sizeof(ElemType));    //开辟一个存储空间,并把这块存储空间的基地址附给elem
    if(!L.elem){
        cout<<"空间分配失败"<< endl;
        return -1;    //空间分配失败
    }
    L.length = 0;    //当前长度
    L.listSize = LIST_INIT_SIZE;    //当前分配量
    return 0;
}

//3.插入元素
int ListInsert(SqList &L, int i, ElemType e){//参数:1.被插入元素的线性表,2.要插入元素的位置,3.插入的元素
    //判断插入位置的合法性
    if(i < 1 || i > L.length + 1){
        return -1;
    }
    //判断存储空间是否够用,不够用则再分配
    if(L.length >= L.listSize){
        //使用realloc函数再分配空间,参数:1.要改变内存的空间地址,2.新分配的内存大小
        ElemType *newbase = (ElemType *) realloc(L.elem,(L.listSize + LISTINCREMENT) * sizeof(ElemType));    
        if(!newbase){
            cout<<"空间分配失败"<< endl;
            return -1;    //存储空间分配失败
        }
        L.elem = newbase;    //新基址
        L.listSize += LISTINCREMENT;    //增加容量
    }
    //插入操作
    ElemType *q,*p;    //定义2个指针变量
    q = &(L.elem[i-1]);    //q为插入位置(注意形参i是序号,序号是从从1开始的,而下标是从0开始的,因此这里转成下标后是i-1)
    for (p = &(L.elem[L.length - 1]); p >= q; --p) //从ai到an-1依次后移,后移操作要从后往前进行
    {
        *(p + 1) = *p;
    }
    *q = e;
    ++L.length;//表长度加1
    return 0;
}

//4.删除元素
int ListDelete(SqList &L, int i, ElemType &e)
{
    //判断删除位置的合法性
    if (i<1 || i>L.length) return -1;
    //删除操作
    ElemType *q, *p;//定义2个指针变量
    p = &(L.elem[i - 1]);//p为被删除元素的位置(注意形参i是序号,序号是从从1开始的,而下标是从0开始的,因此这里转成下标后是i-1)
    e = *p; //被删除的元素赋值给e(可能用不到,也可能用到,所以保存给e吧)
    q = L.elem + L.length - 1;//q指向表尾最后一个元素(q是最后一个元素的地址)
    for (++p; p <= q; ++p) //从p的下一个元素开始依次前移
    {
        *(p - 1) = *p;
    }
     
    --L.length;//表长度减1
    return 0;
}

//5.主函数测试代码
int main()
{
    SqList list;
    InitList(list);
    //给线性表list添加10个元素,值为1到10
    for (int i = 0; i < 10; i++)
    {
       ListInsert(list, i+1, i+1);
    }
    //删除第3个元素
    ElemType e;
    ListDelete(list, 3, e);
    cout<<"删除的元素是:"<<e<<endl;
 
    //在第5个位置插入一个元素-1
    ListInsert(list, 5, -1);
     
    //输出线性表
    cout<<"最后的输出结果如下"<<endl;
    for (int j = 0; j < 10; j++)
    {
        cout<<list.elem[j]<<endl;
    }

    return 0;
}

2.顺序表的两种合并

#include <iostream>             //引入IO流
#include <stdlib.h>             //引入stdlib函数库
using namespace std;                //使用std标准命名空间
typedef int ElemType;           //声明ElemType为int数据类型

/*
*定义一个作为顺序表的结构体,在结构体里包含三种数据类型:
*(1)ElemType:指针用于存放顺序表元素地址,
*(2)int型的listSize代表的是顺序表的大小,
*(3)int型length代表顺序表所包含元素的长度
*/
typedef struct{
    ElemType *elem;
    int listSize;
    int length;
}SqList;

//定义初始化顺序表的方法,参数:SqList变量的原地址
void InitSqList(SqList &L){
    //(1).调用malloc函数在堆内存申请空间,参数为需要申请的空间的大小,并强制转换为ElemType指针类型,作为要进行初始化的顺序表的内存地址
    L.elem = (ElemType *) malloc(100*sizeof(ElemType));
    //(2)声明顺序表的大小100
    L.listSize = 100;
    //(3)声明顺序表当前所包含元素的长度为0
    L.length = 0;
}

//创建顺序表的方法,参数:1.SqList,指向顺序表的空间地址,2.length,要创建的顺序表的长度,3.value要给顺序表元素的值的因子
void CreateSqList(SqList &L,int length,int value){
    //(1)初始化一个线性顺序表
    InitSqList(L);
    //(2)循坏给顺序表元素地址空间赋值
    for(int i = 0; i < length; i++){
        L.elem[i] = value * i;
    }
    //(3)声明顺序表的长度为length
    L.length = length;
}

//遍历顺序表元素、输出元素值的方法,参数:SqList,要遍历的顺序表
void Traverse(SqList L){
    for(int i = 0; i < L.length; i++){
        cout<<L.elem[i]<<"\t";
    }
    cout<<"结束"<<endl<<endl;
}

//合并算法1
//将顺序表A的元素和顺序表B元素按非递减的顺序合并到顺序表C,
//参数:1.La,顺序表A,2.Lb顺序B,3.顺序表C指向的堆内存空间地址
void MergeListAB2C(SqList La, SqList Lb, SqList &Lc){
    int i = 0, j = 0, k =0;
    //(1)从小到大的方式,将顺序表A和B中的元素插入C
    while(i < La.length && j < Lb.length){
        if(La.elem[i] < Lb.elem[j]){
            Lc.elem[k++] = La.elem[i++];
        } else{
            Lc.elem[k++] = Lb.elem[j++];
        }
    }
    
    //(2)将A、B其中一个顺序表全都插入C之后,执行以下代码,一下while循环中只有一个会被执行
    while(i < La.length){
        Lc.elem[k++] = La.elem[i++];
    }
    
    while(j < Lb.length){
        Lc.elem[k++] = Lb.elem[j++];
    }
    //(3)使Lc的长度为:La的长度加上Lb的长度
    Lc.length = La.length + Lb.length;
    
}

//合并算法2
//将顺序表A的元素和顺序表B的元素按非递减的顺序合并到顺序表A,
//参数:1.La,顺序表A的内存空间地址,2.Lb顺序表B
void MergeListAB2A(SqList &La, SqList Lb){
    ElemType e;//(1)定义一个临时指针变量
        
    La.length=La.length+Lb.length;

    int j=0;//(2)j用来记录La的索引

    for(int i=0; i<Lb.length; i++){
        //(3)遍历Lb元素,把Lb的每一个元素先给临时变量e存起来
        //GetElem(Lb,i,e);
        e = Lb.elem[i];
        //(4)while先找到Lb的元素要插入的索引位置j
        while(La.elem[j]<e){
            j=j+1;
        }
        //(5)找到合适的位置后(如La中元素为0、2、3、5、6,Lb的元素为4、5、7、9,那
        //合适的位置就是La中索引为4的位置,此位置中的元素5之后的元素要往后移动),下一行代码实现
         //InsertList_Sq(La,j,e);
        //(6)从当前记录的La的索引位置开始到La的尾端,每个元素都要往后移动一位
        for(int k=La.length-1; k>=j; k--){
            La.elem[k+1]=La.elem[k];
        }
        //(7)移动La元素结束后,当前索引位置为空,再把临时元素e放在当前La索引的位置
        La.elem[j] = e;
    }
}

int main(int argc, char const *argv[])
{
    //1.定义、创建、遍历输出La顺序表
    SqList La;
    CreateSqList(La, 8, 5);
    Traverse(La);
    //2.定义、创建、遍历输出Lb顺序表
    SqList Lb;
    CreateSqList(Lb, 8, 2);
    Traverse(Lb);


    //3.定义、初始化C,把A和B合并到C,遍历输出
    cout<<"将顺序表A和顺序表B合并到C的结果如下:"<< endl;
    SqList Lc;
    InitSqList(Lc);
    MergeListAB2C(La, Lb, Lc);
    Traverse(Lc);
    
    
    //4.将线性表A和线性表B合并到线性表A的结果如下
    cout<<"将顺序表A和顺序表B合并到A的结果如下:"<< endl;
    MergeListAB2A(La,Lb);
    Traverse(La);
    return 0;
}

3.链表的基本操作

#include <iostream> //引入标准IO流
#include <stdlib.h> //引入标准库函数
using namespace std;    //使用标准命名空间

typedef int ElemType;   //把ElemType定义为int型

//定义LNode结构体,结构体里包含data数据域和next指针域
typedef struct LNode{
    ElemType data;
    LNode* next;
}LNode;

typedef LNode* LinkList;    //定义LinkList为Lnode*的变量

//1.创建:创建链表,参数:1.链表L的地址,n:为链表L创建的元素的个数
void CreateList(LinkList& L, int n){
    L = (LinkList) malloc(sizeof(LNode));   //申请链表L申请空间
    L->next = NULL;                     //刚开始使链表的指针域为NULL,代表空链表
    
    LNode* ptail;                       //定义一个ptail临时的LNode*变量,使ptail的值总是等于链表L的尾节点的值,起到标记作用
    ptail = L;                          

    LNode* s;                           //定义一个LNode*的临时变量s,用于申请空间并暂时保存创建的链表元素
    //循环创建n个链表元素
    for(int i = 0; i < n; i++){
        s = (LNode*) malloc(sizeof(LNode)); //1.申请空间
        s->data = 5 * i;                        //2.赋值
        s->next = NULL;                     //3.使新元素指针域为空
        
        ptail->next = s;                        //4.使上一个元素的指针域指向当前创建的元素
        ptail = s;                          //5.再使patil指针的值等于当前创建成功的元素的值,即总是使patil指针指向链表L的尾节点
    }
}

//2.遍历:遍历输出链表的方法,参数:L,需要遍历输出的链表
void Traverse(LinkList L){
    LNode* p;                   //定义一个LNode*的临时变量p,用于标记链表L正在访问的元素
    p = L->next;
    
    while(p){                   //如果当前元素存在,即打印出当前元素数据域的值
        cout<<p->data<<endl;        //打印当前元素数据域的值
        p = p->next;                //打印结束后,使p指向下一个元素
    }
}


//3.插入:插入元素的方法,参数:1.L为要插入的链表,2.i为插入的位置,3.e为插入的元素,4.result为插入是否成功的结果的标记
void InsertList(LinkList &L, int i, ElemType e, int &result){
    LNode* p = L;                               //定义LNode*的临时变量p,使p指向L的地址
    int j = 0;                              //定义一个索引变量j 

    while(p && j<i-1 ){                     //使用while循环,找到第i个元素的位置,找到第i个位置即停止循环
        p = p->next;
        j = j + 1;
    }

    if(p && (j == i -1) ){                      //如果第i个位置的存在则进行插入操作
        LNode* s;                           //1.定义LNode*临时变量s,用于保存插入的元素
        s = (LNode *) malloc(sizeof(LNode));    //2.为s申请空间
        s->data = e;                            //3.赋值
        
        //插入操作,把s挂第i个位置
        s->next = p->next;
        p->next = s;

        result = 1;                         //成功,返回1
    }else {
      result = 0;                               //失败,返回0
    }
}


//删除:删除元素的实现,参数:1.L链表,2.e,需要删除的元素
void ListDelete(LinkList L,ElemType x)
{
    LNode *p,*pre;                   //pre为前驱结点,p为查找的结点。 
    p = L->next;

    while(p->data != x)              //查找值为x的元素 
    {   
        pre = p; 
        p = p->next;
    }
    //删除操作
    pre->next = p->next;          //删除操作,将其前驱指针域指向其后继指针域。 
    free(p);                      //释放空间,完成删除
} 

int main(){
    LinkList L = NULL;      //声明链表
    CreateList(L, 5);           //创建链表
    cout<<"创建链表"<< endl;
    Traverse(L);                //打印链表

    //插入测试
    cout<<"在第2个位置插入一个元素5"<< endl;
    int result = 0;
    InsertList(L, 2, 5, result);
    if (result == 1)
    {
        cout<<"插入成功"<< endl;
    }else{
        cout<<"插入失败"<< endl;
    }
    Traverse(L);        
    //删除测试
    cout<<"删除一个元素10"<< endl;
    ListDelete(L,10);           
    Traverse(L);                
    return 0;
}

4.栈的基本操作

#include <iostream>         //引入IO流
#include <stdlib.h>         //引入stdlib函数库
using namespace std;            //使用标准命名空间

typedef int SElemType;

//1.定义:构造结构体,base为栈底指针,top为栈顶指针
typedef struct SqStack{
    SElemType *base;//构造栈之前和销毁栈之后base的值都为NULL
    SElemType *top;
    int stackSize;
}SqStack;


//2.初始化:初始化栈,即构造一个空栈
void InitStack(SqStack &s){
    s.base = (SElemType *)malloc(100 * sizeof(SElemType));//分配100个分配量
    if(!s.base)exit(0);//如果分配内存失败则退出
    s.top = s.base;//使当前栈作为栈顶
    s.stackSize = 100;//记录栈的长度为100
}

//3.判断:判断栈是否为空
int isEmpty(SqStack &s){
    //如果栈顶位置为0,代表为空栈
    return (s.top == 0);
}

//4.判断栈是否已满
int isFull(SqStack &s){
    //指针索引的差等于栈大小时栈已满
    return ((s.top - s.base) == s.stackSize);
}


//5.入栈:将元素e插入栈顶
void push(SqStack &s, SElemType &e){
    if(s.top - s.base >= s.stackSize){
        cout<<"栈已满";
    }else {
        *s.top++ = e;
    }
}

//6.出栈:如栈不为空,删除栈顶元素,参数:1.操作的栈,2.用于记录删除的元素
void pop(SqStack &s, SElemType &e){
    if (s.base == s.top){
        cout<<"错误";
    }else{
        e = * --s.top;
    }
}


//7.获取栈顶元素:参数:1.从s栈中获取,2.获取的栈顶元素赋值给e
void getTop(SqStack s,SElemType &e){
    //当s.top==s.base时,代表栈中没有元素,即为空
    if(!(s.top == s.base)){
        //若栈不为空,使用e保存栈顶元素
        e = *(s.top-1);
    }
}

//8.测试栈
int main(){
    SqStack s;      //声明栈
    InitStack(s);   //初始化栈

    //循环入栈
    for (int i = 0; i < 5; ++i)
    {
        push(s,i);
        cout<< i<<"成功入栈"<< endl;
    }
    cout<< endl;

    //循环出栈
    SElemType e;            //用于记录出栈元素
    while(s.top != s.base){
        pop(s,e);
        cout<< e<<"出栈成功"<< endl;
    }

    return 0;
}

5.二叉树的先序递归遍历

#include <iostream>         //引入标准IO流
#include <stdlib.h>         //引入标准函数库
using namespace std;            //使用标准命名空间

typedef int ElemType;       //定义ElemType为int类型

//1.定义:定义二叉树
typedef struct BiTNode{
    ElemType data;          //数据域
    BiTNode *lChild;            //左子节点
    BiTNode *rChild;            //右子节点
}BiTNode,*BiTree;           //定义BiTree为BiTNode的指针变量

//2.访问:访问并打印出二叉树的节点数据域的值
void visit(BiTNode *p){
    cout<<p->data<<"  ";
}

//3.创建:创建二叉树节点,输入顺序,1.父元素,2.左子元素,3.右子元素
void create(BiTree &t){
    cout<<"请输入一个元素:";
    int v;
    cin>>v;

    if(v==0){
        t = NULL;
    }else{
        t = (BiTNode*)malloc(sizeof(BiTNode));
        t->data = v;
        create(t->lChild);
        create(t->rChild);
    }
}

//4.遍历:先序递归遍历,先序遍历二叉树的步骤包括1.打印当前节点数据域的值,2.访问左子节点,3.访问右子节点
void Traverse(BiTree t){
    if(t){
        visit(t);
        Traverse(t->lChild);
        Traverse(t->rChild);
    }
}

//5.测试函数
int main(){
    BiTree t;
    /*
    树的结构
                9
            7       6

        3          4   5
    */
    //测试时输入顺序为:9 7 3 0 0 0 6 4 0 0 5 0 0
    create(t);                  //创建
    cout<<"测试结果如下"<< endl;           
    Traverse(t);                    //遍历
    cout<< endl;
    return 0;
}

6.二叉树的先序非递归(循环)遍历

#include <iostream>         //引入IO流
#include <stdlib.h>         //引入stdlib函数库
using namespace std;

typedef int Telemtype;      //定义Telemtype为int类型

//1.定义二叉树
typedef struct BitNode{     
    Telemtype data;         //数据域
    BitNode* Lchild;            //左子节点
    BitNode* Rchild;            //右子节点
}BitNode,*Bitree;           //定义BitNode的指针变量Bitree

//2.访问:打印出数据域的值
void visit(BitNode* p){
    cout<< p->data<<" "<< endl;
}

//3.创建:参数:t为二叉树变量,函数体的功能是为t创建子节点
void creat(Bitree& t){
    cout<<"请输入一个int类型的值:";
    int i;
    cin>>i;
    if(i==0){                   //输入0代表为空
        t=NULL;
    }
    else{
        t=(BitNode*)malloc(sizeof(BitNode));
        t->data=i;
        creat(t->Lchild);
        creat(t->Rchild);
    }
}

//4.遍历1:先序非递归遍历,参数:t为要遍历的二叉树,顺序,根左右
void preorder(Bitree& t){
    BitNode* s[100];                //声明栈s,这里使用BitNode的指针数组来表示一个栈,栈的大小为100
    int top = 0;                    //标记栈顶的位置
    BitNode* p = t;             //标记正在访问的节点

    while(p||top>0){                //如果树的节点存在或者栈顶位置大于0,即开始遍历
        
        //节点存在
        if(p){                  
            visit(p);           //1.访问,打印出数据域的值
            top = top + 1;      //2.栈顶往上移
            s[top] = p;         //3.入栈
            p = p->Lchild;      //4.使p指向左子节点
        }
        //节点不存在
        else{
            p = s[top];         //1.使p变为栈顶节点,即可表述为:如果左子节点不存在,先回到父节点
            top = top-1;            //2.出栈:栈顶索引减去1
            p = p->Rchild;      //3.再让父节点访问右子节点
        }
    }
    
}
//5.遍历2:后序非递归遍历,参数:t为要遍历的二叉树,顺序,左右根
void inorder(Bitree& t){
    BitNode* s[100];                //声明栈s,这里使用BitNode的指针数组来表示一个栈,栈的大小为100
    int top = 0;                    //标记栈顶的位置
    BitNode* p = t;             //标记正在访问的节点

    while(p||top>0){                //如果树的节点存在或者栈顶位置大于0,即开始遍历
        
        //节点存在
        if(p){                  
            top = top + 1;      //栈顶往上移
            s[top] = p;         //入栈
            p = p->Lchild;      //使p指向左子节点
        }
        //节点不存在
        else{
            p = s[top];         //使p变为栈顶节点,即可表述为:如果左子节点不存在,先回到父节点
            visit(p);           //访问,打印出数据域的值
            top = top-1;            //出栈:栈顶索引减去1
            p = p->Rchild;      //再让父节点访问右子节点
        }
    }
    
}

//5.测试函数
int main(){
    //构造一个二叉树
    /*
        树的结构
                    9
                7       6

            3          4   5
    */
    //测试时输入顺序为:9 7 3 0 0 0 6 4 0 0 5 0 0
    cout<<"建立一个二叉树:"<< endl;
    Bitree t;
    creat(t);

    //非递归遍历输出
    cout<<"先序非递归遍历输出:"<< endl;
    //以下为遍历的遍历代码测试,测试的时候选择一种即可
    inorder(t);

    return 0;
}

7.顺序查找

#include <iostream>
#include <stdlib.h>
using namespace std;

typedef int ElemType;

//1.定义表
typedef struct {
    //使用数组来保存表的元素
    ElemType elem[100];
    //长度
    int length;
}SSTable;

//2.创建表。参数:1.表的长度.返回创建好的表
SSTable createTable(int len){
    SSTable table;
    table.length = len;

    //创建元素
    for(int i = 0; i < len; i++){
        table.elem[i] = i * 2;
    }

    return table;
}

//3.遍历打印已经创建的表,参数:1.要打印的表
void traverse(SSTable table){
    cout<<"表的元素如下"<< endl;
    for(int i = 0; i < table.length; i++){
        cout<< table.elem[i]<<" ";
    }
    cout<< endl<< endl;
}

//4.查找。参数:1.顺序查找的表,2.查找的表对应的元素,返回查到的位置索引,返回-1代表查不到
int orderSearch(SSTable table, int e){
    for(int i = 0; i < table.length; i++){
        if(table.elem[i] == e){
            return i;
        }
    }
    return -1;
}

//5.主函数测试
int main(){

    //创建表
    SSTable table = createTable(10);
    traverse(table);

    //查找并打印出来
    cout<<"查找元素10的索引位置为"<< orderSearch(table, 10)<< endl;
    
    return 0;
}

8.有序数组的折半查找

#include <iostream>
using namespace std;

typedef int ElemType;

//1.定义表
typedef struct {
    //使用数组来保存表的元素
    ElemType elem[100];
    //长度
    int length;
}SSTable;

//2.创建表。参数:1.表的长度.返回创建好的表
SSTable createTable(int len){
    SSTable table;
    table.length = len;

    //创建元素
    for(int i = 0; i < len; i++){
        table.elem[i] = i * 2;
    }

    return table;
}

//3.遍历打印已经创建的表,参数:1.要打印的表
void traverse(SSTable table){
    cout<<"表的元素如下"<< endl;
    for(int i = 0; i < table.length; i++){
        cout<< table.elem[i]<<" ";
    }
    cout<< endl<< endl;
}

//4.查找。折半查找,参数:1.需要查找的表,2.查找的元素
int binSearch(SSTable table, int e){
    int low = 1, high = table.length, mid;      //置区间初始值
    while(low <= high){
        mid = (low + high) / 2;
        if(table.elem[mid] < e){
            low = mid + 1;
        } else if(table.elem[mid] > e){
            high = mid - 1;
        } else{
            return mid;     //找到元素时,返回元素的所在位置的索引值
        }
    }
}

//5.主函数测试
int main(){

    //创建表
    SSTable table = createTable(10);
    traverse(table);

    //查找并打印出来
    cout<<"查找元素10的索引位置为"<< binSearch(table, 10)<< endl;
    
    return 0;
}

9.希尔排序

#include <iostream>
using namespace std;

int arrs[] = { 49, 2, 65, 44, 81, 97, 76, 13, 27, 52, 30 }; //给定的数组
int arrLen = sizeof(arrs) / sizeof(arrs[0]);           //算出数组的长度

void shellSort(int * arrs){
    int step = arrLen / 2;                                 //初始增量
    while(step > 0){
        for(int i = step; i < arrLen; i++){
          //以下对列进行排序,把大的元素放到后面
            int temp = arrs[i];
            int j;
            for(j = i-step; j>=0 && temp < arrs[j]; j=j-step){
                arrs[j+step]=arrs[j];  
            }
            arrs[j+step]=temp;
        }
        step /= 2;                                          //缩小增量
    }
}

int main()
{
    shellSort(arrs);
    cout<<"希尔排序结果如下"<< endl;
    for (int i = 0; i < arrLen; i++){
            //打印排序结果
        cout << arrs[i] << endl;
    }
    return 0;
}

10.快速排序

#include <iostream>
using namespace std;

int arrs[] = { 49, 38, 65, 44, 81, 97, 76, 13, 27, 52, 30 };
int arrLen = sizeof(arrs) / sizeof(arrs[0]);

//1.划分代码
int partition(int a[], int left, int right){
    int base = a[left]; //基准元素
    while(left < right){
        while(left < right && a[right] > base){
            --right;//从右向左找第一个比基准小的元素
        }
        a[left] = a[right];
        while(left < right && a[left] < base){
            ++left;//从左向右找第一个比基准大的元素
        }
        a[right] = a[left];
    }
    a[left] = base;
    return left;
}

//2.快速排序
void quickSort(int  a[], int left, int right){
    int i,j;
    if(left < right){
            i = partition(a, left, right);//分割
            quickSort(a, left, i-1);//将两部分分割排序
            quickSort(a, i+1, right);
    }
}

int main(){
    cout<<"原数组:"<< endl;
    for (int i = 0; i < arrLen; ++i){
            cout<< arrs[i]<<" ";
    }

    //快速排序
    quickSort(arrs, 0, arrLen - 1);

    cout<< endl<<"排序后:"<< endl;
    for (int i = 0; i < arrLen; ++i){
            cout<< arrs[i]<<" ";
    }
    cout<< endl;

    return 0;
}

11.找到链表中的第i个节点和倒数第i个指针

#include <iostream>
#include <stdlib.h>

using namespace std;

//1.定义栈,base为栈底指针,top为栈顶指针
typedef struct SqStack{
    int *base;//构造栈之前和销毁栈之后base的值都为NULL
    int *top;
    int stackSize;
}SqStack;

//2.初始化:初始化栈,即构造一个空栈
void InitStack(SqStack &s){
    s.base = (int *)malloc(100 * sizeof(int));//分配100个分配量
    if(!s.base)exit(0);//如果分配内存失败则退出
    s.top = s.base;//使当前栈作为栈顶
    s.stackSize = 100;//记录栈的长度为100
}

//3.入栈:将元素e插入栈顶
void push(SqStack &s, int &e){
    if(s.top - s.base >= s.stackSize){
        cout<<"栈已满";
    }else {
        *s.top++ = e;
    }
}

//4.出栈:如栈不为空,删除栈顶元素,参数:1.操作的栈,2.用于记录删除的元素
void pop(SqStack &s, int &e){
    if (s.base == s.top){
        cout<<"错误";
    }else{
        e = * --s.top;
    }
}

//5.定义LNode链表,结构体里包含data数据域和next指针域
typedef struct LNode{
    int data;
    LNode* next;
}LNode;

typedef LNode* LinkList;    //定义LinkList为Lnode*的变量

//6.创建链表:创建链表,参数:1.链表L的地址,n:为链表L创建的元素的个数
void createList(LinkList& L, int n){
    L = (LinkList) malloc(sizeof(LNode));   //申请链表L申请空间
    L->next = NULL;                     //刚开始使链表的指针域为NULL,代表空链表
    
    LNode* ptail;                       //定义一个ptail临时的LNode*变量,使ptail的值总是等于链表L的尾节点的值,起到标记作用
    ptail = L;                          

    LNode* s;                           //定义一个LNode*的临时变量s,用于申请空间并暂时保存创建的链表元素
    //循环创建n个链表元素
    for(int i = 0; i < n; i++){
        s = (LNode*) malloc(sizeof(LNode)); //1.申请空间
        s->data = 5 * i;                        //2.赋值
        s->next = NULL;                     //3.使新元素指针域为空
        
        ptail->next = s;                        //4.使上一个元素的指针域指向当前创建的元素
        ptail = s;                          //5.再使patil指针的值等于当前创建成功的元素的值,即总是使patil指针指向链表L的尾节点
    }
}

//7.打印链表函数,参数:要打印的链表
void displayList(LinkList l){
    LNode *p = l->next;//用p来标记正在访问的链表节点
    while(p){
        cout<<p->data<<" ";
        p = p->next;
    }
    cout<<endl;
}

12.二叉树的中序线索化

#include <iostream>
#include "stdlib.h"
using namespace std;

typedef int ELemType;
typedef enum PointerTag{Link, Thread};//枚举值:Link指针为0,Thread线索为1

typedef struct Node{
    ELemType data;
    PointerTag lTag, rTag;          //左右标志
    struct Node *lChild, *rChild;
}Node;

typedef Node *BiTree;

//创建线索二叉树:参数:t为二叉树变量,函数体的功能是为t创建子节点
void creat(BiTree& t){
    cout<<"请输入一个int类型的值:";
    int i;
    cin>>i;
    if(i==0){                   //输入0代表为空
        t=NULL;
    }
    else{
        t=(Node*)malloc(sizeof(Node));
        t->data=i;
        //初始指针标志均为Link
        t->rTag = Link; t->lTag = Link;

        creat(t->lChild);
        creat(t->rChild);
    }
}

BiTree pre;//定义前驱全局变量
//二叉树中序线索化算法:root所指的二叉树进行中序线索化, 其中pre始终指向刚访问过的结点, 其初值为NULL
void inThread(BiTree root){
    if(root != NULL){
        inThread(root->lChild);                 //线索化左子树

        if(root->lChild == NULL){
            root->lTag = Link; root->lChild = pre;      //置前驱线索
        }

        if(pre != NULL && pre->rChild == NULL){
            pre->rChild = root;                 //置后驱线索
        }

        pre = root;                             //保持pre指向root的前驱
        inThread(root->rChild);                 //右子树线索化
    }
}
//中序线索化二叉树
BiTree inOrderTread(BiTree T){
    Node *thre = new Node;//thre为头节点指针
    thre->lTag = Link; thre->rTag = Thread;//建头节点

    thre->rChild = thre;//左指针指向传进来的二叉树,右指针指向自己

    if(!T){
        //如果二叉树为空,左指针回指
        thre->lChild = thre;
    }else {
        //二叉树不为空,进行中序遍历进行中序线索化
        inThread(T);
        pre->rTag = Thread; pre->rChild = thre;//最后一个节点线索化
        thre->rChild = pre;
    }
    return thre;//返回线索化完成的二叉树
}


int main(int argc, char const *argv[])
{
    //主函数不写了,不会了^_^
    return 0;
}

13.二叉树的孩子兄弟表示法

#include <iostream>
#include <stdlib.h>
using namespace std;

typedef int ElemType;

//二叉树的孩子兄弟表示法
struct Node{
    ElemType data;
    struct Node *child, *brother;
}*CSTree;//直接定义一个Node孩子兄弟二叉树的变量CSTree

//前序遍历
void preOrder(Node *head){
    if(head == NULL){
        return;
    }
    cout<<head->data<<" ";
    preOrder(head->child);
    preOrder(head->brother);
}

//初始化树的结点
void init(){
    CSTree = (Node *) malloc(10*sizeof(Node));//申请空间
    for(int i = 0; i < 10; i++){
        CSTree[i].child = NULL;
        CSTree[i].brother = NULL;
        CSTree[i].data = i;
    }
}

//添加子节点,parent代表当点节点,child代表要添加的子节点
void addNode(Node *parent, Node *child){
    if(parent->child != NULL){
        //如果当前点已经存在孩子,那么给孩子添加兄弟
        parent->brother = child;
    }else {
        parent->child = child;
    }
}


int main(int argc, char const *argv[])
{
    init();

    //添加孩子
    addNode(&CSTree[0], &CSTree[1]);
    addNode(&CSTree[0], &CSTree[2]);
    addNode(&CSTree[1], &CSTree[3]);
    addNode(&CSTree[1], &CSTree[4]);
    addNode(&CSTree[2], &CSTree[5]);
    addNode(&CSTree[3], &CSTree[6]);
    addNode(&CSTree[5], &CSTree[7]);
    addNode(&CSTree[5], &CSTree[8]);

    //先序遍历
    preOrder(&CSTree[0]);
    
    return 0;
}

14.图的基本操作

#include <iostream>
#include <stdlib.h>
#include <stdio.h>

using namespace std;
#define VERTER_MAX 26  //定义图的最大定点数
#define MAXVALUE 32767  //定义图的最大值

//定义图
typedef struct{
    char vertex[VERTER_MAX];    //保存定点的信息的数组
    int edges[VERTER_MAX][VERTER_MAX];//用二维数组保存边的权,权值就是边的权重,其意义表示链接两个结点的边的大小或者长度等
    int isTrav[VERTER_MAX];         //遍历标志
    int edegeNum;                   //  边数量
    int graphType;                  //图的类型,无向图,或者有向图
}MatrixGraph;                   //定义邻居矩阵的图结构

//创建邻阶矩阵图
void create(MatrixGraph *g){
    int i, j, k, weight;
    char start, end;//边起终点

    cout<<"请输入各点的信息"<<endl;
    for(i = 0; i < g->vertex[i]; i++){//输入顶点
        getchar();
        printf("第%d个定点:", i);
        scanf("%c", &(g->vertex[i]));       //保存点的信息到数组元素中
    }

    cout<<"输入构成各个边的两个顶点及权值(用逗号隔开):"<<endl;
    for(k = 0; k < g->edegeNum; k++){//输入边的信息
        getchar();//暂停输入
        printf("第%d条边:", k);
        scanf("%c,%c,%c", &start, &end, &weight);

        for(i = 0; start != g->vertex[i]; i++);//在已有定点中查找起始点
        for(j = 0; end != g->vertex[j]; j++);//在已有终结点中查找终结点

        g->edges[i][j] = weight;//对应位置保存权值,表示有一条边
        if(g->graphType == 0){
            //若是无向图,在对角位置保存权值
            g->edges[j][i] = weight;
        }
    }
}

//输出邻阶表矩阵图
void outMatrix(MatrixGraph *g){
    int i,j;
    for(j = 0; j < g->edegeNum; j++){
        printf("%c\n", g->vertex[j]);;  //输出第1行的顶点信息
    }
    cout<<endl;
    for(i = 0; i < g->edegeNum; i++){
        printf("%c\n", g->vertex[i]);
        for(j = 0; j < g->edegeNum; j++){
            if(g->edges[i][j]){
                //若权值为最大值,输出无穷大符号
                printf("\t%c\n");
            }else{
                printf("\t%d\n", g->edges[i][j]);//输出边的权值
            }
        }
        cout<<endl;
    }
}

int main(int argc, char const *argv[])
{
    //主函数不写了,太费劲了
    return 0;
}

到此结束,如果你有问题,可以在文章下面留言评论