��ݽṹ

Article View: cn.bbs.comp.lang.java

Article #20074

Back to cn.bbs.comp.lang.java Previous Next

#20074

From: Ψ��Ϸ��
Date: Thu, 25 Dec 2003 18:57

82 lines
7529 bytes

���λ�ã������� -- ��ݽṹ���㷨 -- ��ν��ݽṹ
��ν��ݽṹ
���ߣ�starfish starfish@vip.sina.com
 ��ݽṹ�������������ѧ�뼼�������Ϲ㷺��ʹ�õ������������ӳһ����ݵ�
�ڲ����ɣ���һ���������Щ�ɷ���ݹ��ɣ���ʲô��ʽ���ɣ���ʲô�ṹ����ݽṹ
���߼��ϵ���ݽṹ�������ϵ���ݽṹ֮�֡��߼��ϵ���ݽṹ��ӳ�ɷ����֮���
�߼���ϵ���������ϵ���ݽṹ��ӳ�ɷ�����ڼ�����ڲ��Ĵ洢���š���ݽṹ����
�ݴ��ڵ���ʽ��
��ݽṹ����Ϣ��һ����֯��ʽ����Ŀ����Ϊ������㷨��Ч�ʣ���ͨ����һ���㷨��
�������Ӧ��ͨ�������㷨���Ͽ��Զ���ݽṹ�е���ݽ���ĳ�ֲ�����
��ݽṹ��Ҫ�о�ʲô��
��ݽṹ��Ϊһ��ѧ����Ҫ�о���ݵĸ����߼��ṹ�ʹ洢�ṹ���Լ�����ݵĸ��ֲ�
������ˣ���Ҫ�������������ݣ���ݵ��߼��ṹ����ݵ�����洢�ṹ������ݵ�
���������㷨����ͨ�����㷨�����ȡ������ݵ��߼��ṹ���㷨��ʵ��ȡ������ݵ�
����洢�ṹ��
ʲô����ݽṹ��ʲô���߼��ṹ������ṹ��
�����ָ�����޵ķ�ţ����磬"0"��"1"���������Լ��Ľṹ������������Ӧ�����壩
��ɵ�Ԫ�صļ��ϡ��ṹ��Ԫ��֮��Ĺ�ϵ�ļ��ϡ�ͨ����˵��һ����ݽṹDS ���Ա�
ʾΪһ����Ԫ�飺
DS=(D,S), //i.e., data-structure=(data-part,logic-structure-part)
����D�����Ԫ�صļ��ϣ������ǡ���㡱�����ܻ����С�����������򡱣���S
�Ƕ�����D��������ϣ��ϵĹ�ϵ�ļ��ϣ�S = { R | R : D��D��...}����֮ΪԪ�ص�
�߼��ṹ��
�߼��ṹ�����ֻ����ͣ����Ͻṹ�����Խṹ����״�ṹ������ṹ����������
�õ����ָ�Ч��ݽṹ������Ч���㷨��������������ݽṹ�����ʵ�֡���������
�ṹ�ģ�ȫ���ϵ������(ƫ����ι�ϵ)��ͼ���ֲ�����(weak/local orders)���Ƿ�
���Խṹ��
��ݽṹ������ṹ��ָ�߼��ṹ�Ĵ洢����(image)����ݽṹ DS ������ṹ P ��
Ӧ�ڴ� DS �����Ԫ�ص��洢��M��ά�����߼��ṹS����һ��ӳ�䣺
P:(D,S) --> M
�洢��ģ�ͣ�һ���洢�� M ��һϵ�й̶���С�Ĵ洢��Ԫ��ÿ����Ԫ U ��һ��Ψһ��
��ַ A(U)���õ�ַ������ر��롣ÿ����Ԫ U ��һ��Ψһ�ĺ�̵�Ԫ U'=succ(U)��
P �����ֻ�ӳ��ģ�ͣ�˳��sequential�������ӣ�linked��������indexed����ɢ
�У�hashing��ӳ�䡣
��ˣ��������ٿ��Եõ�4��4�ֿ��ܵ�������ݽṹ��
sequential (sets)
linked lists
indexed trees
hash graphs
�����������еĿ�����϶����?
��ݽṹDS�ϵĲ��������еĶ�����DS�ϵĲ����ڸı����Ԫ�أ��ڵ㣩��ڵ����ʱ
���뱣��DS���߼�������ṹ��
DS�ϵĻ�������κ������DS�ĸ߼���������������Щ�������ʵ�֡���ý�DS��
������л��������һ�����塪����֮Ϊģ�顣���ǿ��Խ�һ������ģ�����Ϊ���
���ͣ�����DS�Ĵ洢�ṹ����ʾΪ˽�г�Ա�����������ʾΪ��������������֮ΪAD
T����ΪADT����ջ�Ͷ��ж���һ������ı?����ӵ�б�Ĳ������Ӽ���
����DATs�ĸ߼��������Ա����Ϊ������װ�ģ��㷨�����û������DS���д��?
�õĺͻ���DS�����һ��DS����ͨ��ĳ�֡����Թ��򡱱�ת��Ϊ���Ե�DS���������Ա�
���������Ϊ�õ�DS���õ�DSͨ����Ӧ�ںõģ���Ч�ģ��㷨�������ɼ����ļ�����
�������ģ���Ϊ���������ֻ�ܴ�ȡ�߼�������ڴ浥Ԫ��������û�����Ի��Ľ�
���߼����ǲ��ɼ���ġ������һ��ͼ���в�����Ҫ����ͼ�����н�㣬����밴��ĳ
��˳�������η������нڵ㣨Ҫ�γ�һ��ƫ�򣩣�����ͨ��ĳ�ַ�ʽ��ͼ���еķ�����
�ṹת��Ϊ���Խṹ���ܶ�ͼ���в�����
���Ǻõ�DS�������зǳ��򵥶��Ч�����Ի�������˿�����������Ƴ����ǳ���
Ч���㷨������ʵ�ֺ�ʹ�ö��ܼ򵥣������Խ����������ĸ������⣬�������ʵ��
���������Ҫ�������õ�һ����ݽṹ�����Ľṹ�������еݹ�����ʡ���ÿһ��Ҷ��
����Ա�һ�����������֮��Ȼ��ʵ���ϣ�ÿһ�ֵݹ�Ľṹ�����Ա�ת��Ϊ����
�ȼ��ڣ����νṹ��
���õ���ݽṹ
���Խṹ
  ���Ա�
     ˳���
     ����
  ջ
  ����
  ��ϣ��
