一个北大学生学习数据结构的经验

-.z一个北大学生学习数据构造的经历1学习方法因为要准备这个话题，所以我认真的思考了我的学习方法，但是我觉得根本上我就是上课前看看书、上课时认真听课、下课以后复习复习、当然还有做作业时很认真的去做。根本谈不上什么好方法，不过我还是有一些话要送给大家。我能行！

个人觉得这句话非常重要，不知道大家是怎样对待数据构造这门课的，有多少人觉得数据构造很难呢.我知道还是有一些同学这样觉得的，有时候我跟我的朋友讲要怎样学，讲了一大堆以后，他就向我抱怨：我以前c＋＋都没有学好，数据构造更学不好了，这哪跟哪的话啊，数据构造与c＋＋没有什么关系，我想假设抱有这样的心态，自己就不相信自己，那是不可能学好的，然后那些觉得数据构造很难的同学，我想他们应该会很看重数据构造的吧，然后就一天到晚捧着一本数据构造，这样不会觉得很累吗.而且因为觉得很难，就容易不相信自己，学的效率也不会很好，个人认为数据构造很好学，很容易学，或许这有点妄自菲薄吧，但是因为我觉得很容易，当然就会觉得自己没问题，学得很轻松，效果也还可以。大家都是从高考走过来的，应该知道心态的重要性吧，两种不同的心态，完全就是两种不同的效果。

学了这么久数据构造了，我们到底在学些什么呢.不知道大家有没有想过，那现在我们现在来归纳一下我们学习的容吧，其实学到现在我们也就学了几种普通的数据构造，象二叉树，树，图，还有排序的问题，前面的线性表和字符串也就是一些概念，当然还有一个很重要的KMP算法，然后在每种数据构造中我们也就是学到了假设干处理的算法，

我想真正数起来也就是几十个算法吧。学习数据构造也就是要掌握这几十种算法，多简单。至于如何掌握每个算法呢，我想就是多看看书，重要的是能够理解。我能单独完成作业！这里我的定义和教师的不同，教师是鼓励大家讨论的，不过我发现还是有一些同学就是先问好别人算法，然后再自己写，虽然这个不算抄袭作业，但自己根本上没有一个思考问题的过程，虽然要理解算法也会要思考很多，但是因为没有自己独立的思考过程，要自己写程序、写算法的时候根本写不出来，所以我想如果真的想学好数据构造的话，最好是能够自己思考问题，不要刚想了一会就觉得做不出来，然后就去问其他人。其实教师给我们的作业还是基于我们的水平的，我绝对相信我们自己能够单独想出算法，虽有可能会比较长时间吧，但是这样肯定会比问其他人学到更多的东西。当然我并不是说不要问同学，有时候就是脑筋转不过来，一问别人就懂了，当然问了别人不能只是我知道了这个算法，还应该去想如何思考才能得到这个算法，这样水平会提高很多。多实验！这个就没有太多理由了，我一直觉得编程是一门熟练科学，多编程，水平肯定会提高，最重要的是能够养成一种感觉，就是对程序对算法的敏感，为什么那些牛人看一个算法一下子就看懂了.而自己要看很久才能弄懂，而且弄懂了过了一阵子又忘记了.其实这个是因为牛人们以前看的程序很多，编得也很多，所以他们有了那种感觉，所以我觉得大家应该多看程序，多写程序，培养自己的感觉。2复习和考试的技巧我想大家应该都有这样的感觉，就是觉得自己什么都掌握了，但是在考试的时候就是会犯晕，有时候一出考场就知道错在哪个了，然后考完以后一对答案，发现其实考得很简单，应该都是自己会做的，这个就是与自己的复习和考试的技巧有关系了。首先就是复习，前面已经说过其实我们学的算法也就是几十个，则我们的任务也就是理解这几十个算法，复习也就是要加深你的理解。如何理解算法，然后理解到什么程度呢.是能默出整个算法吗.其实不是这样的，数据构造的考试有它的特点，考过期中考试了，大家应该都发现数据构造其实不要求你把整个算法背出来，它注重考察你的理解，则怎么考察呢.其实也就是两种方式吧，一种就是用实例，就是给你一个例子，要你用*个算法运行出结果，我想这个期末考试的时候仍然会有很多这样的题目，比方排序那块就很好出这样的题目，要复习这种题目我觉得很简单，就是每个算法都自己用例子去实践一下，以不变应万变，我期中复习的时候就是这样去做的，而且考试之前我就觉得那个并查集的题目就很有可能会考，于是就自己出了几个例子，做了一下。另外一种考察方式就是算法填空和算法改错，可能有一些同学觉得这种题目很难，其实我们首先可以确定这两种题目肯定是与书上算法有关系的，只要理解了书上的算法就可以了，有人觉得看完书以后什么都懂了，而且要默也默得出来，其实不是这样的，算法改错和填空主要是考察的细微处，虽然你觉得你默得出来，那是能够默出算法的主体局部，很多细微的地方你就会很容易忽略。我想大家考过期中考以后应该都有这种感觉吧.那要怎样解决这种问题呢.我觉得有两种方法，一种就是自己去编程实现，这种方法比较有意义，还能够提高编程水平，

