注意：本页面中大部分代码都是用C++编写，在提交时尽量将所有的代码的提交方式都改为C++，否则提交时会报错。
6-1 顺序表的插入
void insert(int a[],int*n,int x)
{
int i,t;
for(i=*n-1;i>=0;i--)
{
if(x>=a[i])
{
a[i+1]=x;
break;
}
else
{
t=a[i];
a[i]=x;
a[i+1]=t;
}
}
(*n)++;}6-2 顺序表的删除
int del(int a[], int *n, int x) {
int i;
for (i = 0; i < *n; i++) {
if (a[i] == x) {
// 从当前位置开始，将后面的元素向前移动一位
for (; i < *n - 1; i++) {
a[i] = a[i + 1];
}
// 更新数组长度
(*n)--;
return 1; // 找到了并删除了元素，返回1
}
}
return 0; // 没有找到元素，返回0
}6-3 构造有序顺序表
void readArray(int a[], int n) {
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
}
// 函数用于对整数数组进行降序排序（冒泡排序）
void bubbleSortDescending(int a[], int n) {
int temp;
int swapped;
for (int i = 0; i < n - 1; i++) {
swapped = 0; // 标记这一轮是否有交换发生
for (int j = 0; j < n - i - 1; j++) { // 只需比较到未排序部分的最后一个元素
if (a[j] > a[j + 1]) {
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
swapped = 1; // 发生了交换
}
}
if (!swapped) {
break; // 如果没有交换发生，说明数组已经排序完成
}
}
}
// 主处理函数，现在只负责调用上面两个函数
void process(int a[], int n) {
readArray(a, n);
bubbleSortDescending(a, n);
// 这里可以添加代码以输出排序后的数组或其他后续处理
}6-4 快速求最大最小值（分治法）
int find_extreme(int *a, int m, int n, int (*compare)(int, int)) {
if (m == n) return a[m]; // 只有一个元素时直接返回
int mid = (m + n) / 2;
int left = find_extreme(a, m, mid, compare);
int right = find_extreme(a, mid + 1, n, compare);
return compare(left, right) ? right : left;
}
// 比较函数
int greater_than(int a, int b) {
return a > b;
}
int less_than(int a, int b) {
return a < b;
}
int max(int *a, int m, int n) {
return find_extreme(a, m, n, &less_than);
}
int min(int *a, int m, int n) {
return find_extreme(a, m, n, &greater_than);
}6-5 最大子段和（分治法）
int maxsubsum(int *a,int left,int right){
int sum=a[0],maxx=a[0];for(left=1;left<=right;left++){sum=sum>0?sum:0;sum+=a[left];maxx=maxx>sum?maxx:sum;}return maxx;
}6-6 棋盘覆盖问题（分治法）
void ChessBoard(int tr, int tc, int dr, int dc, int size){
int sxr,ssr;
if(size==1) return;//跳出循环
sxr=++num;
ssr=size/2;
if(dr<(tr+ssr)&&dc<(tc+ssr)){//在左上角
ChessBoard(tr,tc,dr,dc,ssr);
}
else{
board[tr+ssr-1][tc+ssr-1]=sxr;
ChessBoard(tr,tc,tr+ssr-1,tc+ssr-1,ssr);
}
if(dr<(tr+ssr)&&dc>=(tc+ssr)){//在右上角
ChessBoard(tr,tc+ssr,dr,dc,ssr);
}
else{
board[tr+ssr-1][tc+ssr]=sxr;
ChessBoard(tr,tc+ssr,tr+ssr-1,tc+ssr,ssr);
}
if(dr>=(tr+ssr)&&dc<(tc+ssr)){//在左下角
ChessBoard(tr+ssr,tc,dr,dc,ssr);
}
else{
board[tr+ssr][tc+ssr-1]=sxr;
ChessBoard(tr+ssr,tc,tr+ssr,tc+ssr-1,ssr);
}
if(dr>=(tr+ssr)&&dc>=(tc+ssr)){//在右下角
ChessBoard(tr+ssr,tc+ssr,dr,dc,ssr);
}
else{
board[tr+ssr][tc+ssr]=sxr;
ChessBoard(tr+ssr,tc+ssr,tr+ssr,tc+ssr,ssr);
}
}6-7 两位数合并
void swap(int a, int b, int *c) {
// 确保a和b都是两位数
if (a < 10 || a > 99 || b < 10 || b > 99) {
// 处理错误情况，例如设置c为某个特殊值或返回错误代码
*c = -1; // 示例：将c设置为-1表示错误
return;
}
// 提取a和b的十位数和个位数
int tensA = a / 10;
int onesA = a % 10;
int tensB = b / 10;
int onesB = b % 10;
// 重新组合数字并存储在c指向的位置
*c = 1000 * tensB + 100 * tensA + 10 * onesB + onesA;
}6-8 用指针操作数组输入输出元素(指针做形参）
void fun(int *b, int n) {
for (int i = 0; i < n; i++) {
int *temp = b + i; // 使用临时指针来指向当前要读取或打印的元素
scanf("%d", temp); // 读取输入到当前位置
if (i < n - 1) {
printf("%d ", *temp); // 如果不是最后一个元素，打印并加上空格
} else {
printf("%d", *temp); // 如果是最后一个元素，只打印元素值
}
}
}6-9 结构体指针形式输出
void output(RECORD *p, int n) {
while (n--) {
printf("%s,%d\n", p->no, p->score);
p--; // 移动到前一个元素
}
}6-10 操作指针串接两个结点
ptr Connect(int x1, int x2) {
// 分配第一个节点的内存
ptr first = (ptr)malloc(sizeof(snode));
if (first == NULL) {
// 处理内存分配失败的情况
return NULL;
}
// 为第一个节点赋值
first->data = x1;
// 分配第二个节点的内存并直接链接到第一个节点的next
first->next = (ptr)malloc(sizeof(snode));
if (first->next == NULL) {
// 如果第二个节点内存分配失败，释放第一个节点并返回NULL
free(first);
return NULL;
}
// 为第二个节点赋值
first->next->data = x2;
// 设置第二个节点的next为NULL，表示链表结束
first->next->next = NULL;
// 返回链表的头节点
return first;
}6-11 操作指针删除三个已串接结点中的第二个结点
ptr destroy(ptr p1) {
if (p1 != NULL && p1->next != NULL) {
ptr to_free = p1->next;
p1->next = to_free->next;
free(to_free);
}
return p1;
}6-12 表头插入法构造链表
ptr creat() {
ptr head = NULL, p, prev = NULL;
int x;
// 读取第一个数据项
scanf("%d", &x);
// 当用户输入非0值时，创建新节点并添加到链表中
while (x != 0) {
p = (ptr)malloc(sizeof(snode));
if (p == NULL) {
// 处理内存分配失败的情况
// ...
return NULL;
}
p->data = x;
p->next = head; // 新节点指向当前头节点
head = p; // 更新头节点为新节点
prev = p; // 更新prev为当前节点，以便在下次循环中处理
scanf("%d", &x); // 读取下一个数据项
}
return head;
}
void output(ptr p) {
while (p != NULL) {
printf("%d ", p->data);
p = p->next; // 移动到下一个节点
}
printf("\n"); // 输出换行符以改善可读性
}6-13 表尾插入法构造链表
ptr creat() {
int x;
ptr head = NULL, last = NULL;
// 读取第一个元素
scanf("%d", &x);
// 如果输入的是0，则直接返回空链表
if (x == 0) return head;
// 创建第一个节点
head = (ptr)malloc(sizeof(snode));
if (head == NULL) {
// 处理内存分配失败的情况
return NULL;
}
head->data = x;
head->next = NULL;
last = head; // last指向链表的最后一个节点
// 循环读取剩余元素，并创建新的节点
while (1) {
scanf("%d", &x);
if (x == 0) break; // 如果输入的是0，则结束循环
// 创建新节点
ptr p = (ptr)malloc(sizeof(snode));
if (p == NULL) {
// 处理内存分配失败的情况
// 释放已分配的节点内存（此处需要添加额外的逻辑来遍历链表并释放）
return NULL;
}
p->data = x;
p->next = NULL;
// 将新节点添加到链表的末尾
last->next = p;
last = p; // 更新last指针
}
return head;
}
void output(ptr p) {
while (p != NULL) {
printf("%d ", p->data);
p = p->next; // 移动到下一个节点
}
printf("\n"); // 输出换行符以改善可读性
}6-14 寻找链表元素的前驱结点
ptr pre(ptr h, int x) {
ptr current = h, prev = NULL;
// 遍历链表，直到找到值为x的节点或到达链表末尾
while (current != NULL && current->data != x) {
prev = current;
current = current->next;
}
// 如果找到了值为x的节点，则返回它的前一个节点；否则返回NULL
if (current != NULL && current->data == x) {
return prev;
}
return NULL;
}6-15 求链表的倒数第m个元素
ElementType Find(List L, int m) {
struct Node *current;
int count = 0;
// 第一次遍历，计算链表长度，同时检查是否小于m
current = L->Next;
while (current != NULL) {
count++;
if (count < m) {
current = current->Next;
} else {
break; // 如果链表长度大于或等于m，则退出循环
}
}
// 如果链表长度小于m，则返回错误
if (count < m) {
return ERROR;
}
// 第二次遍历，找到第m个节点的数据
current = L->Next;
for (int i = 0; i < m - 1; i++) { // 注意这里只需要遍历到第m-1个节点
current = current->Next;
}
// 返回第m个节点的数据
return current->Data;
}6-16 构造有序链表
ptr creat() {
ptr head = NULL; // 链表的头指针
ptr tail = NULL; // 链表的尾指针
ptr newNode; // 新节点的指针
int value;
// 循环读取用户输入，直到输入0
while (1) {
scanf("%d", &value);
if (value == 0) {
break;
}
// 创建新节点
newNode = (ptr)malloc(sizeof(snode));
newNode->data = value;
newNode->next = NULL;
// 插入新节点到有序链表中
if (head == NULL || value <= head->data) {
// 新节点成为新的头节点或插入到头部
newNode->next = head;
head = newNode;
if (tail == NULL) {
tail = newNode;
}
} else {
// 查找插入位置
ptr current = head;
while (current->next != NULL && current->next->data < value) {
current = current->next;
}
// 插入新节点
newNode->next = current->next;
current->next = newNode;
// 更新尾指针，如果必要
if (current == tail) {
tail = newNode;
}
}
}
return head;
}
// 输出链表元素
void output(ptr p) {
ptr current = p;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
} 6-17 加头链表的插入和删除
void ins(ptr h,int x){
ptr newNode,a,b;
newNode=(ptr)malloc(sizeof(snode));
newNode->data=x;
ptr sxr = h;
while (sxr->next != NULL && sxr->next->data < x) {
sxr = sxr->next;
}
// 插入新节点
newNode->next = sxr->next;
sxr->next = newNode;
return;
}
void del(ptr h, int x){
ptr sxr = h, prev = NULL;
while(sxr != NULL && sxr->data != x){
prev = sxr; // 保存当前节点的上一个节点
sxr = sxr->next;
}
if(sxr == NULL){
printf("no %d\n", x);
return;
}
if(prev == NULL){ // 如果要删除的节点是头节点
h = sxr->next;
} else {
prev->next = sxr->next; // 否则更新上一个节点的 next 指针
}
free(sxr); // 释放被删除节点的内存
return;
}6-18 循环单链表的追加
void AppendP(struct Node **rear,struct Node *p){
if((*rear)==NULL){
p->next=p;
(*rear)=p;
}
else{
p->next=(*rear)->next;
(*rear)->next=p;
(*rear)=p;
}
return;
}6-19 循环双链表插入操作
Status ListInsert_DuL(DuLinkList &L, int i, ElemType e){
DuLinkList sxr=L;
DuLinkList rxs;
rxs=(DuLinkList)malloc(sizeof(DuLNode));
rxs->data=e;
for(int j=0;j<i-1;j++){
sxr=sxr->next;
}
rxs->next=sxr->next;
sxr->next->prior=rxs;
sxr->next=rxs;
rxs->prior=sxr;
return 0;
}6-20 循环双链表删除操作
int ListDelete_DuL(DuLinkList &L, int i){
DuLinkList sxr=L,rxs,rsx;
for(int j=0;j<i-1;j++){
sxr=sxr->next;
}
rsx=sxr->next;
sxr->next=rsx->next;
rsx->prior=sxr;
free(rsx);
return 0;
}6-21 创建循环双链表
void CreateDuList(DuLinkList &L,int n){
L=(DuLinkList)malloc(sizeof(DuLNode));
L->prior=L;
L->next=L;
DuLinkList p,en=L;
for(int i=0;i<n;i++){
p=(DuLinkList)malloc(sizeof(DuLNode));
cin>>p->data;
p->prior=en;
p->next=L;
en->next=p;
en=en->next;
L->prior=en;
}
return;
}6-22 有序稀疏多项式求和
ptr add(ptr ha,ptr hb){
ptr h,h1=ha->next,h2=hb->next,p,end;
h=malloc(sizeof(node));
end=h;
while(h1!=NULL&&h2!=NULL){
p=malloc(sizeof(node));
if(h1->exp<h2->exp){
p->ceof=h1->ceof;
p->exp=h1->exp;
p->next=NULL;
h1=h1->next;
end->next=p;
end=p;
}
else if(h1->exp>h2->exp){
p->ceof=h2->ceof;
p->exp=h2->exp;
p->next=NULL;
h2=h2->next;
end->next=p;
end=p;
}
else{
if((h1->ceof+h2->ceof)!=0){
p->ceof=h1->ceof+h2->ceof;
p->exp=h1->exp;
p->next=NULL;
h1=h1->next;
h2=h2->next;
end->next=p;
end=p;
}
else{
h1=h1->next;
h2=h2->next;
}
}
}
while(h1!=NULL){
p=malloc(sizeof(node));
p->ceof=h1->ceof;
p->exp=h1->exp;
p->next=NULL;
h1=h1->next;
end->next=p;
end=p;
}
while(h2!=NULL){
p=malloc(sizeof(node));
p->ceof=h2->ceof;
p->exp=h2->exp;
p->next=NULL;
h2=h2->next;
end->next=p;
end=p;
}
return h;
}6-23 简单表达式求值
int cal( char a[] )
{
int i=0,x=0,z=0,s;
char sxr;
while(a[i]!='=')
{
while(a[i]>='0'&&a[i]<='9')
{
x=x*10+a[i]-'0';
i++;
}
sxr=a[i++];
while(a[i]>='0'&&a[i]<='9')
{
z=z*10+a[i]-'0';
i++;
}
}
switch(sxr)
{
case '+':s=x+z;break;
case '-':s=x-z;break;
case '*':s=x*z;break;
case '/':s=x/z;
}
return s;
}6-24 括号匹配判断
typedef struct {
char data[1000];
int top;
} Stack;
// 初始化栈
void initStack(Stack *s) {
s->top = -1;
}
// 判断栈是否为空
int isEmpty(Stack *s) {
return s->top == -1;
}
// 入栈
void push(Stack *s, char item) {
if (s->top < 999) {
s->data[++s->top] = item;
} else {
printf("Stack is full\n");
exit(1);
}
}
// 出栈
char pop(Stack *s) {
if (!isEmpty(s)) {
return s->data[s->top--];
} else {
printf("Stack is empty\n");
exit(1);
}
}
// 检查栈顶元素
char peek(Stack *s) {
if (!isEmpty(s)) {
return s->data[s->top];
} else {
printf("Stack is empty\n");
exit(1);
}
}
// 匹配函数
int match(char *exp) {
Stack s;
initStack(&s);
char *p = exp;
while (*p) {
switch (*p) {
case '(':
case '[':
case '{':
push(&s, *p);
break;
case ')':
if (!isEmpty(&s) && peek(&s) == '(') {
pop(&s);
} else {
return 0; // 不匹配
}
break;
case ']':
if (!isEmpty(&s) && peek(&s) == '[') {
pop(&s);
} else {
return 0; // 不匹配
}
break;
case '}':
if (!isEmpty(&s) && peek(&s) == '{') {
pop(&s);
} else {
return 0; // 不匹配
}
break;
default:
// 如果是其他字符，则继续检查下一个字符
break;
}
p++;
}
return isEmpty(&s); // 如果栈为空，说明所有括号都匹配，返回1；否则返回0
} 6-25 表达式求值-混合四则运算
int order(char a, char b)
{
int ar=0,br=0;
if(a=='*'||a=='/') ar=2;
else
if(a=='+'||a=='-') ar=1;
if(b=='*'||b=='/') br=2;
else
if(b=='+'||b=='-') br=1;
if(b=='=')br=-1;
if(ar>=br) return 1;
else return 0;
}
double calcu(double a, double b ,char c)
{
switch(c)
{
case '+':return a+b;
case '-':return a-b;
case '*':return a*b;
case '/':return a/b;
}
return 0;
}
void insta(char str[],double nust[],char opst[])
{
int m=0, n=0,i=0;
double tenu=0;
for(;str[i]!='\0';i++)
{
if(str[i]<='9'&&str[i]>='0')
tenu=tenu*10+str[i]-'0';
else
if(str[i]=='+'||str[i]=='-'||str[i]=='*'||str[i]=='/'||str[i]=='('||str[i]==')'||str[i]=='=')
{
nust[m++]=tenu;
tenu=0;
opst[n++]=str[i];
}
}
}
int cal(char str[])
{
double nust[20];
char opst[20];
insta(str,nust,opst);
while(opst[0]!='=')
{
int i=0;
if(order(opst[i],opst[i+1]))
{
double a=calcu(nust[i],nust[i+1],opst[i]);
nust[i]=a;
for(int w=i+1;nust[w]!=0;w++)
nust[w]=nust[w+1];
for(int w=i;opst[w]!='\0';w++)
opst[w]=opst[w+1];
}
else
{
i++;
double a=calcu(nust[i],nust[i+1],opst[i]);
nust[i]=a;
for(int w=i+1;nust[w]!=0;w++)
nust[w]=nust[w+1];
for(int w=i;opst[w]!='\0';w++)
opst[w]=opst[w+1];
}
}
return nust[0];
}
6-26 矩阵转稀疏矩阵
int create_mat(int (*d)[N],int m,int n,elem *a){
int i,j,k=0;
for(i=0;i<m;i++){
for(j=0;j<n;j++){
if(d[i][j]!=0){
a[k].row=i;
a[k].col=j;
a[k].val=d[i][j];
k++;
}
}
}
return k;
}
void show_mat(elem *a,int n){
int i;
for(i=0;i<n;i++){
printf("%d %d %d\n",a[i].row,a[i].col,a[i].val);
}
return;
}6-27 稀疏矩阵转置
void trans_mat(elem a[],int n,elem b[]){
int i,k=0;
for(i=0;i<n;i++){
b[k].row=a[i].col;
b[k].col=a[i].row;
b[k].val=a[i].val;
k++;
}
return;
}
void show_mat(elem a[],int n){
int i,j,sxr[6][6]={0};
for(i=0;i<n;i++){
sxr[a[i].row][a[i].col]=a[i].val;
}
for(i=0;i<N;i++){
for(j=0;j<N;j++){
if(sxr[i][j]!=0){
printf("%d %d %d\n",i,j,sxr[i][j]);
}
}
}
return;
}6-28 稀疏矩阵求和
int add_mat(elem a[],int t1,elem b[],int t2, elem c[]){
int i,j,k=0,sxr[M][N]={0},s;
for(i=0;i<t1;i++){
for(j=0;j<t2;j++){
if(a[i].row==b[j].row&&a[i].col==b[j].col&&(a[i].val+b[j].val)!=0){
sxr[a[i].row][a[i].col]=a[i].val+b[j].val;
}
}
}
for(i=0;i<t1;i++){
for(j=0;j<t2;j++){
if(a[i].row==b[j].row&&a[i].col==b[j].col){
j=999;
}
}
if(j==t2){
sxr[a[i].row][a[i].col]=a[i].val;
}
}
for(j=0;j<t2;j++){
for(i=0;i<t1;i++){
if(a[i].row==b[j].row&&a[i].col==b[j].col){
i=999;
}
}
if(i==t1){
sxr[b[j].row][b[j].col]=b[j].val;
}
}
for(i=0;i<M;i++){
for(j=0;j<N;j++){
if(sxr[i][j]!=0){
c[k].row=i;
c[k].col=j;
c[k].val=sxr[i][j];
k++;
}
}
}
return k;
}6-29 二叉树的遍历
Bptr creat(){
Bptr a,b,c;
a=(Bptr)malloc(sizeof(Bnode));
b=(Bptr)malloc(sizeof(Bnode));
c=(Bptr)malloc(sizeof(Bnode));
scanf("%d%d%d",&a->data,&b->data,&c->data);
a->Lson=b;
a->Rson=c;
b->Lson=NULL;
b->Rson=NULL;
c->Lson=NULL;
c->Rson=NULL;
return a;
}
void preorder(Bptr p){
printf("%d ",p->data);
printf("%d ",p->Lson->data);
printf("%d ",p->Rson->data);
return;
}
void inorder(Bptr p){
printf("%d ",p->Lson->data);
printf("%d ",p->data);
printf("%d ",p->Rson->data);
return;
}
void postorder(Bptr p){
printf("%d ",p->Lson->data);
printf("%d ",p->Rson->data);
printf("%d ",p->data);
return;
}6-30 计算二叉树的叶子数
int num(Bptr p) {
if (p == NULL) {
// 如果节点为空（到达叶子的下方），则返回0
return 0;
}
if (p->Lson == NULL && p->Rson == NULL) {
// 如果节点是叶子节点（没有左右子节点），则返回1
return 1;
}
// 否则，递归地计算左子树和右子树的叶子节点数，并返回它们的和
return num(p->Lson) + num(p->Rson);
}7-1 栈的基本操作
#include <stack>
#include <iostream>
using namespace std;
int main(){
int n,tem;
stack <int> sxr;
cin>>n;
for(int i=0;i<n;i++){
cin>>tem;
if(tem!=0){
if(sxr.size()==10) cout<<"FULL ";
else sxr.push(tem);
}
else{
if(!sxr.empty()){
cout<<sxr.top()<<" ";
sxr.pop();
}
else cout<<"EMPTY ";
}
}
cout<<endl;
while(!sxr.empty()){
cout<<sxr.top()<<" ";
sxr.pop();
}
}7-2 Windows消息队列
#include <bits/stdc++.h>
using namespace std;
struct Message {
string name;
int priority;
Message(const string& n, int p) : name(n), priority(p) {}
// 比较函数，用于优先队列的自定义排序
bool operator<(const Message& other) const {
// 注意这里的比较是反的，因为优先级值越小优先级越高
return priority > other.priority;
}
};
int main() {
int n;
cin >> n;
priority_queue<Message> msgQueue;
while (n--) {
string command;
cin >> command;
if (command == "PUT") {
string msgName;
int priority;
cin >> msgName >> priority;
msgQueue.push(Message(msgName, priority));
} else if (command == "GET") {
if (msgQueue.empty()) {
cout << "EMPTY QUEUE!" << endl;
} else {
Message msg = msgQueue.top();
msgQueue.pop();
cout << msg.name << endl;
}
}
}
return 0;
}7-3 求解右最值问题
#include <iostream>
using namespace std;
int main(void)
{
int n,i,j,a[20],b[20],count=0,flag=0;
cin >> n;
for(i=0;i<n;i++) cin >>a[i];
for(i=0;i<n;i++)
{
flag=0;
for(j=i+1;j<n;j++)
{
if(a[i]<a[j]) flag++;
}
if(flag==0)
{
b[count]=a[i];
count++;
}
}
for(i=0;i<count;i++) cout << b[i] << " ";
}7-4 队的基本操作
//注意：这里是采用循环队列完成，禁用一个空间的方法
//禁用一个空间
#include <queue>
#include <iostream>
using namespace std;
int main(){
int n,tem;
queue <int> sxr;
cin>>n;
for(int i=0;i<n;i++){
cin>>tem;
if(tem!=0){
if(sxr.size()==9) cout<<"FULL ";
else sxr.push(tem);
}
else{
if(!sxr.empty()){
cout<<sxr.front()<<" ";
sxr.pop();
}
else cout<<"EMPTY ";
}
}
cout<<endl;
while(!sxr.empty()){
cout<<sxr.front()<<" ";
sxr.pop();
}
}7-5 矩阵A乘以B
#include <bits/stdc++.h>
using namespace std;
int main(){
int ra,ca,rb,cb,sum=0;
int a[100][100];
int b[100][100];
cin>>ra>>ca;
for(int i=0;i<ra;i++){
for(int j=0;j<ca;j++){
cin>>a[i][j];
}
}
cin>>rb>>cb;
for(int i=0;i<rb;i++){
for(int j=0;j<cb;j++){
cin>>b[i][j];
}
}
if(ca!=rb) cout<<"Error: "<<ca<<" != "<<rb;
else{
cout<<ra<<" "<<cb<<endl;
for(int i=0;i<ra;i++){
for(int j=0;j<cb;j++){
sum=0;
for(int k=0;k<ca;k++){
sum+=a[i][k]*b[k][j];
}
cout<<sum;
if(j!=cb-1) cout<<" ";
}
cout<<endl;
}
}
}7-6 构造散列表
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,a[18]={0},data,h;
cin>>n;
for(int i=0;i<n;i++){
cin>>data;
h=data%17;
if(a[h]==0)
{
a[h]=data;
cout<<data<<" pos: "<<h<<endl;
}
else{
while(a[h]!=0){
h=(h+5)%18;
}
a[h]=data;
cout<<data<<" pos: "<<h<<endl;
}
}
}7-7 散列表查找
//本题的坑点：当想要查找0的时候，若设置的a[18]初始值为0，则此时会报找到了，这不符合我们想要的查找存不存在0
#include <bits/stdc++.h>
using namespace std;
int main() {
// 初始化散列表数组a，大小为18，所有元素初始化为0
int a[18];
memset(a,-1,sizeof(a));
int n, data, cou = 0;
// 第一个循环：接收数据并存储到散列表
cin >> n;
for (int i = 0; i < n; i++) {
cin >> data;
int h = data % 17; // 计算哈希值
int k = 0;
int hp = h; // 初始位置为哈希值对应的位置
// 查找第一个空位置存储数据
while (a[hp] != -1) {
k++;
hp = (h + k * k) % 18;
}
a[hp] = data; // 将数据存储到找到的位置
cout << hp << " "; // 输出存储位置
}
cout << endl; // 输出换行
// 第二个循环：接收数据并查找在散列表中的位置
cin >> n;
for (int i = 0; i < n; i++) {
cin >> data;
cou = 1; // 尝试次数初始化为1
int h = data % 17; // 计算哈希值
int k = 0;
int hp = h; // 初始位置为哈希值对应的位置
// 查找数据在散列表中的位置
while (a[hp] != data && a[hp] != -1) {
cou++; // 尝试次数加1
k++;
hp = (h + k * k) % 18; // 使用哈希函数计算下一个可能的位置
}
// 输出结果
if (a[hp] == data)
cout << data << " pos:" << hp << ",try " << cou << endl;
else
cout << data << " not found,try " << cou << endl;
}
return 0;
}7-8 后序和中序构造二叉树
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 使用后序和中序序列构建二叉树的递归函数
TreeNode* buildTree(int postorder[], int inorder[], int postStart, int postEnd, int inStart, int inEnd) {
if (postStart > postEnd) return nullptr;
// 后序序列的最后一个元素是根节点
TreeNode* root = new TreeNode(postorder[postEnd]);
int inRootIndex = -1;
// 在中序序列中找到根节点的索引
for (int i = inStart; i <= inEnd; ++i) {
if (inorder[i] == root->val) {
inRootIndex = i;
break;
}
}
// 递归构建左子树和右子树
root->left = buildTree(postorder, inorder, postStart, postStart + inRootIndex - inStart - 1, inStart, inRootIndex - 1);
root->right = buildTree(postorder, inorder, postStart + inRootIndex - inStart, postEnd - 1, inRootIndex + 1, inEnd);
return root;
}
// 先序遍历二叉树并打印
void preorderTraversal(TreeNode* root) {
if (!root) return;
cout << root->val << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
int main() {
int n;
cin >> n;
int postorder[10], inorder[10];
// 读取后序序列
for (int i = 0; i < n; ++i) cin >> postorder[i];
// 读取中序序列
for (int i = 0; i < n; ++i) cin >> inorder[i];
// 构建二叉树并遍历
TreeNode* root = buildTree(postorder, inorder, 0, n - 1, 0, n - 1);
preorderTraversal(root);
return 0;
}7-9 先序和后序构造正则二叉树
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 通过先序序列和后序序列构造正则二叉树
TreeNode* buildTree(vector<int>& preorder, vector<int>& postorder, int preStart, int preEnd, int postStart, int postEnd) {
if (preStart > preEnd || postStart > postEnd) {
return nullptr;
}
TreeNode* root = new TreeNode(preorder[preStart]);
if (preStart == preEnd) {
return root;
}
int leftRootValue = preorder[preStart + 1];
int leftRootIndexPost = postStart;
while (postorder[leftRootIndexPost] != leftRootValue) {
leftRootIndexPost++;
}
int leftSubtreeSize = leftRootIndexPost - postStart + 1;
root->left = buildTree(preorder, postorder, preStart + 1, preStart + leftSubtreeSize, postStart, leftRootIndexPost);
root->right = buildTree(preorder, postorder, preStart + leftSubtreeSize + 1, preEnd, leftRootIndexPost + 1, postEnd - 1);
return root;
}
// 中序遍历，获取中序序列
void inorderTraversal(TreeNode* root, vector<int>& inorder) {
if (root == nullptr) {
return;
}
inorderTraversal(root->left, inorder);
inorder.push_back(root->val);
inorderTraversal(root->right, inorder);
}
int main() {
int n;
cin >> n;
vector<int> preorder(n);
vector<int> postorder(n);
for (int i = 0; i < n; ++i) {
cin >> preorder[i];
}
for (int i = 0; i < n; ++i) {
cin >> postorder[i];
}
// 构造二叉树
TreeNode* root = buildTree(preorder, postorder, 0, n - 1, 0, n - 1);
// 中序遍历输出中序序列
vector<int> inorder;
inorderTraversal(root, inorder);
// 输出中序序列
for (int i = 0; i < n; ++i) {
cout << inorder[i];
if (i < n - 1) {
cout << " ";
} else {
cout << " " << endl;
}
}
return 0;
}7-10 构造二叉检索树
#include <iostream>
using namespace std;
struct node {
int val;
node *lson, *rson;
};
void app(node*& z, node* x) {
if (z == nullptr) {
z = x;
return;
}
if (x->val <= z->val) {
app(z->lson, x);
} else {
app(z->rson, x);
}
}
void out(node* l) {
if (l == nullptr) {
return;
}
cout << l->val << " ";
out(l->lson);
out(l->rson);
}
int main() {
int x;
node* root = nullptr;
while (cin >> x && x != 0) {
node* tem = new node{x, nullptr, nullptr};
app(root, tem);
}
out(root);
return 0;
}7-11 是否完全二叉搜索树
#include<stdio.h>
#include<stdlib.h>
typedef struct TNode* BinTree;
struct TNode{
int Data;
BinTree Left;
BinTree Right;
};
BinTree Insert( BinTree BST, int x )
{
if(!BST){
BST=(BinTree)malloc(sizeof(struct TNode));
BST->Data=x;
BST->Left=BST->Right=NULL;
}
else{
if(x>BST->Data) BST->Left=Insert( BST->Left, x );
else if(x<BST->Data) BST->Right=Insert( BST->Right, x );
}
return BST;
}
void Out(BinTree BST)
{
int i,front=0,tail=0,p=0;
BinTree a[30],x;
a[++tail]=BST;
while(tail!=front){
x=a[++front];
if(p==0) {
printf("%d",x->Data);
p=1;
}
else printf(" %d",x->Data);
if(x->Left) a[++tail]=x->Left;
if(x->Right) a[++tail]=x->Right;
}
}
void Pan(BinTree BST)
{
int i,front=0,tail=0,q=0;
BinTree a[30],x;
a[++tail]=BST;
while(tail!=front){
x=a[++front];
if(!x->Left&&x->Right){
printf("\nNO");
return;
}
if(x->Left&&x->Right){
a[++tail]=x->Left;
a[++tail]=x->Right;
}
if(!x->Right&&x->Left){
a[++tail]=x->Left;
q=1;
}
if(!x->Right&&!x->Left) q=1;
while(q==1&&tail!=front){
x=a[++front];
if(x->Left||x->Right){
printf("\nNO");
return;
}
}
}
printf("\nYES");
}
int main()
{
int n,i,x;
BinTree BST=NULL;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d",&x);
BST=Insert(BST, x);
}
Out(BST);
Pan(BST);
return 0;
}7-12 构造哈夫曼树-无序输入
#include <iostream>
#include <climits>
using namespace std;
struct node{
int data, parent, lson, rson;
}sxr[22];
int n;
void inorder_traversal(int index) {
if (index==-1){
return;
}
inorder_traversal(sxr[index].lson);
printf("%d ", sxr[index].data);
inorder_traversal(sxr[index].rson);
}
void select(node hf[], int k, int &t1, int &t2){
int min1 = INT_MAX, min2 = INT_MAX;
t1 = t2 = -1;
for(int i = 0; i < n + k; i++){
if(hf[i].parent == -1 && hf[i].data < min1){
min2 = min1;
t2 = t1;
min1 = hf[i].data;
t1 = i;
}
else if(hf[i].parent == -1 && hf[i].data < min2 && t1 != i){
min2 = hf[i].data;
t2 = i;
}
}
}
int main(){
int i, j,k;
cin >> n;
for(i = 0; i < n; i++){
cin >> sxr[i].data;
sxr[i].parent = sxr[i].lson = sxr[i].rson = -1;
}
for(k = 0; k < n-1; k++){
select(sxr, k, i, j);
if(i == -1 || j == -1) break;
sxr[n + k].data = sxr[i].data + sxr[j].data;
sxr[n + k].parent = -1;
sxr[n + k].lson = i;
sxr[n + k].rson = j;
sxr[i].parent = sxr[j].parent = n + k;
}
for(i=0;i<2*n-1;i++){
if(sxr[i].parent==-1){
inorder_traversal(i);
break;
}
}
return 0;
}
7-13 图的存储-邻接表
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,m,s,x,y;
cin>>n>>m>>s;
vector<int> v[n];
for(int i=0;i<m;i++){
cin>>x>>y;
v[x-1].push_back(y-1);
if(s==0){
v[y-1].push_back(x-1);
}
}
for(int i=0;i<n;i++){
cout<<i<<":";
for(int j=v[i].size()-1;j>=0;j--){
cout<<v[i][j]<<" ";
}
cout<<endl;
}
return 0;
}7-14 图的存储-邻接矩阵
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,m,s,sxr[52][52]={0},x,y;
cin>>n>>m>>s;
for(int i=0;i<m;i++){
cin>>x>>y;
sxr[x][y]=1;
}
if(s==0){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(sxr[i][j]!=0){
sxr[j][i]=sxr[i][j];
}
if(sxr[j][i]!=0){
sxr[i][j]=sxr[j][i];
}
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cout<<sxr[i][j]<<" ";
}
cout<<endl;
}
return 0;
}7-15 图的先广搜索
#include<stdio.h>
#include<malloc.h>
typedef struct edgenode{
int adjacent;
struct edgenode *next;
}edgenode,*eptr;
typedef struct{
int mark;
eptr firstedge;
}hnode;
void creatlist(hnode l[],int n,int m){
eptr p;
int v1,v2;
for (int i=0;i<n;i++){
l[i].mark=0;
l[i].firstedge=NULL;
}
for (int i=0;i<m;i++){
scanf("%d %d",&v1,&v2);
p=(eptr)malloc(sizeof(edgenode));
p->adjacent=v2-1;
p->next=l[v1-1].firstedge;
l[v1-1].firstedge=p;
p=(eptr)malloc(sizeof(edgenode));
p->adjacent=v1-1;
p->next=l[v2-1].firstedge;
l[v2-1].firstedge=p;
}
}
void bfs(hnode l[],int n,int v){
eptr p;
int u,w,first,last,q[n];
first=last=0;
for(u=0;u<n;u++)l[u].mark=0;
for (u=0;u<n;u++)
if (l[v].mark==0){
q[last++]=v;
l[v].mark=1;
while(first!=last){
v=q[first++];
printf("%d ",v+1);
p=l[v].firstedge;
while(p!=NULL){
w=p->adjacent;
if (l[w].mark==0){
q[last++]=w;
l[w].mark=1;
}
p=p->next;
}
}
}
}
int main(){
int n,m,s;
int num=0;
scanf("%d %d %d",&n,&m,&s);
hnode l[10];
creatlist(l,n,m);
bfs(l,n,s-1);
for (int i=0;i<n;i++){
if (l[i].mark==1){
num++;
}
}
if (num!=n){
printf("\n0");
}
return 0;
}
7-16 最小生成树-kruskal算法
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
struct Edge {
int u, v, cost;
bool operator<(const Edge& other) const {
return cost < other.cost;
}
};
int find(int x, vector<int>& parent) {
if (parent[x] != x) {
parent[x] = find(parent[x], parent);
}
return parent[x];
}
bool unionSet(int x, int y, vector<int>& parent, vector<int>& rank) {
int rootX = find(x, parent);
int rootY = find(y, parent);
if (rootX != rootY) {
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
return true;
}
return false;
}
int main() {
int N, M;
cin >> N >> M;
vector<Edge> edges;
for (int i = 0; i < M; ++i) {
int u, v, cost;
cin >> u >> v >> cost;
edges.push_back({u, v, cost});
}
sort(edges.begin(), edges.end());
vector<int> parent(N + 1);
vector<int> rank(N + 1, 0);
for (int i = 1; i <= N; ++i) {
parent[i] = i;
}
vector<Edge> mst;
for (const Edge& edge : edges) {
if (unionSet(edge.u, edge.v, parent, rank)) {
mst.push_back(edge);
}
}
for (const Edge& edge : mst) {
cout << min(edge.u, edge.v) << "," << max(edge.u, edge.v) << "," << edge.cost << endl;
}
return 0;
}7-17 最小生成树-Prim算法（从任意顶点开始）
#include<bits/stdc++.h>
using namespace std;
int inf=0x3f3f3f3f;
int graph[10000][10000]={0};
int lowcost[10000]={0};//点集
int tree[10000]={0};
int m,n,ls;
void prim(int s)
{
for(int i=1;i<=n;i++)
{
if(i==s)
lowcost[i]=0;
else
lowcost[i]=graph[s][i];
tree[i]=s;//初始化，所有的边都待选
}
int minn,pos;
for(int i=1;i<n;i++)//循环了n-1次，因为n个点，n-1个边
{
minn=inf;
for(int j=1;j<=n;j++)
{
if(lowcost[j]!=0&&lowcost[j]<minn)
{
minn=lowcost[j];
pos=j;
}//这个找的就是点集周围的最小边
}
cout<<(tree[pos]<pos?tree[pos]:pos)<<","<<(tree[pos]>pos?tree[pos]:pos)<<","<<graph[tree[pos]][pos]<<endl;//每找到一个边就输出一个边
if(minn==inf)
break;
lowcost[pos]=0;//加入！！
for(int j=1;j<=n;j++)
{
if(lowcost[j]!=0&&graph[pos][j]<lowcost[j])//因为没在点集里，s到j比较大，pos到j小，就更新一下
{
lowcost[j]=graph[pos][j];//其实就是点集到j最短的距离
tree[j]=pos;//加入到tree的待选，下次循环会选出来合适的，到时候这里的j会是合适的pos，这里的pos对应上一次合适的值。
}
}
}
}
int main()
{
cin>>n>>m>>ls;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
graph[i][j]=inf;
for(int i=0;i<m;i++)
{
int a,b;
cin>>a>>b;
cin>>graph[a][b];
graph[b][a]=graph[a][b];
}
prim(ls);
}7-18 最短路径-Dijkstra
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>
#define MAX_SIZE 10
#define INF 1000
void dijkstra(int graph[MAX_SIZE][MAX_SIZE], int start, int N) {
int distance[MAX_SIZE]; // 存储起始点到各个点的最短距离
bool visited[MAX_SIZE]; // 记录节点是否已访问
int i,j;
// 初始化距离和访问状态
for (i = 0; i < N; i++) {
distance[i] = INF;
visited[i] = false;
}
// 设置起始点的最短距离为0
distance[start] = 0;
// 依次找到距离最短的节点并更新其他节点的最短距离
for (i = 0; i < N; i++) {
int min_dis = INF;
int min_node = -1;
// 找到当前最小距离的节点
for (j = 0; j < N; j++) {
if (!visited[j] && distance[j] < min_dis) {
min_dis = distance[j];
min_node = j;
}
}
// 标记该节点已访问
visited[min_node] = true;
// 更新其他节点的最短距离
for (j = 0; j < N; j++) {
if (!visited[j] && graph[min_node][j] != INF && distance[j] > distance[min_node] + graph[min_node][j]) {
distance[j] = distance[min_node] + graph[min_node][j];
}
}
}
// 输出最短距离
for (i = 0; i < N; i++) {
if (distance[i] >=1000) {
printf("%d->%d:no path\n", start + 1, i + 1);
} else {
printf("%d->%d:%d\n", start + 1, i + 1, distance[i]);
}
}
}
int main() {
int N, M, directed;
int i,j,u, v, time, start;
// 读取输入
scanf("%d %d %d", &N, &M, &directed);
// 构建图的邻接矩阵
int graph[MAX_SIZE][MAX_SIZE];
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
graph[i][j] = INF;
}
}
for (i = 0; i < M; i++) {
scanf("%d %d %d", &u, &v, &time);
graph[u-1][v-1] = time;
if (!directed) {
graph[v-1][u-1] = time;
}
}
// 选择起始点
scanf("%d", &start);
start--;
// 调用Dijkstra算法计算最短距离
dijkstra(graph, start, N);
return 0;
}
7-19 求最短路径-flyod算法
#include <bits/stdc++.h>
using namespace std;
int graph[15][15];
int n,m,s,x,y;
void flyod(){
for(int k=0;k<n;k++){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(graph[i][k]+graph[k][j]<graph[i][j]){
graph[i][j]=graph[i][k]+graph[k][j];
}
}
}
}
return;
}
int main(){
int maxx,maxxnum;
memset(graph,999,sizeof(graph));
cin>>n>>m>>s;
for(int i=0;i<n;i++){
graph[i][i]=0;
}
for(int i=0;i<m;i++){
cin>>x>>y;
cin>>graph[x-1][y-1];
if(s==0){
graph[y-1][x-1]=graph[x-1][y-1];
}
}
flyod();
/*
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cout<<graph[i][j]<<" ";
}
cout<<endl;
}
*/
maxx=INT_MAX;
maxxnum=0;
for(int i=0;i<n;i++){
int smax=0;
for(int j=0;j<n;j++){
if(graph[i][j]>smax){
smax=graph[i][j];
}
}
if(smax<maxx){
maxx=smax;
maxxnum=i;
}
}
cout<<maxxnum+1;
return 0;
}7-20 有向图的拓扑序列
#include <bits/stdc++.h>
using namespace std;
#define MAX_LENGTH 1010
vector<int> G[MAX_LENGTH];
int n, m, inDegree[MAX_LENGTH];
stack<int> s;
bool TopologicalOrder() {
int num = 0;
for (int i = 1; i <= n; i++) {
if (inDegree[i] == 0) {
s.push(i);
}
}
while (s.size()) {
int u = s.top();
cout << u << " ";
s.pop();
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
inDegree[v]--;
if (inDegree[v] == 0) {
s.push(v);
}
}
num++;
}
if (num == n) return true;
else return false;
}
int main() {
int x, y;
cin >> n >> m;
memset(inDegree, 0, sizeof(inDegree));
for (int i = 1; i <= m; i++) {
cin >> x >> y;
inDegree[y]++;
if(!G[x].size()) G[x].push_back(y);
else{
G[x].insert(G[x].begin(), y);
}
}
if (!TopologicalOrder()) {
cout << endl;
cout << "0" << endl;
}
return 0;
}
7-21 冒泡排序
#include <iostream>
using namespace std;
int main(void)
{
int i,j,n,a[100],tem;
cin >> n;
for(i=0;i<n;i++) cin >> a[i];
for(i=0;i<3;i++)
{
for(j=n-1;j>i;j--)
{
if(a[j]<a[j-1])
{
tem=a[j];
a[j]=a[j-1];
a[j-1]=tem;
}
}
for(j=0;j<n;j++) cout << a[j] << " ";
cout << endl;
}
return 0;
}7-22 简单选择排序
#include <iostream>;
using namespace std;
int main(void)
{
int n,i,j,tem,a[100],max,maxj;
cin >> n;
for(i=0;i<n;i++) cin >> a[i];
for(i=0;i<3;i++)
{
max=a[0],maxj=0;
for(j=0;j<n-i;j++)
{
if(a[j]>max)
{
max=a[j];
maxj=j;
}
}
tem=a[n-i-1];
a[n-i-1]=a[maxj];
a[maxj]=tem;
for(j=0;j<n;j++) cout << a[j] <<" ";
cout << endl;
}
}7-23 直接插入排序
#include <iostream>
using namespace std;
int main(void)
{
int n,i,j,a[100],count,tem;
cin >> n;
for(i=0;i<n;i++) cin >> a[i];
for(i=0;i<3;i++)
{
for(j=0;j<i+1;j++)
{
if(a[i+1]<=a[j])
{
tem=a[i+1];
a[i+1]=a[j];
a[j]=tem;
}
}
for(j=0;j<n;j++) cout << a[j] <<" ";
cout << endl;
}
}7-24 递归二路归并排序
#include <iostream>
using namespace std;
int n,a[120],sxr=0;
void merage(int p,int q,int s,int t){
int i=p,j=s,k=p-1,b[n];
while((i<=q)&&(j<=t))
if(a[i]<=a[j])
b[++k]=a[i++];
else
b[++k]=a[j++];
while(i<=q)
b[++k]=a[i++];
while(j<=t)
b[++k]=a[j++];
for(i=p;i<=t;i++)
a[i]=b[i];
}
void merage_sort(int i,int j){
int k;
if(i<j){
k=(i+j)/2;
merage_sort(i,k);
merage_sort(k+1,j);
merage(i,k,k+1,j);
if(sxr<3){
for(int l=0;l<n;l++){
cout<<a[l]<<" ";
}
sxr++;
cout<<endl;
}
}
}
int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
}
merage_sort(0,n-1);
return 0;
}7-25 PAT排名汇总
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
struct node
{
string num;//不能用Longlong，longlong第一位为0会自动删除
int score;
int sumrank;
int rank;
int work;
}student[30005];//存学生信息
bool cmp(node* a,node* b)
{
if(a->score!=b->score)
return a->score>b->score;
return a->num<b->num;
}//比较函数，分数不等按学号排
int main()
{
int T,t,n,i,j,k,s=0;
vector<node*> q;//vector存指向结构体的指针
vector<node*>::iterator it;
cin>>T;
for(i=1;i<=T;i++)
{
q.clear();//清空，否则会在原基础上存数据
cin>>n;
while(n--)
{
cin>>student[s].num>>student[s].score;
student[s].work=i;
q.push_back(&student[s]);//压入结构体的指针
s++;//学生数量加1
}
sort(q.begin(),q.end(),cmp);
(*q.begin())->rank=1;//注意这地方的运用，(*q.begin())是指向结构体的指针，必须加括号，->的优先级大于*，*a.b等级于a->b
for(it=q.begin()+1,j=2;it!=q.end();it++,j++)
{
(*it)->rank=j;//(*it)是结构体的地址
if((*it)->score==(*(it-1))->score)(*it)->rank=(*(it-1))->rank;
}
}
q.clear();
for(i=0;i<s;i++)
q.push_back(&student[i]);
sort(q.begin(),q.end(),cmp);
(*q.begin())->sumrank=1;
for(it=q.begin()+1,j=2;it!=q.end();it++,j++)
{
(*it)->sumrank=j;
if((*it)->score==(*(it-1))->score) (*it)->sumrank=(*(it-1))->sumrank;
}
cout<<s<<endl;
for(i=0;i<s;i++)
cout<<q[i]->num<<" "<<q[i]->sumrank<<" "<<q[i]->work<<" "<<q[i]->rank<<endl;
}
7-26 奥运排行榜
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<string.h>
struct jp{
double jin;
double jiang;
double people;
double aver_jin;
double aver_jiang;
}a[300];
int main()
{
int N,M,i,j;
int b[500];//存储最后一行M个前来咨询的国家的编号
int p0,p1,p2,p3;
scanf("%d%d",&N,&M);
for(i=0;i<N;i++)
{
scanf("%lf%lf%lf",&a[i].jin,&a[i].jiang,&a[i].people);
a[i].aver_jin=a[i].jin/a[i].people;
a[i].aver_jiang=a[i].jiang/a[i].people;
}
for(i=0;i<M;i++)
scanf("%d",&b[i]);
for(i=0;i<M;i++)
{
p0=0;p1=0;p2=0;p3=0;
for(j=0;j<N;j++)
{
if(a[b[i]].jin>=a[j].jin) p0++;
if(a[b[i]].jiang>=a[j].jiang) p1++;
if(a[b[i]].aver_jin>=a[j].aver_jin) p2++;
if(a[b[i]].aver_jiang>=a[j].aver_jiang) p3++;
}
int max=p0,t=1;
//计算重要度排名为金牌，奖牌，人均金牌，人均奖牌
if(max<p1){max=p1;t=2;}
if(max<p2){max=p2;t=3;}
if(max<p3){max=p3;t=4;}
if(i==0)
printf("%d:%d",N-max+1,t);
else printf(" %d:%d",N-max+1,t);
//N-max+1为该国家所能拿到的最高名次的排序方式
//t为此方式能够获得的最高的排名
}
}
7-27 寻找大富翁
#include <bits/stdc++.h>
using namespace std;
bool cmp(int x,int y){
if(x>=y)
return 1;
return 0;
}
int main(){
int sxr[1000050],n,m;
cin>>n>>m;
for(int i=0;i<n;i++){
cin>>sxr[i];
}
sort(sxr,sxr+n,cmp);
if(n>=m){
cout<<sxr[0];
for(int i=1;i<m;i++){
cout<<" "<<sxr[i];
}
}
else{
cout<<sxr[0];
for(int i=1;i<n;i++){
cout<<" "<<sxr[i];
}
}
return 0;
}7-28 士兵排队
#include<cstdio>
#include<algorithm>//sort函数
#include<cstdlib> //abs函数
using namespace std;
int main()
{
int n;//士兵数
scanf("%d",&n);
int x[10000],y[10000];
//x数组存储士兵的横坐标，y数组存储士兵的纵坐标
int sum=0,rex,rey;
//sum记录步数之和，rex记录x方向的中位数，rey记录y方向的中位数
int i;
for(i=1;i<=n;i++)
scanf("%d%d",x+i,y+i);
//数据的输入到x[1]~x[n],y[1]~y[n],此处使用的是数组地址法
sort(x+1,x+n+1);
sort(y+1,y+n+1);
//对数据x[1]~x[n],y[1]~y[n]分别进行由小到大的排序
for(i=1;i<=n;i++)
x[i]=x[i]-i;
//构造x1-1，x2-2，......，xn-n数列
sort(x+1,x+n+1);
//对新数列进行排序
if(n%2==0)//n为偶数
{
rex = (x[n/2]+x[n/2+1])/2;
rey = (y[n/2]+y[n/2+1])/2;
}
else//n为奇数
{
rex = x[n/2+1];
rey = y[n/2+1];
}
//下面计算最小移动步数
for(i=1;i<=n;i++)
sum += abs(x[i]-rex)+abs(y[i]-rey);
printf("%d",sum);
//输出结果
return 0;
}