目录
顺序线性表的基本操作
合并顺序表
顺序表逆置
链式线性表的基本操作
合并链表
**反转链表 **
**顺序栈的基本操作**
栈的应用——进制转换
括号匹配检验
**汉诺塔问题**
计算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;
}
