数据结构知识点整理(清华大学出版社).doc

第一章 绪论1. 数据结构:主要研究非数值计算问题中计算机得操作对象有哪些结构(逻辑结构）、这些结构在计算机中得表示及其操作得定义与实现问题。2. 逻辑结构:不考虑实现，仅瞧问题域中数据元素根据相互间得逻辑关系形成得结构称为数据结构得逻辑结构。通常说得数据结构即此义.分类：如书目表根据一对一相邻关系形成线性结构、棋盘格局间根据下棋规则(一对多）形成一个树形数据结构，城市间据通路（多对多）形成图状结构，此外还有集合结构（除同属一个集合外,无其它关联),共四类3. 数据结构（数据元素及关系结构）在计算机中得表示或者说映像称为该数据结构得物理结构或存储结构.4. 顺序存储结构：关系采取顺序映像表示,即借助元素在存储器中得位置上得相邻关系隐式表示数据元素间具有关系。此时物理结构对应一个数组。优点:可根据起始地址随机访问各元素。缺点：需事先分配一足够大空间，且插入删除结点需移动大量数据。链式存储结构:关系采取链式映像表示,即借助附加信息指针显式表示元素间得关系,对应一个链表。优点就是更有效利用空间、插入或者删除结点快，但要顺序访问各元素。5. 度量指标：算法运行时间主要取决于基本操作得执行次数（频度)，执行次数通常随问题规模扩大而增加,增加越快意味着算法随问题规模得扩大,运行时间增长得也快，从而该种算法效果较差；增长越慢算法越好,故可用基本操作得频度随问题规模得增长率反映算法得效率.6. 时间复杂度：频度函数得增长率基本与函数中“关键项”(去掉低次项与常数项）得增长率相同，故可用“关键项”反映算法效率。假设关键项为f（n）,用T(n）=O（f(n)表示算法时间增长率与（n)增长率同阶。称O（f（n)为算法得渐近时间复杂度,简称时间复杂度。f(n）得增长率为f（n+1）f（n），如对复杂度为O（）得算法其运行时间随问题规模增长率为1/n，复杂度为O（1）得算法时间增长率为1.7. 按增长率由小至大得顺序排列下列各函数（2/3)n 1002n2nn2nn3/ 2-2n！-nn第二章 线性表1. 顺序表：借助元素在存储器中位置上得”相邻”关系表示数据元素间具有得关系,如此存储得线性表称为顺序表。顺序表优点就是实现简单方便,可随机访问各元素；缺点就是插入或删除元素时会引起大量得数据元素移动（表尾除外)；对于长度变化较大得线性表,要一次性地分配足够得存储空间，但这些空间常常得不到充分利用。2. 线性链表：采用链式存储结构得线性表对应一个链表。结点包含数据域与指针域两部分。链表名指向第一个结点 (头指针），尾结点指针域值为NULL。链表优点就是空间利用好，插入删除不移动数据，表头表尾操作快（改进得单链表）,位置概念强；缺点就是需要顺序访问各元素，位序概念弱.顺序表相关程序：dfineLIST_I_IE 1 /fineLSTINCRMENT 10 /typedef * lemype;tpedef strutElemTpe *eem； /存储空间基址 nt leh； / i litize; / SqLs；Sit L,Lb，Lc；Status nitLit_Sq(SqLit&）/构造空线性表L L、elm=（eType）mloc(LSTINI_SIZ*sizeof(Eeype)f(、eem=0)exi（OVEFLOW）；L、length0; /初始化表长为0,“空”表 L、lstsLISTINIT_SI；/初始化存储容量 retr（OK）;/IniLi_Sqid LisDelete(SLstL，int i，EemTye &e）/在顺序表L中删除第个元素,用e返回其值。/i得合法值就是1，ListLengh（L） if（i、lngth） urn ERR；/删除位置不合理 EleType *=&L、lei1，*qL、elem+L、lenh1; e*p； we（p)p=（+);+；/删除位置后元素左移 -L、lngt; return Ok;/LstDelet_SqttusListIns_S（SLit &L,it ， ElTyp e)在顺序表L得第i个位置前插入元素e,i得合法值为1、length+1 f（iL、length+1） turn ERROR;/插入不合法 (L、ngt=L、lstsize） /表满,增加存储容量mTenewe=(EeTyp ）ealoc（L、el,(、stsize+LITCREMEN）*sizef(EeTpe)i(！ewbase)ext(OVEFLW); 、elem=ewase;、istizeISTCRMENT; ElmTyp q=&L、lmi-1,*p=L、leL、length1； whi（p=q） （p+1)=p； ； /插入位置后得元素右移 q=e; +L、lenth； erK;/istInsetS线性表相关程序：tyede * ElemType；ypeef strct Lode ElemTye ta; /数据域 uct Nde et； /指针域Lde，LinkList;/默认带头结点,需说明LNd node1； Likt L;Stts etElem_L（nkLt L， i，lemType e)/为带头结点得单链表得头指针.第i个元素存在时,其值赋给e并返回OK,否则返回ERR LNode *ex;/p指向第个”结点，int j=1；/j为指向结点得位序 while(p&j)/顺序查找,只要p不空且未到第i结点就前进 p=pnext；+j; f（！）retu ERRR； 第i个元素不存在 e=pat; /取第个元素reurn OK;SttuisInsrt（LinLit L， n， lmypee）/向链表L中第个位置插入eLNodepL； int j0; /p始终指向第j个结点/while(p&j-1)p=nxt；+j；/寻找第i1个结点 if(！) eturn RROR； LNode temp； temp=（Lode *）Maoc(siof（LNode)； if（！tp)xt（OVERFLOW）; tempda=; tempnext-ext； p-ext=te； rur(O）;Listnet_LStatu Listlte_（Lnkist L, nt ， Elemype e) oepL,q； intj； p始终指向第j个结点/whle（&ji1）-net; +j；/寻找第i1个结点, 最终为i1，除非到表尾p空if（！p|！pnext） eturn EROR;/第i个或更前结点不存在=-next; e=ata; peqnxt； fre（）； run（O)；/istDleteLtatus CateListL(LinkLitL, nt ）/逆位序输入个元素得值,建立带头结点得单链表。o p; (LinkList）mlloc(szeof（LNod）;L-nx=NUL；or(nt i=1;inext;/插入到表头 /CreateLst_L相关两表得归并voidMergei_Sq (SqLst La，Sqist Lb，Sqlit &)/归并非降顺序表a与Lb构成非降顺序表LcLc、ltize=L、length=La、lenth+b、ngth;Lc、elem=(lmTye) maloc（Lc、liszesizeof（EleType）；f（！Lc、ele)exit（OVFLW)； /存储分配失败EmTe pa=L、ele，*pb=Lb、ele，*pc=Lc、eem；ElmTyp plas=L、ele+La、lstize1；ElemType *pb_last=Lb、ele+La、ssize1;hil(a=pa_lat&b=p_last）/归并 f(*papb)*pc+=pa+; lse *pc+=*pb+；while（papalst）*pc+=pa+; /插入La剩余段whle（pb_lat) pc+b+； /插入b剩余段/MergeLis_SqSatu LisMergeStedL(oedSList a,SorteSqLisLb，SotedSqist ）/将两个有序顺序表La与b归并为有序顺序表Lcint la_len=ListLngh_Sq(a）;ntl_le=LsLengh_Sq(Lb)； nt=1，j1，k=1； ElemTy a，b; nLt_S（c）； while(la_len&j=_len） /归并 GetElem_Sq(a，）；etle_Sq（L，j,）； i（axt; nxt=UL;hie（p!=ULL) q=p-ex；令指向p得后继结点,以便以后p后移接下来两句将p所指向节点插入到头结点后 pnext=L-nxt； nex=; q;/q后移 reurn OK; 有序顺序表插入Sat LisInsrt_SortedS(Sqist L，lemType ）/在非降顺序表L中插入元素e，使得L中各元素仍然非降。注意插入位置据求得/思路:从最后一个元素开始,只要它比待插入元素大就后移.条件不成立时退出循环，将e插入当前位置后即可。顺序表插入操作莫忘表满得处理。只要就是顺序表得插入操作就需要判断就是否表满,对于链表则无此要求i（、egth=L、lstsiz）/表满,增加存储容量EemTye ewbase=(Elmpe *）reallc(、elem,(、lste+LITINCREMENT）szof（Elemy）; if（！newbse) exit（OVERFOW）；L、ele=ebae； L、lisize=LISICREMENT； /下面从最后一个元素开始,只要大于e就后移，最后插入当前位置后 =L、ele、lengt-; hile(L、empe)(p1）=p；p; *(p+1）=e; +L、length;/表长加1 return O;5. 循环链表、双向链表、双向循环链表得特点与基本操作.主要就是插入删除得相关指针操作。/线性表得双向（循环）链表存储结构-typedf truLNod mType data; srct DuLNod ir； struct uNdnext;Dode,DLList;Satu LstIsr_Du（DuLinkist ,nt ，EleTye )在带头结点得双向链表L得第i个位置插入e，1i表长+1 oe *p=； it j=0； wile(ji1&p）pnext;+j; if(!p）rturERROR； s=（DuLNode *）mallo(sizeo(uLNo)； if（！s）exit(OVRFLOW）； sdatae； s-prior；sext=pnext； /记:注意分析指针改变 pnext-pir=s;pnext=s; /次序对结果得影响 return O;另外瞧下多项式得相关课件，老师复习提纲上有写这方面得代码。第三章 栈与队列1. 栈（Sk)就是定义在线性结构上得抽象数据类型，其操作类似线性表操作，但元素得插入、删除与访问都必须在表得一端进行,为形象起见,称允许操作端为栈顶(op），另一端为栈底（bae)，注意Top指向待插入位置.特性:Last I rst Out后进先出/总就是访问最近插入得一个/按插入顺序倒着访问。#defin STAC_NI_SIZE 100efie TAINCREMET 10typde ?？SEeType；/栈元素类型typedef rct SElmType base; /栈底指针 leme*to； /栈顶指针 int stacksiz；/栈容量 SqStackSttusIntStc(SqStak &S）/构造空栈 、ae=（ElmType*）maloc(STAK_T_SIZEizef(SElmType）)； f（！、base)ex（OVEFOW）； /存储分配失败 S、top=S、base; /空栈 、stacksize=STACK_INIT_SZE; etr(K）；/Stack 复杂度”O（1）”Stts DestroyStac（SStck&）/销毁栈S ree（S、se)； S、a=NULL； 、top=NUL; S、sacsie0; retur OK； 复杂度（1）Statu ClerStc(SqStack)置为空栈 S、top=S、base; rtr OK; /复杂度O(1)ttus Pu（SqStck &S，SElemType e）插入e为栈顶元素 f(S、tS、base=S、stasiz）/判断栈满/栈满则应重新分配空间 、a=（SElemType ）r（S、bae，(S、scksize+CINCEMNT)zeof(EleTpe)）; if（！S、ba)eit(OVFOW）； 、top=（S、base+S、stacksize）;/使得S、top重新指向栈顶，因ralloc S、tacksi=STAKINCEENT； 、tp +=e； /top指向待插入位置 retur(OK）；/Pus ，复杂度O(1)Satu Pop(SqSack S,SElemTe e)/若栈不空则栈顶元素出栈并用e带回其值 f(、to=S、as）rerERRO；/判断栈空 e=(-S、tp)； /栈顶元素为（S、to) return OK;/复杂度O(）StatsSakEpy（SqSta S)if(S、op=S、base)etun TRUE；lse ret FALS;int SakLenth （Sqtack S）etun (、topS、as）； Statu GtTop（Stac S，EleType e） （S、top=S、bae)retunEOR; e(S、to-1)； /注意top指向待插入位置 eturnOK；栈得遍历一直没用到，可以自己找找课件瞧。2. 队列类似线性表与栈，也就是定义在线性结构上得ADT,与线性表与栈得区别在于,元素得插入与删除分别在表得两端进行。类似日常生活中排队,允许插入得一端为队尾(rear),允许删除端称队头(ft）。特性：First InFirst u先进先出,如操作系统中得作业队列与打印任务队列、日常生活中各类排队业务等均可用队列模拟。fine Qepe typedf srut Ne QEemType ata; stct Nd *e; QNod， Queet;tpdef strct uePr frot；/队头指针 ueePtr e； /队尾指针 Linkue；/ 链队列Stat Initu （LinQuee &Q）/ 构造一个空队列Q 、ront=、ear=（QePtr）moc(szeof(QNode）); if （!Q、ront）xit （OVERFLOW); Q、frontnext NULL； /莫忘!！ eurnOK；/时间复杂度(1）Stat estrouue （kuee Q）/销毁队列Q,此处不同于教材,先清空元素结点,后释放头结点 QueuePtr p=Q、frt-nxt；whle(p）/依次释放首元素至最后一个元素、frot-next=pnxt;ee(p）；p=Q、frontex；free(Q、front);Q、fon=NU；Q、rear=ULL； etnO;/去掉下划线部分为置空操作, 复杂度O（n） StausEueue (LnkQueue Q, Eleype e） / 插入元素为得新得队尾元素 ueutr ； p=(Quuetr)malloc（sizeof(Qod）); f (!p)it(VERFLOW)；/存储分配失败 pata = e； pext NULL；/莫忘!！ Q、rea-ne = p； Q、rear p; retur ; /复杂度(1）Satus DQee(LiQueu &， QEemype ) / 若队列不空,则删除Q得队头元素，用 e 返回其“值” if（Q、rt=、ea） etrn ERRR；/空队列 euePtr= Q、frontxt; e= pdaa; Q、front-net = -next; if(Q、e= p) Q、rr=Q、rot;/只1个结点时改尾指针 e（p)； rtrn OK；/复杂度O（1）3. 循环队列#efine AQSI 10 /最大队列长度typedef strct QElemype base；/ 动态分配存储空间 nt front； / 头指针，队列不空则指向队列头元素 it rer; /尾指针，指向待插入元素位置 Squue；Status IniQueue（SqQuue Q) / 构造一个空队列Q Q、base=(lemTye*)mallc（MXSIZEizeo （QElmyp)； if (!Q、bas） xit （OEROW）; / 存储分配失败 Q、frt 、rear = ; ern OK;/复杂度(1)Sttus Detoe(SqQueueQ） /销毁队列Qfree(Q、bse）；Q、frnt =Q、rar = 0； retur OK;/时间复杂度O（1），比链队列快Status Ceaeue(Squ Q) / 将队列Q置空 Q、rot=Q、rar=；/只要想等即可 rer OK;/复杂度O（)比链队列快Stats nueue（SqQuue Q, Elemype e) / 插入元素e为Q得新得队尾元素,无法插入（已满）则返回ERROR if（Q、ar）MAXIZE=、front）retun ERROR；判断循环队列满得条件 Q、baseQ、rear e； 、rea (Q、rer+1)% AXQSE； /加便可能越界，故取余 reurn K;/时间复杂度O(1）Satu DQue （e Q, EmTye&e） /队列不空则删除队头元素, 用e带回其值并返OK；否则返ERROR if (、rar=Q、rnt） returnROR；/判断循环队列空 = Q、baseQ、o；Q、fn=（Q、fn1)% XSIE； /加就可能越界,故取余 returnK;/时间复杂度(1）in ueeLengh（SQueu Q） /返回队长rern (Q、r、ont+MXQSIZ）%MAXQSIZE；/减可能为负/时间复杂度(1)，比链队列快，可修改链队列定义Stus QueueEmpty（SqQueu Q) /判断队列空 if （、reaQ、font) rturnTRUE; ele reurn ASE;/O()Staus Gete（SqueQ，QElemye ） if （Q、rear=Q、frot）etu RROR；=、e、fro;retr ;/ O（1）若要修改对头元素得值可新设Stead（&Q,e）4. 证明:若借助栈由输入序列12n得到得输出序列为p1p2p（它就是输入序列得一个排列）,则在输出序列中不可能出现这样得情形:存在ijk使pki。思路:假设pjkpi往证in,则该结点无右孩子,否则，编号为2i+1 得结点为其右孩子结点.4. 含n个结点得树中，只有度为k得分支结点与度为0得叶子结点，试求该树含有得叶子结点数提示：n0+n=n； e=knkk(n-n)=n故:n(nk+）/5. 二叉树就是度不大于得有序树（每个结点最多两棵子树,子树有左右之分)。6. 满二叉树：设深度为k，含2k1个结点得二叉树。结点数达最大。7. 完全二叉树:设树中含个结点， 它们与满二叉树中编号为1至得结点位置上一一对应（编号规则为由上到下,从左到右）。相比满二叉树仅少“最后得”若干个,不能少中间得。完全二叉树特点：(1)叶子结点出现在最后2层或多或1层。（）对于任意结点，若其右分支下得子孙得最大层次为L，则左分支下得子孙得最大层次为或L+。8. 二叉树顺序存储：将二叉树映射到完全二叉树上,不存在得结点以空标记，之后用地址连续得存储单元（一维数组）依次自上而下、自左而右存储完全二叉树上得各元素、（将一般二叉树以完全二叉树形式存储)，最坏情况下k个结点需2k1个单元。但适合完全二叉树得存储，操作简单方便.9. 二叉树链表存储：二叉链表包含内容,左孩子及右孩子得指针。三叉链表多了一个指向双亲结点得指针。typde struct BiTode TElTpe daa； struct BiTNode child， rhid； Biod, iTee；iTre T;ypeef stuct TriTNe strt TrNde *aet； TElmpe ta； suctTrTNode *lcil， rhild;Tro， Trr10. 先(根）序遍历:树非空则访问根结点,后递归地先序遍历其左子树；再递归地先序遍历其右子树；空则无操作。中（根）序遍历：树非空则递归地中序遍历根左子树;后访问根结点，再递归地中序遍历右子树;空则无操作.后(根）序遍历:树非空则递归地后序遍历根右子树；后递归地后序遍历右子树,再访问根结点;空则无操作层次遍历:由上到下，由左到右,不宜递归tyeef structBiTNode TElemTp dta； stuctBiTode *lchil, *rchld;BiTode， *iTre;BTee T；/tyedefint TElemTp；Status CreaeBiTree(BTee)/递归创建二叉树 TEleTye e; sn(%,e）； if（e=0）=NUL； ele =(Bre)mlloc(sizeof（BTod)）; if(！T）it(OVERFL）; Tdata=e； CeiTre(T-lchid); CrateiTree（rcil)； etn OK; /若元素为字符型则输入时不可随意加空格tatus DstoyBiTre(iTree T)/二叉链表得后序递归销毁 f(!T）etur O; lse DesyBiTree(Tlchild