ͼ�ṹ
 ��
  ������
  B ��
  ��չ��
  ��
�ύʱ�䣺2003-04-14
������Դ��http://algorithm.126.com/
�Ķ�����1904



--

��[1;5;34m��[0m��[1;5;31m��[0m
[m[1;32m�� ��Դ:�����Ļ����� bbs.cqupt.edu.cn��[FROM: dangdang][m

Technical Details

Message-ID: <4A0Y5E$A0G@bbs.cqupt.edu.cn>

Path:

arc1-ca.pugleaf.net!archiver1.google.com!news2.google.com!news.maxwell.syr.edu!newshub.sdsu.edu!elnk-nf2-pas!newsfeed.earthlink.net!sjc70.webusenet.com!news.webusenet.com!maily.cic.tsinghua.edu.cn!news.uestc.edu.cn!CQUPT

Show Full Headers

Complete Article Headers

X-Google-Language: Chinese,GB
X-Google-Thread: f6cb0,b96757e6944c6436,start
X-Google-Attributes: gidf6cb0,public
X-Google-ArrivalTime: 2003-12-24 18:57:29 PST
Path: arc1-ca.pugleaf.net!archiver1.google.com!news2.google.com!news.maxwell.syr.edu!newshub.sdsu.edu!elnk-nf2-pas!newsfeed.earthlink.net!sjc70.webusenet.com!news.webusenet.com!maily.cic.tsinghua.edu.cn!news.uestc.edu.cn!CQUPT
From: zhaov.bbs@bbs.cqupt.edu.cn (Ψ��Ϸ��������)
Newsgroups: cn.bbs.comp.lang.java
Subject: ��ݽṹ
Date: 25 Dec 2003 18:57:07 GMT
Organization: ���Ļ�����
Message-ID: <4A0Y5E$A0G@bbs.cqupt.edu.cn>
X-Filename: Java/M.1072378622.A
Lines: 82