另外一种就是用实例分析算法的每句话，我认为这种方法是最有效的。然后还有一种题目，就是最后的写算法的题目，我觉得这种题目还是很好解决的，只要是能够自己做出作业的，根本上都会很容易做出来，这也是为什么我前面觉得平时做作业应该自己独立思考的原因，同时做这种题目千万要小心，尤其是题目简单的时候，那肯定会有一些小地方要考虑清楚，一不小心就会被扣掉很多分，这样很不值。我觉得考试的时候没有太多要讲的，只要复习好了，考试的时候细心一点就可以了，然后就是做一个题目开场就要尽量保证正确，如果觉得留在那里等后面做完了再来检查，这样错误还是很有可能检查不出来，我期中考试的时候就根本上没有检查，因为我做每个题目都是确保正确，用的时间也挺多的，然后也觉得没有检查的必要了。

一个学生学习数据构造的体会〔转〕读?数据构造〔C语言版〕?〔1〕今天开场认真读这本清华版的数据构造，严蔚敏和吴伟民编著。也许你会奇怪我为什么会选择这本C语言描述的数据构造书，现在的数据构造不都用面向对象语言描述吗.其实这本书不是我选的，而是我参加的机试指定的参考书。不过对于本书选用的语言，我倒有自己的看法。用C语言描述显然有很多不便，但是在一个充满着用OO描述数据构造的世界里，从OO中抽身出来用C对待数据构造的思想，也许更能看清数据构造的本质。好了，言归正传。在今天这第一篇文章里，我来探讨一下数据构造的根本概念。作者一开篇就归纳了计算机解题的一般步骤：“首先要从具体问题抽象出一个适当的数学模型，然后设计一个解此数学模型的算法，最后编出程序，进展测试、调试直至得到最终解答。〞我把它再进一步归纳一下，就是：抽象数学模型——设计算法——编写程序。这个思路非常重要，除了一些非常简单的问题，所有的程序设计都应该遵循这三个根本步骤。我们平时写程序常犯的错误是忽略第一个或第二个步骤，或者更甚者，前两个都忽略。在设计数学模型的过程中，实际上就引出了数据构造的概念。本书中作者给出的定义是：“简单来说，数据构造是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。〞国的教材为了语言上的严谨常常把话说得很难懂。请大家注意这句话里的这几个关键词：1〕非数值计算，这说明了数据构造这门学科的应用围，如果你想解一个线性方程组，大概很难直接找到适宜的数据构造；2〕操作对象，也就是问题中的数据及其表示的形式；3〕关系，即数据间的关系；4〕操作，即针对数据的操作。把以上的定义用公式写出来，就是Data_Structure=(D,S)其中D是数据元素的有限集，S是D上关系的有限集。所以在设计数据构造时，首要的任务就是找出要操作的数据，其次是挖掘出数据间的关系。这两步完成以后，数据的逻辑构造就定下来了。其中数据间的构造有以下几种：集合，这和数学中的集合概念是一致的；

线性构造，即数据元素之间一对一的关系；

树形构造，即数据元素之间一对多的关系；

图状构造或网状构造，即数据元素之间多对多的关系。

然而只有逻辑构造是不够的，程序要能够运行，必须把数据的逻辑构造在计算机中表示出来，也就是设计物理构造。大多数高级语言都对数据的物理构造有较好支持，如各种数据类型。作者在解释数据类型的概念时说到：“引入数据类型的目的，从硬件的角度看，是作为解释计算机存息含义的一种手段，而对使用数据类型的用户来说，实现了信息的隐蔽，即将一切用户不必了解的细节都封装在类型中。〞这个概括非常精辟，从中可以看出以后的OOP只是在更高层次上对信息的封装和隐蔽。对数据类型进一步扩展，作者引出了抽象数据类型的概念。抽象数据类型〔ADT〕是指一个数学模型以及定义在该模型上的一组操作。在引入抽象数据类型后，使逻辑构造更加独立，从而让程序员可以更加专注于逻辑构造的设计。把抽象数据类型用公式表示出来，就是(D,S,P)，其中D是数据对象，S是D上的关系集，P是对D的根本操作集。如果计算机解题一定要遵循一个通用的模式的话，上面这个式子就给出了答案。

