mutong在yj41上第21讲指针与链表

第4讲指针类型与链表学习的原因：构造合适的哈希函数，便于分类查找。

空间和时间都得到改进。搜索中应用（查找某个元素是否在某个集合中）存储数据的需要

树和图的链式存储结构：操作方便减少空间

需要多少，申请多少，没有冗余。最简单的例子Varp:^integer;Beginnew(p);p^:=123;writeln(p^);End.一、指针的定义

指针的定义：

1、type指针名字=^指向的基类型；如：typepoint=^integer;varp1,p2:point;2、直接定义指针变量：

varp1,p2:^integer;p1,p2是指向整型的指针指针名字可以是任意的标识符基类型可以是基本类型或自定义的类型。一般变量：静态变量

只要定义了，就分配占用固定的存储单元，直到程序结束。指针变量：动态变量存储的某个存储单元的地址如果是仅仅定义了指针变量，并没有开辟存储单元开辟一个动态的存储单元：调用标准过程：newVarp:^integer;//定义指向整型的指针Beginnew(p);//动态分配内存区域

p^:=123;//为p指向的区域赋值

writeln(p^);//输出p指向的区域内容End.//p^即相当于整型变量格式：new(指针变量)功能：开辟一个指针类型的存储单元，并把此存储单元的地址赋给指针变量。标准过程：new功能：释放空间的

如：dispose(p)

