scau数据结构实验

news/2024/10/31 5:31:27/

目录

顺序线性表的基本操作     

合并顺序表 

顺序表逆置 

链式线性表的基本操作 

合并链表 

**反转链表 **

**顺序栈的基本操作**

栈的应用——进制转换 

括号匹配检验 

**汉诺塔问题**

计算next值

**KMP算法** 

不完整的排序 

二叉树的构建及遍历操作 

求二叉树各种节点数

二叉树的宽度 

**二叉树的直径**

顺序查找 

二分查找 

哈希查找 

直接插入排序 

折半插入排序 

希尔(shell)排序 

**冒泡排序**

快速排序 

简单选择排序 


写到快排,接下来连续修改 

顺序线性表的基本操作     

#include<stdio.h>
#include<malloc.h>
#define OK 1 
#define ERROR 0
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define ElemType inttypedef struct
{int *elem;int length;int listsize;
}SqList;int InitList_Sq(SqList &L)
{
// 算法2.3,构造一个空的线性表L,该线性表预定义大小为LIST_INIT_SIZE
// 请补全代码L.listsize=LIST_INIT_SIZE;L.elem=new int[LIST_INIT_SIZE+1];L.length=0;return OK;
}int Load_Sq(SqList &L)
{
// 输出顺序表中的所有元素int i;if(L.length==0) printf("The List is empty!");  // 请填空else{printf("The List is: ");for(int i=1;i<=L.length;++i) printf("%d ",L.elem[i]);  // 请填空}printf("\n");return OK;
}int ListInsert_Sq(SqList &L,int i,int e)
{
// 算法2.4,在顺序线性表L中第i个位置之前插入新的元素e
// i的合法值为1≤i≤L.length +1
// 请补全代码if(i<1||i>L.length+1)return ERROR;for(int j=L.length;j>=i;--j){L.elem[j+1]=L.elem[j];}L.elem[i]=e;L.length++;return OK;
}int ListDelete_Sq(SqList &L,int i, int &e)
{
// 算法2.5,在顺序线性表L中删除第i个位置的元素,并用e返回其值
// i的合法值为1≤i≤L.length
// 请补全代码if(i<1||i>L.length)return ERROR;e=L.elem[i];for(int j=i;j<=L.length-1;++j){L.elem[j]=L.elem[j+1];}L.length--;return OK;
}int main()
{SqList T;int a, i;ElemType e, x;if(InitList_Sq(T))    // 判断顺序表是否创建成功{printf("A Sequence List Has Created.\n");}while(1){printf("1:Insert element\n2:Delete element\n3:Load all elements\n0:Exit\nPlease choose:\n");scanf("%d",&a);switch(a){case 1: scanf("%d%d",&i,&x);if(!ListInsert_Sq(T,i,x)) printf("Insert Error!\n"); // 执行插入函数,根据返回值判断i值是否合法else printf("The Element %d is Successfully Inserted!\n", x); break;case 2: scanf("%d",&i);if(!ListDelete_Sq(T,i,e)) printf("Delete Error!\n"); // 执行删除函数,根据返回值判断i值是否合法else printf("The Element %d is Successfully Deleted!\n", e);break;case 3: Load_Sq(T);break;case 0: return 1;}}
}


合并顺序表 

#include<iostream>
#include<algorithm>using namespace std;int a[100];int main()
{int n,m;cin>>n;for(int i=0;i<n;++i){cin>>a[i];}cout<<"List A:";for(int i=0;i<n;++i){cout<<a[i]<<' ';}cout<<endl;cin>>m;for(int i=n;i<n+m;++i){cin>>a[i];}cout<<"List B:";for(int i=n;i<n+m;++i){cout<<a[i]<<' ';}cout<<endl;sort(a,a+n+m);cout<<"List C:";for(int i=0;i<n+m;++i){cout<<a[i]<<' ';}return 0;
}

顺序表逆置 

#include<iostream>
#include<algorithm>using namespace std;int a[100];int main()
{int n;cin>>n;for(int i=0;i<n;++i){cin>>a[i];}cout<<"The List is:";for(int i=0;i<n;++i){cout<<a[i]<<' ';}cout<<endl;cout<<"The turned List is:";for(int i=n-1;i>=0;--i){cout<<a[i]<<' ';}return 0;
}


链式线性表的基本操作 

#include<stdio.h>
#include<malloc.h>
#define ERROR 0
#define OK 1 
#define ElemType inttypedef struct LNode
{int data;struct LNode *next;
}LNode,*LinkList;int CreateLink_L(LinkList &L,int n){
// 创建含有n个元素的单链表LinkList p,q;int i;ElemType e;L = new LNode;L->next = NULL;              // 先建立一个带头结点的单链表q = L;for (i=0; i<n; i++) {scanf("%d", &e);p = new LNode;  // 生成新结点// 请补全代码p->data=e;p->next=NULL;q->next=p;q=p; }return OK;
}int LoadLink_L(LinkList &L){
// 单链表遍历LinkList p = L->next;if(!p)printf("The List is empty!"); // 请填空else{printf("The LinkList is:");while(p)    // 请填空{printf("%d ",p->data); p=p->next;    // 请填空}}printf("\n");return OK;
}int LinkInsert_L(LinkList &L,int i,ElemType e){
// 算法2.9
// 在带头结点的单链线性表L中第i个位置之前插入元素e
// 请补全代码LinkList p=L,q;int j=1;while(j<i&&p){p=p->next;++j;}if(i<1||!p){return ERROR;}q=new LNode;q->data=e;q->next=p->next;p->next=q;return OK;}int LinkDelete_L(LinkList &L,int i, ElemType &e){
// 算法2.10
// 在带头结点的单链线性表L中,删除第i个元素,并用e返回其值
// 请补全代码LNode* p,*q;p=L;int j=1;while(j<i&&p->next){p=p->next;j++;}if(i<1||!p->next){return ERROR;}q=p->next;e=q->data;p->next=p->next->next;delete q;return OK;
}int main()
{LinkList T;int a,n,i;ElemType x, e;printf("Please input the init size of the linklist:\n");scanf("%d",&n);printf("Please input the %d element of the linklist:\n", n);if(CreateLink_L(T,n))     // 判断链表是否创建成功,请填空{printf("A Link List Has Created.\n");LoadLink_L(T);}while(1){printf("1:Insert element\n2:Delete element\n3:Load all elements\n0:Exit\nPlease choose:\n");scanf("%d",&a);switch(a){case 1: scanf("%d%d",&i,&x);if(!LinkInsert_L(T,i,x)) printf("Insert Error!\n"); // 判断i值是否合法,请填空else printf("The Element %d is Successfully Inserted!\n", x); break;case 2: scanf("%d",&i);if(!LinkDelete_L(T,i,e)) printf("Delete Error!\n"); // 判断i值是否合法,请填空else printf("The Element %d is Successfully Deleted!\n", e);break;case 3: LoadLink_L(T);break;case 0: return 1;}}
}

合并链表 

#include<iostream>
#include<algorithm>using namespace std;int a[100];int main()
{int n,m;cin>>n;for(int i=0;i<n;++i){cin>>a[i];}cout<<"List A:";for(int i=0;i<n;++i){cout<<a[i]<<' ';}cout<<endl;cin>>m;for(int i=n;i<n+m;++i){cin>>a[i];}cout<<"List B:";for(int i=n;i<n+m;++i){cout<<a[i]<<' ';}cout<<endl;sort(a,a+n+m);cout<<"List C:";for(int i=0;i<n+m;++i){cout<<a[i]<<' ';}return 0;
}


**反转链表 **

保存cur的next

让cur的next指向pre