读?数据构造〔C语言版〕?〔2〕本节谈一谈算法分析和大O估算法〔big-Onotation〕。算法效率的度量一般采用事前分析估算的方法，通常的做法是，“从算法中选取一种对于所研究的问题〔或算法类型〕来说是根本操作的原操作，以该根本操作重复执行的次数作为算法的时间量度〞。谈到这里时，作者引出了大O估算法。在本书中，作者对大O估算法的介绍显得有些草率。一开场就冒出一个式子T(n)=O(n3)，然后在本页最底下用小字介绍了所谓的“"O"的形式定义〞：假设f(n)是正整数n的一个函数，则*n=O(f(n))表示存在一个正的常数M，使得当n≥n0时都满足|*n|≤M|f(n)|。也许是我数学根底太差，总之看到这个定义时我一头雾水。不知道为什么作者没有花一点篇幅介绍大O估算法的由来和定义。我google了一下，发现了这样的介绍：Definition:Atheoreticalmeasureofthee*ecutionofanalgorithm,usuallythetimeormemoryneeded,giventheproblemsizen,whichisusuallythenumberofitems.Informally,sayingsomeequationf(n)=O(g(n))meansitislessthansomeconstantmultipleofg(n).Thenotationisread,"fofnisbigohofgofn".FormalDefinition:f(n)=O(g(n))meanstherearepositiveconstantscandk,suchthat0≤f(n)≤cg(n)foralln≥k.Thevaluesofcandkmustbefi*edforthefunctionfandmustnotdependonn.

Note:Asane*ample,n2+3n+4isO(n2),sincen2+3n+4<2n2foralln>10.Strictlyspeaking,3n+4isO(n2),too,butbig-Onotationisoftenmisusedtomeanequaltoratherthanlessthan.Thenotionof"equalto"ise*pressedbyΘ(n).Theimportanceofthismeasurecanbeseenintryingtodecidewhetheranalgorithmisadequate,butmayjustneedabetterimplementation,orthealgorithmwillalwaysbetooslowonabigenoughinput.Forinstance,quicksort,whichisO(nlogn)onaverage,runningonasmalldesktopcomputercanbeatbubblesort,whichisO(n2),runningonasupercomputeriftherearealotofnumberstosort.Tosort1,000,000numbers,thequicksorttakes20,000,000stepsonaverage,whilethebubblesorttakes1,000,000,000,000steps!Anymeasureofe*ecutionmustimplicitlyore*plicitlyrefertosomecomputationmodel.Usuallythisissomenotionofthelimitingfactor.Foroneproblemormachine,thenumberoffloatingpointmultiplicationsmaybethelimitingfactor,whileforanother,itmaybethenumberofmessagespassedacrossanetwork.Othermeasureswhichmaybeimportantarecompares,itemmoves,diskaccesses,memoryused,orelapsed("wallclock")time.〔以上介绍来自：PaulE.Black,"big-Onotation",fromDictionaryofAlgorithmsandDataStructures,PaulE.Black,ed.,NIST.〕另外，这个帖子也讨论了算法的时间复杂度估计，说得非常通俗易懂。

说明：因我上传受到限制，只能这样发帖。读?数据构造〔C语言版〕?〔3〕【问题描述】

设计一个可进展复数运算的演示程序。【根本要求】

实现以下六种根本运算：由输入的实部和虚部生成一个复数；

两个复数求和；

两个复数求差；

两个复数求积；

从复数中别离出实部；

从复数中别离出虚部。

运算结果以相应的复数或实数的表示形式显示。【测试数据】

对以下各对数据实现求和：0；0；应输出“0〞

3.1，0；4.22，8.9；应输出“7.32+i8.9〞

-1.33，2.34；0.1，-6.5；应输出〞

0，9.7；-2.1，-9.7；应输出“-2.1〞

7.7，-8；-7.7，0；应输出“-i8〞

【实现提示】

定义复数为由两个相互之间存在次序关系的实数构成的抽象数据类型，则可以利用实数的操作来实现复数的操作。【我的源码】*include<stdio.h>

*include<stdlib.h>*defineMA*LINE100typedefstruct

{

doublereal;

doubleimag;

}Comple*;Comple*InitComple*(doublereal,doubleimag)

{

Comple*c;

c.real=real;

c.imag=imag;

returnc;

}Comple*Add(Comple*c1,Comple*c2)

{

Comple*c;

c.real=c1.real+c2.real;

c.imag=c1.imag+c2.imag;

returnc;

}Comple*Subtract(Comple*c1,Comple*c2)

{

Comple*c;

c.real=c1.real-c2.real;

c.imag=c1.imag-c2.imag;

returnc;

}Comple*Multiply(Comple*c1,Comple*c2)

{

Comple*c;

c.real=c1.real*c2.real-c1.imag*c2.imag;

c.imag=c1.real*c2.imag+c1.imag*c2.real;

returnc;

}doubleGetReal(Comple*c)

{

returnc.real;

}doubleGetImag(Comple*c)

