数据结构笔记(c++版).docx

《数据结构笔记(c++版).docx》由会员分享，可在线阅读，更多相关《数据结构笔记(c++版).docx（92页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第一章概述1.1研究内容软件设计中常用的基本技术实用问题I数据结构组织数个模型I构造求解算吵I求解方法/ 程序设计A测试日数据结构核心课程之一1.2术语数据(data) 能够输入到计算机中并能被计算机处理的符号的集合。(广义) 1分解数据不素(data element) 构成数据的基本单位(具有完整的独立意义)。I描述在某些场合还被称为元素、记录、结点、顶点等。数据质(字段)元素的具体信息数据结构(data structure)构成数据元素之间的结构关系。线性结构J树形结构(树型结构)图结构(网状结构)I集合编号姓彳基本资奖金数据结构示例:(a)工资表示例序号学号姓名成绩备注(b)成绩表示例（

2、C）家族关系示例（d）群体间关系示例（连线表示相互认识关系）逻辑结构I线性、树形（树型）、图（网状）、集合存储结构|数据结构在内存中的实现形式同样的逻辑结构w同样的存储结构 运算（判断存储结构的好坏）有关数据结构几个方面的联系图抽象 数据 类型 （ADT）逻辑结构运算定义算法性能存储结构运算实现（算法）算法分析1.3算法及其描述算法特定问题的求解方法指令的有限序列满足：（1）输入0n个（2）输出1n个 与输入有特定联系（3）确定性（无二义性）相同的输入只能有相同的输出（4）有限性执g次数有限（5）可行性算强可用计算机在有限时间内实现算法描述语言易懂，灵活自然语言Y不准确准确，严格计算机语言-死

