数据结构实验练习题

数据结构练习题

/*【问题描述】
有一个带头结点的无序单链表L（允许出现值域相同的结点），编写算法程序，删除值域相同的多余结点（值域相同的结点仅保留第一个结点），统计被删除结点的个数。
typedef int ElemType;
typedef struct LNode {  ElemType data;struct LNode *next;
}LNode,*LinkList;
【输入形式】
从标准输入读入数据。输入的第一行是正整数n，表示有n个结点；接下来的一行是n个结点的整数值。
【输出形式】
输出到标准输出。第一行输出被删除结点的个数，如果无结点被删除，则输出0；第二行输出删除值域相同结点后的结点序列。
【样例输入】
8
3 7 3 3 2 6 6 1
【样例输出】
3
3 7 2 6 1 */
#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
typedef int ElemType;
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode,*LinkList;void CreateList_L(LinkList &L,int n){
int i;LinkList p,q;L=(LinkList)malloc(sizeof(LNode));L->next=NULL;q=L;for(i=n;i>0;--i){p=(LinkList)malloc(sizeof(LNode));scanf("%d",&p->data);//p->next=L->next;L->next=p;p->next=NULL;q->next=p;q=p;}
}Status OutputList_L(LinkList L){LinkList p=L->next;if(!p) return ERROR;while(p){printf("%d ",p->data);p=p->next;}printf("\n");return OK;
}Status GetElem_L(LinkList &L,int i,ElemType &e){int j;LinkList p;p=L->next; j=1;while(p&&j<i){p=p->next; ++j;}if(!p||j>i) return ERROR;e=p->data;return OK;
}Status ListDelete_L(LinkList &L,int i,ElemType &e){LinkList p,q;int j;p=L; j=0;while(p->next&&j<i-1){p=p->next;++j;}if(!(p->next)||j>i-1) return ERROR;q=p->next;p->next=q->next;e=q->data;free(q);return OK;
}int main(void){LinkList L;int n,i,j,a=0,b=0,cnt=0;scanf("%d",&n);CreateList_L(L,n);for(i=0;i<n-cnt-1;i++){GetElem_L(L,i+1,a);for(j=i+1;j<n-cnt;){GetElem_L(L,j+1,b);if(a==b){ListDelete_L(L,j+1,b);cnt++;}else j++;}}printf("%d\n",cnt);OutputList_L(L);return 0;
}

/*有一个非空双链表L，设计一个算法删除所有值为x的结点。
【问题描述】
有一个非空双链表L，设计一个算法删除所有值为x的结点。
【输入形式】
输入数据为两行，第一行是输入数据个数，第二行是输入数据，第三行是x的值
【输出形式】
删除值为x后的序列，以空格分隔
【样例输入】
7
1 3 5 6 8 6 7
6
【样例输出】
1 3 5 8 7*/
#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int ElemType;
typedef int Status;
typedef struct LNode{ElemType data;struct LNode *llnode,*rlnode;
}LNode,*LinkList;void CreateList_L(LinkList &L,int n){int i;LinkList p,q;L=(LinkList)malloc(sizeof(LNode));L->llnode=L;L->rlnode=L;q=L;for(i=n;i>0;--i){p=(LinkList)malloc(sizeof(LNode));scanf("%d",&p->data);p->rlnode=L;p->llnode=q;q->rlnode=p;q=p;}
}Status OutputList_L(LinkList L){LinkList p=L->rlnode;if(!p) return ERROR;while(p!=L){printf("%d ",p->data);p=p->rlnode;}printf("\n");return OK;
}Status GetElem_L(LinkList &L,int i,ElemType &e){int j;LinkList p;p=L->rlnode; j=1;while(p&&j<i){p=p->rlnode; ++j;}if(!p||j>i) return ERROR;e=p->data;return OK;
}Status ListDelete_L(LinkList &L,ElemType e){LinkList p,q;p=L->rlnode; while(p!=L){if(p->data==e){p->llnode->rlnode=p->rlnode;p->rlnode->llnode=p->llnode;q=p;p=p->rlnode;free(q);}else p=p->rlnode;}return OK;
}int main(void){LinkList L;int n,x;scanf("%d",&n);CreateList_L(L,n);scanf("%d",&x);ListDelete_L(L,x);OutputList_L(L);return 0;
}

/*设计一个高效算法，将顺序表L中的所有元素逆置，要求算法的空间复杂度为O（1）。
【输入形式】两行，第一行是输入数据数量，第二行是线性表数据，元素之间用空格间隔。
【输出形式】输入线性表的逆序，元素之间用空格间隔
【样例输入】
5
1 2 3 4 5
【样例输出】
5 4 3 2 1
【样例说明】输入数据是整数列，数据间以空格分开。
【评分标准】必须使用顺序表存储元素，算法空间复杂度O（1），顺序表存储实现逆序。*/
#include<stdio.h>
#define MaxSize 50
typedef int ElemType;
typedef struct {ElemType data[MaxSize];int length;
}SqList;void InitList(SqList &L)
{L.length=0;
};void CreateList(SqList &L,int n){int i;for(i=0;i<n;i++)scanf("%d",&L.data[i]);L.length=n;
}int ListEmpty(SqList L){return(L.length==0);
}int ListLength(SqList L){return(L.length);
}void DispList(SqList L){int i;if(L.length==0)return;for(i=0;i<L.length;i++)printf("%d ",L.data[i]);
}int GetElem(SqList L,int i,ElemType &e){if(i<1||i>L.length)return 0;e=L.data[i-1];return 1;
}int LocateElem(SqList L,ElemType e){int i=1;while(i<=L.length&&L.data[i-1]!=e)i++;if(i<=L.length)return i;elsereturn 0;
}int ListInsert(SqList &L,int i,ElemType e){int j;if(i<1||i>L.length+1)return 0;for(j=L.length-1;j>=i-1;j--)L.data[j+1]=L.data[j];L.data[i-1]=e;++L.length;return 1;
}int ListDelete(SqList &L,int i,ElemType &e)
{int j;if(i<1||i>L.length)return 0;e=L.data[i-1];for(j=i-1;j<L.length-1;j++)L.data[j]=L.data[j+1];--L.length;return 1;
}int ListReverse(SqList &L){int tmp;for(int i=0;i<L.length/2;i++){tmp=L.data[i];L.data[i]=L.data[L.length-i-1];L.data[L.length-i-1]=tmp;}return 0;
}int main(void){int n;SqList L;InitList(L);scanf("%d",&n);CreateList(L,n);ListReverse(L);DispList(L);return 0;
}

/*【问题描述】给定一个链表，升序排列，要求删除其中的重复元素
【输入形式】一个链表
【输出形式】去重后的链表
【样例输入】1 2 3 3 3 4 5
【样例输出】1 2 3 4 5*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>typedef struct _Node {int value;struct _Node* next;
} Node, *List;void print_list (List list)
{Node* p = list->next;while (p) {printf("%d ", p->value);p = p->next;}
}void free_list (List list)
{Node* p = list->next, *q;while (p) {q =p;p = p->next;free(q);}
}void remove_duplicates (List list)
{Node *p,*q;p=list->next;q=p->next;while(q){if(q->value==p->value){p->next=q->next;free(q);q=p->next;}else{p=p->next;q=p->next;}}
}// new element will be appended to tail
List create_list ()
{List list = (Node*)malloc(sizeof(Node));list->next = NULL;int v;Node* prev = list;// sample input: 1 2 3 #while (scanf("%d", &v) > 0){Node* node = (Node*)malloc(sizeof(Node));node->value = v;node->next = NULL;prev->next = node;prev = node;}return list;
}int main (int argc, char** argv)
{List list = create_list();remove_duplicates(list);print_list(list);free_list(list);return 0;
}

/*【问题描述】假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的值，否则输出-1
【输入形式】第一个数是k，后面的依次是链表元素
【输出形式】找到的值
【样例输入】1 2 3 4 5 6 7 8 9 0
【样例输出】0
【样例说明】倒数第1个数是0*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>typedef struct _Node {int value;struct _Node* next;
} Node, *List;// new element will be appended to tail
List create_list ()
{List list = (Node*)malloc(sizeof(Node));list->next = NULL;int v;Node* prev = list;// sample input: 1 2 3 while (scanf("%d", &v) > 0){Node* node = (Node*)malloc(sizeof(Node));node->value = v;node->next = NULL;prev->next = node;prev = node;}return list;
}void print_rev_kth (List list, int k)
{Node *prior=list->next;Node *node=list->next;for(int i=0;i<k&&prior!=NULL;i++){prior=prior->next;}while(node!=NULL&&prior!=NULL){node=node->next;prior=prior->next;}if(node!=NULL){printf("%d\n",node->value);}
}int main (int argc, char** argv)
{int k;scanf("%d", &k);List list = create_list();print_rev_kth(list, k);return EXIT_SUCCESS;
}

/*【问题描述】
假设表达式中允许包含圆括号和方括号两种括号，括号嵌套的顺序随意，设计算法判别一个表达式的圆括号和方括号是否正确配对。
【输入形式】
一个以@为结尾的表达式
【输出形式】
若括号正确配对，则输出圆括号和方括号的对数和；否则输出no
【样例输入】(a+b)/[(c+d)-3]@
【样例输出】3
【样例说明】共有三对括号，输出3 */
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef int Status;
typedef char SElemType;
//存储空间初始分配量
//存储空间分配增量
typedef struct{SElemType *base;//在栈构造之前和销毁之后，base的值为NULLSElemType *top;//栈顶指针int stacksize;//当前已分配的存储空间，以元素为单位
}SqStack;Status InitStack(SqStack &S){
//构造一个空栈SS.base =(SElemType*)malloc(STACK_INIT_SIZE* sizeof(SElemType));if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;
}//InitStackStatus StackEmpty(SqStack &S){if(S.top==S.base)return TRUE;elsereturn FALSE;
}//StackEmptyStatus GetTop(SqStack &S, SElemType &e){//若栈不空，则用e返回s的栈顶元素，并返回OK:否则返回ERRORif(S.top ==S.base) return ERROR;else e=*S.top;return OK;
}//GetTopStatus Push(SqStack &S, SElemType e){//插入元素e为新的栈顶元素if(S.top-S.base >=S.stacksize){//栈满，追加存储空间S.base = (SElemType* )realloc(S.base,(S.stacksize + STACKINCREMENT)* sizeof(SElemType));if (!S.base) exit(OVERFLOW);//存储分配失败S.top=S.base + S.stacksize;S.stacksize+=STACKINCREMENT;}S.top++;*S.top=e;S.stacksize++;return OK;
}//Push;Status Pop(SqStack &S,SElemType &e){//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK;否则返回ERRORif(S.top==S.base) return ERROR;else{e=*S.top;S.top--;S.stacksize--;return OK;}
}//PopStatus Correct(SElemType str[]){//使用运算符栈S，当遇到'('、'['时进栈，遇到')'、']'出栈并判断出栈元素是否为相应的符号，若是则继续下一个，否则算法结束SqStack S;InitStack(S);//构造空栈int i,state=1,sum=0;SElemType e;for(i=0;str[i]!='\0';i++){switch(str[i]){case '(':Push(S,str[i]);state++;break;case '[':Push(S,str[i]);state++;break;case ')':if(*S.top=='('){Pop(S,e);state--;sum++;}else{Push(S,str[i]);state++;}break;case ']':if(*S.top=='['){Pop(S,e);state--;sum++;}else{Push(S,str[i]);state++;}break;default:break;}if(!state)break;}if(StackEmpty(S)&&state==1)return sum;elsereturn ERROR;
}//Correctint main(void){SElemType str[100];char ch;int i=0,sum;while((ch=getchar())!='@'){if(ch=='('||ch==')'||ch=='['||ch==']')str[i++]=ch;}sum=Correct(str);if(Correct(str)==ERROR)printf("no\n");elseprintf("%d\n",sum);return 0;
}

