一 单链表 .................................................................................................. 1 1 链表的输入、输出和删除以及求链表的长度 ..................................................... 1 2 链表逆序 .............................................................................................. 3 3 链表合并 .............................................................................................. 5 4 从A链表中删去与B链表中有相同学号的那些结点 ............................................ 7 5 如果链表中的年龄与输入的年龄相等，则将该结点删去 ....................................... 8 6 链表排序 ............................................................................................ 11 7 遍历一次求链表的中间结点 ...................................................................... 12 8 判断一个单链表是否有环（不能用标志位，最多只能用两个额外指针） ................. 13 9 用链表输出三个学生的数据 ...................................................................... 15 10 链表实现建立，输出，删除，插入的操作 .................................................... 16 11 键盘输入10个整数，生成一个链表，按顺序输出链表中的结点的数值。然后输入一个待查找整数，找到则删除该整数所在的结点（多次出现则全部删除），然后输出删除结点以后的链表，在程序结束之前清空链表 ..................................................................... 20 二 双链表 ................................................................................................ 22 1 双链表的建立、删除、插入和输出 .............................................................. 22 三 环状链表（约瑟夫环） ............................................................................. 26 1 十三个人围成一个圈，从第一个人开始顺序报号1、2、3。凡是报到“3”者退出圈子，请找出最后留在圈子中的人原来的序号 ............................................................... 26 2 15个美国人和15个日本人围坐一圈，从其中一人开始数数，从1数到9，数到9的人踢出去，设计代码使被踢出的人都是日本人，输出日本人坐的位置 .............................. 28 3 已知N个人（以编号1，2，3...N分别表示）围坐在一张圆桌周围。从编号为K的人开始报数，数到M的那个人出列；他的下一个人又从1开始报数，数到M的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列 ....................................................... 29 四 树 ...................................................................................................... 33 1 建立二叉树 .......................................................................................... 33 2 二叉树根结点为ROOT,用递归法把二叉树的叶子结点按从左到右的顺序连成一个单链表 ............................................................................................................ 33 3 写一个求二叉树深度的算法 ...................................................................... 34 4 在已排序的二叉树中插入一个节点 .............................................................. 34 5 建立排序二叉树并中序遍历 ...................................................................... 35 五 堆、栈、队列 ........................................................................................ 37 1 入栈出栈 ............................................................................................ 37 2 入队出队 ............................................................................................ 38 3 用栈、队列和类设计一个程序，检查所输入的数据是不是回文数据，这串数据以点作为结束符 ...................................................................................................... 40 4 队列测长 ............................................................................................ 42 5 队列打印 ............................................................................................ 43
I
6 用两个队列实现一个栈的功能 ................................................................... 43 六 排序 ................................................................................................... 45 1 冒泡法排序 .......................................................................................... 45 2 选择法排序 .......................................................................................... 46 3 快速排序 ............................................................................................ 47 4 直接插入排序函数模板 ............................................................................ 48 5 直接选择排序函数模板 ............................................................................ 49 6 起泡排序函数模板 ................................................................................. 50 7 顺序查找函数模板 ................................................................................. 51 8 折半查找函数模板 ................................................................................. 51
II
一 单链表
1 链表的输入、输出和删除以及求链表的长度 #include typedef struct student { // 建立链表 void create(node *&head) //为什么参数是\"*&\"? { } // 求链表长度 1 int data; struct student *next; }node; node *p1,*p2; head=NULL; int n; cout<<\"输入数序(以负数或0结束): \"; cin>>n; while(n>0) { } p1=(node *)malloc(sizeof(node)); p1->data=n; p1->next=NULL; if(NULL==head) //将head, p1, p2都指向头结点 { } else { } cin>>n; p2->next=p1; p2=p1; head=p1; p2=head; int len(node *h) { int i=0; while(h!=NULL) { i++; h=h->next; } return i; } // 删除结点 void del(node *h,int i) { node *p,*q; p=h; if(i<1||i>len(h)) { return; } else if(i==1) { h=h->next; free(p); } else { while(i-->2) p=p->next; q=p->next; p->next=q->next; free(q); } } // 输出链表 void disp(node *h) { cout<<\"输出链表: \"; while(h!=NULL) { cout< cout< } void main() { } node *head; int i; create(head); disp(head); cout<<\"链表长度: \"< 2 链表逆序 #include struct node { }; typedef struct node Node; Node* ReverseList(Node *head) { int data; node *next; if(!head || !head->next) { } Node *p1 = head; 3 return head; } Node *p2 = p1->next; head->next = NULL; while(p2) { } return head; p1 = p2; p2 = p2->next; p1->next = head; head = p1; Node *RecReverseList(Node *head) { } int main (int argc, char * const argv[]) { Node a,b,c; a.data = 1, a.next = &b; b.data = 2, b.next = &c; c.data = 3, c.next = NULL; Node *tmp = &a; while(tmp) { } cout << endl; tmp = RecReverseList(&a); while(tmp) { cout << tmp->data<<\" \"; tmp = tmp->next; cout << tmp->data<<\" \"; tmp = tmp->next; if(!head || !head->next) { } Node *newhead = RecReverseList(head->next); head->next->next = head; head->next = NULL; return newhead; return head; 4 } } cout << endl; return 0; 输出结果： 1 2 3 3 2 1 3 链表合并 (1) 已知两个链表head1 和head2 各自有序，请把他们合并成一个有序链表。(保留所有结点，即便大小相同） Node *Merge(Node *head1 , Node *head2) { if(NULL==head1) return head2; return head1; if(NULL==head2) Node *head=NULL; Node *p1=NULL; Node *p2=NULL; // 获取头结点 if(head1->data Node *pcurrent=head; while(p1!=NULL&&p2!=NULL) { if(p1->data<=p2->data) { 5 head=head1; p1=head1->next; p2=head2; head=head2; p2=head2->next; p1=head1; } } } pcurrent->next=p1; pcurrent=p1; p1=p1->next; else { } pcurrent->next=p2; pcurrent=p2; p2=p2->next; // 剩余结点 if(p1!=NULL) pcurrent->next=p1; pcurrent->next=p2 ; if(p2!=NULL) return head ; (2) 已知两个链表head1 和head2 各自有序，请用递归方法把它们合并成一个有序链表。 (Autodesk) Node *MergeRecursive(Node *head1,Node *head2) { } if(head1->data return head; head=head2; head->next=MergeRecursive(head1,head2->next); head=head1; head->next=MergeRecursive(head1->next,head2); if(head1==NULL) return head2; return head1; if(head2==NULL) Node *head=NULL; 6 4 从a链表中删去与b链表中有相同学号的那些结点 #include struct student { void main() { struct struct student student a[LA]={{\"101\ b[LB]={{\"103\u\ char num[6]; char name[8]; struct student *next; }a[LA],b[LB]; int i; struct student *p,*p1,*p2,*head1,*head2; /*初始化*/ head1=a; head2=b; printf(\"List a:\\n\"); for(p1=head1,i=1;p1 for(p2=head2,i=1;p2 p=p1; p1->next=a+i; printf(\"%8s%8s\\n\p1=p1->next; p=p2; p2->next=b+i; printf(\"%8s%8s\\n\p2=p2->next; } p->next=NULL; printf(\"\\n\"); /*删除*/ p1=head1; while(p1!=NULL) { } /*输出*/ p1=head1; printf(\"\\nresult:\\n\"); while(p1!=NULL) { } printf(\"%7s%7s\\n\p1=p1->next; p2=head2; while(p2!=NULL&&strcmp(p1->num,p2->num)!=0) p2=p2->next; if(p1==head1) head1=p1->next; p->next=p1->next; else if(strcmp(p1->num,p2->num)==0) //此句编译无法通过 p=p1; p1=p1->next; 5 如果链表中的年龄与输入的年龄相等，则将该结点删去 #include #define LEN sizeof(struct student) 8 struct student { void main() { /*输入节点个数*/ int flag=1; int length; while(flag==1) { } /*建立链表*/ int i; struct student*p,*pt,*head; for(i=0;i p=(struct student *) malloc(LEN); if(i==0) head=pt=p; pt->next=p; else pt=p; printf(\"NO:\"); scanf(\"%s\printf(\"name:\"); scanf(\"%s\printf(\"sex:\"); scanf(\"%s\printf(\"age:\"); scanf(\"%d\ printf(\"Input length of list struct student *next; }stu[10]; 9 printf(\"\\n NO. name sex age\\n\"); while(p!=NULL) { } /*删除*/ int delAge; int find=0; printf(\"Input delete age:\"); scanf(\"%d\p=pt=head; if(pt->age==delAge) /*链头是待删元素*/ { } else /*链头不是待删元素*/ { } while(pt!=NULL) { } /*没找到对应的要删除的年龄*/ if(!find) { } /*输出删除之后的链表*/ else { p=head; printf(\"Age %d not found!\\n\if(pt->age==delAge) { } else /*中间结点不是待删元素*/ { } pt=pt->next; p=pt; p->next=pt->next; find=1; pt=pt->next; p=pt->next; head=pt=p; find=1; /* find为1时表示找到待删年龄，为0表示未找到*/ printf(\"%4s%9s%7s%7d\\n\p=p->next; 10 } } printf(\"\\n NO. name sex age\\n\"); while(p!=NULL) { } printf(\"%4s%9s%6s%8d\\n\p=p->next; 6 链表排序 node *sort(node *head) { node *p; int n; n=length(head); if(head==NULL||head->next==NULL) return head; p=head; for(int j=0;j for(int i=0;i 11 } } } } p->data = p->data ^ p->next->data; p->next->data = p->data ^ p->next->data; p->data = p->data ^ p->next->data; p=p->next; return head; 7 遍历一次求链表的中间结点 #include struct node { int data; node* next; node(int data):next(NULL),data(data) { } }; node* CreateLink(int num) { node* head = new node(-1); node* temp = head; for(int i = 0; i < num; i++) { head = head->next = new node(i); } return temp; } void Print(const node* head) { while(head != NULL) { cout << head->data << \" \"; head = head->next; 12 } cout << endl; } node* find_mid_element(node* head) { if(NULL == head) return NULL; node* mid = head; node* p = mid->next; while(NULL != p && NULL != p->next) { mid = mid->next; p = p->next->next; } return mid; } int main(int argc,char* argv[]) { node* h = CreateLink(100); Print(h); } 输出结果： -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 49 8 判断一个单链表是否有环（不能用标志位，最多只能用两个额外指针） #include cout< 13 typedef struct list { int data; struct list *next; } LIST; /* Method 1: check the occurrence of p->next from head to p */ int check_circle_1(LIST *head) { LIST *p = head, *q= NULL; if (p == NULL) return 0; { while (p->next) /* check whether p points to itself */ if (p->next == p) { return 1; } /* check the occurrence of p->next in head to p */ q = head; while (q != p) { if (q == p->next) { return 1; } q = q->next; } p = p->next; } /* p->next is NULL, not a circle */ return 0; } /* Method 2: q goes faster than p, if at last p == q, means there's circle */ /* 优点：逻辑上简单。 缺点：无法具体知道从哪个点拆开该圈 */ int check_circle_2(LIST *head) { 14 LIST *p, *q; p = head; if (p == NULL) return 0; { { q = p->next; while (p != NULL && q != NULL) if (p == q) return 1; } p = p->next; if (q->next == NULL) { return 0; } else { q = q->next->next; } } return 0; } int main() { LIST a, b, c, *head = &a; a.next = &b; b.next = &c; c.next = &a; printf(\"%d\\n\", check_circle_1(head)); printf(\"%d\\n\", check_circle_2(head)); } 9 用链表输出三个学生的数据 源程序： #include long num; 15 }; float score; struct student *next; int main() { } 输出结果： struct student a,b,c,*head,*p; a.num=99101; a.score=89.5; b.num=99103; b.score=90; c.num=99107; c.score=85; head=&a; a.next=&b; b.next=&c; c.next=NULL; p=head; do { printf(\"%ld %.1f\\n\p=p->next; }while(p!=NULL); 10 链表实现建立，输出，删除，插入的操作 #include #define LEN sizeof(struct student) struct student { }; int n; long num; float score; struct student *next; 16 struct student *creat(void) //建立链表 { } void print(struct student *head) //打印链表数据 { } struct student *del(struct student *head,long num) //删除链表数据 { struct student *p1,*p2; if(head==NULL) {printf(\"\\nList null!\\n\"); } p1=head; while(num!=p1->num&&p1->next!=NULL) { p2=p1; struct student *p; printf(\"\\nNow,These %d records are: \\n\p=head; if(head!=NULL) { } do { printf(\"%ld,%.1f\\n\p=p->next; struct student *head; struct student *p1,*p2; n=0; p1=p2=(struct student *)malloc(LEN); //开辟一个新单元 scanf(\"%ld,%f\head=NULL; while(p1->num!=0) { } p2->next=NULL; return(head); n=n+1; if(n==1) head=p1; else p2->next=p1; p2=p1; p1=(struct student *)malloc(LEN); scanf(\"%ld,%f\ }while(p!=NULL); 17 } } p1=p1->next; if(num=p1->num) { } else { } return(head); printf(\"%ld not been found!\\n\if(p1==head) head=p1->next; p2->next=p1->next; else printf(\"delete: %ld\\n\n=n-1; //插入链表数据 struct student *insert(struct student *head,struct student *stud) { struct student *p0,*p1,*p2; p1=head; p0=stud; if(head==NULL) { } else { while((p0->num>p1->num)&&(p1->next!=NULL)) { } if(p0->num<=p1->num) { } else { if(head==p1) head=p0; else p2->next=p0; p0->next=p1; p2=p1; p1=p1->next; head=p0; p0->next=NULL; 18 } } p1->next=p0; p0->next=NULL;} n=n+1; return(head); int main() { } struct student *head,*stu; long del_num; printf(\"input records:\\n\"); head=creat(); //返回头指针 print(head); //输出全部结点 printf(\"\\ninput the deleted number:\"); scanf(\"%ld\while(del_num!=0) { } printf(\"\\ninput the inserted record:\"); stu=(struct student *)malloc(LEN); scanf(\"%ld,%f\while(stu->num!=0) { } head=insert(head,stu); print(head); printf(\"\\ninput the inserted record:\"); stu=(struct student *)malloc(LEN); scanf(\"%ld,%f\head=del(head,del_num); print(head); printf(\"\\ninput the deleted number:\"); scanf(\"%ld\ 19 11 键盘输入10个整数，生成一个链表，按顺序输出链表中的结点的数值。然后输入一个待查找整数，找到则删除该整数所在的结点（多次出现则全部删除），然后输出删除结点以后的链表，在程序结束之前清空链表 源程序： #include int main() { list for(i=0;i<10;i++) //输入10个整数依次向表头插入 20 } { } cout<<\"List:\"; //输出链表 list cout< Link.remove(key); cout<<\"List:\"; p=Link.begin(); while(p!=Link.end()) { } cout< cout<<*p<<\" \"; p++; cin>>item; Link.push_front(item); 输出结果： 21 二 双链表 1 双链表的建立、删除、插入和输出 //本程序C和C++混用 #include typedef struct person { //建立双链表 node *create() { int data; person *next; person *pre; }node; node *head,*p,*s; int n,loop=1; head=(node*)malloc(sizeof(node)); p=head; while(loop) { } head=head->next; head->pre=NULL; //链表的第一个元素为NULL,head为第二个元素 p->next=NULL; 22 printf(\"Please input the data: \"); scanf(\"%d\if(n!=0) { } else loop=0; s=(node *)malloc(sizeof(node)); s->data=n; p->next=s; s->pre=p; p=s; } return(head); //删除结点 node *del(node *head,int num) { } //插入结点，从小到大的顺序 node *insert(node *head,int num) { node *p0,*p1; p1=head; p0=(node *)malloc(sizeof(node)); p0->data=num; if(num==p1->data) { } else printf(\"\\n%d could not been found\return(head); if(p1==head) { } else if(p1->next==NULL) { } else { } p1->next->pre=p1->pre; p1->pre->next=p1->next; p1->pre->next=NULL; free(p1); head=head->next; head->pre=NULL; free(p1); node *p1; p1=head; while(num!=p1->data&&p1->next!=NULL) { } p1=p1->next; 23 while(p0->data>p1->data&&p1->next!=NULL) {p1=p1->next;} if(p0->data<=p1->data) { if(head==p1) //p0比head小 { p0->next=p1; p1->pre=p0; head=p0; } else { p1->pre->next=p0; p0->next=p1; p0->pre=p1->pre; p1->pre=p0; } } else //p0比所有的数都大 { p1->next=p0; p0->pre=p1; p0->next=NULL; } return(head); } //输出链表 void print(node *head) { node *p; p=head; printf(\"输出链表:\"); while(p!=NULL) { printf(\"%d \ p=p->next; } printf(\"\\n\"); } int main() { 24 } node *head; int delNum,insertNum; head=create(); print(head); cout<<\"\\nPlease input the delete number: \"; cin>>delNum; head=del(head,delNum); print(head); cout<<\"\\nPlease input the insert data:\"; cin>>insertNum; head=insert(head,insertNum); print(head); return 0; 25 三 环状链表（约瑟夫环） 约瑟夫环（Josephus）问题是由古罗马的史学家约瑟夫（Josephus）提出的，他参加并记录了公元66—70年犹太人反抗罗马的起义。约瑟夫作为一个将军，设法守住了裘达伯特城达47天之久，在城市沦陷之后，他和40名死硬的将士在附近的一个洞穴中避难。在那里，这些叛乱者表决说“要投降毋宁死”。于是，约瑟夫建议每个人轮流杀死他旁边的人，而这个顺序是由抽签决定的。约瑟夫有预谋地抓到了最后一签，并且，作为洞穴中的两个幸存者之一，他说服了他原先的牺牲品一起投降了罗马。 约瑟夫环问题的具体描述是：设有编号为1，2，……，n的n(n>0)个人围成一个圈，从第1个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。 1 十三个人围成一个圈，从第一个人开始顺序报号1、2、3。凡是报到“3”者退出圈子，请找出最后留在圈子中的人原来的序号 源程序1： #include void main() { int num; int next; }link[N]; int i; //围成一个圈 for(i=1;i<=N;i++) { } //踢人 int count=0; int h=N; 26 if(i==N) link[i].next=1; link[i].next=i+1; else link[i].num=i; } printf(\"Persons leave the circle: \\n\"); while(count printf(\"\\nThe last one is: \\n\"); for(i=1;i<=N;i++) { } if(link[i].num) printf(\"%4d\\n\i=0; while(i!=3) { } printf(\"%4d\link[h].num=0; count++; h=link[h].next; if(link[h].num) i++; 源程序2： #include int i,n,num[50],*p; printf(\"Input number of person: n=\"); scanf(\"%d\p=num; for(i=0;i *(p+i)=i+1; /*以1至n为序给每个人编号*/ 27 } int count=0; /*退出人数*/ i=0; /*每次循环的计数变量*/ while(count printf(\"The last one is No.%d\\n\ p++; if(*(p+i)!=0) j++; if(j==3) /*对退出者编号置为0*/ { } i++; if(i==n) i=0; /*报数到最后一个后，i恢复为0*/ *(p+i)=0; j=0; count++; 2 15个美国人和15个日本人围坐一圈，从其中一人开始数数，从1数到9，数到9的人踢出去，设计代码使被踢出的人都是日本人，输出日本人坐的位置 #include struct person { }; int main() { 28 int position; bool Remove; //delCountapanese be removed person *next; } person p[30]; for(int i=0;i<30;i++) { p[i].position=i+1; p[i].Remove=false; if(i==29) p[i].next=p; else p[i].next=&p[i+1]; } //finish the circle link table person *pos=p; int delCount=0,count=0; while(count<15) // remove 15 times: from count 0 to count 14 { } cout< pos=pos->next; delCount++; if(delCount==9) // guys be removed { } cout< 3 已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列 解法一： #include 29 #include typedef struct LNode { int data; struct LNode *next; }LNode,*LinkList; /////////////////////////////////////////////////////////////////////////////// // 约瑟夫函数 // n为总人数，k的下一位为第一个开始报数的人，m为出列者喊到的数 /////////////////////////////////////////////////////////////////////////////// void JOSEPHUS(int n,int k,int m) { /* pcur为当前结点,pre为辅助结点，指向pcur的前驱结点，head为头节点 LinkList pcur,pre,head; head=NULL; /*建立循环链表*/ for(int i=1;i<=n;i++) { pcur=(LinkList)malloc(sizeof(LNode)); pcur->data=i; if(head==NULL) head=pcur; else pre->next=pcur; pre=pcur; } pcur->next=head; /*尾节点连到头结点，使整个链表循环起来*/ pcur=head; /*使pcur指向头节点*/ /*把当前指针移动到第一个报数的人，即第k位的下一位*/ for(i=1;i<=k;i++) { pre=pcur; pcur=pcur->next; } /*循环地删除队列结点，每隔m-1个结点删一个*/ while(pcur->next!=pcur) { for(i=1;i<=m-1;i++) { 30 */ pre=pcur; pcur=pcur->next; } pre->next=pcur->next; printf(\"delete number: %d\\n\ free(pcur); pcur=pre->next; } printf(\"The last one is No.%d\\n\ } void main() { } // 总共有13人，从第1位开始报数，每隔两位踢出1个。 JOSEPHUS(13,13,3); 解法二： 上面的方法在时间效率上有缺陷，如果N 和M的值非常大的话 时间复杂度就会非常高，我们如果换个角度来考虑这个问题的话，或许能够得到一个时间效率较高的解决方法。 n个元素，从0开始，遍历到m-1删除，剩下的元素从0开始，从新遍历； 在第一次遍历第一个被删除的元素一定是m-1%n，剩下的n-1个元素从新组成了一个新的约瑟夫环，以编号k=m%n开始：K K+1 K+2 K+3...N-2 N-1 0 1 2 3...K-2 将K为新环的0；上面的队列变为 0 1 2 3 ....n-3 n-2 那么删除第一次遍历后得到节点的元素将组成一个新的约瑟夫环 ，遵循这一规则我们将面对的是一个旧规则的新问题. 下面我们来实现这个递推思想: 设 a[n] 则a[i]=(a[i-1]+m)%i;(i>1) 31 源程序： #include int n,m,i,a=0; printf(\"n=\"); scanf(\"%d\printf(\"m=\"); scanf(\"%d\for(i=2;i<=n;i++) a=(a+m)%i; printf(\"The winner is No.%d\\n\ 32 四 树 1 建立二叉树 Status CreateBiTree(BiTree &T) { } 2 二叉树根结点为root,用递归法把二叉树的叶子结点按从左到右的顺序连成一个单链表 typedef struct node { char c; struct node *left,*right; scanf(&ch); if(ch==' ') T=NULL; else { } return OK; if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) exit(OVERFLOW); T->data=ch; //生成根结点 CreateBiTree(T->lchild); //构造左子树 CreateBiTree(T->rchild); //构造右子树 }btreeNode; btreeNode *firstLeaf,*pre; // 分别记录叶子链表的第一个叶子结点及当前结点的前驱 void leafLink(btreeNode *root) { if(!root) { if(firstLeaf==NULL) { } else { // 链接时用叶子结点的rchild域存放指针 pre->right=root; pre=pre->right; 33 return; if(root->left==NULL&&root->right==NULL) firstLeaf=root; // 保存找到的第一个叶子结点（k指针） pre = firstLeaf; } } } if(root->left) leafLink(root->left); leafLink(root->right); if(root->right) return; 3 写一个求二叉树深度的算法 int GetDepth(btree *root) { } 4 在已排序的二叉树中插入一个节点 分析： 排序二叉树：左小于根，根小于右。左右又分别是排序二叉树。 前序遍历：根左右 中序遍历：左根右 后序遍历：左右根 排序二叉树插入一个结点：大于左，往右找，小于右往左找，递归实现。 void insert(Root r,element e) { int dep1=0,dep2=0; if(root==NULL) return 0; dep1=GetDepth(root->lchild); dep2=GetDepth(root->rchild); if(dep1>dep2) return dep1+1; return dep2+1; else if(r>e) { } else if(r<=e) { if(r->right!=NULL) insert(r->right,e); //递归 34 if(r->left!=NULL) insert(r->left,e); //递归 r->left=e; else } } else r->right=e; 5 建立排序二叉树并中序遍历 #include struct tree //二叉树结点结构 { }; class Btree { }; void Btree::create_btree(int x) { int data; tree *left,*right; //左、右子树指针 tree *root; //根结点的指针 Btree() {root=NULL;} void create_btree(int); void display() {inorder(root);cout< tree *newnode=new tree; newnode->data=x; newnode->left=NULL; newnode->right=NULL; if(NULL==root ) { tree *back; tree *current=root; while(current!=NULL) //找到要插入newnode的节点指针 { back=current; if(current->data>x) current=current->left; 35 root=newnode; else } } } else current=current->right; if(back->data>x) back->left=newnode; back->right=newnode; else void Btree::inorder(tree *tmp) //中序遍历排序二叉树 { } void main() { } Btree A; int arr[]={7,4,1,5,12,8,13,11}; cout<<\"建立排序二叉树:\"< 36 五 堆、栈、队列 1 入栈出栈 #include struct list //定义栈结点结构 { }; class Stack { }; void Stack::push(int x) //入栈 { } int Stack::pop() //出栈 { } 37 int data; list *next; list *ptr; Stack(){ptr=NULL;} void push(int i); int pop(); public: list *newnode=new list; newnode->data=x; newnode->next=ptr; ptr=newnode; list *top; int value; value=ptr->data; top=ptr; ptr=ptr->next; delete top; return value; void main() { } Stack A; int arr[]={3,12,8,9,11}; cout<<\"入栈顺序:\"; for(int i=0;i<5;i++) { } cout< #include struct list //定义队列结点结构 { }; class Queue { int data; list *next; list *ptrf,*ptrl; //分别为队首队尾指针 Queue() { } void enqueue(int); int dequeue(); 38 public: ptrf=ptrl=NULL; }; void Queue::enqueue(int x) //入队 { list *newnode=new list; newnode->data=x; newnode->next=NULL; if(ptrl==NULL) //队空的情况 ptrf=ptrl=newnode; else { ptrl->next=newnode; ptrl=newnode; } } int Queue::dequeue() //出队 { list *tmp; int value; value=ptrf->data; tmp=ptrf; ptrf=ptrf->next; delete tmp; return value; } void main() { Queue A; int arr[]={3,12,8,9,11}; cout<<\"入队顺序:\"; for(int i=0;i<5;i++) { cout< 39 3 用栈、队列和类设计一个程序，检查所输入的数据是不是回文数据，这串数据以点作为结束符 #include struct list //定义结构 { }; class Stack //定义一个栈操作类 { }; void Stack::push(int x) { } int Stack::pop() 40 int data; list *next; list *ptr; Stack() {ptr=NULL;} void push(int i); int pop(); int empty() //判断栈是否为空 { } if(ptr==NULL) return 1; else return 0; public: list *newnode=new list; //分配内存 newnode->data=x; newnode->next=ptr; ptr=newnode; { } class Queue //定义队列操作类 { }; void Queue::enqueue(int x) //入队成员函数 { }; int Queue::dequeue() //出队成员函数 { } list *tmp; int value; value=ptrf->data; tmp=ptrf; ptrf=ptrf->next; delete tmp; //释放内存 return value; list *newnode=new list; //分配内存 newnode->data=x; newnode->next=NULL; if(ptrl==NULL) //队空的情况 { } ptrl->next=newnode; ptrl=newnode; ptrf=ptrl=newnode; else list *ptrf,*ptrl; //队首和队尾指针 Queue() {ptrf=ptrl=NULL;} void enqueue(int); int dequeue(); public: list *top; int value; value=ptr->data; top=ptr; ptr=ptr->next; delete top; //释放内存 return value; 41 void main() { } Stack S; Queue Q; char ch; cout<<\"输入数据: \"; while((ch=getchar())!='.') { } //退栈和退队并比较是否相同 while(!S.empty()&&S.pop()==Q.dequeue()); if(S.empty()) cout<<\"输入的是回文数据\"< 4 队列测长 int lenth(node *head) { int n=0; node *p; p=head; while(p!=NULL) { } return(n); 42 p=p->next; n++; } 5 队列打印 void print(queue *head) { } 6 用两个队列实现一个栈的功能 思路： 假设两个栈A和B,且都为空。 可以认为栈A提供入队功能，栈B提供出队功能。 入队列：入栈A。 出队列：如果栈B不为空，直接弹出栈B的数据；如果栈B为空，则依次弹出栈A的数据，放入栈B中，再弹出栈B的数据。 #include template node *p; p=head; while(p!=NULL) { } printf(\"%d\p=p->next; void push(T &t) { } T pushFromPop() { if(s2.empty()) { if(s1.size()==0) throw; while(!s1.empty()) { s2.push(s1.top()); 43 s1.push(t); }; } } } s1.pop(); return s2.top(); void pop() { } stack if(s2.empty()) { } if(!s2.empty()) s2.pop(); while(!s1.empty()) { } s2.push(s1.top()); s1.pop(); int main() { } MyQueue for(i=0;i<10;i++) { } for(i=0;i<10;i++) { } cout< 六 排序 1 冒泡法排序 /////////////////////////////////////////////////////////////////////////////// // 冒泡法排序 // 原理（由小到大）： // 将相邻两个数比较，将大的调到后头。如果有n个数，则要进行n-1趟比较。 // 在第1趟中要进行n-1次两两比较，在第j趟比较中要进行n-j次两两比较。 /////////////////////////////////////////////////////////////////////////////// #include 45 int a[10]; int i,j; printf(\"Input 10 numbers:\\n\"); for(i=0;i<10;i++) { } printf(\"\\n\"); for(j=0;j<9;j++) { } printf(\"The sorted numbers:\\n\"); for(i=0;i<10;i++) { } printf(\"\\n\"); printf(\"%d \for(i=0;i<=9-j;i++) { } if(a[i]>a[i+1]) { } a[i] = a[i] ^ a[i+1]; a[i+1] = a[i] ^ a[i+1]; a[i] = a[i] ^ a[i+1]; scanf(\"%d\ 2 选择法排序 //////////////////////////////////////////////////////////////////////////////////// // 选择法排序 // 原理（由小到大）： // 先将n个数中最小的数与a[0]对换，再将a[1]到a[n-1]中最小的数与a[1]对换 // ……每比较一轮，找出未经排序的数中最小的一个。共比较n-1轮。 //////////////////////////////////////////////////////////////////////////////////// #include int main() { 46 int i,j,min; { } min=i; for(j=i+1;j array[min] = array[min] ^ array[i]; array[i] = array[min] ^ array[i]; array[min] = array[min] ^ array[i]; if(array[j] for(i=0;i int a[10],i; printf(\"Enter the array:\\n\"); for(i=0;i<10;i++) { } sort(a,10); printf(\"The sorted array:\\n\"); for(i=0;i<10;i++) { } printf(\"\\n\"); return 0; printf(\"%d \",a[i]); scanf(\"%d\",&a[i]); 运行结果： Enter the array: 9 8 7 6 5 4 3 2 1 0 The sorted array: 0 1 2 3 4 5 6 7 8 9 3 快速排序 #include void QuickSort(int a[], int low, int high) { if (low >= high) { return; } int i = low; int j = high; int pivot = a[low]; while(i <= j) { if (a[i] <= pivot) { i++; } 47 else if (a[j] > pivot) { j--; } else {// swap a[i], a[j] int tmp = a[i]; a[i] = a[j]; a[j] = tmp; i++; j--; } } // swap a[low] , a[j] a[low] = a[j]; a[j] = pivot; j--; QuickSort(a, low, j); QuickSort(a, i, high); } void PrintArrary(int data[], int size) { for (int i=0; i int array[]= {20,34,4,53,43,42,6,67,193}; int size = sizeof(array)/sizeof(int); QuickSort(array, 0, size - 1); PrintArrary(array, size); return 0; } 4 直接插入排序函数模板 源程序： 48 #ifndef ARRAY_BASED_SORTING_FUNCTIONS #define ARRAY_BASED_SORTING_FUNCTIONS template void InsertionSort(T A[],int n) { } #endif 5 直接选择排序函数模板 源程序： #ifndef ARRAY_BASED_SORTING_FUNCTIONS #define ARRAY_BASED_SORTING_FUNCTIONS template template void SelectionSort(T A[],int n) { int i,j; T temp; for(i=1;i while(j>0&&temp A[j]=A[j-1]; j--; T temp; temp=x; x=y; y=temp; int i,j,min; for(i=0;i } } min=i; for(j=i+i;j Swap(A[i],A[min]); #endif 6 起泡排序函数模板 源程序： #ifndef ARRAY_BASED_SORTING_FUNCTIONS #define ARRAY_BASED_SORTING_FUNCTIONS template template void BubbleSort(T A[],int n) { T temp; temp=x; x=y; y=temp; int i,j; int lastExchangeIndex; i=n-1; while(i>0) { } 50 lastExchangeIndex=0; for(j=0;j if(A[j+1] } #endif 7 顺序查找函数模板 源程序： #ifndef SEARCH_METHODS #define SEARCH_METHODS //用顺序查找法在数组中查找值为key的元素 //若找到，返回该元素下标，否则返回-1 template int SeqSearch(T list[],int n,T key) { } #endif 8 折半查找函数模板 源程序： #ifndef SEARCH_METHODS #define SEARCH_METHODS template int BinSearch(T array[],int n,T key) { for(int i=0;i if(list[i]==key) return i; int mid,low,high; T midvalue; low=0; high=n-1; while(low<=high) { mid=(low+high)/2; midvalue=array[mid]; if(key==midvalue) return mid; high=mid-1; 51 else if(key } else low=mid+1; return -1; //没有找到返回-1 #endif 52 因篇幅问题不能全部显示，请点此查看更多更全内容 using namespace std;