搜索
第一章绪论1.数据结构:主要研究非数值计算问题中计算机的操作对象有哪些结构(逻辑结构)、这些结构在计算机中的表示及其操作的定义和实现问题。2.逻辑结构：不考虑实现，仅看问题域中数据元素根据相互间的逻辑关系形成的结构称为数据结构的逻辑结构。通常说的数据结构即此义。分类：如书目表根据一对一相邻关系形成线性结构、棋盘格局间根据下棋规则(一对多)形成一个树形数据结构，城市间据通路(多对多)形成图状结构，此外还有集合结构(除同属一个集合外，无其它关联)，共四类3.数据结构(数据元素及关系/结构)在计算机中的表示或者说映像称为该数据结构的物理结构或存储结构。4.顺序存储结构：关系采取顺序映像表示，即借助元素在存储器中的位置上的”相邻”关系隐式表示数据元素间具有关系。此时物理结构对应一个数组。优点:可根据起始地址随机访问各元素。缺点:需事先分配一足够大空间，且插入删除结点需移动大量数据。链式存储结构：关系采取链式映像表示，即借助附加信息指针显式表示元素间的关系，对应一个链表。优点是更有效利用空间、插入或者删除结点快，但要顺序访问各元素。5.度量指标：算法运行时间主要取决于基本操作的执行次数(频度)，执行次数通常随问题规模扩大而增加，增加越快意味着算法随问题规模的扩大，运行时间增长的也快，从而该种算法效果较差；增长越慢算法越好，故可用基本操作的频度随问题规模的增长率反映算法的效率。6.时间复杂度：频度函数的增长率基本与函数中“关键项”(去掉低次项和常数项)的增长率相同，故可用“关键项”反映算法效率。假设关键项为f(n)，用T(n)=O(f(n))表示算法时间增长率与f(n)增长率同阶。称O(f(n))为算法的渐近时间复杂度，简称时间复杂度。f(n)的增长率为f(n+1)/f(n)，如对复杂度为O(n)的算法其运行时间随问题规模增长率为1+1/n,复杂度为O(1)的算法时间增长率为1。7.按增长率由小至大的顺序排列下列各函数(2/3)n-2100-㏒2n-n1/2-n-n㏒2n-n3/2-2n-n!-nn第二章线性表1.顺序表：借助元素在存储器中位置上的”相邻”关系表示数据元素间具有的关系，如此存储的线性表称为顺序表。顺序表优点是实现简单方便，可随机访问各元素；缺点是插入或删除元素时会引起大量的数据元素移动(表尾除外)；对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常得不到充分利用。2.线性链表:采用链式存储结构的线性表对应一个链表。结点包含数据域和指针域两部分。链表名指向第一个结点(头指针)，尾结点指针域值为NULL。链表优点是空间利用好,插入删除不移动数据,表头表尾操作快(改进的单链表),位置概念强；缺点是需要顺序访问各元素，位序概念弱。顺序表相关程序：#defineLIST_INIT_SIZE100//…#defineLISTINCREMENT10//…typedef*****ElemType;typedefstruct{ElemType*elem;//存储空间基址intlength;//…intlistsize;//……}SqList；SqListLa,Lb,Lc;StatusInitList_Sq(SqList&L){//构造空线性表LL.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType))if(L.elem==0)exit(OVERFLOW);L.length=0;//初始化表长为0，“空”表L.listsize=LIST_INIT_SIZE;//初始化存储容量return(OK);}//InitList_SqvoidListDelete(SqList&L,inti,ElemType&e){//在顺序表L中删除第ｉ个元素，用ｅ返回其值．//i的合法值是[1，ListLength(L)]if(i1||iL.length)returnERROR;//删除位置不合理ElemType*p=&L.elem[i-1],*q=L.elem+L.length-1;e=*p;while(pq){*p=*(p+1);++p;}//删除位置后元素左移--L.length;returnOk;}//ListDelete_SqStatusListInsert_Sq(SqList&L,inti,ElemTypee){//在顺序表L的第i个位置前插入元素e,i的合法值为1..L.length+1if(i1||iL.length+1)returnERROR;//插入不合法if(L.length=L.listsize){//表满，增加存储容量ElemType*newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType))if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;}ElemType*q=&L.elem[i-1],*p=&L.elem[L.length-1];while(p=q){*(p+1)=*p;--p;}//插入位置后的元素右移*q=e;++L.length;returnOK;}//ListInsert_S线性表相关程序：typedef*****ElemType;typedefstructLNode{ElemTypedata;//数据域structLNode*next;//指针域}LNode,*LinkList;//默认带头结点,需说明LNodenode1;LinkListLa；StatusGetElem_L(LinkListL,inti,ElemType&e){//L为带头结点的单链表的头指针。第i个元素存在时,其值赋给e并返回OK,否则返回ERRORLNode*p=L-next;//p指向”第1个”结点，intj=1;//j为指向结点的位序while(p&&ji){//顺序查找，只要p不空且未到第i结点就前进p=p-next;++j;}if(!p)returnERROR;//第i个元素不存在e=p-data;//取第i个元素returnOK；}StatusListInsert_L(LinkList&L,inti,ElemTypee){//向链表L中第i个位置插入eLNode*p=L;intj=0;/*p始终指向第j个结点*/while(p&&ji-1){p=p-next;++j;}//寻找第i-1个结点if(!p)returnERROR;LNode*temp;temp=(LNode*)Malloc(sizeof(LNode));if(!temp)exit(OVERFLOW);temp-data=e;temp-next=p-next;p-next=temp;return(OK);}//ListInsert_LStatusListDelete_L(LinkList&L,inti,ElemType&e){LNode*p=L,*q;intj=0;/*p始终指向第j个结点*/while(p&&ji-1){p=p-next;++j;}//寻找第i-1个结点，j最终为i-1,除非到表尾p空if(!p||!p-next)returnERROR;//第i个或更前结点不存在q=p-next;e=q-data;p-next=q-next;free(q);return(OK);}//ListDelete_LStatusCreateList_L(LinkList&L,intn){//逆位序输入n个元素的值，建立带头结点的单链表L。LNode*p;L=(LinkList)malloc(sizeof(LNode));L-next=NULL;for(inti=1;i=n;++i){p=(LNode*)malloc(sizeof(LNode));//LNode*等同LinkListscanf(“…”,&p-data);p-next=L-next;L-next=p;//插入到表头}}//CreateList_L相关两表的归并voidMergeList_Sq(SqListLa,SqListLb,Sqlist&Lc){//归并非降顺序表La与Lb构成非降顺序表LcLc.listsize=Lc.length=La.length+Lb.length;Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType));If(!Lc.elem)exit(OVERFLOW);//存储分配失败ElemType*pa=La.elem,*pb=Lb.elem,*pc=Lc.elem;ElemType*pa_last=La.elem+La.listsize-1;ElemType*pb_last=Lb.elem+La.listsize-1;while(pa=pa_last&&pb=pb_last){//归并if(*pa=*pb)*pc++=*pa++;else*pc++=*pb++;}while(papa_last)*pc++=*pa++;//插入La剩余段while(pbpb_last)*pc++=*pb++;//插入Lb剩余段}//MergeList_SqStatusListMerge_SortedL(SortedSqListLa,SortedSqListLb,SortedSqList&Lc){//将两个有序顺序表La与Lb归并为有序顺序表Lcintla_len=ListLength_Sq(La);intlb_len=ListLength_Sq(Lb);inti=1,j=1,k=1;ElemTypea,b;InitList_Sq(Lc);while(i=la_len&&j=lb_len){//归并GetElem_Sq(La,i,a);GetElem_Sq(Lb,j,b);if(ab){ListInsert_Sq(Lc,k++,a);++i;}else{ListInsert_Sq(Lc,k++,b);++j;}}while(i=la_len)//插入La的剩余元素{GetElem_Sq(La,i++,a);ListInsert_Sq(Lc,k++,a);}while(j=lb_len)//插入Lb的剩余元素{GetElem_Sq(Lb,j++,b);ListInsert_Sq(Lc,k++,b);}returnOK;}//复杂度O(ListLength(La)+ListLength(Lb),因只在表尾插入)3.注意链表中next指针的应用，如插入，删除等操作各个元素的链接。4.顺序表的就地逆置思路：分别设两个指针p与q指向第一个和最后一个元素，当pq时{*p与*q互换，之后++p,--q}。单链表的就地逆置思路：令指针p指向首元结点,头结点断开,{将p所指结点插入到表头后,p后移,直至p为空}StatusListInverse_Sq(SqList&L){//顺序表就地逆置ElemType*p,*q;ElemTypee;p=L.elem;q=L.elem+L.length-1;while(pq){temp=*p;*p=*q;*q=temp;++p;--q;}returnOK;}StatusListInverse_L(LinkList&L){//思路:令指针p指向首元结点,头结点断开,{将p所指结点插入到表头后,p后移,至p空}LNode*p,*q;p=L-next;L-next=NULL;while(p!=NULL){q=p-next;//令q指向p的后继结点，以便以后p后移接下来两句将p所指向节点插入到头结点后p-next=L-next;L-next=p;p=q;//q后移}returnOK;}有序顺序表插入StatusListInsert_SortedSq(SqList&L,ElemTypee){/