/*【问题描述】遍历数组删除其中的重复元素，要求时间复杂度为O(n)，除题目要求数组外，不另设新数组。
【输入形式】从标准输入读入数据。输入少于10个英文字母字符，以$结束，字符之间用空格分隔。
【输出形式】输出到标准输出。输出删除后剩余的元素，输出时每个英文字母后面跟一个空格。
【样例输入1】a p o k p a a w $
【样例输出1】a p o k w
【样例输入2】A A A b b b b b $
【样例输出2】A b*/
#include<stdio.h>
#include<stdlib.h>
typedef int Status;int main(void){char ch;int a[30]={0};while((ch=getchar())!='$'){getchar();if(a[ch-'a']==0){printf("%c ",ch);a[ch-'a']=1;}else continue;}
}

/*【问题描述】输入一个后缀表达式，求这个表达式的值。输入的数字皆为大于或等于零的整数，涉及的运算只有加法、减法及乘法。数字之间用空格隔开。表达式以#结束
【输入形式】以#为结束标志的后缀表达式
【输出形式】后缀表达式的计算结果
【样例输入】10 5 2 3 * - 2 * + #
【样例输出】8
【样例说明】表达式以#结尾*/
#include<iostream>
#include<cstdlib>
#include<stack>
#include<ctype.h>
using namespace std;
stack<int> s;int main(void){char ch;int num=0,x,y,p=-1;//p=1时为数字，p=0时为运算符while((ch=getchar())!='#'){if(isdigit(ch)){num*=10;num+=ch-'0';p=1;}else if(isspace(ch)){if(p==1){s.push(num);num=0; p=-1; }else continue;}else{y=s.top();s.pop();x=s.top();s.pop();switch(ch){case '+':s.push(x+y);break;case '-':s.push(x-y);break;case '*':s.push(x*y);break;case '/':s.push(x/y);break;default:break;}p=0;}}printf("%d\n",s.top());return 0;
}

