数据结构讲义01col dsintro计算机系数据库与信息系统

学会合理地组织数据,有效地表示数据,有效地处理数据 译,《数据结构与算法 1.11.21.31.41.51.1 数学,硬件,软件之 结构批数据,按一定的 计算机中,并在这些数据上定义了一个运(1B=(K RK上的有穷关系的集合一般Rr}表–例如rki-1ki>|Ki∈K1in(2)常见逻辑关系有:线性(线性表，栈，队列，向量，字符串， =(K,R)，其–K＝｛k0,k1,…,kn-–R={r}，r={<ki-1,ki>|Ki∈K,1<i<n••…了）B={K,R}R={r}r满足下列条件：有且仅有一个称为根了）图：B={K,R},R={r},K中结点相对于r前驱和后继个数左图逻辑 =(K,R)，其R={r}，r={<A, <A,E>,<E,A>, <C,F>,<F,C>,<D,FR={r}，r={(A,C),(A,E),(B,C),(B,F),(C,D),(C,F),(D,F),(E,F)}

∧…∧ 密度(≤1)=数据本身 链表：rn·E/n(P+E)E 437321533Pointerlistof 据结构不同.例如,栈与队列数据抽象与过程抽象实现信息隐蔽和局部化以一个严格定义的过程接口的方式数抽象数据类型,定义了一组运算的数学模型.与物理 结构无关,使软件系统建立在数据之上(面向对象)逻辑定义：线性表list是由叫做元素 =(K,R)，其 R={r}，r={<ki-1,ki>|Ki∈K,1<i<nclasslist{ //ListclassADTlist(constint voidinsert(constELEM&);voidappend(constELEM&);ELEMremove();voidvoidnext(); voidprev();intlength()const;voidsetPos(constvoidsetValue(constELEM&);ELEMcurrValue()const;boolisEmpty()const;boolisInList()boolfind(const (1(2(3递归法分治法(二分法检索(4回溯法(八皇后(8)typedefstructelem{intkey;datatype}#defineUNSUCCESSFUL- 性表array中顺序检索，查找关键码i为关键码K在表中的下标，i值为-1表示检索intseqsrch(intK,ELEM*array,intn){inti=n-1;while(i>=0&&array[i].key!=K)i--;returni;}1假设检索每个关键码是等概率的，Pi=n-Pi·(n-i)i=

1n-(n-ni== i=n+12

i= ） –如果kmid=k，–当kmid>k时，检索继 –相反地，若kmidk，就可以忽略mid以前的那部–Kmidk。该过程至多需要重复 n次intbinary(intK,ELEM*array,intleft,intright)返回值为K//landrarebeyondtheboundsofintl=left-1;intr=right+1;while(l+1!=r){ //Stopwhenlandrmeetintmid=(l+r)/2; //Lookatmiddleif(K<array[mid].key)r= //Inleftif(K==array[mid].key)returnmid;//Founditif(K>array[mid].key)l=mid; //Inrighthalf}returnUNSUCCESSFUL;//valueKnotin} 1011121314(1)(4) 检索关键码45。l=0;r=15;K=45第一次：mid=7;l=7;第二次：mid=11;array[11]=56>45r=11;(l=7)第三次：mid=9;r=9;第四次：mid=8;array[8]=45==45；return7352 2 n2)失败的检索长度是 或 n二分法检索性能分析（续E(n)

ji2i-(ni=( (n+1)- 4)

(n+1)-2

(n>–缺点：要排序、顺 时解决该问题所占用的时间1增至f(n),则称该算法的时间代价为f(n)。时解决该问题所占用的空间1增至f(n),则称该算法的空间代价为f(n)。大O表示法称某程序的时间(或空间)代价O(f(n)),若存在正常数c和n0,当问题的规模n≥n0后,该算法的时间(或空间)代价T(n)≤c·f(n),也称该算法的时间(或空间)对于所有足够大的输入数据集（n≥n0），算 则:f1(n)+f2(n)=Ｏ(max(f1(n), 则:f1(n)·f2(n)=for,whiledo-whilesum=for(i=1;i<=n;i++)for(j=1;j<=n;j++)T(n)=c１＋c2n2例：假设CPU每秒处理106个指令，对21016106例：假设CPU每秒处理106个指令，对于输入规模为n=108的问题，时间代价T(n)=T(108)=1082.66109106对T(n2n2£3600·n£42,T(n)=nlogn£3600·n£133,000,处理输入规