然后还原回原来的相对位置

nex = cur->next;
cur->next = pre;
pre = cur;
cur = nex;

**顺序栈的基本操作**

栈空:S.base==S.top;

栈满:S.top-S.base==size;

S.top指向栈顶的后一个元素

#include<malloc.h> 
#include<stdio.h> 
#define OK 1
#define ERROR 0
#define STACK_INIT_SIZE 100 // 存储空间初始分配量
#define STACKINCREMENT 10 // 存储空间分配增量typedef int SElemType; // 定义栈元素类型
typedef int Status; // Status是函数的类型,其值是函数结果状态代码,如OK等struct SqStack
{SElemType *base; // 在栈构造之前和销毁之后,base的值为NULLSElemType *top; // 栈顶指针int stacksize; // 当前已分配的存储空间,以元素为单位
}; // 顺序栈Status InitStack(SqStack &S)       
{      
// 构造一个空栈S,该栈预定义大小为STACK_INIT_SIZE
// 请补全代码S.base=new int[STACK_INIT_SIZE];S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;
}Status Push(SqStack &S,SElemType e)   
{
// 在栈S中插入元素e为新的栈顶元素
// 请补全代码if(S.top-S.base==S.stacksize){return ERROR;}*S.top++ =e;return OK;
}Status Pop(SqStack &S,SElemType &e)   
{
// 若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR
// 请补全代码if(S.top==S.base){return ERROR;}e= *--S.top;return OK;
}Status GetTop(SqStack S,SElemType &e)   
{ 
// 若栈不空,则用e返回S的栈顶元素,并返回OK;否则返回ERROR
// 请补全代码if(S.top==S.base){return ERROR;}e= *(S.top-1);return OK;
}int StackLength(SqStack S) 
{
// 返回栈S的元素个数
// 请补全代码return S.top-S.base;
}Status StackTraverse(SqStack S)
{
// 从栈顶到栈底依次输出栈中的每个元素SElemType *p  =  S.top;        //请填空if(S.top==S.base)printf("The Stack is Empty!"); //请填空else{printf("The Stack is: ");while(p!=S.base)            //请填空{p--;               //请填空printf("%d ", *p);}}printf("\n");return OK;
}int main()
{int a;SqStack S;
SElemType x, e;if(InitStack(S))    // 判断顺序表是否创建成功,请填空
{printf("A Stack Has Created.\n");
}
while(1){printf("1:Push \n2:Pop \n3:Get the Top \n4:Return the Length of the Stack\n5:Load the Stack\n0:Exit\nPlease choose:\n");scanf("%d",&a);switch(a){case 1: scanf("%d", &x);if(!Push(S,x)) printf("Push Error!\n"); // 判断Push是否合法,请填空else printf("The Element %d is Successfully Pushed!\n", x); break;case 2: if(!Pop(S,e)) printf("Pop Error!\n"); // 判断Pop是否合法,请填空else printf("The Element %d is Successfully Poped!\n", e);break;case 3: if(!GetTop(S,e))printf("Get Top Error!\n"); // 判断Get Top是否合法,请填空else printf("The Top Element is %d!\n", e);break;case 4: printf("The Length of the Stack is %d!\n",StackLength(S)); //请填空break;case 5: StackTraverse(S);  //请填空break;case 0: return 1;}}
}

循环队列的基本操作 

队空:Q.front==Q.rear;

队满:(Q.front+1)%MAXSIZE==Q.rear 

#include<malloc.h> 
#include<stdio.h> 
#define OK 1
#define ERROR 0
typedef int Status; // Status是函数的类型,其值是函数结果状态代码,如OK等
typedef int QElemType;
#define MAXQSIZE 100 // 最大队列长度(对于循环队列,最大队列长度要减1)typedef struct
{QElemType *base; // 初始化的动态分配存储空间int front; // 头指针,若队列不空,指向队列头元素int rear; // 尾指针,若队列不空,指向队列尾元素的下一个位置}SqQueue;Status InitQueue(SqQueue &Q)   
{
// 构造一个空队列Q,该队列预定义大小为MAXQSIZE
// 请补全代码Q.base=new int[MAXQSIZE];Q.front=Q.rear=0;return OK;
}Status EnQueue(SqQueue &Q,QElemType e)  
{ 
// 插入元素e为Q的新的队尾元素
// 请补全代码if((Q.rear+1)%MAXQSIZE==Q.front){return ERROR;}Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;return OK;
}Status DeQueue(SqQueue &Q, QElemType &e) 
{  
// 若队列不空, 则删除Q的队头元素, 用e返回其值, 并返回OK; 否则返回ERROR
// 请补全代码if(Q.front==Q.rear){return ERROR;}e=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;return OK;
}Status GetHead(SqQueue Q, QElemType &e)
{	
// 若队列不空,则用e返回队头元素,并返回OK,否则返回ERROR
// 请补全代码if(Q.front==Q.rear){return ERROR;}e=Q.base[Q.front];return OK;
}int QueueLength(SqQueue Q)  
{
// 返回Q的元素个数
// 请补全代码return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}Status QueueTraverse(SqQueue Q)  
{ 
// 若队列不空,则从队头到队尾依次输出各个队列元素,并返回OK;否则返回ERROR.int i;i=Q.front;if(Q.front==Q.rear)printf("The Queue is Empty!");  //请填空else{printf("The Queue is: ");while(i%MAXQSIZE!=Q.rear)     //请填空{printf("%d ",Q.base[i] );   //请填空i = (i+1)%MAXQSIZE;   //请填空}}printf("\n");return OK;
}int main()
{int a;SqQueue S;QElemType x, e;if(InitQueue(S))    // 判断顺序表是否创建成功,请填空{printf("A Queue Has Created.\n");}while(1){printf("1:Enter \n2:Delete \n3:Get the Front \n4:Return the Length of the Queue\n5:Load the Queue\n0:Exit\nPlease choose:\n");scanf("%d",&a);switch(a){case 1: scanf("%d", &x);if(!EnQueue(S,x)) printf("Enter Error!\n"); // 判断入队是否合法,请填空else printf("The Element %d is Successfully Entered!\n", x); break;case 2: if(!DeQueue(S,e)) printf("Delete Error!\n"); // 判断出队是否合法,请填空else printf("The Element %d is Successfully Deleted!\n", e);break;case 3: if(!GetHead(S,e))printf("Get Head Error!\n"); // 判断Get Head是否合法,请填空else printf("The Head of the Queue is %d!\n", e);break;case 4: printf("The Length of the Queue is %d!\n",QueueLength(S));  //请填空break;case 5: QueueTraverse(S); //请填空break;case 0: return 1;}}
}


栈的应用——进制转换 

#include<stdio.h>int main(){int n;scanf("%d",&n);printf("%o",n);return 0;
}


括号匹配检验 

typedef char SElemType;
#include"malloc.h" 
#include"stdio.h"
#include"math.h"
#include"stdlib.h" // exit()
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status; // Status是函数的类型,其值是函数结果状态代码,如OK等
#define STACK_INIT_SIZE 10 // 存储空间初始分配量
#define STACKINCREMENT 2 // 存储空间分配增量
struct SqStack
{SElemType *base; // 在栈构造之前和销毁之后,base的值为NULLSElemType *top; // 栈顶指针int stacksize; // 当前已分配的存储空间,以元素为单位}; // 顺序栈
Status InitStack(SqStack &S)
{ S.base=new char[STACK_INIT_SIZE];S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;
}Status StackEmpty(SqStack S)
{ if(S.top==S.base){return true;}return ERROR;}
Status Push(SqStack &S,SElemType e)
{ if(S.top-S.base==STACK_INIT_SIZE){return ERROR;} *S.top++=e;return OK;}Status Pop(SqStack &S,SElemType &e)
{ if(S.top==S.base){return OK;}e=*--S.top;return OK;}
void check(){ // 对于输入的任意一个字符串,检验括号是否配对SqStack s;SElemType ch[80],*p,e;if(InitStack(s)) // 初始化栈成功{//printf("请输入表达式\n");scanf("%s",ch);p=ch;while(*p) // 没到串尾switch(*p){case '(':case '[':Push(s,*p);p++;break; // 左括号入栈,且p++case ')':case ']':if(!StackEmpty(s)) // 栈不空{Pop(s,e); // 弹出栈顶元素if(*p==')'&&e!='('|| *p==']'&&e!='[') {// 弹出的栈顶元素与*p不配对printf("isn't matched pairs\n");exit(ERROR);}else{p++;break; // 跳出switch语句}}else // 栈空{printf("lack of left parenthesis\n");exit(ERROR);}default: p++; // 其它字符不处理,指针向后移}if(StackEmpty(s)) // 字符串结束时栈空printf("matching\n");elseprintf("lack of right parenthesis\n");}}
int main(){check();}

行编辑程序 

Push函数注意 

typedef char SElemType;
#include"malloc.h" 
#include"stdio.h"
#include"math.h"
#include"stdlib.h" // exit()
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status; // Status是函数的类型,其值是函数结果状态代码,如OK等
#define STACK_INIT_SIZE 10 // 存储空间初始分配量#define STACKINCREMENT 2 // 存储空间分配增量
struct SqStack
{SElemType *base; // 在栈构造之前和销毁之后,base的值为NULLSElemType *top; // 栈顶指针int stacksize; // 当前已分配的存储空间,以元素为单位
}; // 顺序栈Status InitStack(SqStack &S)
{ // 构造一个空栈SS.base=new char[STACK_INIT_SIZE];S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;}
Status StackEmpty(SqStack S){ // 若栈S为空栈,则返回TRUE,否则返回FALSEif(S.top==S.base){return true; }return false;}
Status ClearStack(SqStack &S){ // 把S置为空栈S.top=S.base;return OK;}
Status DestroyStack(SqStack &S){ // 销毁栈S,S不再存在free(S.base);S.base=NULL;S.top=NULL;S.stacksize=0;return OK;}
Status Push(SqStack &S,SElemType e){ // 插入元素e为新的栈顶元素if(S.top-S.base>=S.stacksize){S.base=(char*)realloc(S.base,sizeof(char)*(S.stacksize+STACKINCREMENT));S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;return OK;}Status Pop(SqStack &S,SElemType &e){ // 若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERRORif(S.base==S.top){return ERROR;}e=*--S.top;return OK;}
Status StackTraverse(SqStack S,Status(*visit)(SElemType)){ // 从栈底到栈顶依次对栈中每个元素调用函数visit()。// 一旦visit()失败,则操作失败while(S.top>S.base)visit(*S.base++);printf("\n");return OK;}
Status visit(SElemType c){printf("%c",c);return OK;}void LineEdit(){ // 利用字符栈s,从终端接收一行并送至调用过程的数据区。算法3.2SqStack s;char ch,c;int n,i;InitStack(s);scanf("%d",&n);ch=getchar();for(i=1;i<=n;i++){ ch=getchar();while(ch!='\n'){switch(ch){case '#':Pop(s,c);break; // 仅当栈非空时退栈case '@':ClearStack(s);break; // 重置s为空栈default :Push(s,ch); // 有效字符进栈}ch=getchar(); // 从终端接收下一个字符}StackTraverse(s,visit); // 将从栈底到栈顶的栈内字符输出ClearStack(s); // 重置s为空栈}DestroyStack(s);}int main(){LineEdit(); return 0;}

表达式求值 

#include<cstdlib>
#include<cstdio>
#include <iostream>
#include <cstring>
#define OK 1
#define ERROR 0
#define STACK_INIT_SIZE 100 // 存储空间初始分配量
#define STACKINCREMENT 10 // 存储空间分配增量

typedef int SElemType; // 定义栈元素类型
typedef int Status; // Status是函数的类型,其值是函数结果状态代码,如OK等
using namespace  std;
struct SqStack
{
    SElemType *base; // 在栈构造之前和销毁之后,base的值为NULL
    SElemType *top; // 栈顶指针
    int stacksize; // 当前已分配的存储空间,以元素为单位
}; // 顺序栈

Status InitStack(SqStack &S)
{
// 构造一个空栈S,该栈预定义大小为STACK_INIT_SIZE
    S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
    if(!S.base) return ERROR;
    S.top=S.base;
    S.stacksize=STACK_INIT_SIZE;
    return OK;
}

Status Push(SqStack &S,SElemType e)
{
// 在栈S中插入元素e为新的栈顶元素
    if(S.top-S.base>=S.stacksize)
    {
        S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
        if(!S.base) return ERROR;
        S.top=S.base+S.stacksize;
        S.stacksize+=STACKINCREMENT;
    }
    *S.top++=e;
    return OK;
}

Status Pop(SqStack &S,SElemType &e)
{
// 若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR
    if(S.top==S.base) return ERROR;
    e=*--S.top;
    return OK;
}

Status GetTop(SqStack S,SElemType &e)
{
// 若栈不空,则用e返回S的栈顶元素,并返回OK;否则返回ERROR
    if(S.top==S.base) return ERROR;
    e=*(S.top-1);
    return OK;
}

int StackLength(SqStack S)
{
// 返回栈S的元素个数
    int i;
    i=S.top-S.base;
    return i;
}

Status StackTraverse(SqStack S)
{
// 从栈顶到栈底依次输出栈中的每个元素
    SElemType *p = (SElemType *)malloc(sizeof(SElemType));
    p = S.top;
    if(S.top==S.base)printf("The Stack is Empty!");
    else
    {
        printf("The Stack is: ");
        p--;
        while(p>=S.base)
        {
            printf("%d ", *p);
            p--;
        }
    }
    printf("\n");
    return OK;
}

char prio(char e,char c){//比较运算符优先级
    char n;
    switch(c){
        case'+':
        case'-':{
            if(e=='('||e=='=') n='<';  //c>e
            else n='>';}break;
        case'*':
        case'/':{
            if(e=='*'||e=='/'||e==')') n='>';//c<e
            else n='<';}break;
        case'(':{
            if(e==')')
            {
                printf("括号不匹配\n");
                exit(ERROR);
            }
            else n='<';} //c>e;
            break;
        case')':{
            if(e=='(') n='=';
            else if(e=='=') {printf("缺少左括号\n");exit(ERROR);}
            else n='>';
        }//e>c
            break;
        case'=':{
            if(e=='=') n='=';
            else if(e=='(') {printf("缺少右括号\n");exit(ERROR);}
            else n='>';
        } //e>c
    }//switch

    return n;
}

int main()
{
    SqStack s1,s2;//s1操作数栈,s2算符栈
    InitStack(s1);
    InitStack(s2);
    Push(s2,'=');
    char w;
    w=getchar();
        int e;
        GetTop(s2,e);
        while(w!='='||e!='=')
        {
          //  cout<<w<<endl;
          int d=0;
          if(w>='0'&&w<='9') {
              while (w >= '0' && w <= '9') {
                  d = d * 10 + (w - '0');
                  w = getchar();
              }
              Push(s1, d);
             // cout << d << endl;
          }
          else {
              if (prio(e, w) == '<') {
                  //cout<<"123"<<endl;
                  Push(s2, w);
                  //StackTraverse(s1);
                  w = getchar();

              } else if (prio(e, w) == '=' && w == ')') {
                  //cout<<"321"<<endl;
                  int t;
                  Pop(s2, t);
                  w = getchar();
              } else if (prio(e, w) == '>') {
                  int a, b, c = 0, d;
                  Pop(s1, a);
                  Pop(s1, b);
                  Pop(s2, d);
                  if (d == '+')
                      c = a + b;
                  else if (d == '-')
                      c = b - a;
                  else if (d == '/')
                      c = b / a;
                  else if (d == '*')
                      c = b * a;
                  Push(s1, c);
              }
          }
            GetTop(s2,e);
        }
        int r;
        Pop(s1,r);
        cout<<r<<endl;
    return 0;
}

**汉诺塔问题**

#include<iostream>
#include<algorithm>using namespace std;void move(int n,char a,char b){cout<<a<<"->"<<n<<"->"<<b<<endl;
}void hnt(int n,char a,char c,char b){if(n==1){move(n,a,b);}else{hnt(n-1,a,b,c);move(n,a,b);hnt(n-1,c,a,b);}
}int main(){int n;cin>>n;char a,b,c;cin>>a;getchar();cin>>b;getchar();cin>>c;getchar();hnt(n,a,c,b);return 0;
} 

队列的应用——银行客户平均等待时间 

#include<stdio.h>

int main(){
    int n;
    scanf("%d",&n);
    double a,b,time=0,ans=0;
    scanf("%lf%lf",&a,&b);
    time=a+b;
    for(int i=1;i<n;++i){
        scanf("%lf%lf",&a,&b);
        if(a>=time){
            time=a+b;
        }else{
            ans+=time-a;
            time+=b;
        }
        
    }
    printf("%.2lf",ans/n);
    return 0;
}


阿克曼(Ackmann)函数 

#include<iostream>
#include<algorithm>using namespace std;int akm(int m,int n){if(m==0){return n+1;}else if(m>0&&n==0){return akm(m-1,1);}else if(m>0&&n>0){return akm(m-1,akm(m,n-1));}
}int main(){int n,m;cin>>m>>n;cout<<akm(m,n);return 0;
} 


计算next值

#include "stdio.h"
#include "stdlib.h"
#include <iostream>
#define  MAXSTRLEN  255                   // 用户可在255以内定义最大串长
typedef unsigned char SString[MAXSTRLEN+1];	// 0号单元存放串的长度void get_next(SString T,int next[]){
// 算法4.7
// 求模式串T的next函数值并存入数组next// 请补全代码int i=1,j=0;next[1]=0;while(i<T[0]){if(j==0||T[i]==T[j]){next[++i]=++j;}else{j=next[j];}} }
int main(){
int next[MAXSTRLEN];
SString S;
int n,i,j;
char ch;
scanf("%d",&n);    // 指定要验证NEXT值的字符串个数
ch=getchar();
for(i=1;i<=n;i++)    
{
ch=getchar();
for(j=1;j<=MAXSTRLEN&&(ch!='\n');j++)    // 录入字符串
{
S[j]=ch;
ch=getchar();
}
S[0]=j-1;    // S[0]用于存储字符串中字符个数
get_next(S,next);
printf("NEXT J is:");
for(j=1;j<=S[0];j++)
printf("%d",next[j]);
printf("\n");
}
return 0;
}


**KMP算法** 

#include "stdio.h"
#include "stdlib.h"
#include <iostream>
#define TRUE  1
#define FALSE  0
#define OK  1
#define ERROR  0
#define INFEASLBLE  -1
#define OVERFLOW  -2
#define MAXSTRLEN  255 	//用户可在255以内定义最大串长
typedef unsigned char SString[MAXSTRLEN+1];	//0号单元存放串的长度void get_next(SString T,int next[]){
// 算法4.7
// 求模式串T的next函数值并存入数组next// 请补全代码int i=1,j=0;next[1]=0;while(i<T[0]){if(j==0||T[i]==T[j]){next[++i]=++j;}else{j=next[j];}}}int Index_KMP(SString S,SString T,int pos){
// 算法4.6
// 利用模式串T的next函数求T在主串S中第pos个字符之后的位置
// KMP算法。请补全代码int next[MAXSTRLEN+1];get_next(T,next);int i=pos,j=1;while(i<=S[0]&&j<=T[0]){if(j==0||S[i]==T[j]){++i,++j;}else{j=next[j];}}if(j>T[0]){return i-T[0];}else{return 0;}}
int main()
{
SString T,S;int i,j,n;char ch;int pos;scanf("%d",&n);    // 指定n对需进行模式匹配的字符串
ch=getchar();
for(j=1;j<=n;j++)
{
ch=getchar();for( i=1;i<=MAXSTRLEN&&(ch!='\n');i++)    // 录入主串{
S[i]=ch;ch=getchar();
}
S[0]=i-1;    // S[0]用于存储主串中字符个数
ch=getchar();
for( i=1;i<=MAXSTRLEN&&(ch!='\n');i++)    // 录入模式串
{T[i]=ch;ch=getchar();
}
T[0]=i-1;    // T[0]用于存储模式串中字符个数
pos=Index_KMP(S,T,1)                 ;    // 请填空
printf("%d\n",pos);
}
return 0;}


稀疏矩阵的运算 (选做) 

#include<iostream>
#include<algorithm>

using namespace std;
struct node{
    int x,y,v;
}a[10005];

bool cmp(node a,node b){
    if(a.y==b.y){
        return a.x<b.x;
    }else{
        return a.y<b.y;
    }
}

int main(){
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=k;++i){
        cin>>a[i].x>>a[i].y>>a[i].v;
    }
    sort(a+1,a+k+1,cmp);
    for(int i=1;i<=k;++i){
        cout<<a[i].y<<' '<<a[i].x<<' '<<a[i].v<<endl;
    }
    return 0;
}


不完整的排序 

#include<iostream>
#include<algorithm>using namespace std;
const int N=100005;int a[N];int main(){int t,n;cin>>t;while(t--){int i,j;cin>>n;for(i=1;i<=n;++i){cin>>a[i];}i=1,j=n;while(i<j){while(a[i]<0&&i<j){++i;}while(a[j]>0&&i<j){--j;}if(i<j){swap(a[i],a[j]);}}for(i=1;i<=n;++i){cout<<a[i]<<' ';}cout<<endl;}return 0;
}

二叉树的构建及遍历操作 

#include "stdio.h"
#include "malloc.h"
#define TRUE 1
#define FALSE 0
#define OK  1
#define ERROR  0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int  Status;typedef char  ElemType;
typedef struct BiTNode{ElemType data;struct BiTNode *lchild,*rchild;//左右孩子指针
} BiTNode,*BiTree;Status CreateBiTree(BiTree &T) {  // 算法6.4// 按先序次序输入二叉树中结点的值(一个字符),’#’字符表示空树,// 构造二叉链表表示的二叉树T。char ch;scanf("%c",&ch);if (ch=='#') T = NULL;else {if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) return ERROR;T->data=ch; // 生成根结点CreateBiTree(T->lchild);   // 构造左子树CreateBiTree(T->rchild);  // 构造右子树}return OK;
} // CreateBiTreeStatus PreOrderTraverse( BiTree T) {// 前序遍历二叉树T的递归算法//补全代码,可用多个语句if(!T){return OK;}else{printf("%c",T->data);PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}
} // PreOrderTraverseStatus InOrderTraverse( BiTree T) {// 中序遍历二叉树T的递归算法//补全代码,可用多个语句if(!T){return OK;}else{InOrderTraverse(T->lchild);printf("%c",T->data);InOrderTraverse(T->rchild);}} // InOrderTraverseStatus PostOrderTraverse( BiTree T) {// 后序遍历二叉树T的递归算法//补全代码,可用多个语句if(!T){return OK;}else{PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);printf("%c",T->data);}
} // PostOrderTraverseint main()   //主函数
{BiTree T;CreateBiTree(T);PreOrderTraverse(T);printf("\n");InOrderTraverse(T);printf("\n");PostOrderTraverse(T);return 0;                  //补充代码}

求二叉树各种节点数

#include "stdio.h"
#include "malloc.h"
#define TRUE 1
#define FALSE 0
#define OK  1
#define ERROR  0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int  Status;typedef char  ElemType;
int a,b,c;
typedef struct BiTNode{ElemType data;struct BiTNode *lchild,*rchild;//左右孩子指针
} BiTNode,*BiTree;Status CreateBiTree(BiTree &T) {  // 算法6.4// 按先序次序输入二叉树中结点的值(一个字符),’#’字符表示空树,// 构造二叉链表表示的二叉树T。char ch;scanf("%c",&ch);if (ch=='#') T = NULL;else {if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) return ERROR;T->data=ch; // 生成根结点CreateBiTree(T->lchild);   // 构造左子树CreateBiTree(T->rchild);  // 构造右子树}return OK;
} // CreateBiTreevoid f(BiTree &T){if(!T){return;}else{if(T->lchild&&T->rchild){a+=1;}else if(!T->lchild&&!T->rchild){c+=1;}else{b+=1;}f(T->lchild);f(T->rchild);}
}int main()   //主函数
{BiTree T;CreateBiTree(T);                  //补充代码f(T);printf("%d\n%d\n%d",a,b,c);}

二叉树的宽度 

#include<iostream>
#include<queue>
#include<algorithm>using namespace std;
typedef pair<int,int> PII;PII a[55];
int main() {int n,x,y,ans=0;cin>>n;for(int i=1; i<=n-1; ++i) {cin>>x>>y;if(!a[x].first) {a[x].first=y;} else {a[x].second=y;}}queue<int>q;q.push(1);while(!q.empty()) {int len=q.size();ans=max(ans,len);for(int i=1; i<=len; ++i) {int t=q.front();q.pop();if(a[t].first) {q.push(a[t].first);}if(a[t].second) {q.push(a[t].second);}}}cout<<ans;return 0;
}


二叉树的遍历运算     

#include<iostream>
#include<string>
#include<algorithm>using namespace std;string s1,s2;void solve(int l1,int r1,int l2,int r2){char c=s1[l1];int i;if(l1>r1||l2>r2){return;}for(i=l2;i<=r2;++i){if(s2[i]==c){break;}}solve(l1+1,l1+i-l2,l2,i-1);solve(l1+i-l2+1,r1,i+1,r2);cout<<c;
}int main() {cin>>s1>>s2;int l1=s1.size(),l2=s2.size();solve(0,l1-1,0,l2-1);return 0;
}


**二叉树的直径**

#include<iostream>
#include<algorithm>using namespace std;
typedef pair<int,int> PII;PII a[55];
int ans;
int dfs(int n){if(!n){return 0;}else{int l=dfs(a[n].first),r=dfs(a[n].second);int len=max(l,r)+1;ans=max(ans,l+r);return len;}
}int main(){int n;cin>>n;for(int i=1;i<=n-1;++i){int x,y;cin>>x>>y;if(!a[x].first){a[x].first=y;}else{a[x].second=y;}}dfs(1);cout<<ans;return 0;
} 

哈夫曼树 

#include "stdio.h"
#include "string.h"
#include <iostream>
using namespace std;
typedef struct
{
    unsigned int weight;
    unsigned int parent,lchild,rchild;
} HTNode,*HuffmanTree;
typedef char **HuffmanCode;
void   select(HuffmanTree &HT, int n, int &s1, int &s2)
{
    int minn=1;
    for(int i=1;i<=n;++i){
        if(HT[i].parent==0){
            minn=i;
            break;
        }
    }
    for(int i=minn;i<=n;++i){
        if(HT[i].parent==0&&HT[i].weight<HT[minn].weight){
            minn=i;
        }
    }
    s1=minn;
    minn=1;
    for(int i=1;i<=n;++i){
        if(HT[i].parent==0&&s1!=i){
            minn=i;
            break;
        }
    }
    for(int i=minn;i<=n;++i){
        if(HT[i].parent==0&&HT[i].weight<HT[minn].weight&&i!=s1){
            minn=i;
        }
    }
    s2=minn;
}
void createHuffmanTree(HuffmanTree &HT, int n)
{ //构造哈夫曼树HT
    int i, m, s1, s2;
    if (n<=1) return;
    m = 2 * n - 1;
    HT = new HTNode[m+1];  // 0号单元未用
    for (i=1; i<=m; i++) { //初始化HT数组
        HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;
    }
    for (i=1; i<=n; i++)
        cin>>HT[i].weight;
    for (i=n+1; i<=m; i++)    // 建哈夫曼树
    { 
         select(HT,i-1,s1,s2);
         HT[i].lchild=s1;
         HT[i].rchild=s2;
         HT[s1].parent=i;
         HT[s2].parent=i;
         HT[i].weight=HT[s1].weight+HT[s2].weight;
    }
}
void createHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n)
{//--- 从叶子到根逆向求每个字符的哈夫曼编码 ---
    char *cd = new char[n];    // 分配求编码的工作空间
    cd[n-1] = '\0';  // 编码结束符。
    int i,c,f,start;
    for (i=1; i<=n; ++i)
    {
        start = n-1;
        c=i, f=HT[i].parent;
        while(f)// 从叶子到根逆向求编码
        {
            --start;
            if (HT[f].lchild==c) cd[start] = '0';
            else cd[start] = '1';
            c=f,f=HT[f].parent;
        }
        HC[i] = new char[n-start];// 为第i个字符编码分配空间
        strcpy(HC[i], &cd[start]);    // 从cd复制编码(串)到HC
    }
}
int main()
{
    int i,n;
    int *w;
    HuffmanTree HT;
    HuffmanCode HC;
    scanf("%d",&n);  //权值个数
    HC=new char*[n+1]; //0空间未用
    createHuffmanTree(HT,n);
    createHuffmanCode(HT,HC,n);
    for (i = 1; i<=n; i++)
        printf("%s\n",HC[i]);  //输出哈夫曼编码
}

顺序查找 

#include<iostream>
#include<algorithm>using namespace std;int a[55];int main(){int n,x,i;cin>>n;for(i=1;i<=n;++i){cin>>a[i];}cin>>x;for(i=1;i<=n;++i){if(x==a[i]){cout<<"The element position is "<<i<<".";break;}}if(i>n){cout<<"The element is not exist.";}return 0;
} 

二分查找 

#include<iostream>
#include<algorithm>using namespace std;int a[55];int main(){int n,x,i;cin>>n;for(i=0;i<n;++i){cin>>a[i];}cin>>x;int k=lower_bound(a,a+n,x)-a;if(k!=n){cout<<"The element position is "<<k<<".";}else{cout<<"The element is not exist.";}return 0;
} 
#include<iostream>
#include<algorithm>using namespace std;int a[55];int main(){int n,x,i,k;cin>>n;k=n;for(i=0;i<n;++i){cin>>a[i];}cin>>x;int l=0,r=n-1;while(l<=r){int mid=l+r>>1;if(a[mid]>x){r=mid-1;}else if(a[mid]<x){l=mid+1;}else{k=mid;break;}}if(k!=n){cout<<"The element position is "<<k<<".";}else{cout<<"The element is not exist.";}return 0;
} 


哈希查找 

记得注掉TraverseHash里面的一句printf

#include"malloc.h" /* malloc()等 */
#include"stdlib.h" /* exit() */
#include"stdio.h"
#define EQ(a,b) ((a)==(b))
#define SUCCESS 1
#define UNSUCCESS 0
#define NULLKEY -1 /*哈希表无元素时值为-1*/
typedef int ElemType;
int length;
typedef struct
{ElemType *elem; /* 数据元素存储基址,动态分配数组 */int count; /* 当前数据元素个数 */
}HashTable;void InitHashTable(HashTable *H){ /* 操作结果: 构造一个长度为length的哈希表,length为全局变量 */int i;(*H).count=0; /* 当前元素个数为0 */(*H).elem=(ElemType*)malloc(length*sizeof(ElemType));if(!(*H).elem)exit(0); /* 存储分配失败 */for(i=0;i<length;i++)(*H).elem[i]=NULLKEY; /* 未填记录的标志 */
}
unsigned Hash(ElemType K)
{ /* 一个简单的哈希函数*/return 3*K%length; }
void collision(int *p) /*线性探测再散列 */
{ /* 开放定址法处理冲突 */*p=(*p+1)%length;}
int SearchHash(HashTable H,ElemType K,int *p,int *c)
{  /* 在开放定址哈希表H中查找关键码为K的元素,若查找成功,以p指示待查数据 *//* 元素在表中位置,并返回SUCCESS;否则,以p指示插入位置,并返回UNSUCCESS *//* c用以计冲突次数,其初值置零,供建表插入时参考。算法9.17 */*p=Hash(K); /* 求得哈希地址 */while(H.elem[*p]!=NULLKEY&&!EQ(K,H.elem[*p])){ /* 该位置中填有记录,并且关键字不相等 */(*c)++;if(*c<length)collision(p); /* 求得下一探查地址p */elsebreak;}if EQ(K,H.elem[*p])return SUCCESS; /* 查找成功,p返回待查数据元素位置 */elsereturn UNSUCCESS; /* 查找不成功(H.elem[p].key==NULLKEY),p返回的是插入位置 */
}
int InsertHash(HashTable *H,ElemType e)
{ /* 查找不成功时插入数据元素e到开放定址哈希表H中,并返回查找长度 */int c,p;c=0;if(SearchHash(*H,e,&p,&c))   /* 表中已有与e有相同关键字的元素 */printf("哈希表中已有元素%d。\n",e);else{ /* 插入e */  (*H).elem[p]=e; ++(*H).count;}return c+1; /*查找长度为冲突次数加1*/
}
void TraverseHash(HashTable H){ /* 按哈希地址的顺序打印哈希表,无元素位置用X表示 */int i;//printf("HashTable Address:0~%d\n",length-1);for(i=0;i<length;i++)if(H.elem[i]==NULLKEY) /* 有数据 */printf("X ");elseprintf("%d ",H.elem[i]); printf("\n");
}
main()
{float i=0,j=0;ElemType e;HashTable H;//printf("Input Table length:");scanf("%d",&length);InitHashTable(&H);//printf("Input key words sequence, -1 conclusion input:");scanf("%d",&e);while(e!=-1){j ++;  /*j记录输入元素个数*/i = i + InsertHash(&H,e);  /*i记录查找长度的和*/ scanf("%d",&e);		                       }TraverseHash(H);	printf("Average search length=%f\n",i/j);
}


直接插入排序 

#include<iostream>
#include<algorithm>using namespace std;
int a[55];
int main(){int n,i,j,k;cin>>n;for(int i=1;i<=n;++i){cin>>a[i];}for(i=2;i<=n;++i){a[0]=a[i];for(j=i-1;a[j]>a[0];--j){a[j+1]=a[j];}a[j+1]=a[0];for(k=1;k<=n;++k){cout<<a[k]<<' ';}cout<<endl;}return 0;
}


折半插入排序 

#include<iostream>
#include<algorithm>
using namespace std;
int a[100];
int n;void insertSort(){for(int i=2;i<=n;++i){if(a[i]<a[i-1]){a[0]=a[i];int l=1,r=i-1,ans=r;while(l<=r){int mid=(l+r)/2;if(a[0]<a[mid]){ans=mid;r=mid-1;}else{l=mid+1;}}for(int k=i-1;k>=ans;--k){a[k+1]=a[k];}a[ans]=a[0];}for(int k=1;k<=n;++k){cout<<a[k]<<' ';}cout<<endl;}
}int main(){cin>>n;for(int i=1;i<=n;++i){cin>>a[i];}insertSort();return 0;
} 
#include<iostream>
#include<algorithm>using namespace std;
int a[55];
int main(){int i,j,k,n;cin>>n;for(i=1;i<=n;++i){cin>>a[i];}for(i=2;i<=n;++i){a[0]=a[i];for(j=i-1;a[j]>a[0];--j){a[j+1]=a[j];}a[j+1]=a[0];for(k=1;k<=n;++k){cout<<a[k]<<' ';}cout<<endl;}return 0;
}

希尔(shell)排序 

#include<iostream>
#include<algorithm>using namespace std;
int a[55];
int main(){int i,j,k,n,d;cin>>n;for(i=1;i<=n;++i){cin>>a[i];}d=n/2;while(d){for(i=1;i+d<=n;++i){a[0]=a[i+d];for(j=i;j>=1&&a[j]>a[0];j-=d){a[j+d]=a[j];}a[j+d]=a[0];}for(i=1;i<=n;++i){cout<<a[i]<<' ';}cout<<endl;d/=2;}return 0;
}

**冒泡排序**

1.要求当一趟冒泡过程中不再有数据交换,则排序结束

2.不再交换的那组排序也要输出

#include<iostream>
#include<algorithm>using namespace std;
int a[55];
int main(){int i,j,k,n,d;cin>>n;for(i=1;i<=n;++i){cin>>a[i];}for(i=1;i<=n-1;++i){int flag=0;for(j=1;j<=n-i;++j){if(a[j]>a[j+1]){flag=1;swap(a[j],a[j+1]);}}for(j=1;j<=n;++j){cout<<a[j]<<' ';}cout<<endl;if(!flag){break;}} return 0;
}

快速排序 


#include <iostream>

using namespace std;
int a[100],n;

void qsort(int l,int r){
    if(l>=r){
        return;
    }
    a[0]=a[l];
    int i=l,j=r;
    while(i<j){
        while(i<j&&a[j]>=a[0]){
            --j;
        }
        a[i]=a[j];
        while(i<j&&a[i]<=a[0]){
            ++i;
        }
        a[j]=a[i];
    }
    a[i]=a[0];
    for(int k=1;k<=n;++k){
        cout<<a[k]<<' ';
    }
    cout<<endl;
    qsort(l,i-1);
    qsort(i+1,r);
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>a[i];
    }
    qsort(1,n);
    return 0;
}

简单选择排序 

#include<iostream>
#include<algorithm>using namespace std;
int a[55];
int main(){int i,j,k,n,d;cin>>n;for(i=1;i<=n;++i){cin>>a[i];}for(i=1;i<=n-1;++i){int minn=i;for(j=i+1;j<=n;++j){if(a[j]<a[minn]){minn=j;}}swap(a[i],a[minn]);for(j=1;j<=n;++j){cout<<a[j]<<' ';}cout<<endl;} return 0;
}

堆排序

#include<iostream>
#include<algorithm>

using namespace std;

int n,a[100];
void HeadAdjust(int start,int end){
    for(int i=2*start+1;i<=end;i=i*2+1){
        if(i<end&&a[i]<a[i+1]){
            i++;
        }
        if(a[i]>a[start]){
            swap(a[i],a[start]);
            start=i;
        }else{
            break;
        }
        
    }
    
}
void HeapSort(){
    for(int i=(n-2)/2;i>=0;--i){
        HeadAdjust(i,n-1);
    }
    for(int i=0;i<n-1;++i){
        for(int i=0;i<n;++i){
            cout<<a[i]<<' ';
        }
        swap(a[0],a[n-1-i]);
        
        cout<<endl;
        HeadAdjust(0,n-2-i);
    }
    
}
int main(){
    cin>>n;
    for(int i=0;i<n;++i){
        cin>>a[i];
    }
    HeapSort();
    for(int i=0;i<n;++i){
            cout<<a[i]<<' ';
        }
    return 0;
}


归并排序(非递归算法)

#include<iostream>
#include<string>
#include<algorithm>

using namespace std;
const int N=100;
int n; 
int a[N],tmp[N];

void merg(int arr[],int i,int step,int j,int brr[]){
    int cnt=i,last_i,last_j;
    last_i=min(i+step,n+1);
    last_j=min(j+step,n+1);
    while(i<last_i&&j<last_j){
        if(arr[i]<=arr[j]){
            brr[cnt++]=arr[i++];
        }else{
            brr[cnt++]=arr[j++];
        }
    }
    while(i<last_i){
        brr[cnt++]=arr[i++];
    }
    while(j<last_j){
        brr[cnt++]=arr[j++];
    }
}

void mergesort(){
    int i,j,step,k;
    for(step=1,k=0;step<n;k++,step=step*2){
        for(i=1,j=i+step;j<=n;i=j+step,j=i+step){
            if(k%2==0){
                merg(a,i,step,j,tmp);
            }else{
                merg(tmp,i,step,j,a);
            }
        }
        while(i<=n){
        if(k%2==0){
            tmp[i]=a[i];
            i++;
        }else{
            a[i]=tmp[i];
            i++;
        }
    }
    if(k%2==0){
        for(int i=1;i<=n;++i){
            cout<<tmp[i]<<' ';
        }
        cout<<endl;
    }else{
        for(int i=1;i<=n;++i){
            cout<<a[i]<<' ';
        }
        cout<<endl;
    }
    }
    
}
int main(){
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>a[i];
    }
    mergesort();
    return 0;
}