/*给出一个堆栈的输入序列，试判断一个序列是否能够由这个堆栈输出。如果能，返回总的出栈次数，如果不能，返回0。序列的输入及输出都是从左往右。（输入输出序列皆为整数且没有重复的数字，如果一个数字在输入序列中没有出现，那么其在输出序列中也不会出现）
【输入形式】第一行为输入序列的长度，第二行为输入序列的数字；第三行为输出序列的数字。输入数据以空格隔开。
【输出形式】如果是一个出栈序列，则返回总的出栈次数， 否则返回0
【样例输入】
5 
1 2 3 4 5
1 2 3 4 5
【样例输出】5
【样例说明】第一行输入的是序列的长度，第一行输入的1 2 3 4 5 是输入序列，第三行是输出序列，以空格隔开，输出的总的出栈次数。*/
#include <iostream>
using namespace std;
int main() {int n, top = 0, t = 1, ans = 0;cin >> n;int *a = new int[n + 10], *stk = new int[n + 10], *pop_t = new int[n + 10];  // 申请空间,a存原数组,stk存栈,pop_t存弹出序列for (int i = 1; i <= n; ++i) cin >> a[i];    // 读入原数组for (int i = 1; i <= n; ++i) cin >> pop_t[i];    // 读入弹出序列for (int i = 1; i <= n; ++i) {stk[++top] = a[i];  while (top != 0 && stk[top] == pop_t[t]) {  // 栈顶元素与弹出序列元素相同,弹出栈顶元素top--, t++, ans++;}}if (top != 0) {  // 栈中还有元素未弹出cout << 0 << "\n";} else {cout << ans << "\n";}return 0;
}

/*对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数*/
#include <iostream>
using namespace std;
int main() {int n, t = 0;int *res = new int[101];    // 申请数组空间，存放结果cin >> n;while(n<=0){printf("Error!\n");cin>>n;}while (n != 0) {res[++t] = n % 8;    // 取余数n /= 8;    // 除以8}for (int i = t; i >= 1; --i) cout << res[i];    // 倒序输出cout << "\n";return 0;
}

/*【问题描述】假设一算术表达式中包括三种括号：圆括号（和）, 方括号[和], 花括号{和}，且三种括号可按意次序嵌套使用，试编写程序判定输入的表达式所含的括号是否正确配对出现。若匹配，则返回1，否则返回0。
【输入形式】含括号的算数表达式
【输出形式】若表达式中的括号正确配对，则输出1。否则，输出0。
【样例输入】3+(44*[5-{6*[7*(45-10)]}])
【样例输出】1
【样例说明】判断括号是否匹配涉及两方面的问题，一是对左右括号的出现次数的判定，二是对不同括号的出现次序的判定。*/
#include <iostream>
#include<ctype.h>
using namespace std;
int main() {char str[1001];int top=0;char ch;while((ch=getchar())!='\n'){if(ch=='('||ch==')'||ch=='['||ch==']'||ch=='{'||ch=='}'){if(top==0){if(ch=='('||ch=='['||ch=='{') str[top++]=ch;else{printf("0\n");return 0;}}else{switch(ch){case '(':case '[':case '{':str[top++]=ch;break;case ')':if(str[top-1]=='('){str[top-1]='\0';top--;}else str[top++]=ch;break;case ']':if(str[top-1]=='['){str[top-1]='\0';top--;}else str[top++]=ch;break;case '}':if(str[top-1]=='{'){str[top-1]='\0';top--;}else str[top++]=ch;break;default:break;}}}else continue;}if(top==0) printf("1\n");else printf("0\n");return 0;
}

