天津住房和城乡建设部网站,做图片祝福的网站,网站建设都需要哪些工具或软件,网页界面设计使用的单位主要是一、数组线性表#xff08;ADT#xff09; 线性表#xff1a;又称动态数组#xff0c;核心是动态数组#xff0c;可以自行扩容#xff0c;支持增删改查四种功能 java中有ArrayList也可以自行扩容#xff0c;二者功能较为相似#xff0c;且ArrayList也支持转换为数组。 …一、数组线性表ADT 线性表又称动态数组核心是动态数组可以自行扩容支持增删改查四种功能 java中有ArrayList也可以自行扩容二者功能较为相似且ArrayList也支持转换为数组。 ArrayListString listnew ArrayList();
int sizelist.size();
//转换为String类型数组
String[] array (String[])list.toArray(new String[size]);
//转换为int类型数组
int[] arr list.stream().mapToInt(k - k).toArray(); 1.定义成员变量泛型
private E[] array;//定义一个泛型数组
private int size;//数组内元素的实际数量
public MyArray(int capacity)
{this.array(E[]) new Object[capacity];this.size0;//size代表数组里实际有效的数据数量
}
2. 添加元素 添加指定的元素线性表有可能元素已满需要扩容 扩容后或未扩容再添加元素并将元素数量1 public void add(E element)
{//数组按照顺序添加元素//如果实际元素数量已达到数组长度判断为线性表已满//线性表已满则扩容if(sizearray.length)resize();array[size]element;size;
}
3. 插入元素 输入指定元素和要插入的位置下标 需要进行两个判断 1.需要判断插入的位置是否合法别超出线性表已有的范围 2.如果线性表现在已满就扩容 判断过后实现插入for循环解决给指定位置赋值为输入元素即可 别忘了最后增加元素数量 public void insert(E element,int index) throws IndexOutOfBoundsException {//插入元素必须按照顺序插入并且插入次数达到数组长度时才能扩容if(index0 || indexsize)//判断数组是否越界{throw new IndexOutOfBoundsException(超出数组范围);}if(sizearray.length)//如果实际元素达到数组容量上限{//数组扩容resize();}//实现数组插入for (int i size-1; i index; i--) {array[i1]array[i];}array[index]element;//插入元素size;}
4. 删除元素 输入要删除元素的位置下标 需要判断该位置是否超出线性表范围 判断不超出后执行删除一个for循环解决 记得让元素数量-1 public void delete(int index) throws IndexOutOfBoundsException
{//删除指定位置的数组元素if(index0||indexsize){throw new IndexOutOfBoundsException(数组越界删除失败);}for(int iindex;isize-1;i){array[i]array[i1];}size--;}
5. 线性表扩容 扩容 新建一个数组数组范围为原数组的两倍 然后把旧数组复制到新数组里 把新数组命名为旧数组的名字这样就可以继续使用旧数组的名字 而原旧数组已经被抛弃。 public void resize()
{//数组扩容E[] newArray(E[]) new Object[array.length*2];//把旧数组的内容复制到新的数组中System.arraycopy(array,0,newArray,0,array.length);this.arraynewArray;
}
6.输出
public void Print()
{for (int i 0; i size; i) {System.out.print(array[i] );}
}
7.主函数试验
public static void main(String[] args) {MyArray anew MyArray(4);for(int i0;i5;i)a.add(i);//0 1 2 3 4a.insert(9,2);//0 1 9 2 3 4a.delete(4);//0 1 9 2 4a.Print();}
8.完整代码
public class MyArrayE {private E[] array;//定义一个泛型数组private int size;//数组内元素的实际数量public MyArray(int capacity){this.array(E[]) new Object[capacity];this.size0;//size代表数组里实际有效的数据数量}public void add(E element){//数组按照顺序添加元素if(sizearray.length)resize();array[size]element;size;}//数组插入元素public void insert(E element,int index) throws IndexOutOfBoundsException {//插入元素必须按照顺序插入并且插入次数达到数组长度时才能扩容if(index0 || indexsize)//判断数组是否越界{throw new IndexOutOfBoundsException(超出数组范围);}if(sizearray.length)//如果实际元素达到数组容量上限{//数组扩容resize();}//实现数组插入for (int i size-1; i index; i--) {array[i1]array[i];}array[index]element;//插入元素size;}public void delete(int index) throws IndexOutOfBoundsException {//删除指定位置的数组元素if(index0||indexsize){throw new IndexOutOfBoundsException(数组越界删除失败);}for(int iindex;isize-1;i){array[i]array[i1];}size--;}public void resize(){//数组扩容E[] newArray(E[]) new Object[array.length*2];//把旧数组的内容复制到新的数组中System.arraycopy(array,0,newArray,0,array.length);this.arraynewArray;}public void Print(){for (int i 0; i size; i) {System.out.print(array[i] );}}public static void main(String[] args) {MyArray anew MyArray(4);for(int i0;i5;i)a.add(i);a.insert(9,2);a.delete(4);a.Print();}
} 二、链表 java自带的List列表结构void add(E element)在列表末尾添加元素E get(int index)获取指定索引位置的元素E set(int index,E element)替换指定索引位置的元素E remove(int index)移除指定索引位置的元素int size()返回表的大小我们用自定义类重新实现List的单链表版本 包括增删改查功能 优点 线性表逻辑上相邻物理上也相邻可随机存取任意元素。 缺点 线性表插入、删除操作需要移动大量元素 存储空间是预分配的不灵活空间浪费表的存储空间难扩充 1.定义成员变量 java里面没有像C语言的结构体但java有内部类 新建一个内部类Node表示链表内的单个节点内部类中包括 1.元素 2.指向下一节点的指针 3.构造函数给元素赋值 构造好节点类再新建头结点和尾结点指针并新建size表示链表的有效长度 private static class NodeE{//定义一个结点内部类E data;Node next;//指向下一结点的指针Node(E data){this.datadata;}}private Node head;//头结点private Node last;//尾结点private int size;//链表实际长度
2. 查找节点 输入想要查找的节点下标返回该下标位置的节点 新建一个指针从头结点遍历到下标位置返回指针指到下标位置的节点 public Node get(int index)throws Exception{//获取指定下标位置的结点if(index0 || indexsize)throw new IndexOutOfBoundsException(超出范围);Node temphead;for (int i 0; i index; i) {temptemp.next;//指针后移}return temp;}
3. 插入节点 输入要插入的节点元素值和要插入的位置下标 新建一个结点存储该结点元素值 先将要插入的节点指针指向插入位置的下一节点 然后再让插入位置的前一节点指向新结点 获取前一节点可使用第二步定义的“查找节点”方法输入位置-1下标 插入头结点、尾结点、中间某一节点的三种情况不同 public void insert(E data,int index)throws Exception{if(index0 || indexsize)throw new IndexOutOfBoundsException(超出链表表长);Node insertNodenew Node(data);//定义待插入结点if(size0){//空链表headinsertNode;lastinsertNode;}else if(index0){//插入到头结点前面insertNode.nexthead;//把原头结点放在待插入元素的下一个位置上headinsertNode;//把待插入元素放置在头结点上}else if(indexsize){//插入到尾结点后面last.nextinsertNode;//先把待插入结点放在尾结点的下一个位置lastinsertNode;//再把待插入节点设置为尾结点也就是指针后移了一位}else{//插入中间位置Node prevNodeget(index-1);//设置插入位置的前结点insertNode.nextprevNode.next;//先让待插入结点指向插入位置结点prevNode.nextinsertNode;//再让前结点指向待插入结点}size;}
4. 删除节点 输入要删除节点的下标 如果为空表删不了 新建一个节点指针指向将要被删除的节点垃圾桶 要删除谁就把谁的值赋给垃圾桶指针然后再让前一结点指向后一结点 删除头结点、尾结点、中间某一节点情况不同 public void delete(int index)throws Exception{if(index0 || indexsize){throw new IndexOutOfBoundsException(删除失败超出有效链表长度);}if(size0){//空链表System.out.println(链表中无有效结点删除失败);}Node removeNodenew Node(null);if(index0){//删除head结点removeNodehead;//把旧的头结点设置为已删除结点headhead.next;//把头结点的下一个结点设置为新的头结点}else if(indexsize-1){//删除尾结点removeNodelast;//把旧的尾结点设置为已删除Node prevNodeget(size-2);//获取前结点prevNode.nextnull;//让前结点指向空lastprevNode;//设置前结点为新的尾结点}else{//删除中间节点Node prevNodeget(index-1);//获取前结点Node nextNodeprevNode.next.next;//获取删除节点的下一节点removeNode prevNode.next;prevNode.nextnextNode;//让前结点指向后节点}size--;}
5. 输出节点 public void output(){Node temphead;//设置一个结点指针指向头结点for (int i 0; i size; i) {//遍历链表System.out.print(temp.data );temptemp.next;}} 6.主函数检验 public static void main(String[] args) throws Exception{MyListInteger LinkListnew MyList();LinkList.insert(3,0);//3LinkList.insert(8,1);//3-8LinkList.insert(3,2);//3-8-3LinkList.insert(8,3);//3-8-3-8LinkList.insert(9,1);//3-9-8-3-8LinkList.delete(0);//9-8-3-8LinkList.output();}
7.完整代码
/*
* java自带的List列表结构
* void add(E element)在列表末尾添加元素
* E get(int index)获取指定索引位置的元素
* E set(int index,E element)替换指定索引位置的元素
* E remove(int index)移除指定索引位置的元素
* int size()返回表的大小*//*数据结构就是用自定义类实现List结构增删改查*/
public class MyListE
{private static class NodeE{//定义一个结点内部类E data;Node next;//指向下一结点的指针Node(E data){this.datadata;}}private Node head;//头结点private Node last;//尾结点private int size;//链表实际长度//查找节点public Node get(int index)throws Exception{//获取指定下标位置的结点if(index0 || indexsize)throw new IndexOutOfBoundsException(超出范围);Node temphead;for (int i 0; i index; i) {temptemp.next;//指针后移}return temp;}//链表插入元素public void insert(E data,int index)throws Exception{if(index0 || indexsize)throw new IndexOutOfBoundsException(超出链表表长);Node insertNodenew Node(data);//定义待插入结点if(size0){//空链表headinsertNode;lastinsertNode;}else if(index0){//头插insertNode.nexthead;//把原头结点放在待插入元素的下一个位置上headinsertNode;//把待插入元素放置在头结点上}else if(indexsize){//尾差last.nextinsertNode;//先把待插入结点放在尾结点的下一个位置lastinsertNode;//再把待插入节点设置为尾结点也就是指针后移了一位}else{//插入中间位置Node prevNodeget(index-1);//设置插入位置的前结点insertNode.nextprevNode.next;//先让待插入结点指向插入位置结点prevNode.nextinsertNode;//再让前结点指向待插入结点}size;}//链表删除元素public void delete(int index)throws Exception{if(index0 || indexsize){throw new IndexOutOfBoundsException(删除失败超出有效链表长度);}if(size0){//空链表System.out.println(链表中无有效结点删除失败);}Node removeNodenew Node(null);if(index0){//删除head结点removeNodehead;//把旧的头结点设置为已删除结点headhead.next;//把头结点的下一个结点设置为新的头结点}else if(indexsize-1){//删除尾结点removeNodelast;//把旧的尾结点设置为已删除Node prevNodeget(size-2);//获取前结点prevNode.nextnull;//让前结点指向空lastprevNode;//设置前结点为新的尾结点}else{//删除中间节点Node prevNodeget(index-1);//获取前结点Node nextNodeprevNode.next.next;//获取删除节点的下一节点removeNode prevNode.next;prevNode.nextnextNode;//让前结点指向后节点}size--;}//输出链表public void output(){Node temphead;//设置一个结点指针指向头结点for (int i 0; i size; i) {//遍历链表System.out.print(temp.data );temptemp.next;}}public static void main(String[] args) throws Exception {MyListInteger LinkListnew MyList();LinkList.insert(3,0);LinkList.insert(8,1);LinkList.insert(3,2);LinkList.insert(8,3);LinkList.insert(9,1);LinkList.delete(0);LinkList.output();}
}三、栈 Java自带栈
StackE stacknew Stack();
boolean stack.empty() 测试此堆栈是否为空
E stack.pop() 出栈
E stack.push(E item) 入栈
E stack.peek() 获取栈顶元素
int stack.search(Object o) 返回对象在堆栈里的位置下标 栈是后进先出的经典例子如弹夹压弹羽毛球筒等 后面会附有实际运用的题目 栈的应用场景 栈的输出顺序和输入顺序相反所以栈通常用于对“历史”的回溯也就是逆流而上追溯“历史” 例如实现递归的逻辑就可以用栈来代替因为栈可以回溯方法的调用链。 栈还有一个著名的应用场景是面包屑导航使用户在浏览页面时可以轻松地回 溯到上一级或更上一级页面。 1. 定义成员变量 栈由数组来实现栈内实际元素的数量用size来记录 private E[] arr;//将元素存到数组中private int size;//栈的实际长度元素数量public MyStack(){//调用无参构造方法 默认最大容量12this(12);}public MyStack(int MaxSize) {this.arr(E[])new Object[MaxSize];} 2.判断栈是否为空 public boolean isEmpty(){//判断是否为空栈return this.size0;}
3. 入栈 元素自栈顶入栈栈顶为数组[size] 判断栈是否已满已满就扩容 把元素加入到栈顶记得有效长度1 public E push(E value){//入栈if(this.size arr.length){//栈满扩容E[] copyArr(E[])new Object[arr.length*2];arrcopyArr;}this.arr[size]value;this.size;return value;}
4.获取栈顶元素 判断栈空 把栈顶元素返回 public E get(){//获取栈顶元素if(isEmpty()){System.out.println(栈为空);return null;}return arr[size-1];} 5.出栈 判断栈空 先把栈顶元素存起来然后清除栈顶元素 再把栈的有效长度-1 public E pop(){//出栈if(isEmpty()){//栈空抛出异常throw new RuntimeException(栈中无元素);}E toparr[size-1];//size始终比栈顶元素的下标多1arr[size]null;size--;return top;}
6. 返回栈的长度 public int getSize() {//返回数组大小return this.size;}
7. 打印栈 由于栈是只能通过一次出栈一个栈顶元素来遍历 而遍历结束栈也就空了 因此要新建一个栈把原栈输出的栈顶元素都存起来 等原栈遍历结束为空栈后再把新建栈内存的元素再依次遍历入栈到原栈里 这样就保证了打印结束后原栈内元素不变 public void print(){MyStackE stacknew MyStack();//新建栈while(!isEmpty())//遍历到栈空也可以改成输入要遍历的元素数量{E elemthis.pop();//存储栈顶元素并出栈//栈顶元素为null说明是数组冗余的部分非有效元素if(elemnull){continue;}stack.push(elem);//把原栈栈顶元素入栈到新建栈System.out.print(elem );}System.out.println();while(!stack.isEmpty()){//把新建栈的栈顶依次赋值给原栈E elemstack.pop();this.push(elem);}} 8.主函数检验 public static void main(String[] args) {MyStackInteger stacknew MyStack();for (int i 0; i 11; i) {stack.push(i);//入栈}stack.print();//10 9 8 7 6 5 4 3 2 1 0stack.pop();//10System.out.println(stack.get());//9System.out.println(stack.getSize());//10}
9.完整代码
/*
* Java自带栈
* StackE stacknew Stack();
* boolean stack.empty() 测试此堆栈是否为空
* E stack.pop() 出栈
* E stack.push(E item)入栈
* E stack.peek() 获取栈顶元素
* int stack.search(Object o)返回对象在堆栈里的位置下标*//*
* java数据结构就是要实现java自带的堆栈的方法
* 了解堆栈实现的原理*/public class MyStackE {private E[] arr;//将元素存到数组中private int size;//栈的实际长度元素数量public MyStack(){//调用无参构造方法 默认最大容量12this(12);}public MyStack(int MaxSize) {this.arr(E[])new Object[MaxSize];}public boolean isEmpty(){//判断是否为空栈return this.size0;}public E get(){//获取栈顶元素if(isEmpty()){System.out.println(栈为空);return null;}return arr[size-1];}public E push(E value){//入栈if(this.size arr.length){//栈满扩容E[] copyArr(E[])new Object[arr.length*2];arrcopyArr;}this.arr[size]value;this.size;//栈的实际长度始终比栈顶元素的下标多1return value;}public E pop(){//出栈if(isEmpty()){//栈空抛出异常throw new RuntimeException(栈中无元素);}E toparr[size-1];arr[size]null;size--;return top;}public int getSize() {//返回数组大小return this.size;}public void print(){MyStackE stacknew MyStack();while(!isEmpty()){E elemthis.pop();if(elemnull){continue;}stack.push(elem);System.out.print(elem );}System.out.println();while(!stack.isEmpty()){E elemstack.pop();this.push(elem);}}public static void main(String[] args) {MyStackInteger stacknew MyStack();for (int i 0; i 11; i) {stack.push(i);//入栈}stack.print();//10 9 8 7 6 5 4 3 2 1 0stack.pop();//10System.out.println(stack.get());//9System.out.println(stack.getSize());//10}
}四、队列 JAVA自带Queue队列接口
LinkedList(双向链表)、ArrayList均可实现Queue
boolean add(E element): 将指定的元素添加到队列的末尾如果成功则返回true 如果队列已满则抛出异常。
boolean offer(E element) 同上如果队列已满返回false;
E remove() 移除并返回队列头部元素如果队列为空抛出异常
E poll() 同上如果队列为空返回null
E element() 获取队列头部的元素但不移除队列为空抛出异常
E peek() 同上队列为空返回null
int size() 返回队列中元素个数
boolean isEmpty() 判断队列是否为空
clear() 清空
contains(Object o) 是否包含某元素 使用自定义类实现队列满足先进先出的原则实现循环队列 队列的应用 队列的输出顺序和输入顺序相同所以队列通常用于对“历史”的回放也就 是按照“历史”顺序把“历史”重演一遍。 例如在多线程中争夺公平锁的等待队列就是按照访问顺序来决定线程在队 列中的次序的。 再如网络爬虫实现网站抓取时也是把待抓取的网站URL存入队列中再按照存 入队列的顺序来依次抓取和解析的。 1.定义成员变量 队列元素由数组实现定义一个头部指针和一个尾部指针 队列长度由new MyQueue(int MaxSize)决定 需要注意由于循环队列的定义出于判断队空还是队满的区分只要队不空头指针和尾指针永远至少隔一个位置 也就是说队列里的实际元素数量永远比队列长度少1 private E[] arr;private int front;//头部指针private int rear;//尾部指针public MyQueue(int MaxSize){arr(E[])new Object[MaxSize];}
2. 判断队列是否为空 初始位置头指针和尾指针都没动 public boolean isEmpty(){return rearfront;//头指针等于尾指针队列无元素}
3. 入队 先判断队列是否已满判断已满的方法是尾指针1%队列长度头指针 如果未满就为尾指针赋值需注意队列为循环队列尾指针的位置取决于头指针的位置 因此尾指针的位置需要%长度表示在一个循环里 添加元素后尾指针1 public boolean offer(E element) throws Exception {//判断队列是否已满已满返回falseif((rear1)%arr.lengthfront){System.out.println(队列已满);return false;}arr[rear%arr.length]element;rear(rear1)%arr.length;//队尾指针后移一位return true;}
4. 出队 判断队空 存储队首的元素后清除队首元素后把头指针后移一位就能达到出队的效果 public E poll() throws Exception {//如果队列为空返回nullif(isEmpty()){System.out.println(队列为空);return null;}E elementarr[front];//存储需要出队的元素arr[front]null;front(front1)%arr.length;//队头指针后移一位return element;}
5. 获取队首元素 public E getElement(){//判断是否为空为空返回nullif(isEmpty())return null;return arr[front];}
6. 获取队列长度 public int size(){return (reararr.length-front)% arr.length;}
7. 清空队列 public boolean clear(){E[] newArr(E[]) new Object[arr.length];arrnewArr;frontrear0;//必须让指针回归零的位置return true;}
8. 队列是否包含某元素 public boolean contains(E element){if(isEmpty())return false;for (E e : arr) {if(eelement)return true;}return false;}
9. 输出队列 public void print(){for (int i front; i ! rear; i(i1)%arr.length) {System.out.print(arr[i] );}System.out.println();}
10.主函数检验
public static void main(String[] args) throws Exception {MyQueueInteger myquenew MyQueue(5);myque.offer(1);//入队rear0-1myque.offer(2);//rear1-2myque.offer(3);//rear2-3myque.offer(4);//rear3-4myque.poll();//1出队 front0-1myque.poll();//2出队 front1-2myque.offer(5);//5入队 rear4-5-0myque.print();//3 4 5 rear0 front2System.out.println(myque.getElement());//3System.out.println(myque.contains(4));//trueSystem.out.println(myque.contains(1));//falsemyque.offer(3);//入队 rear0-11front队列已满myque.offer(8);//myque.offer(9);myque.print();//3 4 5 3队列实际可存储元素为arr.length-1个也就是4个System.out.println(myque.clear());//清空myque.offer(888);myque.print();//888} 11.完整代码
import java.util.Scanner;
/*
* JAVA自带Queue队列接口
* LinkedList(双向链表)、ArrayList均可实现Queue
* boolean add(E element): 将指定的元素添加到队列的末尾如果成功则返回true如果队列已满则抛出异常。
* boolean offer(E element)同上如果队列已满返回false;
* E remove() 移除并返回队列头部元素如果队列为空抛出异常
* E poll() 同上如果队列为空返回null
* E element()获取队列头部的元素但不移除队列为空抛出异常
* E peek() 同上队列为空返回null
* int size()返回队列中元素个数
* boolean isEmpty() 判断队列是否为空
* clear()清空
* contains(Object o)是否包含某元素*/
public class MyQueueE
{private E[] arr;private int front;//头部指针private int rear;//尾部指针public MyQueue(int MaxSize){arr(E[])new Object[MaxSize];}//判断是否为空public boolean isEmpty(){return rearfront;//头指针等于尾指针队列无元素}//入队public boolean offer(E element) throws Exception {//判断队列是否已满已满返回falseif((rear1)%arr.lengthfront){System.out.println(队列已满);return false;}arr[rear%arr.length]element;rear(rear1)%arr.length;//队尾指针后移一位return true;}//出队public E poll() throws Exception {//如果队列为空返回nullif(isEmpty()){System.out.println(队列为空);return null;}E elementarr[front];//存储需要出队的元素arr[front]null;front(front1)%arr.length;//队头指针后移一位return element;}//获取队首元素public E getElement(){//判断是否为空为空返回nullif(isEmpty())return null;return arr[front];}//返回队列中的元素个数public int size(){return (reararr.length-front)% arr.length;}//清空public boolean clear(){E[] newArr(E[]) new Object[arr.length];arrnewArr;frontrear0;//必须让指针回归零的位置return true;}//是否包含某元素public boolean contains(E element){if(isEmpty())return false;for (E e : arr) {if(eelement)return true;}return false;}//输出队列public void print(){for (int i front; i ! rear; i(i1)%arr.length) {System.out.print(arr[i] );}System.out.println();}public static void main(String[] args) throws Exception {MyQueueInteger myquenew MyQueue(5);myque.offer(1);//入队rear0-1myque.offer(2);//rear1-2myque.offer(3);//rear2-3myque.offer(4);//rear3-4myque.poll();//1出队 front0-1myque.poll();//2出队 front1-2myque.offer(5);//5入队 rear4-5-0myque.print();//3 4 5 rear0 front2System.out.println(myque.getElement());//3System.out.println(myque.contains(4));//trueSystem.out.println(myque.contains(1));//falsemyque.offer(3);//入队 rear0-11front队列已满myque.offer(8);//myque.offer(9);myque.print();//3 4 5 3队列实际可存储元素为arr.length-1个也就是4个System.out.println(myque.clear());//清空myque.offer(888);myque.print();//888}
}
