数据结构考研讲义.doc
《数据结构考研讲义.doc》由会员分享,可在线阅读,更多相关《数据结构考研讲义.doc(74页珍藏版)》请在咨信网上搜索。
1、目录绪论30、1 基本概念3第一章 线性表41、1 线性表得定义41、2 线性表得实现41、2、2 线性表得链式存储结构6第二章 栈、队列与数组112、1 栈112、2 队列152、3 特殊矩阵得压缩存储172、3、1 数组172、3、2 特殊矩阵17第三章 树与二叉树203、1 树得概念201、树得定义202.相关术语203、2 二叉树213、2、1 定义与性质213、2、2 二叉树得存储223、2、3 二叉树得遍历233、2、4 线索二叉树253、3 树与森林293、3、1 树得存储结构293、3、2 森林与二叉树得转换303、3、3 树与森林得遍历303、4 哈夫曼( Huffman)树
2、与哈夫曼编码31第四章 图324、1 图得概念324、2 图得存储及基本操作334、2、1 邻接矩阵334、2、2 邻接表334、3 图得遍历354、3、1 深度优先搜索354、3、2 广度优先搜索354、4 图得基本应用374、4、1 最小生成树374、4、2 最短路径374、4、3 拓扑排序394、4、4 关键路径40第五章 查找425、1 查找得基本概念425、2 顺序查找法435、3 折半查找法445、4 动态查找树表455、4、1 二叉排序树455、4、2 平衡二叉树475、4、3 B 树及其基本操作、 B+树得基本概念495、5 散列表515、5、2 常用得散列函数515、5、3
3、处理冲突得方法525、5、4 散列表得查找525、5、5 散列表得查找分析53第六章 排序546、1 插入排序546、1、1 直接插入排序546、1、2 折半插入排序546、2 冒泡排序556、3 简单选择排序566、4 希尔排序576、5 快速排序586、6 堆排序606、7 二路归并排序626、8 基数排序636、9 各种内部排序算法得比较64绪论0、1 基本概念1、数据结构数据结构就是指互相之间存在着一种或多种关系得数据元素得集合。数据结构就是一个二元组 Data_Structure ( D, R),其中, D 就是数据元素得有限集, R 就是D 上关系得有限集。2、逻辑结构:就是指数据
4、之间得相互关系。通常分为四类结构:( 1)集合:结构中得数据元素除了同属于一种类型外,别无其它关系。( 2)线性结构:结构中得数据元素之间存在一对一得关系。( 3)树型结构:结构中得数据元素之间存在一对多得关系。( 4)图状结构:结构中得数据元素之间存在多对多得关系。3、存储结构:就是指数据结构在计算机中得表示,又称为数据得物理结构。通常由四种基本得存储方法实现:( 1)顺序存储方式。数据元素顺序存放,每个存储结点只含一个元素。存储位置反映数据元素间得逻辑关系。存储密度大。但有些操作(如插入、删除)效率较差。( 2)链式存储方式。每个存储结点除包含数据元素信息外还包含一组(至少一个)指针。指针
5、反映数据元素间得逻辑关系。这种方式不要求存储空间连续,便于动态操作(如插入、删除等),但存储空间开销大(用于指针),另外不能折半查找等。( 3)索引存储方式。除数据元素存储在一组地址连续得内存空间外,还需建立一个索引表,索引表中索引指示存储结点得存储位置(下标)或存储区间端点(下标)。( 4)散列存储方式。通过散列函数与解决冲突得方法,将关键字散列在连续得有限得地址空间内,并将散列函数得值解释成关键字所在元素得存储地址。其特点就是存取速度快,只能按关键字随机存取,不能顺序存取,也不能折半存取。2 算法与算法得衡量1、算法就是对特定问题求解步骤得一种描述,就是指令得有限序列。其中每一条指令表示一
6、个或多个操作。算法具有下列特性:有穷性确定性可行性输入输出。算法与程序十分相似,但又有区别。程序不一定具有有穷性,程序中得指令必须就是机器可执行得,而算法中得指令则无此限制。算法代表了对问题得解,而程序则就是算法在计算机上得特定得实现。一个算法若用程序设计语言来描述,则它就就是一个程序。2、算法得时间复杂度:以基本运算得原操作重复执行得次数作为算法得时间度量。一般情况下,算法中基本运算次数 T(n)就是问题规模 n(输入量得多少,称之为问题规模)得某个函数f(n),记作:T(n) (f(n);也可表示 T(n) m(f(n),其中 m 为常量。记号“O”读作“大 O”,它表示随问题规模 n 得
7、增大,算法执行时间 T(n)得增长率与 f(n)得增长率相同。注意:有得情况下,算法中基本操作重复执行得次数还随问题得输入数据集不同而不同。常见得渐进时间复杂度有: (1)(log2n)(n)(nlog2n)(n2)(n3)(2n) O(n!) O(nn)。3、算法得空间复杂度:就是对一个算法在运行过程中临时占用得存储空间大小得量度。只需要分析除输入与程序之外得辅助变量所占额外空间。原地工作:若所需额外空间相对于输入数据量来说就是常数,则称此算法为原地工作,空间复杂度为 O(1)。第一章 线性表1、1 线性表得定义线性表就是一种线性结构,在一个线性表中数据元素得类型就是相同得,或者说线性表就是
8、由同一类型得数据元素构成得线性结构,定义如下:线性表就是具有相同数据类型得n(n0)个数据元素得有限序列,通常记为:(a1, a2, ai-1, ai, ai+1, an)其中n为表长, n0 时称为空表。需要说明得就是: ai为序号为 i 得数据元素( i=1,2,n),通常将它得数据类型抽象为ElemType, ElemType根据具体问题而定。1、2 线性表得实现1、2、1 线性表得顺序存储结构1、顺序表线性表得顺序存储就是指在内存中用地址连续得一块存储空间顺序存放线性表得各元素,用这种存储形式存储得线性表称其为顺序表。因为内存中得地址空间就是线性得,因此,用物理上得相邻实现数据元素之间
9、得逻辑相邻关系就是既简单又自然得。设a得存储地址为Loc(a),每个数据元素占d个存储地址,则第i个数据元素得地址为:Loc(ai)=Loc(a)+(i-1)*d 1in这就就是说只要知道顺序表首地址与每个数据元素所占地址单元得个数就可求出第i个数据元素得地址来,这也就是顺序表具有按数据元素得序号随机存取得特点。线性表得动态分配顺序存储结构:#define LIST_INIT_SIZE 100 /存储空间得初始分配量#define LISTINCREMENT 10 /存储空间得分配增量typedef structElemType *elem; /线性表得存储空间基址int length; /当
10、前长度int listsize; /当前已分配得存储空间SqList;2、顺序表上基本运算得实现( 1)顺序表得初始化顺序表得初始化即构造一个空表, 这对表就是一个加工型得运算, 因此, 将L设为引用参数,首先动态分配存储空间,然后,将length置为0,表示表中没有数据元素。int Init_SqList (SqList &L)L、elem = (ElemType * )malloc(LIST_INIT_SIZE * sizeof(ElemType);if (!L、elem) exit (OVERFLOW); /存储分配失败L、length=0;L、 listsize = LIST_INIT
11、_SIZE; /初始存储容量return OK;( 2)插入运算线性表得插入就是指在表得第i(i得取值范围: 1in+1)个位置上插入一个值为 x 得新元素,插入后使原表长为 n得表:(a1, a2, 、 , ai-1, ai, ai+1, 、 , an)成为表长为 n+1 表:(a1, a2, 、, ai-1, x, ai, ai+1, 、, an ) 。顺序表上完成这一运算则通过以下步骤进行: 将aian 顺序向下移动,为新元素让出位置;(注意数据得移动方向:从后往前依次后移一个元素) 将 x 置入空出得第i个位置; 修改表长。int Insert_SqList (SqList &L, i
12、nt i, ElemType x)if (i L、length+1) return ERROR; / 插入位置不合法if (L、length = L、listsize) return OVERFLOW; / 当前存储空间已满,不能插入/需注意得就是,若就是采用动态分配得顺序表,当存储空间已满时也可增加分配q = &(L、elemi-1); / q 指示插入位置for (p = &(L、elemL、length-1); p = q; -p)*(p+1) = *p; / 插入位置及之后得元素右移*q = e; / 插入e+L、length; / 表长增1return OK;顺序表上得插入运算, 时
13、间主要消耗在了数据得移动上, 在第i个位置上插入 x , 从 ai 到an 都要向下移动一个位置,共需要移动 ni1个元素。( 3)删除运算线性表得删除运算就是指将表中第 i ( i 得取值范围为 : 1 in)个元素从线性表中去掉,删除后使原表长为 n 得线性表:(a1, a2, 、 , ai-1, ai, ai+1, 、, an)成为表长为 n1 得线性表:(a1, a2, 、 , ai-1, ai+1, 、 , an)。顺序表上完成这一运算得步骤如下: 将ai+1an 顺序向上移动;(注意数据得移动方向:从前往后依次前移一个元素) 修改表长。int Delete_SqList (SqLi
14、st &L;int i) if (i L、length) return ERROR; / 删除位置不合法p = &(L、elemi-1); / p 为被删除元素得位置e = *p; / 被删除元素得值赋给 eq = L、elem+L、length-1; / 表尾元素得位置for (+p; p data=x;s-next=L; L=s;scanf (%d,&x);return L;尾插法在单链表得尾部插入结点建立单链表头插入建立单链表简单, 但读入得数据元素得顺序与生成得链表中元素得顺序就是相反得,若希望次序一致,则用尾插入得方法。因为每次就是将新结点插入到链表得尾部,所以需加入一个指针 r 用
15、来始终指向链表中得尾结点,以便能够将新结点插入到链表得尾部。初始状态, 头指针L=NULL, 尾指针 r=NULL; 按线性表中元素得顺序依次读入数据元素,不就是结束标志时,申请结点,将新结点插入到 r 所指结点得后面,然后 r 指向新结点(注意第一个结点有所不同)。LinkList CreateListR1 ( )LinkList L=NULL;LNode *s,*r=NULL;int x; /设数据元素得类型为intscanf(%d,&x);while (x!=flag) s=(LNode *)malloc(sizeof(LNode);s-data=x;if (L=NULL) L=s; /
16、第一个结点得处理else r-next=s; /其它结点得处理r=s; /r 指向新得尾结点scanf(%d,&x);if ( r!=NULL) r-next=NULL; /对于非空表,最后结点得指针域放空指针return L;在算法CreateListR1中,第一个结点得处理与其它结点就是不同得,原因就是第一个结点加入时链表为空,它没有直接前驱结点,它得地址就就是整个链表得指针,需要放在链表得头指针变量中;而其它结点有直接前驱结点,其地址放入直接前驱结点得指针域。 “第一个结点”得问题在很多操作中都会遇到,如在链表中插入结点时,将结点插在第一个位置与其它位置就是不同得,在链表中删除结点时,删
17、除第一个结点与其它结点得处理也就是不同得,等等。为了方便操作,有时在链表得头部加入一个“头结点”,头结点得类型与数据结点一致,标识链表得头指针变量L中存放该结点得地址,这样即使就是空表,头指针变量L也不为空了。头结点得加入使得“第一个结点”得问题不再存在,也使得“空表”与“非空表”得处理成为一致。头结点得加入完全就是为了运算得方便,它得数据域无定义,指针域中存放得就是第一个数据结点得地址,空表时为空。尾插法建立带头结点得单链表,将算法CreateListR1改写成算法CreateListR2形式。LinkList CreateListR2( )LinkList L=(LNode *)mallo
18、c(sizeof(LNode);L-next=NULL; /空表LNode *s,*r=L;int x; /设数据元素得类型为intscanf(%d,&x);while (x!=flag) s=(LNode *)malloc(sizeof(LNode);s-data=x;r-next=s;r=s; /r 指向新得尾结点scanf(%d,&x);r-next=NULL;return L;因此,头结点得加入会带来以下两个优点:第一个优点:由于开始结点得位置被存放在头结点得指针域中,所以在链表得第一个位置上得操作就与在表得其它位置上得操作一致,无需进行特殊处理;第二个优点:无论链表就是否为空,其头指
19、针就是指向头结点在得非空指针(空表中头结点得指针域为空),因此空表与非空表得处理也就统一了。在以后得算法中不加说明则认为单链表就是带头结点得。(2)查找操作按序号查找 Get_LinkList(L,i)从链表得第一个元素结点起,判断当前结点就是否就是第i个,若就是,则返回该结点得指针,否则继续后一个,表结束为止,没有第个结点时返回空。LNode * Get_LinkList(LinkList L, int i); LNode * p=L;int j=0;while (p-next !=NULL & jnext; j+;if (j=i) return p;else return NULL;(3)
20、插入运算后插结点:设p指向单链表中某结点, s指向待插入得值为x得新结点,将*s插入到*p得后面,插入示意图如图所示。操作如下:s-next=p-next;p-next=s;注意:两个指针得操作顺序不能交换。(4)删除运算删除结点设p指向单链表中某结点,删除*p。操作过程如图。要实现对结点*p得删除,首先要找到*p得前驱结点*q,然后完成指针得操作即可。操作如下:q=L;while (q-next!=p)q=q-next; /找*p得直接前驱q-next=p-next;free(p);因为找*p前驱得时间复杂度为O(n),所以该操作得时间复杂度为O(n)通过上面得基本操作我们得知:(1) 单链
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 考研 讲义
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【丰****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【丰****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。