基数排序

#include<iostream>
#include<string>
#include<cstdio>

using namespace std;
const int N=100;
int n; 
int a[N],tmp[N],bucket[10];
int maxBit(){
    int ans=a[1];
    for(int i=2;i<=n;++i){
        if(a[i]>ans){
            ans=a[i];
        }
    }
    int cnt=1;
    while(ans>=10){
        ans/=10;
        cnt++;
    }
    return cnt;
}

void radixsort(){
    int radix=1;
    int cnt=maxBit();
    for(int i=0;i<cnt;++i){
        for(int j=0;j<10;++j){
            bucket[j]=0;
        }
        for(int j=1;j<=n;++j){
            int k=(a[j]/radix)%10;
            bucket[k]++;
        }
//        for(int i=0;i<10;++i){
//            cout<<bucket[i]<<' '; 
//        }
//        cout<<endl;
        for(int j=1;j<10;++j){
            bucket[j]+=bucket[j-1];
        }
        for(int j=n;j>=1;--j){
            int k=(a[j]/radix)%10;
            tmp[bucket[k]--]=a[j];
        }
        for(int j=1;j<=n;++j){
            a[j]=tmp[j];
            printf("%03d ",a[j]);
        }
        printf("\n");
        radix*=10;
    }
}

int main(){
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>a[i];
    }
    radixsort();
    return 0;
}

