数据结构躬行记1_顺序表&单链表&栈

顺序表

概念

顺序表是指用一组地址连续的存储单元依次存储各个元素，使得在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中的线性表。

代码实现

  1 public class SequentialList {
  2     private int length;
  3     private int[] List;
  4 
  5     //初始化顺序表
  6     public SequentialList(int max){
  7         this.List = new int[max];
  8         this.length = 0;
  9     }
 10     //清空数据表
 11     public void clearList(){
 12         this.length = 0;
 13     }
 14     //检测顺序表是否为空
 15     public boolean isEntry(){
 16         if(this.length == 0){
 17             return true;
 18         }
 19         else{
 20             return false;
 21         }
 22     }
 23     //返回顺序表的长度
 24     public int Listlength(){
 25         return this.length;
 26     }
 27     //返回顺序表中指定位置元素的值
 28     public int [] getElem(int site){
 29         int []result = new int [1];
 30         if(site<1||site>this.length){
 31             return null;
 32         }else{
 33             result[0] = this.List[site-1];
 34         }
 35         return result;
 36     }
 37     //返回顺序表中第一个与指定值相同的元素的位置
 38     public int locateElem(int value){
 39         for(int i=0;i<this.length;i++){
 40             if(this.List[i] == value){
 41                 return i+1;
 42             }
 43         }
 44         return 0;
 45     }
 46     //返回指定元素的直接前驱
 47     public int [] priorElem(int value){
 48         int []prior = new int[this.length];
 49         int ls = 0;
 50         for(int i=1;i<this.length;i++){
 51             if(this.List[i]==value){
 52                 prior[ls] = this.List[i-1];
 53                 ls++;
 54             }
 55         }
 56         if(ls!=0){
 57             return prior;
 58         }else{
 59             return null;
 60         }
 61     }
 62     //返回指定元素的直接后继
 63     public int[] nextElem(int value){
 64         int []next = new int[this.length];
 65         int ls = 0;
 66         for(int i=0; i<this.length-1;i++){  //不能是最后一个元素的后继，要考虑边缘情况
 67             if(this.List[i] == value){
 68                 next[ls]=this.List[i+1];
 69                 ls++;
 70             }
 71         }
 72         if(ls!=0){
 73             return next;
 74         }else{
 75             return null;
 76         }
 77     }
 78     //向指定位置插入元素
 79     public boolean listInsert(int site,int value){
 80         if(site<1||site>this.length+1){
 81             return false;
 82         }else if(this.length == this.List.length){
 83             return false;
 84         }
 85             for(int i=this.length;i>=site;i--){
 86                 this.List[i]=this.List[i-1];
 87             }
 88             this.List[site-1]=value;
 89             this.length++;
 90             return true;
 91     }
 92     //删除指定位置的元素
 93     public boolean listDelete(int site) {
 94         if(site<1||site>this.length){
 95             return false;
 96         }else if(site == this.length){
 97             this.length--;
 98             return true;
 99         }else {
100             for (int i = site - 1; i < this.length; i++) {
101                 this.List[i] = this.List[i + 1];
102             }
103             this.length--;
104             return true;
105         }
106     }
107     //遍历顺序表
108     public String traverseList(){
109         String s = "";
110         for(int i=0;i<this.length;i++){
111             s+=this.List[i]+"、";
112         }
113         if(s.length()==0){
114             return s;
115         }
116         return s.substring(0,s.length()-1);  //去掉字符串最后一个符号
117     }
118 
119     public static void main(String[] args) {
120         SequentialList list =new SequentialList(10);
121         for(int i=1;i<=6;i++){
122             list.listInsert(i,i*i);
123         }
124         list.listDelete(4);
125         System.out.println(list.traverseList());
126     }
127 }

单链表

概念

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点由元素和指针构成。在Java中，我们可以将单链表定义成一个类，单链表的基本操作即是类的方法，而结点就是一个个实例化的对象，每个对象中都有“元素值”和“下一结点地址”两个属性。在“下一结点地址”属性中存储的是下一个对象的引用，这样，一个个对象连在一起就成为了单链表

