数据结构-代码（自用）

第二章：动态分配顺序表：

#include 

using namespace std;

#define InitSize 10
#define ElemType int

typedef struct
{
    ElemType *data;
    int MaxSize;    //表示当前最大长度
    int length;     //表示当前字符串长度
} SeqList;

/*
* 初始化顺序表
*/
void InitList(SeqList &L)
{
    L.data=(ElemType *)malloc(sizeof(ElemType)*InitSize);
    L.length=0;
    L.MaxSize=InitSize;
}

/*
*   求顺序表长度
*/
int Length(SeqList &L)
{
    return L.length;
}

/*
*   查找顺序表元素
*/
int LocateElem(SeqList L,ElemType e)
{
    for(int i=0; i)
    {
        if(e==L.data[i])
        {
            return i;
        }
    }
    return -1;
}

ElemType getElem(SeqList L,int i)
{
    return L.data[i-1];
}


bool listInsert(SeqList &L,int i,ElemType e)
{
    if(i<1||i>L.length+1||i>L.MaxSize)
    {
        return false;
    }

    //ElemType *p=L.data;

    for(int k=L.length; k>=i; k--)
    {
        L.data[k]=L.data[k-1];
    }
    L.data[i-1]=e;
    L.length++;
    return true;
}

void IncreaseSize(SeqList &L,int len)
{
    int *p=L.data;
    L.data=(ElemType *)malloc(sizeof(ElemType)*(L.MaxSize+len));
    for(int i=0; i)
    {
        L.data[i]=p[i];
    }
    L.MaxSize=L.MaxSize+len;
    free(p);
}

bool Empty(SeqList L)
{
    if(L.length==0)
    {
        return true;
    }
    else
    {
        return false;
    }
}
void Transpose(SeqList&L){
    for(int i=0;i2;i++){
        ElemType temp=L.data[i];
        L.data[i]=L.data[L.length-i-1];
        L.data[L.length-i-1]=temp;
    }
}

void DeleteAllNum(SeqList&L,ElemType e){
    int num=0;
    for(int i=0;i)
    {
        if(L.data[i]!=e)
        {
            L.data[num]=L.data[i];
            num++;
        }
    }
    L.length=num;
}
bool DeleteMinElm(SeqList&L,ElemType &e)
{
    if(L.length<=0)
    {
        return false;
    }
    int pos=0;
    e=L.data[0];
    for(int i=0; i)
    {
        if(e>L.data[i])
        {
            e=L.data[i];
            pos=i;
        }
    }
    L.data[pos]=L.data[L.length-1];
    L.length--;
    return true;
}

void PrintList(SeqList L)
{
    for(int i=0; i)
        cout<endl;
}

void DestoryList(SeqList &L)
{
    free(L.data);
}
int main()
{
    SeqList L;
    InitList(L);
    IncreaseSize(L,5);
    listInsert(L,1,3);
    listInsert(L,1,3);
    listInsert(L,1,3);
    listInsert(L,1,45);
    PrintList(L);
    ElemType temp;
    DeleteAllNum(L,3);
    //Transpose(L);
    //DeleteMinElm(L,temp);
    PrintList(L);
    return 0;
}

 第三章：栈与队列

顺序栈

#include 

using namespace std;
#define Maxsize 10      //栈中元素最大容量
#define ElemType int
typedef struct
{
    ElemType data[Maxsize];     //静态数组存放元素
    int top;    //栈顶指针
} SqStack;

void InitStack(SqStack &S)
{
    S.top=-1;
}

bool StackEmpty(SqStack S)
{
    if(S.top==-1)
    {
        return true;
    }
    else
    {
        return false;
    }
}

void Push(SqStack &S,ElemType X)
{
    if(S.top<Maxsize)
    {
        S.data[++S.top]=X;
    }
    else
    {
        cout<<"栈溢出"<<endl;
    }
}

void Pop(SqStack &S,ElemType &X)
{
    if(S.top>-1)
    {
        X=S.data[S.top--];
    }
    else
    {

        cout<<"已经到达栈底"<<endl;
    }
}

void GetTop(SqStack &S,ElemType &X)
{
    if(S.top>-1)
    {
        X=S.data[S.top];
    }
    else
    {

        cout<<"栈已经空"<<endl;
    }
}

void Destory(SqStack &S)
{
    S.top=-1;
}

int main()
{
    SqStack S;
    InitStack(S);
    Push(S,6);
    int x,y;
    Pop(S,x);
    cout<","<endl;
    cout<<StackEmpty(S);
    return 0;
}

 循环队列：

#include 

using namespace std;
#define Maxsize 3
#define ElemType int
typedef struct
{
    ElemType data[Maxsize];
    int front;
    int rear;
} SeqQueue;

void InitQueue(SeqQueue &Q)
{
    Q.front=0;      //表示队头    出队
    Q.rear=0;       //表示队列尾     入队
}