/*【问题描述】输入一个中缀表达式，表达式中有+、-、*、/四种运算以及（、），表达式中的其他符号为大写的字母。实现一个算法，得到相应的后缀表达式。
【输入形式】一个式子的中缀表达式，以#结束
【输出形式】相应的后缀表达式 
【样例输入】A*(B-C)/D+E#
【样例输出】ABC-*D/E+*/
#include <iostream>
using namespace std;
int main() {// +:-1 *:-2 -:-3 /:-4 (:-5int n = 0, top1 = 0, top2 = 0;char str[1001];int stk1[1001], stk2[1001]; // 操作栈和结果栈while ((str[n++] = getchar()) != '#');  // 读入表达式n -= 1;for (int i = 0; i < n; ++i) {if (str[i] >= 'A' && str[i] <= 'Z') {   // 数值入栈stk2[++top2] = str[i];continue;}if (str[i] == '+' || str[i] == '-') {while (top1 != 0 && stk1[top1] != -5) { // 优先级判断(如果为-5(左括号)，则不弹出)stk2[++top2] = stk1[top1];top1--;}stk1[++top1] = (str[i] == '+' ? -1 : -3);}if (str[i] == '*' || str[i] == '/') {while (top1 != 0 && stk1[top1] != -5 && stk1[top1] != -1 &&stk1[top1] != -3) {  // 优先级判断(如果为-1(+)或-3(-)或-5(左括号)，则不弹出)stk2[++top2] = stk1[top1];top1--;}stk1[++top1] = (str[i] == '*' ? -2 : -4);}if (str[i] == '(') stk1[++top1] = -5;    // 左括号入栈if (str[i] == ')') {while (top1 != 0 && stk1[top1] != -5) { // 弹出左括号及其对应的右括号stk2[++top2] = stk1[top1];top1--;}top1--;}}while (top1 != 0) {  // 弹出剩余操作符stk2[++top2] = stk1[top1];top1--;}for (int i = 1; i <= top2; ++i) {    // 输出结果if (stk2[i] >= 0) cout << (char)stk2[i];if (stk2[i] == -1) cout << "+";if (stk2[i] == -2) cout << "*";if (stk2[i] == -3) cout << "-";if (stk2[i] == -4) cout << "/";}cout << "\n";return 0;
}

/*【问题描述】字符串删除操作，将第一行字符串中包含第二行字符串的子串全部删除。
【输入形式】两行，第一行一个字符串，第二行一个字符串
【输出形式】一行：删除子串后的字符串
【样例输入】
1234567845690
456
【样例输出】1237890*/
#include<stdio.h>
#include<stdlib.h>
#define MAXSTRLEN 255
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef unsigned char SString[MAXSTRLEN+1];//0号单元存放串的长度
typedef int Status;Status Index(SString S,SString T,int pos){int i=pos;int j=1;while(i<=S[0]&&j<=T[0]){if(S[i]==T[j]){++i;++j;}else{i=i-j+2;j=1;}}if(j>T[0]) return i-T[0];else return 0;
}Status StrDelete(SString &S,int pos,int len){int i;if(pos<1||pos+len-1>S[0]||len<0) return FALSE;for(i=pos+len;i<=S[0];i++){S[i-len]=S[i];}S[0]-=len;return 0;
}int main(void){SString a,b;int i=1,j=1,pos;char ch;while((ch=getchar())!='\n'){a[i++]=ch;}a[0]=i-1;while((ch=getchar())!='\n'){b[j++]=ch;}b[0]=j-1;while((pos=Index(a,b,1))!=0){StrDelete(a,pos,b[0]);}for (i = 1; i <= a[0]; i++){printf("%c", a[i]);}printf("\n");return 0;
}

/*【问题描述】字符串删除操作，将第一行字符串中包含第二行字符串的子串全部删除。
【输入形式】两行，第一行一个字符串，第二行一个字符串
【输出形式】一行：删除子串后的字符串
【样例输入】
1234567845690
456
【样例输出】1237890*/
#include<stdio.h>
#include<string.h>
int main()
{char s1[100];gets(s1);char s2[100];gets(s2);int len1,len2;//字符串长度len1=strlen(s1);len2=strlen(s2);int i,j,k;//循环变量int flag=1;//控制while循环int f;//判断是否删除while(flag)for(i=0; i<len1; i++){flag=0;//默认s1中不存在符合要求的子串，若遍历完后flag仍为0则程序结束 if(s1[i]==s2[0])//寻找与子串第一个字母相同的字符 {f=1;//默认从第i个字符开始的子串符合要求 for(j=i,k=0; k<len2; j++,k++)//检验是否符合要求if(s1[j]!=s2[k])//若不符合要求，则f=0,退出for循环的检验{f=0;  break;}if(f)//若f不为0，则进行删除操作{flag=1;//即存在符合要求的子串，将flag=1以便再次检查 for(; j<len1; j++,i++)//将后面的字符逐一替换到前面 s1[i]=s1[j];for(; i<len1; i++)//对后续多余的字符串进行清空 s1[i]='\0';break;//重新开始for循环，从第一位开始寻找 }}len1=strlen(s1);//重新计算s1的长度，此步影响的用时很小，可有可无}puts(s1);return 0; 
}