实现图的存储结构

#include <iostream>
#include <algorithm>
using namespace std;
int e[100][100];
int main()
{
    int n,m,a,b;
    cin>>n>>m;
    for(int i=0;i<m;++i){
        cin>>a>>b;
        e[a][b]=1;
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            cout<<e[i][j]<<' ';
        }
        cout<<endl;
    }
    return 0;

}

图的深度遍历

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
vector<int>e[30];
int v[30];
void dfs(int start){
    if(!e[start].size()){
        return;
    }else{
        for(int i=0;i<e[start].size();++i){
            if(!v[e[start][i]]){
                char c=e[start][i]+'a';
                cout<<c<<' ';
                v[e[start][i]]=1;
                dfs(e[start][i]);
            }
            
        }
    }
}

int main() {
    int a;
    cin>>a;
    int n,m;
    char ch,first;
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        cin>>ch;
    }
    for(int i=1;i<=m;++i){
        char c1,c2;
        cin>>c1>>c2;
        int x,y,w;
        x=c1-'a';
        y=c2-'a';
        if(i==1){
            first=c1;
        }
        if(a<=1){
            e[x].insert(e[x].begin(),y);
            if(a==1){
                cin>>w;
            }
        }else{
            e[x].insert(e[x].begin(),y);
            e[y].insert(e[y].begin(),x);
            if(a==3){
                cin>>w;
            }
        }
    }
    cout<<first<<' ';
    v[first-'a']=1;
    dfs(first-'a');
    return 0;
}

