1、 编写算法，将二个升序链表在原表空间内归并成一个升序链表。
/* 1、 编写算法，将二个升序链表在原表空间内归并成一个升序链表。*/#include <stdio.h>#include <stdlib.h>#define MaxSize 50typedef int ElementType;typedef struct LNode {ElementType data;struct LNode *Next;} LNode,*List;/*尾插法建立链表L */void createListR(LNode *&L) {LNode *s, *r; //s用来指向新申请的结点，r始终指向L的终端结点ElementType x;L = (LNode *)malloc(sizeof(struct LNode));//申请L的头结点空间L->Next = NULL;r = L;//r指向头结点，因为此时头结点就是终端结点printf("\n(尾插法)请依次输入链表元素(以-999作结束标志)：\n");while(1) {//循环申请结点来接收输入缓冲区中的元素，直到遇到-999结束接收scanf("%d",&x);if(x == -999) break;s = (LNode *)malloc(sizeof(struct LNode));//s指向新申请的结点s->data = x;//用新申请的结点来接收输入的元素r->Next = s;//用r来接纳新结点r = r->Next;//r指向终端结点，以便于接纳下一个到来的结点}r->Next = NULL;//输入缓冲区的所有元素都已经装入链表L中，L的终端结点的指针域置位NULL，L建立完成}/*打印链表*/void printList(LNode *L) {LNode *p = L->Next;// printf("\n链表元素依次为：");while(p != NULL) {printf("%d ",p->data);p = p->Next;}printf("\n");}//以下是题目算法void merge_up(LNode *&A, LNode *B) {LNode *p = A->Next;LNode *q = B->Next;LNode *s;A->Next = NULL;free(B);s = A;while(p !=NULL && q != NULL) {if(p->data <= q->data) {s->Next = p;p = p->Next;s = s->Next;} else {s->Next = q;q = q->Next;s = s->Next;}}s->Next = NULL;//以下两个if语句将还有剩余结点的链表链接在A的尾部if(p != NULL) s->Next = p;if(q != NULL) s->Next = q;}int main(){LNode *La,*Lb;printf("1、编写算法，将二个升序链表在原表空间内归并成一个升序链表。\n");printf("尾插法创建链表La(元素升序)：");createListR(*&La);printf("尾插法创建链表Lb(元素升序)：");createListR(*&Lb);merge_up(La, Lb);printf("归并成一个升序链表(仍使用原表的存储空间)：");printList(La);system("pause");return 0;}
2、 编写算法，将二个升序链表在原表空间内归并成一个降序链表。
/* 2、 编写算法，将二个升序链表在原表空间内归并成一个降序链表。*/#include <stdio.h>#include <stdlib.h>#define MaxSize 50typedef int ElementType;typedef struct LNode {ElementType data;struct LNode *Next;} LNode,*List;/*尾插法建立链表L */void createListR(LNode *&L) {LNode *s, *r; //s用来指向新申请的结点，r始终指向L的终端结点ElementType x;L = (LNode *)malloc(sizeof(struct LNode));//申请L的头结点空间L->Next = NULL;r = L;//r指向头结点，因为此时头结点就是终端结点printf("\n(尾插法)请依次输入链表元素(以-999作结束标志)：\n");while(1) {//循环申请结点来接收输入缓冲区中的元素，直到遇到-999结束接收scanf("%d",&x);if(x == -999) break;s = (LNode *)malloc(sizeof(struct LNode));//s指向新申请的结点s->data = x;//用新申请的结点来接收输入的元素r->Next = s;//用r来接纳新结点r = r->Next;//r指向终端结点，以便于接纳下一个到来的结点}r->Next = NULL;//输入缓冲区的所有元素都已经装入链表L中，L的终端结点的指针域置位NULL，L建立完成}/*打印链表*/void printList(LNode *L) {LNode *p = L->Next;// printf("\n链表元素依次为：");while(p != NULL) {printf("%d ",p->data);p = p->Next;}printf("\n");}//题目要求的算法void merge_down(LNode *&A, LNode *B) {LNode *p = A->Next;LNode *q = B->Next;LNode *s;A->Next = NULL;free(B);while(p !=NULL && q != NULL) {//下边的if else语句体现了链表的头插法if(p->data <= q->data) {s = p;p = p->Next;s->Next = A->Next;A->Next = s;} else {s = q;q = q->Next;s->Next = A->Next;A->Next = s;}}//下边两个循环是和求递增归并序列不同的地方，必须将剩余元素逐个插入C的头部才能得到最终的递减序列while(p != NULL) {s = p;p = p->Next;s->Next = A->Next;A->Next = s;}while(q != NULL) {s = q;q = q->Next;s->Next = A->Next;A->Next = s;}}int main(){LNode *La,*Lb;printf("2、 编写算法，将二个升序链表在原表空间内归并成一个降序链表。\n");printf("创建链表La(元素升序)：");createListR(*&La);printf("创建链表Lb(元素升序)：");createListR(*&Lb);merge_down(La, Lb);printf("归并成一个降序链表(仍使用原来两个链表的存储空间)：");printList(La);system("pause");return 0;}
3、 编写算法，用顺序存储结构实现二个升序集合的A=A－B运算。
/*3、 编写算法，用顺序存储结构实现二个升序集合的A=A－B运算。*/#include<stdio.h>#include <stdlib.h>#define maxsize 10typedef struct sqlist {int data[maxsize];int length;} sqlist,*lnode;void create(lnode &l,int a[],int n) {l=(sqlist*)malloc(sizeof(sqlist));for(int i=0; i<n; i++) {l->data[i]=a[i];}l->length=n;}void del(lnode &l,int n) {int i;for(i=n; i<l->length-1; i++) {l->data[i]=l->data[i+1];}l->length--;}void listminus(lnode &a,lnode b) {int m=a->length,n=b->length;int i,j,k=0;for(i=0; i<m; i++) {for(j=k; j<=n; j++) {if(a->data[i]==b->data[j]) {del(a,i);k=j+1;}}}}void show(lnode l) {int i;for(i=0; i<l->length; i++)printf("%d ",l->data[i]);}int main() {printf("3、 编写算法，用顺序存储结构实现二个升序集合的A=A－B运算。\n");lnode A,B;int a[10],b[10],i;printf("input six number: ");for(i=0; i<6; i++) {scanf("%d",&a[i]);}printf("input six number: ");for(i=0; i<6; i++) {scanf("%d",&b[i]);}create(A,a,6);create(B,b,6);listminus(A,B);printf("\nA = A-B :\n");show(A);printf("\n");system("pause");return 0;}
4、 编写算法，用单链表实现二个升序集合A和B的差集存放在集合C，即C=A－B运算，要求C中元素递增有序。
/*4、 编写算法，用单链表实现二个升序集合A和B的差集存放在集合C，即C=A－B运算，要求C中元素递增有序。*/#include <stdio.h>#include <stdlib.h>typedef struct Node {int data;struct Node* next;} LNode, * LinkList;void CreateList(LNode* A) {// 创建单循环链表，返回链表头LNode* p;int i, n;printf("输入链表的元素个数:");scanf("%d", &n);//输入集合元素的个数printf("输入链表元素（按升序）:");for (i = 0; i < n; i++) {p = (LNode*)malloc(sizeof(LNode));scanf("%d", &p->data);//输入每个元素，空格隔开p->next = A->next;A->next = p;A = p;}}void PrintList(LNode* head) {LNode* p = head->next;while (p) {printf("%d ", p->data);p = p->next;}}void listASC(LNode* A, LNode* B, LNode* C) {//用单链表实现二个升序集合A和B的差集存放在集合C，即C=A－B运算，要求C中元素递增有序LNode* pa, * pb, * pc;int count;pa = A->next;pc = C->next;while (pa) {count = 0;pb = B->next;while (pb) {if (pa->data == pb->data)count++;pb = pb->next;}if (count == 0) {pc = (LNode*)malloc(sizeof(LNode));pc->data = pa->data;pc->next = C->next;C->next = pc;C = pc;}pa = pa->next;}}void listDESC(LNode* A, LNode* B, LNode* C) {//用单链表实现二个升序集合A和B的差集存放在集合C，即C=A－B运算，要求C中元素递减有序LNode* pa, * pb, * pc, * p;int count;pa = A->next;pc = C->next;while (pa) {count = 0;pb = B->next;while (pb) {if (pa->data == pb->data)count++;pb = pb->next;}if (count == 0) {pc = (LNode*)malloc(sizeof(LNode));pc->data = pa->data;pc->next = C->next;C->next = pc;}pa = pa->next;}}int main() {printf("4、 编写算法，用单链表实现二个升序集合A和B的差集存放在集合C，即C=A－B运算，要求C中元素递增有序。\n");LNode* A, * B, * C;A = (LNode*)malloc(sizeof(LNode));A->next = NULL;B = (LNode*)malloc(sizeof(LNode));B->next = NULL;C = (LNode*)malloc(sizeof(LNode));C->next = NULL;CreateList(A);CreateList(B);listASC(A, B, C); printf("\nC = A-B :\n");PrintList(C);printf("\n");system("pause");return 0;}
5、 编写算法，用单链表实现二个升序集合A和B的差集存放在集合C，即C=A－B运算，要求C中元素递减有序。
/*5、 编写算法，用单链表实现二个升序集合A和B的差集存放在集合C，即C=A－B运算，要求C中元素递减有序。*/#include <stdio.h>#include <stdlib.h>typedef struct Node {int data;struct Node* next;} LNode, * LinkList;void CreateList(LNode* A) {// 创建单循环链表，返回链表头LNode* p;int i, n;printf("输入链表的元素个数:");scanf("%d", &n);//输入集合元素的个数printf("输入链表元素（按升序）:");for (i = 0; i < n; i++) {p = (LNode*)malloc(sizeof(LNode));scanf("%d", &p->data);//输入每个元素，空格隔开p->next = A->next;A->next = p;A = p;}}void PrintList(LNode* head) {LNode* p = head->next;while (p) {printf("%d ", p->data);p = p->next;}}void listASC(LNode* A, LNode* B, LNode* C) {//用单链表实现二个升序集合A和B的差集存放在集合C，即C=A－B运算，要求C中元素递增有序LNode* pa, * pb, * pc;int count;pa = A->next;pc = C->next;while (pa) {count = 0;pb = B->next;while (pb) {if (pa->data == pb->data)count++;pb = pb->next;}if (count == 0) {pc = (LNode*)malloc(sizeof(LNode));pc->data = pa->data;pc->next = C->next;C->next = pc;C = pc;}pa = pa->next;}}void listDESC(LNode* A, LNode* B, LNode* C) {//用单链表实现二个升序集合A和B的差集存放在集合C，即C=A－B运算，要求C中元素递减有序LNode* pa, * pb, * pc, * p;int count;pa = A->next;pc = C->next;while (pa) {count = 0;pb = B->next;while (pb) {if (pa->data == pb->data)count++;pb = pb->next;}if (count == 0) {pc = (LNode*)malloc(sizeof(LNode));pc->data = pa->data;pc->next = C->next;C->next = pc;}pa = pa->next;}}int main() {printf("5、 编写算法，用单链表实现二个升序集合A和B的差集存放在集合C，即C=A－B运算，要求C中元素递减有序。\n");LNode* A, * B, * C;A = (LNode*)malloc(sizeof(LNode));A->next = NULL;B = (LNode*)malloc(sizeof(LNode));B->next = NULL;C = (LNode*)malloc(sizeof(LNode));C->next = NULL;CreateList(A);CreateList(B);printf("\nC = A-B :\n");listDESC(A, B, C);PrintList(C);printf("\n");system("pause");return 0;}
6、 编写算法，将一单链表就地逆置。
/*6、 编写算法，将一单链表就地逆置。*/#include <stdio.h>#include <stdlib.h>#define MaxSize 50typedef int ElementType;typedef struct LNode {ElementType data;struct LNode *Next;} LNode,*List;/*尾插法建立链表L */void createListR(LNode *&L) {LNode *s, *r; //s用来指向新申请的结点，r始终指向L的终端结点ElementType x;L = (LNode *)malloc(sizeof(struct LNode));//申请L的头结点空间L->Next = NULL;r = L;//r指向头结点，因为此时头结点就是终端结点printf("\n(尾插法)请依次输入链表元素(以-999作结束标志)：\n");while(1) {//循环申请结点来接收输入缓冲区中的元素，直到遇到-999结束接收scanf("%d",&x);if(x == -999) break;s = (LNode *)malloc(sizeof(struct LNode));//s指向新申请的结点s->data = x;//用新申请的结点来接收输入的元素r->Next = s;//用r来接纳新结点r = r->Next;//r指向终端结点，以便于接纳下一个到来的结点}r->Next = NULL;//输入缓冲区的所有元素都已经装入链表L中，L的终端结点的指针域置位NULL，L建立完成}/*打印链表*/void printList(LNode *L) {LNode *p = L->Next;// printf("\n链表元素依次为：");while(p != NULL) {printf("%d ",p->data);p = p->Next;}printf("\n");}/*解法一:将头结点摘下，然后从第一结点开始，依次插入到头结点的后面(头插法建立单链表)，直到最后一个结点为止，这样就实现了链表的逆置*/LNode * Reverse_1 (LNode *L) {//L是带头结点的单链表，本算法将L就地逆置LNode *p, *r;//p为工作指针，r为p的后继，以防断链p=L->Next;//从第一个元素结点开始L->Next=NULL;//先将头结点L的Next域置为NULLwhile (p!=NULL) {//依次将元素结点摘下r=p->Next;//暂存P的后继p->Next=L->Next;//将P结点插入到头结点之后L->Next=p;p=r;}return L;}/*解法二 ：假设pre、p和r指向3个相邻的结点，如下图所示。假设经过若干操作后，*pre 之前的;结点的指针都已调整完毕，它们的Next都指向其原前驱结点。现在令*p结点的Next域指向*pre结点，注意到一旦调整指针的指向后，*p 的后继结点的链就会断开，为此需要用r来指向原*p的后继结点。处理时需要注意两点:一是在处理第一个结点时，应将其Next域置为NULL,而不是指向头结点(因为它将作为新表的尾结点);二是在处理完最后一个结点后，需要将头结点的指针指向它。*/LNode * Reverse_2 (LNode *L) {//依次遍历线性表L,并将结点指针反转LNode *pre, *p=L->Next, *r=p->Next;p->Next=NULL;//处理第一个结点while(r!=NULL) {//r为空，则说明p为最后一个结点pre=p;//依次继续遍历p=r;r=r->Next;p->Next=pre;//指针反转}L->Next=p;//处理最后一个结点return L;}int main(){LNode *La;printf("6、 编写算法，将一单链表就地逆置。");createListR(*&La);La = Reverse_1 (La);printf("链表就地逆转后：");printList(La);system("pause");return 0;}
7、 编写算法，在一个双链表的第i个元素前插入一个元素。
/*7、 编写算法，在一个双链表的第i个元素前插入一个元素。*/#include <stdio.h>#include <stdlib.h>typedef int ElemType;typedef struct line {struct line * prior;ElemType data;struct line * next;}line;line * insertLine(line * head, int data, int add) {//新建数据域为data的结点line * temp = (line*)malloc(sizeof(line));temp->data = data;temp->prior = NULL;temp->next = NULL;//插入到链表头，要特殊考虑if (add == 1) {temp->next = head;head->prior = temp;head = temp;}else {int i = 0;line * body = head;//找到要插入位置的前一个结点for (i = 1; i < add - 1; i++) {body = body->next;if (body == NULL) {printf("插入位置有误\n");break;}}if (body) {//判断条件为真，说明插入位置为链表尾if (body->next == NULL) {body->next = temp;temp->prior = body;}else {body->next->prior = temp;temp->next = body->next;body->next = temp;temp->prior = body;}}}return head;}//输出链表的功能函数void display(line * head) {line * temp = head;while (temp) {if (temp->next == NULL) {printf("%d\n", temp->data);}else {printf("%d-", temp->data);}temp = temp->next;}}line* initLine(line * head) {int i = 0;line * list = NULL;head = (line*)malloc(sizeof(line));head->prior = NULL;head->next = NULL;head->data = 1;list = head;for (i = 2; i <= 10; i++) {line * body = (line*)malloc(sizeof(line));body->prior = NULL;body->next = NULL;body->data = i;list->next = body;body->prior = list;list = list->next;}return head;}int main() {ElemType x;int i;printf("7、 编写算法，在一个双链表的第i个元素前插入一个元素。\n");line * head = NULL;printf("初始链表为：\n");head = initLine(head);display(head);printf("在表中第 i 的位置插入新元素 x (input i and x)：\n");scanf("%d %d",&i,&x);head = insertLine(head, x, i);display(head);system("pause");return 0;}
8、 编写算法，删除一个双链表的第i个元素。
/*8、 编写算法，删除一个双链表的第i个元素。*/#include <stdio.h>#include <stdlib.h>typedef int ElemType;typedef struct line {struct line * prior;ElemType data;struct line * next;} line;//删除函数，其中，pos 表示要删除结点在双链表中的位置line *Del_ith(line * p, int pos) {int i = 0;line * temp = p;//遍历到被删除结点for (i = 1; i < pos; i++) {temp = temp->next;if (temp == NULL) {printf("删除位置有误！\n");break;}}if (temp) {temp->prior->next = temp->next;temp->next->prior = temp->prior;free(temp);// return p;}return p;}//输出链表的功能函数void display(line * head) {line * temp = head;while (temp) {if (temp->next == NULL) {printf("%d\n", temp->data);} else {printf("%d-", temp->data);}temp = temp->next;}}line* initLine(line * head) {int i = 0;line * list = NULL;head = (line*)malloc(sizeof(line));head->prior = NULL;head->next = NULL;head->data = 1;list = head;for (i = 2; i <= 10; i++) {line * body = (line*)malloc(sizeof(line));body->prior = NULL;body->next = NULL;body->data = i;list->next = body;body->prior = list;list = list->next;}return head;}int main() {int i;printf("8、 编写算法，删除一个双链表的第i个元素。\n");line * head = NULL;printf("初始链表为：\n");head = initLine(head);display(head);printf("删除一个双链表的第i个元素(input i)：\n");scanf("%d",&i);head = Del_ith(head,i);display(head);system("pause");return 0;}
9、 编写算法，删除一升序单链表中所有值相同的多余元素，释放被删结点空间。
/*9、 编写算法，删除一升序单链表中所有值相同的多余元素，释放被删结点空间。*/#include <stdio.h>#include <stdlib.h>#define MaxSize 50typedef int ElementType;typedef struct LNode {ElementType data;struct LNode *Next;} LNode,*List;/*尾插法建立链表L */void createListR(LNode *&L) {LNode *s, *r; //s用来指向新申请的结点，r始终指向L的终端结点ElementType x;L = (LNode *)malloc(sizeof(struct LNode));//申请L的头结点空间L->Next = NULL;r = L;//r指向头结点，因为此时头结点就是终端结点printf("\n(尾插法)请依次输入链表元素(以-999作结束标志)：\n");while(1) {//循环申请结点来接收输入缓冲区中的元素，直到遇到-999结束接收scanf("%d",&x);if(x == -999) break;s = (LNode *)malloc(sizeof(struct LNode));//s指向新申请的结点s->data = x;//用新申请的结点来接收输入的元素r->Next = s;//用r来接纳新结点r = r->Next;//r指向终端结点，以便于接纳下一个到来的结点}r->Next = NULL;//输入缓冲区的所有元素都已经装入链表L中，L的终端结点的指针域置位NULL，L建立完成}/*打印链表*/void printList(LNode *L) {LNode *p = L->Next;// printf("\n链表元素依次为：");while(p != NULL) {printf("%d ",p->data);///lei?spm=1010.2135.3001.5343p = p->Next;}printf("\n");}void delsll (LNode *L) {LNode *p=L->Next,*q;while (p->Next !=NULL) {if (p->data == p->Next->data) {//找到重 复结点并删除q=p->Next;p->Next=q->Next;free (q) ;} elsep=p->Next;}}int main() {LNode *L;printf("9、 编写算法，删除一升序单链表中所有值相同的多余元素，释放被删结点空间。\n");printf("创建链表L(元素升序)：");createListR(*&L);delsll(L);printf("删除一升序单链表中所有值相同的多余元素后：");printList(L);system("pause");return 0;}
10、 编写算法，删除一升序单链表中所有值在[mink,maxk]之间的元素，释放被删结点空间。
/*10、 编写算法，删除一升序单链表中所有值在[mink,maxk]之间的元素，释放被删结点空间。*/#include <stdio.h>#include <stdlib.h>#define MaxSize 50typedef int ElementType;typedef struct LNode {ElementType data;struct LNode *Next;} LNode,*List;/*尾插法建立链表L */void createListR(LNode *&L) {LNode *s, *r; //s用来指向新申请的结点，r始终指向L的终端结点ElementType x;L = (LNode *)malloc(sizeof(struct LNode));//申请L的头结点空间L->Next = NULL;r = L;//r指向头结点，因为此时头结点就是终端结点printf("\n(尾插法)请依次输入链表元素(以-999作结束标志)：\n");while(1) {//循环申请结点来接收输入缓冲区中的元素，直到遇到-999结束接收scanf("%d",&x);if(x == -999) break;s = (LNode *)malloc(sizeof(struct LNode));//s指向新申请的结点s->data = x;//用新申请的结点来接收输入的元素r->Next = s;//用r来接纳新结点r = r->Next;//r指向终端结点，以便于接纳下一个到来的结点}r->Next = NULL;//输入缓冲区的所有元素都已经装入链表L中，L的终端结点的指针域置位NULL，L建立完成}/*打印链表*/void printList(LNode *L) {LNode *p = L->Next;// printf("\n链表元素依次为：");while(p != NULL) {printf("%d ",p->data);///lei?spm=1010.2135.3001.5343p = p->Next;}printf("\n");}void RangeDelete (LNode *&L, int mink, int maxk) {LNode *pr = L, *p=L->Next;//p是检测指针，pr是其前驱while (p !=NULL)if (p->data>=mink && p->data<=maxk) {//寻找到被删结点，删除pr->Next = p->Next;free(p);p = pr->Next;} else {//否则继续寻找被删结点pr = p;p =p->Next;}}int main() {LNode *La;ElementType mink,maxk;printf("10、 编写算法，删除一升序单链表中所有值在[mink,maxk]之间的元素，释放被删结点空间。\n");createListR(*&La);printf("输入 mink 和 maxk:");scanf("%d %d",&mink,&maxk);RangeDelete(*&La,mink,maxk);printf("删去介于%d和%d之间的所有元素后:",mink,maxk);printList(La);system("pause");return 0;}
11、 编写算法，判断一表达式中的括号是否配对，包括大、中、小三类括号。
/*11、 编写算法，判断一表达式中的括号是否配对，包括大、中、小三类括号。*/#include <stdio.h>#include <stdlib.h>#include <string.h>#define MaxSize 50typedef struct {char data[MaxSize];// 存放栈中元素，MaxSize是已经定义好的常量int top;// 栈顶指针} SqStack; // 顺序栈类型定义/* 初始化顺序栈 */void initStack(SqStack &st) {st.top=-1; // 只需将栈顶指针设置为-1，本栈中将top=-1规定为栈空状态}/* 判断栈空 */int isEmpty(SqStack st) {// 栈为空的时候返回1，否则返回0if(st.top==-1) {// 判空的条件是栈顶指针是否等于-1return 1;} else {return 0;}}/* 判断栈满 */int isFull(SqStack st) {// 如果栈顶指针等于MaxSize-1那么栈满，否则栈空if(st.top==MaxSize-1) {// MaxSize是栈中最大元素个数，已经定义return 1;// 栈满返回1} else {return 0;// 栈空返回0}}/* 进栈 */int push(SqStack &st,char x) {/* 进栈首先要判断栈是否栈满，如果满栈则不能进栈 */if(isFull(st)==1) {return 0;// 如果栈满返回0，表示不能进栈} else {// 注意：++top和top++在这里的作用是一样的，都可以使用，如果是a=++top和a=top++，那么两个a的值是不一样的，最后top的值还是一样++st.top;// 先移动指针，再进栈st.data[st.top]=x;return 1;// 进栈成功返回1}}/* 出栈 */int pop(SqStack &st,char &x) {/* 出栈之前要判断栈是否为空 */if(isEmpty(st)==1) {// 1表示栈空，0表示非空return 0;// 如果栈空，不能出栈，返回0} else {x=st.data[st.top];// 先取出元素，再出栈--st.top;return 1;// 出栈成功返回1}}/* 打印栈，从左到右表示栈底到栈顶 */void printStack(SqStack stack) {printf("\n");for(int i=0; i<=stack.top; i++) {// 注意：data[0]表示栈底元素，data[top]表示栈顶元素printf("%c\t",stack.data[i]);// 打印栈中元素}printf("\n");}/* 用来比较括号是否正确配对，如果正常配对返回1，否则返回0 */int match(char exp[]) {SqStack stack;// 定义一个顺序栈char x;// 定义一个放出栈元素的变量initStack(stack);// 调用函数初始化顺序栈int n=strlen(exp);int i;/* 判断表达式的括号是否匹配 */for(i=0; i<n; i++) {// 循环遍历数组中的每个括号if(exp[i]=='(' || exp[i]=='[' || exp[i]=='{') {// 判断括号是不是'(','[','{'，如果是的话push(stack,exp[i]);// 则压入顺序栈}if(exp[i]==')' || exp[i]==']' || exp[i]=='}') {// 判断括号是不是')',']','}'，如果是的话if(isEmpty(stack)==1) {// 如果当前遇到的括号是")"，并且栈已空，则不匹配，返回0return 0;} else {// 如果栈不空，则出栈。也就是划掉"()"pop(stack,x);}}}/* 循环遍历括号表达式完毕后，对结果进行反馈 */if(isEmpty(stack)==1) {// 如果栈空的话，即所有括号都正确配对，返回1return 1;} else {// 如果栈不空，则栈中存在着"("，故未能正确配对，返回0return 0;}}int main() {int check_result;char exp[100];printf("11、 编写算法，判断一表达式中的括号是否配对，包括大、中、小三类括号。\n");printf("\n[括号匹配]请输入表达式:\n");scanf("%s",exp);check_result=match(exp);if(check_result == 1) printf("括号匹配\n");else printf("括号不匹配\n");system("pause");return 0;}
12、 编写算法，实现hanoi塔问题。
/*12、 编写算法，实现hanoi塔问题。*/#include <stdio.h>#include <stdlib.h>#define MaxSize 50int hanoi(int n,char x,char y,char z) {int move(char,int,char);if(n==1)//如果圆盘数量仅有 1 个，则直接从起始柱移动到目标柱move(x,1,z);else {hanoi(n-1,x,z,y);//递归调用 hanoi() 函数，将 n-1 个圆盘从起始柱移动到辅助柱上move(x,n,z);//将起始柱上剩余的最后一个圆盘移动到目标柱上hanoi(n-1,y,x,z);//递归调用 hanoi() 函数，将辅助柱上的 n-1 圆盘移动到目标柱上}return 0;}int move(char getone,int n,char putone) {static int k=1;//统计移动次数printf("第%2d次:%3d号盘 # 由%c--->%c\n",k,n,getone,putone);if(k++%3==0)printf("\n");return 0;}int main() {// int hanoi(int,char,char,char);int n,counter;printf("\n12、 编写算法，实现hanoi塔问题.\n");printf("输入盘子数量：");scanf("%d",&n);fflush(stdin);printf("\n");counter=hanoi(n,'A','B','C');system("pause");return 0;}
13、 编写算法，计算一个后缀表达式的值。
/*13、 编写算法，计算一个后缀表达式的值。*/#include <stdio.h>#include <stdlib.h>#include <string.h>char a[10000];long long stack[1000],top=-1;int main() {printf("13、 编写算法，计算一个后缀表达式的值。\n");long long k=0,i=0,len,b,tag,d,e,f;char c;printf("输入后缀表达式(例如：16 9 4 3 +*-)：\n");gets(a);len=strlen(a);while(i<len) {b=0,tag=0;while(i<len&&'0'<=a[i]&&a[i]<='9')b*=10,b+=a[i]-'0',i++,tag=1;if(tag) top++,stack[top]=b;else if(a[i]=='+'||a[i]=='-'||a[i]=='*'||a[i]=='/') {d=stack[top],top--;e=stack[top],top--;switch(a[i]) {case '+':f=e+d;break;case '-':f=e-d;break;case '*':f=e*d;break;case '/':f=e/d;break;}top++;stack[top]=f;i++;} else i++;}printf("result = %lld\n",stack[top]);system("pause");return 0;}
14、 编写算法，求子串t在主串s中的位置。
/*14、 编写算法，求子串t在主串s中的位置。*/#include <stdio.h>#include <stdlib.h>#include <string.h>#define MaxSize 10#define SIZE 1000//KMP算法中的next数组void Next(char*V,int *next) {int i=1;next[1]=0;int j=0;while (i<strlen(V)) {if (j==0||V[i-1]==V[j-1]) {i++;j++;if (V[i-1]!=V[j-1])next[i]=j;elsenext[i]=next[j];} elsej=next[j];}}//KMP算法(快速模式匹配)void KMP(char * S,char * T,int (*a)[SIZE],int *number) {int next[10];Next(T,next);//根据模式串T,初始化next数组int i=1,j=1;*number=0;while (i<=strlen(S)) {if (j==0 || S[i-1]==T[j-1]) {i++;j++;} else {j=next[j];}if (j>strlen(T)) {(*number)++;(*a)[(*number)]=i-(int)strlen(T);j=0;i--;}}}void runFindPos() {char S[SIZE],V[SIZE],T[SIZE];char *newString=(char*)malloc(SIZE*sizeof(char));char judge;printf("请输入原字符串S：\n");fflush(stdin);scanf("%[^\n]",S);getchar();//用于承接缓冲区冲的换行符printf("输入要查找位置的子串T：\n");fflush(stdin);while (scanf("%s",T)) {getchar();int a[SIZE],number;KMP(S,T,&a,&number);if (number==0) {printf("未检测到原字符串S中有该字符串！是否重新输入(Input Y or N)：\n");fflush(stdin);scanf("%c",&judge);getchar();if (judge=='N') {break;} else {printf("输入要查找位置的子串T：\n");}} else {printf("检测到该子串T在原字符串中出现 %d 次，起始位置依次是：\n",number);int i;for (i=1; i<=number; i++) {printf("%d ",a[i]);}printf("\n");}}free(newString);}int main(){printf("14、 编写算法，求子串t在主串s中的位置。\n");runFindPos();system("pause");return 0;}
15.编写算法,在主串s的第i个位置前插入子串t
/*15.编写算法,在主串s的第i个位置前插入子串t*/#include <stdio.h>#include <string.h>#include <stdlib.h>#include <math.h>#define MAXSIZE 100typedef char elemtype;typedef struct {elemtype num[MAXSIZE+1];int length;} SString;void initString(SString &s) {memset(s.num,0,sizeof(s.num));s.length=0;}void assignString(SString &s,char *w) {int wlen=strlen(w);for(int i=1; i<=wlen; i++)s.num[i]=*w++;s.length+=wlen;}void insertString(SString &s,SString &t,int pos) {int i;for(i=s.length; i>=pos; i--)if(i+t.length<=MAXSIZE)s.num[i+t.length]=s.num[i];for(i=0; i<t.length; i++)if(pos+i<=MAXSIZE)s.num[pos+i]=t.num[i+1];if(s.length+t.length<=MAXSIZE)s.length+=t.length;elses.length=s.length+t.length-MAXSIZE;}int getLengthString(SString s) {return s.length;}void printString(SString s) {for(int i=1; i<=s.length; i++)printf("%c",s.num[i]);printf("\n");}int main() {printf("15、 编写算法，在主串s的第i个位置前插入子串t\n");SString s1,s2;initString(s1);initString(s2);char str[MAXSIZE];printf("Input s1:");gets(str);assignString(s1,str);int s1_length=getLengthString(s1);printf("Input s2:");gets(str);assignString(s2,str);int pos;do {printf("Input insert position:");scanf("%d",&pos);} while(pos<=0 || pos>s1_length);insertString(s1,s2,pos);printString(s1);printf("\n");system("pause");return 0;}
16、 编写算法，删除主串s中所有和串t相同的子串。
//16、 编写算法，删除主串s中所有和串t相同的子串。#include<stdio.h>#include<stdlib.h>#include<string.h>#define S_len 1000#define T_len 1000int main() {printf("16、 编写算法，删除主串s中所有和串t相同的子串。\n");char s[S_len];char t[T_len];printf("输入主串S:");scanf("%s",s);printf("输入要删除的串t:");scanf("%s",t);int ls=strlen(s),lt=strlen(t),i,j,k;for(i=0,j=0; i<ls; i++) {if(s[i]==t[j])j++;else j=0;if(j==lt) {ls-=lt;for(j=i-lt+1; j<ls; j++) {s[j]=s[j+lt];}j=0;i=i-lt;}}printf("输出结果：");for(i=0; i<ls; i++) {printf("%c",s[i]);}printf("\n");system("pause");return 0;}
17、 编写算法，实现串的比较运算。
//17、 编写算法，实现串的比较运算。#include<stdio.h>#include<stdlib.h>/*字符串比较函数，相同返0，str1>str2返1，否则返-1*/int strcompare(char str1[], char str2[]) {int size1 = 0, size2 = 0; //用来累计字符ascll码之和for (int i = 0; str1[i] != '\0'; i++)size1 += (int)str1[i]; //加上字符的（int）即ascll码for (int i = 0; str2[i] != '\0'; i++)size2 += (int)str2[i];if (size1 == size2) //字符串大小一样return 0;else if (size1 > size2)return 1;elsereturn -1;}int main() {printf("17、 编写算法，实现串的比较运算。\n");char str1[] = "aseff";char str2[] = "assff";char str3[] = "aesff";if (strcompare(str1, str2)==0) //比较str1和str2printf("%s和%s相同！\n",str1,str2);else if(strcompare(str1,str2)==-1)printf("%s小于%s\n", str1, str2);elseprintf("%s大于%s\n", str1, str2);if (strcompare(str1, str3) == 0) //比较str1和str3printf("%s和%s相同！\n", str1, str3);else if (strcompare(str1, str3) == -1)printf("%s小于%s\n", str1, str3);elseprintf("%s大于%s\n", str1, str3);system("pause");return 0;}
18、 编写算法，实现串的连接运算。
//18、 编写算法，实现串的连接运算。#include<stdio.h>#include<stdlib.h>//#include<string.h>#define MaxSize 100 //最多的字符个数typedef struct {char data[MaxSize];//定义可以容纳MaxSize个字符的空间int length; //标记当前实际串长} SqString;void StrAssign(SqString &str,char cstr[]) {//由串常量cstr创建strint i;for(i=0; cstr[i]!='\0'; i++)str.data[i]=cstr[i];str.length=i;}SqString Concat(SqString s,SqString t) {//将串t连接到串s之后产生新串SqString str;int i;str.length=s.length+t.length;for(i=0; i<s.length; i++) //将s.data[0...s.length-1]复制到strstr.data[i]=s.data[i];for(i=0; i<t.length; i++) //将t.data[0...t.length-1]复制到strstr.data[s.length+i]=t.data[i];return str;}void DispStr(SqString s) {//输出串s的所有元素int i;if(s.length>0) {for(i=0; i<s.length; i++)printf("%c",s.data[i]);printf("\n");}}int main() {printf("18、 编写算法，实现串的连接运算。\n");SqString s1,s2,s3;printf("建立串s和串s1\n");StrAssign(s1,"abcdef");StrAssign(s2,"xyz");printf("串s1和串s2连接产生串s3\n");s3=Concat(s1,s2);printf("输出串s3:");DispStr(s3);printf("\n");system("pause");return 0;}
19、 编写算法，实现串的置换操作，即将串s中所有的子串t用子串v替换。
/*19、 编写算法，实现串的置换操作，即将串s中所有的子串t用子串v替换。*/#include <stdio.h>#include <stdlib.h>#include <string.h>#define MaxSize 10#define SIZE 1000//KMP算法中的next数组void Next(char*V,int *next) {int i=1;next[1]=0;int j=0;while (i<strlen(V)) {if (j==0||V[i-1]==V[j-1]) {i++;j++;if (V[i-1]!=V[j-1])next[i]=j;elsenext[i]=next[j];} elsej=next[j];}}//KMP算法(快速模式匹配)void KMP(char * S,char * T,int (*a)[SIZE],int *number) {int next[10];Next(T,next);//根据模式串T,初始化next数组int i=1,j=1;*number=0;while (i<=strlen(S)) {if (j==0 || S[i-1]==T[j-1]) {i++;j++;} else {j=next[j];}if (j>strlen(T)) {(*number)++;(*a)[(*number)]=i-(int)strlen(T);j=0;i--;}}}void replace(char * S,char * T,char * V,int *a,int number,char * newString) {int order=0;//表示newString存储字符的位置int begin=0;int i,j,k;for (i=1; i<=number; i++) {//先将替换位置之前的字符完整的复制到新字符串数组中for (j=begin; j<a[i]-1; j++) {newString[order]=S[j];order++;}//替换字符，用新字符代替for (k=0; k<strlen(V); k++) {newString[order]=V[k];order++;}//代替完成后，计算出原字符串中隔过该字符串的下一个起始位置begin=a[i]+(int)strlen(T)-1;}//要替换位置全部替换完成后，检测是否还有后续字符，若有直接复制while(begin<strlen(S)) {newString[order]=S[begin];order++;begin++;}}void runReplace() {char S[SIZE],V[SIZE],T[SIZE];char *newString=(char*)malloc(SIZE*sizeof(char));char judge;printf("请输入原字符串S：\n");fflush(stdin);scanf("%[^\n]",S);getchar();//用于承接缓冲区冲的换行符printf("输入要替换的字符或字符串T：\n");fflush(stdin);while (scanf("%s",T)) {getchar();int a[SIZE],number;KMP(S,T,&a,&number);if (number==0) {printf("未检测到原字符串S中有该字符串！是否重新输入(Input Y or N)：\n");fflush(stdin);scanf("%c",&judge);getchar();if (judge=='N') {break;} else {printf("输入要替换的字符或字符串V：\n");}} else {printf("检测到该字符串在原字符串中出现 %d 次，起始位置依次是：\n",number);int i;for (i=1; i<=number; i++) {printf("%d ",a[i]);}printf("\n");printf("是否使用新字符串替换所有的 %s(Input Y or N)\n",T);fflush(stdin);scanf("%c",&judge);getchar();if (judge=='Y') {printf("请输入用于替换的字符串：\n");fflush(stdin);scanf("%[^\n]",V);getchar();replace(S,T,V,a,number,newString);printf("新生成的字符串为: %s\n",newString);}break;}}free(newString);}int main(){printf("19、 编写算法，实现串的置换操作，即将串s中所有的子串t用子串v替换。\n");runReplace();system("pause");return 0;}
20、 编写算法，实现先序遍历二叉树。
//20、 编写算法，实现先序遍历二叉树。#include <stdio.h>#include <stdlib.h>#define MaxSize 30typedef char ElementType;typedef struct TNode {/* 树结点定义 */ElementType Data; /* 结点数据 */struct TNode *Left;/* 指向左子树 */struct TNode *Right; /* 指向右子树 */} TNode,*BinTree;//采用前序初始化二叉树//中序和后序只需改变赋值语句的位置即可void CreateBT(BinTree * BT) {char data;scanf("%c",&data);if (data!='#') {if (!((*BT)=(TNode*)malloc(sizeof(TNode)))) {printf("申请结点空间失败");return;} else {(*BT)->Data=data;//采用前序遍历方式初始化二叉树CreateBT(&((*BT)->Left));//初始化左子树CreateBT(&((*BT)->Right));//初始化右子树}} else {*BT=NULL;}}//先序遍历void PreorderTraversal( BinTree BT ) {if( BT ) {printf("%c ", BT->Data );PreorderTraversal( BT->Left );PreorderTraversal( BT->Right );}}//先序遍历非递归算法void Pre_Nonrecur(BinTree *BT) {if (BT != NULL) {TNode *Stack[MaxSize];//定义一个栈int top = -1;//初始化栈TNode *p;Stack[++top] = BT;//根节点入栈while(top != -1) {//只要栈非空，就一直循环p = Stack[top--];//出栈并输出栈顶结点printf("%c ",p->Data);if(p->Right != NULL) {Stack[++top] = p->Right;//如果栈顶的右孩子存在，则右孩子入栈}if(p->Left != NULL) {Stack[++top] = p->Left;//如果栈顶的左孩子存在，则左孩子入栈}}}}int main() {BinTree BT;ElementType X;printf("20、 编写算法，实现先序遍历二叉树。\n");printf("\n请输入二叉树结点(前序,#代替空结点)[例如 ABD###CE##F##]:\n");CreateBT(&BT);printf("\n先序遍历：");PreorderTraversal(BT);printf("\n");system("pause");return 0;}
21、 编写算法，实现中序遍历二叉树。
//21、 编写算法，实现中序遍历二叉树。#include <stdio.h>#include <stdlib.h>#define MaxSize 30typedef char ElementType;typedef struct TNode {/* 树结点定义 */ElementType Data; /* 结点数据 */struct TNode *Left;/* 指向左子树 */struct TNode *Right; /* 指向右子树 */} TNode,*BinTree;//采用前序初始化二叉树//中序和后序只需改变赋值语句的位置即可void CreateBT(BinTree * BT) {char data;scanf("%c",&data);if (data!='#') {if (!((*BT)=(TNode*)malloc(sizeof(TNode)))) {printf("申请结点空间失败");return;} else {(*BT)->Data=data;//采用前序遍历方式初始化二叉树CreateBT(&((*BT)->Left));//初始化左子树CreateBT(&((*BT)->Right));//初始化右子树}} else {*BT=NULL;}}//中序遍历void InorderTraversal( BinTree BT ) {if( BT ) {InorderTraversal( BT->Left );/* 此处假设对BT结点的访问就是打印数据 */printf("%c ", BT->Data); /* 假设数据为字符型 */InorderTraversal( BT->Right );}}int main() {BinTree BT;ElementType X;printf("21、 编写算法，实现中序遍历二叉树。\n");printf("\n请输入二叉树结点(前序,#代替空结点)[例如 ABD###CE##F##]:\n");CreateBT(&BT);printf("\n中序遍历：");InorderTraversal(BT);printf("\n");system("pause");return 0;}
22、 编写算法，实现后序遍历二叉树。
//22、 编写算法，实现后序遍历二叉树。#include <stdio.h>#include <stdlib.h>#define MaxSize 30typedef char ElementType;typedef struct TNode {/* 树结点定义 */ElementType Data; /* 结点数据 */struct TNode *Left;/* 指向左子树 */struct TNode *Right; /* 指向右子树 */} TNode,*BinTree;//采用前序初始化二叉树//中序和后序只需改变赋值语句的位置即可void CreateBT(BinTree * BT) {char data;scanf("%c",&data);if (data!='#') {if (!((*BT)=(TNode*)malloc(sizeof(TNode)))) {printf("申请结点空间失败");return;} else {(*BT)->Data=data;//采用前序遍历方式初始化二叉树CreateBT(&((*BT)->Left));//初始化左子树CreateBT(&((*BT)->Right));//初始化右子树}} else {*BT=NULL;}}//后序遍历void PostorderTraversal( BinTree BT ) {if( BT ) {PostorderTraversal( BT->Left );PostorderTraversal( BT->Right );printf("%c ", BT->Data);}}int main() {BinTree BT;ElementType X;printf("22、 编写算法，实现后序遍历二叉树。\n");printf("\n请输入二叉树结点(前序,#代替空结点)[例如 ABD###CE##F##]:\n");CreateBT(&BT);printf("\n后序遍历：");PostorderTraversal(BT);printf("\n");system("pause");return 0;}
23、 编写算法，实现层序遍历二叉树。
//23、 编写算法，实现层序遍历二叉树。#include <stdio.h>#include <stdlib.h>#define MaxSize 30typedef char ElementType;typedef struct TNode {/* 树结点定义 */ElementType Data; /* 结点数据 */struct TNode *Left;/* 指向左子树 */struct TNode *Right; /* 指向右子树 */} TNode,*BinTree;//采用前序初始化二叉树//中序和后序只需改变赋值语句的位置即可void CreateBT(BinTree * BT) {char data;scanf("%c",&data);if (data!='#') {if (!((*BT)=(TNode*)malloc(sizeof(TNode)))) {printf("申请结点空间失败");return;} else {(*BT)->Data=data;//采用前序遍历方式初始化二叉树CreateBT(&((*BT)->Left));//初始化左子树CreateBT(&((*BT)->Right));//初始化右子树}} else {*BT=NULL;}}//层序遍历void LevelorderTraversal ( BinTree *BT ) {int front,rear;TNode *que[MaxSize]; //定义一个循环队列，用来记录将要访问的层次上的结点front = rear = 0;TNode *q;if (BT != NULL) {rear = (rear + 1)%MaxSize;que[rear] = *BT;//根节点入队while (front != rear) {front = (front + 1)%MaxSize;q = que[front]; //队头结点出队printf("%c ",q->Data); //访问队头结点if (q->Left != NULL) {//如果左子树不空，则左子树的根节点入队rear = (rear + 1)%MaxSize;que[rear] = q->Left;}if (q->Right != NULL) {//如果右子树不空，则右子树的根节点入队rear = (rear + 1)%MaxSize;que[rear] = q->Right;}}}}int main() {BinTree BT;ElementType X;printf("23、 编写算法，实现层序遍历二叉树。\n");printf("\n请输入二叉树结点(前序,#代替空结点)[例如 ABD###CE##F##]:\n");CreateBT(&BT);printf("\n层序遍历：");LevelorderTraversal(&BT);printf("\n");system("pause");return 0;}
24、 编写算法，计算一棵二叉树的高度。
//24、 编写算法，计算一棵二叉树的高度。#include <stdio.h>#include <stdlib.h>#define MaxSize 30typedef char ElementType;typedef struct TNode {/* 树结点定义 */ElementType Data; /* 结点数据 */struct TNode *Left;/* 指向左子树 */struct TNode *Right; /* 指向右子树 */} TNode,*BinTree;//采用前序初始化二叉树//中序和后序只需改变赋值语句的位置即可void CreateBT(BinTree * BT) {char data;scanf("%c",&data);if (data!='#') {if (!((*BT)=(TNode*)malloc(sizeof(TNode)))) {printf("申请结点空间失败");return;} else {(*BT)->Data=data;//采用前序遍历方式初始化二叉树CreateBT(&((*BT)->Left));//初始化左子树CreateBT(&((*BT)->Right));//初始化右子树}} else {*BT=NULL;}}//求二叉树的高度int GetHeight(BinTree BT) {int HL, HR, MaxH;if(BT) {HL = GetHeight (BT->Left) ; /*求左子树的深度*/HR = GetHeight (BT->Right) ; /*求右子树的深度*/MaxH = (HL > HR) ? HL : HR; /*取左右 子树较大的深度*/return ( MaxH + 1 ) ; /*返回树的深度*/} elsereturn 0; /*空树深度为0 */}int main() {BinTree BT;ElementType X;printf("24、 编写算法，计算一棵二叉树的高度。\n");printf("\n请输入二叉树结点(前序,#代替空结点)[例如 ABD###CE##F##]:\n");CreateBT(&BT);printf("\n该二叉树高度为：%d\n", GetHeight(BT));printf("\n");system("pause");return 0;}
25、 编写算法，计算一棵二叉树的叶子结点个数。
//25、 编写算法，计算一棵二叉树的叶子结点个数。#include <stdio.h>#include <stdlib.h>#define MaxSize 30typedef char ElementType;typedef struct TNode {/* 树结点定义 */ElementType Data; /* 结点数据 */struct TNode *Left;/* 指向左子树 */struct TNode *Right; /* 指向右子树 */} TNode,*BinTree;//采用前序初始化二叉树//中序和后序只需改变赋值语句的位置即可void CreateBT(BinTree * BT) {char data;scanf("%c",&data);if (data!='#') {if (!((*BT)=(TNode*)malloc(sizeof(TNode)))) {printf("申请结点空间失败");return;} else {(*BT)->Data=data;//采用前序遍历方式初始化二叉树CreateBT(&((*BT)->Left));//初始化左子树CreateBT(&((*BT)->Right));//初始化右子树}} else {*BT=NULL;}}//求叶子结点个数int Leaf_num(BinTree BT) {int l,r;if (!BT) return 0;if (!BT->Left && !BT->Right) return 1;else {l = Leaf_num(BT->Left);r = Leaf_num(BT->Right);return l + r;}}int main() {BinTree BT;ElementType X;printf("25、 编写算法，计算一棵二叉树的叶子结点个数。\n");printf("\n请输入二叉树结点(前序,#代替空结点)[例如 ABD###CE##F##]:\n");CreateBT(&BT);printf("\n该二叉树叶子结点个数为：%d\n", Leaf_num(BT));printf("\n");system("pause");return 0;}
26、 编写算法，计算一棵二叉树的非叶子结点个数。
//26、 编写算法，计算一棵二叉树的非叶子结点个数。#include <stdio.h>#include <stdlib.h>#define MaxSize 30typedef char ElementType;typedef struct TNode {/* 树结点定义 */ElementType Data; /* 结点数据 */struct TNode *Left;/* 指向左子树 */struct TNode *Right; /* 指向右子树 */} TNode,*BinTree;//采用前序初始化二叉树//中序和后序只需改变赋值语句的位置即可void CreateBT(BinTree * BT) {char data;scanf("%c",&data);if (data!='#') {if (!((*BT)=(TNode*)malloc(sizeof(TNode)))) {printf("申请结点空间失败");return;} else {(*BT)->Data=data;//采用前序遍历方式初始化二叉树CreateBT(&((*BT)->Left));//初始化左子树CreateBT(&((*BT)->Right));//初始化右子树}} else {*BT=NULL;}}//求结点个数int Node_num(BinTree BT) {int left,right,n;if(!BT) {n = 0;return n;} else if(!BT->Left && !BT->Right) {n = 1;return n;} else {left = Node_num(BT->Left);right = Node_num(BT->Right);n = left + right + 1;return n;}}//求叶子结点个数int Leaf_num(BinTree BT) {int l,r;if (!BT) return 0;if (!BT->Left && !BT->Right) return 1;else {l = Leaf_num(BT->Left);r = Leaf_num(BT->Right);return l + r;}}int main() {BinTree BT;ElementType X;printf("26、 编写算法，计算一棵二叉树的非叶子结点个数。\n");printf("\n请输入二叉树结点(前序,#代替空结点)[例如 ABD###CE##F##]:\n");CreateBT(&BT);printf("\n该二叉树非叶子结点个数为：%d\n", Node_num(BT)-Leaf_num(BT));printf("\n");system("pause");return 0;}
27、 编写算法，交换一棵二叉树的左右子树。
//27、 编写算法，交换一棵二叉树的左右子树。#include <stdio.h>#include <stdlib.h>#define MaxSize 30typedef char ElementType;typedef struct TNode {/* 树结点定义 */ElementType Data; /* 结点数据 */struct TNode *Left;/* 指向左子树 */struct TNode *Right; /* 指向右子树 */} TNode,*BinTree;//采用前序初始化二叉树//中序和后序只需改变赋值语句的位置即可void CreateBT(BinTree * BT) {char data;scanf("%c",&data);if (data!='#') {if (!((*BT)=(TNode*)malloc(sizeof(TNode)))) {printf("申请结点空间失败");return;} else {(*BT)->Data=data;//采用前序遍历方式初始化二叉树CreateBT(&((*BT)->Left));//初始化左子树CreateBT(&((*BT)->Right));//初始化右子树}} else {*BT=NULL;}}// 交换二叉树每个结点的左孩子和右孩子。/*采用递归算法实现交换二叉树的左、右子树，首先交换结点的左孩子的左、右子树，然后交换结点的右孩子的左、右子树，最后交换结点的左、右孩子，当结点为空时递归结束(后序遍历的思想)*/void SwapLR (BinTree T) {BinTree temp;if (T) {SwapLR(T->Left) ;//递归地交换左子树SwapLR(T->Right);//递归地交换右子树temp=T->Left;//交换左、右孩子结点T->Left=T->Right;T->Right=temp;}}//先序遍历void PreorderTraversal( BinTree BT ) {if( BT ) {printf("%c ", BT->Data );PreorderTraversal( BT->Left );PreorderTraversal( BT->Right );}}int main() {BinTree BT;ElementType X;printf("27、 编写算法，交换一棵二叉树的左右子树。\n");printf("\n请输入二叉树结点(前序,#代替空结点)[例如 ABD###CE##F##]:\n");CreateBT(&BT);printf("\n先序遍历：");PreorderTraversal(BT);printf("\nafter 交换左右子树：");SwapLR (BT);PreorderTraversal(BT);printf("\n");system("pause");return 0;}
28、 编写算法，判断二棵二叉树是否相等。
//28、 编写算法，判断二棵二叉树是否相等。#include <stdio.h>#include <stdlib.h>#define MaxSize 30typedef char ElementType;typedef struct TNode {/* 树结点定义 */ElementType Data; /* 结点数据 */struct TNode *Left;/* 指向左子树 */struct TNode *Right; /* 指向右子树 */} TNode,*BinTree;//采用前序初始化二叉树//中序和后序只需改变赋值语句的位置即可void CreateBT(BinTree * BT) {char Data;scanf("%c",&Data);if (Data!='#') {if (!((*BT)=(TNode*)malloc(sizeof(TNode)))) {printf("申请结点空间失败");return;} else {(*BT)->Data=Data;//采用前序遍历方式初始化二叉树CreateBT(&((*BT)->Left));//初始化左子树CreateBT(&((*BT)->Right));//初始化右子树}} else {*BT=NULL;}}int IsEqual(BinTree T1,BinTree T2) {if(!T1 && !T2) //T1和T2都为空return 1;if(!T1 || !T2) //T1，T2有一颗为空，一颗不为空return 0;if(T1 && T2) {if(T1->Data != T2->Data)return 0;int l = IsEqual(T1->Left,T2->Left);int r = IsEqual(T1->Right,T2->Right);return l && r;}}int main() {printf("28、 编写算法，判断二棵二叉树是否相等。\n");BinTree T1,T2;printf("\n输入第一棵树结点(前序,#代替空结点)[例如 ABD###CE##F##]：");CreateBT(&T1);getchar();printf("\n输入第二棵树结点(前序,#代替空结点)[例如 ABD###CE##F##]：");CreateBT(&T2);getchar();printf("\n");if(IsEqual(T1,T2) == 1)printf("\nT1和T2这两棵树相等\n");elseprintf("\nT1和T2这两棵树不相等\n");printf("\n");system("pause");return 0;}
29、 编写算法，完成将一棵二叉树进行复制。
//29、 编写算法，完成将一棵二叉树进行复制。#include <stdio.h>#include <stdlib.h>#define MaxSize 30typedef char ElementType;typedef struct TNode {/* 树结点定义 */ElementType Data; /* 结点数据 */struct TNode *Left;/* 指向左子树 */struct TNode *Right; /* 指向右子树 */} TNode,*BinTree;//采用前序初始化二叉树//中序和后序只需改变赋值语句的位置即可void CreateBT(BinTree * BT) {char Data;scanf("%c",&Data);if (Data!='#') {if (!((*BT)=(TNode*)malloc(sizeof(TNode)))) {printf("申请结点空间失败");return;} else {(*BT)->Data=Data;//采用前序遍历方式初始化二叉树CreateBT(&((*BT)->Left));//初始化左子树CreateBT(&((*BT)->Right));//初始化右子树}} else {*BT=NULL;}}BinTree copyTree(BinTree t) {BinTree l,r,p;if(t==NULL)return NULL;l=copyTree(t->Left);r=copyTree(t->Right);p=(TNode*)malloc(sizeof(TNode));p->Data=t->Data;p->Left=l;p->Right=r;return p;}//先序遍历void PreorderTraversal( BinTree BT ) {if( BT ) {printf("%c ", BT->Data );PreorderTraversal( BT->Left );PreorderTraversal( BT->Right );}}int main() {printf("29、 编写算法，完成将一棵二叉树进行复制。\n");BinTree T1,T2;printf("\n输入第一棵树结点(前序,#代替空结点)[例如 ABD###CE##F##]：");CreateBT(&T1);getchar();printf("\n复制T1至T2,先序遍历T2：\n");T2 = copyTree(T1);PreorderTraversal(T2);printf("\n");system("pause");return 0;}
30、 编写算法，判断二棵二叉树是否形态相似。
//30、 编写算法，判断二棵二叉树是否形态相似。#include <stdio.h>#include <stdlib.h>#define MaxSize 30typedef char ElementType;typedef struct TNode {/* 树结点定义 */ElementType Data; /* 结点数据 */struct TNode *Left;/* 指向左子树 */struct TNode *Right; /* 指向右子树 */} TNode,*BinTree;//采用前序初始化二叉树//中序和后序只需改变赋值语句的位置即可void CreateBT(BinTree * BT) {char Data;scanf("%c",&Data);if (Data!='#') {if (!((*BT)=(TNode*)malloc(sizeof(TNode)))) {printf("申请结点空间失败");return;} else {(*BT)->Data=Data;//采用前序遍历方式初始化二叉树CreateBT(&((*BT)->Left));//初始化左子树CreateBT(&((*BT)->Right));//初始化右子树}} else {*BT=NULL;}}int similar(BinTree t1,BinTree t2) {if(t1==NULL || t2==NULL) {return (t1==NULL)&&(t2==NULL);}return similar(t1->Left,t2->Left) && similar(t1->Right,t2->Right);}//先序遍历void PreorderTraversal( BinTree BT ) {if( BT ) {printf("%c ", BT->Data );PreorderTraversal( BT->Left );PreorderTraversal( BT->Right );}}int main() {printf("30、 编写算法，判断二棵二叉树是否形态相似。\n");BinTree T1,T2;printf("创建T1：先序输入节点创建二叉树(以#虚设节点)：\n");CreateBT(&T1);getchar(); //承接回车符，吃掉回车printf("创建T2：先序输入节点创建二叉树(以#虚设节点)：\n");CreateBT(&T2);getchar(); //承接回车符，吃掉回车if(similar(T1,T2))printf("T1和T2相似！");else printf("T1和T2不相似!");printf("\n");system("pause");return 0;}
31、 为二叉链表的节点增加Descnum域，编写一个算法，求二叉树的每个节点的子孙数目并存入Descnum域。
//31、 为二叉链表的节点增加Descnum域，编写一个算法，求二叉树的每个节点的子孙数目并存入Descnum域。#include <stdio.h>#include <stdlib.h>#define MaxSize 30typedef char ElementType;typedef struct TNode {/* 树结点定义 */ElementType Data; /* 结点数据 */int Descnum;//31题，结点的子孙数目struct TNode *Left;/* 指向左子树 */struct TNode *Right; /* 指向右子树 */} TNode,*BinTree;//采用前序初始化二叉树//中序和后序只需改变赋值语句的位置即可void CreateBT(BinTree * BT) {char Data;scanf("%c",&Data);if (Data!='#') {if (!((*BT)=(TNode*)malloc(sizeof(TNode)))) {printf("申请结点空间失败");return;} else {(*BT)->Data=Data;//采用前序遍历方式初始化二叉树CreateBT(&((*BT)->Left));//初始化左子树CreateBT(&((*BT)->Right));//初始化右子树}} else {*BT=NULL;}}int d = 0;int Descnum(BinTree &T) {if (T == NULL)return -1;elsed = Descnum(T->Left) + Descnum(T->Right) + 2;T->Descnum= d;return d;}//先序遍历Descnum域void PreOrderDescnum(BinTree T) {if (T == NULL) {return;} else {printf("%d ", T->Descnum);PreOrderDescnum(T->Left);PreOrderDescnum(T->Right);}}//先序遍历void PreorderTraversal( BinTree BT ) {if( BT ) {printf("%c ", BT->Data );PreorderTraversal( BT->Left );PreorderTraversal( BT->Right );}}int main() {printf("31、 为二叉链表的节点增加Descnum域，编写一个算法，求二叉树的每个节点的子孙数目并存入Descnum域。\n");BinTree T;printf("创建T：先序输入节点创建二叉树(以#虚设节点)：\n");CreateBT(&T);getchar(); //承接回车符，吃掉回车Descnum(T);printf("先序遍历二叉树：");PreorderTraversal(T);printf("\n");printf("先序遍历二叉树Descnum域：");PreOrderDescnum(T);printf("\n");system("pause");return 0;}
32、 编写算法，计算一棵以孩子兄弟表示法存储的树的高度。
//32、 编写算法，计算一棵以孩子兄弟表示法存储的树的高度。#include <stdio.h>#include <stdlib.h>typedef char TElemType;typedef struct tnode {TElemType data;struct tnode *child,*brother;} tnode,*bitree;void create(bitree &t) {char ch;scanf("%c",&ch);getchar();if(ch == '#')t=NULL;else {t=(tnode*)malloc(sizeof(tnode));t->data=ch;printf("输入 %c 的孩子结点：",ch);create(t->child);printf("输入 %c 的兄弟结点：",ch);create(t->brother);}}int depth(bitree t) {int i,j=0;if(!t)return 0;i=1+depth(t->child);j=depth(t->brother);return (i>j)?i:j;}int main() {bitree t;printf("32、 编写算法，计算一棵以孩子兄弟表示法存储的树的高度。\n");printf("输入根节点：");create(t);printf("这棵树的高度: %d",depth(t));printf("\n");system("pause");return 0;}
33、 给出哈夫曼树的构造算法。
//33、 给出哈夫曼树的构造算法。#include <stdio.h>#include <stdlib.h>typedef struct HTNode {int weight;int parent;int lchild;int rchild;}HTNode, * HuffmanTree;void Select(HuffmanTree HT, int m, int* s1, int* s2) {int i;//从下标为1的位置开始计数int min1 = 1000;int min2 = 1000;//规定一个特别大的数for (i = 1; i <= m; i++) {if (HT[i].parent == 0 && min1 > HT[i].weight) {min1 = HT[i].weight;*s1 = i;}}for (i = 1; i <= m; i++) {//注意这个I!=*s1标记minif (i != (*s1) && HT[i].parent == 0)if (HT[i].weight < min2) {min2 = HT[i].weight;*s2 = i;}}}void CreateHuffmanTree(HuffmanTree* HT, int n) {if (n <= 1)return;int i;int s1, s2;*(HT) = (HTNode*)malloc(2 * n * sizeof(HTNode));//huffmantree有其他辅助结点 for (i = 0; i <= 2 * n; i++) {(*HT)[i].lchild = 0; (*HT)[i].parent = 0; (*HT)[i].rchild = 0;}printf("请输入这%d个结点的weight：",n);for (i = 1; i <= n; i++)scanf("%d", &(*HT)[i].weight);for (i = n + 1; i < 2 * n; i++) {//进行n-1次的结合 //最后一个位置为2n-1Select(*HT, i - 1, &s1, &s2);(*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight;(*HT)[s1].parent = i;(*HT)[s2].parent = i;(*HT)[i].lchild = s1;(*HT)[i].rchild = s2;}}void outHuffmanTree(HuffmanTree HT, int n) {if (HT == NULL)printf("无huffmantree\n");int i;printf("输出huffmantree表格\n");printf("结点 weight parent lchild rchild\n");for (i = 1; i < 2 * n; i++) {//是2n-1个结点，申请了2n个位置0-2n-1（这是2n个用1-2n-1）printf("%2d %6d %6d %6d %6d\n", i, HT[i].weight, HT[i].parent, HT[i].lchild, HT[i].rchild);}}int main() {printf("33、 给出哈夫曼树的构造算法。\n");int n;HuffmanTree HT;printf("下面进行huffmantree的创建\n请输入你想要输入的结点个数:\n");scanf("%d", &n);CreateHuffmanTree(&HT, n);printf("创建Huffman tree完成\n");outHuffmanTree(HT, n);system("pause");return 0;}
34、 假定以二叉链表存放一颗哈夫曼树，编写算法计算其WPL值。
//34、 假定以二叉链表存放一颗哈夫曼树，编写算法计算其WPL值。#include<stdio.h>#include<stdlib.h>typedef struct BiTNode {int data;struct BiTNode* lChild;struct BiTNode* rChild;} BiTNode, * BiTree;void CreateBiTree(BiTree& T) {int ch;scanf("%d", &ch);if (ch == -1) {T = NULL;return;} else {T = (BiTree)malloc(sizeof(BiTNode));T->data = ch;printf("输入%d的左子节点：", ch);CreateBiTree(T->lChild);printf("输入%d的右子节点：", ch);CreateBiTree(T->rChild);}return;}int WPL = 0;void GetWPL(BiTree HT, int Deep = 0) {if (HT != NULL) {//对叶子节点进行计算if ((HT->lChild == NULL) && (HT->rChild == NULL)) {WPL += (HT->data) * Deep;}GetWPL(HT->lChild, Deep + 1);GetWPL(HT->rChild, Deep + 1);}}int main() {printf("34、 假定以二叉链表存放一颗哈夫曼树，编写算法计算其WPL值。\n");BiTree HT;//课本P137 图5.25（c）的例子，a=7,b=5,c=2,d=4.WPL=35。此时这棵树是哈夫曼树，输入结果是0 7 -1 -1 0 5 -1 -1 0 2 -1 -1 4 -1 -1。0表示没有数值printf("请输入第一个节点的值，-1表示没有叶节点：\n");CreateBiTree(HT);GetWPL(HT, 0);printf("WPL=%d\n",WPL);system("pause");return 0;}
35、 编写算法，实现在一个单链表中查找关键字为K的元素，若查找成功，返回TRUE，并将查找到的结点调整到表头，否则返回FALSE。
//35、 编写算法，实现在一个单链表中查找关键字为K的元素，若查找成功，返回TRUE，并将查找到的结点调整到表头，否则返回FALSE。#include<stdio.h>#include <stdlib.h>typedef struct LNode {int data;struct LNode* next;}LNode, * LinkList;void creatL(LinkList& L, int a[], int n) {LNode* r;LNode* p;L = (LinkList)malloc(sizeof(LNode));L->next = NULL;r = L;for (int i = 0; i < n; i++) {p = (LinkList)malloc(sizeof(LNode));p->next = NULL;p->data = a[i];r->next = p;r = p;}}//单链表查找算法bool ListLocate(LinkList L, int k){LNode* p1 = L;while (p1->next) {if (p1->data == k) {int temp;temp = L->next->data;L->next->data = p1->data;p1->data = temp;return true;}else {p1 = p1->next;}if (p1 == L) {return false;}}}int main() {printf("35、 编写算法，实现在一个单链表中查找关键字为K的元素，若查找成功，返回TRUE，并将查找到的结点调整到表头，否则返回FALSE。\n");LNode* L;int a[5] = {1,3,5,7,9 };creatL(L, a, 5);LNode* read;read = L->next;while (read) {printf("%d ", read->data);read = read->next;}printf("\n");read = L->next;ListLocate(L, 5);while (read) {printf("%d ", read->data);read = read->next;}system("pause");return 0;}
36、 给出折半查找的非递归算法。
37、 给出折半查找的递归算法。
//36、 给出折半查找的非递归算法。//37、 给出折半查找的递归算法。#include<stdio.h>#include <stdlib.h>//折半查找 非递归实现int BinSearch1(int r[], int n, int k) {int mid, low = 1, high = n;while (low <= high) {mid = (low + high) / 2;if (k < r[mid])high = mid - 1;else if (k > r[mid])low = mid + 1;else return mid;}return 0;}//折半查找递归实现int BinSearch2(int r[], int low, int high, int k) {int mid;if (low > high)return 0;else {mid = (low + high) / 2;if (k < r[mid])return BinSearch2(r, low, mid - 1, k);else if (k > r[mid])return BinSearch2(r, mid + 1, high, k);else return mid;}}int main() {printf("36、 给出折半查找的非递归算法。\n");printf("37、 给出折半查找的递归算法。\n");int r[10] = {0,7,14,18,21,23,29,31,35,38 };int k, i;printf("元素序列为：\n");for (i = 1; i < 10; i++)printf("%5d", r[i]);printf("\n请输入要查找的元素值：");scanf("%d", &k);//36题 折半查找的非递归方法if (BinSearch1(r, 9, k) == 0)printf("非递归方法:查找失败：查找表中无该元素\n");elseprintf("非递归方法:查找该元素所在位置为：%d\n", BinSearch1(r, 9, k));//37 折半查找的递归方法if (BinSearch2(r, 1, 9, k) == 0)printf("递归方法:查找失败：查找表中无该元素\n");elseprintf("递归方法查找该元素所在位置为：%d\n", BinSearch2(r, 1, 9, k));system("pause");return 0;}
38、 给出索引顺序表的分块查找算法。
//38、 给出索引顺序表的分块查找算法。#include<stdio.h>#include <stdlib.h>struct index {//定义块的结构int key; //块的关键字int start; //块的起始值int end; //块的结束值} index_table[4]; //定义结构体数组//自定义实现分块查找int block_search(int key,int a[]) {int i,j;i=1;while(i<=3&&key>index_table[i].key) //确定在哪个块中i++;if(i>3) //大于分得的块数，则返回0return 0;j=index_table[i].start; //j等于块范围的起始值while(j<=index_table[i].end&&a[j]!=key) //在确定的块内进行顺序查找j++;if(j>index_table[i].end) //如果大于块范围的结束值，则说明没有要査找的数，j置0j = 0;return j;}int main() {printf("38、 给出索引顺序表的分块查找算法。\n");int i,j=0,k,key,a[16];printf("请输入15个数(升序)：\n");for(i=1; i<16; i++)scanf("%d",&a[i]); //输入由小到大的15个数for(i=1; i<=3; i++) {index_table[i].start=j+1; //确定每个块范围的起始值j=j+1;index_table[i].end=j+4; //确定每个块范围的结束值j=j+4;index_table[i].key=a[j]; //确定每个块范围中元素的最大值}printf("请输入你想査找的元素：\n");scanf("%d",&key); //输入要查询的数值k=block_search(key,a); //调用函数进行杳找if(k!=0)printf("查找成功：其位置是：%d\n",k); //如果找到该数，则输出其位置elseprintf("查找失败：查找表中无该元素!\n"); //若未找到，则输出提示信息system("pause");return 0;}
39、 给出二叉排序树的插入算法。
40、 给出二叉排序树的删除算法。
具体见/lei/article/details/117487372?spm=1001..3001.5501
41、 编写一个高效算法，使得一个整型数组中的所有负数排在正数之前。
/*41、 编写一个高效算法，使得一个整型数组中的所有负数排在正数之前。*/#include <stdio.h>#include <string.h>#include <stdlib.h>typedef int elemtype;typedef struct {elemtype *elem;int length;} Sqlist;void initList(Sqlist &list,int n) {/*创建顺序存储数组*/list.elem=new int[n+1];if(!list.elem)return;list.length=n;}void ListInsert(Sqlist &list,int i,int num) {/*插入数据*/if(i<1)return;list.elem[i]=num;}void outputList(Sqlist list) {/*输出顺序存储的数组*/for(int i=1; i<=list.length; i++) {printf("%4d",list.elem[i]);if(i%10==0)printf("\n");}printf("\n");}int findlow(Sqlist &list,int low,int high) {elemtype temp;list.elem[0]=list.elem[low];temp=list.elem[low];while(low<high) {while(low<high && list.elem[high]>=temp)--high;list.elem[low]=list.elem[high];while(low<high && list.elem[low]<=temp)++low;list.elem[high]=list.elem[low];}list.elem[low]=list.elem[0];return low;}void qlsort(Sqlist &list,int low,int high) {int mid;if(low<high) {mid=findlow(list,low,high);qlsort(list,low,mid-1);qlsort(list,mid+1,high);}}/*快速排序*/void quicksort(Sqlist &list) {qlsort(list,1,list.length);}int main() {Sqlist list1;printf("41、 编写一个高效算法，使得一个整型数组中的所有负数排在正数之前。\n");int num,input;printf("请输入需要输入的数的个数:");scanf("%d",&num);if(num!=0) {initList(list1,num);printf("请输入需要输入的数据:\n");for(int i=1; i<=num; i++) {scanf("%d",&input);ListInsert(list1,i,input);}printf("\nBefore sorted:\n");outputList(list1);quicksort(list1);printf("After sorted:\n");outputList(list1);} elseprintf("\n输入的个数为0!\n");system("pause");return 0;}
42、 给出顺序存储结构下的直接插入排序算法。
/*42、 给出顺序存储结构下的直接插入排序算法。*/#include <stdio.h>#include <stdlib.h>#define RSize 2000int n,R[RSize];//直接插入排序void InsertSort(int R[],int n) {//待排关键字存储在R[]中，默认为整型，个数为nint i,j,temp; //老师的程序用R[0]做哨兵，这里用临时变量temp存for (i=2; i<=n; ++i) {//n个数据只需要排n-1次即可temp=R[i] ;//将待插入关键字暂存于temp中j=i-1;/*下面这个循环完成了从待排关键字之前的关键字开始扫描，如果大于待排关键字，则后移一位*/while (j>=0&&temp<R[j]) {R[j+1]=R[j] ;--j;}R[j+1]=temp; //找到插入位置， 将temp中暂存的待排关键字插入}}//输出n个数的函数,格式控制每10个一行void put_data(int R[],int n) {int i;printf("\n");for(i=1; i<=n; i++) {printf("%6d",R[i]);if(!(i%10))printf("\n");}printf("\n");}int main() {printf("42、 给出顺序存储结构下的直接插入排序算法。\n");printf("请依次输入若干个非负整数(以-9999作为结束输入标志)：");int i=1,data;fflush(stdin);while(1) {scanf("%d",&data);if(data == -9999) break;R[i++]=data;}n=i-1;printf("\n输入的%d个待排序整数如下：\n",n);put_data(R,n);printf("after直接插入排序：\n");InsertSort(R,n);put_data(R,n);system("pause");return 0;}
43、 给出以单链表为存储结构的直接插入排序算法。
/*43、 给出以单链表为存储结构的直接插入排序算法。*///单链表上实现直接插入排序//输入任意N个数,按“回车”结束输入。递增排序后输出（若要实现递减,修改"l1->data<l2->data"为“l1->data>l2->data”）。#include <stdio.h>#include <stdlib.h>typedef struct node {//定义单链表结点int data; //数据域struct node *next;//指针域} linklist;void creatlist(linklist *head) {//尾插法建立单链表linklist *p,*q;//p是指向新分配节点的指针，q是已分配链表尾指针int i=0;int x=0;int j=0;printf("please input the node:\n");while(1) {scanf("%d",&x);p=(linklist *)malloc(sizeof(linklist));p->data=x;if(++i==1) {//头指针指向第一个结点head->next=p;} else {//链入新结点q->next=p;}q=p;//更新尾指针q->next=NULL; //尾指针置空if(getchar()=='\n') {//按回车结束输入break;}}}void sortlist(linklist *head) {//插入排序在单链表上的实现linklist *newhead, *pre, *l1, *l2,*l;l1=head->next; //变量p用来存放链L1的头结点地址newhead=l1->next; //newhead用来标记链L2的头结点的地址l1->next=NULL; //将原来的链L断开while(newhead) {//判断：1.原链L中元素不少于两个。2.新链L2中还有元素未插入L1l2=newhead; //l2指向待插入结点（链L2的头结点）newhead=newhead->next; //l2去掉头结点后头指针后移pre=head; //pre指向链L1待插入位置的前驱l1=head->next; //l1指向链L1待插入位置的后继while(l1!=NULL&&l1->data<l2->data) {//与L1中元素作比较pre=l1;//依次向后找合适的插入点l1=l1->next;}l2->next=l1;pre->next=l2;//将L2中元素链入L1中合适位置}l=head->next;printf("after 以单链表为存储结构的直接插入排序:\n") ;while(l) {//依次输出排序后链表元素printf("%d ",l->data);l=l->next;}printf("\n");}int main() {linklist *h;printf("43、 给出以单链表为存储结构的直接插入排序算法。\n") ;h=(linklist *)malloc(sizeof(linklist)); //建头结点h->next=NULL; //初始化头指针creatlist(h);sortlist(h);system("pause");return 0;}
44、 给出折半插入排序算法。
/*44、 给出折半插入排序算法。*/#include <stdio.h>#include <stdlib.h>#define RSize 2000int n,R[RSize];//折半插入排序void BInsertSort(int R[],int n) {int i,j,low,high,mid,temp;for(i=1; i<=n; i++) {temp=R[i];low=1;high=i-1;while(low<=high) {mid=(low+high)/2;if(temp>=R[mid])low=mid+1;elsehigh=mid-1;}for(j=i-1; j>=high+1; j--)R[j+1]=R[j];R[j+1]=temp;}}//输出n个数的函数,格式控制每10个一行void put_data(int R[],int n) {int i;printf("\n");for(i=1; i<=n; i++) {printf("%6d",R[i]);if(!(i%10))printf("\n");}printf("\n");}int main() {printf("44、 给出折半插入排序算法。\n");printf("请依次输入若干个整数(以-9999作为结束输入标志)：");int i=1,data;fflush(stdin);while(1) {scanf("%d",&data);if(data == -9999) break;R[i++]=data;}n=i-1;printf("\n输入的%d个待排序整数如下：\n",n);put_data(R,n);printf("after折半插入排序：\n");BInsertSort(R,n);put_data(R,n);system("pause");return 0;}
45、 给出SHELL排序算法。
//45、 给出SHELL排序算法。#include <stdio.h>#include <stdlib.h>#define RSize 2000int n,R[RSize];//希尔排序void SHELLSort(int R[],int n) {int i,j,d=n/2;int temp;while(d) {for(i=d; i<=n; i++) {temp=R[i];for(j=i-d; j>0 && R[j]>temp; j-=d)R[j+d]=R[j];R[j+d]=temp;}d/=2;}}//输出n个数的函数,格式控制每10个一行void put_data(int R[],int n) {int i;printf("\n");for(i=1; i<=n; i++) {printf("%6d",R[i]);if(!(i%10))printf("\n");}printf("\n");}int main() {printf("45、 给出SHELL排序算法。\n");printf("请依次输入若干个整数(以-9999作为结束输入标志)：");int i=1,data;fflush(stdin);while(1) {scanf("%d",&data);if(data == -9999) break;R[i++]=data;}n=i-1;printf("\n输入的%d个待排序整数如下：\n",n);put_data(R,n);printf("after希尔SHELL排序：\n");SHELLSort(R,n);put_data(R,n);system("pause");return 0;}
46、 给出冒泡排序算法。
//46、 给出冒泡排序算法。#include <stdio.h>#include <stdlib.h>#define RSize 2000int n,R[RSize];//冒泡排序void BubbleSort(int R[],int n) {//默认待排序关键字为整型int i, j,temp;int key;//有多少记录，就需要多少次冒泡，当比较过程，所有记录都按照升序排列时，排序结束for (i = 1; i <= n; i++) {key=0;//每次开始冒泡前，初始化 key 值为 0//每次起泡从下标为 1 开始，到 n-i+1 结束for (j = 1; j<n-i+1; j++) {if (R[j] > R[j+1]) {key=1;temp=R[j+1] ;R[j+1]=R[j] ;R[j]=temp;}}//如果 key 值为 0，表明表中记录排序完成if (key==0) {break;}}}//输出n个数的函数,格式控制每10个一行void put_data(int R[],int n) {int i;printf("\n");for(i=1; i<=n; i++) {printf("%6d",R[i]);if(!(i%10))printf("\n");}printf("\n");}int main() {printf("46、 给出冒泡排序算法。\n");printf("请依次输入若干个整数(以-9999作为结束输入标志)：");int i=1,data;fflush(stdin);while(1) {scanf("%d",&data);if(data == -9999) break;R[i++]=data;}n=i-1;printf("\n输入的%d个待排序整数如下：\n",n);put_data(R,n);printf("after冒泡排序：\n");BubbleSort(R,n);put_data(R,n);system("pause");return 0;}
47、 给出双向冒泡排序算法。
//47、 给出双向冒泡排序算法。#include<iostream>using namespace std;typedef struct node {int data;struct node *prior, *next;}*LinkList;//对存储在带头结点的双向链表L中的元素进行双向起泡排序。void TwoWayBubbleSort(LinkList &L){//双向冒泡，最大沉底，最小冒出int tag = 1;LinkList head = L;//双向链表头，算法过程中是向下起泡的开始结点LinkList tail = NULL;//双向链表尾，算法过程中是向上起泡的开始结点while(tag) {LinkList p = head->next;//p是工作指针，指向当前结点tag = 0;//假定本趟无交换while (p->next != tail) {//向下(右)起泡，一趟有一最大元素沉底if (p->data > p->next->data) {//交换两结点指针，涉及6条链LinkList temp = p->next;tag = 1;//有交换p->next = temp->next;if(temp->next)temp->next->prior = p;//先将结点从链表上摘下temp->next = p;p->prior->next = temp;//将temp插到p结点前temp->prior = p->prior;p->prior = temp;} else p = p->next; //无交换，指针后移}tail = p;//准备向上起泡p = tail->prior;while (tag&&p->prior != head) {//向上(左)起泡，一趟有一最小元素冒出if (p->data < p->prior->data) {//交换两结点指针，涉及6条链LinkList temp = p->prior;tag = 1;//有交换p->prior = temp->prior;temp->prior->next = p;//先将temp结点从链表上摘下temp->prior = p;p->next->prior = temp;//将temp插到p结点后(右)temp->next = p->next;p->next = temp;} else p = p->prior; //无交换，指针前移}head = p;//准备向下起泡}}void Create(LinkList &L, int n) {LinkList p, rear;L = new node;L->next = NULL;L->prior = NULL;rear = L;while (n--) {p = new node;cin>>p->data;p->next = rear->next;rear->next = p;p->prior = rear;rear = p;}}int main() {int n;cout << "47、 给出双向冒泡排序算法。" << endl;while (true) {cout << "请输入元素个数n" << endl;cin >> n;if (!n)break;else {LinkList L;cout << "请输入" <<n<<"个元素"<< endl;Create(L, n);TwoWayBubbleSort(L);cout << "after TwoWayBubbleSort：" << endl;LinkList p = L->next;while (p->next) {cout << p->data << " ";p = p->next;}cout << p->data << endl;}}return 0;}
48、 给出快速排序算法。
//48、 给出快速排序算法。#include <stdio.h>#include <stdlib.h>#define RSize 2000int n,R[RSize];//快速排序void QuickSort (int R[], int low, int high) {//对从R[low]到R [high]的关键字进行排序int temp;int i=low, j=high;if (low<high) {temp=R[low];/*下面这个循环完成了一趟排序，即将数组中小于temp的关键字放在左边，大于temp的关键字放在右边*/while(i<j) {while (j>i&&R[j]>=temp) --j;//从右往左扫描， 找到一个小于temp的关键字if(i<j) {R[i]=R[j];//放在temp左边++i;//i右移一位}while(i<j && R[i]<temp) ++i; //从左往右扫描，找到一个大于temp的关键字if (i<j) {R[j]=R[i] ;//放在temp右边--j;//j左移一位}}R[i]=temp;//将temp放在最终位置QuickSort (R, low, i-1) ;//递归地对temp左边的关键字进行排序QuickSort (R, i+1,high) ;//递归地对temp右边的关键字进行排序}}//输出n个数的函数,格式控制每10个一行void put_data(int R[],int n) {int i;printf("\n");for(i=1; i<=n; i++) {printf("%6d",R[i]);if(!(i%10))printf("\n");}printf("\n");}int main() {printf("48、 给出快速排序算法。\n");printf("请依次输入若干个整数(以-9999作为结束输入标志)：");int i=1,data;fflush(stdin);while(1) {scanf("%d",&data);if(data == -9999) break;R[i++]=data;}n=i-1;printf("\n输入的%d个待排序整数如下：\n",n);put_data(R,n);printf("after快速排序：\n");QuickSort(R,1,n);put_data(R,n);system("pause");return 0;}
49、 给出顺序存储结构下的简单选择排序算法。
//49、 给出顺序存储结构下的简单选择排序算法。#include <stdio.h>#include <stdlib.h>#define RSize 2000int n,R[RSize];//简单选择排序void SelectSort (int R[],int n) {int i,j,k;int temp;for (i=1; i<=n; ++i) {k=i;/*这个循环是算法的关键，它从无序序列中挑出一个最小的关键字*/for (j=i+1; j<=n; ++j)if (R[k]>R[j])k=j;/*下面3句完成最小关键字与无序序列第一个关键字的交换*/temp=R[i];R[i]=R[k];R[k]=temp;}}//输出n个数的函数,格式控制每10个一行void put_data(int R[],int n) {int i;printf("\n");for(i=1; i<=n; i++) {printf("%6d",R[i]);if(!(i%10))printf("\n");}printf("\n");}int main() {printf("49、 给出顺序存储结构下的简单选择排序算法。\n");printf("请依次输入若干个整数(以-9999作为结束输入标志)：");int i=1,data;fflush(stdin);while(1) {scanf("%d",&data);if(data == -9999) break;R[i++]=data;}n=i-1;printf("\n输入的%d个待排序整数如下：\n",n);put_data(R,n);printf("after简单选择排序（顺序存储结构）：\n");SelectSort(R,n);put_data(R,n);system("pause");return 0;}
50、 给出以单链表为存储结构的简单选择排序算法。
//50、 给出以单链表为存储结构的简单选择排序算法。#include <stdio.h>#include <stdlib.h>typedef int ElemType;typedef struct LNode {ElemType data;struct LNode *Next;}*link;//单链表实现简单选择排序void linkSelectSort(link head) {link p = (link )malloc(sizeof(struct LNode));p = head->Next;while(p != NULL) {link q = (link)malloc(sizeof(struct LNode));q = p->Next;link r = (link)malloc(sizeof(struct LNode));r = p;while(q != NULL) {if (q->data<r->data) r = q;q = q->Next;}if(r != p) {int a=p->data;p->data=r->data;r->data=a;}p = p->Next;}}void CreateLink(link head) {int elem;printf("input data(end of -999):");while(1) {scanf("%d",&elem);if(elem == -999) break;link p;p = (link)malloc(sizeof(struct LNode));p->data = elem;p->Next= head->Next;head->Next=p;}}void VisitLink(link head) {link p;p = head->Next;while(p != NULL) {printf("%d ",p->data);p = p->Next;}}int main() {link head;printf("50、 给出以单链表为存储结构的简单选择排序算法。\n");head = (link)malloc(sizeof(struct LNode));head->data = 0;head->Next = NULL;CreateLink(head);printf("The linklist before sort is ：\n");VisitLink(head);printf("\n");linkSelectSort(head);printf("after linkSelectSort:\n");VisitLink(head);system("pause");return 0;}
51、 给出堆排序算法。
//51、 给出堆排序算法。#include <stdio.h>#include <stdlib.h>#define RSize 2000int n,R[RSize];/*本函数完成在数组R[1ow]到R[high]的范围内对在位置low上的结点进行调整-----用于堆排序*/void Sift(int R[],int low,int high) {//这里 关键字的存储设定为从数组下标1开始int i=low,j=2*i;//R[j]是R[i]的左孩子结点int temp=R[i];while(j<=high) {if (j<high && R[j]<R[j+1])//若右孩子较大，则把j指向右孩子++j;//j变为2*i+1if (temp<R[j]) {R[i]=R[j];//将R[j]调整到双亲结点的位置上i=j;//修改i和j的值，以便继续向下调整j=2*i;} elsebreak;//调整结束}R[i]=temp;//被调整结点的值放入最终位置}/*堆排序函数*/void heapSort(int R[], int n) {int i;int temp;for (i=n/2; i>0; i--)//建立初始堆Sift (R,i,n);for (i=n; i>1; i--) {//进行n-1次循环，完成堆排序/*以下3句换出了根结点中的关键字，将其放入最终位置*/temp=R[1];R[1]=R[i];R[i]=temp;Sift(R,1,i-1);//在减少了1个关键字的无序序列中进行调整}}//输出n个数的函数,格式控制每10个一行void put_data(int R[],int n) {int i;printf("\n");for(i=1; i<=n; i++) {printf("%6d",R[i]);if(!(i%10))printf("\n");}printf("\n");}int main() {printf("51、 给出堆排序算法。\n");printf("请依次输入若干个整数(以-9999作为结束输入标志)：");int i=1,data;fflush(stdin);while(1) {scanf("%d",&data);if(data == -9999) break;R[i++]=data;}n=i-1;printf("\n输入的%d个待排序整数如下：\n",n);put_data(R,n);printf("after堆排序：\n");heapSort(R,n);put_data(R,n);system("pause");return 0;}
52、 给出归并排序算法。
//52、 给出归并排序算法。#include <stdio.h>#include <stdlib.h>#define RSize 2000int n,R[RSize];void merge(int R[],int R1[],int low,int mid,int high) {int i=low,j=mid+1,k=low;while(i<=mid&&j<=high)if(R[i]<=R[j]) R1[k++]=R[i++];else R1[k++]=R[j++];while(i<=mid) R1[k++]=R[i++];while(j<=high) R1[k++]=R[j++];}void mergepass(int R[],int R1[],int len,int n) {int i=1;while(i+2*len-1<=n) {merge(R,R1,i,i+len-1,i+2*len-1);i+=2*len;}if(i+len-1<n) merge(R,R1,i,i+len-1,n);elsewhile(i<=n) {R1[i]=R[i];i++;}}//二路归并排序void mergeSort(int R[],int n) {int *R1,len=1;R1=(int*)malloc(sizeof(int)*(n+1));while(len<n) {mergepass(R,R1,len,n);len*=2;mergepass(R1,R,len,n);len*=2;}}//输出n个数的函数,格式控制每10个一行void put_data(int R[],int n) {int i;printf("\n");for(i=1; i<=n; i++) {printf("%6d",R[i]);if(!(i%10))printf("\n");}printf("\n");}int main() {printf("52、 给出归并排序算法。\n");printf("请依次输入若干个整数(以-9999作为结束输入标志)：");int i=1,data;fflush(stdin);while(1) {scanf("%d",&data);if(data == -9999) break;R[i++]=data;}n=i-1;printf("\n输入的%d个待排序整数如下：\n",n);put_data(R,n);printf("after归并排序：\n");mergeSort(R,n);put_data(R,n);system("pause");return 0;}
