《数据结构》 (java版) 课件 6-0回顾

adatastructureDS=(D,R)D={a1,a2,...,an}R={<ai,aj>|ai,aj∈D}一组数据和数据之间的关系共同构成了一个数据结构线性表的数组实现云飞扬17181[0][1][2]浪淘沙18170万山红17165线性表的链式实现云飞扬17181

浪淘沙18170万山红17165ACGBDEFHJI12345678910

012345678910ABCEFDGHIJ完全二叉树的数组实现二叉树的链式实现AF∧∧E∧C∧D∧∧B∧rootABDCEF树的数组实现ABCDEFGpublic

classNode<T>{ Tdata;

intnext;}data-1000225parentABCDEFG0123456ABCDEFG树的链式实现a.结点同构b.结点异构树的链式实现节点有可变个引用：public

classNode<T>{ Tdata; T[]subTrees;

@SuppressWarnings("unchecked")

publicNode(int

count){//new的时候给定子树的个数

subTrees=(T[])newObject[count]; }}ABCDEFGBCEFGADrootABCDEFG树的链式实现ABCDEFGroot=0n=7data123firstchild456树的数组＋链式实现ABCDEFG0123456孩子链表：找孩子方便，如何找双亲？总结数组实现：随机存取、受限的关系、连续的空间(？)链式实现：顺序存取、任意的关系、零散的空间描述关系并没有修改数据，而是创建了Node，借助于Node表达数据之间的关系关系：线性、层次、multilinkedstructure(网状？)总结d4d1d5d3d2d4d1d5d3d2classmateclassmateclassmateroommateroommateroommateroommateclassmate总结public

classMultiLinkStructure<T>implementsIterable<T>{

privateMap<T,Node<T>>data2node=newHashMap<>();//数据绑定到了哪个node

private

static

classNode<T>{ Tdata; List<Node<T>>to;//与哪些其它的数据有联系 Node(Tnode){

data=node;

to=newLinkedList<>(); } }

public

voidadd(Tdata){ Node<T>n=data2node.get(data);

if(n!=null)

throw

newIllegalArgumentException();

n=newNode<>(data);

data2node.put(data,n); }总结

public

voidremove(Tdata){ Node<T>n1=data2node.get(data);

if(n1==null)

throw

newIllegalArgumentException();

data2node.remove(data);

for(Node<T>n2:data2node.values())

n2.to.remove(n1); }

public

voidaddRelation(Td1,Td2){ Node<T>n1=data2node.get(d1); Node<T>n2=data2node.get(d2);

if(n1==null||n2==null)

throw

newIllegalArgumentException();

n1.to.add(n2); }

public

voidremoveRelation(Td1,Td2){ Node<T>n1=data2node.get(d1); Node<T>n2=data2node.get(d2);

if(n1==null||n2==null)

throw

newIllegalArgumentException();

n1.to.remove(n2); }总结

publicList<T>dataSet(Td){ Node<T>n1=data2node.get(d);

if(n1==null)

throw

newIllegalArgumentException(); ArrayList<T>list=newArrayList<>(n1.to.size());

for(Node<T>n2:n1.to)

list.add(n2.data);

return

list; }

publicIterator<T>iterator(){

return

data2node.keySet().iterator(); }总结

public

static

voidmain(String[]args){ MultiLinkStructure<Character>structure=newMultiLinkStructure<>(); Characterd1=Character.valueOf('a'); Characterd2=Character.valueOf('b'); Characterd3=Character.valueOf('c'); Characterd4=Character.valueOf('d'); Characterd5=Character.valueOf('e');

structure.add(d1);

structure.add(d2);

structure.add(d3);

structure.add(d4);

structure.add(d5); System.out.print("data:");

for(Characterc:structure) System.out.print(c+""); System.out.println();

structure.addRelation(d1,d2);

structure.addRelation(d1,d3);

structure.addRelation(d1,d5);

structure.addRelation(d5,d1);

structure.addRelation(d5,d2);

structure.addRelation(d5,d3);

structure.addRelation(d5,d4); List<Character>list=structure.dataSet(d5);

for(int

i=0;i<list.size();i++) System.out.print(list.get(i)+""); System.out.println();

structure.remove(d1);

list=structure.dataSet(d5);

for(int

i=0;i<list.size();i++) System.out.print(list.get(i)+""); System.out.println(); }总结public

classMultiLinkLabledStructure<T,E>implementsIterable<T>{

privateMap<T,Node<T,E>>data2node=newHashMap<>();

private

static

classNode<T,E>{ Tdata; Map<Node<T,E>,E>map;//联系和标签 Node(Tnode){

data=node;

map=newHashMap<>(); } }

public

voidadd(Tdata){ Node<T,E>n=data2node.get(data);

if(n!=null)

throw

newIllegalArgumentException();

n=newNode<>(data);

data2node.put(data,n); }总结

public

voidremove(Tdata){ Node<T,E>n1=data2node.get(data);

if(n1==null)

throw

newIllegalArgumentException();

data2node.remove(data);

for(Node<T,E>n2:data2node.values())

n2.map.remove(n1); }

public

voidaddRelation(Td1,Td2,Er){ Node<T,E>n1=data2node.get(d1); Node<T,E>n2=data2node.get(d2);

if(n1==null||n2==null)

throw

newIllegalArgumentException();

n1.map.put(n2,r); }

public

voidremoveRelation(Td1,Td2){ Node<T,E>n1=data2node.get(d1); Node<T,E>n2=data2node.get(d2);

if(n1==null||n2==null)

throw

newIllegalArgumentException();

n1.map.remove(n2); }总结

publicList<T>dataSet(Td){ Node<T,E>n1=data2node.get(d);

if(n1==null)

throw

newIllegalArgumentException(); Set<Node<T,E>>set=n1.map.keySet(); ArrayList<T>list=newArrayList<>(set.size());

for(Node<T,E>n2:set)

list.add(n2.data);

return

list; }

publicCollection<E>labelCollection(Td){ Node<T,E>n=data2node.get(d);

return

n.map.values(); }

publicIterator<T>iterator(){

return

data2node.keySet().iterator(); }总结

public

static

voidmain(String[]args){ MultiLinkLabledStructure<Character,String>structure=newMultiLinkLabledStructure<>(); Characterd1=Character.valueOf('a'); Characterd2=Character.valueOf('b'); Characterd3=Character.valueOf('c'); Characterd4=Character.valueOf('d'); Characterd5=Character.valueOf('e');

structure.add(d1);

structure.add(d2);

structure.add(d3);

structure.add(d4);

structure.add(d5); System.out.print("data:");

for(Characterc:structure) System.out.print(c+""); System.out.println();

structure.addRelation(d1,d2,"classmate");

structure.addRelation(d1,d4,"classmate");

structure.addRelat