图的广度遍历

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>

using namespace std;
vector<int>e[30];
int v[30];

int main() {
    int a;
    cin>>a;
    int n,m;
    char ch,first;
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        cin>>ch;
    }
    for(int i=1;i<=m;++i){
        char c1,c2;
        cin>>c1>>c2;
        int x,y,w;
        x=c1-'a';
        y=c2-'a';
        if(i==1){
            first=c1;
        }
        if(a<=1){
            e[x].insert(e[x].begin(),y);
            if(a==1){
                cin>>w;
            }
        }else{
            e[x].insert(e[x].begin(),y);
            e[y].insert(e[y].begin(),x);
            if(a==3){
                cin>>w;
            }
        }
    }
    queue<int>q;
    q.push(first-'a');
    v[first-'a']=1;
    while(!q.empty()){
        int t=q.front();
        q.pop();
        char c;
        c=t+'a';
        cout<<c<<' ';
        for(int i=0;i<e[t].size();++i){
            if(!v[e[t][i]])
                q.push(e[t][i]);
                v[e[t][i]]=1;
        }
    }
    return 0;
}

最小生成树

#include<iostream>
#include<algorithm>

using namespace std;

typedef long long ll;
const int N=2023,INF=1e18;
ll n,m,a,b,w;
ll e[N][N],d[N],v[N];

