《数据结构知识点整理(清华大学出版社)》由会员分享，可在线阅读，更多相关《数据结构知识点整理(清华大学出版社)（12页珍藏版）》请在金锄头文库上搜索。
1、第一章 绪论1. 数据结构:主要研究非数值计算问题中计算机的操作对象有哪些结构(逻辑结构)、这些结构在计算机中的表示及其操作的定义和实现问题。2. 逻辑结构：不考虑实现，仅看问题域中数据元素根据相互间的逻辑关系形成的结构称为数据结构的逻辑结构。通常说的数据结构即此义。分类：如书目表根据一对一相邻关系形成线性结构、棋盘格局间根据下棋规则(一对多)形成一个树形数据结构，城市间据通路(多对多)形成图状结构，此外还有集合结构(除同属一个集合外，无其它关联)，共四类3. 数据结构(数据元素及关系/结构)在计算机中的表示或者说映像称为该数据结构的物理结构或存储结构。4. 顺序存储结构：关系采取顺序映像表示
2、，即借助元素在存储器中的位置上的”相邻”关系隐式表示数据元素间具有关系。此时物理结构对应一个数组。优点:可根据起始地址随机访问各元素。缺点:需事先分配一足够大空间，且插入删除结点需移动大量数据。链式存储结构：关系采取链式映像表示，即借助附加信息指针显式表示元素间的关系，对应一个链表。优点是更有效利用空间、插入或者删除结点快，但要顺序访问各元素。5. 度量指标：算法运行时间主要取决于基本操作的执行次数(频度)，执行次数通常随问题规模扩大而增加，增加越快意味着算法随问题规模的扩大，运行时间增长的也快，从而该种算法效果较差；增长越慢算法越好，故可用基本操作的频度随问题规模的增长率反映算法的效率。6.
3、 时间复杂度：频度函数的增长率基本与函数中“关键项”(去掉低次项和常数项)的增长率相同，故可用“关键项” 反映算法效率。假设关键项为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 -n2n-n3/ 2-2n-n!-nn第二章 线性表1. 顺序表：借助元素在存储器中位置上的”相邻”关系
4、表示数据元素间具有的关系，如此存储的线性表称为顺序表。顺序表优点是实现简单方便，可随机访问各元素；缺点是插入或删除元素时会引起大量的数据元素移动(表尾除外)；对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常得不到充分利用。2. 线性链表:采用链式存储结构的线性表对应一个链表。结点包含数据域和指针域两部分。链表名指向第一个结点 (头指针)，尾结点指针域值为NULL。链表优点是空间利用好,插入删除不移动数据,表头表尾操作快(改进的单链表),位置概念强；缺点是需要顺序访问各元素，位序概念弱。顺序表相关程序：#define LIST_INIT_SIZE 100 /#define
5、LISTINCREMENT 10 /typedef * ElemType;typedef structElemType *elem; /存储空间基址 int length; / int listsize; / SqList；SqList La,Lb,Lc;Status InitList_Sq(SqList &L)/构造空线性表L L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType) if(L.elem=0)exit(OVERFLOW);L.length=0; /初始化表长为0，“空”表 L.listsize=LIST_INIT_SIZ
6、E;/初始化存储容量 return(OK);/InitList_Sqvoid ListDelete(SqList &L,int i,ElemType &e)/在顺序表L中删除第个元素，用返回其值/i的合法值是1，ListLength(L) if(iL.length) return ERROR;/删除位置不合理 ElemType *p=&L.elemi-1,*q=L.elem+L.length-1; e=*p; while(pq)*p=*(p+1);+p;/删除位置后元素左移 -L.length; return Ok;/ListDelete_SqStatus ListInsert_Sq(SqLi
7、st &L,int i, ElemType e)/在顺序表L的第i个位置前插入元素e,i的合法值为1.L.length+1 if(iL.length+1) return ERROR;/插入不合法 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
8、=&L.elemi-1, *p=&L.elemL.length-1; while(p=q) *(p+1)=*p; -p; /插入位置后的元素右移 *q=e; +L.length; return OK;/ListInsert_S线性表相关程序：typedef * ElemType;typedef struct LNode ElemType data; /数据域 struct LNode * next; /指针域LNode,*LinkList;/默认带头结点,需说明LNode node1; LinkList La；Status GetElem_L(LinkList L,int i,ElemType
9、 &e)/L为带头结点的单链表的头指针。第i个元素存在时,其值赋给e并返回OK,否则返回ERROR LNode *p=L-next; /p指向”第1个”结点，int j=1;/ j为指向结点的位序 while(p&jnext;+j; if(!p)return ERROR; /第i个元素不存在 e=p-data; /取第i个元素 return OK；Status ListInsert_L(LinkList &L, int i, ElemType e)/向链表L中第i个位置插入eLNode *p=L; int j=0; /*p始终指向第j个结点*/while(p&jnext; +j;/寻找第i-1
10、个结点 if(!p) return ERROR; LNode *temp; temp=(LNode *)Malloc(sizeof(LNode); if(!temp)exit(OVERFLOW); temp-data=e; temp-next=p-next; p-next=temp; return(OK);/ListInsert_LStatus ListDelete_L(LinkList &L, int i, ElemType &e) LNode *p=L,*q; int j=0; /*p始终指向第j个结点*/while(p&jnext; +j;/寻找第i-1个结点，j 最终为i-1,除非到表
11、尾p空if(!p|!p-next) return ERROR;/第i个或更前结点不存在q=p-next; e=q-data; p-next=q-next; free(q); return(OK);/ListDelete_LStatus CreateList_L(LinkList &L, int n)/逆位序输入n个元素的值，建立带头结点的单链表L。LNode *p; L=(LinkList) malloc(sizeof(LNode);L-next=NULL;for(int i=1;idata); p-next=L-next;L-next=p;/插入到表头 /CreateList_L相关两表的归
12、并void MergeList_Sq (SqList La,SqList Lb,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;ElemTyp
13、e *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_SqStatus ListMerge_SortedL(SortedSqList La,SortedSqList Lb,SortedSqList &Lc)/将两个有序顺序表La与Lb归并为有序顺序表Lcint la_len=ListLength_Sq(La);int lb_len=ListLength_Sq(Lb); int i=1,j=1,k=1; ElemType a,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;
