//归并排序递归方法实现
#include <iostream>
#include <cstdio>
using namespace std;
#define maxn 1000005
int a[maxn], temp[maxn];
long long ans;
void MergeSort(int a[], int l, int mid, int r)
{
int k=;
int i = l, n = mid, j = mid, m = r;
while ( i<n && j<m )
{
if (a[i] <= a[j])
{
temp[k++] = a[i++];
}
else
{
ans += n-i;
temp[k++] = a[j++];
}
}
while (i<n)
temp[k++] = a[i++];
while (j<m)
temp[k++] = a[j++];
for (int t = ; t<k; ++t)
a[l+t] = temp[t];
}
void Sort(int a[], int l, int r)
{
if (r-l<=)
return ;
int mid = (l+r)>>;
Sort(a, l, mid);
Sort(a, mid, r);
MergeSort(a, l, mid, r);
}
//快速排序
1 #include<iostream>
#include<cstdio>
#define MAXSIZE 100
using namespace std;
int partition(int a[],int low,int high)
{
int i,j;
int x;
x=a[low];
i=low;
j=high;
while(i<j)
{
while(i<j&&a[j]>=x) j--;
if(i<j) a[i++]=a[j];
while(i<j&&a[i]<=x) i++;
if(i<j) a[j--]=a[i];
}
a[i]=x;
return i;
}
void quicksort(int r[],int low ,int high)
{ int mid;
if(low<high)
{ mid = partition(r,low,high);
quicksort(r,low,mid-);
quicksort(r,mid+,high);
}
}
int main()
{ int R[MAXSIZE]={,,,,,,,,};
int len =;
quicksort(R,,len-);
for(int i=;i<len-;i++)
{ cout<<R[i]<<" ";
}
}
//最小生成树prim算法
#include<iostream>
#include<cstdio>
#define MAXSIZE 101
#define MAX 9999
using namespace std;
struct Graph{
int data[MAXSIZE][MAXSIZE];
int vexnum,arcnum;
};
int prim3(Graph G)
{
int min,i,j,pos;
int visited[MAXSIZE];
int low[MAXSIZE];
int result;
pos=;
visited[]=;
for(i=;i<=G.vexnum;i++)
{
visited[i]=;
if(i!=pos)
low[i]=G.data[pos][i];
}
for(i=;i<=G.vexnum;i++)
{
int min=MAX;
for(j=;j<=G.vexnum;j++)
{
if(visited[j]==&&min>low[j])
{
min=low[j];
pos=j;
}
}
result+=min;
visited[pos]=;
for(j=;j<=G.vexnum;j++)
{
if(visited[j]==&&low[j]>G.data[pos][j])
{
low[j]=G.data[pos][j];
}
}
}
return result;
}
1 ///链队列
struct LQueue
{
int data;
LQueue *next; }; struct Queue
{
LQueue *front,*rear;///队头队尾不存元素
};
int EnQueue(Queue *qu,int x)
{
LQueue *p;
p = (LQueue *)malloc(sizeof(LQueue));
if(!p) return ERROR;
else
{
p->data=x;
qu->rear->next = p;
qu->rear=p;
return OK;
} }
int OutQueue(Queue *qu)
{
LQueue *p;
if(qu->front==qu->rear)
{
return ERROR;
}
else
{
p=qu->front->next;
qu->front->next=p->next;
if(p->next==NULL)
{
qu->front=qu->rear;
}
free(p);
return OK;
}
}
//图的建立和遍历
#include<iostream>
#include<cstdio>
#include<cstdlib>
#define MAXSIZE 1000
#define MAX 100
#include<queue>
using namespace std;
bool visit[MAXSIZE]; struct AdjLink
{
int data;
AdjLink *next;
};
struct Graph
{
int vexNum,arcNum;
AdjLink *Head[MAXSIZE];
int kind; };
void DFS(Graph G,int i);
int FirstAdjLink(Graph G,int i);
int NextAdjLink(Graph G,int i,int w);
void BFSTraverse(Graph G);
void CreatGraph(Graph &G)
{
int Start,End;
AdjLink *p;
for(int i=;i<=G.vexNum;i++) G.Head[i]=NULL;
for(int i=;i<=G.arcNum;i++)
{
cout<<"请输入起点和终点："<<endl;
cin>>Start>>End; p=(AdjLink*)malloc(sizeof(AdjLink));
p->next=G.Head[Start];
p->data=End;
G.Head[Start]=p; }
}
void DFSTraverse(Graph G)
{
for(int i=;i<=G.vexNum;i++) visit[i]=false;
for(int i=;i<=G.vexNum;i++)
if(!visit[i]) DFS(G,i);
cout<<"\b\b \n";
}
void DFS(Graph G,int i)
{
int w;
visit[i]=true;
cout<<i<<"->";
for(w=FirstAdjLink(G,i);w;w=NextAdjLink(G,i,w))
if(!visit[w])
DFS(G,w); }
int FirstAdjLink(Graph G,int i)
{
if(!G.Head[i]) return ;
else
{
return G.Head[i]->data;
}
}
int NextAdjLink(Graph G,int i,int w)
{
AdjLink *p;
p=G.Head[i];
while(p->data!=w) p=p->next;
if(p->next==NULL) return ;
else return p->next->data;
}
int main()
{
Graph G;
cout<<"请输入结点数和边数:"<<endl;
cin>>G.vexNum>>G.arcNum;
CreatGraph(G);
DFSTraverse(G);
BFSTraverse(G);
}
void BFSTraverse(Graph G)
{
queue<int> q;
for(int i=;i<=G.vexNum;i++) visit[i]=false;
for(int i=;i<=G.vexNum;i++)
{
if(!visit[i])
{
visit[i]=true;
cout<<i<<"->";
q.push(i);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int w=FirstAdjLink(G,u);w;w=NextAdjLink(G,u,w))
{
if(!visit[w])
{
visit[w]=true;
cout<<w<<"->";
q.push(w);
}
}
}
} }
cout<<"\b\b \n";
}
//线性表
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cstdlib>
using namespace std;
///都用c语言写的
///建议从主函数开始看
int sequence_map[]; ///顺序表的数组
int total_sequence=,total_list=; ///定义两个全局变量用来计算顺序表与链表长度，初始值为0
struct List ///当对顺序表和链表操作时对于相应长度值进行改变
{
int num;
List *next;
}; ///定义结构体表示链表中的各个元素
List *head=NULL,*p=NULL,*list_temp=NULL,*pback=NULL,*insert_temp=NULL;
void init_print() ///一级菜单操作界面
{
printf("* *\n");
printf("* 请输入对应序号进行操作 *\n");
printf("* 1.顺序表操作 *\n");
printf("* 2.链表操作 *\n");
printf("* 3.退出 *\n");
printf("**********************************\n");
printf("请输入对应序号进行操作:");
}
void init_sequence() ///二级菜单中顺序表的操作界面
{
printf("* *\n");
printf("* 请输入对应序号进行操作 *\n");
printf("* 1.顺序表的建立 *\n");
printf("* 2.顺序表的插入 *\n");
printf("* 3.顺序表的输出 *\n");
printf("* 4.顺序表的删除 *\n");
printf("* 5.顺序表的长度 *\n");
printf("* 6.返回上一层 *\n");
printf("**********************************\n");
printf("请输入对应序号进行操作:");
}
void init_pointlist() ///二级菜单中链表的操作界面
{
printf("* *\n");
printf("* 请输入对应序号进行操作 *\n");
printf("* 1.链表的建立 *\n");
printf("* 2.链表的插入 *\n");
printf("* 3.链表的输出 *\n");
printf("* 4.链表的删除 *\n");
printf("* 5.链表的长度 *\n");
printf("* 6.返回上一层 *\n");
printf("**********************************\n");
printf("请输入对应序号进行操作:");
}
void establish_sequence() ///建立顺序表
{
system("cls");
memset(sequence_map,,sizeof(sequence_map)); ///初始化数组为0
printf("请输入顺序表数据组数：");
int group;
scanf("%d",&group); ///首先输入数据的组数
total_sequence=group;
printf("请分别输入%d组数据，用空格或回车隔开：\n",group);
for(int i=; i<group; i++) ///在输入数据的同时进行排序
{
int sequence_temp;
bool flag=false; ///bool变量用来记录数据是否被插入当前数组
scanf("%d",&sequence_temp);
for(int j=; j<i; j++) ///在已经输入的数据中循环找是否有比当前元素大的元素
{
if(sequence_temp<sequence_map[j]) ///如果存在比当前值更大的元素
{ ///使bool变量变成true，表示数据被插入数组
flag=true;
for(int k=i-; k>=j; k--) ///把当前顺序表中比这个元素大的元素都后移一位
sequence_map[k+]=sequence_map[k];
sequence_map[j]=sequence_temp; ///将这个元素插入顺序表
break;
}
}
if(!flag) ///如果循环没有找到比当前元素大的元素
sequence_map[i]=sequence_temp; ///说明当前元素为最大值，直接加到数组最后一位
}
printf("创建顺序表成功!");
system("pause");
system("cls");
init_sequence();
}
void insert_sequence() ///插入数据和建立顺序表原理相同
{ ///可以优化成同一个程序
system("cls");
printf("请输入要插入的数据：");
int insert_temp;
bool flag=false;
scanf("%d",&insert_temp);
for(int i=; i<total_sequence; i++)
{
if(insert_temp<sequence_map[i])
{
flag=true;
for(int k=total_sequence-; k>=i; k--)
sequence_map[k+]=sequence_map[k];
sequence_map[i]=insert_temp;
break;
}
}
if(!flag)
sequence_map[total_sequence]=insert_temp;
total_sequence++;
printf("顺序表插入成功!");
system("pause");
system("cls");
init_sequence();
}
void output_sequence() ///遍历数组，输出所有元素
{
system("cls");
printf("顺序表当前为：\n");
for(int i=; i<total_sequence; i++)
{
printf("%d",sequence_map[i]);
printf(i==total_sequence-?"\n":" ");
}
system("pause");
system("cls");
init_sequence();
}
void delete_sequence() ///删除数据和插入原理相似，需要注意如果存在相同元素需要全部删除
{
system("cls");
printf("请输入要删除的数据：");
int delete_temp;
bool flag=false; ///判断顺序表中是否有当前元素
while(~scanf("%d",&delete_temp))
{
for(int i=; i<total_sequence; i++)
{
if(delete_temp==sequence_map[i])
{
total_sequence--; ///如果遇到需要删除的元素，将线性表长度-1
flag=true; ///表示已经删除该元素
for(int k=i; k<=total_sequence-; k++) ///从这一位开始将后面所有比它大的元素都前移一位
sequence_map[k]=sequence_map[k+];
i--; ///重点：如果不将i-1，会导致删除完本元素后i向后前进一位
} ///数组元素整体向前前进一位，相当于i+=2，如果此时有相同
} ///需要删除的元素，会跳过这个元素，导致删除不成功，有兴趣
if(!flag) ///可以注释掉i--这一句测试一些数据
{
printf("当前顺序表中无此元素，请重新输入：");
continue; ///如果flag值没有发生变化说明顺序表中没有这个元素
}
else
{
printf("顺序表元素删除成功!");
system("pause");
system("cls");
init_sequence(); ///否则删除成功，重新回到上级菜单
break;
}
}
}
void length_sequence()
{
system("cls");
printf("当前顺序表长度为：");
printf("%d\n",total_sequence); ///由于用了全局变量统计了顺序表的长度，就不用遍历了
system("pause");
system("cls");
init_sequence();
}
void establish_pointlist() ///链表的建立
{
system("cls");
printf("请输入链表数据组数：");
int list_group;
scanf("%d",&list_group);
printf("请分别输入%d组数据，用空格或回车隔开：\n",list_group);
for(int i=; i<list_group; i++)
{
total_list++;
list_temp=new List; ///动态申请新的内存空间
scanf("%d",&list_temp->num);
list_temp->next=NULL;
if(i==) ///第一个插入的元素连接到头指针后
head=list_temp;
else ///其余元素找到其应在的位置后插入
{
p=head; ///首先让p指针指向头指针
while(p->next!=NULL&&list_temp->num > p->num) ///当p不为空并且输入的值大于p指向的元素的值时
{
pback=p; ///使pback=p，p指向下一个元素
p=p->next; ///pback永远都表示p当前元素的前一个元素
}
if(list_temp->num <= p->num) ///当输入的值小于等于p指向的值时
{
if(p==head) ///如果此时p为头指针，即当前值为链表中的最小值
head=list_temp; ///所以temp值应该插入链表头部
else pback->next=list_temp; ///否则将需要插入的元素的地址存在pback->next中
list_temp->next=p; ///将p指向的元素地址存在temp->next中
} ///实现了向有序链表中插入元素
else
{
p->next=list_temp; ///此时链表中没有比当前元素大的值，说明当前元素为最大值
list_temp->next=NULL; ///将其插入链表最后即可
}
}
}
printf("链表创建成功！");
system("pause");
system("cls");
init_pointlist();
}
void insert_pointlist() ///插入元素和创建链表过程一样
{
total_list++;
system("cls");
printf("请输入要插入的数据：");
p=NULL,pback=NULL;
insert_temp=new List;
scanf("%d",&insert_temp->num);
insert_temp->next=NULL;
p=head;
pback=head;
while(p->next!=NULL&&insert_temp->num > p->num)
{
pback=p;
p=p->next;
}
if(insert_temp->num <= p->num)
{
if(p==head)
head=insert_temp;
else pback->next=insert_temp;
insert_temp->next=p;
}
else
{
p->next=insert_temp;
insert_temp->next=NULL;
}
printf("链表插入成功！");
system("pause");
system("cls");
init_pointlist();
}
void output_pointlist()
{
system("cls");
printf("当前链表元素为：\n");
p=head;
while(p!=NULL) ///利用指针p输出链表中的各个元素
{
printf("%d ",p->num);
p=p->next;
}
printf("\n");
system("pause");
return;
}
void delete_pointlist() ///删除链表中的元素
{
system("cls");
if(head==NULL) ///如果头指针为空，说明链表未创建
{
printf("尚未创建链表！");
system("pause");
return;
}
printf("请输入要删除的数据：");
int delete_temp;
while(~scanf("%d",&delete_temp))
{
p=head;
pback=head;
while(p->next!=NULL&&delete_temp!=p->num) ///指针p和pback移动，使p指向需要删除的位置
{ ///pback指向p的前一元素
pback=p;
p=p->next;
}
if(delete_temp == p->num) ///如果此时p的值与需要删除的值相同
{
while(delete_temp==p->num) ///由于要删除全部相同元素，要用循环
{
total_list--; ///每删除一次使链表长度-1
if(p==head) ///如果当前p为头指针，说明需要删除的是最小元素
head=p->next; ///使头指针指向p的下一元素即可
else pback->next=p->next; ///否则说明删除元素在链表中，直接使下一元素和上一元素相连
List *p_temp=p; ///保存下此时需要删除的地址
delete p_temp; ///释放内存
p=p->next; ///p继续移动，找下一个需要删除的元素
}
printf("链表元素删除成功！");
system("pause");
system("cls");
init_pointlist();
break;
}
else
{
printf("当前链表中无此元素，请重新输入："); ///如果p->next指向NULL时仍没有元素可以删除
continue; ///说明此链表中无此元素
}
}
}
void length_pointlist() ///链表的长度，原理和线性表长度相同
{
system("cls");
printf("当前链表长度为：");
printf("%d\n",total_list);
system("pause");
system("cls");
init_sequence();
}
void sequence()
{
system("cls");
init_sequence();
int op_sequence; ///二级菜单中线性表的操作选项
while(~scanf("%d",&op_sequence))
{
if(op_sequence==)
establish_sequence();
else if(op_sequence==)
insert_sequence();
else if(op_sequence==)
output_sequence();
else if(op_sequence==)
delete_sequence();
else if(op_sequence==)
length_sequence();
else if(op_sequence==)
return;
else
{
printf("输入非法，请重新输入：");
continue;
}
}
}
void pointlist()
{
system("cls");
init_pointlist();
int op_pointlist; ///二级菜单中链表的操作选项
while(~scanf("%d",&op_pointlist))
{
if(op_pointlist==)
establish_pointlist();
else if(op_pointlist==)
insert_pointlist();
else if(op_pointlist==)
{
output_pointlist();
system("cls");
init_pointlist();
}
else if(op_pointlist==)
{
delete_pointlist();
system("cls");
init_pointlist();
}
else if(op_pointlist==)
length_pointlist();
else if(op_pointlist==)
return;
else
{
printf("输入非法，请重新输入：");
continue;
}
}
}
int main()
{
init_print(); ///初始化的菜单界面
int init_op; ///一级菜单的操作选项，1为顺序表，2为链表，3为退出
while(~scanf("%d",&init_op))
{
if(init_op==)
{
sequence(); ///当输入值为1时调用sequence函数进行顺序表操作
system("cls");
init_print();
}
else if(init_op==)
{
pointlist(); ///当输入值为2时调用pointlist函数进行链表操作
system("cls");
init_print();
}
else if(init_op==) ///当输入值为3时退出程序
exit();
else ///其余情况输入非法操作，继续重新输入
{
printf("输入非法，请重新输入：");
continue;
}
}
}
//栈 更改一下主函数就可用 lz这里是倒栈输出，便于观察进制的转换
#include<iostream>
#include<cstdio>
#include<malloc.h>
#define MAXSIZE 1000
#define NEW 10
using namespace std;
struct Stack
{
int *base;
int *top;
int length;
};
void InitStack(Stack &s)
{
s.base = (int *)malloc(NEW *sizeof(int));
if(!s.base)
{
cout<<"动态申请内存失败！！！"<<endl;
}
else
{
s.top = s.base;
s.length = NEW;
}
}
void Push(Stack &s,int e)
{
if(s.top-s.base>=s.length)
{
s.base=(int *)realloc(s.base,(s.length+NEW)*sizeof(int));
if(!s.base) cout<<"动态申请内存失败！！！"<<endl;
else
{
s.length+=NEW;
s.top = s.base+s.length;
}
} *s.top++=e;
}
void DisplayStack(Stack s)
{
int *p;
p = s.top-;
if(s.base ==s.top)
cout<<"当前栈为空栈！！！"<<endl;
else
{
cout<<"当前栈内元素为：";
while(p!=s.base-)
{
if(*(p)<)
{
cout<<*(p)<<" ";
p--;
}
else
{
cout<<char(*(p)+)<<" ";
p--;
}
}
cout<<endl;
}
}
int StackLength(Stack s)
{
int *p;
p=s.base;
int cont;
while(p!=s.top)
{
p++;
cont++;
}
return cont;
}
void pop(Stack &s)
{
if(s.top == s.base)
cout<<"当前已为空栈，操作失败！！！"<<endl;
else
{
*s.top--;
cout<<"操作成功！！！"<<endl;
}
}
void ClearStack(Stack &s)
{
s.top =s.base;
cout<<"栈已清空！！！"<<endl;
}
void StackEmpty(Stack s)///判空
{
if(s.top==s.base)
cout<<"栈为空！！！"<<endl;
else cout<<"栈不为空！！！"<<endl;
}
void DestroyStack(Stack &s)
{
s.base =NULL;
cout<<"栈已销毁！！！"<<endl;
}
void GetTop(Stack s,int &e)
{
if(s.top==s.base) cout<<"栈已为空，操作失败！！！"<<endl;
else
{
cout<<"栈顶元素为：";
e=*(s.top-);
cout<<e<<endl;
}
}
int main()
{
int x,r;
printf("请输入要转换的10进制数和要转的进制：\n");
while(cin>>x>>r)
{
Stack s;
InitStack(s);
while(x>)
{
Push(s,x%r);
x=x/r;
}
DisplayStack(s);
}
}
//串
#include<iostream>
#include<cstdio>
#include<string.h>
#include<malloc.h>
#include<cstdlib>
using namespace std;
#define MAXSIZE 100
#define FAlSE 0
#define OK 1
#define ERROR 0
#define OVERLOE -2
typedef int Status;
struct HString{
char *ch;
int length;
};
Status StrAssign(HString &H)
{
H.length = ;
H.ch = (char *)malloc((MAXSIZE)*sizeof(char));
printf("请输入字符串的长度\n");
int n;
scanf("%d",&n);
for(int i=;i<n;i++)
{
H.ch[i] = getchar();
H.length++;
if(getchar()=='\0')
break;
}
return OK;
}
Status PrintHString(HString H)
{
if(H.length == )
cout<<"空串\n";
else
{
for(int i=;i<H.length;i++)
{
cout<<H.ch[i]<<" ";
}
cout<<endl;
}
return OK;
}
Status HStringLength(HString H)
{
printf("输入的字符串的长度为：\n");
cout<<H.length<<endl;
return OK;
}
Status HStringCompare(HString H,HString T)
{
for(int i=;i<H.length&&i<T.length;i++)
{
if(T.ch[i]!= H.ch[i]) return T.ch[i]-H.ch[i];
else return T.length - H.length;
}
}
Status HStringConcat(HString &S,HString H,HString T)
{
if(!(S.ch = (char *)malloc((H.length+T.length)*sizeof(char))))
exit(OVERLOE);
for(int i=;i<H.length;i++)
S.ch[i] = H.ch[i];
S.length = T.length+H.length;
for(int i=H.length;i<S.length;i++)
{
S.ch[i] = T.ch[i-H.length];
}
return OK;
}
Status SubHString(HString &Sub,HString S,int pos ,int len)
{
if(pos<||len<||pos+len>S.length)
{
cout<<"输入长度有误！\n";
}
else
{
Sub.ch = (char *)malloc(len*sizeof(char));
for(int i= ;i< len;i++)
Sub.ch[i] = S.ch[pos + i-];
Sub.length = len;
}
return OK;
}
///串的模式匹配
int Index(HString S,HString T,int pos)
{
HString Sub;
int i=;
if(pos>)
{
int n = S.length;
int m = T.length;
i = pos;
while(i<=n-m+)
{
SubHString(Sub,S,i,m);
if(HStringCompare(Sub,T)!= )
i++;
else return i;
}
return ;
}
}
///串的替换
Status Replace(HString &S,HString T,HString V)
{
int i=;
if(T.length == )
return ERROR;
while(i)
{
i = Index(S,T,i);
if(i)
{
for(;i<T.length;i++)
{
S.ch[i] = V.ch[i];
}
i+= V.length;
}
}
return OK;
}
//二叉树
#include<iostream>
#include<cstdio>
#include<cstring>
#include<malloc.h>
#include<stdlib.h>
#include<conio.h>
#define MAXSIZE 201
using namespace std;
typedef struct BiTNode
{
char data;
struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;
int len,i=-;
char *p;
char ch[MAXSIZE];
int CreatBiTree(BiTree &T)
{
if(!(*p)||*p==' ')
{
T=NULL;
p++;
}
else
{
T = (BiTNode *)malloc(sizeof(BiTNode));
T->data =*(p++);
CreatBiTree(T->lchild);
CreatBiTree(T->rchild);
}
return ;
}
void Visit(char ch)
{
cout<<ch<<" ";
}
void PreOrderTraverse(BiTree T)///前序遍历
{
if(T)
{
Visit(T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
void InOrderTraverse(BiTree T)
{
if(T)
{
InOrderTraverse(T->lchild);
Visit(T->data);
InOrderTraverse(T->rchild);
}
}
void PostOrderTraverse(BiTree T)
{
if(T)
{
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
Visit(T->data);
}
}
void DestroyBiTree(BiTree T)
{
if(T)
{
if(T->lchild) DestroyBiTree(T->lchild);
if(T->rchild) DestroyBiTree(T->rchild);
free(T);
T=NULL;
}
}
int main()
{
int choice,flag=;
BiTree T;
printf("请输入要插入的字符串，空格表示字数为空:\n");
gets(ch);
p=ch;
CreatBiTree(T);
while(flag)
{
printf("请输入要操作程序的内容\n");
printf("1.递归先序遍历\n");
printf("2.递归中序遍历\n");
printf("3.递归后序遍历\n");
printf("4.退出\n");
scanf("%d",&choice);
if(choice == )
{
printf("先序遍历二叉树：\n");
PreOrderTraverse(T);
cout<<endl;
}
else if(choice == )
{
printf("中序遍历二叉树：\n");
InOrderTraverse(T);
cout<<endl;
}
else if(choice == )
{
printf("后序遍历二叉树\n");
PostOrderTraverse(T);
cout<<endl;
}
else
{
flag=;
printf("程序运行结束，按任意键退出！\n");
getch();
}
}
DestroyBiTree(T);
}