数据结构和核心算法企业面试题(北大青鸟内部整理).pptVIP

数据结构和核心算法 目 录 顺序线性表 链表 树 图 排序 选择排序 插入排序 冒泡排序 算法的复杂度问题 经典算法 汉诺塔 二分有哪些信誉好的足球投注网站法 斐波那契数列 八皇后问题 1.交换两个整数不需要一个额外的空间用于保存.有两个数值变量分别为a与b　试写算法，实现a与b值的交换，在程序中只能出现a,b两个变量。 答案一： int a = 2, b = 3; Console.WriteLine(a + + b); a = a ^ b; b = a ^ b; a = a ^ b; Console.WriteLine(a + + b); Console.Read(); 代码参考“ConsoleApplication1” 答案二： int x = 3, y = 5; Console.WriteLine(x+ +y); x = x + y; y = x - y; x = x - y; Console.WriteLine(x + + y); x = x - y; y = y + x; x = y - x; Console.WriteLine(x + + y); x = y - x; y = y - x; x = x + y; Console.Read(); 数据结构的基本概念和术语 数据结构的基本概念和术语 数据结构的基本概念和术语 数据结构的基本概念和术语 数据结构的基本概念和术语 单链表 单链表定义： 　用一组地址任意的存储单元存放线性表中的数据元素。 以元素(数据元素的映象) + 指针(指示后继元素存储位置)= 结点(表示数据元素 或 数据元素的映象) 数据元素（data element）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 1、链接存储方法 　　链接方式存储的线性表简称为链表（Linked List）。 　　链表的具体存储表示为： 　　① 用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的） 　　② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)） 　　注意： 　　链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。 单链表类型描述： 　　typedef char DataType; //假设结点的数据域类型为字符 　　typedef struct node //结点类型定义 { 　　 DataType data; //结点的数据域 　 　 struct node *next;//结点的指针域 　　}ListNode; 　　typedef ListNode *LinkList; 　　ListNode *p; 　　LinkList head; 　　注意： 　　①LinkList和ListNode *是不同名字的同一个指针类型（命名的不同是为了概念上更明确） 　　②LinkList类型的指针变量head表示它是单链表的头指针 　　③ListNode *类型的指针变量p表示它是指向某一结点的指针 树，二叉树，森林 树 是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构，很象自然界中的树那样。 树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树形象表示。 树在计算机领域中也得到广泛应用，如在编译源程序如下时，可用树表示源源程序如下的语法结构。 又如在数据库系统中，树型结构也是信息的重要组织形式之一。 一切具有层次关系的问题都可用树来描述。 一、树的概述 　　树结构的特点是：它的每一个结点都可以有不止一个直接后继，除根结点外的所有结点都有且只有一个直接前趋。以下具体地给出树的定义及树的数据结构表示。 　　 （一）树的定义 　　树是由一个或多个结点组成的有限集合，其中： 　　⒈必有一个特定的称为根(ROOT)的结点； 　　⒉剩下的结