《數(shù)據(jù)結(jié)構(gòu)》 (java版) 課件 6-0回顧

adatastructureDS=(D,R)D={a1,a2,...,an}R={<ai,aj>|ai,aj∈D}一組數(shù)據(jù)和數(shù)據(jù)之間的關(guān)系共同構(gòu)成了一個(gè)數(shù)據(jù)結(jié)構(gòu)線(xiàn)性表的數(shù)組實(shí)現(xiàn)云飛揚(yáng)17181[0][1][2]浪淘沙18170萬(wàn)山紅17165線(xiàn)性表的鏈?zhǔn)綄?shí)現(xiàn)云飛揚(yáng)17181

浪淘沙18170萬(wàn)山紅17165ACGBDEFHJI12345678910

012345678910ABCEFDGHIJ完全二叉樹(shù)的數(shù)組實(shí)現(xiàn)二叉樹(shù)的鏈?zhǔn)綄?shí)現(xiàn)AF∧∧E∧C∧D∧∧B∧rootABDCEF樹(shù)的數(shù)組實(shí)現(xiàn)ABCDEFGpublic

classNode<T>{ Tdata;

intnext;}data-1000225parentABCDEFG0123456ABCDEFG樹(shù)的鏈?zhǔn)綄?shí)現(xiàn)a.結(jié)點(diǎn)同構(gòu)b.結(jié)點(diǎn)異構(gòu)樹(shù)的鏈?zhǔn)綄?shí)現(xiàn)節(jié)點(diǎn)有可變個(gè)引用：public

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

@SuppressWarnings("unchecked")

publicNode(int

count){//new的時(shí)候給定子樹(shù)的個(gè)數(shù)

subTrees=(T[])newObject[count]; }}ABCDEFGBCEFGADrootABCDEFG樹(shù)的鏈?zhǔn)綄?shí)現(xiàn)ABCDEFGroot=0n=7data123firstchild456樹(shù)的數(shù)組＋鏈?zhǔn)綄?shí)現(xiàn)ABCDEFG0123456孩子鏈表：找孩子方便，如何找雙親？總結(jié)數(shù)組實(shí)現(xiàn)：隨機(jī)存取、受限的關(guān)系、連續(xù)的空間(？)鏈?zhǔn)綄?shí)現(xiàn)：順序存取、任意的關(guān)系、零散的空間描述關(guān)系并沒(méi)有修改數(shù)據(jù)，而是創(chuàng)建了Node，借助于Node表達(dá)數(shù)據(jù)之間的關(guān)系關(guān)系：線(xiàn)性、層次、multilinkedstructure(網(wǎng)狀？)總結(jié)d4d1d5d3d2d4d1d5d3d2classmateclassmateclassmateroommateroommateroommateroommateclassmate總結(jié)public

classMultiLinkStructure<T>implementsIterable<T>{

privateMap<T,Node<T>>data2node=newHashMap<>();//數(shù)據(jù)綁定到了哪個(gè)node

private

static

classNode<T>{ Tdata; List<Node<T>>to;//與哪些其它的數(shù)據(jù)有聯(lián)系 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); }總結(jié)

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); }總結(jié)

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(); }總結(jié)

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(); }總結(jié)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;//聯(lián)系和標(biāo)簽 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); }總結(jié)

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); }總結(jié)

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(); }總結(jié)

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