3、板伪语言（类语言）：类pascal、类C、类C+算法举例：1.求最大公因子（辗转相除法）2 .韩信点兵问题3 .幻方问题（纵横图）1.4算法分析算法的衡量指标：在正确性的前提下(1)时间性能运行算法的时间开销(2)空间性能运行算法的辅助空间规模(3)其它性能一一如可读性/可移植性时间性能(时间复杂度)：以算法运.而并钏来度量改q与具体机器相关以算法中E句的执行次数来衡量简化I计算麻烦以算法中也句的执行次数的回典来替代数量级：如果变量n的函数f(n)和g(n)满足：lira f(n)/g(n)=常数k(k# 8,0),则称f(n)和g(n) 是同一数量级的，并用f(n)=O(g(n)的形式来表示

4、。0(1 )og,n)O(n)O(nbg,n)O(n2)O(n)k O(2n) O(n!)O(nAn)难以实现例子：求解以下程序段的时间复杂度：for (i=l;i=n;i+)共：3n+2次数量级为：lim f(n)/g(n)= lim (3n+2)/n = 3,则时间复杂度为为O (n) 练习：(l)fbr(i=l;in;i+)fbr(j=l；j=i；j+) x+;O(n2)(2)i=l；while (i data;return success;error code stack:push(const elementtype x )an Aerror code stack:pop()if (

5、empty() return underflow;u = top;top-next=u-next; delete u;count ;return success;)error code stack:-stack() while ( !empty() pop();存储结构 front4.2链队列分析一：只设置头指针front时，若要做入队操作，即在链表尾插入，则操作步骤为： node * R;R = front;while( R - next != NULL) R = R - next; 需要做整个链表的遍历，效率低s = new node;s - data = x;R - next = s;R

6、 = s;R - next = NULL;因此，引入尾指针rear,使入队操作方便封装类：class queue public:qucue();queue。；Bool empty()const;Bool full()const;error codc get_front(elmcnttype &x)const;error code append(const elementtype x);error codc serve();private:int count;node * front, * rear;/设置尾指针rear是保证链队列尾部插入的方便定义其它成员 分析二：做入队操作时，第一个结点入队

7、操作为:frontrears = new node;s - data = x;rear = Gont = s;s - next = NULL;其他结点的入队操作为:s = new node;s - data = x;s - next = NULL;结果：两种情况入队操作不一致解决：引入“头结点”（附加结点），以保证操作的一致性带头结点的链队列存储结构为:frontI a/ -HU-T aarearfront口运算实现：queue: :queue()front = new node;rear = front;front - next = NULL;count = 0;Bool stack:emp

8、ty() return count = 0; 等价于：return front = rear;等价于：return front - next = NULL;Bool stack:full() return FALSE;本函数无实际意义error code queue:get_front(elementtype &x)constif ( empty() return underflow;x = front - next - data;return success;error code queue:appcnd(const elementtype x ) s = new node;s - data

9、 = x;s- next = NULL;rear - next = s;“qr = c* front . return success;error code queue:serve()delete u;count ;if (fk)nt next = NULL) rear = fh)nt;return success;error code queue:queue。 while (!empty() serve();|delete froni 释放头结点第五章线性表5.1 线性表的定义和运算定义：线性表L是由n个元素a” a2,，a”组成的有限 序列。记作L= (a, a2, , an)其中n=0为

10、表长；n=0时为L空表，记作L=()特性：A、只有一个第一个元素和一个最后一个元素；B、除第一个元素外其他元素有且仅有一个直接前趋(前驱)；C、除最后一个元素外其他元素有且仅有一个直接后继元素省的含义：同一表中，元素类型相同。在不同的场合有不同的含义例：字母表(A, B, C, D,，Z)；数字表(0, 1, 2, 3, 4,，9)；每月天数(31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31)CH伪语言描述心算；封装类，class list public:(1)初始化list();(2)求长度int length()const;(3)按序号取元素er

11、ror code get_element(const int i, elementtype &x)const;(4)按值查找元素int locate(const elementtype x)const;插入error code insert(const int i, const elementtype x);删除error codc delcte_element(const int i);定义其它成员)；5.2 顺序表存储结构：:list封装类：class listpublic:list。；int length()const;error code get_element(const int i

12、, elementtype &x)const;int locate(const elementtype x)const;error codc insert(const int i, const elementtype x);error code delete_element(const int i);private:elementtype datamaxlen;int count;定义其它成员运算实现：list:list() count = 0; int list:length() return count; error codc list:get_element(const int i, e

13、lementtype &x)constif (i count) return range error;x = datai - 1;return success;int list:locate(const elmenttypc x)constfor (i = 0; i length(); i -H-)if ( datai = x ) return (i + 1 );return 0;aia2a3a.an012 i-1n-1maxlen-1error code list:insert(const int i, const elementtype x)if ( count = maxlen )ret

14、urn overflow;if(i length() + 1 )return arrange error;fbr( j = count; j = i; j -)dataj = dataj - 1 ;大量移动元素dataj - 1 = x;条件：顺序表不满；序号正确，在中 操作：药a”后移填入xCount -H-return success;error code list:delete_element(const int i)if (length() = 0 ) return underflow;if (i length() return arrange error;for (j = i + l

15、;j data = x;s next = p next;| p - next = s;链表头位置插入时，s = new node;s - data = x;s next = p;p = s;|head = p;结论：在链表头插入时与其它两种情况操作不致解决：引入“头结点”(附加结点)，以保证操作的一致性 带头结点的单链表存储结构head a/ . . -| an| Aclass listpublic:Hst();int length()const;error codc get_element(const int i, elementtypc &x)const;|node locate(cons

16、t elmenttype x)const;error codc insert(const int i, const elmenttype x);error code delete_element(const int i);private:int count;node * head;定义其它成员运算实现：list:list()head = new node;head - next = NULL;count = 0;int list:length()constp = head - next;n = 0;while ( p != NULL)n -H-；p = p - next;return n;若定

17、义count成员，则直接返回count值即可error code list:get_element(const int i, element &x)constp = head - next; j= 1;while (j !=i&p!=NULL)p = p - next; j -H-;if ( p = NULL) return arrange error;x = p - data;return success;(考虑画流程图)node * list:locate(const elementtype x)constp = head - next;while ( p != NULL)if ( p -

18、 data = x ) return p;else p = p - next;return NULL;error code list:insert(const int i; const elementtype x)p = head; j = 0;while (j!=i-l&p!= NULL) p = p - next; j -H-;if(i count + 1 ) Z/if(p = NULL) return arrange error;s = new node;s - data = x;s - next = p - next;p - next = s;count -H-；return succ

19、ess;error code list:dclete_elcment(const int i)p = head; j = 0;while (j!=i-l &p!= NULL)p = p-next;j+;)if(i count)/if( p = NULL)return arrange error;u = p - next;p - next = u - next;delete u;count -;return success;cm xs = new node; s - data = x;s - next = head -next;head - next =s ;构造链表基本方法：从键盘输入数据，每

20、读入一个元素，产生结点装入, 插入链表中，重复上述操作讨论：产生结点：s = new node; s-data = x;插入链表：插入位置如何确定，有表头表尾两个位置可选头插法尾插法重复上述操作：何时结束封装的链表类中增加两个成员函数：class listpublic:void create 1(); 头插法void create2(); 尾插法；头插法运算实现：void list:createl()cin x;while ( x !=结束符) count -H-;s = new node;s - data = x;s - next = head - next;head - next = s;

21、cin x;)尾插法运算实现：void list:create2()cin x;rear = head;while ( x !=结束符) count -H-;s = new node;s - data = x;rear - next = s;Arear = s;rear - next = NULL; cin x;*)练习：A、B链表之间复制void copy(Iist A, list &B)B = new node;B - next = NULL;PA = A - next;PB = B;while ( PA !=NULL)s = new node;s - data = PA - data;P