ll prim(){
    d[1]=0;
    ll sum=0;
    for(int i=1;i<=n;++i){
        int cur=-1;
        for(int j=1;j<=n;++j){
            if(!v[j]&&(cur==-1||d[j]<d[cur])){
                cur=j;
            }
        }
        
        if(d[cur]>=INF){
            return INF;
        }
        sum+=d[cur];
        v[cur]=1;
        for(int k=1;k<=n;++k){
            if(!v[k])
                d[k]=min(d[k],e[cur][k]);
        }
    }
    return sum;
}

int main() {
    
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            e[i][j]=INF;
        }
    }
    for(int i=1;i<=n;++i){
        d[i]=INF;
    }
    for(int i=1;i<=m;++i){
        cin>>a>>b>>w;
        e[a][b]=min(e[a][b],w);
        e[b][a]=min(e[b][a],w);
    }
    cout<<prim();
    return 0;
}

最短路问题


#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=300,INF=0x3f3f3f3f;
int e[N][N],d[N],v[N];
int n,m,a,b,x;

int dijkstra(){
    d[1]=0;
    for(int i=1;i<=n;++i){
        int cur=-1;
        for(int j=1;j<=n;++j){
            if(!v[j]&&(cur==-1||d[j]<d[cur])){
                cur=j;
            }
        }
        if(d[cur]>=INF){
            return -1;
        }
        v[cur]=1;
        for(int k=1;k<=n;++k){
            if(!v[k]){
                d[k]=min(d[k],d[cur]+e[cur][k]);
            }
        }    
    }
    return d[n];
}
int main() {
    
    cin>>n>>m;
    memset(d,0x3f,sizeof(d));
    memset(e,0x3f,sizeof(e));
    for(int i=1;i<=m;++i){
        cin>>a>>b>>x;
        e[a][b]=min(e[a][b],x);
        e[b][a]=min(e[b][a],x);
    }
    cout<<dijkstra();
    return 0;
}