/*【问题描述】假设二叉树采用二叉链存储结构存储。设计一个算法，输出从每个叶子结点到根结点的逆路径
【输入形式】广义表表示的二叉树，结点元素类型为字符，例如：a( b( c ( d, e ) ), f( g, h( i, j) ) )
【输出形式】从左至右，从上至下，依次打印每一个叶子节点到根节点的逆路径，元素间以空格隔开。每一叶子结点单独输出一行。
【样例输入】a(b(c(d,e)),f(g,h(i,j))), 字符中间不含有空格
【样例输出】
d c b a
e c b a
g f a
i h f a 
j h f a
【样例说明】叶子节点的输出顺序按中序遍历顺序依次输出 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 定义二叉树的节点结构
typedef struct TreeNode {char val;struct TreeNode *left;struct TreeNode *right;
} TreeNode;// 动态创建一个新的TreeNode
TreeNode* createTreeNode(char val) {TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));node->val = val;node->left = NULL;node->right = NULL;return node;
}// 辅助函数，用于将广义表字符串转换为二叉树
TreeNode* strToTree(const char** str) {if(**str == '\0' || **str == ',') return NULL;TreeNode* root = createTreeNode(*((*str)++));if(*(*str) == '(') {(*str)++;root->left = strToTree(str);if(*(*str) == ',') {(*str)++;root->right = strToTree(str);}(*str)++;}return root;
}// 递归函数，用于收集从叶子节点到根节点的路径
void collectPaths(TreeNode* node, char* path, int pathIndex) {if (node == NULL) return;// 将当前节点加入路径path[pathIndex] = node->val;pathIndex++;// 如果是叶子节点，打印路径if (node->left == NULL && node->right == NULL) {for (int i = pathIndex - 1; i >= 0; i--) {printf("%c ", path[i]);}printf("\n");} else {// 否则，继续递归左右子树collectPaths(node->left, path, pathIndex);collectPaths(node->right, path, pathIndex);}
}// 释放二叉树内存
void deleteTree(TreeNode* node) {if (node == NULL) return;deleteTree(node->left);deleteTree(node->right);free(node);
}int main() {char input[1024];scanf("%s", input);const char* str = input;TreeNode* root = strToTree(&str);char path[1024]; // 假设路径长度不会超过1024collectPaths(root, path, 0);// 释放二叉树内存deleteTree(root);return 0;
}

/*【问题描述】假设二叉树采用二叉链存储结构存储。设计一个算法，判断一棵二叉树是否为对称同构。所谓对称同构是指二叉树中任何结点的左、右子树结构是相同的。
【输入形式】广义表表示的二叉树，结点元素类型为字符，，例如：a( b( c ( d, e ) ), f( g, h( i, j) ) )
【输出形式】true 或者false
【样例输入】A(B,C)，字符串内没有空格
【样例输出】true*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 定义二叉树的节点结构
typedef struct TreeNode {char val;struct TreeNode *left;struct TreeNode *right;
} TreeNode;// 动态创建一个新的TreeNode
TreeNode* createTreeNode(char val) {TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));node->val = val;node->left = NULL;node->right = NULL;return node;
}// 辅助函数，用于将广义表字符串转换为二叉树
TreeNode* strToTree(const char** str) {if(**str == '\0' || **str == ',') return NULL;TreeNode* root = createTreeNode(*((*str)++));if(*(*str) == '(') {(*str)++;root->left = strToTree(str);if(*(*str) == ',') {(*str)++;root->right = strToTree(str);}(*str)++;}return root;
}// 递归函数，用于判断两棵树是否对称同构
int isSymmetric(TreeNode* left, TreeNode* right) {if (left == NULL && right == NULL) return 1;if (left == NULL || right == NULL) return 0;//if (left->val != right->val) return 0;return isSymmetric(left->left, right->right) && isSymmetric(left->right, right->left);
}// 判断二叉树是否对称同构
int isSymmetricTree(TreeNode* root) {if (root == NULL) return 1;return isSymmetric(root->left, root->right);
}// 释放二叉树内存
void deleteTree(TreeNode* node) {if (node == NULL) return;deleteTree(node->left);deleteTree(node->right);free(node);
}int main() {char input[1024];scanf("%s", input);const char* str = input;TreeNode* root = strToTree(&str);int result = isSymmetricTree(root);printf("%s\n", result ? "true" : "false");// 释放二叉树内存deleteTree(root);return 0;
}

/*【问题描述】给定一颗二叉树，要求从下至上按层遍历二叉树，每层的访问顺序是从左到右，每一层单独输出一行。
【输入形式】广义表表示的二叉树，结点元素类型为整型，且都大于0，例如：1( 2( 3 ( 4, 5 ) ), 6( 7, 8( 9, 10 ) ) )
【输出形式】从下至上，打印每一层的结点元素值，元素间以空格隔开。每层的访问顺序是从左到右，每一层单独输出一行。
【样例输入】 1(2(3(4,5)),6(7,8(9,10)))，字符串内没有空格
【样例输出】4 5 9 103 7 82 61*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct BiTNode
{int data;int cs;//记录层数struct BiTNode *lchild ,*rchild;
}BiTNode,*BiTree;
typedef struct
{BiTree *base;BiTree *top;int stacksize;
}SqStack;typedef struct QNode
{BiTree data;struct QNode *next;
}QNode,*QueuePtr;typedef struct
{QueuePtr front;QueuePtr rear;    
}LinkQueue;int InitQueue(LinkQueue &Q)
{Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front) exit(-1);Q.front->next=NULL;return 1;
}
int EnQueue(LinkQueue&Q, BiTree e)
{QueuePtr p=(QueuePtr)malloc(sizeof(QNode));if(!p) exit(-2);p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;return 1;
}
int DeQueue(LinkQueue &Q,BiTree &e)
{if(Q.front==Q.rear) return -1;QueuePtr p=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear==p) Q.rear=Q.front;free(p);return 1;
}int InitStack(SqStack &S)
{S.base=( BiTree*)malloc(STACK_INIT_SIZE*sizeof(BiTree));if(!S.base) exit(-1);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return 1;
}int Push(SqStack &S,BiTree e)
{if(S.top-S.base>=S.stacksize){S.base=(BiTree*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(BiTree));if(!S.base) exit(-1);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;return 1;
}
int Pop(SqStack&S,BiTree &e)
{if(S.top==S.base)return -1;e=*--S.top;return 1;
}
int GetTop(SqStack S,BiTree &e)
{if(S.top==S.base) return 0;e=*(S.top-1);return 1;
}
void CreatBiNode(BiTree &T,int integer,int cs)
{T=(BiTNode *)malloc(sizeof(BiTNode));if(T==NULL) exit(-1);T->data=integer;T->cs=cs;T->rchild=NULL;T->lchild=NULL;
}
//字符是1，数字是0
int ShuOrFu(char c)
{if((c=='(')||(c==')')||(c==','))return 1;elsereturn 0;
}
void CreatBiTree(BiTree &T,char *s)
{int integer,cs=1;SqStack S;   //用栈来记录InitStack(S);//根节点integer=s[0]-'0';CreatBiNode(T,integer,cs);BiTree p=T,q=NULL;  //辅助char c;for(int i=1;i<strlen(s)-1;i++){if((ShuOrFu(s[i])==0)&&(ShuOrFu(s[i+1])==1))integer=s[i]-'0';    if(ShuOrFu(s[i])==1){    c=s[i]; if(c=='('||c==',')continue;}    if((ShuOrFu(s[i])==0)&&(ShuOrFu(s[i+1])==0)){    integer=(s[i]-'0')*10+(s[i+1]-'0');i=i+1;}if(c=='('){    cs++;CreatBiNode(p->lchild,integer,cs);GetTop(S,q);if(q!=p)Push(S,p);    p=p->lchild;}else if(c==')'){Pop(S,p);cs--;}else if(c==','){    Pop(S,p);CreatBiNode(p->rchild,integer,cs);Push(S,p->rchild);p=p->rchild;}else break;}
}void ACTraverse(BiTree T)
{LinkQueue Q;InitQueue(Q);BiTree a[100];EnQueue(Q,T);int i=0;while(Q.front!=Q.rear){//printf("%d ",Q.front->data->data);if(Q.front->next->data->rchild!=NULL)EnQueue(Q,Q.front->next->data->rchild);if(Q.front->next->data->lchild!=NULL)EnQueue(Q,Q.front->next->data->lchild);DeQueue(Q,a[i]);i++;}int k=a[i-1]->cs;for(int j=i-1;j>=0;j--){if(k!=a[j]->cs)printf("\n");printf("%d ",a[j]->data);k=a[j]->cs;}
}
void PreOrder(BiTree T)
{if(T){printf("%d ",T->data);PreOrder(T->lchild);PreOrder(T->rchild);}
}int main()
{BiTree T=NULL;    char s[100];gets(s);CreatBiTree(T,s);//PreOrder(T);ACTraverse(T);return 0;
}

/*已知一个二叉树的中序遍历序列和后序遍历序列，求这棵树的前序遍历序列
【输入形式】一个树的中序遍历序列 该树后序遍历序列，中间用空格分开。输入序列中仅含有小写字母,且没有重复的字母
【输出形式】一个树的前序遍历序列
【样例输入】dbeafcg debfgca
【样例输出】abdecfg*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MAX_SIZE 26char preOrder[MAX_SIZE]; // 存储前序遍历序列
int preIndex = 0; // 前序遍历序列的当前索引// 根据中序和后序遍历序列重建二叉树，并生成前序遍历序列
void buildTree(const char* inOrder, int inStart, int inEnd, const char* postOrder, int postStart, int postEnd) {if (inStart > inEnd) return;// 访问根节点，即后序遍历的最后一个元素char root = postOrder[postEnd];preOrder[preIndex++] = root;int rootIndex = -1;// 在中序遍历中找到根节点的位置for (int i = inStart; i <= inEnd; i++) {if (inOrder[i] == root) {rootIndex = i;break;}}// 重建左子树int leftTreeSize = rootIndex - inStart;buildTree(inOrder, inStart, rootIndex - 1, postOrder, postStart, postStart + leftTreeSize - 1);// 重建右子树buildTree(inOrder, rootIndex + 1, inEnd, postOrder, postStart + leftTreeSize, postEnd - 1);
}int main() {char inOrder[MAX_SIZE];char postOrder[MAX_SIZE];// 读取输入scanf("%s %s", inOrder, postOrder);// 根据中序和后序遍历序列重建二叉树，并生成前序遍历序列buildTree(inOrder, 0, strlen(inOrder) - 1, postOrder, 0, strlen(postOrder) - 1);// 输出前序遍历序列for (int i = 0; i < preIndex; i++) {printf("%c", preOrder[i]);}printf("\n");return 0;
}

/*【问题描述】假设一个带权有向图采用邻接表存储，设计求源点v到其他顶点最短路径的Dijkstra算法。
【输入形式】第一行顶点个数n,边数，第二行到第n+1行是邻接矩阵
【输出形式】从顶点0依次输出到其它每个顶点的最短路径序列
【样例输入】
7 12
0 4 6 6 32767 32767 32767
32767 0 1 32767 7 32767 32767
32767 32767 0 32767 6 4 32767
32767 32767 2 0 32767 5 32767
32767 32767 32767 32767 0 32767 6
32767 32767 32767 32767 1 0 8
32767 32767 32767 32767 32767 32767 0 
【样例输出】
4 5 6 10 9 16
【样例说明】
数字32767代表∞，说明两个顶点不相连*/
#include<iostream>
using namespace std;
const int MAX = 32767;class Dijkstra {
private:int vexnum;int arcnum;bool* in_s;int* D;int** g;public:void create();void shortest_path();};void Dijkstra::create()
{cin >> vexnum >> arcnum;in_s = new bool[vexnum]();D = new int[vexnum];g = new int* [vexnum];;for (int i = 0; i < vexnum; i++) {g[i] = new int[vexnum];for (int j = 0; j < vexnum; j++) {g[i][j] = MAX;}}int temp;for (int i = 0; i < vexnum; i++) for (int j = 0; j < vexnum; j++) {cin >> temp;if (temp != 0 && temp != MAX)g[i][j] = temp;}for (int i = 0; i < vexnum; i++) {D[i] = g[0][i];}
}void Dijkstra::shortest_path()
{in_s[0] = true;for (int v = 0; v < vexnum-1; v++) {int j = 0;while (in_s[j])j++;for (int i = j + 1; i < vexnum; i++)if (!in_s[i] && D[i] < D[j])j = i;in_s[j] = true;for (int k = 0; k < vexnum; k++)if (!in_s[k] && (D[j] + g[j][k] < D[k]))D[k] = D[j] + g[j][k];}cout << endl;for (int i = 0; i < vexnum; i++) {if (D[i] != MAX)cout << D[i] << " ";}
}int main() {Dijkstra d;d.create();d.shortest_path();
}