慎用！标准过程：dispose(指针变量）Nil符号：空地址指针变量除了指向内存地址外，还可以指向空地址，用nil表示。表示不指向任何一个地址。例：varp^:integer;

p:=nil;

往往初始化指针时用二、链表数组和链表是线形表的两种表现形式。

数组存取方便，但插入元素复杂度高。链表插入方便，但随机读取复杂度高。存储一批数：链表定义typePoint=^node;//指向结点的指针

node=record//结点类型

data:integer;//结点数据

next:point;//下一个指针

end;varhead,p,q:point;单链表：必须有一个头指针指向链表的第一个结点，然后依次可以访问后面的结点。操作：插入查找删除在链表前端插入元素新生成一个结点p；给p的数据域赋值；该结点next指向head指针；head指向该指针；pnew(p);P^.data:=x;P:=head;Head:=p;1、插入（前插,后插,中间插）例1建立一个由n个数组成的链表，每读入一个数后，将该数插入到链表的最前端。然后从头依次输出n个数。输入：512345输出：54321//按读入顺序倒序输出typepoint=^node;node=recorddata:integer;next:point;end;varhead:point;n,i,x:integer;beginhead:=nil;readln(n);fori:=1tondobeginread(x);

insert(x);end;

print;cedureinsert(x:integer);//前插xvarp:point;beginnew(p);p^.data:=x;p^.next:=head;head:=p;end;procedureprint;//从头依次输出结点的值

varp:point;beginp:=head;whilep<>nildobeginwrite(p^.data,'');p:=p^.next;end;end;在链表尾端插入元素（再设置一个尾指针tail）新生成一个结点p；给p的数据域赋值；尾tail的next指向p指针；tail指向p；new(p);P^.data:=x;tail^.next:=p;tail:=p;例2建立一个由n个数组成的链表，每读入一个数后，将该数插入到链表的最前端。然后从头依次输出n个数。输入：512345输出：12345//按读入顺序倒序输出为了插入方便，先单独建立第一个结点head:=nil;readln(n);

new(tail);read(x);tail^.data:=x;head:=tail;fori:=1ton-1dobeginread(x);insert(x);end;print;5nilheadtailprocedureinsert(x:integer);//表尾插入，表尾指针tailvarp:point;beginnew(p);p^.data:=x;//p^.next:=nil;tail^.next:=p;tail:=p;end;链表中间插入元素：设r是指向需插入的元素的指针，r应插入指针p与q之间，则插入过程为；

p^.next:=r;r^.next:=q;若果q=nil,就是在尾插入。

所以表后插入是中间插入的特例

操作一样2、链表中查找元素x用一个临时指针p遍历链表，每次与p^.data比较，如果相等，则查找成功，否则p:=p^.next，如果p为空，则查找失败。functionfind(x:integer):boolean;varp:point;;beginp:=head;while(p<>nil)and(p^.data<>x)dop:=p^.next;ifp=nilthenexit(false)elseexit(true);end;3、链表元素的删除设p指向需删除的元素，q是p的前一个元素，则删除过程为：

q^.next:=p^.next;(dispose(p);)proceduredel(x:integer);varp,q:point;beginifhead^.data=xthen//头元素

beginhead:=head^.next;exit;end;p:=head;while(p<>nil)and(p^.data<>x)dobeginq:=p;p:=p^.next;end;ifp=nilthenwriteln('nofound')elseq^.next:=p^.next;end;例3：p4.pas输入n及n个元素，建立一个链表。输出元素（顺序或逆序都可以）输入一x，如果在链中，就删除，不在输出“nofound”输出删除后的数据如：3123321231head:=nil;readln(n);fori:=1tondobeginread(x);

insert(x);end;print;readln(x);

del(x);print;1、用链表实现插入排序（从小到大）如：输入：531425输出：12345三、综合应用方法1：p31readln(n);new(head);read(x);head^.data:=x;//先建第一个结点

fori:=2tondobeginread(x);insert(x);end;print;procedureinsert(x:integer);varp,q,r:point;beginnew(r);r^.data:=x;ifx<head^.datathen//前插：最小

beginr^.next:=head;head:=r;exit;end;q:=head;while(q<>nil)and(x>q^.data)dobeginp:=q;q:=q^.next;end;p^.next:=r;r^.next:=q;end;方法2：p32附加一个无穷小的头结点，这样可以保证x一定是后插（相对于head而言）。

readln(n);new(head);head^.data:=-maxlongint;fori:=1tondobeginread(x);insert(x);end;print;procedureinsert(x:integer);//肯定不会插在最前面：尾插或中间插一样操作

varp,q,r:point;beginq:=head;while(q<>nil)and(x>q^.data)dobeginp:=q;q:=q^.next;end;new(r);r^.data:=x;p^.next:=r;r^.next:=q;end;2、输入n(<=10000)个正整数，按照他们对m的余数分类。然后按余数的大小从小大大输出n个数。重复的只输出一次（重复的数只保留一个即可）如：m=10；输入：61511152011输出：20111155constm=10;typepoint=^node;node=recorddata:integer;next:point;end;vara:array[0..m-1]ofpoint;n,i,x:integer;Main：fori:=0tom-1doa[i]:=nil;readln(n);fori:=1tondobeginread(x);ifnotfind(x)theninsert(x);end;print;functionfind(x:integer):boolean;varp:point;k:integer;begink:=xmodm;p:=a[k];while(p<>nil)and(p^.data<>x)dop:=p^.next;ifp=nilthenexit(false)elseexit(true);end;procedureinsert(x:integer);varp:point;k:integer;beginnew(p);p^.data:=x;k:=xmodm;p^.next:=a[k];a[k]:=p;end;procedureprint;varp:point;beginfori:=0tom-1doifa[i]<>nilthenbeginp:=a[i];whilep<>nildobeginwrite(p^.data,'');p:=p^.next;end;writeln;end;end;3：输入100000个1至1000000000之间的整数，然后输入m个需查找的数，输出是否存在。分析：定义一个0至99999之间数组，数组元素为链表，数组a[i]存储mod100000余数为i的所有的数。查找是只需遍历其中某一个链表。平均每个数组中有一个元素，时间复杂度为O(n)4、字符串转换（chuan22.pas）Maxn=1000000;point=^pnode;pnode=recordstr:string;next:point;end;hash:array[0..maxn-1]ofpoint;//如果在链中，返回true，如果不在，插入到链中。

functionfind(s:string):boolean;vark,i:longint;p:point;begink:=0;fori:=1tolength(s)dobegink:=k*131+ord(s[i]);k:=kmod1000000;end;p:=hash[k];while(p<>nil)and(p^.str<>s)dop:=p^.next;ifp<>nilthenexit(true);new(p);p^.str:=s;p^.next:=hash[k];hash[k]:=p;exit(false);end;5、方程的解数（noi2001）四、总结1、如果链表加一个头结点，不存要求的信息，真正的信息从第二个开始存，这样可以保证插入和删除都是在后面进行，可以统一处理，不要单独考虑删除头或在链头插入元素。缺点是多了一个结点。根据习惯选择合适的方法。2、可以用数组来模拟链表。目前有很多选手采取这样的方法。尤其在保存图时（稀疏图）如：输入n(<=10000)个正整数，按照他们对m的余数分类。然后按余数的大小从小大大输出n个数。重复的只输出一次（重复的数只保留一个即可）如：m=10；输入：7151115202125输出：202111125155下标1234567data151115202125next001203415111520212505162030405760708090Hash[i]topa[i]下标datanext15111520212500102030405060