郑州轻工业大学2020年数据结构练习集

技术2022-07-14 82

郑州轻工业大学2020年数据结构练习集

按顺序：

函数题

1

List MakeEmpty() { List list; list = (List)malloc(sizeof(struct LNode)); list->Last = -1; return list; } Position Find( List L, ElementType X ) { int i; for(i = 0; i < MAXSIZE; i++) { if(L->Data[i] == X) return i; } return ERROR; } bool Insert( List L, ElementType X, Position P ) { int i; if(L->Last == MAXSIZE-1) { printf("FULL"); return false; } if(P < 0 || P > L->Last+1) { printf("ILLEGAL POSITION"); return false; } for(i = L->Last; i >= P; i--) { L->Data[i+1] = L->Data[i]; } L->Data[P] = X; L->Last++; return true; } bool Delete( List L, Position P ) { int i; if(P < 0 || P > L->Last) { printf("POSITION %d EMPTY", P); return false; } for(i = P; i < L->Last; i++) { L->Data[i] = L->Data[i+1]; } L->Last--; return true; }

2

List MakeEmpty() { List p; p=(Position)malloc(sizeof(struct LNode)); p->Data =0; p->Next =NULL; return p; } Position Find( List L, ElementType X ) { List p=L; while(p->Next) { if(p->Next->Data==X) { return p->Next; } p=p->Next ; } return ERROR; } bool Insert( List L, ElementType X, Position P ) { Position tmp,pre; pre=L; while(pre->Next!=NULL && pre->Next !=P) pre=pre->Next ; if(pre->Next==P) { tmp=(Position)malloc(sizeof(struct LNode)); tmp->Data=X; tmp->Next=pre->Next; pre->Next =tmp; return true; } else { printf("Wrong Position for Insertion\n"); return false; } } bool Delete( List L, Position P ) { Position tmp,pre; pre=L; while(pre->Next!=NULL &&pre->Next !=P) pre=pre->Next ; if(pre->Next==P) { tmp=pre->Next ; pre->Next =tmp->Next; free(tmp); return true; } else { printf("Wrong Position for Deletion\n"); return false;} }

3

void merge(int* a, int m, int* b, int n, int* c){ int a_index = 0, b_index = 0; int c_index = 0; while(a_index < m && b_index < n){ if(*(a + a_index) < *(b + b_index)){ *(c + c_index) = *(a + a_index); c_index++, a_index++; }else{ *(c + c_index) = *(b + b_index); c_index++, b_index++; } } while(a_index < m){ *(c + c_index) = *(a + a_index); c_index++, a_index++; } while(b_index < n){ *(c + c_index) = *(b + b_index); c_index++, b_index++; } }

4

List Delete( List L, ElementType minD, ElementType maxD ) { int i,sum=0; if(!L || minD >= maxD) return L; for(i=0;i<=L->Last;i++) { if(L->Data[i]>minD && L->Data[i]<maxD ) sum++; else L->Data[i-sum]=L->Data[i]; } L->Last-=sum; return L; }

5