{

returnc.imag;

}voidRead(Comple**pc)

{

chara[MA*LINE];

inti,c;

for(i=0;(c=getchar())!=','&&c!=';';i++)

a[i]=c;

a[i]='\0';

pc->real=atof(a);

if(c==';')

{

pc->imag=0;

return;

}

for(i=0;(c=getchar())!=';';i++)

a[i]=c;

a[i]='\0';

pc->imag=atof(a);

}voidPrint(Comple*c)

{

if(c.real!=0&&c.imag!=0)

{

printf("%g",c.real);

if(c.imag>0)

printf("+i%g",c.imag);

else

printf("-i%g",-c.imag);

}

elseif(c.real==0&&c.imag!=0)

{

if(c.imag>0)

printf("i%g",c.imag);

else

printf("-i%g",-c.imag);

}

else

printf("%g",c.real);

}main()

{

intc;

Comple*c1,c2,result;

clrscr();

while(1)

{

printf("Selectanoperation(press1,2,3or4):\n\n");

printf("--------------------------------------------\n\n");

printf("1.Addacomple*toanother\n\n");

printf("2.Subtractacomple*fromanother\n\n");

printf("3.Multiplyacomple*toanother\n\n");

printf("4.Quit\n\n");

printf("--------------------------------------------\n\n");

while((c=getch())!='1'&&c!='2'&&c!='3'&&c!='4')

;

if(c=='4')

return;

printf("Inputtwocomple*es(e.g.:1.3,2.4;6;):\n\n");

Read(&c1);

Read(&c2);

printf("\nTheresultis:\t");

switch(c)

{

case'1':

result=Add(c1,c2);

break;

case'2':

result=Subtract(c1,c2);

break;

case'3':

result=Multiply(c1,c2);

break;

}

Print(result);

printf("\nTherealis:\t%g",GetReal(result));

printf("\nTheimagis:\t%g\n\n",GetImag(result));

}

}

读?数据构造〔C语言版〕?〔4〕从本节开场讨论线性表，这次先讨论线性表的顺序实现。一提到线性表，我们脑子很可能会出现数组、链表这样的概念。没错，数组和链表都是线性表，但它们只是线性表的两种实现，强调的是线性表的物理构造。我们研究一个数据构造时，一般先从它的逻辑构造入手，等研究清楚了逻辑构造再考虑具体的物理实现。在写程序时，思路也是一样的，先要分清哪些问题是逻辑的，哪些问题是物理的，先逻辑后物理是计算机解题的一般步骤。如果开场不想清楚逻辑，而一头扎到物理细节中，就容易理不清思路或者作出有缺陷的设计。当然这不是绝对的，很多情况下物理构造也会影响逻辑构造的设计。简单来说，一个线性表是n个一样特性的数据元素的有限序列。这里“n个一样特性的数据元素〞指的是数据对象，“序列〞指的是数据关系，每个数据元素都有一个确定的位置。从数据对象和数据关系入手，就很容易看清一个数据构造的本质。就线性表来说，只要*些数据存在次序关系，并且各个元素特性一样，就可以认为是一个线性表。下面我们来考虑线性表的顺序实现。在很多人包括我自己的眼里，线性表的顺序实现已经和数组画上了等号。虽然用数组实现线性表的顺序存储构造天经地义，但不应该把顺序实现局限在数组上。如果有一天你必须用汇编语言实现一个顺序存储的线性表，没有了数组你岂不是哭了。如作者所说，线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。用C语言实现时，由于线性表的长度可变，且所需最大存储空间随问题不同而不同，所以通常用动态分配的一维数组来实现。*defineLIST_INIT_SIZE100

//初始长度

*defineLISTINCREMENT

10

//分配增量typedefstruct{

ElemType*elem;

//存储基址

intlength;

//当前长度

intlistsize;

//存储容量

}SqList;用上述构造在分配存储空间时，初始分配可以用malloc，空间不够再分配时可以用realloc，这个函数保证在原分配根底上扩大容量时不影响其容。

读?数据构造〔C语言版〕?〔5〕考研终于尘埃落定，这个系列也得以继续。查看上篇文章的发表日期，已一月有余。回想这一个月中的种种经历，仍然心有余悸，听到看到的种种现象，更是让人触目惊心。还好，一切都过去了，我又可以静静地写文章了。上篇谈到线性表的顺序表示，这次接着谈线性表的链式表示。顺序表示的优势很明显，它在数据的物理位置中隐含了数据的逻辑关系，简单直接又威力无穷。但缺点也很明显，在做插入或删除操作时，需要移动大量数据。为了抑制这个缺点，可以使用链式存储。链式存储不用物理位置隐含表示数据关系，它增加了一个指针域专门用来描述数据间的先后次序关系。在一个节点中，数据域存储数据信息，而指针域存储数据关