传智播客C和C++与数据结构基础讲义

轻松入门实战应用传智播客C++课程传智播客C和C++与数据结构基础讲义传智扫地僧1、数据结构概念1.1数据结构相关概念1.1.1疑惑1、我学完了C语言，可是现在感觉还是写不出代码。2、为什么会有各种各样的程序存在？3、程序的本质是什么？程序是为了具体问题而存在的程序需要围绕问题的解决进行设计同一个问题可以有多种解决方案如何追求程序的“性价比”？是否有可量化的方法判别程序的好坏？1.1.2数据结构起源计算机从解决数值计算问题到解决生活中的问题现实生活中的问题涉及不同个体间的复杂联系需要在计算机程序中描述生活中个体间的联系数据结构主要研究非数值计算程序问题中的操作对象以及它们之间的关系不是研究复杂的算法1.1.3数据结构中的基本概念数据–程序的操作对象，用于描述客观事物(inta,intb,)数据的特点：可以输入到计算机可以被计算机程序处理数据是一个抽象的概念，将其进行分类后得到程序设计语言中的类型。如：int，float，char等等数据元素：组成数据的基本单位数据项：一个数据元素由若干数据项组成数据对象–性质相同的数据元素的集合（比如：数组，链表）轻松入门实战应用传智播客C++课程//友情提示，来自结构体课堂代码//声明一个结构体类型struct_MyTeacher//一种数据类型{charname[32];chartile[32];intage;charaddr[128];};intmain21(){struct_MyTeachert1;//数据元素struct_MyTeachertArray[30];//数据对象memset(&t1,0,sizeof(t1));strcpy(t1.name,name);//数据项strcpy(t1.addr,addr);//数据项strcpy(t1.tile,addr);//数据项t1.age=1;}数据元素之间不是独立的，存在特定的关系，这些关系即结构数据结构指数据对象中数据元素之间的关系如：数组中各个元素之间存在固定的线性关系编写一个“好”的程序之前，必须分析待处理问题中各个对象的特性，以及对象之间的关系。基本概念总结：轻松入门实战应用传智播客C++课程1.1.4数据的逻辑结构指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。逻辑结构可细分为4类：轻松入门实战应用传智播客C++课程1.1.5数据的物理结构1.1.6数据的运算轻松入门实战应用传智播客C++课程1.2、算法1.2.1算法概念算法是特定问题求解步骤的描述在计算机中表现为指令的有限序列算法是独立存在的一种解决问题的方法和思想。对于算法而言，语言并不重要，重要的是思想。1.2.2算法和数据结构区别数据结构只是静态的描述了数据元素之间的关系高效的程序需要在数据结构的基础上设计和选择算法===程序=数据结构+算法总结：算法是为了解决实际问题而设计的数据结构是算法需要处理的问题载体数据结构与算法相辅相成1.2.3算法特性输入算法具有0个或多个输入输出算法至少有1个或多个输出有穷性算法在有限的步骤之后会自动结束而不会无限循环确定性算法中的每一步都有确定的含义，不会出现二义性可行性算法的每一步都是可行的1.2.4算法效率的度量1、事后统计法比较不同算法对同一组输入数据的运行处理时间轻松入门实战应用传智播客C++课程缺陷为了获得不同算法的运行时间必须编写相应程序运行时间严重依赖硬件以及运行时的环境因素算法的测试数据的选取相当困难事后统计法虽然直观，但是实施困难且缺陷多算法效率的度量事前分析估算依据统计的方法对算法效率进行估算影响算法效率的主要因素算法采用的策略和方法问题的输入规模编译器所产生的代码计算机执行速度//算法最终编译成具体的计算机指令//每一个指令，在具体的计算机上运行速度固定//通过具体的n的步骤，就可以推导出算法的复杂度longsum1(intn){longret=0;int*array=(int*)malloc(n*sizeof(int));inti=0;for(i=0;in;i++){array[i]=i+1;}for(i=0;in;i++){ret+=array[i];}free(array);returnret;}longsum2(intn){longret=0;inti=0;for(i=1;i=n;i++){轻松入门实战应用传智播客C++课程ret+=i;}returnret;}longsum3(intn){longret=0;if(n0){ret=(1+n)*n/2;}returnret;}intmain(){printf(%d\n,sum1(100));printf(%d\n,sum2(100));printf(%d\n,sum3(100));return0;}intfunc(inta[],intlen){inti=0;intj=0;ints=0;for(i=0;ilen;i++)n{for(j=0;jlen;j++)n{s+=i*j;//n*n}}returns;}//n*n轻松入门实战应用传智播客C++课程注意1：判断一个算法的效率时，往往只需要关注操作数量的最高次项，其它次要项和常数项可以忽略。注意2：在没有特殊说明时，我们所分析的算法的时间复杂度都是指最坏时间复杂度。2、大O表示法算法效率严重依赖于操作(Operation)数量在判断时首先关注操作数量的最高次项操作数量的估算可以作为时间复杂度的估算O(5)=O(1)O(2n+1)=O(2n)=O(n)O(n2+n+1)=O(n2)O(3n3+1)=O(3n3)=O(n3)常见时间复杂度关系轻松入门实战应用传智播客C++课程3、算法的空间复杂度算法的空间复杂度通过计算算法的存储空间实现S(n)=O(f(n))其中，n为问题规模，f(n))为在问题规模为n时所占用存储空间的函数大O表示法同样适用于算法的空间复杂度当算法执行时所需要的空间是常数时，空间复杂度为O(1)空间与时间的策略多数情况下，算法执行时所用的时间更令人关注如果有必要，可以通过增加空间复杂度来降低时间复杂度同理，也可以通过增加时间复杂度来降低空间复杂度练习1：分析sum1sum2sum3函数的空间复杂度O(4n+12)O(8)=O(1)O(4)=O(1)总结：实现算法时，需要分析具体问题，对执行时间和空间的要求。练习2：时间换空间/*问题：在一个由自然数1-1000中某些数字所组成的数组中，每个数字可能出现零次或者多次。设计一个算法，找出出现次数最多的数字。*/方法1：排序，然后找出出现次数最多的数字方法2：voidsearch(inta[],intlen){intsp[1000]={0};inti=0;intmax=0;for(i=0;ilen;i++){intindex=a[i]-1;sp[index]++;}for(i=0;i1000;i++){if(maxsp[i])轻松入门实战应用传智播客C++课程{max=sp[i];}}for(i=0;i1000;i++){if(max==sp[i]){printf(%d\n,i+1);}}}intmain(){intarray[]={1,1,3,4,5,6,6,6,2,3};search(array,sizeof(array)/sizeof(*array));return0;}把每个数字出现的次数的中间结果，缓存下来；在缓存的结果中求最大值。轻松入门实战应用传智播客C++课程2、线性表2.1线性表基本概念2.1.1线性表定义线性表(List)是零个或多个数据元素的集合线性表中的数据元素之间是有顺序的线性表中的数据元素个数是有限的线性表中的数据元素的类型必须相同2.1.2数学定义线性表是具有相同类型的n（≥0）个数据元素的有限序列（a1,a2,…,an）ai是表项，n是表长度。2.1.3性质a0为线性表的第一个元素，只有一个后继an为线性表的最后一个元素，只有一个前驱除a0和an外的其它元素ai，既有前驱，又有后继线性表能够逐项访问和顺序存取2.1.4练习下面的关系中可以用线性表描述的是A.班级中同学的友谊关系N:NB.公司中的上下级关系1:NC.冬天图书馆排队占座关系D.花名册上名字之间的关系1::1轻松入门实战应用传智播客C++课程2.2.5线性表的操作创建线性表销毁线性表清空线性表将元素插入线性表将元素从线性表中删除获取线性表中某个位置的元素获取线性表的长度线性表在程序中表现为一种特殊的数据类型线性表的操作在程序中的表现为一组函数C语言描述=====》线性表的设计与实现ADT抽象层《[数据结构(C语言版)].严蔚敏_吴伟民.扫描版.pdf》p44页人生财富库积累#ifndef_WBM_LIST_H_#define_WBM_LIST_H_typedefvoidList;typedefvoidListNode;//创建并且返回一个空的线性表List*List_Create();//销毁一个线性表listvoidList_Destroy(List*list);//将一个线性表list中的所有元素清空,线性表回到创建时的初始状态voidList_Clear(List*list);//返回一个线性表list中的所有元素个数intList_Length(List*list);//向一个线性表list的pos位置处插入新元素nodeintList_Insert(List*list,ListNode*node,intpos);//获取一个线性表list的pos位置处的元素ListNode*List_Get(List*list,intpos);//删除一个线性表list的pos位置处的元素返回值为被删除的元素，NULL表示删除失败ListNode*List_Delete(List*list,intpos);#endif轻松入门实战应用传智播客C++课程注意:intList_Insert(List*list,ListNode*node,intpos);(重点:分离思想)2.2线性表的顺序存储结构2.2.1基本概念2.2.2设计与实现插入元素算法判断线性表是否合法判断插入位置是否合法把最后一个元素到插入位置的元素后移一个位置将新元素插入线性表长度加1获取元素操作判断线性表是否合法判断位置是否合法直接通过数组下标的方式获取元素删除元素算法判断线性表是否合法判断删除位置是否合法将元素取出将删除位置后的元素分别向前移动一个位置线性表长度减1链表顺序存储插入算法和删除算法轻松入门实战应用传智播客C++课程2.2.3优点和缺点优点：无需为线性表中的逻辑关系增加额外的空间可以快速的获取表中合法位置的元素缺点：插入和删除操作需要移动大量元素当线性表长度变化较大时难以确定存储空间的容量2.3线性表的链式存储2.3.1基本概念链式存储定义为了表示每个数据元素与其直接后继元素之间的逻辑关系，每个元素除了存储本身的信息外，还需要存储指示其直接后继的信息。轻松入门实战应用传智播客C++课程表头结点链表中的第一个结点，包含指向第一个数据元素的指针以及链表自身的一些信息数据结点链表中代表数据元素的结点，包含指向下一个数据元素的指针和数据元素的信息尾结点链表中的最后一个数据结点，其下一元素指针为空，表示无后继。2.3.2链表技术领域推演轻松入门实战应用传智播客C++课程2.3.2设计与实现链表链式存储_api实现分析在C语言中可以用结构体来定义链表中的指针域链表中的表头结点也可以用结构体实现带头结点、位置从0的单链表返回链表中第3个位置处，元素的值LinkListNode*LinkList_Get(LinkList*list,intpos){inti=0;TLinkList*tList=(TLinkList*)list;LinkListNode*current=NULL;轻松入门实战应用传智播客C++课程LinkListNode*ret=NULL;if(list==NULL||pos0||pos=tList-