《NOIP基础数据结构》由会员分享，可在线阅读，更多相关《NOIP基础数据结构（68页珍藏版）》请在金锄头文库上搜索。
1、NOIP基础数据结构纲要,佛山石门中学 江涛,Pascal和C+双语对照,目录,记录、指针、链表,图,二叉树与树,3,数组、栈、队列,1,2,4,目录,数组的特性,数组、栈、队列,数组(array)的元素(element)或项(item) 的类型是相同的 数组的大小是固定的、静态的、连续的 数组对某元素的地址可O(1)时间计算 数组对某元素的存取是O(1)时间 数组的插入、删除操作是O(n)时间,数组,Pascal语言var tab:array-1010 of integer ; 变量名 下标范围 类型二维tt:array19,19 of char;,C+语言int tab 21; 类型 变量
2、名 数组大小二维 char tt99;,数组、栈、队列,数组定义举例,栈的特性,数组、栈、队列,信息学中的栈一般就是用数组实现 栈(stack)是后进先出(last-in-first-out,LIFO)或先进后出(FILO)的 栈有两个基本操作压入(push),弹出(pop) 操作都为O(1)时间 栈有一个计数器counter或栈顶指针,栈,栈的实现样例Pascal代码,数组、栈、队列,const maxn = 1000; var stack:array1maxn of integer;counter:integer;Procedure push(x:integer); begin /入栈in
3、c(counter); stackcounter :=x; end; function pop():integer; begin /出栈pop:=stackcounter; dec(counter); end;,栈的实现样例C+代码,数组、栈、队列,const int maxn=1000; int stackmaxn, counter=0;void push(int x) /入栈 stack+counter=x; int pop() /出栈 return stackcounter-; ,队列的特性,数组、栈、队列,信息学中的队列一般也用数组实现 队列(queue)是先进先出(first-in-
4、first-out,FIFO)或后进后出(LILO)的 队列有两个基本操作入队(push),出队(pop)操作都为O(1)时间 队列有队头front和队尾back两个指针，一般也有个计数器counter,队列,const maxn = 1000; var queue:array1maxn of integer;front,back,counter:integer; procedure push(x:integer); begininc(counter); inc(back); queueback :=x; end; function pop():integer; beginpop:=queue
5、front; inc(front); dec(counter); end;,队列的实现样例Pascal代码,数组、栈、队列,const int maxn=1000; int queuemaxn,counter=0,front=0,back= -1 ;void push(int x)queue+back=x;+counter; int pop()-counter;return queuefront+; ,队列的实现样例C+代码,数组、栈、队列,由于front和back一直向后移动， 有可能counter不大，但back却超过maxn， 而引起数组越界。,数组实现的可能缺点,数组、栈、队列,fro
6、nt,back,在保证countermaxn then front:=1;同样的，back:=back+1; 后加上if backmaxn then back:=1;,队列的”循环数组”方案,数组、栈、队列,练习,数组、栈、队列,1、判断字符串()()是否括号匹配。 2、有n(n1000000)个数排成一行，找出一段长度为L(1L=n)的连续一段，其中的最大值a与最小值b之差(a-b)是最大(小）的。求这个最大值。 3、SPFA算法。,记录的特性,记录、指针、链表,记录(record),C+中为结构(struct),它的各项可以是不同的类型 记录把各个项组成一“整体”，很多情况下也称为节点(n
7、ode),记录,Pascal语言type Tperson =recordname :string;age :integer;weight :real; end;,C+语言struct Tperson string name ;int age float weight ; ;,记录、指针、链表,记录定义举例,Pascal语言 varg:array1100 of Tperson; Beging1.name:=LiHong;g1.age :=16;g1.weight :=50.2;writeln(g1.name); End.,C+语言 Tperson g100; int main() g0.name
8、 =“LiHong”;g0.age =16;g0.weight=50.2;coutg0.nameendl; ,记录、指针、链表,记录的项访问举例,Pascal语言 g:array1100 of Tperson;t: Tperson; Begint:=g1;t.name:=LiHong;t.age :=16;t.weight :=50.2;writeln(g1.name); End.,C+语言 Tperson g100; int main() Tperson ,记录、指针、链表,记录数组的项访问另类法举例,指针的特性,记录、指针、链表,指针(point),其本质是内存的“地址”，指针变量所保存的
9、就是一个32位地址(对32位操作系统而言) 指针变量要“指向有意义的地址”，指向错误的地址很容易引起程序崩溃。通常是指向一个其它变量的地址或用new命令来申请一块“有意义的地址”。内存大小以机器的可用内存为上限,指针,Pascal语言 Varp1,p2: integer; /定义beginp2:=nil; /空指针new(p1); /申请空间Xp1:=32; /附值到空间X中p2:=p1; /p2也指向空间Xwriteln(p2);/打印出32 End.,C+语言 int *p1, *p2; int main() p2=NULL;p1= new(int);*p1=32;p2=p1;cout*p
10、2v=x; /必须先申请一个新节点t-next=front-next; / 插入到“头哨兵”后面front-next=t; ,链表的实现样例C+代码1,记录、指针、链表,/遍历链表的常用方法,int main() front=new Tnode; /申请一个哨兵，它下一个才是链表front-next=NULL; /初始化链表为空cinn;for (int i=0; ix; insert(x); /下面是遍历链表的常用方法for(t=front-next; t!=NULL; t=t-next) coutv ; return 0; end.,链表的实现样例C+代码2,记录、指针、链表,链表的“数组实现”法背景,因为有些语言(如fortran)不提供指针类型，人们使用数组和数组下标来模拟实现指针功能。 虽然在应用程序中这种方法有缺陷，但在信息学竞赛中，却是完全可行的，甚至速度更快。很多选手偏爱数组法，所以在此介绍。,“数组表示“,记录、指针、链表,链表的“数组实现”法要点,记录、指针、链表,1、先开一个足够大的数组，即先静态产生 足够的节点。 2、取一个节点即为取一个数组元素。 3、“指针”的“地址”现在是数组的下标，即数组的第几个元素。 4、“指针”为数组下标值，一般为整数型。,