22、B - next = s;PB = s;PB - next = NULL;PA = PA - next;)练习：A表分成奇、偶两个子表A、B (A表做删除，B表做插入) 递增有序链表集合求交并差子集，考虑时空复杂度5.4 其它结构形式的链表（1）单循环链表（优点：可在表中反复搜索）head初始化操作为：head = new node;head - next = |head|;求长度：p = head - next; n = 0;while （ p != head |） p = p - next; n + ;应用：m人开m把锁问题（每人一把钥匙，要求所有锁都能开）约瑟夫环问题（利用循环队列，不带

23、头结点的循环链表都可）实现部分语句为：u = A- next;A - next = B - next - next;delete B - next;B - next = u;A = B;（3）双链表（优点：求前驱后继都方便）带头结点或者不带头结点typedef elementtype data;prior | data | nextdunode * prior, * next;dunode;head初始化head = new node;head - prior = head - next = head;求长度查找类似插入时：s - prior = p - prior;s - next = p;

24、p - prior = s; s - prior - next = s;删除时：p - prior - next = p - next; p - next - prior = p - prior;delete p;应用：判断双循环链表是否时称双循环链表倒置（动指针、动结点值） 小结：线性表逻辑上相邻的元素顺序表物理上也相邻插入、删除需移动元素链表 物理上不一定相邻插入、删除不需移动元素5.5 串定义：串是由n个字符为曲,a”组成的有限序列。（n=0）元素是字符的线性表记作S= 御瓯其中n为串长度。n=0时为空串。注意：空串和空格串的区别。空串没有元素。空格串元素是空格符。子串串S中若干个连续的

25、字符组成的序列。运算：基本运算：赋值（=）：将一个串值S1传送给一个串名S。（如：S=S1）求长度length（S）：返回串S的长度值。连接运算（如S1+S2）：将如和S2连接成一个新串。求子串（substr （S,iJ）：返回串S从第i个元素开始的j个元素所组成的子串。串比较：（strcmp（Sl,S2）比较两个串的大小。对齐按ASCII码进行比较。结果为-1 0 1常用运算：可由基本运算实现插入（insert （S,i,Sl）：将子串S1插入到串S的从第i个字符开始的位置上。删除(deletestr (S,i,len)：删除串S中从第i个字符开始的len个字符。替换(replace(S,i

26、,len,Sl)s用字串S1替换串S中从第i个字符开始的len个字符。定位(index (S,S1) 模式匹配 例：S= aa,a2,-,anw.在S的第i个位置插入SI运算为insert(S,i,Sl),为常用运算可操作为:substr(l,i-l,Xl)substr(i, length() - (i - 1), X2)S = X1 +S1+X2为基本运算两者可互换存储结构顺序串紧凑格式： 优点：节省空间；缺点：运算不方便。非紧凑格式：优点：运算方便；缺点：浪费空间。等于1：S - ai a2 a3 a4 a5 a6 a7 比.SnA第六章递归(Recursive)递归是一种程序的形式，在函

27、数体内调用自身更是一种程序设计(算法设计)的技术例 n 0=靠1+ fn.2n -1 储n -2 章2例1 当n=0时n!=,n(n-l)! 当 n0 时例 int fact (int n) if ( n = 0 ) return 1;else return n * fact( n - 1 );)void print( link L)if(L!= NULL)cout L - data;print( L - next);6.1 递归的定义定义：在函数体中引用自身，则称之为递归函数。直接递归间接递归一般形式：void Pname（参数表）if（条件）递归出口简单操作；else 简单操作；Pname

28、 （实参表）；简单操作；Pname （实参表）；简单操作;可能有多次的调用6.2 递归的内部实现原理1 . 一般函数的内部实现A：A：al;call B;a2;call B;a3;call B;a4;(1)从程序的执行过程来讨论在执行调用时，计算机内部至少执行如下操作：(a)保存返回地址，即将返回地址入栈。(b)为被调子程序准备数据：计算实在参数的值，并赋给对应的形参。(c)转入子程序执行。在执行返回操作时，计算机内部至少执行如下操作：(a)从栈顶取出返回地址，并出栈。(b)按返回地址返回。(2)关于局部变量的实现的讨论在执行调用时，内部操作如下：(a)返回地址入栈，同时在栈顶为被调过程的局部变量和形参开辟存储空间。(b)为被调子程序准备数据：计算实在参数的值，并赋给对应的形参(在栈顶)。(c)转入子程序执行。在执行返回操作时，计算机内部至少执