/*【问题描述】
给定n个村庄之间的交通图。若村庄i与村庄j之间有路可通，则将顶点i与顶点j之间用边连接，边上的权值wij表示这条道路的长度。现打算在这n个村庄中选定一个村庄建一所医院，设计一个算法求出该医院应建在哪个村庄才能使距离医院最远的村庄到医院的路程最短。
【输入形式】
第一行顶点个数n，边的个数。第二行到n+1行邻接矩阵
【输出形式】
村庄的编号，从0开始
【样例输入】
5 10
0 13 32767 4 32767 
13 0 15 32767  5
32767  32767 0 12 32767 
4 32767 12 0 32767 
32767 32767 6 3 0
【样例输出】
3
【样例说明】
32767表示两个顶点不连接，是∞*/#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX_N 100// Floyd算法求最短路径
void floyd(int graph[][MAX_N], int n) {int i, j, k;for (k = 0; k < n; k++) {for (i = 0; i < n; i++) {for (j = 0; j < n; j++) {if (graph[i][k]!= 32767 && graph[k][j]!= 32767) {if (graph[i][j] > graph[i][k] + graph[k][j]) {graph[i][j] = graph[i][k] + graph[k][j];}}}}}
}// 找到距离每个顶点最远的距离
void findFarthest(int graph[][MAX_N], int n, int *max_distances) {int i, j;for (i = 0; i < n; i++) {int max_dist = 0;for (j = 0; j < n; j++) {if (graph[j][i] > max_dist) {max_dist = graph[j][i];}}max_distances[i] = max_dist;}
}// 找到距离最远村庄路程最短的顶点
int findBestVertex(int *max_distances, int n) {int min_max_distance = INT_MAX;int best_vertex = 0;for (int i = 0; i < n; i++) {if (max_distances[i] < min_max_distance) {min_max_distance = max_distances[i];best_vertex = i;}}return best_vertex;
}int main() {int n, m;int graph[MAX_N][MAX_N];scanf("%d %d", &n, &m);//读取邻接矩阵for(int i=0;i<n;i++){for(int j=0;j<n;j++){scanf("%d",&graph[i][j]);}}// 使用Floyd算法求最短路径floyd(graph, n);// 找到距离每个顶点最远的距离int max_distances[MAX_N];findFarthest(graph, n, max_distances);// 找到距离最远村庄路程最短的顶点int best_vertex = findBestVertex(max_distances, n);printf("%d", best_vertex);return 0;
}