拓扑排序

#include<iostream>
#include<queue>
#include<algorithm>

using namespace std;
int e[40][40],d[40];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        int x,y;
        cin>>x>>y;
        e[x][y]=1;
        d[y]++;
    }
    priority_queue<int,vector<int>,greater<int> >q;
    for(int i=1;i<=n;++i){
        if(d[i]==0){
            q.push(i);
        }
    }
    while(!q.empty()){
        int t=q.top();
        q.pop();
        cout<<t<<' ';
        for(int i=1;i<=n;++i){
            if(e[t][i]==1){
                d[i]--;
                if(d[i]==0){
                    q.push(i);
                }
            }
        }
    }
    return 0;
}

关键路径

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
int n,m;  //顶点数   边数 
int indegree[30];   //入度数 
int topo[30];    //拓扑序列 
int arcs[30][30];    //矩阵存图   值为权值 
int ve[30];        //事件vi最早发生时间 
int vL[30];        // 事件vi最迟发生时间 
const int MAX=0x3f3f3f3f;

int CP(int cnt)    //关键路径 
{
    if(cnt<n) return -1;    //存在有向环 返回-1 
    
    memset(ve,0,sizeof(ve));    //ve,vL初始化 
    memset(vL,0,sizeof(vL));
    
    for(int i=1;i<=n;i++)
    {    //按拓扑次序求每个事件的最早发生时间 
        int k=topo[i];
        for(int j=1;j<=n;j++)     //依次更新k所有邻接顶点的ve 
        {    
            if(arcs[k][j]!=MAX&&ve[j]<ve[k]+arcs[k][j])    //更新j的ve
            ve[j]=ve[k]+arcs[k][j];
        }
    }
    
    for(int i=1;i<=n;i++)     //给每个事件的最迟发生时间vL设置初值vL[n] 
    vL[i]=ve[n];
    
    for(int i=n;i>=1;i--)        
    {        //按逆拓扑次序求每个事件的最迟发生时间vL 
        int k=topo[i];
        for(int j=1;j<=n;j++)
        {
            if(arcs[k][j]!=MAX&&vL[k]>vL[j]-arcs[k][j])
            vL[k]=vL[j]-arcs[k][j];
        }
    }
    
    int ans=0;        //路径总长度 
    
    for(int i=1;i<=n;i++)     //判断每一次是否为关键路径 
    {
        for(int j=1;j<=n;j++)
        {
            int e=ve[i];
            if(arcs[i][j]!=MAX)
            {
                int L=vL[j]-arcs[i][j];
                if(e==L)   //如果活动<vi,vj>的最早开始时间和最迟开始时间相等,则为关键路径 
                ans+=arcs[i][j];
            }
        }
    }
    return ans;
}