List Insert( List L, ElementType X ) { List head = L;///头结点无信息 L = L->Next;///转到第一个结点 List p = (List)malloc(sizeof(struct Node)); p->Data = X; p->Next = NULL; List q = head;///初始为头结点 if(L == NULL)///空链表 { head->Next = p; return head; } while(L->Data < X) { q = L; L = L->Next; if(L->Next == NULL)///链表尾 { L->Next = p; return head; } } p->Next = L;//插在中间 q->Next = p; return head; }

6

List Merge( List L1, List L2 ) { List p1, p2, p3, L; L = (List)malloc(sizeof(struct Node)); p1 = L1->Next; p2 = L2->Next; p3 = L; while (p1 && p2){ if (p1->Data <= p2->Data){ p3->Next = p1; p3 = p1; p1 = p1->Next; } else { p3->Next = p2; p3 = p2; p2 = p2->Next; } } p3->Next = p1 ? p1 : p2; L1->Next = NULL; L2->Next = NULL; return L; }

7

ElementType Find( List L, int m ) { List p1,p2; p1=L->Next; p2=L->Next; int i=0; int flag=0; for(i=0;i<m;i++) { if(p2==NULL) { flag=1; break; } p2=p2->Next; } if(flag!=1) { while(p2) { p1 = p1->Next; p2 = p2->Next; } return p1->Data; } else return ERROR; }

8

bool Push( ElementType X, Deque D ) { if((D->Rear+1)%(D->MaxSize)==D->Front) return false; D->Front--; D->Front=(D->MaxSize+D->Front)%(D->MaxSize); D->Data[D->Front]=X; return true; } ElementType Pop( Deque D ) { if(D->Front==D->Rear) return ERROR; ElementType d=D->Data[D->Front]; D->Front++; D->Front=D->Front%(D->MaxSize); return d; } bool Inject( ElementType X, Deque D ) { if((D->Rear+1)%(D->MaxSize)==D->Front) return false; D->Data[D->Rear]=X; D->Rear=(D->Rear+1)%D->MaxSize; return true; } ElementType Eject( Deque D ) { if(D->Front==D->Rear) return ERROR; if(!D->Rear) D->Rear=D->MaxSize; D->Rear--; ElementType d=D->Data[D->Rear]; return d; }

9

int GetHeight(BinTree BT){ int cnt =0; if(BT){ int l,r; l=GetHeight(BT->Left); r=GetHeight(BT->Right); if(l>r)cnt=l+1;else cnt=r+1; } return cnt; }

10

void InorderTraversal( BinTree BT ) { if(BT){ InorderTraversal(BT->Left); printf(" %c",BT->Data); InorderTraversal(BT->Right); } } void PreorderTraversal( BinTree BT ) { if(BT) { printf(" %c",BT->Data); PreorderTraversal(BT->Left); PreorderTraversal(BT->Right); } } void PostorderTraversal( BinTree BT ) { if(BT) { PostorderTraversal(BT->Left); PostorderTraversal(BT->Right); printf(" %c",BT->Data); } } void LevelorderTraversal( BinTree BT ) { BinTree p; BinTree q[50]; int head=0;int tail=0; if(BT) { q[tail++]=BT; while(head!=tail) { p=q[head++]; printf(" %c",p->Data); if(p->Left!=NULL) { q[tail++]=p->Left; } if(p->Right!=NULL) { q[tail++]=p->Right; } } } }

11

void InorderTraversal( BinTree BT ){ Stack s=CreateStack(); if(BT!=NULL) Push(s,BT); BinTree now; while(!IsEmpty(s)){ while(Peek(s)->Left!=NULL) Push(s,Peek(s)->Left); while(!IsEmpty(s)){ now=Peek(s); printf(" %c",now->Data); Pop(s); if(now->Right!=NULL){ Push(s,now->Right); break; } } } } void PreorderTraversal( BinTree BT ){ Stack s=CreateStack(); //Push(s,BT); BinTree now=BT; if(now!=NULL) Push(s,now); while(!IsEmpty(s)){ now=Pop(s); printf(" %c",now->Data); if(now->Right!=NULL) Push(s,now->Right); if(now->Left!=NULL) Push(s,now->Left); } } void PostorderTraversal( BinTree BT ){ Stack s=CreateStack(); if(BT!=NULL) Push(s,BT); BinTree now=BT,last=NULL; while(!IsEmpty(s)){ while(Peek(s)->Left!=NULL) Push(s,Peek(s)->Left); while(!IsEmpty(s)){ now=Peek(s); if(now->Right==last||now->Right==NULL){ printf(" %c",now->Data); Pop(s); last=now; } else{ Push(s,now->Right); break; } } } }

12

void DFS( MGraph Graph, Vertex V, void (*Visit)(Vertex) ) /*第一个参数是传入二维数组的头地址（即图）第二个参数是结点编号第三个参数是传入Visit()这个函数的地址（可以自行百度函数是怎么作为参数传递的）*/ { /*从第V个顶点出发递归地深度优先遍历图G*/ int i; Visited[V] = true;//标记为true，说明已经遍历过了 Visit(V); //打印出V这个结点 for(i = 0; i < Graph->Nv; i++) //遍历V的每个邻接点 { if(Graph->G[V][i] == 1 && !Visited[i]) /*Graph->G[V][i] == 1说明有结点，!Visited[i]为真，说明未遍历过*/ { DFS(Graph, i, Visit); //递归调用DFS } } }

13

void BFS ( LGraph Graph, Vertex S, void (*Visit)(Vertex) ) { Visited[S]=true;//标记起始点 Visit(S); int queue[1000],front=0,rear=0; queue[rear++]=S;//起始点入队列 PtrToAdjVNode temp;//temp就代表当前点的邻接点的下标 while(front<rear){//队伍不为空 temp=Graph->G[queue[front++]].FirstEdge; while(temp){ int p=temp->AdjV;//把temp中的下标提取出来 if(!Visited[p]){//如果p点没有被标记的话 Visited[p]=true; Visit(p); queue[rear++]=p;//储存在队列中 } temp=temp->Next;//指向下一个邻接点 } } }

14

BinTree Insert( BinTree BST, ElementType X ) { if(BST==NULL) { BinTree gg=(BinTree)malloc(sizeof(struct TNode)); gg->Data=X; gg->Left=NULL; gg->Right=NULL; BST=gg; return BST; } else { BinTree hh=BST,parent; int flag; while(hh!=NULL) { parent=hh; if(X>hh->Data) hh=hh->Right,flag=1; else hh=hh->Left,flag=0; } BinTree tmp=(BinTree)malloc(sizeof(struct TNode)); tmp->Data=X; tmp->Left=NULL; tmp->Right=NULL; hh=tmp; if(flag)parent->Right=hh; else parent->Left=hh; return BST; } } Position Find( BinTree BST, ElementType X ) { if(BST) { while(BST) { if(X==BST->Data)return BST; else if(X>BST->Data) BST=BST->Right; else if(X<BST->Data) BST=BST->Left; } } return BST; } Position FindMin( BinTree BST )//找到搜索二叉树中最小值 { BinTree gg=NULL; if(BST) { while(BST) gg=BST, BST=BST->Left; } return gg; } Position FindMax( BinTree BST )//找到搜索二叉树最大值 { BinTree gg=NULL; if(BST) { while(BST) gg=BST,BST=BST->Right; } return gg; } BinTree Delete( BinTree BST, ElementType X ) { //删除处理的关键在于删除这个节点 //之后还要就是将后面是节点给补上去 Position tmp; if(!BST) { printf("Not Found\n"); return BST; } else if(X<BST->Data) BST->Left=Delete(BST->Left,X); else if(X>BST->Data) BST->Right=Delete(BST->Right,X); else { if(BST->Left && BST->Right) { /* 被删除的结点有左右子结点 */ tmp=FindMin(BST->Right); /* 在右子树中找到最小结点填充删除结点 */ BST->Data = tmp ->Data; BST->Right=Delete(BST->Right,BST->Data);/* 递归删除要删除结点的右子树中最小元素 */ //这一步无法理解 }else { if(!BST->Left) BST=BST->Right; else if(!BST->Right) BST=BST->Left; } } return BST; }

编程题

1

#include <stdio.h> #include <stdlib.h> typedef struct PolyNode* Polynomial; struct PolyNode{ int coef; int expon; Polynomial next; }; Polynomial ReadPoly(); Polynomial Mult(Polynomial P1,Polynomial P2); void PrintPoly(Polynomial PP); Polynomial Add(Polynomial P1,Polynomial P2); int main() //程序框架搭建 { Polynomial P1, P2, PP, PS; P1 = ReadPoly(); P2 = ReadPoly(); PP = Mult(P1, P2); PrintPoly(PP); PS = Add(P1, P2); PrintPoly(PS); return 0; } //对Rear指针的处理：1.初值为NULL,根据是否为空做不同处理；2.指向一个空节点 //*pRear当前结果表达式尾项指针的指针 //函数实现在pRear后面插入节点 void Attach(int c, int e, Polynomial *pRear) { Polynomial P; P = (Polynomial)malloc(sizeof(struct PolyNode)); P->coef = c; P->expon = e; P->next = NULL; (*pRear)->next = P; *pRear = P; } Polynomial ReadPoly() { Polynomial P, Rear, t; int c, e, N; scanf("%d", &N); P = (Polynomial)malloc(sizeof(struct PolyNode)); //链表头空节点 P->next = NULL; Rear = P; while (N--) { scanf("%d %d", &c, &e); if (c != 0) Attach(c, e, &Rear); //将当前项插入多项式尾部 } t = P; P = P->next; free(t); //删除临时生成的头结点 return P; } Polynomial Add(Polynomial P1, Polynomial P2) { Polynomial t1, t2; t1 = P1; t2 = P2; //生成新的头结点 Polynomial P,t; P = (Polynomial)malloc(sizeof(struct PolyNode)); P->next = NULL; Polynomial Rear; Rear = P; while (t1&&t2) { if (t1->expon==t2->expon) { if (t1->coef+t2->coef) //系数和为0时不添加到尾节点上 /*考虑周全*/ { Attach(t1->coef + t2->coef, t1->expon, &Rear); } t1 = t1->next; t2 = t2->next; } else if (t1->expon>t2->expon) { Attach(t1->coef, t1->expon, &Rear); t1=t1->next; }else { Attach(t2->coef, t2->expon, &Rear); t2 = t2->next; } } while (t1) { Attach(t1->coef, t1->expon, &Rear); t1 = t1->next; } while (t2) { Attach(t2->coef, t2->expon, &Rear); t2 = t2->next; } t = P; P = P->next; free(t); return P; } //多项式乘法方法： //1. 将乘法运算转换为加法运算，让P1的每一项和P2相乘，在加到结果多项式中 //2. 逐项插入，将P1当前项乘P2当前项，在插入到结果表达式中，关键是要找到插入的位置 Polynomial Mult(Polynomial P1, Polynomial P2) { Polynomial P, Rear; Polynomial t1, t2, t; if (!P1||!P2) { return NULL; } t1 = P1; t2 = P2; P = (Polynomial)malloc(sizeof(struct PolyNode)); Rear = P; while (t2) { //先用P1的第一项乘以P2,得到初始结果多项式 Attach(t1->coef*t2->coef, t1->expon + t2->expon, &Rear); t2 = t2->next; } t1 = t1->next; while (t1) { t2 = P2; Rear = P; //将尾节点置到头结点来 while (t2) { int e = t1->expon + t2->expon; int c = t1->coef * t2->coef; //以后的每一项相乘的结果 while (Rear->next&&Rear->next->expon>e) //找插入位置 { Rear = Rear->next; } if (Rear->next&&Rear->next->expon==e) { if (Rear->next->coef+c) //判系数是否为0 { Rear->next->coef += c; } else //为0删除节点 { t = Rear->next; Rear->next = t->next; free(t); } } else //插入位置 { t = (Polynomial)malloc(sizeof(struct PolyNode)); t->coef = c; t->expon = e; t->next = Rear->next; Rear->next = t; Rear = Rear->next; } t2 = t2->next; } t1 = t1->next; } t2 = P; P = P->next; free(t2); return P; } void PrintPoly(Polynomial P) { int flag = 0;//辅助调整输出格式 if (!P) { printf("0 0\n"); /*格式*/ return; } while (P) { if (!flag) //第一次 { flag = 1; } else { printf(" "); } printf("%d %d", P->coef, P->expon); P = P->next; } printf("\n"); }

2

#include <stdio.h> #include <stdlib.h> typedef int Position; typedef int ElementType; typedef struct Node *PtrToNode; struct Node { Position Address; ElementType Data; Position Next; PtrToNode Nextptr; }; typedef PtrToNode List; #define MaxSize 100000 struct Node arr[MaxSize]; List ReadList(Position firstAddr, int *length) { int i, list_size; Position addr, pos; List L, p, temp; L = (List)malloc(sizeof(struct Node)); L->Nextptr = NULL; p = L; memset(&arr, -1, sizeof(struct Node)); for ( i = 0; i < (*length); ++i ) { scanf("%d", &addr); arr[addr].Address = addr; scanf("%d %d", &arr[addr].Data, &arr[addr].Next); } list_size = 0; pos = firstAddr; while (arr[pos].Address != -1) { p->Nextptr = &arr[pos]; p = p->Nextptr; ++list_size; if (arr[pos].Next == -1) break; pos = p->Next; } *length = list_size; temp = L; L = L->Nextptr; free(temp); return L; } List Reverse(List L, int reverse_length) { List p1, p2, p3, rear; p1 = L; p2 = L->Nextptr; p3 = p2->Nextptr; while (reverse_length--) { p2->Nextptr = p1; p1 = p2; p2 = p3; if(p3) p3 = p3->Nextptr; } rear = L->Nextptr; rear->Nextptr = p2; L->Nextptr = p1; return rear; } List ReverseList(List L, int length, int reverse_length) { if (reverse_length == 1) return L; int t; List head, p, temp; head = (List)malloc(sizeof(struct Node)); head->Nextptr = L; p = head; t = length / reverse_length; while (t--) { p = Reverse(p, reverse_length); } if (length % reverse_length == 0) p->Nextptr = NULL; temp = head; head = head->Nextptr; free(temp); return head; } void PrintList( List L ) { List p; p = L; while (p) { if (!p->Nextptr) printf("%.5d %d %d\n", p->Address, p->Data, -1); else printf("%.5d %d %.5d\n", p->Address, p->Data, p->Nextptr->Address); p = p->Nextptr; } } int main() { Position firstAddr; int N, K; List L; scanf("%d %d %d", &firstAddr, &N, &K); L = ReadList(firstAddr, &N); L = ReverseList(L, N, K); PrintList(L); return 0; }

3

#include<stdio.h> #define maxsize 1003 int main() { char stack[maxsize]; int top=-1; char ch[maxsize],ch1[maxsize],ch2[maxsize]; int i,j,k=0; ch1['(']=')'; ch1['[']=']'; ch1['{']='}'; ch1['<']='>'; while(1) //此函数地目的是，依次输入所有字符，当遇到字符为括号符时，存入数组ch2; { gets(ch); //看样例3，里面有0.1这个小数点。再加上结束的标记是某一行只有一个小数点和一个回车，因此，一行字符一行字符地输入。 if(ch[0]=='.'&&ch[1]=='\0') break; for(j=0;ch[j]!='\0';j++) { if(ch[j]=='('||ch[j]==')'||ch[j]=='['||ch[j]==']'||ch[j]=='{'||ch[j]=='}') ch2[k++]=ch[j]; else if(ch[j]=='/'&&ch[j+1]=='*') //因为这里有j和j+1，所以，完成后j需要加1； {ch2[k++]='<';j++;} else if(ch[j]=='*'&&ch[j+1]=='/') {ch2[k++]='>';j++;} } } int flag=1; for(i=0;i<k;i++) { if(ch2[i]=='('||ch2[i]=='['||ch2[i]=='{'||ch2[i]=='<') stack[++top]=ch2[i]; if(ch2[i]==')'||ch2[i]==']'||ch2[i]=='}'||ch2[i]=='>') { if(top!=-1&&ch1[stack[top]]==ch2[i]) top--; else { printf("NO\n"); if(top==-1) //缺左边符号 { if(ch2[i]==')') printf("?-)"); else if(ch2[i]==']') printf("?-]"); else if(ch2[i]=='}') printf("?-}"); else if(ch2[i]=='>') printf("?-*/"); } else if(top!=-1&&ch1[stack[top]]!=ch2[i]) //缺右边符号 { if(stack[top]=='(') printf("(-?"); else if(stack[top]=='[') printf("[-?"); else if(stack[top]=='{') printf("{-?"); else if(stack[top]=='<') printf("/*-?"); } flag=0; break; //只要检测到不匹配，就结束 } } } if(flag==1&&top==-1) //只有再栈为空时才可能输出yes； printf("YES"); else if(flag==1&&top!=-1) //当输入字符为[[[]时，虽然flag=1，但是也是错误的 { printf("NO\n"); if(stack[top]=='(') printf("(-?"); //跟上面一样 else if(stack[top]=='[') printf("[-?"); else if(stack[top]=='{') printf("{-?"); else if(stack[top]=='<') printf("/*-?"); } return 0; }

4

#include<stdio.h> #include<string.h> #include<stdlib.h> char str[27]; int len; char stack[27]; int top=0; int index=0; int IsNum(char c) { if(c>='0'&&c<='9'||c=='.') return 1; else return 0; } int compare(char a,char b) { if(b==')')return 1; if(a=='('||b=='(')return 0; switch(b) { case '+': case '-': return 1; case '*': case '/': switch(a){ case '+': case '-': return 0; case '*': case '/': return 1; } } } int ZhengFu(char a) { if(a=='+'||a=='-') return 1; else return 0; } void Mainfun() { int space=0; for(index=0;index<len;index++) { //先判断是否为数字，为数字就输出 if(IsNum(str[index])) { if(space==1) { printf(" "); space =0; } printf("%c",str[index]); } //+ - 这两个符号要进一步判断是否是正负号 //判断符号为+-号并且是在第一位或者前一位不是数字和‘）’ 那么这个就是正负号 else if(ZhengFu(str[index])&&( (index==0) || (IsNum(str[index-1])!=1&&str[index-1]!=')') )) { //如果是正负号，那么符号需要输出，正号不需要输出 if(str[index]=='-') { if(space==1) { printf(" "); space=0; } printf("%c",str[index]); } } //如果是运算符 else { if(top!=0) //栈内有运算符，需要比较 { if(str[index]==')') //如果是')',就要输出'('之前的所有运算符 { while(top--) { if(stack[top]=='(')break; else printf(" %c",stack[top]); } } else { while(top!=0) { if(compare(stack[top-1],str[index])) //来比较运算符 printf(" %c",stack[--top]); else break; } stack[top++]=str[index]; } } else //栈为空，直接入栈 { stack[top++]=str[index]; } int j; for(j=0;j<top;j++) if(stack[j]!='(') { space=1; break; } } } while(top!=0) printf(" %c",stack[--top]); } int main() { scanf("%s",str); len=strlen(str); Mainfun(); return 0; }

5

#include<stdio.h> #include<stdlib.h> struct st { int date[1005]; int front,rear; }; typedef struct st *Qnode; typedef Qnode queue; int main() { int n; scanf("%d",&n); queue q1,q2; q1=(queue)malloc(sizeof(st));//c创建奇数队列q1 q2=(queue)malloc(sizeof(st));//创建偶数队列q2 q1->rear=q2->rear=q1->front=q2->front=0;//初始化q1 q2 while(n--) { int m; scanf("%d",&m); if(m%2) {//如果是奇数就存在q1 q1->date[q1->rear]=m; q1->rear++; } else {//如果是偶数就存在q2 q2->date[q2->rear]=m; q2->rear++; } } //队列就相当于一个结构体里面嵌套了一个数组然后用front和rear来指向队首和队尾进而模拟这个操作 //入队的话相当于rear向后移出队的话就相当于front向后移 while(q1->front!=q1->rear)//模拟出队的过程如果q1->front不等于q2->rear就让front向后移 { int cnt=2,i=0; //cnt 记录每次要输出两个个数i是用来控制空格的 while(cnt--&&q1->front!=q1->rear){ // if(i++) printf(" ");//奇数的第一个前面不加空格其他都加 printf("%d",q1->date[q1->front]);//输出这个队首的元素 //同时让front后移 q1->front++; } if(q2->front!=q2->rear){//同上 printf(" %d ",q2->date[q2->front]); q2->front++; } } int cnt=0; while(q2->rear!=q2->front){ //如果奇数输出完了还有偶数就让偶数输出道理相同cnt是控制空格的个人习惯这样你也可以换其他的方法 if(cnt++) printf(" "); printf("%d",q2->date[q2->front]); q2->front++; } return 0; }

6

#include<iostream> #include<stack> #include<algorithm> using namespace std; int main() { stack<int>a, b; int c, d; cin >> c >> d; if (c > d)swap(c, d);//让1为小栈 while (1) { char temp1; cin >> temp1; if (temp1 == 'T') break; if (temp1 == 'A') { int temp2; cin >> temp2; if (a.size() < c)//1栈没满 { a.push(temp2); } else { if (b.empty())//2栈为空 { while (!a.empty()) { int temp = a.top(); a.pop(); b.push(temp); } a.push(temp2); } else { cout << "ERROR:Full" << endl; } } } else if (temp1 == 'D') { if (!b.empty())//2栈不空 { int temp = b.top(); b.pop(); cout << temp << endl; } else//2栈为空 { if (!a.empty())//1栈不空 { while (!a.empty()) { int temp = a.top(); a.pop(); b.push(temp); } int temp = b.top(); b.pop(); cout << temp << endl; } else//1栈也为空 { cout << "ERROR:Empty" << endl; } } } } }

7

#include<stdio.h> #include <iostream> #include<string> #include<cstring> using namespace std; int main() { char s1[1000001]; scanf("%s",s1); int N; cin >> N; char s2[10][100001]; for(int i = 0;i<N;i++) { cin>>s2[i]; } string s3[10]; char *s; for(int i = 0;i<N;i++) { //s3[i] = strstr(s1,s2[i]); //strcpy(s3[i],strstr(s1,s2[i])); s = strstr(s1,s2[i]); if(s==NULL) { s3[i] = "Not Found"; } else { s3[i] = s; } } for(int i = 0;i<N;i++) { cout << s3[i]<<endl; } return 0; }

8

#include <iostream> #include <vector> using namespace std; #define Max_Node 11 #define END -1 typedef struct node { char value; int left; int right; }Node; void CreateTree(vector<Node>& Tree,int N)//获取树的输入，并将输入的字符合理转化成整型数字 { char value,left,right; for (int i=0; i<N; ++i) { cin>>value>>left>>right; Tree[i].value=value; if (left=='-') { Tree[i].left=END; }else { Tree[i].left=left-'0'; } if (right=='-') { Tree[i].right=END; }else { Tree[i].right=right-'0'; } } } int FindTreeRoot(vector<Node>& Tree,int N)//寻找树的树根（树根没有其它的结点指向它） { int Flag[Max_Node]; for (int i=0; i<N; ++i) { Flag[i]=0; } for (int i=0; i<N; ++i) { if (Tree[i].left!=END) { Flag[Tree[i].left]=1; } if (Tree[i].right!=END) { Flag[Tree[i].right]=1; } } int k; for (k=0; k<N; ++k) { if (Flag[k]==0) { break; } } return k; } bool IsOmorphic(int Root1,int Root2,vector<Node>& Tree1,vector<Node>& Tree2)//递归判断两树是否同构 { if (Tree1[Root1].value==Tree2[Root2].value) { //两结点相等，并都是叶子结点 if (Tree1[Root1].left==END && Tree1[Root1].right==END && Tree2[Root2].left==END && Tree2[Root2].right==END) { return true; } //以下四种情况都是，两个结点都是有一个孩子为空，另一个子树不空且这两个孩子相等的情形 if (Tree1[Tree1[Root1].left].value==Tree2[Tree2[Root2].left].value && Tree1[Root1].right==END && Tree2[Root2].right==END) { return IsOmorphic(Tree1[Root1].left, Tree2[Root2].left, Tree1, Tree2); } if (Tree1[Tree1[Root1].left].value==Tree2[Tree2[Root2].right].value && Tree1[Root1].right==END && Tree2[Root2].left==END) { return IsOmorphic(Tree1[Root1].left, Tree2[Root2].right, Tree1, Tree2); } if (Tree1[Tree1[Root1].right].value==Tree2[Tree2[Root2].left].value && Tree1[Root1].left==END && Tree2[Root2].right==END) { return IsOmorphic(Tree1[Root1].right, Tree2[Root2].left, Tree1, Tree2); } if (Tree1[Tree1[Root1].right].value==Tree2[Tree2[Root2].right].value && Tree1[Root1].left==END && Tree2[Root2].left==END) { return IsOmorphic(Tree1[Root1].right, Tree2[Root2].right, Tree1, Tree2); } //以下两种情形，两个结点的孩子都相等 if (Tree1[Tree1[Root1].left].value==Tree2[Tree2[Root2].left].value && Tree1[Tree1[Root1].right].value==Tree2[Tree2[Root2].right].value) { return (IsOmorphic(Tree1[Root1].left, Tree2[Root2].left, Tree1, Tree2))&&(IsOmorphic(Tree1[Root1].right, Tree2[Root2].right, Tree1, Tree2)); } if (Tree1[Tree1[Root1].left].value==Tree2[Tree2[Root2].right].value && Tree1[Tree1[Root1].right].value==Tree2[Tree2[Root2].left].value) { return (IsOmorphic(Tree1[Root1].left, Tree2[Root2].right, Tree1, Tree2))&&(IsOmorphic(Tree1[Root1].right, Tree2[Root2].left, Tree1, Tree2)); } } //不符合以上7种情况的其它情况都说明这两棵树不同构 return false; } int main(int argc, const char * argv[]) { //Input int N1=0; cin>>N1; vector<Node> Tree1(Max_Node); CreateTree(Tree1,N1); int N2=0; cin>>N2; vector<Node> Tree2(Max_Node); CreateTree(Tree2,N2); if (N1!=N2) { cout<<"No"; }else { if (N1==0) { cout<<"Yes"; }else { //Build Tree int root1=FindTreeRoot(Tree1,N1); int root2=FindTreeRoot(Tree2,N2); //Judge if (IsOmorphic(root1, root2, Tree1, Tree2)) { cout<<"Yes"; }else { cout<<"No"; } } } return 0; }

9

#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a) memset(a, 0, sizeof(a)) #define pb push_back using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair<string, int> psi; typedef pair<string, string> pss; const double PI = 3.14159265358979323846264338327; const double E = exp(1); const double eps = 1e-30; const int INF = 0x3f3f3f3f; const int maxn = 1e2 + 5; const int MOD = 1e9 + 7; int v[10]; struct Node { int l, r; }q[10]; void init() { CLR(q); CLR(v); } queue <int> Q; vector <int> ans; void bfs() { int len = Q.size(); for (int i = 0; i < len; i++) { int num = Q.front(); Q.pop(); if (q[num].l == -1 && q[num].r == -1) ans.pb(num); if (q[num].l != -1) Q.push(q[num].l); if (q[num].r != -1) Q.push(q[num].r); } if (Q.size()) bfs(); } int main() { init(); int n; scanf("%d", &n); char a, b; for (int i = 0; i < n; i++) { scanf(" %c %c", &a, &b); if (a == '-') q[i].l = -1; else { q[i].l = a - '0'; v[a - '0'] = 1; } if (b == '-') q[i].r = -1; else { q[i].r = b - '0'; v[b - '0'] = 1; } } int root; for (int i = 0; i < n; i++) { if (v[i] == 0) { root = i; break; } } Q.push(root); bfs(); vector <int>::iterator it; for (it = ans.begin(); it != ans.end(); it++) { if (it != ans.begin()) printf(" "); printf("%d", *it); } cout << endl; }

10

#include <stdio.h> #include <stdlib.h> #define Max 10001 #define INF -1 void BulidHeap(); void Insert(int n); void Calculate(); int Delete(); typedef struct HeapStruct MinHeap; struct HeapStruct{ int Data[Max]; int Size; }; MinHeap H; int Sum; int main() { BulidHeap(); Calculate(); printf("%d",Sum); } void BulidHeap() { int N,i,n; H.Data[0] = INF;//哨兵 scanf("%d",&N); for(i = 1; i <= N; i++){ scanf("%d",&n); Insert(n); } } void Insert(int n) { int i; i = ++H.Size; for( ; H.Data[i / 2] > n; i /= 2){ H.Data[i] = H.Data[i / 2]; } H.Data[i] = n; } void Calculate() { int a1,a2; while(H.Size > 1){ a1 = Delete(); a2 = Delete(); Insert(a1 + a2); Sum = Sum + a1 + a2; } } int Delete() { int parent,child,t,n; n = H.Data[1]; t = H.Data[H.Size--]; for(parent = 1; parent * 2 <= H.Size;parent = child){ child = parent * 2; if(H.Data[child + 1] < H.Data[child]){ child++; } if(t <= H.Data[child]) break; else{ H.Data[parent] = H.Data[child]; } } H.Data[parent] = t; return n; }

11

#include <stdio.h> #include <stdlib.h> void find(int *a,int i,int j) { if(a[i]==0) { printf("ERROR: T[%d] is NULL\n",i); return; } if(a[j]==0) { printf("ERROR: T[%d] is NULL\n",j); return; } while(1) { if(i==j)break; else { if(i>j) i=i/2; else j=j/2; } } printf("%d %d\n",i,a[i]); } int main() { int a[1100],i,j,n; scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&a[i]); scanf("%d%d",&i,&j); find(a,i,j); return 0; }

12

#include<cstdio> #include<cstring> #include<queue> #define MAX 20 using namespace std; int map[MAX][MAX] = {0}; int visited[MAX]={0}; int m,n; void dfs(int x){ for(int i = 0; i < n; ++i){ if(!visited[i]&&map[x][i]){ visited[i] = 1; printf(" %d",i); dfs(i); } } } int main() { int v1,v2; scanf("%d",&n); scanf("%d",&m); for(int i = 0; i < m; ++i){ scanf("%d %d",&v1,&v2); map[v1][v2]=map[v2][v1]=1; } for(int i = 0; i < n; ++i){ if(!visited[i]){ visited[i]=1; printf("{"); printf(" %d",i); dfs(i); printf(" }\n"); } } //bfs memset(visited,0,sizeof(visited)); queue<int> q; for(int i = 0; i < n; ++i){ if(!visited[i]){ visited[i]=1; printf("{"); //printf(" %d",i); q.push(i); while(!q.empty()){ for(int j = 0; j <= n; ++j){ if(!visited[j]&&map[q.front()][j]){ visited[j]=1; q.push(j); } } printf(" %d",q.front()); q.pop(); } printf(" }\n"); } } return 0; }

13

/*2015.7.16cyq*/ //Prim最小生成树算法 #include <iostream> #include <vector> #include <fstream> #include <algorithm> using namespace std; const int MAX=2147483647; //ifstream fin("case1.txt"); //#define cin fin struct node{ int num; //结点序号 int weight; //能连通到已确定子图的最小边 int preNode;//最小边依附的结点,用于输出具体生成树 node():num(-1),weight(-1),preNode(-1){} node(int n,int wei,int preN):num(n),weight(wei),preNode(preN){} bool operator < (const node &a) const{ return weight<a.weight; } }; int main(){ int N,M; cin>>N>>M; vector<vector<int> > edges(N+1,vector<int>(N+1,-1));//-1表示不连通 int a,b,c; while(M--){ cin>>a>>b>>c; edges[a][b]=c; edges[b][a]=c; } vector<node> AB;//已吸收的点,一开始只有结点1 AB.push_back(node(1,0,-1));// vector<node> UD(N-1);//未吸收的点 for(int i=0;i<N-1;i++){ UD[i].num=i+2;//编号2到N int tmp=edges[1][UD[i].num]; if(tmp>0){//能连到结点1的结点 UD[i].weight=tmp; UD[i].preNode=1; }else{//不能连到结点1的结点 UD[i].weight=MAX; UD[i].preNode=-1; } } int totalLength=0; //vector<pair<int,int> > result;//用于输出具体生成树 while(!UD.empty()){ sort(UD.begin(),UD.end()); node cur=UD[0];//取出能以最小代价吸收的点 UD.erase(UD.begin()); if(cur.weight==MAX){ cout<<"-1"<<endl; return 0; } totalLength+=cur.weight; // result.push_back(make_pair(cur.num,cur.preNode)); for(auto it=UD.begin();it!=UD.end();++it){//用该点修正未吸收的点 int w=edges[cur.num][(*it).num]; if(w>0){ if(w<(*it).weight){ (*it).weight=w; (*it).preNode=cur.num; } } } } cout<<totalLength<<endl; //for(auto it=result.begin();it!=result.end();++it){//输出最小生成树 // cout<<(*it).first<<" "<<(*it).second<<" "<<edges[(*it).first][(*it).second]<<endl; //} return 0; }

14

#include <bits/stdc++.h> using namespace std; const int maxn=1000+10; const int INF=0x3f3f3f3f; int cost[maxn][maxn]; int mincost[maxn]; bool used[maxn]; int V,E; void prim() { memset(mincost,INF,sizeof(mincost)); memset(used,false,sizeof(used)); mincost[1]=0; int res=0; bool flag=false; while(true) { int v=-1; //cout<<"ggV: "<<V<<endl; for(int u=1;u<=V;u++) { //cout<<"gg: "<<mincost[u]<<" "<<used[u]<<endl; if(!used[u]&&(v==-1||mincost[u]<mincost[v])) { v=u; } } //cout<<"ggv: "<<v<<endl; if(v==-1) break; used[v]=true; if(mincost[v]==INF) { flag=true; break; } res+=mincost[v]; for(int u=1;u<=V;u++) { mincost[u]=min(mincost[u],cost[u][v]); } } if(flag) printf("Impossible\n"); else printf("%d\n",res); } int main() { for(int i=0;i<maxn;i++) memset(cost[i],INF,sizeof(cost[i])); //for(int i=0;i<maxn;i++) cout<<"gg:: "<<cost[i][1]<<endl; scanf("%d %d",&V,&E); for(int i=0;i<E;i++) { int s,t,c; scanf("%d %d %d",&s,&t,&c); cost[s][t]=c; cost[t][s]=c; //cout<<"输出中间值 "<<s<<" "<<t<<" "<<c<<" "<<f<<endl; } prim(); return 0; }

15

#include<bits/stdc++.h> using namespace std; const int N=105; vector<pair<int,int> >G[N]; int n,m,out[N],ans[N],dis[N],tot; int main() { cin>>n>>m; for(int i=0,u,v,w; i<m; i++)cin>>u>>v>>w,out[v]++,G[u].push_back({v,w}); queue<int>Q; for(int i=0; i<n; i++)if(!out[i])Q.push(i); while(!Q.empty()) { int u=Q.front(); Q.pop(),ans[tot++]=u; for(auto X:G[u]) { int v=X.first,w=X.second; if(--out[v]==0)Q.push(v); if(dis[v]<dis[u]+w)dis[v]=dis[u]+w; } } if(tot==n) { int ans1=0; for(int i=0;i<n;i++)ans1=max(ans1,dis[i]); cout<<ans1<<"\n"; } else cout<<"Impossible"; return 0; }

16

#include<stdio.h> #include<stdlib.h> #define maxvertex 110 #define maxweigh 0x3f3f3f int mindis = maxweigh; int mindex = 0; int maxn; int main(){ //利用邻接矩阵存储图 int Graph[maxvertex][maxvertex]; int N,M; int idx1,idx2,weigh; scanf("%d%d",&N,&M); //初始化 for (int i=1; i<=N; i++) { for (int j=1; j<=N; j++) { if (i==j) { Graph[i][j] = 0; } else Graph[i][j] = maxweigh; } } //输入边，建立图 for (int i=0; i<M; i++) { scanf("%d%d%d",&idx1,&idx2,&weigh); Graph[idx1][idx2] = Graph[idx2][idx1] = weigh; } //floyd算法 for (int k=1; k<=N; k++) { for (int i=1; i<=N ; i++) { for (int j=1; j<=N; j++) { if (Graph[i][j] > (Graph[i][k]+Graph[k][j])) { Graph[i][j] = (Graph[i][k]+Graph[k][j]); } } } } for (int i=1; i<=N; i++){ maxn =0; for (int j=1; j<=N; j++) { //更新当前结点的最大值 if (Graph[i][j] > maxn) { maxn = Graph[i][j]; } } if (maxn < mindis) { mindis = maxn; mindex = i; } } //输出结果 if (mindex ==0 ) { printf("0\n"); } else printf("%d %d\n",mindex,mindis); return 0; }

17

#include<iostream> #include<cstring> #define MAXN 505 #define MCOST 250005 #define ERROR 0 using namespace std; float g[MAXN][MAXN],dist[MAXN]; int cost[MAXN][MAXN],dis[MAXN][MAXN],collected[MAXN],path[MAXN]; int n; int FindMinDist( ) { /* 返回未被收录顶点中dist最小者 */ int MinV, V; float MinDist = MCOST; for (V=0; V<n; V++) { if ( collected[V]==0 && dist[V]<MinDist) { /* 若V未被收录，且dist[V]更小 */ MinDist = dist[V]; /* 更新最小距离 */ MinV = V; /* 更新对应顶点 */ } } if (MinDist < MCOST) /* 若找到最小dist */ return MinV; /* 返回对应的顶点下标 */ else return ERROR; /* 若这样的顶点不存在，返回错误标记 */ } int Dijkstra( int S ) { int V, W; /* 初始化：此处默认邻接矩阵中不存在的边用INFINITY表示 */ for ( V=0; V<n; V++ ) { dist[V] = g[S][V]; if ( dist[V]<MCOST ) path[V] = S; else path[V] = -1; collected[V] = 0; } /* 先将起点收入集合 */ dist[S] = 0; collected[S] = 1; while (1) { /* V = 未被收录顶点中dist最小者 */ V = FindMinDist( ); if ( V==ERROR ) /* 若这样的V不存在 */ break; /* 算法结束 */ collected[V] = 1; /* 收录V */ for( W=0; W<n; W++ ) /* 对图中的每个顶点W */ /* 若W是V的邻接点并且未被收录 */ if ( collected[W]==0 && g[V][W]<MCOST ) { if ( g[V][W]<0 ) /* 若有负边 */ return 0; /* 不能正确解决，返回错误标记 */ /* 若收录V使得dist[W]变小 */ if ( dist[V]+g[V][W] < dist[W] ) { dist[W] = dist[V]+g[V][W]; /* 更新dist[W] */ path[W] = V; /* 更新S到W的路径 */ } } } /* while结束*/ return 1; /* 算法执行完毕，返回正确标记 */ } int main(){ cin>>n; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ g[i][j]=MCOST; } g[i][i]=0; } int m,s,d;cin>>m>>s>>d;int a,b,p,c; for(int i=0;i<m;i++){ cin>>a>>b>>p>>c; g[a][b]=p*0.9999+c*0.0001;g[b][a]=p*0.9999+c*0.0001; cost[a][b]=c;cost[b][a]=c; dis[a][b]=p;dis[b][a]=p; } Dijkstra(s); int cntc=0,t=d,cntd=0; while(t!=s){ cntc+=cost[t][path[t]]; cntd+=dis[t][path[t]]; t=path[t]; } cout<<cntd<<" "<<cntc; return 0; }

18

#include <iostream> #include <deque> #include <iomanip> #define ElementType int #define Vertex int typedef struct _ENode { Vertex V1; Vertex V2; }Edge; typedef struct _GNode { int num_of_array;//下三角矩阵存储，所以和一般的二维不一样 int Nv;//顶点数 int Ne;//边数 ElementType *G;//下三角临接矩阵,一维代替二维 }Graph; using namespace std; void creat_Graph(Graph *, int num_v, int num_e); void insert_Edge(Graph *, Edge); void Six_Degrees(Graph *); double Calculate_Six_Percent(Graph *, Vertex, int degrees, bool visited[]); void print(Graph *); double *percent; int main() { int N, M; cin >> N >> M; Graph *graph = new Graph; creat_Graph(graph, N, M); for (int i = 0; i < M; i++) { Edge edge; cin >> edge.V1 >> edge.V2; insert_Edge(graph, edge); } percent = new double[graph->num_of_array]; Six_Degrees(graph); print(graph); return 0; } void creat_Graph(Graph *graph, int num_v, int num_e) { graph->num_of_array = num_v * (num_v + 1) / 2; graph->Nv = num_v; graph->Ne = num_e; graph->G = new ElementType[graph->num_of_array]; for (int i = 0; i < graph->num_of_array; i++) //下三角临接矩阵初始化 graph->G[i] = 0; } void insert_Edge(Graph *graph, Edge edge) { edge.V1 -= 1;//输出的是从1开始计数，而此程序矩阵从0开始 edge.V2 -= 1; if (edge.V1 < edge.V2) graph->G[edge.V2*(edge.V2 + 1) / 2 + edge.V1] = 1; else graph->G[edge.V1*(edge.V1 + 1) / 2 + edge.V2] = 1; } void Six_Degrees(Graph *graph) { bool *visited = new bool[graph->Nv]; for (Vertex i = 0; i < graph->Nv; i++) { for (int i = 0; i < graph->Nv; i++)//初始化visited，visited只有Nv个数据 visited[i] = 0; percent[i] = Calculate_Six_Percent(graph, i, 1, visited);//percent也只有Nv个数据 } } double Calculate_Six_Percent(Graph *graph, Vertex start_V, int degrees, bool visited[]) { Vertex *queue = new Vertex[graph->num_of_array + 1]; int front = 0, rear = 0, last = 0; int num_six_degrees = 0;//不超过6度的顶点数 Vertex V = start_V; visited[V] = 1; queue[rear++] = V;//入队 while (front != rear && degrees <= 6) { V = queue[front++];//出队 Vertex target_V = 0;//由于三角矩阵的关系，i不能表示顶点，遂用 target_V 表示要与顶点 V 做判断的顶点 Vertex start_TLine = V * (V + 1) / 2; Vertex start_VLine = start_TLine + V; for (Vertex i = start_TLine; i < start_TLine + V; i++) //遍历横向顶点 { if (graph->G[i] == 1 && visited[target_V] == 0) { //有边且未被访问过 queue[rear++] = target_V; visited[target_V] = 1; num_six_degrees++; } target_V++; } int k = 0; for (Vertex i = start_VLine; i < graph->num_of_array; i = i + V + k)//遍历竖向顶点 { k++; if (graph->G[i] == 1 && visited[target_V] == 0) { queue[rear++] = target_V; visited[target_V] = 1; num_six_degrees++; } target_V++; } if (last == front - 1) { degrees++; last = rear - 1; } } return (double)(num_six_degrees + 1) / graph->Nv; } void print(Graph *graph) { int flag = 1; cout << setprecision(2) << setiosflags(ios::fixed); for (int i = 0; i < graph->Nv; i++) { if (flag) flag = 0; else cout << endl; cout << i+1 << ": " << percent[i] * 100 << "%"; } }

19

#include <cstdio> #include <iostream> #include <algorithm> #include <cmath> #include <cstdlib> #include <cstring> #include <vector> #include <list> #include <map> #include <stack> #include <queue> using namespace std; #define ll long long typedef struct Tree{ int data; Tree *l,*r; }*BiTree; bool check[20]; void build(BiTree &T,int e) { if(!T) { T = new Tree; T->data = e; T->l = T->r = NULL; return; } if(!T->l && e < T->data) { /*BiTree temp = new Tree; temp->l = temp->r = NULL; T->l = temp; temp->data = e;*/ T->l = new Tree; T->l->l = T->l->r = NULL; T->l->data = e; return; } if(!T->r && e > T->data) { /*BiTree temp = new Tree; temp->l = temp->r = NULL; T->r = temp; temp->data = e;*/ T->r = new Tree; T->r->l = T->r->r = NULL; T->r->data = e; return; } if(e > T->data) build(T->r,e); else build(T->l,e); return; } bool juge(BiTree T,int e) { if(!check[T->data] && e != T->data) return false; check[T->data] = 1; if(e == T->data) return true; if(e < T->data) return juge(T->l,e); else return juge(T->r,e); } int main() { int n,l; while(cin >> n&&n) { cin >> l; BiTree T ; T = NULL; for(int i = 0;i < n;i++) { int x; cin >> x; build(T,x); } while(l--) { int f = 0; memset(check,0,sizeof(check)); for(int i = 0;i < n;i++) { int x; cin >> x; if(!juge(T,x)) f = 1; } if(f) cout << "No" <<endl; else cout << "Yes" <<endl; } } //cout << "AC" <<endl; return 0; }

20

#include <bits/stdc++.h> #define KEYLENGTH 15 typedef char ElementType[KEYLENGTH+1]; typedef int Index; typedef struct LNode *PtrToLNode; struct LNode { ElementType Data; PtrToLNode Next; int cnt; }; typedef PtrToLNode Position; typedef PtrToLNode List; typedef struct TblNode *HashTable; struct TblNode { int TableSize; List Heads; }; typedef struct Result { ElementType MinData; int sum; } Result; int GetTableSize(int n) { int i, j; for(i = n; ; ++i) { for(j = 2; j * j <= i; ++j) if(i % j == 0) break; if(j * j > i) return i; } } Index Hash(ElementType Key, int TableSize ) { return (atoi(Key + 6))%TableSize; //Key 取第六位到最后一位，全取的话太长 } PtrToLNode GetMax(HashTable H) { int Max = 0; PtrToLNode mmax = NULL; for(int i = 0; i < H->TableSize; ++i) { PtrToLNode temp = H->Heads[i].Next; while(temp != NULL) { if(Max < temp->cnt) { Max = temp->cnt; mmax = temp; } temp = temp->Next; } } return mmax; } PtrToLNode Find(HashTable H, ElementType key) { int hvalue = Hash(key, H->TableSize); PtrToLNode temp = H->Heads[hvalue].Next; while(temp != NULL) { if(strcmp(temp->Data, key) == 0) return temp; temp = temp->Next; } return NULL; } void Insert(HashTable &H, ElementType key) { int hvalue = Hash(key, H->TableSize); PtrToLNode temp = Find(H, key); if(temp != NULL) { ++temp->cnt; } else { PtrToLNode ins = (PtrToLNode)malloc(sizeof(struct LNode)); strcpy(ins->Data, key); ins->cnt = 1; ins->Next = H->Heads[hvalue].Next; H->Heads[hvalue].Next = ins; } } HashTable BuildTable() { int n; scanf("%d", &n); HashTable H = (HashTable)malloc(sizeof(struct TblNode)); H->TableSize = GetTableSize(2 * n); H->Heads = (PtrToLNode)malloc(sizeof(struct LNode) * (H->TableSize)); char key1[KEYLENGTH - 1], key2[KEYLENGTH - 1]; for(int i = 0; i < H->TableSize; ++i) { H->Heads[i].Next = NULL; } for(int i = 0; i < n; ++i) { scanf("%s %s", key1, key2); Insert(H, key1); Insert(H, key2); } return H; } void Solve(HashTable H) { PtrToLNode Max = GetMax(H); Result re; strcpy(re.MinData, Max->Data); re.sum = 0; for(int i = 0; i < H->TableSize; ++i) { PtrToLNode temp = H->Heads[i].Next; while(temp != NULL) { if(temp->cnt == Max->cnt) { ++re.sum; if(strcmp(re.MinData, temp->Data) > 0) strcpy(re.MinData, temp->Data); } temp = temp->Next; } } printf("%s %d", re.MinData, Max->cnt); if(re.sum > 1) printf(" %d", re.sum); printf("\n"); } int main() { int n; HashTable H; H = BuildTable(); Solve(H); return 0; }

21

#include<iostream> #include<map> #include<algorithm> #include<string> using namespace std; int main() { int n; cin>>n; map<long long,string> mp; for(int i=0;i<n;i++) { char c; long long a; string b; cin>>c>>a>>b; if(mp.count(a)==0 )//如果映射中还没有这个QQ号 { if(c=='L') { cout<<"ERROR: Not Exist"<<endl; } else if(c=='N') { mp[a]=b; cout<<"New: OK"<<endl; } } else { if(c=='N') { cout<<"ERROR: Exist"<<endl; } else if(c=='L') { if(b==mp[a]) { cout<<"Login: OK"<<endl; } else { cout<<"ERROR: Wrong PW"<<endl; } } } } }

22

#include <stdio.h> #include <stdlib.h> #define N 100000 #define Cutoff 10 #define Radix 10 void percdown(long *a, int n, int i); void merge(long *a, long *tmp, int start, int end, int middle); void msort(long *a, long *tmp, int start, int end); void merge_pass(long *a, long *tmp, int n, int length); void q_sort(long *a, int left, int right); void bubble_sort(long *a, int n); void insertion_sort(long *a, int n); void selection_sort(long *a, int n); void shell_sort(long *a, int n); void shellsedgewick_sort(long *a, int n); void heap_sort(long *a, int n); void merge1_sort(long *a, int n); void merge2_sort(long *a, int n); void quick_sort(long *a, int n); void radix_sort(long *a, int n); int main() { int i, n; long a[N]; scanf("%d", &n); for (i = 0;i < n;i++) scanf("%ld", &a[i]); radix_sort(a, n); printf("%ld", a[0]); for (i = 1;i < n;i++) printf(" %ld", a[i]); return 0; } //冒泡排序 void bubble_sort(long *a, int n) { int i, j, flag; long temp; for (i = n - 1;i > 0;i--) { flag = 0; for (j = 0;j < i;j++) { if (a[j] > a[j + 1]) { temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; flag = 1; } } if (!flag) break; } } //插入排序 void insertion_sort(long *a, int n) { int i, j; long temp; for (i = 1;i < n;i++) { temp = a[i]; for (j = i; j > 0 && a[j - 1] > temp; j--) a[j] = a[j - 1]; a[j] = temp; } } //选择排序 void selection_sort(long *a, int n) { int i, j, t; long temp; for (i = 0;i < n - 1;i++) { temp = a[i]; t = i; for (j = i + 1;j < n;j++) { if (a[j] < temp) { temp = a[j]; t = j; } } a[t] = a[i]; a[i] = temp; } } //希尔排序-希尔增量 void shell_sort(long *a, int n) { int i, j, d; long temp; for (d = n / 2;d > 0;d /= 2) { for (i = d;i < n;i++) { temp = a[i]; for (j = i;j >= d && a[j - d] > temp;j -= d) a[j] = a[j - d]; a[j] = temp; } } } //希尔排序-sedgewick增量 void shellsedgewick_sort(long *a, int n) { int i, j, d, si; int Sedgewick[] = { 929, 505, 209, 109, 41, 19, 5, 1, 0 }; long temp; for (si = 0;Sedgewick[si] >= n;si++) ; for (;Sedgewick[si] > 0;si++) { d = Sedgewick[si]; for (i = d;i < n;i++) { temp = a[i]; for (j = i;j >= d && a[j - d] > temp;j -= d) a[j] = a[j - d]; a[j] = temp; } } } //堆排序 void heap_sort(long *a, int n) { int i; long temp; for (i = (n - 2) / 2; i >= 0; i--) percdown(a, n, i); for (i = n - 1;i > 0;i--) { temp = a[i]; a[i] = a[0]; a[0] = temp; percdown(a, i, 0); } } void percdown(long *a, int n, int i) { int child; long x = a[i]; for (;i * 2 + 1 <= n - 1;i = child) { child = i * 2 + 1; if (child < n - 1 && a[child + 1] > a[child]) child++; if (x >= a[child]) break; else a[i] = a[child]; } a[i] = x; } //归并排序-递归实现 void merge1_sort(long *a, int n) { long *tmp = (long*)malloc(n*sizeof(long)); msort(a, tmp, 0, n - 1); free(tmp); } void msort(long *a, long *tmp, int start, int end) { int middle; if (start < end) { middle = (start + end) / 2; msort(a, tmp, start, middle); msort(a, tmp, middle + 1, end); merge(a, tmp, start, end, middle); } } void merge(long *a, long *tmp, int start, int end, int middle) { int l, r, s; s = start; l = start; r = middle + 1; while (l <= middle && r <= end) { if (a[l] <= a[r]) tmp[s++] = a[l++]; else tmp[s++] = a[r++]; } while (l <= middle) tmp[s++] = a[l++]; while (r <= end) tmp[s++] = a[r++]; for (;start <= end;start++) a[start] = tmp[start]; } //归并排序-循环实现 void merge2_sort(long *a, int n) { int length = 1; long *tmp = (long*)malloc(n*sizeof(long)); while (length < n) { merge_pass(a, tmp, n, length); length *= 2; merge_pass(tmp, a, n, length); length *= 2; } free(tmp); } void merge_pass(long *a, long *tmp, int n, int length) { int i, j; for (i = 0;i + 2 * length <= n;i += 2*length) merge(a, tmp, i, i + 2 * length - 1, i + length - 1); if (i + length <= n) merge(a, tmp, i, n - 1, i + length - 1); else for (j = i;j < n;j++) tmp[j] = a[j]; } //快速排序 void quick_sort(long *a, int n) { q_sort(a, 0, n - 1); } void q_sort(long *a, int left, int right) { long pivot, temp; int i, j, center; if (right - left + 1 > Cutoff) { center = (left + right) / 2; if (a[center] < a[left]) { temp = a[center];a[center] = a[left];a[left] = temp; } if (a[right] < a[left]) { temp = a[right];a[right] = a[left];a[left] = temp; } if (a[right] < a[center]) { temp = a[right];a[right] = a[center];a[center] = temp; } temp = a[right - 1];a[right - 1] = a[center];a[center] = temp; pivot = a[right - 1]; i = left; j = right - 1; for (;;) { while (a[++i] < pivot); while (a[--j] > pivot); if (i < j) { temp = a[i];a[i] = a[j];a[j] = temp; } else break; } temp = a[i];a[i] = a[right - 1];a[right - 1] = temp; q_sort(a, left, i - 1); q_sort(a, i + 1, right); } else insertion_sort(a + left, right - left + 1); } //基数排序-次位优先 struct Node { int data; Node* next; }; struct Bucket { Node *head, *tail; }; void radix_sort(long *a, int n) { int d, di, i, flag; long t; Bucket b[Radix*2 - 1];//19个桶 -9--1，0，1-9； Node *tmp, *p, *list = NULL; for (i = 0;i <= (Radix-1) * 2;i++) b[i].head = b[i].tail = NULL; for (i = n - 1;i >= 0;i--) { tmp = (Node*)malloc(sizeof(Node)); tmp->data = a[i]; tmp->next = list; list = tmp; } for (d = 1;;d++) { p = list; flag = 0; while (p) { t = p->data; for (i = 1;i <= d;i++) { di = t % Radix;t /= Radix; } if (di != 0) flag = 1; di += Radix-1; tmp = p; p = p->next; tmp->next = NULL; if (!b[di].head) b[di].head = b[di].tail = tmp; else { b[di].tail->next = tmp; b[di].tail = tmp; } } if (!flag) break; else { list = NULL; for (i = (Radix - 1) * 2;i >= 0;i--) { if (b[i].head) { b[i].tail->next = list; list = b[i].head; b[i].head = b[i].tail = NULL; } } } } for (i = 0;i < n;i++) { a[i] = b[Radix - 1].head->data; b[Radix - 1].head = b[Radix - 1].head->next; } }

23

#include<bits/stdc++.h> using namespace std; int main() { int n,m,k; cin>>n>>m>>k; int data[10]; double num[10000],num1[10000]; int t=0; while(n--) { int sum=0; memset(data,0,sizeof(data)); for(int i=0; i<m; i++) cin>>data[i]; sort(data,data+m); for(int i=1; i<m-1; i++) { sum+=data[i]; } num[t++]=1.0*sum/(m-2); } int ss,tt=0; while(k--) { double max1=-1000.0; for(int i=0; i<t; i++) { if(num[i]>max1) { max1=num[i]; ss=i; } } num1[tt++]=max1; num[ss]=0; } for(int i=tt-1;i>0;i--) printf("%.3lf ",num1[i]); printf("%.3lf\n",num1[0]); return 0; }

24

#include<iostream> #include<algorithm> using namespace std; int sum[100005]; int main(){ int n; cin>>n; int s=0; for(int i=0;i<n;i++){ cin>>sum[i]; s+=sum[i]; } sort(sum+0,sum+n); int out=0,in=0; for(int i=0;i<n/2;i++){ in+=sum[i]; } for(int i=n-1;i>=n/2;i--){ out+=sum[i]; } printf("Outgoing #: %d\nIntroverted #: %d\nDiff = %d",n%2==0? n/2:n/2+1,n/2,out-in); return 0; }

25

#include<stdio.h> #include<stdlib.h> int cmp(const void *a,const void *b) //定义快排函数规则，这里即非升序 { return (*(long *)b > *(long *)a) ? 1 : -1; } int main() { int i, k, n, m, cnt = 0, flag = 1; long x, s[10] = {0}; scanf("%d %d", &n, &m); int len = m < n ? m : n; //判读数组的长度取m还是n（取小的那个） for(i = 0; i < len; i ++) { scanf("%ld", &s[i]); } qsort(s, len, sizeof(long), cmp); //调用快排函数 for(i = len; i < n; i ++) { scanf("%ld", &x); if(x > s[len-1]) { //如果当前输入的x大于数组最小的那个元素 for(k = 0; k < len; ++ k) { //遍历数组 if(s[k] < x) { //找到第一个s[k] < x的位置 int t; for(t = len-1; t > k; t --) { //k后面的元素全部往后移一个位置 s[t] = s[t-1]; } s[t] = x; //移动后，空出来的位置，即x插入的位置 break; //跳出循环 } } } } if(len >= 1) { printf("%ld", s[0]); } for(i = 1; i < len; i ++) { printf(" %ld", s[i]); } return 0; }

26

#include<iostream> #include<string> #include<map> #include<algorithm> using namespace std; struct student { string id;//考号 int kao;//考场 int score;//成绩 int rank;//在考场内的排名 int rankz;//总排名 }stu[30005]; bool cmp(student a,student b) { if(a.score ==b.score )//如果两人分数相同个，按考号递增输出 return a.id <b.id ; else return a.score >b.score ; } int main() { int n,cnt=0,s=0;//cnt来记录下标，s记录总数 cin>>n; for(int i=0;i<n;i++) { int k,st; cin>>k; s+=k; for(int j=0;j<k;j++) { stu[cnt].kao =i+1; cin>>stu[cnt].id >>stu[cnt].score ; cnt++; } st=s-k; //st表示这一个考场的第一个人在stu[]中起始下标，s表示末下标 sort(stu+st,stu+s,cmp);//这个处理非常重要 int p=1;//用来排名次 for(int i=st;i<s;i++) { if(stu[i].score ==stu[i-1].score&&i>=1 )//如果和前面一个人分数相同，则名次一样 stu[i].rank =stu[i-1].rank ; else stu[i].rank =p; p++;//记得要加1 } } sort(stu,stu+s,cmp);//对整个结构体数组进行排序 for(int i=0;i<s;i++) { if(stu[i].score ==stu[i-1].score&&i>=1 ) stu[i].rankz =stu[i-1].rankz ; else stu[i].rankz =i+1;//i是下标从0开始的，所以表示排名的时候要+1 } cout<<s<<endl; for(int i=0;i<s;i++) { cout<<stu[i].id <<' '<<stu[i].rankz<<' '<<stu[i].kao <<' '<<stu[i].rank <<endl; } }

r(int i=0; i<t; i++) { if(num[i]>max1) { max1=num[i]; ss=i; } } num1[tt++]=max1; num[ss]=0; } for(int i=tt-1;i>0;i–) printf("%.3lf “,num1[i]); printf(”%.3lf\n",num1[0]); return 0; }

### 24 ```c #include<iostream> #include<algorithm> using namespace std; int sum[100005]; int main(){ int n; cin>>n; int s=0; for(int i=0;i<n;i++){ cin>>sum[i]; s+=sum[i]; } sort(sum+0,sum+n); int out=0,in=0; for(int i=0;i<n/2;i++){ in+=sum[i]; } for(int i=n-1;i>=n/2;i--){ out+=sum[i]; } printf("Outgoing #: %d\nIntroverted #: %d\nDiff = %d",n%2==0? n/2:n/2+1,n/2,out-in); return 0; }

25

26

Processed: 0.022, SQL: 9