数据结构分类
1、线形结构：
- 都是非空集
- 有且仅有一个开始节点和结束节点
- 最多只有一个直接前趋结点和直接后继结点
- 线性表、栈、队列和串都是
2、非线性结构：
- 一个结点可以有多个前趋结点和后继结点
- 数组、广义表、树结构和图结构都是
存储方式
- 顺序存储：
- 在一块连续的存储区域一个接一个存放数据。逻辑上相连的结点放在物理位置相邻的单元里。
- 链接存储：
- 不要求逻辑相连的点物理位置也相连
- 附加字段表示下一个结点位置
- 索引存储方式：
- 稠密索引：一个结点在索引表只有一个索引
- 稀疏索引：一组结点只有一个索引
- 散列存储：
- 根据结点关键字直接计算结点的存储地址
常用结构
顺序表
线性表
定义：n(n>=0)个数据元素a1,a2,a3…an组成有限序列（可重复）
特点：每个元素类型长度一样，插入和删除任何一个，在这个元素之后的元素下标都要改变
实例：
data.java:
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33package Sequencelist; public class data { String key; String name; int age; public String getKey() { return key; } public void setKey(String key) { this.key = key; } public String getName() { return name; } public void setName(String name) { this.name = name; } public int getAge() { return age; } public void setAge(int age) { this.age = age; } @Override public String toString() { return "data [key=" + key + ", name=" + name + ", age=" + age + "]"; } }
SLType.java:
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87package Sequencelist; public class SLType { static final int MAXLEN = 10; public data[] ListData = new data[MAXLEN + 1];//保存顺序表各个结点的数组 int ListLen;//顺序表已有结点长度 public void SLInit(SLType sl) { sl.ListLen = 0;//初始化顺序表 } public int SLLength(SLType sl) { return sl.ListLen; } public int SLInsert(SLType sl, int n, data d) { int i; if (sl.ListLen > MAXLEN) { System.out.println("sequence is full"); return 0; } if (n < 1 || n > sl.ListLen + 1) { System.out.println("Wrong number"); return 0;//插入的序号不对 } for (i = sl.ListLen; i >= n; i--) { sl.ListData[i + 1] = sl.ListData[i]; } sl.ListData[n] = d;//插入结点 sl.ListLen++; return 1; } public int SLALL(SLType sl) { int i; for (i = 1; i <= sl.ListLen; i++) { System.out.printf("data"+"["+i+"]"+":(%s,%d,%s)n", sl.ListData[i].key, sl.ListData[i].age, sl.ListData[i].name); } return 0; } public int SLadd(SLType sl,data d) { if(sl.ListLen>=MAXLEN) { System.out.println("sequence is full"); return 0; } sl.ListData[++sl.ListLen]=d; return 1; } public int SLdelete(SLType sl,int n) { int i; if(n<1||n>sl.ListLen) { System.out.println("wrong number"); return 0; } for(i=n;i<sl.ListLen;i++) { sl.ListData[i]=sl.ListData[i+1];//直接覆盖 } sl.ListLen--; return 1; } // 按照序号查找结点 public data slfindbynum(SLType sl,int n) { if(n<1||n>sl.ListLen) { System.out.println("wrong number"); return null; } return sl.ListData[n]; } // 按照关键字 public int slfindbycont(SLType sl,String key) { int i; for(i=1;i<=sl.ListLen;i++) { if(sl.ListData[i].key.compareTo(key)==0) { return i; } } return 0; } }
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68package Test; import Sequencelist.SLType; import Sequencelist.data; import java.util.Scanner; @SuppressWarnings("ALL") public class SLtest { public static void main(String[] args) { // TODO Auto-generated method stub int d,i,n=1; data pda; SLType sl=new SLType(); String key; System.out.println("Here is sequence list's operation demo:"); sl.SLInit(sl); System.out.println("Initialization completed!"); Scanner in=new Scanner(System.in); do { System.out.println("input the point's(key name age):"); data da=new data(); da.setKey(in.next()); da.setName(in.next()); da.setAge(in.nextInt()); if(da.getAge()!=0) { if(sl.SLadd(sl,da)==0) { break; } } else { break; } }while(true); System.out.println(" All the sequence list's point:"); sl.SLALL(sl); System.out.print("which point do you want to take?input it's serial number:-->"); i=in.nextInt(); pda=sl.slfindbynum(sl, i); if(pda!=null) { System.out.printf("the %d point is:(%d,%s,%s)",i,pda.getAge(),pda.getName(),pda.getKey()); } System.out.printf("seach by key:"); key=in.next(); i=sl.slfindbycont(sl, key); pda=sl.slfindbynum(sl, i); if(pda!=null) { System.out.printf("the %d point is:(%d,%s,%s)",i,pda.getAge(),pda.getName(),pda.getKey()); } /* * d=sl.SLLength(sl); System.out.println(d); */ } }
链表
定义：结点之间不一定连续，每个结点包括引用和数据域
特点：数据域–结点实际数据；地址部分–下一个结点的地址；有头结点head指向第一个结点，最后一个结点的地址部分为null;
复制代码
1
2
3
4
5
6
7
8
9package Linklist; public class data2 { public String key; public String name; public int age; }
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110package Linklist; public class CLType { public data2 nodeData=new data2(); public CLType nextNode; public CLType CLAddEnd(CLType head,data2 nodeData){ CLType node,htemp; if((node=new CLType())==null){ System.out.println("申请内存失败！"); return null; } else { node.nodeData=nodeData;//数据域 node.nextNode=null;//表尾 if(head==null){ head=node; return head; } htemp=head; while (htemp.nextNode!=null){//查找链尾 htemp=htemp.nextNode;//htemp在不停移动 } htemp.nextNode=node;//尾部插入结点 return head; } } public CLType CLAddFirst(CLType head,data2 nodeData) { CLType node; if ((node = new CLType()) == null) { System.out.println("申请内存失败！"); return null; } else { node.nodeData = nodeData; node.nextNode = head;//指向头引用指向的结点，代替之前第一个结点 head = node;//头引用指向插入的新结点 return head; } } public CLType CLFindNode(CLType head,String key){ CLType htemp; htemp=head; while (htemp!=null){ if(htemp.nodeData.key.compareTo(key)==0){ return htemp; } htemp=htemp.nextNode; } return null; } public CLType CLInsertNode(CLType head,String findkey,data2 nodeData){ CLType node,nodetemp; if ((node = new CLType()) == null) { System.out.println("申请内存失败！"); return null; } node.nodeData=nodeData; nodetemp=CLFindNode(head,findkey);//得到要插入点位置 if (nodetemp!=null){ node.nextNode=nodetemp.nextNode;//新插入点指向目标点的下一结点 nodetemp.nextNode=node;//目标位置点指向插入点 } else { System.out.println("未找到正确位置！"); } return head; } public int CLDeleteNode(CLType head,String key){ CLType node,htemp; htemp=head; node=head; while (htemp!=null) { if (htemp.nodeData.key.compareTo(key) == 0) { node.nextNode = htemp.nextNode;//找到要删除的结点，使前一结点指向当前结点的下一结点，node代表前一个 return 1; } else { node = htemp;//node代表前一个结点 htemp = htemp.nextNode; } } return 0; } public int CLlength(CLType head){ CLType htemp; int len=0; htemp=head; while (htemp!=null){ len++; htemp=htemp.nextNode; } return len; } public void CLALLNode(CLType head){ CLType htemp; data2 nodeData; htemp=head; System.out.printf("当前链表共有%d个结点,链表数据如下：n",CLlength(head)); while (htemp!=null){ nodeData=htemp.nodeData; System.out.printf("结点(%s,%s,%d)",nodeData.key,nodeData.name,nodeData.age); htemp=htemp.nextNode; } } }
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58package Test; import Linklist.CLType; import Linklist.data2; import java.util.Scanner; public class LinkTest { public static void main(String[] args) { CLType node,head=null; CLType cl=new CLType(); String key,findkey; Scanner in=new Scanner(System.in); System.out.println("输入数据，格式为：key name age"); do{ data2 nodeData=new data2(); nodeData.key=in.next(); if (nodeData.key.equals("0")){ break; } else { nodeData.name=in.next(); nodeData.age=in.nextInt(); head=cl.CLAddEnd(head,nodeData); } }while (true); cl.CLALLNode(head); System.out.println("插入结点，请在下一行输入插入位置关键字:"); findkey=in.next(); System.out.println("输入结点的数据（key name age）"); data2 nodeData=new data2(); nodeData.key=in.next(); nodeData.name=in.next(); nodeData.age=in.nextInt(); head=cl.CLInsertNode(head,findkey,nodeData); System.out.println("删除结点，输入要删除的关键字"); key=in.next(); cl.CLDeleteNode(head,key); cl.CLALLNode(head); System.out.println("链表中查找，输入关键字"); key=in.next(); node=cl.CLFindNode(head,key); if (node!=null){ nodeData=node.nodeData; System.out.printf("关键字%s对应结点(%s,%s,%d)n",key,nodeData.key,nodeData.name,nodeData.age); } else { System.out.println("链表没有相关关键字"); } } }
栈
顺序栈：
定义：用一组地址连续的内存单元存储数据，即定义一个数组，序号0元素就是栈底，top变量保存栈顶
特点：先进后出，只在栈顶端操作
入栈：先修改栈顶引用，让其上移一个位置，再保存数据到指定位置
出栈：同样先移动再保存
复制代码
1
2
3
4
5
6
7
8package Stack.Stacklist; public class data3 { public String name; public int age; }
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58package Stack.Stacklist; public class StackType { static final int MAXLEN=50; data3[] data=new data3[MAXLEN+1];//结点 int top;//栈顶 public StackType STInit(){ StackType p; if ((p=new StackType())!=null){ p.top=0; return p; } return null; } public boolean STIsEmpty(StackType s){ boolean t; t=(s.top==0); return t; } public boolean STIsFull(StackType s){ boolean t; t=(s.top==MAXLEN); return t; } public void STCleat(StackType s){ s.top=0; } public void STFree(StackType s){ if(s!=null){ s=null; } } public int Push(StackType s,data3 data3){ if(s.top+1>MAXLEN){ System.out.println("栈满溢出"); return 0; } s.data[++s.top]=data3;//先移动再赋值 return 1; } public data3 Pop(StackType s){ if(s.top==0){ System.out.println("栈空"); System.exit(0); } return (s.data[s.top--]); } public data3 ReadST(StackType s){ if(s.top==0){ System.out.println("空栈"); System.exit(0); } return (s.data[s.top]); } }
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43package Test; import Stack.Stacklist.StackType; import Stack.Stacklist.data3; import java.util.Scanner; public class StacklistTest { public static void main(String[] args) { StackType st=new StackType(); data3 data3=new data3(); StackType sta=st.STInit(); Scanner sc=new Scanner(System.in); System.out.println("入栈"); System.out.println("输入(格式如此)-->: name age"); do { data3 data31=new data3(); data31.name=sc.next(); if(data31.name.equals("0")){ break;//输入0退出 } else{ data31.age=sc.nextInt(); st.Push(sta,data31); } }while (true); String temp="1"; System.out.println("出栈，输入任意非0键继续："); temp=sc.next(); while (!temp.equals("0")){ data3=st.Pop(sta); System.out.printf("出栈数据-->(%s,%d)",data3.name,data3.age); temp=sc.next(); } System.out.println("演示结束"); st.STFree(st); } }
最后
以上就是鳗鱼八宝粥最近收集整理的关于java常用数据结构以及我整理的一些实例的全部内容，更多相关java常用数据结构以及我整理内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复