int main()
{
    /****************拓扑排序************************/ 
    int e,s,w,cnt=0;
    priority_queue<int,vector<int>,greater<int> > q;  //优先队列 
    
    memset(indegree,0,sizeof(indegree));//初始化 
    memset(arcs,0x3f,sizeof(arcs));
    
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>s>>e>>w;
        indegree[e]++;
        arcs[s][e]=w;//s---->e    e依赖于s 
    }
    
    for(int i=1;i<=n;i++)
    if(!indegree[i]) q.push(i);     //入度为0的进队 
    
    while(!q.empty())
    {
        int t=q.top();  //取队首元素 
        q.pop();
        topo[++cnt]=t;    //t存进topo序列 
        for(int i=1;i<=n;i++)
        if(arcs[t][i]!=MAX) //t---->i   i依赖于t 
        {
            indegree[i]--;    //出度-1 
            if(!indegree[i])    //出度为0的入队 
            q.push(i);
        }
    }
    /*************************************************/ 
    
    int ans=CP(cnt);
    cout<<ans<<endl;
    return 0;
}
 


http://www.ppmy.cn/news/279636.html

相关文章

ansible使用剧本操作硬盘

在一个节点添加一块20G的硬盘 通过ansible剧本判断是否存在第二块硬盘&#xff0c;且硬盘的大小大于10G 满足条件&#xff1a; 在此硬盘创建一个分区&#xff0c;大小为10G 使用此分区创建一个卷组 从此卷组中创建一个逻辑卷 将此逻辑卷格式化为xfs 将此逻辑卷挂载至/mountdir目…

7.7 空间曲线及其方程

&#x1f64c;作者简介&#xff1a;数学与计算机科学学院出身、在职高校高等数学专任教师&#xff0c;分享学习经验、生活、 努力成为像代码一样有逻辑的人&#xff01; &#x1f319;个人主页&#xff1a;阿芒的主页 ⭐ 高等数学专栏介绍&#xff1a;本专栏系统地梳理高等数学…

处理器CPU天梯图,显卡天梯图(性能排名图)

自己网上找的几个图&#xff0c;仅供参考&#xff0c;买电脑可以看看了~ 转载于:https://www.cnblogs.com/little-white/p/3324393.html

CPU天梯图/显卡天梯图---kalrry

CPU天梯图/显卡天梯图---kalrry 一、CPU天梯图二、显卡天梯图 一、CPU天梯图 CPU天梯图更注重综合性能&#xff0c;只具有参考意义 二、显卡天梯图 以下显卡天梯图主要是根据传统光栅性能排名

2020cpu天梯图

2020年最新CPU天梯图 桌面CPU的型号还是有很多的&#xff0c;不过一般情况下只有最近的两代有选购的价值&#xff0c;更老的型号因为停产太久&#xff0c;不推荐新手玩家入手&#xff0c;而如果是老手的话&#xff0c;应该也不需要看这篇CPU天梯图文章解析了。 本人的显卡就是活…

CPU显卡性能对比、天梯图

CPU性能比较 Intel AMD CPU排行榜 英特尔 至强 CPU系列对比 显卡性能对比 2012年 显卡、CPU对比 ---------------------------------------------------------------------------------------- 2012年7月15日最新笔记本电脑处理器_CPU_性能排行榜.doc.zip 下载 2011年12月笔…

CPU天梯图2022

组装电脑怎么搭配更好这些点很重要 http://www.adiannao.cn/du 2022CPU选购指南&#xff1a; 500元以下价位&#xff1a; 推荐型号&#xff1a;Intel 酷睿i3 4170&#xff0c;AMD Ryzen 5 1400&#xff08;这个价位就不考虑游戏了&#xff0c;一般只适合家用和办公&#xff0…

电脑硬件天梯图—CPU、显卡、主板

看到许多玩家对电脑的配置一点都不懂&#xff0c;这里特地制作了最新的硬件天梯图--CPU&#xff0c;显卡&#xff0c;主板&#xff0c;让大家对电脑硬件孰优孰劣有个一目了然的了解。 看不清楚的情点击小图看大图。 首先是CPU天梯图&#xff1a; 其次是显卡天梯图&#xff1a; …