/*【问题描述】假设图采用邻接矩阵存储。自由树(即无环连通图)T=(V，E)的直径是树中所有点对点间最短路径长度的最大值，即T的直径定义为MAX d(u,v)(u,v∈V)，这里d(u,v)表示顶点u到顶点v的最短路径长度(路径长度为路径中包含的边数)。设计一个算法求T的直径
【输入形式】第一行顶点个数n，边的个数。第二行到n+1行邻接矩阵
【输出形式】T的直径
【样例输入】
6 5
0 2 0 0 0 0
2 0 4 0 12 5
0 4 0 2 0 0
0 0 2 0 0 0 
0 12 0 0 0 0
0 5 0 0 0 0
【样例输出】18 */
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>#define MAX_N 100
#define INF INT_MAX// Floyd算法求最短路径
void floyd(int graph[][MAX_N], int n) {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] != INF && graph[k][j] != INF && graph[i][j] > graph[i][k] + graph[k][j]) {graph[i][j] = graph[i][k] + graph[k][j];}}}}
}// 找到图中最短路径的最大值
int findMax(int graph[][MAX_N], int n) {int max = -1;for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (i != j && graph[i][j] != INF && graph[i][j] > max) {max = graph[i][j];}}}return max;
}int main() {int n, m;int graph[MAX_N][MAX_N];scanf("%d %d", &n, &m);for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (i == j) {graph[i][j] = 0;} else {graph[i][j] = INF; }}}for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {scanf("%d", &graph[i][j]);if (graph[i][j] == 0 && i != j) {graph[i][j] = INF;}}}floyd(graph, n);int max = findMax(graph, n);printf("%d\n", max);return 0;
}

/*【问题描述】设计一个算法，判断一棵二叉排序树bt是否为平衡的。
【输入形式】两行，第一行是数据个数，第二行是输入数据
【输出形式】true或者false，如果输入数据构成的二叉树是平衡的，输出true, 否则，输出false
【样例输入】
9
5 2 3 4 1 8 6 7 9
【样例输出】true*/
#include <stdio.h>
#include <stdlib.h>// 二叉树节点结构体
typedef struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;
} TreeNode;// 插入节点到二叉排序树
TreeNode* insert(TreeNode* root, int val) {if (root == NULL) {TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));newNode->val = val;newNode->left = NULL;newNode->right = NULL;return newNode;}if (val < root->val) {root->left = insert(root->left, val);} else if (val > root->val) {root->right = insert(root->right, val);}return root;
}// 计算树的高度
int height(TreeNode* root) {if (root == NULL) return 0;int leftHeight = height(root->left);int rightHeight = height(root->right);return (leftHeight > rightHeight? leftHeight : rightHeight) + 1;
}// 判断二叉树是否平衡
int isBalanced(TreeNode* root) {if (root == NULL) return 1;int leftHeight = height(root->left);int rightHeight = height(root->right);if (abs(leftHeight - rightHeight) > 1) return 0;return isBalanced(root->left) && isBalanced(root->right);
}// 释放二叉树内存
void freeTree(TreeNode* root) {if (root == NULL) return;freeTree(root->left);freeTree(root->right);free(root);
}int main() {int n;scanf("%d", &n);TreeNode* root = NULL;for (int i = 0; i < n; i++) {int val;scanf("%d", &val);root = insert(root, val);}if (isBalanced(root)) {printf("true\n");} else {printf("false\n");}freeTree(root);return 0;
}

/*【问题描述】设计一个递归算法，从大到小输出二叉排序树bt中所有值不小于k的关键字。
【输入形式】三行，第一行是数据个数，第二行是输入数据，第三行是关键字k的值
【输出形式】从大到小排列的序列，以空格分隔
【样例输入】
9
5 2 3 4 1 8 6 7 9
5
【样例输出】9 8 7 6 5*/
#include <stdio.h>
#include <stdlib.h>// 二叉树节点结构体
typedef struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;
} TreeNode,*Tree;// 插入节点到二叉排序树
TreeNode* insert(TreeNode* root, int val) {if (root == NULL) {TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));newNode->val = val;newNode->left = NULL;newNode->right = NULL;return newNode;}if (val < root->val) {root->left = insert(root->left, val);} else if (val > root->val) {root->right = insert(root->right, val);}return root;
}void findKey(Tree &root,int key){if(root==NULL){return;}if(root->right!=NULL){findKey(root->right,key);}if(root->val>=key){printf("%d ",root->val);}if(root->left!=NULL){findKey(root->left,key);}
}int main(void){int n,k;scanf("%d", &n);Tree root = NULL;for (int i = 0; i < n; i++) {int val;scanf("%d", &val);root = insert(root, val);}scanf("%d",&k);findKey(root,k);return 0;
}

