程序员数据结构笔记

数据结构知识:1.数据结构中对象的定义,存储的表示及操作的实现.2.线性:线性表、栈、队列、数组、字符串（广义表不考）树：二叉树集合：查找，排序图(不考)能力：分析，解决问题的能力过程：●确定问题的数据。●确定数据间的关系。●确定存储结构（顺序－数组、链表－指针）●确定算法●编程●算法评价（时间和空间复杂度，主要考时间复杂度）一、数组1、存放于一个连续的空间2、一维～多维数组的地址计算方式已知data[0][0]的内存地址，且已知一个元素所占内存空间Ｓ求data[i][j]在内存中的地址。公式：（add+(i*12+j)*S)(假设此数组为data[10][12])注意：起始地址不是data[0][0]时候的情况。起始地址为data[-3][8]和情况；3、顺序表的定义存储表示及相关操作4、顺序表操作中时间复杂度估计5、字符串的定义（字符串就是线性表），存储表示模式匹配算法（简单和KMP（不考））6、特殊矩阵：存储方法（压缩存储（按行，按列））三对角：存储于一维数组三对角问题：已知Aij能求出在一维数组中的下标k;已知下标k求Aij。7、稀疏矩阵：定义，存储方式：三元组表、十字链表（属于图部分，不考）算法●数组中元素的原地逆置；对换●在顺序表中搜索值为X的元素；●在有序表中搜索值为X的元素；（折半查找）●在顺序表中的第i个位置插入元素X；●在顺序表中的第i个位置删除元素X；●两个有序表的合并；算法？线性表数据结构定义：Typedefstruct{intdata[max_size];intlen;}linear_list;●模式匹配●字符串相加●求子串●（i,j）=K注意：不同矩阵所用的公式不同；●稀疏矩阵的转置（两种方式，后种为妙）●和数组有关的算法例程：求两个长整数之和。a=13056952168b=87081299数组:a[]:13056952168b[]:87081299由于以上的结构不够直观(一般越是直观越容易解决)将其改为:a[]:1186125965031a[0]=11(位数)b[]:899218078000b[0]=8c进位01100111100c[]:1176433044231c[0]的值(C位数)由c[max_s+1]决定!注意:在求C前应该将C(max_s+1)位赋0.否则为随机数;较小的整数高位赋0.算法:已知a,b两个长整数,结果:c=a+b;总共相加次数:max_s=max(a[],b[])程序:for(i=1;i=max_s;i++){k=a[i]+b[i]+c[i];c[i]=k%10;c[i+1]=k/10;}求c位数:if(c[max_s+1]==0)c[0]=max_s;elsec[0]=max_s+1;以下代码是我编的(毕竟是初学者.不太简洁大家不要见怪!):/*两长整数相加*/#includestdio.h#includestring.h#definePRINprintf(\n);intflag=0;/*a[0]b[0]?1:0*//*max(a[],b[]){}*/change(charda[],chardb[],inta[],intb[],intc[]){inti;if(a[0]b[0]){for(i=1;i=a[0];a[i]=da[a[0]-i]-'0',i++);/*a[0]-'0'sogood!*/for(i=1;i=b[0];b[i]=db[b[0]-i]-'0',i++);for(i=b[0]+1;i=a[0];b[i]=0,i++);for(i=1;i=a[0]+1;c[i]=0,i++);flag=1;}else{for(i=1;i=b[0];b[i]=db[b[0]-i]-'0',i++);for(i=1;i=a[0];a[i]=da[a[0]-i]-'0',i++);for(i=a[0]+1;i=b[0];a[i]=0,i++);for(i=1;i=b[0]+1;c[i]=0,i++);}}add(inta[],intb[],intc[]){inti,sum;if(flag==1){for(i=1;i=a[0];i++){sum=a[i]+b[i]+c[i];c[i+1]=sum/10;c[i]=sum%10;}if(c[a[0]+1]==0)c[0]=a[0];elsec[0]=a[0]+1;}else{for(i=1;i=b[0];i++){sum=a[i]+b[i]+c[i];c[i+1]=sum/10;c[i]=sum%10;}if(c[b[0]+1]==0)c[0]=b[0];elsec[0]=b[0]+1;}}voidprint(intm[]){inti;for(i=m[0];i=1;i--)printf(%d,,m[i]);PRIN}main(){ints;inta[20],b[20],c[20];charda[]={123456789};chardb[]={12344443};a[0]=strlen(da);b[0]=strlen(db);printf(a[0]=%d\t,a[0]);printf(b[0]=%d,b[0]);PRINchange(da,db,a,b,c);printf(flag=%d\n,flag);PRINprintf(-----------------\n);if(flag==1){print(a);PRINs=abs(a[0]-b[0]);printf(+);for(s=s*2-1;s0;s--)printf();print(b);PRIN}else{s=abs(a[0]-b[0]);printf(+);for(s=s*2-1;s0;s--)printf();print(a);PRINprint(b);PRIN}add(a,b,c);printf(-----------------\n);print(c);}时间复杂度计算:●确定基本操作●计算基本操作次数●选择T(n)●lim(F(n)/T(n))=c●0(T(n))为时间复杂度上例子的时间复杂度为O(max_s);二:链表1、知识点●逻辑次序与物理次序不一致存储方法；●单链表的定义：术语（头结点、头指针等）●注意带头结点的单链表与不带头结点的单链表区别。（程序员考试一般不考带头结点，因为稍难理解）●插入、删除、遍历（p==NULL表明操作完成）等操作●循环链表：定义，存储表示，操作；●双向链表：定义，存储方法，操作；单链表和循环链表区别在最后一个指针域值不同。2、操作●单链表：插入X，删除X，查找X，计算结点个数●单链表的逆置（中程曾考）head-NULL/p-a1/p-a2/p-a3/p……an/NULL注：p代表指针;NULL/p代表头结点＝》head-NULL/p-an/p-an-1/p-an-2/p……a1/NULL●循环链表的操作：插入X，删除X，查找X，计算结点个数；用p=head-next来判断一次计算结点个数完成；程序段如下：k=0;do{k++;p=p-next;}while(p!=head-next);●双向链表●多项式相加●有序链表合并例程：已知两个字符串S，T，求S和T的最长公子串；1、逻辑结构：字符串2、存储结构：数组3、算法：精化（精细化工）**老顽童注：此处“精细化工”说明好像不对！s=abaabcacbt=abdcabcaabcda当循环到s.len-1时，有两种情况：s=abaabcacb、s=abaabcacbs.len-2时，有三种情况：s=abaabcacb、s=abaabcacb、s=abaabcacb...1s.len种情况程序思路：tag=0//没有找到for(l=s.len;l0&&!tag;l--){判断长度为l的s中的子串是否为t的子串;若是：tag=1;}长度为l的s的子串在s中有（s.len-l+1）个。子串0:0～l-11:1～l2:2～l+13:3～l+2…………s.len-l:s.len-l～s.len-1由上面可得：第j个子串为j～l+j-1。判断长度为l的s中的子串是否为t的子串:for(j=0;js.len-l+1&&!tag;j++){判断s中长度为l的第j个子串是否为t的子串;如果是：tag=1;}模式结构：tag=0;for(l=s.len;l0&&tag==0;l--){for(j=0;js.len-l+1&&!tag;j++){??用模式匹配方法确定s[j]～s[l+j-1]这个字符串是否为t的子串；//好好想想若是，tag=1;}}第二天转眼又过了一周了,前面一周里面我编了一些程序:链表,长整型数相加,三元组表转置以及一些简单的函数.其实有些算法想想是很简单,不过写起来还是需要一定耐心和C基础的,如果你自己觉得各算法都很懂了,不妨开机编编试试.或许会有一些新的发现与体会.栈和队列1、知识点:●栈的定义:操作受限的线性表●特点:后进先出●栈的存储结构:顺序,链接/push(s,d)●栈的基本操作:\pop(s)栈定义：struct{datatypedata[max_num];inttop;};●队列定义特点:先进先出/入队列in_queue(Q,x)●队列的操作:\出队列del_queue(Q)●队列存储结构:链队列:Typedefstructnode{Datatypedata;Structnode*next;}NODE;Typedefstruct{NODE*front;NODE*rear;}Queue;顺序队列:struct{datatypedata[max_num];intfront,rear;};问题:队列线性表假溢出=循環队列队列满，队列空条件一样=浪费一个存储空间递归定义：问题规模为N的解依赖于小规模问题的解。问题的求解通过小规模问题的解得到。包括二个步骤：1）递推6!=5!=4!=3!=2!=1!=0!2）回归720=120=24=6=2=1=0递归工作栈实现递归的机制。2、有关算法：1）顺序，链表结构下的出栈，入栈2）循環，队列的入队列，出队列。3）链队列的入队列，出队列。4）表达式计算：后缀表达式35+6/4368/+*-中缀表达式（3+5）/6-4*（3+6/8）由于中缀比较难处理，计算机内一般先将中缀转换为后缀。运算：碰到操作数，不运算，碰到操符，运算其前两个操作数。中缀=后缀5)迷宫问题6)线性链表的递归算法一个链表=一个结点+一个链表intfuction(NODE*p){if(p==NULL)return0;elsereturn(function(p-next));}树与二叉树一、知识点:1.树的定义:data_struct(D,R);其中:D中有一个根,把D和出度去掉,可以分成M个部分.D1,D2,D3,D4,D5…DMR1,R2,R3,R4,R5…RM而子树Ri形成树.1)递归定义高度2)结点个数=1O--0OO--1OOOO--2此树的高度为22.二叉树定义:结点个数=0.3.术语:左右孩子,双亲,子树,度,高度等概念.4.二叉树的性质●层次为I的二叉树I层结点2I个●高度为H的二叉树结点2H+1-1个●H(点)=E(边)+1●个数为N的完全二叉树高度为|_LOG2n_|●完全二叉树结点编号:从上到下,从左到右.i结点的双亲:|_i/2_||_i-1/2_|1i结点的左孩子:2i2i+123i结点的右孩子:2i+12i+24567(根)1为起点0为起点二叉树的存储结构:1)扩展成为完全二叉树,以一维数组存储。ABCDEFGHI数组下标0123456789101112元素ABCDEFGHI2)双亲表示法数组下标012345678元素ABCDEFGHI双亲-1001223343)双亲孩子表示法数组下标012345…元素ABCDEF…双亲-100122…左子134…右子2-15…结构:typedefstruct{datatypedata;intp