/*判断队空*/
bool QueueEmpty(SeqQueue Q)
{
    if(Q.front==Q.rear)
    {
        return true;
    }
    else
    {
        return false;
    }
}


bool EnQueue(SeqQueue &Q,ElemType X)
{
    if(Q.front==(Q.rear+1)%(Maxsize))     //留一个位置
    {
        cout<<"c出错了;"<";"<endl;
        return false;
    }
    else
    {
        cout<";"<endl;
        Q.data[Q.rear++]=X;
        return true;
    }

}

bool DeQueue(SeqQueue &Q,ElemType &X)
{
    if(Q.rear==Q.front)
    {
        cout<<"队列为空"<<endl;
        return false;
    }
    else
    {
        X=Q.data[Q.front++];
        return true;
    }

}

bool GetHead(SeqQueue Q,ElemType &X)
{
    if(Q.rear==Q.front)
    {
        return false;
    }
    else
    {
        X=Q.data[Q.front];
        return true;
    }
}


int main()
{
    SeqQueue S;
    InitQueue(S);
    ElemType a,b,c;

    cout<<QueueEmpty(S);
    EnQueue(S,1);
    EnQueue(S,2);
    cout<<QueueEmpty(S);
    EnQueue(S,3);
    DeQueue(S,a);
    DeQueue(S,b);
    DeQueue(S,c);
    cout<c;
    return 0;
}

 括号匹配

#include 

using namespace std;
#define MaxSize 10
#define Elemtype char


typedef struct
{
    Elemtype data[MaxSize];
    int top;
} SeqStack;

void InitStack(SeqStack &S)
{
    S.top=-1;
}

bool Push(SeqStack &S,Elemtype x)
{
    if(S.top==MaxSize)
    {
        return false;
    }
    else
    {
        S.data[++S.top]=x;
        return true;
    }
}

bool Pop(SeqStack &S,Elemtype &x)
{
    if(S.top==-1)
    {
        return false;
    }
    else
    {
        x=S.data[S.top--];
        return true;
    }
}

bool Gettop(SeqStack &S,Elemtype &x)
{
    if(S.top==-1)
    {
        return false;
    }
    else
    {
        x=S.data[S.top];
        return true;
    }
}

bool StackEmpty(SeqStack S)
{
    if(S.top==-1)
        return true;
    else
        return false;
}

bool bracketCheck(char str[],int length)
{
    SeqStack S;
    InitStack(S);
    for(int i=0; i)
    {
        if(str[i]=='('||str[i]=='{'||str[i]=='[')
            Push(S,str[i]);
        else
        {
            if(StackEmpty(S))
                return false;
            char topElem;
            Pop(S,topElem);
            if(str[i]==')'&&topElem!='(')
                return false;
            if(str[i]==']'&&topElem!='[')
                return false;
            if(str[i]=='}'&&topElem!='{')
                return false;
        }
    }
    return StackEmpty(S);
}
int main()
{
    cout<"({[]})",6)<<endl;
    return 0;
}

 二叉树

#include 

