排序 冒号排序 冒号排序的基本思想:每次比较两个相邻元素,如果他们的顺序错误,就把它们交换过来。 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 #include <stdio.h> int main () { int a[100 ]; int n; scanf ("%d" ,&n); for (int i=0 ;i<n;i++) scanf ("%d" ,&a[i]); for (int i=0 ;i<n;i++) { for (int j=0 ;j<n-i;j++) { if (a[j]<a[j+1 ]) { int t=a[j]; a[j]=a[j+1 ]; a[j+1 ]=t; } } } for (int i=0 ;i<n;i++) printf ("%d " ,a[i]); return 0 ; }
快速排列 在快排之前,要先理解一个东西,基准数,你对{10,6,3,9,1,4,2,8,5,7}这一组数快排的时候,我们选取了第一个数值作为基准数(基准数是每次都不一样的)。
基准数这个东西呢,你可以选取这个数列的开头第一个,就算它是10也可以是基准数,从整个数列的最右开始,选取第一个小于10的数停下来,与这个基准数交换,那就是7了,数列变成了{7 ,6,3,9,1,4,2,8,5,10 },再从右边开始,发现没有小于10的数了,那就说明10已经归位了。(基准数归位的一个条件是,它左边的数都小于它,右边的数都大于它)
然后我们再选取7作为基准数,依旧从右开始,第一个小于7的数,找到了是5,再左边开始,找到第一个大于7的数,找到了是9,将这两个交换位置{7,6,3,5 ,1,4,2,8,9 ,10}。好的,继续我们的找数,右边从9开始,找到了第一个小于7的数,是2,左边从5开始,它和右边找到2的位置撞到了一起,这个时候就走不了了!就将2的位置和7进行交换,我们得到了这样的数列{2 ,6,3,5,1,4,7 ,8,9,10},我们检查一下7是否归位,好的,它已经归位了。
后面的都是一样的,一点点的归位,最后就能得到一个从小到大的排序了~快排的每一轮的处理,就是将这一轮的基准数归位 。虽然是看懂了以上的快速排列的方法了,但是就有不少的问题了。
为什么从右边开始找比基准数小的数呢?这个问题其实可以分成两个问,①为什么从右边开始?②为什么要找比基准数小的数?
①emmmm这个问题比较复杂,可以试一下从左边开始时,会发现最后交换基数时,排列错误,所以我们需要从基数的对面开始。
②第二个问题其实很简单,我们需要把基数移到正确的位置,我们要确保基准数归位的时候,右边的数大,左边的数小。所以在将基准数归位的时候,我们找到右边的小数与左边的大数相交换,直到交换不了了,我们再与基准数交换数,更换基准数。
好的,我们知道快排的基本原理了,那么为什么我们选择快排呢?当然是因为好用,其实是因为时间复杂度低,最坏的情况当然是像冒泡排序法一样的,只交换旁边两个,时间复杂度位O(N²),它的平均时间复杂度为O(NlogN)。
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 #include <stdio.h> int a[101 ],n;void quicksort (int left,int right) { int i,j,k,t,temp; if (left>right) return ; temp=a[left]; i=left; j=right; while (i!=j) { while (a[j]>=temp && i<j) j--; while (a[i]<=temp && i<j) i++; if (i<j) { t=a[i]; a[i]=a[j]; a[j]=t; } } a[left]=a[i]; a[i]=temp; quicksort(left,i-1 ); quicksort(i+1 ,right); } int main () { int i,j; scanf ("%d" ,&n); for (int i=0 ;i<n;i++) { scanf ("%d" ,&a[i]); } quicksort(0 ,n-1 ); for (int i=0 ;i<n;i++) printf ("%d " ,a[i]); return 0 ; }
栈、队列、链表 队列 首先,队列是一种特殊的线性结构(线性结构就是一条,不能处理行列式之类的),只允许在队列的首部(head)进行删除和操作(这个时候其他的都没有改变),称为出队,在队列的尾部(tail)进行插入操作,称为入队。
在知道这些之后,深入分析一下,一整个队列,就只有两个地方能进行处理,一个是头,另一个是尾,其他的数就好像被固定了一样,等到头(head)到达它的时候才能对它进行处理,这个时候队列的位置是没有移动的 ,这一点很重要,移动它将会花掉我们更多的时间,所以我们用空间换时间,以保证程序运行快。
我们称为“先进先出”原则。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #include <stdio.h> int main () { int a[101 ]={6 ,2 ,5 ,1 ,8 ,4 ,7 ,1 ,4 },head,tail; head=0 ; tail=9 ; while (head!=tail) { printf ("%d " ,a[head]); head++; a[tail]=a[head]; tail++; head++; } return 0 ; }
用结构体来实现队列的操作(因为我自己结构体学得太差,所以看着结构体实现队列来学结构体具体用法 )在学习之前,重新捡起结构体的知识,对结构体做一个整体的框架构建吧!内容来自《C语言详解》,《C Primer Plus》。
结构体 结构声明 描述了一个结构的组织布局 1 2 3 4 5 stuct book{ char title[100 ]; char author[100 ]; float value; };
该声明表示了一个由两个字符数组和一个float类型变量组成的结构。该声明并没有创建实际的数据对象,只描述了该对象由什么组成(有时候我们也将结构声明称为模板,和c++的模板不一样)。首先是关键字struct,它表明跟在其后的是一个结构,后面是一个可选的标记(book),我们在后面的程序中可以这样声明: struct book library
这把library声明为一个使用book结构布局的结构变量。
定义结构变量 结构体布局告诉编译器如何表示数据,但是没有让编译器分配空间,下一步是创建一个结构变量,即是结构的另一层含义。 声明结构体的过程和定义结构体的过程可以组合成一个步骤 ,如下所示,组合后的结构声明和结构变量定义不再需要使用结构体标记。 1 2 3 4 5 struct { char title[MAXTITLE]; char author[MAXAUTL]; float value; }library;
访问结构成员 结构体类似于一个“超级数组”,这个超级数组中,可以是各种类型的元素。如何访问结构体的成员?使用结构成员运算符——点(.)访问,ex:library.value。.比&的优先级高,所以&library.value和&(library.value)表达是一样的。如果是结构体指针,那么访问结构体指针应该使用->。
如果him==&barney,那么him->income即是barney.income
如果him==&fellow[0],那么him->income即是fellow[0].income
结构类型 一种针对记录得数据类型,该记录由多个成员组成
结构类型plant_t有5个不同的成员:一个是字符数组类型,一个是int类型,其他三个为double类型。
1 2 3 4 5 6 7 #define STRSIZ 10 typedef struct { char name[STRSIZ]; double diameter; int moons; double orbit_time,rotation_time; }plant_t ;
声明结构体数组
一个例子:struct book library[MAXBKS];
代码把libray声明为一个内含MAXBKS个元素的数组。数组的每个元素都是一个book类型的数组。因此,library[0]是第一个book类型的结构变量……数组名library本身不是结构名,它是一个数名,该数组中的每个元素都是struct book类型的结构变量。
标识结构数组的成员
1 2 3 4 library library[2 ] library[2 ].title library[2 ].title[4 ]
结构体实现队列 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 #include <stdio.h> struct queue { int data[100 ]; int head; int tail; }; int main () { struct queue q ; q.head=1 ; q.tail=1 ; for (int i=0 ;i<9 ;i++) { scanf ("%d" ,&q.data[q.tail]); q.tail++; } while (q.tail!=q.head) { printf ("%d " q.data[q.head]); q.head++; q.data[q.tail]=q.data[q.head]; q.tail++; q.head++; } getchar(); getchar(); return 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 #include <stdio.h> #include <string.h> int main () { char a[101 ],s[101 ]; int len,mid,next,top; gets(a); len=strlen (a); mid=len/2 -1 ; top=0 ; for (int i=0 ;i<=mid;i++) s[++top]=a[i]; if (len%2 ==0 ) next=mid+1 ; else next=mid+2 ; for (int i=next;i<=len-1 ;i++) { if (a[i]!=s[top]) break ; top--; } if (top==0 ) printf ("OK" ); else printf ("Sorry" ); getchar(); getchar(); return 0 ; }
其实栈的使用是很简单的,主要是要注意它只有一边是可以移动的,那就是top,也就是离桶低最远的那一个是可以动的。
链表 在学链表之前先用一段代码来回顾一下指针的内容,malloc是为指针分配内存空间地址,但是我们可能不知道我所定义的类型需要多大的空间,就用sizeof()来计算大小,分配给改类型的指针!不要忘记加括号!
1 2 3 4 5 6 7 8 9 10 11 12 #include <stdio.h> #include <stdlib.h> int main () { int *p; p=(int *)malloc (sizeof (int )); *p=10 ; printf ("%d" ,*p); getchar(); getchar(); return 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 #include <stdio.h> #include <stdlib.h> struct node //声明结构体{ int data; struct node *next ; }; int main () { struct node *head ,*p ,*q ,*t ; int n,a; scanf ("%d" ,&n); head=NULL ; for (int i=0 ;i<n;i++) { scanf ("%d" ,&a); p=(struct node*)malloc (sizeof (struct node)); p->data=a; p->next=NULL ; if (head==NULL ) head=p; else p->next=p; q=p; } scanf ("%d" ,&a); t=head; while (t!=NULL ) { if (t->nxt==NULL ||t->next->data->a) { p=(struct node *)malloc (sizeof (struct node)); p->data=a; p->next=t->next; t->next=p; break ; } t=t->next; } t=head; while (t!=NULL ) { printf ("%d" ,t->data); t=t->next; } getchar(); getchar(); return 0 ; }