数据结构基本算法大全

1、算法/*冒泡算法思想：两个泡泡，大的在后面,小的在后面*/#include void bubble(int a,int n)int temp=0;int lastexchange=O;广传递边界 */ int border=n-1;for(int i=0;in-1 ;i+)bool sort=true;for(int j=0;jaQ+1)(temp=aO；aO=aD+1;aj+1=temp;sort=false; /*两两交换，还得工作*/lastexchange才宀新的边界，解决了不在遍历全部元素，而是从最后交换那个位置开始*/border=lastexchange; /* 给它新的边界 *

2、/if(sort) /*sort=trune才做，每一轮循环如果有交换面用里 的false,如果哪一次循环一次都没有交换那么就不会执行交 换，外面的true,就退出循环*/break;)int main()(int a10,i;printf(请输入10个整数:n);for(i=0;i10;i+)scanf(n%dH,&ai);)bubble(a,10);printf(nbubble 后:nH);for(i=0;i10;i+)printf(H%4d5ai);/槿插入排序思想：把它看作摸牌过程。首先手里面有一张牌，所 以i=1;摸第二张牌时和手里牌比较，比第一张牌小则往前，摸第 二张牌，和前面两张

3、牌比较，比他们都小则移动到最前面，剩下 两张牌向后移动。*/#include void insert(int a,int n)(int tempJJ;for(i=1 ;i=O&tempaj) /* 这里 while 不加花括号，也要执行下面两个语句，说明while循环按括号里的条件结束，不管下面有没有花括号*/利用j-先用后赋值的力量*/aO+1=temp;/* 此时 j-赋值了 */)main()int i,a10;printf(请输入10个整数n);for(i=0;i10;i+)scanf(n%dn3&ai);)printf(nthe array is:nn);for(i=0;i10;i+

4、)printf(H% -4dH,ai);)insert(a,10);prints 排序后：nn);for(i=0;i10;i+)printf(n% -4dH5ai);printf(HnH);)/*顺序查找思想：把查找的数从头至尾 r#in cludeint find(int *ListSep,int ListLengthJnt Keydata)(int temp=O;int length=ListLength;for(int i=O;iListLength;i+)(if(ListSepi=Keydata) return i;return 0;)int main()int TestData5=3

5、4,67,1,47,8;int reData=find(TestData,5,47);printf(HreData:%dn,JreData);return 0;/*算法思想：分而治之，挖坑填数。初始i=0;j=9;x=ai=?,由于已 经将a0中的数保存在x中，可以理解成在数组a0上挖了一个 坑，可以将其它数据填充到这里*/#in cludevoid quick(int a,int l,int r)if(lr) r* 全轮确保 */int i=l,j=r,x=al;/*l,r 的生存期是大 if 结束 */while(ij) /*确保交换到不满足条件*/(while(i=x) /* 这里的 w

6、hile 彳盾环、当找到 ajx 的 数才会退出然后执行下面的if语句。相当于从右往左推进，找到 后停下退出*/J-；/*这里有ij条件是预料这种情况，数组本来就排好了，j都已经指了第一个元素的位置，这时if就不用执行了 Tai+=aj;/*i+3这里的值还是当前的/下面的i,就是赋值后的值*/while(ij&aix) /* 从左往右走 */ i+; if(ij)(aH=ai;ai=x； /*把第一个坑的元素储存起来最后放到该放的位置十/quick(aJJ-l);/* 左边新组 */+此时那个标杆在中间,就不去动它了，它左边比他小,右边比它大+/quick(a,i+1,r); /* 右边新组

7、 */int main()printf(nplese in put ten number:rT); for(i=0;i10;i+)scanf(n%dn,&ai);quick(a,0,9);printf(快速排序的结果：n);for(i=0;i10;i+)printf(H%4dH,ai);)printf(Hnn);/*选择排序思想：从头扫至尾，找到最小的元素，和第一个元素交换，接着找第二个小的放到第二个位置 5#includevoid select(int a,int n)for(int i=0;in-1;i+) /* 完成 n-1 次循环 */int index=i;int j;for(j=i

8、+1;jn;j+) /*在这个for循环中，通过不断交换下标 找出一轮当中，数组元素最小的那个*7(if(ajaindex)(index=j;int temp=aindex; /*这里的index就是j的值，也就是最 小元素的下标*/aindex=ai;ai=temp;)int main()(int a10,i;printf(请输入10个整数:n);for(i=0;i10;i+)scanf(n%dn3&ai);select(a,10);printf(nafter selection:rT);for(i=0;i10;i+)printf(nH);严*希尔排序思想：插入排序特殊情况，和升级版。分成一

9、半一半 的插*/#include#define max 100void shell(int a,int n)int i,j,k,temp,gap;/*这里gap=1是可以分到一个元素一组，然后比较*/for(int gap=n/2;gap=1 ;gap/=2) /* 这里的 for 循环功能是分组，gap/=2和i+样先用再赋值，下面都是这样for(int i=O;igap;i+) /*这里的for是推进下标向右走1步，由于分 了组，就要把左边的组的第一个与右边组第一个进行比较*/ for(j=i+gap;jaO)temp=aj；for(k=j-gap;k=0&aktemp;k-=gap) /

10、*ror,为了向左 交换，这里的一个前提aktemp,满足才能往左边进行交换*/ak+gap=ak; /* 此时 k 还是 j-gap 的值*/* 要 先把这个for循环搞完，在弄ak+gap=ak*/ak+gap=temp;/* 此时 k 的值就是 k-=gap 的值 / int main()int amax5n,q;printf(”输入数据个数nn); scanf(n%dH,&n);printf(输入数组元素值:n);for(int i=O;in;i+)scanf(%dn5&ai);shell(a,8);for(int i=0;i8;i+)printf(H%4dH,ai);printf(H

11、nn);scanf(n%dn,&q);return 0;/*二分查找思想：用给定值K先与中间的结点的尖键字比较， 中间结点把线形表分成两个子表，若相等则查找成功；若不相 等，再根据K与该中间结点矣键字的比较结果确定下一步查找哪 个子表，这样递归进行，直到查找到或查找结束发现表中没有这 样的结点*/*前提是有序顺序存储*/ #includeint binsearch(int *Sep,int sepLength,int keydata)int low=05mid,high=sepLength-1;while(low=high) /防止一个元素都没有mid=(low+high)/2;if(keyd

12、ataSepmid)low=mid+1;else /说明已经找到了，不满足if ,else if说明keydata=sepmidreturn mid;return -1; /查找失败，或一个元素都没有int main()int a=1,2,3,4,5,67,8,9;int location;int target=4; location=binsearch(a,9,target); printf(n%dnH,location); return 0;/*基于结构体栈的实现思路：top始终指向一个待插入的位置 push操作：1.写入数据2.top+ 3.前提：栈非满pop操作：l.top-2弹出数据3.前提:栈非空7 include typedef struct _stackchar mem1024;int top;stack;int isFull(stack *ps) / 判满return ps-top = 1024;int isEmpty(stack *ps) / 判空(return ps-top = 0;void push(stack *ps,char ch) / 压栈(ps-memps-top = ch; (ps-top)+