using namespace std;
#define ElemType char
typedef struct BiTNode
{
    ElemType data;
    struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;


//先序建立二叉树
void CreateBTree(BiTree &S)
{
    ElemType ch;
    cin>>ch;
    //如果输入为#，表示无结点
    if(ch=='#')
    {
        S=NULL;
    }
    else
    {
        S=(BiTNode*)malloc(sizeof(BiTNode));
        S->data=ch;
        cout<data<<endl;
        CreateBTree(S->lchild);
        CreateBTree(S->rchild);
    }
}

void prePrint(BiTree S)
{
    if(S!=NULL)
    {
        cout<data;
        print(S->lchild);
        print(S->rchild);
    }
    else
    {
        return;
    }
}

int main()
{

    //定义二叉树根
    BiTree root=NULL;
    //创建二叉树
    CreateBTree(root);
    //先序输出二叉树
    prePrint(root);
    return 0;
}

 快速排序：

分治思想，选择基准，分成大于基准的与小于基准的（进行元素交换），对于分成的俩队再递归调用

#include 

using namespace std;
void QuickSort(int *array,int left,int right)
{
    if(left>=right)
    {
        return;
    }
    else
    {
        int Base=array[left];
        int low=left;
        int high=right;

        while(low<high)
        {
            while(array[high]>=Base&&low<high)
            {
                high--;
            }
            array[low]=array[high];

            while(array[low]<=Base&&low<high)
            {
                low++;
            }
            array[high]=array[low];

        }
        array[low]=Base;
        QuickSort(array,left,low-1);
        QuickSort(array,low+1,right);
    }

}

int main()
{
    int array[]= {2,5,8,9,1,5,6,2};
    QuickSort(array,0,7);
    for(int i=0; i<=7; i++)
        cout<<array[i];
    return 0;
}

 插入排序：

#include 

using namespace std;

#define Elemtype int

void InsertSort(Elemtype A[],int n) //A表示待排序序列（下标从零开始）  n表示序列长度
{
    int i,j,temp;
    for(i=1; i//扫描未排序序列，i前面已经排序
    {
        if(A[i]1]) //看是否小于已排序序列最大项目    123456[4]  //此时6最大
        {
            temp=A[i];

            for(j=i-1; j>=0&&temp//从已排序序列中 找合适位置插入,该算法具有稳定性
            {
                A[j+1]=A[j];
            }
            A[j+1]=temp;     //循环完后还会执行j--
        }
    }
}
int main()
{
    int a[]= {1,12,4,8,6,9,2,5,8,4,126,7,4,5,9,6,5,8,8,5,8,7,9,6,2};

    cout<<"排序前：";
    for(int i=0; i<(int)sizeof(a)/4; i++)
    {
        cout<" ";
    }
    InsertSort(a,sizeof(a)/4);
    cout<<"\n排序后：";
    for(int i=0; i<(int)sizeof(a)/4; i++)
    {
        cout<" ";
    }
    cout<<endl;
    return 0;
}

折半插入排序：

#include 

using namespace std;

#define Elemtype int

void InsertSort(Elemtype A[],int n) //A表示待排序序列（下标从零开始）  n表示序列长度
{
    int i,j,temp;
    int low,high,mid;
    for(i=1; i//扫描未排序序列，i前面已经排序
    {
        if(A[i]1]) //看是否小于已排序序列最大项目    123456[4]  //此时6最大
        {
            temp=A[i];
            low=0;
            high=i-1;
            while(low<=high)
            {
                mid=(low+high)/2;
                if(temp>=A[mid])
                {
                    low=mid+1;
                }
                else
                {
                    high=mid-1;
                }
            }

            for(j=i-1; j>=high+1; j--)   //从已排序序列中 找合适位置插入,该算法具有稳定性
            {
                A[j+1]=A[j];
            }
            A[j+1]=temp;     //循环完后还会执行j--
        }
    }
}
int main()
{
    int a[]= {3,2,1};

    cout<<"排序前：";
    for(int i=0; i<(int)sizeof(a)/4; i++)
    {
        cout<" ";
    }
    InsertSort(a,sizeof(a)/4);
    cout<<"\n排序后：";
    for(int i=0; i<(int)sizeof(a)/4; i++)
    {
        cout<" ";
    }
    cout<<endl;
    return 0;
}

 希尔排序：

#include 

using namespace std;

#define ElemType int

void ShellSort(ElemType a[],int n){
    int i,j,temp;
    for(int gap=n/2;gap>=1;gap/=2)  //首次步长为数组长度的一半
    {
        for(i=gap;i//例如  123456  步长为3   (由于数组在计算机从0开始）(a[gap])4-1 5-2 6-3
        {
            if(a[i]gap])
            {
                temp=a[i];
                for(j=i-gap;j>=0&&tempgap)
                {
                    a[j+gap]=a[j];
                }
                a[j+gap]=temp;
            }
        }

    }
}
int main()
{
    int A[]={5,8,6,5,4,2,1,7};
    ShellSort(A,8);
    for(int i=0;i<8;i++)
    {
        cout<" ";
    }
    return 0;
}

 归并排序：

#include 

using namespace std;
#define Elemtype int

//辅助数组
Elemtype *B=(Elemtype*)malloc((50)*sizeof(Elemtype));

/*
    将俩个有序数组合并
    Merge（数组，开始位置，中间位置，结束位置）
*/
void Merge(Elemtype A[],int low,int mid,int high)
{
    //cout<//A[low,mid]与A[mid+1,high]有序  将他合并
    int i,j,k;

    //先将A中元素复制到辅助数组B中
    for(int z=0; z<=high; z++)
    {
        B[z]=A[z];
    }

    //k表示记录当前排序的开始位置
    for(i=low,j=mid+1,k=i; i<=mid&&j<=high; k++)
    {
        //如果B[i]<=B[j]  将B[i]复制到A数组中，将i指针后移动，j指针不动
        if(B[i]<=B[j])
        {
            A[k]=B[i];
            i++;
        }
        else
        {
            A[k]=B[j];
            j++;
        }
    }

    //假如一边有剩余直接添加到数组后边
    while(i<=mid)A[k++]=B[i++];
    while(j<=high)A[k++]=B[j++];

}


//递归 从2个元素合并开始
void sort(int arr[],int left,int right)
{
    if(left<right)
    {
        int mid = (left+right)/2;
        sort(arr,left,mid);//左边归并排序，使得左子序列有序
        sort(arr,mid+1,right);//右边归并排序，使得右子序列有序
        Merge(arr,left,mid,right);//将两个有序子数组合并操作
    }
}



int main()
{
    int A[]= {5,8,6,9,6,2,1,4,5};
    for(int i=0; i<(int)sizeof(A)/sizeof(int); i++)
        cout <" ";
    cout<<endl;
    sort(A,0,(int)sizeof(A)/sizeof(int));
    for(int i=0; i<(int)sizeof(A)/sizeof(int); i++)
        cout <" ";
    return 0;
}