代码实现

  1 public class MyLinkedList {
  2     Node head = null; //头结点
  3     /**
  4      * 链表添加结点:
  5      * 找到链表的末尾结点，把新添加的数据作为末尾结点的后续结点
  6      * @param data
  7      */
  8     public void addNode(int data) {
  9         Node newnode = new Node(data);
 10         if(head == null){
 11             head = newnode;
 12             return;
 13         }
 14         Node tmp = head;
 15         while(tmp.next!=null){
 16             tmp = tmp.next;
 17         }
 18         tmp.next = newnode;
 19     }
 20     /**
 21      * 链表删除结点:
 22      * 把要删除结点的前结点指向要删除结点的后结点，即直接跳过待删除结点
 23      * @param index
 24      * @return
 25      */
 26     public boolean delete(int index){
 27         if(index<1||index>length()){
 28             return false;
 29         }
 30         if(index == 1){
 31             head = head.next;
 32             return true;
 33         }
 34         Node preNode = head;
 35         Node curNode = preNode.next;
 36         int i = 1;
 37         while(curNode !=null){
 38             if(i==index){
 39                 preNode.next = curNode.next;
 40                 return true;
 41             }
 42             preNode = preNode.next;
 43             curNode = curNode.next;
 44             i++;
 45         }
 46         return true;
 47     }
 48     public int length(){
 49         int length = 0;
 50         Node tmp = head;
 51         while (tmp.next!=null){
 52             length++;
 53             tmp = tmp.next;
 54         }
 55 
 56         return length+1;
 57     }
 58     /**
 59      * 链表结点排序,并返回排序后的头结点:  (升序)
 60      * 选择排序算法,即每次都选出未排序结点中最小的结点，与第一个未排序结点交换
 61      * @return
 62      */
 63     public Node Listsort(){
 64         Node curNode = head;
 65         while(curNode !=null){
 66             Node nextNode =curNode.next;
 67             while(nextNode !=null){
 68                 if(curNode.data>nextNode.data){
 69                     int tmp = curNode.data;
 70                     curNode.data = nextNode.data;
 71                     nextNode.data = tmp;
 72                 }
 73                 nextNode = nextNode.next;
 74             }
 75             curNode = curNode.next;
 76         }
 77         return head;
 78     }
 79     /**
 80      * 打印结点
 81      */
 82     public String printNode(){
 83         Node curNode = head;
 84         String s = "";
 85         while(curNode !=null){
 86             s += curNode.data+"、";
 87             curNode = curNode.next;
 88         }
 89         return s.substring(0,s.length()-1);
 90     }
 91     /**
 92      * 去掉重复元素:
 93      * 调用hashtable.containsKey()来判断重复结点
 94      */
 95     public void distinctLink(){
 96         Node curNode = head;
 97         Node pre = null;
 98         Hashtable<Integer,Integer> map = new Hashtable<>();
 99         while(curNode !=null){
100             if(map.containsKey(curNode.data)){
101                 pre.next = curNode.next;
102             }else{
103                 map.put(curNode.data,1);
104                 pre = curNode;
105             }
106             curNode = curNode.next;
107         }
108     }
109     /**
110      * 返回倒数第k个结点,
111      * 两个指针，第一个指针向前移动k-1次，之后两个指针共同前进，
112      * 当前面的指针到达末尾时，后面的指针所在的位置就是倒数第k个位置
113      * @param k
114      * @return
115      */
116     public Node findReverNode(int k){
117         if(k<1||k>length()){
118             return null;
119         }
120         Node curNode = head;
121         Node preNode = head;
122         for(int i=0; i<k-1;i++){
123             curNode = curNode.next;
124         }
125         while(curNode.next !=null){
126             curNode =curNode.next;
127             preNode = preNode.next;
128         }
129         return preNode;
130     }
131     /**
132      * 查找正数第k个元素
133      */
134     public Node findNode(int k){
135         if(k<1 || k>length()){//不合法的k
136             return null;
137         }
138         Node temp = head;
139         for(int i = 0; i<k-1; i++){
140             temp = temp.next;
141         }
142         return temp;
143     }
144     /**
145      * 在不知道头结点的情况下删除指定结点：
146      * 删除结点的重点在于找出其前结点，使其前结点的指针指向其后结点，即跳过待删除结点
147      * 1、如果待删除的结点是尾结点，由于单链表不知道其前结点，没有办法删除
148      * 2、如果删除的结点不是尾结点，则将其该结点的值与下一结点交换，然后该结点的指针指向下一结点的后续结点
149      */
150     public boolean deleteSpecialNode(Node n){
151         if(n.next == null){
152             return false;
153         }else{
154             //交换结点和其后续结点中的数据
155             int temp = n.data;
156             n.data = n.next.data;
157             n.next.data = temp;
158             //删除后续结点
159             n.next = n.next.next;
160             return true;
161         }
162     }
163     /**
164      * 反转链表，在反转指针钱一定要保存下个结点的指针
165      */
166     public void reserveLink(){
167         Node curNode = head;//头结点
168         Node preNode = null;//前一个结点
169         while(curNode != null){
170             Node nextNode = curNode.next;//保留下一个结点
171             curNode.next = preNode;//指针反转
172             preNode = curNode;//前结点后移
173             curNode = nextNode;//当前结点后移
174         }
175         head = preNode;
176     }
177 
178 }

栈

概念

栈是限定仅在表的一端进行插入或删除操作的线性表，对于栈来说，操作端称为栈顶，另一端则称为栈底，栈的修改是按照后进先出的原则进行的，因此又称为后进先出的线性表。顺序栈是指利用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。

代码实现

 1 public class MyStack {
 2     private int[] Stack;
 3     private int top = 0;
 4     public MyStack(int max){
 5         this.Stack = new int[max];
 6     }
 7     //清空顺序栈
 8     public void clearStack(){
 9         this.top = 0;
10     }
11     //检测栈顶指针是否指向栈底即可
12     public boolean stackEmpty() {
13         if(this.top == 0) {
14             return true;
15         }else {
16             return false;
17         }
18     }
19     //返回顺序栈中的元素个数
20     public int stackLength(){
21         return this.top;
22     }
23     //返回顺序栈的栈顶元素，不修改栈顶指针
24     public int[] getTop(){
25         if(this.top ==0){
26             return null;
27         }
28 
29         int []top = new int[1];
30         top[0] = this.Stack[this.top-1];
31         return top;
32     }
33     //向顺序栈顶中压入元素
34     public boolean Push(int m){
35         if(this.top ==this.Stack.length){
36             return false;
37         }
38         this.Stack[this.top] = m;
39         this.top++;
40         return true;
41     }
42     //从顺序栈顶中弹出元素
43     public int[] Pop(){
44         if(this.top ==0){
45             return null;
46         }
47         int []value = new int[1];
48         value[0] = this.Stack[this.top-1];
49         this.top--;
50         return value;
51     }
52     public String stackTraverse(){
53         if(this.top ==0)
54             return null;
55         String s = "";
56         for(int i=0;i<this.top;i++){
57             s+=this.Stack[i]+"、";
58         }
59         return s.substring(0,s.length()-1);
60     }
61 }