/*【问题描述】对于二叉排序树bt，设计一个算法，删除其中以关键字k为根节点的子树中所有关键字小于k的结点。
【输入形式】三行，第一行是数据个数，第二行是输入数据，第三行是关键字k的值
【输出形式】以广义表形式输出二叉排序树
【样例输入】
9
5 2 3 4 1 8 6 7 9
2
【样例输出】5(2(,3(,4)),8(6(,7),9))*/
#include <stdio.h>
#include <stdlib.h>// 二叉树节点结构体
typedef struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;
} TreeNode,*Tree;// 插入节点到二叉排序树
TreeNode* insert(TreeNode* root, int val) {if (root == NULL) {TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));newNode->val = val;newNode->left = NULL;newNode->right = NULL;return newNode;}if (val < root->val) {root->left = insert(root->left, val);} else if (val > root->val) {root->right = insert(root->right, val);}return root;
}void deleteKey(Tree &root,int key){if(root==NULL){return;}if(root->val==key){root->left=NULL;return;}if(root->left!=NULL) deleteKey(root->left,key);if(root->right!=NULL)deleteKey(root->right,key);
}void coutTree(Tree root){if(root==NULL)return;printf("%d",root->val);if(root->left!=NULL||root->right!=NULL) printf("(");else return;coutTree(root->left);printf(",");coutTree(root->right);printf(")");
}int main(void){int n,k;scanf("%d", &n);Tree root = NULL;for (int i = 0; i < n; i++) {int val;scanf("%d", &val);root = insert(root, val);}scanf("%d",&k);deleteKey(root,k);coutTree(root);return 0;
}

/*【问题描述】设计一个算法，判断一个数据序列R[1..n]是否构成一个大根堆
【输入形式】两行，第一行是数据个数，第二行是数据序列
【输出形式】true 或者false,如果是大根堆，输出true,否则，输出false
【样例输入】
9
8 7 6 5 4 3 2 1 0
【样例输出】true*/
#include<stdio.h>
#include<stdlib.h>
bool isMaxHeap(int *arr,int n){for(int i=n/2-1;i>=0;i--){int leftChild=2*i+1;int rightChild=2*i+2;if(leftChild<n&&arr[leftChild]>arr[i]) return false;if(rightChild<n&&arr[rightChild]>arr[i])return false;}return true;
}
int main(void){int n;scanf("%d",&n);int arr[n];for(int i=0;i<n;i++){scanf("%d",&arr[i]);}if(isMaxHeap(arr,n)) printf("true");else printf("false");return 0;
}

/*【问题描述】设计快速排序的非递归算法
【输入形式】两行，第一行是数据个数，第二行是待排数据
【输出形式】排序后非递减的有序序列
【样例输入】
9
8 7 6 5 4 3 2 1 0
【样例输出】
0 1 2 3 4 5 6 7 8 */
#include<stdio.h>
#include<stdlib.h>
//每一趟排序
int sort(int* arr, int left, int right) {int i = left;int j = right;int temp = arr[left];while (i != j) {while (temp <= arr[j] && i < j)//j左移j--;while (temp >= arr[i] && i < j)//i向右移i++;if (i < j) {//i与j都停止移动的时候，交换数字int t = arr[i];arr[i] = arr[j];arr[j] = t;}}//此时i与j相遇，进行数字交换arr[left] = arr[i];arr[i] = temp;return i;//返回这个交汇点
}void quick_sort(int* arr, int left, int right) {int* stack = (int*)malloc(sizeof(int) * right);//创建一个数组栈for (int i = 0; i < right; i++)stack[i] = -1;//初始化为-1int count = 0;//当前栈数据的个数if (left < right) {//入栈stack[count++] = left;stack[count++] = right;}while (count) {//当栈为非空的时候//出栈操作int r_pop = stack[count-1];int l_pop = stack[count-2];stack[count - 1] = stack[count - 2] = -1;//出栈后，清空已出栈数据，设置为-1count -= 2;int i = sort(arr, l_pop, r_pop);//如果这个交汇点前面数据的下标比当前最左边的数据下标要大的话，就入栈if (l_pop < i - 1) {stack[count++] = l_pop;stack[count++] = i - 1;}//如果这个交汇点后面一个数据的下标比当前最右边数据的下标要小的话，入栈if (r_pop > i + 1) {stack[count++] = i + 1;stack[count++] = r_pop;}}//释放空间free(stack);stack = NULL;
}int main() {int n;scanf("%d",&n);int array[n];for(int i=0;i<n;i++){scanf("%d",&array[i]);}quick_sort(array, 0, sizeof(array) / sizeof(int) - 1);for (int i = 0; i < sizeof(array) / sizeof(int); i++) {printf("%d ", array[i]);}
}

/*【问题描述】设计一个折半插入算法将初始数据从大到小递减排序，并要求在初始数据正序时移动元素的次数为零。
【输入形式】两行，第一行是数据个数，第二行是待排数据
【输出形式】排序后递减的有序序列
【样例输入】
9
0 1 2 3 4 5 6 7 8 
【样例输出】
8 7 6 5 4 3 2 1 0*/
#include <stdio.h>
void insertSort(int array[], int n){int temp;for(int i = 1; i < n; i++){int low = 0;int hight = i-1;temp = array[i];while(hight>=low){int mid = ( low + hight ) / 2;if (array[mid] < temp){hight = mid - 1;}else{low = mid + 1;}}for (int j = i-1; j > hight; j--) {array[j+1] = array[j];}array[hight+1] = temp;}
}int main(void){int n;scanf("%d",&n);int a[n];for(int i=0;i<n;i++){scanf("%d",&a[i]);}insertSort(a,n);for(int i = 0; i < n; i++){printf("%d ",a[i]);}return 0;
}