python爬虫

Created2021-12-19Updated2021-12-19

爬虫介绍

什么是爬虫

通俗理解：爬虫是一个模拟人类请求网站行为的程序。可以自动请求网页、并把数据抓取下来，然后使用一定的规则提取有价值的数据

爬虫应用场景

搜索引擎
伯乐在线
慧慧购物助手
数据分析
抢票软件等

HTTP协议介绍

认识http协议

http协议：全称是HyperText Transfer Protocol，中文意思是超文本传输协议，是一种发布接收html页面的方法。服务器端口号是80端口。HTTPS协议：是http协议的加密版本，在http下加入了SSL层。服务器端口号是443端口

URL详解

URL是Uniform Resource Locator的简写，统一资源定位符。一个URL由以下几个部分组成：

scheme://host:port/path/?query-string=xxx#anchor

scheme：代表的是访问的协议，一般为http或者https以及ftp等
host：主机号，域名，比如www.baidu.com
port：端口号。当你访问一个网站的时候，浏览器默认使用80端口
path：查找路径。比如www.jianshu.com/trending/now，后面的trending/now就是path
query-string：查询字符串，比如：www.baidu.com/s?wd=python，后面的wd=python就是查询字符串
anchor：描点，前端用来做页面定位的。比如一些前后端分离项目，也用描点来做导航。

在浏览器中请求一个url，浏览器会对这个url进行一个编码。除英文字母，数字和部分符号外，其他的全部使用百分号

+十六进制码值进行编码

常见的请求method

在http协议中，定义了八种请求方法，这里介绍两种常用的请求方法，分别是get请求和post请求。

get请求：一般情况下，只从服务器获取数据下来，并不会对服务器资源产生任何影响的时候会用get请求
post请求：向服务器发送数据（登录）、上传文件等，会对服务器资源产生影响的时候会使用post请求。以上是在网站开发中常用的两种方法。并且一般情况下都会遵循使用的原则。但是有的网站和服务器为了做反爬虫机制，也经常会不按常理出牌，有可能一个应该使用get方法的请求就一定要改为post请求，这个要视情况而定

序号	方法	描述
1	GET	请求指定的页面信息，并返回实体主体
2	HEAD	类似于get请求，只不过返回的响应中没有具体内容，用于获取报头
3	POST	向指定资源提交数据进行处理请求（例如提交表单或者上传文件）。数据被包含在请求体中，POST请求可能会导致新的资源建立和/或已有资源的修改
4	PUT	从客户端向服务器传送的数据取代指定的文档的内容
5	DELETE	请求服务器删除指定的页面
6	CONNECT	HTTP/1.1协议中预留给能够将连接改为管道方式的代理服务器
7	OPTIONS	允许客户端查看服务器的性能
8	TRACE	回显服务器收到的请求，注意用于测试或诊断

常见的请求头参数

在http协议中，向服务器发送一个请求，数据分为三部分，第一个是把数据放在url中，第二个是把数据放在body中（在post请求中），第三个就是把数据放在head中。这里介绍在网络爬虫中经常会用到的一些请求头参数：

User-Agent：浏览器名称。这个在网络爬虫中经常会被使用到。请求一个网页的时候，服务器通过这个参数就可以知道这个请求是由哪种浏览器发送的，如果我们是通过爬虫发送请求，那么我们的User-Agent就是python，这对于那些有反爬机制的网站来说，可以轻易的判断你这个请求是爬虫。因此我们要经常设置这个值为一些浏览器的值，来伪装我们的爬虫
Referer：表明当前这个请求是从哪个url过来的。这个一般也可以用来做反爬虫技术。如果不是从指定页面过来的，那么不做相应的响应
Cookie：http协议是无状态的。也就是同一个人发送了两次请求，服务器没有能力直到这两个请求是否来自同一个人。因此这时候就用cookie来做标识。一般如果想要做登录后才能访问的网站，那么就需要发送cookie信息了

常见的响应状态码

200：请求正常，服务器返回正常的返回数据
301：永久重定向。比如在访问www.jingdong.com的时候会重定向到www.jd.com
302：临时重定向。比如在访问一个需要登录的页面的时候，而此时没有登陆，那么就会定向到登录页面
400：请求的url在服务器上找不到。换句话说就是请求url错误
403：服务器拒绝访问，权限不够
500：服务器内部错误。可能是服务器出现bug了1010

Java集合框架

Created2021-12-19Updated2021-12-19

集合体系结构

    单列集合 collection
       可重复list
           ArrayList LinkedList
       不可重复set
          HashSet TreeSet
    双列集合 map
           HashMap

Collection 集合概述

    1.是单例集合的顶层接口，它表示一组对象，这些对象也称为Collection的元素
    2.JDK不提供此接口的任何直接实现，它提供更具体的子接口（如Set和List）实现
    创建Collection对象
    1.多态的方式
    2.具体的实现类ArrayList

import java.util.ArrayList;
import java.util.Collection;

public class day2collection集合概述和引用 {
    public static void main(String[] args) {
        Collection<String> c = new ArrayList<String>();
        //添加元素 ：boolean add(E e)
        c.add("hello");
        c.add("world");
        c.add("java");
        System.out.println(c);
    }
}

集合常用方法

Collection集合常用方法
boolean add(E e) 添加元素
boolean remove(Object o) 从集合中移除指定的元素
void clear() 清空集合中的元素
boolean contains(Object o) 判断集合中是否包含指定元素
boolean isEmpty() 判断集合是否为空
int size() 集合的长度，也就是集合中元素的个数
alt+7快捷键打开一个窗口 能够看到类的信息

import java.util.ArrayList;
import java.util.Collection;

public class day3Collection集合常用方法 {
    public static void main(String[] args) {
        //创建集合对象
        Collection<String> c = new ArrayList<>();
        //boolean add(E e) 添加元素
        /*System.out.println(c.add("hello"));
        System.out.println(c.add("world"));
        System.out.println(c.add("world"));*/
        c.add("hello");
        c.add("world");
        c.add("java");
        //boolean remove(Object o) 从集合中移除指定的元素
        System.out.println(c.remove("world"));
        System.out.println(c.remove("jaba"));
        //void clear() 清空集合中的元素
        c.clear();
        //boolean contains(Object o) 判断集合中是否包含指定元素
        System.out.println(c.contains("world"));
        //boolean isEmpty() 判断集合是否为空
        System.out.println(c.isEmpty());
        //int size() 集合的长度，也就是集合中元素的个数
        System.out.println(c.size());
        //输出集合对象
        System.out.println(c);
    }
}

Collection集合的遍历

Iterator: 迭代器，集合的专用遍历方式
 *Iterator<E> iterator(): 返回此集合中元素的迭代器，通过集合的iterator()方法得到
*迭代器是通过集合的iterator()方法得到的，所以我们说他是依赖于集合而		存在的
Iterator中的常用方法
E next():返回迭代中的下一个元素
boolean hasNext(): 如果迭代具有更多元素，则返回true

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;

public class day4Collection集合的遍历 {
    public static void main(String[] args) {
        //创建集合对象
        Collection<String> c = new ArrayList<>();
        //添加元素
        c.add("hello");
        c.add("world");
        c.add("java");
        //Iterator<E> iterator():返回此集合中元素的迭代器，通过集合的iterator()方法得到
        Iterator<String> it = c.iterator();
        /*public Iterator<E> iterator() {
            return new ArrayList.Itr();
        }
        private class Itr implements Iterator<E> {
            }*/
        /*System.out.println(it.next());
        System.out.println(it.next());
        System.out.println(it.next());*/
//        if (it.hasNext()){
//            System.out.println(it.next());
//        }if (it.hasNext()){
//            System.out.println(it.next());
//        }if (it.hasNext()){
//            System.out.println(it.next());
//        }if (it.hasNext()){
//            System.out.println(it.next());
//        }
        while(it.hasNext()){
//            System.out.println(it.next());
            String s = it.next();
            System.out.println(s);
        }
    }
}

集合使用步骤

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;

public class day5集合使用步骤 {
    public static void main(String[] args) {
        Collection<String> c = new ArrayList<>();
        c.add("hello");
        c.add("world");
        c.add("java");
        Iterator<String> it = c.iterator();
        while(it.hasNext()){
            String s = it.next();
            System.out.println(s);
        }
    }
}

Collection存储学生对象并遍历

需求：创建一个存储学生对象的集合，存储3个学生对象，使用程序实现在控制台遍历该集合

思路：
①定义学生类
②创建Collection对象
③创建学生对象
④把学生添加到集合
⑤遍历集合（迭代器方式）

public class day6Collection存储学生对象并遍历 {
    public static void main(String[] args) {
        //创建Collection集合对象
        Collection<day6Student> c = new ArrayList<>();
        //创建学生对象
        day6Student s1 = new day6Student("杨要想",19);
        day6Student s2 = new day6Student("率秀气",18);
        day6Student s3 = new day6Student("张帅",20);
        //把学生添加到集合
        c.add(s1);
        c.add(s2);
        c.add(s3);
        //遍历集合（迭代器方法）
        Iterator<day6Student> it = c.iterator();
        while(it.hasNext()){
            day6Student s = it.next();
            System.out.println(s.getName() + "," + s.getAge());
        }
    }
}

List集合概述和特点

List集合概述
 ·有序集合（也称为序列），用户可以精准控制列表中每个元素的插入位置。用户可以	通过整数索引访问元素，并搜索列表中的元素。
·与Set集合不同，列表通常允许重复的元素

List集合特点
·有序：存储和取出的元素顺序一致
 ·可重复：存储的元素可以重复

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class day1List集合概述和特点 {
    public static void main(String[] args) {
        //创建集合元素
        List<String> list = new ArrayList<>();
        //添加元素
        list.add("hello");
        list.add("world");
        list.add("java");
        list.add("world");
        //直接输出集合对象
        System.out.println(list);
        //遍历集合
        Iterator<String> it = list.listIterator();
        while(it.hasNext()){
            System.out.println(it.next());
        }
    }
}

List集合特有方法

void add(int index,E element) 在此集合的指定位置插入指定的元素
E remove(int index) 删除指定索引处的元素，返回被删除的元素
E set(set index,E element) 修改指定索引处的元素，返回被修改的元素
E get(int index) 返回指定索引处的元素

import java.util.ArrayList;
import java.util.List;

public class day2List特有方法 {
    public static void main(String[] args) {
        //创建集合元素
        List<String> list = new ArrayList<>();
        //添加元素
        list.add("hello");
        list.add("world");
        list.add("java");
        //void add(int index,E element) 在此集合的指定位置插入指定的元素
        list.add(1,"javaee");
        //list.add(11,"als") 越界异常
        //E remove(int index) 删除指定索引处的元素，返回被删除的元素
        list.remove(1);
        //E set(set index,E element) 修改指定索引处的元素，返回被修改的元素
        list.set(2,"lzy");
        //E get(int index) 返回指定索引处的元素
        System.out.println(list.get(1));
        //输出集合对象
        System.out.println(list);
        //遍历集合
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
    }
}

需求：创建一个存储学生对象的集合，存储3个学生对象，使用程序实现在控制台遍历该集合

①定义学生类
②创建list对象
③创建学生对象
④把学生添加到集合
⑤遍历集合（迭代器方式，for循环方式）

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class day3List集合存储学生对象并遍历 {
    public static void main(String[] args) {
        //创建list集合对象
        List<day3Student> list  = new ArrayList<>();
        //创建学生对象
        day3Student s1 = new day3Student("张三",66);
        day3Student s2 = new day3Student("李四",96);
        day3Student s3 = new day3Student("王五",86);
        //把学生添加到集合
        list.add(s1);
        list.add(s2);
        list.add(s3);
        //遍历集合
        Iterator<day3Student> it = list.listIterator();
        while(it.hasNext()){
            day3Student s = it.next();
            System.out.println(s.getName() + "," + s.getAge());
        }
        for (int i = 0; i < list.size(); i++) {
            day3Student c = list .get(i);
            System.out.println(c.getName() + "," + c.getAge());
        }
    }
}

并发修改异常

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

//遍历集合 得到每一个元素 看有没有world这个元素 如果有 我就添加一个 javaee 元素
//ConcurrentModificationExceptionh 当不允许这样的修改时，可以通过检测到对象的并发修改的方法来抛出此异常

public class day4并发修改异常 {
    public static void main(String[] args) {
        //创建集合对象
        List<String> list = new ArrayList<>();
        //添加元素
        list.add("hello");
        list.add("world");
        list.add("java");
        //遍历集合 得到每一个元素 看有没有world这个元素 如果有 我就添加一个 javaee 元素
        Iterator<String> it = list.iterator();
        while(it.hasNext()){
            String s = it.next();
            if (s.equals("world")){
                list.add("javaee");
            }
        }
//        for (int i = 0; i < list.size(); i++) {
//            String s = list.get(i);
//            if (s.equals("world")){
//                list.add("javaee");
//            }
//        }
        //输出集合对象
        System.out.println(list);
    }
}

ListIterator:列表迭代器

·通过LIst集合的listIterator()方法得到，所以说它是List集合特有的迭代器
·用于允许程序员沿任一方向遍历列表的的列表迭代器，在迭代期间修改列表，并获取列表中迭代器的当前位置

ListIterator中的常用方法

·E next():返回迭代中的下一个元素
·boolean hasNext():如果迭代具有更多元素，则返回true
·E previous():返回列表中的上一元素
·boolean hasPrevious():如果此迭代器在相反方向遍历列表时具有更多元素，则返回true
·void add(E e):将指定的元素插入列表`

import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;

public class day5列表迭代器 {
    public static void main(String[] args) {
        //创建集合对象
        List<String> list = new ArrayList<>();
        //添加元素
        list.add("hello");
        list.add("world");
        list.add("java");
        //通过list集合的listiterator()方法得到
//        ListIterator<String> lit = list.listIterator();
//        while (lit.hasNext()){
//            String s = lit.next();
//            System.out.println(s);
//        }
//        while (lit.hasPrevious()){
//            String s = lit.previous();
//            System.out.println(s);
//        }
        //获取列表迭代器
        ListIterator<String> it = list.listIterator();
        while(it.hasNext()){
            String s= it.next();
            if (s.equals("world")){
                it.add("javaee");
            }
        }
        System.out.println(list);
    }
}

增强for循环

//增强for：简化数组和Collection集合的遍历
//·实现Iterator接口的类允许其对象成为增强型for语句的目标
//·它是JDK5之后出现的，其内部原理是一个Iterator迭代器

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

//增强for的格式
//·格式：
//  for(元素数据类型变量名:数组或者Collection集合){
//      在此处使用变量即可，该变量就是元素
//  }
public class day6增强for循环 {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5};
        for (int i :arr){
            System.out.println(i);
        }
        System.out.println("--------------------");
        String[] strArray = {"hello","world","java"};
        for (String s:strArray){
            System.out.println(s);
        }
        System.out.println("--------------------");
        List<String> list = new ArrayList<>();
        list.add("hello");
        list.add("world");
        list.add("java");
        for (String s:list){
            System.out.println(s);
        }
        //内部原理是一个Iterator迭代器
        for (String s:list){
            if (s.equals("world")){
                list.add("javaee");
            }
        }
        System.out.println("--------------------");
        Iterator<String> it = list.iterator();
        while (it.hasNext()){
            System.out.println(it.next());
        }
        System.out.println("-------------------");
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
        System.out.println("-------------------");

    }
}

List集合的子类特点

List集合常用子类:ArrayList，LinkedList
ArrayList:底层数据结构是数组，查询快，增删慢
LinkedList:底层数据结构是链表，查询慢，增删快

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class day9List集合的子类特点 {
    public static void main(String[] args) {
        List<String> array = new ArrayList<>();
        array.add("hello");
        array.add("world");
        array.add("java");
        //迭代器
        Iterator<String> it = array.listIterator();
        while(it.hasNext()){
            String s = it.next();
            System.out.println(s);
        }
        //for循环
        for (int i = 0; i < array.size(); i++) {
            System.out.println(array.get(i));
        }
        //增强for
        for(String s : array){
            System.out.println(s);
        }
        System.out.println("----------------");
        List<String> linkedstring = new LinkedList<>();
        linkedstring.add("hello");
        linkedstring.add("world");
        linkedstring.add("java");
        //增强for
        for(String s : linkedstring){
            System.out.println(s);
        }
    }
}

LinkedList集合的特有功能

public void addFirst(E e) 在该列表开头插入指定的元素
public void addLast(E e) 将制定元素追加到此列表的末尾
public E getFirst() 返回此列表中的第一个元素
public E getLast() 返回此列表中的最后一个元素
public E removaFirst() 从此列表中删除并返回第一个元素
public E removaLast() 从此列表中删除并返回最后一个元素

import java.util.LinkedList;

public class day10LinkedList集合的特有功能 {
    public static void main(String[] args) {
        //创建集合对象
        LinkedList<String> linkedlist = new LinkedList<>();

        linkedlist.add("hello");
        linkedlist.add("world");
        linkedlist.add("java");
        //public void addFirst(E e) 在该列表开头插入指定的元素
        linkedlist.addFirst("javase");
        //public void addLast(E e) 将制定元素追加到此列表的末尾
        linkedlist.addLast("javaee");
        //public E getFirst() 返回此列表中的第一个元素
        System.out.println(linkedlist.getFirst());
        //public E getLast() 返回此列表中的最后一个元素
        System.out.println(linkedlist.getLast());
        //public E removaFirst() 从此列表中删除并返回第一个元素
        System.out.println(linkedlist.removeFirst());
        //public E removaLast() 从此列表中删除并返回最后一个元素
        System.out.println(linkedlist.removeLast());
        System.out.println(linkedlist);
    }
}

集合常用方法
Collection集合的遍历
集合使用步骤
Collection存储学生对象并遍历
List集合特有方法
并发修改异常
ListIterator:列表迭代器
ListIterator中的常用方法
增强for循环
List集合的子类特点
LinkedList集合的特有功能
哈希值:
HashSet集合概述和特点
HashSet集合保证元素唯一性源码分析
哈希表
LinkedHashSet集合特点
TreeSet集合概述和特点
自然排序Comparabale的使用
比较器排序Comparator的使用

Set

Set集合概述和特点
Set集合特点：
  不包含重复元素的集合
  没有带索引的方法，所以不能使用普通for循环遍历

import java.util.HashSet;
import java.util.Set;

public class day1Set集合概述和特点 {
    public static void main(String[] args) {
        //创建集合对象
        Set<String> set = new HashSet<>();
        //添加元素
        set.add("hello");
        set.add("world");
        set.add("java");
        //不包含重复元素
        set.add("world");
        //遍历
        for (String s : set){
            System.out.println(s);
        }
    }
}

哈希值:

是JDK根据对象的地址或者字符串或者数字算出来的int类型的数值

Object类中有一个方法可以获取对象的哈希值
  public int hashCode();返回对象的哈希码值

public class day2哈希值 {
    public static void main(String[] args) {
        //创建学生对象
        day2Student s1 = new day2Student("林青霞",30);
        //同一个对象多次调用hashCode()这个方法返回的哈希值是相同的
        System.out.println(s1.hashCode());//1956725890
        System.out.println(s1.hashCode());//1956725890
        System.out.println("---------------------------");
        //默认情况下，不同对象的哈希值是不相同的
        //通过方法重写，可以实现不同对象的哈希值是相同的
        day2Student s2 = new day2Student("林青霞",30);
        System.out.println(s2.hashCode());//356573597

        System.out.println("-------------------------");

        System.out.println("hello".hashCode());//99162322
        System.out.println("world".hashCode());//113318802
        System.out.println("java".hashCode());//3254818

        System.out.println("world".hashCode());//113318802

        System.out.println("重地".hashCode());//1179395
        System.out.println("通话".hashCode());//1179395
    }
}

HashSet集合概述和特点

  底层数据结构是哈希表
  对集合的迭代顺序不保证，也就是说不保证存储和取出的元素顺序一致
  没有带索引的方法，所以不能使用普通for循环遍历
  由于是set集合，所以是不包含重复元素的集合

import java.util.HashSet;

public class day3HashSet集合概述和特点 {
    public static void main(String[] args) {
        //创建集合对象
        HashSet<String> hs = new HashSet<>();
        //添加元素
        hs.add("hello");
        hs.add("world");
        hs.add("java");

        hs.add("world");
        //遍历
        for (String s : hs){
            System.out.println(s);
        }
    }
}

HashSet集合保证元素唯一性源码分析

//创建集合对象
HashSet<String> hs = new HashSet<>();
//添加元素
hs.add("hello");
hs.add("world");
hs.add("java");
------------------------------------

public boolean add(E e) {
        return map.put(e, PRESENT)==null;
}
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
publi c V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //如果哈希表未初始化，就对其进行初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //根据对象的哈希值计算对象的存储位置，如果该位置没有元素，就存储元素
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        /*
            存入的元素和以前的元素比较哈希值
                如果哈希值不同，会继续向下执行，把元素添加到集合
                如果哈希值相同，会调用对象的equals()方法比较
                    如果返回false，会继续向下执行，把元素添加到集合
                    如果返回true，说明元素重复，不存储
        */
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

哈希表

JDK8之前，底层采用数组+链表实现，可以说是一个元素为链表的数组
JDK8之后，在长度比较长的时候，底层实现了优化

//需求:创建一个存储学生对象的系统，存储多个学生对象，使用程序实现在控制台遍历
//要求:学生对象的成员变量相同，我们就认为是同一个对象
//
//思路:
//1.定义学生类
 //2.创建HashSet集合对象
 //3.创建学生对象
 //4.把学生添加到集合
 //5.遍历集合(加强for循环)
//6.在学生类中重写两个方法 hashcode()和equals() 自动生成即可 alt+insert

import java.util.HashSet;

public class day6HashSet集合存储学生对象并遍历 {
    public static void main(String[] args) {
        //创建hashset集合对象
        HashSet<day6Student> hs = new HashSet<>();
        //创建学生对象
        day6Student s1 = new day6Student("林青霞",30);
        day6Student s2 = new day6Student("张曼玉",35);
        day6Student s3 = new day6Student("王祖贤",33);

        day6Student s4 = new day6Student("王祖贤",33);

        //把学生添加到集合
        hs.add(s1);
        hs.add(s2);
        hs.add(s3);

        hs.add(s4);

        //遍历集合
        for (day6Student s : hs){
            System.out.println(s.getName()+","+s.getAge());
        }
    }
}

package 集合框架.Set;

import java.util.Objects;

public class day6Student {
    private String name;
    private int age;

    public day6Student(){

    }
    public day6Student(String name,int age){
        this.name = name;
        this.age = age;
    }
    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 boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        day6Student that = (day6Student) o;
        return age == that.age && Objects.equals(name, that.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
}

LinkedHashSet集合特点

//1.哈希表和链表实现的Set接口，具有可预测的迭代次序
//2.由链表保证元素有序，也就是说元素的存储和取出顺序是一致的
//3.由哈希表保证元素唯一，也就是说没有重复的元素
//
//练习:存储字符串并遍历

import java.util.LinkedHashSet;

public class day7LinkedHashSet集合概述和特点 {
    public static void main(String[] args) {
        //创建集合对象
        LinkedHashSet<String> lsk = new LinkedHashSet<>();
        //添加元素
        lsk.add("hello");
        lsk.add("world");
        lsk.add("java");
        lsk.add("world");
        //遍历集合
        for (String s : lsk){
            System.out.println(s);
        }
    }
}

TreeSet集合概述和特点

1.元素有序，这里的顺序不是指存储和取出的顺序，而是按照一定的规则进行排序，具体排序方式取决于构造方法
TreeSet():根据其元素的自然顺序进行排序
TreeSet(Comparator comparator):根据指定的比较器进行排序
2.没有带索引的方法，所以不能使用普通for循环进行遍历
3.由于是set集合，所以不包含重复元素的集合

TreeSet集合练习:存储整数并遍历

import java.util.TreeSet;

public class day8TreeSet集合概述和特点 {
    public static void main(String[] args) {
        //创建集合对象
        TreeSet<Integer> ts = new TreeSet<>(); //所有基本类型引用时需要用包装类
        //添加元素
        ts.add(10);
        ts.add(40);
        ts.add(30);
        ts.add(50);
        ts.add(20);

        ts.add(30);
        //遍历
        for (Integer i : ts){
            System.out.println(i);
        }
    }
}

自然排序Comparabale的使用

存储学生对象并遍历，创建TreeSet集合使用无参构造方法
要求:按照年龄从小到大进行排序，年龄相同时，按照姓名的字母顺序排序

import java.util.TreeSet;

public class day9自然排序Comparabale的使用 {
    public static void main(String[] args) {
        //创建集合对象
        TreeSet<day9Student> ts = new TreeSet<>();
        //创建学生对象
        day9Student s1 = new day9Student("xishi",29);
        day9Student s2 = new day9Student("wangzhaojun",28);
        day9Student s3 = new day9Student("diaochan",30);
        day9Student s4 = new day9Student("yangyuhuan",33);
        day9Student s5 = new day9Student("linqingxia",33);
        day9Student s6 = new day9Student("linqingxia",33);
        //把学生添加到集合
        ts.add(s1);
        ts.add(s2);
        ts.add(s3);
        ts.add(s4);
        ts.add(s5);
        ts.add(s6);
        //遍历集合
        for (day9Student s : ts){
            System.out.println(s.getName()+","+s.getAge());
        }
    }
}

package 集合框架.Set;

public class day9Student implements Comparable<day9Student>{
    private String name;
    private int age;

    public day9Student(){

    }
    public day9Student(String name,int age){
        this.name = name;
        this.age = age;
    }
    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 int compareTo(day9Student s) {
//        return 0;
//        return 1;
//        return -1;
        //按照年龄进行排序
//        int num = s.age - this.age; 升序
        int num = this.age - s.age;
        int num2  = num==0?this.name.compareTo(s.name):num;
        return num2;
    }
}

比较器排序Comparator的使用

存储学生对象并遍历，创建TreeSet集合使用带参构造方法
要求:按照年龄从小到大排序，年龄相同时，按照姓名的字母顺序排序

import java.util.Comparator;
import java.util.TreeSet;

public class day10比较器排序Comparator的使用 {
    public static void main(String[] args) {
        //创建集合对象
        TreeSet<day10Student> ts = new TreeSet<>(new Comparator<day10Student>() {
            @Override
            public int compare(day10Student s1, day10Student s2) {
                //this.age - s.age
                //s1,s2
                int num = s1.getAge()-s2.getAge();
                int num2 = num==0?s1.getName().compareTo(s2.getName()):num;
                return num2;
            }
        });
        //创建学生对象
        day10Student s1 = new day10Student("xishi",29);
        day10Student s2 = new day10Student("wangzhaojun",28);
        day10Student s3 = new day10Student("diaochan",30);
        day10Student s4 = new day10Student("yangyuhuan",33);

        day10Student s5 = new day10Student("linqingxia",33);
        day10Student s6 = new day10Student("linqingxia",33);
        //把学生添加到集合
        ts.add(s1);
        ts.add(s2);
        ts.add(s3);
        ts.add(s4);
        ts.add(s5);
        ts.add(s6);
        //遍历集合
        for (day10Student s : ts){
            System.out.println(s.getName()+","+s.getAge());
        }
    }
}

package 集合框架.Set;

public class day10Student {
    private String name;
    private int age;

    public day10Student(){

    }
    public day10Student(String name,int age){
        this.name = name;
        this.age = age;
    }
    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;
    }
}

需求:用TreeSet集合存储多个学生信息(姓名，语文成绩，数学成绩)，并遍历该集合
要求:按照总分从高到低出现

思路:
①定义学生类
②创建TreeSet集合对象，通过比较器排序进行排序
③创建学生对象
④把学生对象添加到集合
⑤遍历集合

import java.util.Comparator;
import java.util.TreeSet;

public class day11案例成绩排序 {
    public static void main(String[] args) {
        //创建TreeSet集合对象，通过比较器排序进行排序
        TreeSet<day11Student> ts = new TreeSet<>(new Comparator<day11Student>() {
            @Override
            public int compare(day11Student s1, day11Student s2) {
                //int num = (s2.getChinese() + s2.getMath())-(s1.getChinese()-s2.getMath());
                int num = s2.getSum()-s1.getSum();
                int num2 = num==0?s1.getChinese()-s2.getChinese():num;
                int num3 = num2==0?s1.getName().compareTo(s2.getName()):num2;
                return num3;
            }
        });
        //创建学生对象
        day11Student s1 = new day11Student("林青霞",98,100);
        day11Student s2 = new day11Student("张曼玉",95,95);
        day11Student s3 = new day11Student("王祖贤",100,93);
        day11Student s4 = new day11Student("柳岩",100,97);
        day11Student s5 = new day11Student("风清扬",98,98);
        day11Student s6 = new day11Student("左冷禅",97,99);
        //day11Student s7 = new day11Student("左冷禅",97,99);
        day11Student s7 = new day11Student("赵云",97,99);
        //把学生添加到集合
        ts.add(s1);
        ts.add(s2);
        ts.add(s3);
        ts.add(s4);
        ts.add(s5);
        ts.add(s6);
        ts.add(s7);
        //遍历集合
        for (day11Student s: ts){
            System.out.println(s.getName()+","+s.getChinese()+","+s.getMath()+","+s.getSum());
        }
    }
}

package 集合框架.Set;

public class day11Student {
    private String name;
    private int chinese;
    private int math;

    public day11Student(){

    }
    public day11Student(String name,int chinese,int math){
        this.name = name;
        this.chinese = chinese;
        this.math = math;
    }


    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getChinese() {
        return chinese;
    }

    public void setChinese(int chinese) {
        this.chinese = chinese;
    }

    public int getMath() {
        return math;
    }

    public void setMath(int math) {
        this.math = math;
    }
    public int getSum(){
        return this.chinese+this.getMath();
    }

}

需求:编写一个程序，获取10个1-20之间的随机数，要求随机数不能重复，并在控制台输出
①创建set集合
②创建随机数对象
③判断集合的长度是不是小于10
是:产生一个随机数，添加到集合
回到3继续
④遍历集合

import java.util.HashSet;
import java.util.Random;
import java.util.Set;
import java.util.TreeSet;

public class day12案例不重复的随机数 {
    public static void main(String[] args) {
        //创建set集合
        //Set<Integer> set = new HashSet<>(); 不会排序
        Set<Integer> set = new TreeSet<>();  //会排序
        //创建随机数对象
        Random r = new Random();
        //判断集合的长度是不是小于10
        while (set.size()<10){
            //产生一个随机数，添加到集合
            int number = r.nextInt(20)+1;
            set.add(number);
        }
        //遍历集合
        for (Integer i : set){
            System.out.println(i);
        }
    }
}

Map

Map集合概述:
·Interface Map<K,V> K:键的类型;V:值的类型
·将键映射到值的对象;不能包含重复的键;每个键可以映射最多一个值
·举例:学生的姓名和学号
itheima001 林青霞
itheima002 张曼玉
itheima003 王祖贤

创建Map集合的对象
·多态的方式
·具体的实现类HashMap

import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class day1Map集合概述和使用 {
    public static void main(String[] args) {
        //创建集合对象
        Map<String,String> map = new HashMap<>();
        //添加元素
        //V put(K key, V value) 将指定的值与此映射中的指定键关联（可选操作）。
        map.put("itheima001","林青霞");
        map.put("itheima002","张曼玉");
        map.put("itheima003","王祖贤");
        map.put("itheima003","柳岩");
        //输出集合对象
        System.out.println(map);
    }
}

V put(K key, V value) 添加元素
V remove(Object key) 根据键删除值对元素
void clear() 移除所有的键值对元素
boolean containsKey(Object key) 判断集合是否包含指定的键
boolean containsValue(Object value) 判断集合是否包含指定的值
boolean isEmpty() 判断集合是否为空
int size() 集合的长度也就是集合中键值对的个数

import java.util.HashMap;
import java.util.Map;

public class day2Map集合的基本功能 {
    public static void main(String[] args) {
        //创建集合对象
        Map<String,String> map = new HashMap<>();
        //V put(K key, V value) 添加元素
        map.put("张无忌","赵敏");
        map.put("郭靖","黄蓉");
        map.put("杨过","小龙女");
        //V remove(Object key) 根据键删除值对元素
        System.out.println(map.remove("郭靖"));
        System.out.println(map.remove("郭想"));
        //void clear() 移除所有的键值对元素
        //map.clear();
        //boolean containsKey(Object key) 判断集合是否包含指定的键
        System.out.println(map.containsKey("郭靖"));
        System.out.println(map.containsKey("张无忌"));
        //boolean isEmpty() 判断集合是否为空
        System.out.println(map.isEmpty());
        //int size() 集合的长度也就是集合中键值对的个数
        System.out.println(map.size());
        //输出集合对象
        System.out.println(map);
    }
}

V get(Object key) 根据键获取值
Set<k>keySet() 获取所有键的集合
Collection<V>values() 获取所有值的集合
Set<Map.Entry<K,V>>entrySet() 获取所有键值对对象的集合

import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class day3Map集合的获取功能 {
    public static void main(String[] args) {
        //创建集合对象
        Map<String,String> map = new HashMap<>();
        //添加元素
        map.put("张无忌","赵敏");
        map.put("郭靖","黄蓉");
        map.put("杨过","小龙女");
        //V get(Object key) 根据键获取值s
        System.out.println(map.get("张无忌"));
        System.out.println(map.get("张三丰"));
        //Set<k>keySet() 获取所有键的集合
        Set<String> keySet = map.keySet();
        for (String key: keySet){
            System.out.println(key);
        }
        //Collection<V>values() 获取所有值的集合
        Collection<String> values = map.values();
        for (String value : values){
            System.out.println(value);
        }
    }
}

我们刚才存储的元素都是成对出现的，所以我们把Map看成是一个夫妻对的集合
遍历思路
1.把所有的丈夫集合起来
2.遍历丈夫的集合，获取每一个丈夫
3.根据丈夫去找对应的妻子

转换为Map集合中的操作
1.获取所有键的集合。用keySet()方法实现
2.遍历键的集合，获取每一个键。用增强for实现
3.根据键去找值。用get(Object key)方法实现

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class day4Map集合的遍历1 {
    public static void main(String[] args) {
        //创建集合对象
        Map<String,String> map = new HashMap<>();
        //添加元素
        map.put("张无忌","赵敏");
        map.put("郭靖","黄蓉");
        map.put("杨过","小龙女");
        //1.获取所有键的集合。用keySet()方法实现
        Set<String> keySet = map.keySet();
        //2.遍历键的集合，获取每一个键。用增强for实现
        for (String key:keySet){
            //3.根据键去找值。用get(Object key)方法实现
            String value = map.get(key);
            System.out.println(key+","+value);
        }
    }
}

//我们刚才存储的元素都是成对出现的，所以我们把Map看成是一个夫妻对的集合
//遍历思路
//1.获得所有结婚证的集合
//2.遍历结婚证的集合，得到每一个结婚证
//3.根据结婚证获取丈夫和妻子

//转换为Map集合中的操作:
//获取所有键值对对象的集合
//Set<Map.Entry<K,V>>entrySet():获取所有键值对对象的集合
//遍历键值对对象的集合，得到每一个键值对对象
//用增强for实现，得到每一个Map.Entry
//根据键值对对象获取每一个键值对对象
//用getKey()得到键
//用getValue()得到值

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class day5Map集合的遍历2 {
    public static void main(String[] args) {
        //创建集合对象
        Map<String,String> map = new HashMap<>();
        //添加元素
        map.put("张无忌","赵敏");
        map.put("郭靖","黄蓉");
        map.put("杨过","小龙女");
        //获取所有键值对对象的集合
        Set<Map.Entry<String,String>> entrySet = map.entrySet();
        //遍历键值对对象的集合，得到每一个键值对对象
        for(Map.Entry<String,String> me : entrySet){
            //根据键值对对象获取每一个键值对对象
            String key = me.getKey();
            String value = me.getValue();
            System.out.println(key+","+value);
        }
    }
}

需求:
键盘录入一个字符串，要求统计字符串中每个字符出现的次数。
举例:键盘录入 “aababcabcdabcde” 在控制台输出:“a(5)b(4)c(3)d(2)e(1)”

分析:
①我们可以把结果分成几个部分来看:a(5),b(4),c(3),d(2),e(1)
②每一个部分可以看成是:字符和字符对应的次数组成
③这样的数据，我们可以通过HashMap集合来存储，键是字符，值是字符出现的次数
注意:键是字符，类型应该是Character；值是字符出现的次数，类型应该是Integer

思路:
键盘录入一个字符串
创建HashMap集合，键是Character，值是Integer
遍历字符串，得到一个字符
拿得到的每一个字符作为键到HashMap集合中去找对应的值，看起返回值
如果返回值是null：说明该字符在HashMap集合中不存在，就把该字符作为键，1作为值存储
如果返回值不是null：说明该字符在集合中存在，把值加1，然后重新存储该字符和对应的值
遍历HashMap集合，得到键和值，按照要求进行拼接
输出结果

import java.util.HashMap;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeMap;

public class day10统计字符串中每个字符出现的次数 {
    public static void main(String[] args) {
        //键盘录入一个字符串
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入一个字符串：");
        String line = sc.nextLine();
        //创建HashMap集合，键是Character，值是Integer
        //HashMap<Character,Integer> hm = new HashMap<Character,Integer>();
        TreeMap<Character,Integer> hm = new TreeMap<Character,Integer>();
        //遍历字符串，得到一个字符
        for (int i = 0; i < line.length() ;i++) {
            char key = line.charAt(i);
            //拿得到的每一个字符作为键到HashMap集合中去找对应的值，看起返回值
            Integer value = hm.get(key);
            if (value == null){
                //  如果返回值是null：说明该字符在HashMap集合中不存在，就把该字符作为键，1作为值存储
                hm.put(key,1);
            }else{
                //  如果返回值不是null：说明该字符在集合中存在，把值加1，然后重新存储该字符和对应的值
                value++;
                hm.put(key,value);
            }
        }
        //遍历HashMap集合，得到键和值，按照要求进行拼接
        StringBuilder sb = new StringBuilder();
        Set<Character> keySet = hm.keySet();
        for (Character key : keySet){
            Integer value = hm.get(key);
            sb.append(key).append("(").append(value).append(")");
        }
        String result = sb.toString();
        //输出结果
        System.out.println(result);
    }
}

Collections

Collections类的常用方法
·public static <T extends Comparable <?super T>> void sort(List list):将指定的列表按升序排序
·public static void reverse(List <?>list):反转指定列表中元素的顺序
·public static void shuffle(List<?> list):使用默认的随机源随机排列指定的列表

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class day1Collections概述和使用 {
    public static void main(String[] args) {
        //创建集合对象
        List<Integer> list = new ArrayList<>();
        //添加元素
        list.add(30);
        list.add(20);
        list.add(50);
        list.add(10);
        list.add(40);
        //·public static <T extends Comparable <?super T>> void sort(List<T> list):将指定的列表按升序排序
        Collections.sort(list);
        //·public static void reverse(List <?>list):反转指定列表中元素的顺序
        Collections.reverse(list);
        //·public static void shuffle(List<?> list):使用默认的随机源随机排列指定的列表
        Collections.shuffle(list);
        System.out.println(list);
    }
}

需求:ArrayList存储学生对象，使用Collections对ArrayList进行排序
要求:按照年龄从小到大排序，年龄相同时，按照姓名的字母顺序进行排序

思路:
①定义学生类
②创建ArrayList集合对象
③创建学生对象
④把学生添加到集合
⑤使用Collections对ArrayList集合排序
⑥遍历集合


import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

public class day2ArrayList集合存储学生并排序 {
    public static void main(String[] args) {
        //创建ArrayList集合对象
        ArrayList<day2Student> array = new ArrayList<>();
        //创建学生对象
        day2Student s1 = new day2Student("linqingxia",30);
        day2Student s2 = new day2Student("zhangmanyu",35);
        day2Student s3 = new day2Student("wangzuxian",33);
        day2Student s4 = new day2Student("liuyan",33);
        //把学生添加到集合
        array.add(s1);
        array.add(s2);
        array.add(s3);
        array.add(s4);
        //使用Collections对ArrayList集合排序
        Collections.sort(array, new Comparator<day2Student>() {
            @Override
            public int compare(day2Student s1, day2Student s2) {
                int num = s1.getAge() - s2.getAge();
                int num2 = num==0?s1.getName().compareTo(s2.getName()):num;
                return num2;
            }
        });
        //遍历集合
        for (day2Student s : array){
            System.out.println(s.getName()+","+s.getAge());
        }
    }
}

Java多线程

Created2021-12-19Updated2021-12-19

进程和线程
多线程的实现方式
设置和获取线程名称
线程调度
线程生命周期
多线程的实现方式2
共享数据安全问题
同步方法
线程安全的类
Lock锁
生产者消费者案例

实现多线程

进程和线程

进程: 是正在运行的程序

·是系统进行资源分配和调用的独立单位

·每一进程都有它自己的内存空间和系统资源

线程:

是进程中的单个顺序控制流，是一条执行路径

单线程:一个进程如果只有一条执行路径，则成为单线程程序

多线程:一个进程如果有多条执行路径，则成为多线程程序

举例:

(单线程)记事本程序，(多线程)扫雷游戏

多线程的实现方式

定义一个类MyThread继承Thread类
在MyThread类中重写run()方法
创建MyThread类的对象
启动线程

两个小问题:

为什么要重写run()方法呢？

因为run()是用来封装被线程执行的代码

run()方法和start()方法的区别

run():封装线程执行的代码,直接调用,相当于普通方法的调用

start():启动线程；然后由jvm调用此线程的run()方法

public class day2继承Thread类的方式实现多线程 {
    public static void main(String[] args) {
        day2MyThread my1 = new day2MyThread();
        day2MyThread my2 = new day2MyThread();

        //my1.run();
        //my2.run();

        //void start() 导致此线程开始执行；Java虚拟机调用此线程的run方法
        my1.start();
        my2.start();
    }
}

设置和获取线程名称

Thread类中设置和获取线程名称的方法
·void setName(String name): 将此线程的名称更改为等于参数name
·String getName():返回此线程的名称
·通过构造方法也可以设置线程名称

如何获取main()方法所在的线程名称？
·public static Thread currentThread():返回对当前正在执行的线程对象的引用

public class day3设置和获取线程名称 {
    public static void main(String[] args) {
//        day3MyThread my1 = new day3MyThread();
//        day3MyThread my2 = new day3MyThread();
//        //void setName(String name): 将此线程的名称更改为等于参数
//        my1.setName("高铁");
//        my1.setName("飞机");

        //Thread(String name)
        day3MyThread my1 = new day3MyThread("飞机");
        day3MyThread my2 = new day3MyThread("高铁");

        my1.start();
        my2.start();

        //static Thread currThread() 返回对当前正在执行的线程对象的引用
        System.out.println(Thread.currentThread().getName());
    }
}

public class day3MyThread extends Thread {
    public day3MyThread(){

    }
    public  day3MyThread(String name){
        super(name);
    }
    @Override
    public void run() {
        for (int i = 0; i < 100; i++) {
            System.out.println(getName()+":"+i);
        }
    }
}

线程调度

线程有两种调度模型:

·分时调度模型:所有线程轮流使用CPU的使用权，平均分配每个线程占用CPU的时间片

·抢占式调度模型:优先让优先级高的线程使用CPU，如果线程的优先级相同，那么会随机选择一个，优先级高的线程获取的CPU时间片相对多一点
Java使用的是抢占式调度模型

假设计算机只有一个CPU，那么CPU在某一时刻只能执行一条指令，线程只有得到CPU时间片，也就是使用权，才可以执行指令。
所以说多线程程序的执行是随机性，因为谁抢到CPU的使用权是不一定的

Thread类中设置和获取线程优先级的方法:

1	public final void setPriority(int newPriority):更改此线程的优先级

1	public final int getPriority():返回此线程的优先级

线程默认优先级是5；线程优先级的范围是：1-10
线程优先级高仅仅表示线程获取的CPU时间片的几率高，但是要在次数比较多，或者多次运行的时候才能看到你想要的效果

public class day4线程调度 {
    public static void main(String[] args) {
        day4MyThread tp1 = new day4MyThread();
        day4MyThread tp2 = new day4MyThread();
        day4MyThread tp3 = new day4MyThread();

        tp1.setName("高铁");
        tp2.setName("飞机");
        tp3.setName("汽车");

        //public final int getPriority():返回此线程的优先级
//        System.out.println(tp1.getPriority());//5
//        System.out.println(tp2.getPriority());//5
//        System.out.println(tp3.getPriority());//5

// public final void setPriority(int newPriority):更改此线程的优先级
//        tp1.setPriority(10000);//IllegalArgumentException
//        System.out.println(Thread.MAX_PRIORITY);
//        System.out.println(Thread.MIN_PRIORITY);
//        System.out.println(Thread.NORM_PRIORITY);

        //设置正确的优先级
        tp1.setPriority(5);
        tp2.setPriority(10);
        tp3.setPriority(1);

        tp1.start();
        tp2.start();
        tp3.start();
    }
}

线程生命周期

在这里插入图片描述

public class day6线程生命周期 {
    public static void main(String[] args) throws InterruptedException {
        Thread thread = new Thread(()->{
            for (int i = 0; i < 5; i++) {
                try {
                    Thread.sleep(1000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
            System.out.println("//////");
        });
        //观察状态
        Thread.State state = thread.getState();
        System.out.println(state); //new
        //观察启动后
        thread.start();//启动线程
        state = thread.getState();
        System.out.println(state);//Run
        while (state != Thread.State.TERMINATED) {//只要线程不终止，就一直输出状态
            Thread.sleep(100);
            state = thread.getState();//更新线程状态
            System.out.println(state);//输出状态
        }
    }
}

多线程的实现方式2

方式2:实现Runnable接口

·定义一个类MyRunnable实现Runnable接口

·在MyRunnable中重写run()方法

·创建MyRunnable类对象

·创建Thread类的对象,把MyRunnable对象作为构造方法的参数

·启动线程

多线程的实现有两种:

·继承Thread类

·实现Runnable接口

相比继承Thread类，实现Runnable接口的好处:

·避免了Java单继承的局限性

·适合多个相同程序的代码去处理同一个资源的情况，把线程和程序的代码，数据有效分离，较好的体现了面向对象的设计思想

public class day7多线程的实现方式 {
    public static void main(String[] args) {
        //·创建MyRunnable类对象
        day7MyRunnable my = new day7MyRunnable();
        //把MyRunnable对象作为构造方法的参数
        //Thread(Runnable target)
//        Thread t1 = new Thread(my);
//        Thread t2 = new Thread(my);
        Thread t1 = new Thread(my,"高铁");
        Thread t2 = new Thread(my,"飞机");
        //启动线程
        t1.start();
        t2.start();
    }
}

public class day7MyRunnable implements Runnable {

    @Override
    public void run() {
        for (int i = 0; i < 100; i++) {
            System.out.println(Thread.currentThread().getName()+":"+i);//这里不能直接使用getName方式
        }
    }
}

线程同步

共享数据安全问题

为什么出现问题?(这也是我们判断多线程程序是否会有数据安全问题的标准)

·是否是多线程环境
·是否有共享数据
·是否有多条语句操作共享数据

如何解决多线程安全问题呢？

·基本思想:让程序没有安全问题的环境

怎么实现呢?

把多条语句操作共享数据的代码给锁起来，让任意时刻只能有一个线程执行即可

同步代码块：

锁多条语句操作共享数据的代码，可以使用同步代码块实现
·格式:
synchronized(任意对象){
多条语句操作共享数据的代码
}
·synchronized(任意对象):就相当于给代码加锁了，任意对象就可以看成是一把锁

同步的好处和弊端

·好处：解决了多线程的数据安全问题
·弊端：当线程很多时，因为每个线程都会去判断同步上的锁，这是很耗费资源的，无形中会降低程序的运行效率

public class day3卖票案例数据安全问题的解决 {
    public static void main(String[] args) {
        //  A:创建SellTicket对象
        day3SellTickets st = new day3SellTickets();
        //  B:创建三个Thread类的对象，把SellTicket对象作为构造方法的参数，并给出对应的窗口名称
        Thread t1 = new Thread(st,"窗口一");
        Thread t2 = new Thread(st,"窗口二");
        Thread t3 = new Thread(st,"窗口三");
        //  C:启动线程
        t1.start();
        t2.start();
        t3.start();
    }
}

public class day3SellTickets implements Runnable{
    private int tickets = 100;
    private Object obj = new Object();
    @Override
    public void run() {
        while (true){
            synchronized (obj) {
                if (tickets > 0) {
                    try {
                        Thread.sleep(100);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                    System.out.println(Thread.currentThread().getName() + "正在出售第" + tickets + "张票");
                    tickets--;
                }
            }
        }
    }
}

同步方法

同步方法: 就是把synchronized关键字加到方法上

·格式:

修饰符synchronized返回值类型方法名(方法参数){ }

同步方法的锁对象是什么呢：

·是this这个对象

同步静态方法: 就是把synchronized关键字加到静态方法上

·格式:

修饰符 static synchronized 返回值类型方法名(方法参数){ }

public class day4同步方法 {
    public static void main(String[] args) {
        day4SellTickets st = new day4SellTickets();

        Thread t1 = new Thread(st,"窗口1");
        Thread t2 = new Thread(st,"窗口2");
        Thread t3 = new Thread(st,"窗口3");

        t1.start();
        t2.start();
        t3.start();


    }
}

package 多线程.线程同步;

public class day4SellTickets implements Runnable{
//    private int tickets = 100;
    private static int tickets = 100;
    private Object obj = new Object();
    private int x = 0;
    @Override
    public void run() {
        while(true){
            if (x%2==0) {
                //synchronized (obj) {
//                synchronized (this) {
                synchronized (day4SellTickets.class) {
                    if (tickets > 0) {
                        try {
                            Thread.sleep(100);
                        } catch (InterruptedException e) {
                            e.printStackTrace();
                        }
                        System.out.println(Thread.currentThread().getName() + "正在出售第" + tickets + "张票");
                        tickets--;
                    }
                }
            }else{
//                synchronized (obj) {
//                    if (tickets > 0) {
//                        try {
//                            Thread.sleep(100);
//                        } catch (InterruptedException e) {
//                            e.printStackTrace();
//                        }
//                        System.out.println(Thread.currentThread().getName() + "正在出售第" + tickets + "张票");
//                        tickets--;
//                    }
//                }
                sellTicket();
            }
            x++;
        }
    }

//    private void sellTicket() {
//        synchronized (obj) {
//            if (tickets > 0) {
//                try {
//                    Thread.sleep(100);
//                } catch (InterruptedException e) {
//                    e.printStackTrace();
//                }
//                System.out.println(Thread.currentThread().getName() + "正在出售第" + tickets + "张票");
//                tickets--;
//            }
//        }
//private synchronized void sellTicket() {
//
//        if (tickets > 0) {
//            try {
//                Thread.sleep(100);
//            } catch (InterruptedException e) {
//                e.printStackTrace();
//            }
//            System.out.println(Thread.currentThread().getName() + "正在出售第" + tickets + "张票");
//            tickets--;
//        }
//    }
private static synchronized void sellTicket() {

    if (tickets > 0) {
        try {
            Thread.sleep(100);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println(Thread.currentThread().getName() + "正在出售第" + tickets + "张票");
        tickets--;
    }
    }
}

线程安全的类

StringBuffer

·线程安全,可变的字符序列
·从版本JDK5开始，被StringBuilder替代。通常应该使用StringBuilder类。因为它支持所有相同的操作，但它更快，因为它不执行同步

Vector

·从Java2平台v1.2开始，该类改进了List接口，使其成为Java Collections Framework的成员。与新的集合实现不同，Vector被同步。
如果不需要线程安全的实现，建议使用ArrayList代替Vector

Hashtable

·该类实现了一个哈希表，它将键映射到值。任何非null对象都可以用作键或者值
·从Java2平台v1.2开始，该类进行了改进，实现了Map接口，使其成为Java Collections Framework的成员。
与新的集合实现不同，Hashtable被同步。如果不需要线程安全的实现，建议使用HashMap代替Hashtable

import java.io.StringBufferInputStream;
import java.util.*;

public class day5线程安全的类 {
    public static void main(String[] args) {
        StringBuffer sb = new StringBuffer();
        StringBuilder sb2 = new StringBuilder();

        Vector<String> v = new Vector<>();
        ArrayList<String> array = new ArrayList<>();

        Hashtable ht = new Hashtable();
        HashMap<String,String> hm = new HashMap();

        //static <T> List<T> synchronizedList(List<T> list) 返回由指定列表支持的同步（线程安全）列表。
        Collections.synchronizedList(new ArrayList<>());
    }
}

Lock锁

虽然我们可以理解同步代码块和同步方法的锁对象问题，但是我们没有直接看到在哪里加上了锁，在哪里释放了锁，
为了更清晰的表达如何加锁和释放锁，JDK5以后提供了一个新的锁对象Lock

Lock实现提供比使用synchronized方法和语句可以获得更广泛的锁定操作
Lock中提供了获得锁和释放锁的方法

1	·void lock():获得锁

1	·void unlock():释放锁

Lock是接口不能直接实例化，这里采用它的实现类ReentrantLock来实例化
ReentrantLock的构造方法
·ReentrantLock():创建一个ReentrantLock的实例

public class day6Lock锁 {
    public static void main(String[] args) {
        day6SellTickets st = new day6SellTickets();

        Thread t1 = new Thread(st,"窗口1");
        Thread t2 = new Thread(st,"窗口2");
        Thread t3 = new Thread(st,"窗口3");

        t1.start();
        t2.start();
        t3.start();
    }
}

import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class day6SellTickets implements Runnable{
    private int tickets = 100;
    private Lock lock = new ReentrantLock();
    @Override
    public void run() {
        while (true){
            try{
                lock.lock();
                if (tickets > 0) {
                    try {
                        Thread.sleep(100);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                    System.out.println(Thread.currentThread().getName() + "正在出售第" + tickets + "张票");
                    tickets--;
                }
            }finally {
                lock.unlock();
            }
        }
    }
}

生产者消费者案例

生产者消费者案例中包含的类:

奶箱类(Box):定义一个成员变量，表示第X瓶奶，提供存储牛奶和获取牛奶的操作

生产者类(Producer):实现Runnable接口，重写run()方法，调用存储牛奶的操作

消费者类(Customer):实现Runnable接口，重写run()方法，调用获取牛奶的操作

测试类(BoxDemo):这里面有main方法，main方法中的代码步骤如下

①创建奶箱对象，这是共享数据区域

②创建生产者对象，把奶箱对象作为构造方法参数传递，因为这个类中要调用存储牛奶的操作

③创建消费者对象，把奶箱对象作为构造方法参数传递，因为这个类中要调用获取牛奶的操作

④创建2个线程对象，分别把生产者和消费者对象作为构造方法参数传递

⑤启动线程

//奶箱类(Box):定义一个成员变量，表示第X瓶奶，提供存储牛奶和获取牛奶的操作

public class Box {
    //定义一个成员变量，表示第X瓶奶
    private int milk;
    //定义一个成员对象，表示奶箱的状态
    private boolean state = false;
    //提供存储牛奶和获取牛奶的操作
    public synchronized void put(int milk){
        //如果有牛奶，等待消费
        if (state){
            try {
                wait();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        //如果没有牛奶，生产牛奶
        this.milk = milk;
        System.out.println("送奶工将第"+this.milk+"瓶奶放入奶箱");

        //生产完毕之后，修改奶箱状态
        state = true;
        //唤醒其他等待的线程
        notifyAll();
    }
    public synchronized void get(){
        //如果没有牛奶，等待生产
        if (!state){
            try {
                wait();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        //如果有牛奶，就消费牛奶
        System.out.println("用户拿到了第"+this.milk+"瓶奶");
        //消费完毕之后，修改奶箱状态
        state = false;
        //唤醒其他等待的线程
        notifyAll();
    }
}

//测试类(BoxDemo):这里面有main方法，main方法中的代码步骤如下4
//  ①创建奶箱对象，这是共享数据区域
//  ②创建生产者对象，把奶箱对象作为构造方法参数传递，因为这个类中要调用存储牛奶的操作
//  ③创建消费者对象，把奶箱对象作为构造方法参数传递，因为这个类中要调用获取牛奶的操作
//  ④创建2个线程对象，分别把生产者和消费者对象作为构造方法参数传递
//  ⑤启动线程


public class BoxDemo {
    public static void main(String[] args) {
        //①创建奶箱对象，这是共享数据区域
        Box b = new Box();
        //②创建生产者对象，把奶箱对象作为构造方法参数传递，因为这个类中要调用存储牛奶的操作
        Producer p = new Producer(b);
        //③创建消费者对象，把奶箱对象作为构造方法参数传递，因为这个类中要调用获取牛奶的操作
        Customer c = new Customer(b);
        //④创建2个线程对象，分别把生产者和消费者对象作为构造方法参数传递
        Thread t1 = new Thread(p);
        Thread t2 = new Thread(c);
        //启动线程
        t1.start();
        t2.start();
    }
}

public class Customer implements Runnable{
    private Box b;
    public Customer(Box b) {
        this.b = b;
    }

    @Override
    public void run() {
        while(true){
            b.get();
        }
    }
}

//生产者类(Producer):实现Runnable接口，重写run()方法，调用存储牛奶的操作

public class Producer implements Runnable {
    private Box b;
    public Producer(Box b) {
        this.b = b;
    }

    @Override
    public void run() {
        for (int i = 1; i <= 30; i++) {
            b.put(i);
        }
    }
}

算法和数据结构

Created2021-12-19Updated2021-12-25

绪论

基本概念和术语

数据结构的两个层次

1.逻辑结构

·描述数据元素之间的逻辑关系

·与数据的存储无关，独立于计算机

·是从具体问题抽象出来的数学模型

2.物理结构(存储结构)

·数据元素及其关系在计算机存储器中的结构(存储方式)

·是数据结构在计算机中的表示

逻辑结构与存储结构的关系

·存储结构是逻辑关系的映像与元素本身的映像

·逻辑结构是数据结构的抽象，存储结构是数据结构的实现

·两者综合起来建立了数据元素之间的结构关系

逻辑结构的种类

划分方法一

（1）线性结构

有且仅有一个开始和一个终端结点，并且所有结点都最多只有一个直接前驱和一个直接后继

例如：线性表、栈、队列、串

（2）非线性结构

一个结点可能有多个直接前驱和直接后继

例如：树、图

划分方法二

（1）集合结构:

结构中的数据元素之间除了同属于一个集合的关系外，无任何其他关系

（2）线性结构：

结构中的数据元素之间存在着一对一的线性关系

（3）树形结构:

结构中的数据元素之间存在着一对多的层次关系

（4）图状结构或网状结构

结构中的数据元素之间存在着多对多的任意关系

存储结构的种类

顺序存储结构：

用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示

C语言中用数组来实现顺序存储机构

链式存储结构：

用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示

C语言中用指针来实现链式存储结构

索引存储结构：

在存储结点信息的同时，还建立附加的索引表

索引表中的每一项称为一个索引项

索引项的一般形式是:（关键字，地址）

关键字是能唯一标识一个结点的哪些数据项

若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引（Dense Index）。若一组结点在索引表中只对应一个索引项，则该索引表称之为稀疏索引（Sparse Index）.

散列存储结构：

根据结点的关键字直接计算出该结点的存储地址

数据类型和抽象数据类型

在使用高级程序设计语言编写程序时，必须对程序中出现的每个变量，常量或表达式，明确说明它们所属的数据类型

例如，C语言中：

提供int、char、float、double、等基本数据类型

数组、结构、共用体、枚举等构造数据类型

还有指针，空（void）类型

用户也可以用typedef自己定义数据类型

一些最基本数据结构可以用数据类型来实现，如数组、字符串等

而另一些常用的数据结构，如栈、队列、树、图等，不能直接用数据类型来表示

抽象数据类型

是指一个数学模型以及定义在此数学模型上的一组操作

1.由用户定义，从问题抽象出数据模型（逻辑结构）

2.还包括定义在数据模型上的一组抽象运算（相关操作）

3.不考虑计算机内的具体存储与运算的具体实现算法

抽象数据类型的形式定义

抽象数据类型可用(D,S,P)三元组表示。

其中：

D是数据对象

S是D上的关系集合

P是对D的基本操作集

一个抽象数据类型的定义格式：

ADT 抽象数据类型名{

数据对象:<数据对象的定义>

数据关系:<数据关系的定义>

基本操作:<基本操作的定义>

}ADT 抽象数据类型名

其中：数据对象、数据关系的定义用伪代码描述

基本操作的定义格式为:

- 基本操作名（参数表）
- 初始条件：<初始条件描述>
- 操作结果：<操作结果描述>

基本操作定义格式说明：

参数表：赋值参数只为操作提供输入值

引用参数以&打头，除可提供输入值外，还将返回操作结果

初始条件：描述操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。若初始条件为空，则省略之

操作结果：说明操作正常完成之后，数据结构的变化状况和应返回的结果

抽象数据类型定义举例:Circle的定义

ADT 抽象数据类型名{

Data

数据对象的定义

数据元素之间逻辑关系的定义

Operation

操作1

初始条件

操作结果描述

操作2

…

操作n

…

}

ADT Circle{

数据对象: D = {r,x,y|r,x,y均为实数}

数据关系: R = {<r,x,y>|r是半径,<x,y>是圆心坐标}

基本操作:

Circle(&C,r,x,y)

操作结构:构造一个圆

double Area©

初始条件:圆已存在

操作结构:计算面积

double Circumstance©

初始条件:圆已存在

操作结果:计算周长

}

抽象数据类型的表示和实现

ADT 抽象数据类型名{

Data

数据对象的定义

数据元素之间逻辑关系的定义

Operation

操作1

初始条件

操作结果描述

操作2

…

操作n

…

}

C语言实现抽象数据类型

用已有的数据类型定义描述它的存储结构

用函数定义描述它的操作

就可以在程序中使用

例如：抽象数据类型“复数”的实现

typedef struct{
	float realpart;         /*实部*/
    float imagpart;          /*虚部*/
}Complex

void assign(Complex *A,float real,float imag){    
	A->realpart = real;			/*实部赋值*/
    A->imagepart = imag;		/*虚部赋值*/	
}							  /*End of assign()*/

void add(Complex *c,Complex A,Complex B){        /*c = A + B */
    c->realpart = A.realpart + B.realpart;		/*实部相加*/
    c->imagpart = A.imagpart + B.imagpart;		/*虚部相加*/
} 										     /*End of assign()*/

注意：Complex是我们定义的一个结构体类型

带*：指针变量，它是指向Complex类型的指针

不带*：Complex类型的普通变量

#include <stdlib.h>
typedef struct{
    float realpart;         /*实部*/
    float imagpart;          /*虚部*/
}Complex;
void assign(Complex *A,float real,float imag){
    A->realpart = real;			/*实部赋值*/
    A->imagpart = imag;		/*虚部赋值*/
}
void add(Complex *c,Complex A,Complex B){        /*c = A + B */
    c->realpart = A.realpart + B.realpart;		/*实部相加*/
    c->imagpart = A.imagpart + B.imagpart;		/*虚部相加*/
}
int main(void){
    Complex z1,z2,z3,z4,z;
    float RealPart,ImagePart;
    assign(&z1,8.0,6.0);
    assign(&z2,4.0,3.0);
    add(&z3,z1,z2);
    multiply(z1,z2,z4);
    if(divide(&z,z4,z3)){
        GetReal(&z,RealPart);
        GetImag(&z,ImagePart);
    }
    return 0;
}

以上代码由类C语言实现，仍有不全之处，读者自行补充

算法和算法分析

算法特性:一个算法必须具备以下五个重要特性

有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在又穷时间内完成
确定性：算法中的每一条指令必须有确切的含义，没有二义性，在任何条件下，只有唯一的一条执行路径，即对于相同的输入只能得到相同的输出。
可行性：算法是可执行的，算法描述的操作可以通过已经实现的基本操作执行有限次来实现
输入：一个算法有零个或多个输入
输出：一个算法有一个或多个输出

算法设计的要求

正确性
可读性
健壮性
高效性

算法效率以下两个方面来考虑：

1.时间效率：指的是算法所消耗的时间

2.空间效率：指的是算法执行的过程中所消耗的存储空间

时间效率和空间效率有时候是矛盾的

算法时间效率的度量

算法时间效率可以用一句该算法编制的程序在计算机上执行所消耗的时间来度量

两种度量方法

事后统计：

将算法实现后，测算其时间和空间开销

事前统计：

对算法所消耗资源的一种估算方法

事前分析方法

一个算法的运行时间是指一个算法在计算机上运行所耗费的时间大致可以等于计算机执行一种简单的操作(如赋值、比较、移动等)所需的时间与算法中进行的简单操作次数乘积

算法运行时间 = 一个简单操作所需的时间 × 简单操作次数

也即算法中每条语句的执行时间之和

算法运行时间 = ∑每条语句的执行次数 × 该语句执行一次所需的时间

每条语句执行一次所需的时间，一般是由机器而异的。取决于机器的指令性能、速度以及编译的代码质量。是由机器本身软硬件环境决定的，它与算法无关。

所以,我们可假设执行每条语句所需的时间均为单位时间。此时对算法的运行时间的讨论就可转化为讨论该算法中所有语句的执行次数，即频度之和了。

例如：两个n×n矩阵相乘的算法可描述为：

for(i = 1;i <= n; i++){				//n+1次
    for(j = 1; j <= n; j++){		 //n(n+1)次
        c[i][j] = 0;			     //n*n次	
        for(k = 0; k < n; k++){		  //n*n*(n+1)次
            c[i][j] = c[i][j] + a[i][k]*b[k][j];//n*n*n4次
        }
    }
}

我们把算法所消耗的时间定义为该算法中每条语句的频度之和，则上述算法的时间消耗T(n)为：

T(n) = 2n³+3n²+2n+1

为了便于比较不同算法的时间效率，我们仅比较它们的数量级

例如：两个不同的算法，时间消耗分别是：

T1(n) = 10n² 与 T2(n) = 5n³

若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则成f(n)是T(n)的同数量级函数。记作T(n) = O(f(n))，称 O(f(n))为算法的渐进时间复杂度(O是数量级的符号)，简称时间复杂度

算法时间复杂度定义

算法中基本语句重复执行的次数是问题规模n的某个函数f(n),算法的时间量度记作：T(n) = O(f(n))

基本语句:

算法中重复执行次数和算法的执行时间成正比的语句

对算法运行时间的贡献最大

执行次数最多

n越大算法的执行时间越长

排序：n为记录数

矩阵：n为矩阵的阶数

多项式：n为多项式的项数

集合：n为元素个数

树：n为树的结点个数

图：n为图的定点数或边数

定理1.1

若f(n) = am n^m + am-1 n^m-1 + … + a1 n + a0是m次多项式

则T(n) = O(n^m)

忽略所有低次幂项和最高次幂系数，体现出增长率的含义

分析算法时间复杂度的基本方法

1.找出语句频度最大的那条语句作为基本语句

2计算基本语句的频度得到问题规模n的某个函数f(n)

3.取其数量级用符号"O"表示

例1:

x = 0; y =0;
for (int k = 0;k < n; k++)
    x ++;
for (int i = 0;i < n;i++)
    for(int j = 0;j < n;j++)
        y ++;

时间复杂度是由嵌套最深语句的频度决定的

例2：

for(i = 1ji <= n;i++)
    for(j = 1;j <= i;j ++)
        for(k = 1;k <=j; k ++)
            x = x + 1;

语句频度=\sum_{i=1}^n\sum_{j=1}^i\sum_{k=1}^j1=\sum_{i=1}^n\sum_{j=1}^ij=\sum_{i=1}^n\frac{i(i+1)}{2}

例3:

1	i = 1；①while(i <= n) ② i = i * 2;

关键是要找出来执行次数x与n的关系，并形成n的函数

若循环执行1次：i = 1*2=2,\\ 若循环执行2次：i = 2*2=2^{2},\\ 若循环执行3次：i = 2*2*2=2^{3},\\ 若循环执行x次：i = 2^{x}\\ 设语句②执行次数为x次，由循环条件\\ i \leq n\\ ∴ 2^{x} \leq n\\ ∴ x \leq {log_2{n}}\\ 2^{f(n)} \leq n\\ 即 f(n) \leq {log_2{n}}\\ 取最大值 f(n) = {log_2{n}}\\ 所以该程序段的时间复杂度T(n) = O({log_2{n}})

请注意：有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同

例：顺序查找，在数组a[i]中查找值等于e的元素，返回其所在位置

1
2
3

for(i = 0;i < n;i ++)
    if(a[i] == e) return i+1;
return 0;

最好情况：1次

最坏情况：n

平均时间复杂度：O(n)

最坏时间复杂度：指在最坏情况下，算法的时间复杂度

平均时间复杂度：指在所有可能输入实例在等概率出现的情况下，算法的期望运行时间

最好时间复杂度：指在最好情况下，算法的时间复杂度

一般总是考虑在最坏情况下的时间复杂度，以保证算法的运行时间不会比它更长

对于复杂的算法，可以将它分成几个容易估算的部分，然后利用大O加法法则和乘法法则，计算算法的时间复杂度：

a）加法规则

T(n) = T1(n) + T2(n) = O(f(n)) + O(g(n)) = O(max(f(n),g(n)))

b）乘法规则

T(n) = T1(n) × T2(n) = O(f(n)) × O(g(n)) = O(f(n)×g(n))

算法时间效率的比较

当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊

时间复杂度T(n)按数量级递增顺序为：

常数阶 O(1)\\ 对数阶 O({log_2{n}})\\ 线性阶 O(n)\\ 线性对数阶 O(n {log_2{n}})\\ 平方阶 O(n^2)\\ .........\\ 立方阶 O(n^k)\\ 指数阶 O(2^n)

渐进空间复杂度

空间复杂度：算法所需存储空间的度量

记作 S(n) = O(f(n))

其中n为问题的规模

算法要占据的空间

算法本身要占据的空间，输入/输出，指令，常数，变量等

算法要是用的辅助空间

例：将一维数组a中的n个数逆序存放到原数组中

【算法1】

1	for( i = 0; i < n/2; i++){ t = a[i]; a[i] = a[n-i-1]; a[n-i-1] = t;}

S(n) = O(1)

【算法2】

for(i = 0;i < n;i ++)
    b[i] = a[n-i-1]
for(i = 0; i < n;i ++)
    a[i] = b[i]

S(n) = O(n)

线性表

线性表的定义和特点

线性表是具有相同特性的数据元素的一个有限序列

线性表（Linear List）：

由n(n>=0)个数据元素(结点)a1,a2,…an组成的有限序列

其中数据元素的个数n定义为表的长度
当n=0时称为空表
将非空的线性表(n>0)记作：（a1,a2,an)
这里的数据元素ai(1<=i<=n)只是一个抽象的符号，其具体含义在不同的情况下可以不同

线性表的例子

例1：分析26个英文字母组成的英文表

(A,B,C,D,…,Z)

数据元素都是字母；元素关系是线性

例2：分析学生情况登记表

学号姓名性别年龄班级

498623 nww 男 26 9

线性表的逻辑特征

从以上例子可看出线性表的逻辑特征是：

在非空的线性表，有且仅有一个开始结点a1,它没有直接前驱，而有且仅有一个直接后继a2;

有且仅有一个终端节点an，它没有直接后继，而有且仅有一个直接前驱an-1；

其他的内部节点==结点ai(2<=i<=n-1)都有且仅有一个直接前驱ai-1和一个直接后继ai+1

线性表是一种典型的线性结构

案例引入

案例【2.1】一元多项式的运算：实现两个多项式加、减、乘运算

Pn(x) = p0 + p1x + p2x^2 + … + pnx^n

线性表P = (p0,p1,p2…pn)

（每一项的指数i隐含在其系数pi的序号中）

例如P(x) = 10 +5x - 4x^2 + 3x^3 + 2x^4 用数组来表示

指数（下标i）	0	1	2	3	4
系数p[i]	10	5	-4	3	2

稀疏多项式

S(x) = 1 + 3x^10000 + 2x^20000

会造成存储空间的很大浪费,怎么办？

0	10000	20000
1	3	2

案例【2.2】稀疏多项式的运算

多项式非零项的数组表示

(a) A(x) = 7 + 3x + 9x^8 + 5x^17

下标i	0	1	2	3
系数a[i]	7	3	9	5
指数	0	1	8	17

(b) B(x) = 8x + 22x^7 - 9x^8

下标i	0	1	2
系数b[i]	8	22	-9
指数	1	7	8

Pn(x) = p1x^e1 + p2x^e2 + … + pmx^em

线性表 P = （(p1,e1),(p2,e2),…(pm,em)）

线性表 A = ((7,0),(3,1),(9,8,),(5,17))

线性表 B = ((8,1),(22,7),(-9,8))

创建一个新数组c
分别从头遍历比较a和b的每一项

指数相同：对应系数相加，若其和不为0，则在c中增加一个新项

指数不相同：则将指数较小的项复制到c中
一个多项式已遍历完毕时，将另一个剩余项依次复制到c中即可

顺序存储结构存在问题

存储空间分配不灵活
运算的空间复杂度高

链式存储结构

线性表的类型定义

基本操作：

InitList(&L)

操作结果：构造一个空的线性表L

DestoryList(&L)

初始条件：线性表已经存在
操作结构：销毁线性表L

ClearList(&L)

初始条件：线性表L已经存在
操作结果：将线性表L重置为空表

ListEmpty(L)

初始条件：线性表L已经存在
操作结果：若线性表L为空表，则返回TRUE；否则返回FALSE4

ListLength(L)

初始条件：线性表L已经存在
操作结果：返回线性表L中的数据元素个数

GetElem(L,i,&e)

初始条件：线性表L已经存在，1<=i<=ListLength(L)
操作结果：用e返回线性表L中第i个数据元素的值

LocateElem(L,e,compare())

初始条件：线性表L已经存在，compare()是数据元素判定函数
操作结果：返回L中第1个与e满足compare()的数据元素的位序。若这样的数据元素不存在则返回值为0

PriorElem(L.cur_e,&pre_e)

初始条件：线性表L已经存在
操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败；pre_e无意义

NextElem(L,cur_e,&next_e)

初始条件：线性表L已经存在
操作结果：若cur_e是L的数据元素，且不是第最后个，则用next_e返回它的后继，否则操作失败，next_e无意义

ListInsert(&L,i,e)

初始条件：线性表L已经存在，1<=i<=ListLengtgh(L) + 1
操作结果：在L的第i个位置之前插入新的数据元素e，L的长度加一

ListDelete(&L,i,&e)

初始条件：线性表L已经存在，1<=i<=ListDelete(&L,i,&e)
操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减一

ListTraverse(&L,visited())

初始条件：线性表L已经存在
操作结果：依次对线性表中的每个元素调用visited()

线性表的顺序表示和实现

用一维数组表示顺序表

用一变量表示顺序表的长度属性

#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量
typedef int Element;
typedef struct{
    ElemType elem[LIST_INIT_SIZE];
    int length; //当前长度
}SqList;

多项式的顺序存储结构类型定义

Pn(x) = p1x^e1 + p2x^e2 + … +pmx^em

#define MAXSIZE 1000    //多项式可能达到的最大长度
typedef struct{		   //多项式非零项的定义
    float p;    	   //系数
    int e;			  //指数
}Polynomial;
typedef struct{
    Polynomial *elem;  //存储空间的基地址
    int length;		  //多项式当前项的个数
}SqList;		      //多项式的顺序结构类型为SqList

图书表的顺序存储结构类型定义

#define MAXSIZE 10000  //图书表可能达到的最大长度
typedef struct{		  //图书信息定义
    char no[20];	  //图书ISBN
    char name[50];	  //图书名字
    float price;	  //图书价格
}Book;
typedef struct{
    Book *elem;		  //存储空间的基地址
    int length;		  //图书表中当前图书个数
}SqList;			 //图书表的顺序存储结构类型为SqList

补充：元素类型说明

顺序表类型定义:

typedef struct{
    //typedef char ElemType;
    ElemType data[];//ElemType 可以是任意类型，所以也可以是自定义的结构体类型，即结构体数组
    int length;
}SqList; //顺序表类型

补充：数组静态分配

typedef struct{
    ElemType data[MaxSize];
    int length;
}SqList; //顺序表类型

补充：数组动态分配

typedef struct{
    ElemType *data;
    int length;
}SqList; //顺序表类型
//动态分配内存
SqList L;
L.data = (ElemType*)malloc(sizeof(ElemType)*MaxSize);

补充：C语言的内存动态分配

malloc(m)函数，开辟m字节长度地址空间，并返回这段空间的首地址
sizeof(x)运算，计算变量x的长度
free§函数，释放指针p所指变量的存储空间，即彻底删除一个变量

需要加载头文件:<stdlib.h >

顺序表基本操作实现

线性表的基本操作

InitList(&L) //初始化操作，建立一个空的线性表L
Destory(&L) //销毁已存在的线性表L
ClearList(&L) //将线性表清空
**ListInsert(&L,i,e) ** //在线性表L中的第i个位置插入新元素e
ListDelete(&L,i,&e) //删除线性表L中的第i个位置元素，用e返回
IsEmpty(L) //若线性表为空，则返回True，否则False
ListLength(L) //返回线性表L的元素个数
LocateElem(L,e) //L中查找与给定值e相等的元素，若成功返回该元素在表中的序号，否则返回0
GetElem(L,i,&e) //将线性表L的第i个位置元素返回给e

补充：操作算法中用到的预定义常量和类型

//函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
//status 是函数的类型，其值是函数结果状态代码
typedef int Status;
typedef char ElemType;

顺序表基本操作的实现

【算法2.1】线性表L的初始化(参数用引用)

Status InitList_Sq(SqList &L){ //构造一个空的顺序表L
    L.elem = (ElemType*)malloc(sizeof(ElemType)*MaxSize); //为顺序表分配空间
    if(!L.elem) exit(OVERFLOW); //存储分配失败
    L.length = 0; //空表长度为0
    return OK;
}

【算法2.2】销毁线性表

1
2
3

void Destory(SqList &L){
    if(L.elem) free(L.elem); //释放存储空间
}

【算法2.3】清空线性表

1	void ClearList(SqList &L){ L.length = 0; //将线性表的长度置为0}

【算法2.4】求线性表的长度

1	int GetLength(SqList L){ return L.length;}

【算法2.5】判断线性表是否为空

1	int IsEmpty(SqList L){ if (L.length == 0) return 1; else return 0;}

【算法2.6】顺序表的取值(根据位置i获取相应位置数据元素的内容)

1	int GetElem(SqList L,int i,ElemType &e){ if (i<1\|\|i>L.length) return ERROR; //判断i值是否合理，若不合理，则返回ERROR e = L.elem[i-1]; //第i-1单元存储着第i个数据 return OK;}

顺序表上的查找操作

按值查找：

例如：在图书表中，按照给定书号进行查找，确定是否存在该图书

如果存在：输出是第几个元素

如果不存在：输出0

【算法2.7】顺序表的查找

在线性表L中查找与指定值e相同的数据元素的位置
从表的一端开始，逐个进行记录的关键字和给定值的比较。找到，返回该元素的位置序号，未找到，返回0

int LocateElem(SqList L,ElemType e){    //在线性表L中查找值为e的数据元素，返回其序号(是第几个元素)    for(i = 0; i < L.length ;i ++){        if(L.elem[i] == e){            return i+1;	//查找成功，返回序号        }        return 0;// 查找失败，返回0    }}

int LocateElem(SqList L,ElemType e){
     //在线性表L中查找值为e的数据元素，返回其序号(是第几个元素)
    i = 0；
    while(i<L.length&&L.elem[i]!=e) i++;
    if(i<L.length) return i+1; //查找成功，返回序号
    return 0;// 查找失败，返回0
}

顺序表的查找算法分析：

因为查找算法的基本操作为：将记录的关键字同给定值进行比较

基本操作：L.elem[i] == e

平均查找长度ASL(Average Search Length):

为确定记录在表中位置，需要与给定值进行比较的关键字的个数的期望值叫做查找算法的平均查找长度

ASL = \sum_{i = 1}^nP_iC_i

【算法2.8】顺序表的插入

算法思想：

判断插入位置i是否合法
判断顺序表的存储空间是否已满，若已满返回ERROR
将第n至第i位的元素依次向后移动一个位置，空出第i个位置
将要插入的新元素e放入第i个位置

Status ListInsert_Sq(SqList &L,int i,ElemType e){
    ① if(i<1||i>L.length+1) return ERROR;//i值不合法
    ② if(L.length == MAXSIZE) return ERROR;//当前存储空间已满
    ③ for(j = L.length-1;j>=i-1;j--){
      	L.elem[j+1] = L.elem[j];//插入位置及之后的元素后移
    }
    ④ L.elem[i-1] = e;//将新元素e放入第i个位置
    ⑤ L.length ++;//表长加一
}

【算法2.9】顺序表的删除

算法思想：

判断删除位置i是否合法（合法值为1<=i<=n）
将欲删除的元素保留在e中
将第i+1至第n位的元素依次向前移动一个位置
表长减一，删除成功返回OK

Status ListDelete_Sq(SqList &L,int i){
    ① if(i<1||i>L.length) return ERROR;//i值不合法
    ② for(j = i;j<=L.length-1;j++){
        L.elem[j-1] = L.elem[j];//被删除元素之后的元素前移
    }
    ④ L.length--;//表长减一
    return OK;
}

小结

顺序表(线性表的顺序存储结构)的特点

（1）利用数据元素的存储位置表示线性表中的相邻数据元素之间的前后关系，即线性表得逻辑结构与存储结构一致

（2）在访问线性表时，可以快速地计算出任何一个数据元素的存储地址。因此可以粗略地认为，访问每个元素所花时间相等

这种存取元素的方法被称为随机存取法

线性表的基本操作

InitList(&L) //初始化操作，建立一个空的线性表L
Destory(&L) //销毁已存在的线性表L
ClearList(&L) //将线性表清空
**ListInsert(&L,i,e) ** //在线性表L中的第i个位置插入新元素e
ListDelete(&L,i,&e) //删除线性表L中的第i个位置元素，用e返回
IsEmpty(L) //若线性表为空，则返回True，否则False
ListLength(L) //返回线性表L的元素个数
LocateElem(L,e) //L中查找与给定值e相等的元素，若成功返回该元素在表中的序号，否则返回0
GetElem(L,i,&e) //将线性表L的第i个位置元素返回给e

优点

存储密度大（结点本身所占存储量/结点结构所占存储量）
可以随机存取表中任一元素

缺点

在插入、删除某一元素时，需要移动大量元素
浪费存储空间
属于静态存储形式，数据元素的个数不能自由扩充

线性表的链式表示和实现

链式存储结构

结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻

线性表的链式表示又称为非顺序映像或链式映像

用一组物理位置任意的存储单元来存放线性表的数据元素
这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中任意位置上的
链表中元素的逻辑次序和物理次序不一定相同

例

线性表（赵，钱，孙，李，周，吴，郑，王）

顺序表

存储地址	存储状态
0031	赵
0033	钱
0035	孙
0037	李
0039	周
0041	吴
0043	郑
0045	王

链表

存储地址	数据域	指针域
0001	李	0043
0007	钱	0013
0013	孙	0001
0019	王	NULL
0025	吴	0037
0031	赵	0007
0037	郑	0019
0043	周	0025

与链式存储有关的术语

1.结点：数据元素的存储映像。由数据域和指针域两部分组成

2.链表：n个结点由指针链组成一个链表

它是线性表的链式存储映像，称为线性表的链式存储结构

3.单链表、双链表、循环链表：

结点只有一个指针域的链表，称为单链表或线性链表

结点有两个指针域的链表，称为双链表

首尾相接的链表称为循环链表

4.头指针、头结点和首元结点：

头指针：是指向链表中第一个结点的指针

首元结点：是指向链表中存储第一个数据元素a1的结点

头结点：是在链表的首元结点之前附设的一个结点

如何表示空表？

无头结点时，头指针为空时表示空表
有头结点时，当头结点的指针域为空时表示空表

在链表中设置头结点有什么好处？

1 便于首元结点的处理

首元结点的地址保存在头结点的指针域中，所以在链表的第一个位置上的操作和其他位置一致，无需进行特殊处理

2 便于空表和非空表的统一处理

无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了

头结点的数据域内装的是什么？

头结点的数据域可以为空，也可存放表长度等附加信息，但此结点不能计入链表长度值

链表的特点

结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻
访问时只能通过头指针进入链表，并通过每个结点的指针域依次向后顺序扫描其余结点，所以寻找第一个结点和最后一个结点所花费时间不等。这种存取元素的方法被称为顺序存取法

单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名，若头指针名是L，则把链表称为表L

单链表的存储结构：

typedef struct Lnode{//声明结点的类型和指向结点的指针类型
    ElemType data;//结点的数据域
    struct Lnode *next;//结点的指针域
}Lnode,*LinkList;//LinkList为指向结构体Lnode的指针类型

**定义一个链表L：**LinkList L;

**定义结点指针p：**LNode *p；LinkList p；

例如：存储学生学号、姓名、成绩的单链表结点类型定义如下：

typedef struct student{
    char num[8];//数据域
    char name[8];//数据域
    int score;//数据域
    struct student *next;//指针域
}Lnode,*LinkList;

单链表基本操作的实现

单链表的初始化

即构造一个空表

【算法步骤】

生成新结点作头结点，用头指针L指向头结点
将头结点的指针域置空

【算法描述】

typedef struct Lnode{//声明结点的类型和指向结点的指针类型
    ElemType data;//结点的数据域
    struct Lnode *next;//结点的指针域
}LNode,*LinkList;//LinkList为指向结构体Lnode的指针类型

Status InitList L(LinkList &L){
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
}

【补充算法1】判断链表是否为空

空表：链表中无元素，称为空链表(头指针和头结点仍然在)

【算法思路】判断头结点指针域是否为空

int ListEmpty(LinkList L){//若L为空表，则返回1，否则返回0
    if(L->next)//非空
        return 0;
    else
        return 1;
}

【补充算法2】单链表的销毁：链表销毁后不存在

【算法思路】从头指针开始，依次释放所有结点

Status DestoryList L(LinkList &L){//销毁单链表L
    Lnode *p;//或LinkList p;
	 while(L){
        p = L;
        L = L->next;
        free(p);
    }
    return OK;
}

【补充算法3】清空链表

链表仍存在，但链表中无元素，成为空链表(头指针和头结点仍然在)

【算法思路】依次释放所有结点，并将头结点指针域设置为空

Status ClearList(LinkList &L){//将L重置为空表
    Lnode *p,*q;//或LinkList p,q;
    p = L->next;
    while(p){//没到表尾
        q = p->next;
        free(p);
        p = q;
    }
    L->next = NULL; //头结点指针域为空
    return OK;
}

【补充算法4】求单链表的表长

【算法思路】从首元结点开始，依次计数所有结点

int ListLength_L(LinkList L){//返回L中数据元素个数
    LinkList p;
    p = L->next;//p指向第一个结点
    i = 0;
    while(p){//遍历单链表，统计结点数
        i++;
        p = p->next;
    }
    return i;
}

【算法2.7】取值——取单链表中第i个元素的内容

【算法思路】从链表的头指针出发，顺着链域next逐个结点往下搜索，直到搜索到底i个结点为止。因此，链表不是随机存取结构

1.从第1个结点(L->next)顺链扫描，用指针p指向当前扫描到的结点，p初值p=L->next

2.j做计数器，累计当前扫描过得结点数，j初值为1

3.当p指向扫描到的下一结点时，计数器j加1

4.当j==i时，p所指的结点就是要找的第i个结点

Status GetElem_L(LinkList L,int i,ElemType &e){//获取线性表L中的某个数据元素的内容，通过变量e返回
    p = L->next; j =1;//初始化
    while(p&&j<i){//向后扫描，直到p指向第i个元素或p为空
    	p = p->next; ++j;
    }
    if(!p||j>i) return ERROR; //第i个元素不存在
    e = p->data; //取第i个元素
    return OK;
}

【算法2.8】按值查找——根据指定数据获取该数据所在的位置(地址)

【算法思路】

1.从第一个结点起，依次和相比较

2.如果找到一个其值与e相等的数据元素，则返回其在链表中的“位置”或地址；

3.如果查遍整个链表都没找到其值和e相等的元素，则返回0或“NULL“

Lnode *LocateElem_L(LinkList L,ElemType e){
    //在线性表L中查找值为e的数据元素
    //找到，则返回L中值为e的数据元素的地址，查找失败返回NULL
    p = L->next;
    while(p&&p->data!=e){
        p = p->next;
    }
    return p;
}

【算法2.8变化】按值查找——根据指定数据获取该数据位置序号

//在线性表L中查找值为e的数据元素的位置序号
int LocateElem_L(LinkList L,ElemType e){
    //返回L中值为e的数据元素的位置序号查找失败返回0
    p = L->next; j = 1;
    while(p&&p->data!=e){
        p = p->next;
        j ++;
    }
    if(p) return j;
    else return 0;
}

【算法2.9】插入——在第i个结点前插入值为e的新结点

【算法思路】

1.首先找到a_{i-1}的存储位置p\\ 2.生成一个数据域为e的新结点s\\ 3.插入新结点:\\①新结点的指针域指向结点a_i\\ ②结点a_{i-1}的指针域指向新结点\\ s->next = p->next\\ p->next = s

//在L中第i个元素之前插入数据元素e
Status ListInsert(LinkList &L.int i,ElemType e){
    p = L;j = 0;
    while(p&&j<i-1){
        p = p->next;//寻找第i-1个结点，p指向i-1结点
        ++j;
    }
    if(!p||j>i-1) return ERROR;//i大于表长+1或者小于1，插入位置非法
    s = (LinkList)malloc(sizeof(LNode)); s->data = e;//生成新结点s，将结点s的数据域置为e
    s->next = p->next;//将结点s插入L中
    p->next = s;
    return OK;
}

【算法2.10】删除——删除第i个结点

【算法思路】

1.首先找到a_{i-1}的存储位置p，保存要删除的a_i的值\\ 2.令p->next指向a_{i+1}\\ p->next = p->next->next\\ 3.释放结点a_i的空间

//将线性表L中的第i个元素删除
Status ListDelete_L(LinkList &L,int i,ElemType &e){
    p = L; j = 0;
    while(p->next&&j<i-1){
        //寻找第i个结点，并令p指向其前驱
        p = p->next;
        ++ j;
    }
    if(!(p->next)||j>i-1) return ERROR;//删除位置不合理
    q = q->next;//临时保存被删结点的地址以备释放
    p->next = q->next;//改变删除结点前驱结点的指针域
    e = q->data;//保存删除结点的数据域
    free(q);//释放删除结点的空间  
    return Ok;
}

单链表的查找、插入、删除算法时间效率分析

1.查找：

因线性表只能顺序存取，即查找时要从头指针找起，查找的时间复杂度为O(n)

2.插入和删除:

因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度O(1)

但是，如果要在单链表中进行前插或者删除操作，由于要从头查找前驱结点，所耗时间复杂度为O(n)

【算法2.11】建立单链表：头插法——元素插入在链表头部，也叫前插法

【算法思路】

1.从一个空表开始，重复读入数据

2.生成新结点，将读入数据存放到新结点的数据域中

3.从最后一个结点开始，依次将各结点插入到链表的前端

void CreatList_H(LinkList &L,int n){
    L = (LNode*)malloc(sizeof(LNode));
    L->next = NULL;//先建立一个带头结点的单链表
    for(i = n;i > 0;i --){
        p = (LNode*)malloc(sizeof(LNode));//生成新结点
        scanf(&p->data);//输入元素值
        p->next = L->next;//插入到表头
        L->next = p;
    }
}

【算法2.12】建立单链表：尾插法——元素插入在链表尾部，也叫后插法

【算法思路】

1.从一个空表L开始，将新结点逐个插入到链表的尾部，尾指针r指向链表的尾结点

2.初始时，r同L均指向头结点。每读入一个数据元素则申请一个新结点，将新结点插入到尾结点后，r指向新结点

//正位序输入n个元素的值，建立带表头结点的单链表L
void CreatList_R(LinkList &L,int n){
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    r = L;//尾指针r指向头结点
    for(int i = 0 ; i < n; i ++){
        p = (LinkList)malloc(sizeof(LNode)); // 生成新结点
        scanf(&p->data);//输入元素值
        p->next = NULL;
        r->next = p; //插入到表尾
        r = p; //r指向新的表尾结点
    }
}

循环链表

是一种头尾相接的链表(即：表中最后一个结点的指针域指向头结点，整个链表形成一个环)

优点：从表中任一结点出发均可找到表中其他结点

注意：

由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或p->next是否为空，而是判断它们是否等于头指针

循环条件：

单链表

1 2	p != NULL p->next != NULL

单循环链表

1 2	p != L p->next != L

注意：表的操作常常是在表的首尾位置上进行

头指针表示单循环列表

找a_1的时间复杂度：O(1)\\ 找a_n的时间复杂度：O(n)

不方便

尾指针表示单循环链表

a_1的存储位置是: R->next->next\\ a_n的存储位置是: R\\ 时间复杂度都是O(1)

带尾指针的循环链表的合并(将Tb合并在Ta之后)

分析有哪些操作？

p存表头结点
Tb表头连接到Ta表尾
释放Tb表头结点
修改指针

p = Ta->next
Ta->next = Tb->next->next
free(Tb->next)
Tb->next = p

LinkList Connect(LinkList Ta,LinkList Tb){
    //假设Ta,Tb都是非空的单循环链表
    p = Ta->next; //①p存表头结点
    Ta->next = Tb->next->next;//②Tb表头连接Ta表尾
    free(Tb->next);//③释放Tb表头结点
    Tb->next = p;//④修改指针
    return Tb;
}

双向链表

为什么要讨论双向链表:

单链表：

单链表的结点-有指示后继的指针域-找后继结点方便

即：查找某结点的后继结点的执行时间为O(1)

无指示前驱的指针域-找前驱结点难：从表头出发查找

即：查找某结点的前驱结点的执行时间为O(n)

在单链表的每个结点里再增加一个指向其直接前驱的指针域prior。这样链表中就形成了有两个方向不同的链，故称为双向链表

双向链表的结构可以定义如下：

typedef struct DuLNode{
    Elemtype data;
    struct *prior,*next;
}DuLNode,*DuLinkList;

双向循环链表

和单链的循环表类似，双向链表也可以有循环链表

让头结点的前驱指针指向链表的最后一个结点
让最后一个结点的后继指针指向头结点

双向链表的对称性（设指针p指向某一个结点）：

p->prior->next = p = p->next->prior

在双向链表中有些操作(如：ListLength、GetElem等)，因仅涉及一个方向的指针，故它们的算法与线性链表的相同。但在插入、删除时在，则需同时修改两个方向上的指针，两者操作的时间复杂度均为O(n)

【算法2.13】双向链表的插入

s->prior = p->prior
p->prior->next = s
s->next = p
p->prior = s

void ListInsert_DuL(DuLinkList &L,int i,ElemType e){
    //在带头结点的双向循环链表L中第i个位置之前插入元素e
    if(!(p=GetElemP_DuL(L,i))) return ERRPR;
    s = (DuLinkList)malloc(sizeof(DuLNode));
    s->data = e;
    s->prior = p->prior;
    p->prior->next = s;
    s->next = p;
    p->prior = s;
    return OK;
}

【算法2.14】双向链表的删除

p->prior->next = p->next
p->next->prior = p->prior

void ListDelete_DuL(DuLink &L,int i,ElemType e){
    //删除带头结点的双向链表L的第i个元素，并用e返回
    if(!(p = GetElemP_DuL(L,i))) return  ERROR;
    e = p->data;
    p->prior->next = p->next;
    p->next->prior = p->prior;
    free(p);
    return OK;
}

单链表、循环链表、和双向链表时间效率比较

	查找表头结点(首元结点)	查找表尾结点	查找结点*p的前驱结点
带头结点的单链表L	L->next 时间复杂度O(1)	从L->next 依次向后遍历时间复杂度O(n)	通过p->next无法找到其前驱
带头结点仅设头指针的循环单链表	L->next 时间复杂度O(1)	从L->next 依次向后遍历时间复杂度O(n)	通过p->next可以找到前驱时间复杂度O(n)
带头结点仅设尾指针R的循环单链表	R->next 时间复杂度O(1)	R 时间复杂度O(1)	通过p->next可以找到前驱时间复杂度O(n)
带头结点的双向循环链表L	L->next 时间复杂度O(1)	L-prior 时间复杂度O(1)	p->prior 时间复杂度O(1)

顺序表和链表的比较

链式存储结构优点：

结点空间可以动态申请和释放

数据元素的逻辑次序靠结点的指针来指示，插入和删除时不需要移动数据元素

链式存储结构缺点：

存储密度小没每个结点的指针域需要额外占用存储空间。当每个结点的数据域所占字节不多时，指针域所占存储空间的比重显得很大

链式存储结构是非随机存取结构。对任一节点的操作都要从头指针依指针链查找到该结点，这增加了算法的复杂度

存储密度

是指结点数本身所占的存储量和整个结点结构所占存储量之比，即

存储密度 = 结点数据本身占用的空间/结点占用的空间总量

线性表的应用

线性表的合并：

问题描述：

假设利用两个线性表La和Lb分别表示两个集合A和B，现要求一个新的集合A=A∪B

La = （7,5,3,11）Lb = （2,6,3）=》 La = （7,5,3,11,2,6）

【算法思路】

依次取出Lb中的每个元素，执行以下操作：

1.在La中查找该元素

2.如果找不到，则将其插入La的最后

void union(List &La,List &Lb){
    La_len = ListLength(La);
    Lb_len = ListLength(Lb);
    for( i = 1 ; i < Lb_len; i ++ ){
        GetElem(Lb,i,e);
        if(!LocateElem(La,e)) ListInsert(&La,++La_len,e);
    }
}

有序表的合并：

问题描述：

已知线性表La和Lb中的数据元素按值非递减有序排列，现要求将La和Lb归并为一个新的线性表Lc，且Lc中的数据元素扔按值非递减有序排列

La = (1,7,8) Lb = (2,4,6,8,10,11) => Lc = (1,2,4,6,7,8,8,10,11)

【算法思路】

1.创建一个空表

2.依次从La中或Lb中"摘取"元素值娇小的结点插入到Lc表的最后，直至其中一个变空表为止

3.继续将La或Lb其中一个表的剩余结点插入在Lc表的最后

顺序表实现

void MergeList_Sq(SqList LA,SqList LB,SqList &LC){
    pa = LA.elem;
    pb = LB.elem;//指针pa，pb的初值分别指向两个标的第一个元素
    LC.length = LA.length + LB.length; //新表长度为待合并两表的长度之和
    LC.elem = (int *)malloc(sizeof(LC.length));//为合并后的新表分配一个数组空间
    pc = LC.elem; //指针pc指向新表的第一个元素
    pa_last = LA.elem + LA.length - 1;//指针pa_last指向LA表的最后一个元素
    pb_last = LB.elem + LB.length - 1;//指针pb_Last指向LB表的最后一个元素
    while(pa<=pa_last&&pb<=pb_last){//两个表都非空
        if(*pa<=*pb) *pc ++ = *pa++;//依次"摘取"两表中值娇小的结点
        else *pc ++ = *pb ++;
    }
    while(pa<=pa_last) *pc++ = *pa++; //LB表已到达表尾，将LA中剩余元素加入LC
    while(pb<=pb_last) *pc++ = *pb++;//表LA已到达表尾，将LB中剩余元素加入LC
}

链表实现

void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){
    pa = La->next;
    pb = Lb->next;
    pc = Lc = La; //用La的头结点作为Lc的头结点
    while(pa&&pb){
        if(pa->data<=pb->data){
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        }else{
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
    }
    pc->next = pa?pa:pb;//插入剩余段
    free(Lb);//释放Lb的头结点        
}

案例分析与实现

【案例2.1】一元多项式的运算：实现两个多项式加、减、乘运算

P_n(x) = p_0+p_1x+p_2x^2+...+p_nx^n\\ 线性表P = (p_0,p_1,p_2,...,p_n)\\ 每一项的指数i隐含在其系数p_i的序号中

例如:

P(x) = 10 + 5x - 4x^2 + 3x^3 + 2x^4

指数(下标i)	0	1	2	3	4
系数p[i]	10	5	-4	3	2

例如实现两个多项式相加运算

Pa(x) = 10 + 5x - 4x^2 + 3x^3 + 2x^4\\ Pb(x) = -3 + 8x + 4x^2 - 5x^4 + 7x^5 - 2x^6

系数Pa[i] 10 5 -4 3 2

系数Pb[i] -3 8 4 0 -5 7 -2

系数Pc[i] 7 13 0 3 -3 7 -2

【案例2.2】系数多项式的运算

多项式非零项的数组表示

(a) A(x) = 7 + 3x + 9x^8 + 5x^{17}

下标i	0	1	2	3
系数a[i]	7	3	9	5
指数	0	1	8	17

(b) B(x) = 8x + 22x^7 - 9x^8

下标i	0	1	2
系数b[i]	8	22	-9
指数	1	7	8

P_n(x) = p_1x^{e_1} + p_2x^{e_2} + ... + p_mx^{e_m}

线性表 P = ((p_1,e_1),(p_2,e_2),...,(p_m,e_m))

线性表A = ((7,0),(3,1),(9,8),(5,17))

线性表B = ((8,1),(22,7),(-9,8))

创建一个新数组C
分别从头遍历比较a和b的每一项

指数相同，对应系数相加，若其和不为零，则在c中增加一个新项

指数不相同，则将指数较小的项复制到c中
一个多项式已遍历完毕时，将另一个剩余项依次复制到c中即可

链式存储结构结点定义

typedef struct PNode{
    float coef; //系数
    int expn; //指数
    struct PNode *next;//指针域
}PNode,*Polynomial;

【算法步骤】多项式创建

①0创建一个只有头结点的空链表

②根据多项式的项的个数n，循环n次执行以下操作：

生成一个新结点*s
输入多项式当前项的系数和指数赋给新结点*s的数据域
设置一前驱指针pre，用于指向待找到的第一大于输入项指数的结点的前驱，pre初始值指向头结点
指针q初始化，指向首元结点
循链向下逐个比较链表中当前结点与输入项指数，找到第一个大于输入项指数的结点*q
将输入项结点 *s 插入到结点 *q之前

void CreatPolyn(Polynomial &P,int n){
    //输入m项的系数和指数，建立表示多项式的有序链表P
    P = new PNode;
    P->next = NULL;//先建立一个带头结点的单链表
    for(i = 1;i <=n ;i++){//依次输入n个非零项
    	s = new PNode;//生成新结点
        cin>>s->coef>>s->expn;//输入系数和指数
        pre = P;//pre用于保存q前驱，初值为头结点
        q = P->next;//q初始化，指向首元结点
        while( q && q->expn < s->expn ){//找到第一个大于输入项指数的项*q
            pre = q;
            q = q->next;
        }
        s->next = q;//将输入项s插入到q和其前驱结点pre之间
        pre->next = s;
    }
}

【算法思路】多项式相加

①指针p1和p2初始化，分别指向Pa和Pb的首元结点

②p3指向和多项式的当前结点，初值为Pa的头结点

③当指针p1和p2均未到达表尾时，则循环比较p1的p2所指结点对应的指数值

（p1->expn与p2->expn),有下列3种情况

当p1->expn==p2->expn时，则将两个结点中的系数相加

若和不为零，则修改p1所指结点的系数值，同时删除p2所指结点

若和为零，则删除p1和p2所指结点
当 p1->expn < p2->expn时，则应摘取p1所指结点插入到"和多项式"链表中去
当p1->expn > p2->expn时，则应摘取p2所指结点插入到"和多项式"链表中去

④将非空多项式的剩余段插入到p3所指结点之后

⑤释放Pb的头结点

【案例2.3】图书信息管理系统

struct Book{
    char id[20]; //ISBN
    char name[50]; //书名
    int price; //定价
};

typedef struct{//顺序表
    Book *elem;
    int  length;
}SqList;

typedef struct LNode{//链表
	Book data;
    struct LNode *next;
}LNode,*LinkList;

栈和队列

栈和队列的定义和特点

栈和队列是两种常用的、重要的数据结构

栈和队列是限定插入和删除只能在表的"端点"进行的线性表

线性表

Insert(L,i,x) 1<=i<=n+1

Delete(L,i) 1<=i<=n

栈先进后出

Insert(S,n+1,x)

Delete(S,n)

队列先进先出

Insert(Q,n+1,x)

Delete(Q,1)

栈的应用

由于栈的操作具有后进先出的固有特性，使得栈称为程序设计的有用工具。另外，如果问题求解的过程具有"后进先出"的天然特性的话，则求解的算法中也必然需要利用"栈"

例如：

- 数值转换 - 表达式求值

- 括号匹配的检验 - 八皇后问题

- 行编辑程序 - 函数调用

- 迷宫求解 - 递归调用的实现

队列的常见应用

由于队列的操作具有先进先出的特性，使得队列成为程序设计中解决类似排队问题的有用工具

- 脱机打印输出：按申请的先后顺序依次输出

- 多用户系统中，多个用户排成队，分时地循环使用CPU和主存

- 按用户的优先级排成多个队，每个优先级一个队列

- 实时控制系统中，信号按接收的先后顺序依次处理

- 网络电文传输，按到达时间先后顺序依次进行

栈的定义和特点

栈(Stack)是一个特殊的线性表，是限定仅在一端(通常是表尾)进行插入和删除操作的线性表

又称为后进先出(Last In First Out)的线性表，简称LIFO结构

栈的相关概念

栈是仅在表尾进行插入、删除操作的线性表

表尾（即an端）称为栈顶Top；表头（即a1端）称为栈底Base

例如：栈 S = (a_1,a_2,a_3,...,a_n)\\ a_1称为栈底元素 \\ a_n称为栈顶元素

插入元素到栈顶(即表尾)的操作，称为入栈

从栈顶(即表尾)删除最后一个元素的操作，称为入栈

“入” = 压入 = PUSH(x)

“出” = 弹出 = POP(x)

【思考】假设有3个元素a,b,c，入栈顺序是a,b,c,则它们的出栈顺序有几种可能？

c b a , a b c, a c b, b a c, b c a

插入的时机不一样出栈顺序不一样

队列的定义和特点

队列(queue)是一种先进先出(First In First Out ----FIFO)的线性表。在表的一端插入(表尾)，在另一端(表头)删除

案例引入

【案例3.1】进制转换

十进制整数N向其他进制数d(二、八、十六)的转换是计算机实现计算的基本问题

转换法则:除以d倒取余

该转换法则对应于一个简单算法原理

n = (n div d)*d + n mod d

其中：div为整除运算，mod为求余运算

例把十进制数159转换成八进制数

159/8 = 19 余7

19/8 = 2 余3

2/8 = 0 余2

所以是237 后进先出用栈

【案例3.2】括号匹配的检验

假设表达式中允许包含两种括号：圆括号和方括号
其嵌套的顺序随意，即：
1. （ [ ] ( ) ) 或 [ ( [ ] [ ])]为正确格式
2. [ ( ] ) 为错误格式
3. ( [ ( ) 或 ( ( ) ] )为错误格式

【算法思路】

可以利用一个栈结构保存每个出现的左括号，当遇到右括号时，从栈中弹出左括号，检验匹配情况
在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论
1. 当遇到某一个右括号时，栈已空，说明到目前为止，右括号多余左括号
2. 从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况
3. 算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号

【案例3.3】表达式求值

表达式求值是程序设计语言编译中一个最基本的问题，它的实现也需要运用栈
这里介绍算法是由运算符优先级确定运算顺序的对表达式求值算法

算符优先算法

表达式的组成
- 操作符(operand)：常数、变量
- 运算法(operator)：算术运算符、关系运算符和逻辑运算符
- 界限符(delimiter)：左右括弧的表达式结束符
任何一个算术表达式都由操作数(常数、变量)、算数运算符(+、-、*、/)和界限符(括号、表达式结束符’#’.虚设的表达式起始符’#’)组成。后者统称为运算符
- 例如： # 3 *(7-2) #

为了实现表达式求值。需要设置两个栈:

一个是算符栈OPTR，用于寄存运算符

另一个是称为操作数符OPND，用于寄存运算数和运算结果

求值的处理过程是自左至右扫描表达式的每一个字符

当扫描到的是运算符，则将其压入栈OPND
当扫描到的是运算符时
- 若这个运算符比OPTR栈顶运算符的优先级高，则入栈OPTR，继续向后处理
- 若这个运算符比OPTR栈顶运算符优先级低，则从OPND栈中弹出两个运算符，从栈OPTR中弹出栈顶运算符进行运算，并将运算结果入栈OPND
继续处理当前字符，直到遇见结束符为止

【案例3.4】舞伴问题

假设在舞会上，男士和女士各自排成一队。舞会开始时，依次从男队和女队的队头各出一人配成舞伴。如果两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题
显然，先入队的男士或女士先出队配成舞伴。因此该问题具有典型的先进先出特性，可以用队列作为算法的数据结构
- 首先构造两个队列
- 依次从队头元素出队配成舞伴
- 某队为空，则另外一队等待者则是下一舞曲第一个可获得舞伴的人

栈的表示和操作的实现

顺序栈的表示和实现

存储方式：同一般线性表的顺序存储结构完全相同，利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。栈底一般在低地址端

附设top指针，指示栈顶元素在顺序栈中的位置
另设base指针，指示栈底元素在顺序栈中的位置

但是，为了方便操作，通常top指示真正的栈顶元素之上的下标地址

另外，用stacksize表示栈可使用的最大容量

空栈：base==top是栈空标志

栈满：top-base==stacksize

栈满时的处理方法：

1.报错，返回操作系统

2.分配更大的空间，作为栈的存储空间，将原栈的内容移入新栈

使用数组作为顺序栈存储方式的特点：

简单方便但易溢出（数组大小固定）

上溢(overflow):栈已经满，又要压入元素

下溢(underflow):栈已经空，还要弹出元素

**注：**上溢是一种错误，使问题的处理无法进行，而下溢一般认为是一种结束条件，即问题处理结束

顺序栈的表示

#define MAXSIZE 100
typedef struct{
    SElemType *base;//栈底指针
    SElemType *top;//栈顶指针
    int stacksize;//栈可用最大容量
}SqStack;

顺序栈相关算法

【算法3.1】顺序栈的初始化

Status InitStack(SqStack &S){//构造一个空栈
	S.base = (SElemType)malloc(MAXSIZE*sizeof(SElemType));
    if(!S.base) exit(OVERFLOW);//存储分配失败
    S.top = S.base;//栈顶指针等于栈底指针
    S.tacksize = MAXSIZE;
    return OK;
}

【算法补充】顺序栈判断栈是否为空

Status StackEmpty(SqStack S){
    //若栈为空，则返回TRUE；否则返回FALSE
    if(S.top == S.base){
        return TRUE;
    }else{
        return FALSE;
    }
}

【算法补充】求顺序栈的长度

1
2
3

int StackLength(SqStack S){
    return S.top-S.base;
}

【算法补充】清空顺序栈

Status ClearStack(SqStack &S){
    if(S.base) S.top == S.base;
    return OK;
}

【算法补充】销毁顺序栈

Status DestoryStack(SqStack &S){
    if(S.base){
        free(S.base);
        S.stacksize = 0;
        S.base = S.top = NULL;
    }
    return OK; 
}

【算法3.2】顺序栈的入栈

1.判断是否栈满，若满则出错(上溢)

2.元素e压入栈顶

3.栈顶指针加1

Status Push(SqStack &S,SElemType e){
    if(S.top-S.base == S.stacksize) //栈满
        return ERRPR;
    *S.top = e;
    S.top++;
}

【算法3.3】顺序栈的出栈

判断是否栈空，若空则出错(下溢)
栈顶指针减1
获取栈顶元素e

Status Pop(SqStack &S,SElemType &e){
    //若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK，否则返回ERROR
    if(S.top == S.base) //等价于if(StackEmpty(S))
        return ERROR;
    e = *--S.top;
    return OK; 
}

链栈的表示和实现

链栈的表示

链栈是运算受限的单链表，只能在链表头部进行操作

typedef struct StackNode{
    SElemType data;
    struct StackNode *next;
}StackNode,*Linkstack;

注意：链表中指针的方向是反过来的

链表的头指针就是栈顶
不需要头结点
基本不存在栈满的情况
空栈相当于头指针指向空
插入和删除仅在栈顶处执行

【算法3.5】链栈的初始化

void InitStack(LinkStack &S){
    //构造一个空栈，栈顶指针置为空
    S = NULL;
    return OK;
}

【补充算法】判断链栈是否为空

Status StackEmpty(LinkStack S){
    if(S == NULL) return TRUE;
    else return FALSE;
}

【算法3.6】链栈的入栈

Status Push(LinkStack &S,SElemType e){
    p = (LinkStack)malloc(sizeof(StackNode)); //生成新结点p
    p->data = e; //将新结点数据域置为e
    p->next = S; //将新结点插入栈顶
    S = p;//修改栈顶指针
    return OK;
}

【算法3.7】链栈的出栈

Status Pop(LinkStack &S,SElemType &e){
    if(S==NULL) return ERROR;
    e = S->data;
    p = S;
    S = S->next;
    free(p);
    return OK;
}

【算法3.8】取栈顶元素

SElemType GetTop(LinkStack S){
    if(S!==NULL)
        return S->data;
}

栈与递归

递归的定义
- 若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的
- 若一个过程直接地或间接地调用自己，则称这个过程是递归的过程

分治法求解递归算法的一般形式：

void p(参数表){
    if(递归结束条件) 可直接求解步骤; //基本项
    else p(较小的参数); //归纳项
}

函数调用过程

调用前，系统完成
1. 将实参，返回地址等传递给被调函数
2. 为被调函数的局部变量分配存储区
3. 将控制转移到被调函数的入口
调用后，系统完成
1. 保存被调函数的计算结果
2. 释放被调函数的数据区
3. 依照被调用函数保存的返回地址将控制转移到调用函数

队列的表示和操作的实现

队列的顺序表示——用一位维数组base[MAXSIZE]

#define MAXSIZE 100//最大队列长度
typedef struct{
    QElemType *base;//初始化的动态分配存储空间
    int front;//头指针 称为指针，但不是指针变量
    int rear;//尾指针
}SqQueue;

入队存在的问题

设数组大小为MAXSIZE

rear =MAISIZE时，发生溢出

若 front = 0 rear = MAXSIZE时，再入队，真溢出

若 front ≠ 0 rear = MAXSIZE时，再入队，假溢出

解决假上溢的办法

将队中元素依次向队头方向移动

缺点：浪费时间。每移动一次，队中元素都要移动
将队空间设想成一个循环的表，即分配给队列的m个存储单元可以循环使用，当rear为maxsize时，若向量的开始端空着，又可以从头使用空着的空间。当front为maxsize时，也是一样

引入循环队列

base[0]

接在base[MAXSIZE-1]之后，若rear+1==M,则令rear=0

实现方法:利用模(mod,C语言中:%)运算

插入元素:Q.base[Q.rear] = x

Q.rear = (Q.rear+1)%MAXSIZE

删除元素：x = Q.base[s.front]

Q.front = (Q.front+1)%MAXSIZE

队空：front == rear

队满：front == rear

解决方案：

另外设一个标志以区别队空、队满
另设一个变量，记录元素个数
少用一个元素空间

【算法3.11】队列的初始化

Status InitQueue(SqQueue &Q){
    Q.base = (QElemType*)malloc(MAXSIZE*sizeof(QElemType));//分配数组空间
    if(!Q.base) exit(OVERFLOW);//存储分配失败
    Q.front = Q.base = 0;//头指针尾指针置为0，队列为空
    return OK;
}

【算法3.12】求队列的长度

1
2
3

int QueueLength(SqQueue Q){
	return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;                        
}

【算法3.13】循环队列入队

Status ENQueue(SqQueue &){
    if((Q.rear+1)%MAXSIZE==Q.front) return ERROR;//队满
    Q.base[Q.rear] = e;//新元素加入队尾
    Q.rear = (Q.rear+1)%MAXSIZE;//队尾指针+1
}

【算法3.14】循环队列出队

Status DeQueue(SqQueue &Q,QElemType &e){
    if(Q.front == Q.rear) return ERROR;//队空
    e = Q.base[Q.base];//保存队头元素
    Q.front = (Q.front+1)%MAXSIZE;//队头指针+1
}

【算法3.15】取队头元素

SElemType GetHead(SqQueue Q){
    if(Q.front!=Q.rear)//队列不为空
        return Q.base[Q.base];//返回队头指针元素的值，队头指针不变
}

链队

若用户无法估计所用队列的长度，则宜采用链队列

链队列的类型定义

#define MAXSIZE 100 //最大队列长度
typedef struct Qnode{
    QElemType data;
    struct Qnode *next;
}QNode,*QuenePtr;

typedef struct{
    QuenePtr front;//队头指针
    QuenePtr rear;//队尾指针
}LinkQueue;

链队列运算指针变化状况

【算法3.16】链队列的初始化

Status InitQueue(LinkQueue &Q){
    Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
    if(!Q.front) exit(OVERFLOW);
    Q.front->NULL;
    return OK;
}

【补充算法】销毁链队列

Status DestroyQueue(LinkQueue &Q){
    while(Q.front){
        p = Q.front->next;
        free(Q.next);
        Q.front = p;
    }
    return OK;
}

【算法3.17】将元素e入队

Status EnQueue(LinkQueue &Q,QElemType e){
    p = (QueuePtr)malloc(sizeof(QNode));
    p->data = e;
    p->next = NULL;
    Q.rear = p;
    return OK;
}

【算法3.18】链队列出队

Status DeQueue(LinkQueue &Q,QElemType &e){
    if(Q.front == Q.rear) return ERROR;
    p = Q.front->next;
    e = p->data;
    Q.front->next = p->next;
    if(Q.rear == p){
        Q.rear  = Q.front;
    }
    free(p);
    return OK;
}

【算法3.19】求链队列的队头元素

Status GetHead(LinkQueue Q,QElemType &e){
    if(Q.front == Q.rear) return ERROR;
    e = Q.front->next->data;
    return OK;
}

串、数组和广义表

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      ## 串

串的定义

零个或多个任意字符组成的有限序列

子串：串中任意个连续字符组成的子序列（含空串）称为该串的子串

主串：包含子串的串相应的称为主串

字符位置：字符在序列中的序号为该字符在串中的位置

子串位置：****子串中第一个字符在主串中的位置

**空格串：**由一个或多个空格组成的串 与空串不同

串相等：当且仅当两个串的长度相等并且各个对应位置上的字符都相等时，这两个串才是相等的

所有的空串都是相等的

案例引入

【案例4.1】病毒感染监测

研究者将人的DNA和病毒DNA均表示成由一些字母组成的字符串序列，然后检测某种病毒DNA序列是否在患者的DNA序列中出现过，如果出现过，则此人感染了该病毒，否则没有感染

例如：假设被病毒的DN序列为baa，患者1的DNA序列为aaabbba，则感染，患者2的DNA序列为babbba，则未感染

注意，人的DNA序列是线性的，而病毒的DNA序列是环状的

串的类型定义、存储结构及运算

串的顺序存储结构

#define MAXLEN 255
typedef struct{
    char ch[MAXLEN+1];//存储串的一维数组
    int length; //串的当前长度
}SString;

串的链式存储结构–块链结构

#define CHUNKSIZE 80 //块的大小可由用户定义
typedef struct Chunk{
    char ch[CHUNKSIZE];
    struct Chunk *next;
}Chunk;
typedef struct{
    Chunk *head,*tail;//串的头指针和尾指针
    int curlen; //串的当前长度
}LString;//字符串的块链结构

串的模式匹配算法

算法目的：

确定主串中所含子串(模式串)第一次出现的位置(定位)

算法应用：

搜索引擎拼写检查语言翻译数据压缩

算法种类：

BF算法(Brute-Force,又称古典的、经典的、朴素的、穷举的)
KMP算法(特点：速度快)

Brute-Force简称为BF算法，亦称简单匹配算法。采用穷举法的思想

S: a a a a b c d 主串：正文串

T: a b c 子串：模式

算法思路是从S的每一个字符开始依次与T的字符进行匹配

BF算法设计思想：

将主串的第pos个字符和模式串的第一个字符比较
- 若相等，继续逐个比较后续字符
- 若不等，从主串的下一字符起，重新与模式串的第一个字符比较

直到主串的一个连续子串字符序列与模式串相等。返回值为S中与T匹配的子序列第一个字符的的序号，即匹配成功。否则，匹配失败，返回0

int Index_BF(SString S,SString T){
     int i = 1, j = 1;
    while(i<=S.length&&j<=T.length){
        if(s.ch[i] == t.ch[i]){//主串和子串依次匹配下一个字符
        	++i;
            ++j;
        }else{
            i = i-j+2;//主串子串指针回溯重新开始下一次匹配
            j = 1;
        }
    }
    if(j>T.length) return i-T.length;//返回匹配的第一个字符的下标
    else return 0;//模式匹配不成功 
}

KMP算法

KMP算法设计思想

利用已经部分匹配的结果而加快模式串的滑动速度且主串S的指针i不必回溯

可提速到O(n+m)

j	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
模式串	a	b	c	a	a	b	b	c	a	b	c	a	a	b	d	a	b
next[j]	0	1	1	1	2	2	3	1	1	2	3	4	5	6	7	1	2

int Index_KMP(SString S,SString T,int pos){
    i = pos,j = 1;
    while(i<S.length&&j<T.length){
        if(j == 0||S.ch[i] = S.ch[j]){
            i++;
            j++;
        }else{
            j = next[j]; //i不变，j后退
        }
    }
    if(j>T.length) return i-T.length; //匹配成功
    else return 0;//不匹配
}

void get_next(SString T,int &next[]){
    i = 1;
    next[1] = 0;
    j = 0;
    while(i<T.length){
        if(j == 0||T.ch[i] == T.ch[j]){
    		i++;
             j++;
             next[i] = j;
        }else{
            j = next[j];                                                 
        }
    }
}

数组

声明格式: 数据类型变量名称 [行数] [列数]

n维数组：若n-1维数组中的元素又是一个一维数组结构，则称作n维数组

一维数组：

例如，有数组定义：int a[5]

每个字节占用4字节，假设a[0]存储在2000单元，a[3]地址是多少

数组的顺序存储

存储单元是一维结构，而数组是个多维结构，则用一维连续存储单元存放数组的数据元素就有个次序约定问题

以行序为主序

C JAVA PASCAL BASIC

特殊矩阵的压缩存储

什么是压缩存储？

若多个数据元素的值都相同，则只分配一个元素值的存储空间，且零元素不占存储空间
什么样的矩阵能够压缩？

一些特殊矩阵，如：对称矩阵，三角矩阵，对角矩阵，稀疏矩阵等
什么叫稀疏矩阵？

矩阵中非零元素的个数很少(一般小于5%)

1.对称矩阵

【特点】在n×n的矩阵a中，满足如下性质：

a_{ij} = a_{ji}(1<=i,j<=n)

【存储方式】只存储下(或者上)三角(包括主对角线)的数据元素。共占用n(n+1)/2个元素空间

下三角：k = i(i-1)/2 + j

2.三角矩阵

【特点】对角线以下（或者以上）的数据元素（不包括对角线）全部为常数c

【存储方法】重复元素c共享一个元素存储空间，共占用n(n+1)/2+1个元素空间

下三角矩阵

k = i×(i-1)/2 + j i>= j

n(n+1)/2 + 1 i<j

上三角矩阵

k = i(2n-i+1)/2+j-1 i<=j

n(n+1)/2 + 1 i>j

3.对角矩阵

【特点】在n×n的方阵中，所有非零元素都集中在以主对角线为中心的带状区域中，区域外的值全为0，则成为对角矩阵。常见的有三对角矩阵、五对角矩阵、七对角矩阵等

稀疏矩阵存储

设在m×n的矩阵中有t个非零元素\\ 令 {\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,} \delta = t/(m×n)\\ {\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}当{\,}{\,}{\,}{\,}{\,}{\,}\delta \leq0.05时称为稀疏矩阵

三元组顺序表：

用行数、列数表示非零元素所在位置

十字链表：

在十字链表中，矩阵的每一个非零元素用一个结点表示，该结点除了(row,col,value)以外，还要有两个域：

right:用于链接同一行中的下一个非零元素
down:用于链接同一列中的下一个非零元素

Java集合框架面试题（更新中）

Created2021-12-19Updated2021-12-19

说出 collection 的常用子接口？说出 3 个以上的常用方法？都有什么作用？

1. Collection具有两个比较常用的子接口，List和Set;
2. Collection中的常用方法
在这里插入图片描述

1、添加

Boolean add(E e):在集合中添加一个对象，如果添加成功，返回true，如果失败，返回false

Boolean addAll(Collection<?extend E> e)：在集合中添加另一个集合，成功true,失败false;

2、删除
Boolean remove(object obj):删除一个对象,会改变集合的长度

Boolean removeAll(Colleciton con);删除一个集合，还有两个集合中相同的元素

void clear():删除所有

3、判断
Boolean contains(object obj):在集合中是否包含指定的对象

Boolean containsAll(Collection con):在集合是否包含另一个集合

Boolean isEmpty( )：判断集合是否为空

4、获取

int size( )：得到集合的尺寸大小数组:length 字符串:length( );

Iterator iterator( )：取出元素的方式。迭代器。该对象必须依赖于绝缘体容器，因为每一个容器的数据结构都不同。所以该迭代器对象是在容器中进行内部实现的，对于使用容器者而言，绝缘体的实现不重要，只要通过容器获取到该实现的迭代器的对象即可，也就是iterator方法，Iterator接口就是对所有的collection容器进行元素取出的公共接口。将每一个容器中的取出方式进行了封装，并对外暴露，这样无论是什么容器或者数据结构，只要内部取出方式实现了Iterator接口，都可以通过该接口取出这些容器中的元素。他的出现，将容器的取出方式和容器的数据结构相分离，降低了耦合性，而取出方式因为直接在访问容器的元素，并依赖具体的数据结构，所以被定义在了容器中。通过内部类来实现Iterator接口。

Collection c = new ArrayList();

c.add("hello");

Iteratot it = c.iterator();//返回的是Iterator的子类对象

while(it.hasNext()){

String str = (String)it.next();

System.out.println(str);

}

for(object obj:con)用于数组和集合(高级for循环)

注意：迭代要强转，只能有一个next( )方法，否则会有NoSuchElementException异常。

5、交集

boolean retainAll(Collection c)：返回两个集合的交集元素，删除其他元素，功能和removeAll相反。有A,B两个集合，做完交集后，A集合中的元素发生变化，取得是A和B相同的元素，B不变化。boolean值的问题-------->只要A集合变化,那么返回true.否则false

6、集合转数组

Object[ ] toArray()：把集合转换成对象。

如果向 TreeSet 中加入类对象，需要做什么？

实现Comparable接口重写compareTo方法或者在TreesSet创建对象时传入自定义的比较类

Set 里的元素是不能重复的，那么用什么方法来区分重复与否呢? 是用==还是 equals()? 它们有何区别?

从它俩的区别谈起，==是用来判断两者是否是同一对象（同一事物），而equals是用来判断是否引用同一个对象。再看一下Set里面存的是

对象，还是对象的引用。根据java的存储机制可知，set里面存放的是对象的引用，所以当两个元素只要满足了equals()时就已经指向同一个对象，

也就出现了重复元素。所以应该用equals()来判断。

ArrayList 和 Vector 的区别？

1.ArrayList是线程不安全的，Vector是线程安全的
2.ArrayList扩容是原来一半，Vector是原来的一倍

集合当中能存放基本数据类型的数据吗？

Java集合不能存放基本数据类型，只能存放对象的引用。

每个集合元素都是一个引用变量，实际内容都存放在堆内或方法区里面，

但是基本数据类型是在栈内存上分配空间的，栈上的数据随时会被收回。

如何解决？

可以通过包装类，把基本数据类型转化为对象类型，存放引用。

更方便的，由于有了自动拆箱和装箱功能，基本数据类型和其对应对象

之间的转换变得很方便，把基本数据类型存入集合中可以自动存，系统

会自动将其装箱成封装类，然后将其加入到集合当中。

ArrayList 与数组的区别?

Array可以包含基本类型和对象类型，ArrayList只能包含对象类型。

Array大小是固定的，ArrayList的大小是动态变化的。

java 集合框架的四种主要接口是

Collection：存储无序的、不唯一的数据；其下有List和Set两大接口。

List：存储有序的、不唯一的数据；

Set：存储无序的、唯一的数据；

Map：以键值对的形式存储数据，以键取值。键不能重复，但值可以重复。

HashMap 和 Hashtable 的区别?

1 HashMap不是线程安全的

HashMap是map接口的子类，是将键映射到值的对象，其中键和值都是对象，并且不能包含重复键，但可以包含重复值。HashMap允许null key和null value，而hashtable不允许。

2 HashTable是线程安全。

HashMap是Hashtable的轻量级实现（非线程安全的实现），他们都完成了Map接口，主要区别在于HashMap允许空（null）键值（key）,由于非线程安全，效率上可能高于Hashtable。

HashMap允许将null作为一个entry的key或者value，而Hashtable不允许。 HashMap把Hashtable的contains方法去掉了，改成containsvalue和containsKey。因为contains方法容易让人引起误解。 Hashtable继承自Dictionary类，而HashMap是Java1.2引进的Map interface的一个实现。最大的不同是，Hashtable的方法是Synchronize的，而HashMap不是，在多个线程访问Hashtable时，不需要自己为它的方法实现同步，而HashMap 就必须为之提供外同步。 Hashtable和HashMap采用的hash/rehash算法都大概一样，所以性能不会有很大的差

Collection 框架中实现比较方法

Java集合框架中需要比较大小的集合包括TreeMap、TreeSet，其中TreeMap会根据key-value对中key的大小进行排序，而TreeSet则会对集合元素进行排序。
因此TreeMap的key、TreeSet的集合元素，都需要可以比较大小。集合框架中之比较大小的有两种方式：

A．自然排序：对于自然排序来说，要求TreeMap中的所有key都实现Comparable接口，实现该接口时需要实现一个int compareTo(T o)方法，用于判断当前对象与o对象之间的大小关系。如果该方法返回正整数，则说明当前对象大于o对象；如果该方法返回0，说明两个对象相等；如果该方法返回负整数，则说明当前对象小于o对象；JDK的很多类都已经实现了Comparable接口，例如String、Date、BigDecimal等。

B．定制排序：定制排序需要在创建TreeMap或TreeSet时传入一个Comparator对象，此时TreeMap或TreeSet不再要求key、集合元素本身是可比较大小的，而是由Comparator来负责比较集合元素的大小。Comparator本身只是一个接口，因此创建Comparator对象只能是创建它的实现类的对象，Comparator的实现类需要实现int compare(T o1, T o2)方法，该方法用于判断o1、o2两个对象的大小，如果该方法返回正整数，则说明o1大于o2、如果该方法返回负整数，则说明o1小于o2、如果返回0，则说明两个对象相等。

在 Java 中，HashMap 中是用哪些方法来解决哈希冲突的？

解决哈希冲突的方法有三种,分别是:

```再散列法(二次哈希法)```:再次使用一个不同的哈希算法再计算一次 (第一次%16换另一个数进行%运算)
```链地址法(拉链法)```:将所有冲突元素按照链表存储,冲突后时间复杂度变为O(1+n)n为冲突元素个数)[hashMap就是用这种方法]

**首先来了解一下什么是哈希表**

哈希表是以(Key,Value):数值的形式存储数据的

根据相应的哈希算法计算key,返回值即为V存储的数组下标

哈希算法:f(K) --- . int即为V需要存储的数组下标

**为什么会造成哈希冲突呢?**

用一个数去模运算,取得余数就是所要存储数组数据的下标,但是余数可能会存在一样的,这样就导致一样余数的户数无处存储,所以就造成了哈希冲突.

**哈希冲突解决思路:**

哈希算法计算的两个不同对象的哈希值相等的情况

> eg:1 % 16 == 17 % 16[1和17是不同的key值]--->就是哈希冲突了

HashMap中用链地址法来解决 

HashMap源码解析(负载因子,树化策略,内部hash实现,resize策略...)
HashMap中的内部属性:

负载因子:final loadFactor (默认为0.75f)
实际容量: int threshold = loadFactor * tab.length
树化阈值:int TREEIFY_THRESHOLD = 8;
解除树化阈值: int UNTREEIFY_THRESHOLD = 6;
HashMap也采用了懒加载策略,第一次put时初始化哈希表
树化逻辑:索引下标对应的链表长度达到阈值8并且当前哈希表长度达到64才不会树化,否则只是调用resize()方法进行哈希表扩容
resize();扩容为原先数组的2倍
负载因子大小怎么决定?

负载因子过大会导致哈希冲突明显增加,节省内存

负载因子过小会导致哈希表频繁扩容,内存利用率低

 默认0.75,0.75是一个经过计算得出的值,即能保证哈希冲突不会太严重也能保证效率不会太低

源码: 

```java
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
 
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

可以发现源码中并没有直接使用Object中的hashCode方法,而是再让h无符号右移了16位

为何不直接使用Object提供的hashCode?

为了将哈希码保留一半,将高低位都参与运算,减少内存开销,减少哈希冲突

直接使用会造成空间浪费

(h = key.hashCode()) ^ (h >>> 16); //32 —>16 保留一半(原本32右移16位去掉了一半)

put内部逻辑:

1.哈希表索引下标计算:

i = (n-1) & hash //与运算

保证求出的索引下标都在哈希表的长度范围之内

2.n为哈希表的长度

n必须为2 的n次方,保证哈希表中的所有索引下标都会被访问到

若n=15,则以下位置永远不可能存储元素

0011,0101,1001,1011,1101,1111

接下来再看源码:

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
//第一次put值的时候将哈希表初始化
//resize():1,完成哈希表的初始化  2.完成哈希表的扩容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
//当目标索引未存储元素时,将当前元素存储到目标索引位置
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
//哈希表已经初始化并且算出的数据下标已经有元素了
    else {
        Node<K,V> e; K k;
//若索引下标对应的元素key值恰好与当前元素key值相等且不为空,
//将value替换为当前元素的value
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
//此时索引对应的链表已经树化了,采用红黑树方式将当前节点添加到树中
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//以链表方式将当前节点添加到链表末尾
        else {
            for (int binCount = 0; ; ++binCount) { //binCount当前链表的长度
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        //尝试将链表树化
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
//扩容策略
//此时添加了新节点
    if (++size > threshold)
        //扩容
        resize();
    afterNodeInsertion(evict);
    return null;
}

为何HashMap中JDK1.8要引入红黑树?

当链表长度过长时,会将哈希表查找的时间复杂度退化为O(n),树化会保证即便在哈希冲突严重时,查找的时间复杂度也为O(logn)

当红黑树结点个数在扩容或者删除元素时减少为6以下,在下次resize()过程中会将红黑树退化为链表,节省空间

Collection 和 Collections 的区别?

1、Collection 是一个集合接口。它提供了对集合对象进行基本操作的通用接口方法。Collection接口在Java 类库中有很多具体的实现。Collection接口的意义是为各种具体的集合提供了最大化的统一操作方式。
2、Collections 是一个包装类。它包含有各种有关集合操作的静态多态方法。此类不能实例化，就像一个工具类，服务于Java的Collection框架。

Java网络编程

Created2021-12-19Updated2021-12-19

网络编程概述

计算机网络

·是指将地理位置不同的具有独立功能的多台计算机及其外部设备，通过通信线路连接起来，
在网络操作系统，网络管理软件及网络通信协议的管理和协调下，实现资源共享和信息传递的计算机系统

网络编程

·在通信协议下，实现网络互连的不同计算机上运行的程序间可以进行数据交换

网络编程三要素

IP地址

·要想让网络中的计算机能够互相通信，必须为每台计算机指定一个标识号，通过这个标识号来指定
要接收数据的计算机和识别发送的计算机，而IP地址就是这个标识号。也就是设备的标识

端口

·网络的通信，本质是两个应用程序的通信。每台计算机都有很多的应用程序，那么在网络通信时，
如何区分这些应用程序呢？如果说IP地址可以唯一识别网络中的设备，那么端口号就可以唯一标识
设备中的应用程序了。也就是应用程序的标识。

协议:

·通过计算机网络可以使多台计算机实现连接，位于同一网络中的计算机在进行连接和通信时需要遵守一定的规则，
这就好比在道路中行驶的汽车一定要遵守交通规则一样。在计算机网络中，这些连接和通信的规则被称为网络通信协议
它对数据的传输格式，传输速率，传输步骤等做了统一规定，通信双方必须同时遵守才能完成数据交换。
常见的协议有UDP协议和TCP协议

IP地址

是网络中设备的唯一标识

IP地址分类两大类:

IPv4：是给每个连接在网络上的主机分配一个32bit地址。按照TCP/IP规定，IP地址用二进制来表示，每个IP地址长32bit
也就是4个字节。例如一个采用二进制形式的IP地址是"11000000 10101000 00000001 01000010",这么长的地址，处理
起来也太费劲了。为了方便使用，IP地址通常被写成十进制的形式，中间使用符号".“分隔不同的字节
于是，上面的IP地址可以表示为"192.168.1.66”。IP地址的这种表示法叫做"点分十进制表示法"，这显然比1和0容易记忆得多

IPv6：由于互联网的蓬勃发展，IP地址的需求量越来越大，但是网络地址资源有限，使得IP的分配越发紧张。
为了扩大地址空间，通过IPv6重新定义地址空间，采用128位地址长度，每16字节一组，分成8组十六进制数，这样就解决了网络
地址资源数量不够的问题

IP地址

常用命令:

ipconfig:查看本机IP地址
ping IP地址:检查网络是否联通

特殊IP地址:

127.0.0.1：是回送地址，可以代表本机地址，一般来测试使用

InetAddress的使用

为了方便我们对IP地址的获取和操作，Java提供了一个类InetAddress供我们使用

InetAddress:此类表示Internet协议(IP)地址

           方法名                            说明

static InetAddress getByName(String host)
确定主机名称的IP地址。主机名称可以是机器名称，也可以是IP地址

String getHostName() 获取此IP地址的主机名

String getHostAddress() 返回文本显示的IP地址字符串

import java.net.InetAddress;
import java.net.UnknownHostException;

public class day4InetAddress的使用 {
    public static void main(String[] args) throws UnknownHostException {
        //static InetAddress getByName(String host)    确定主机名称的IP地址。主机名称可以是机器名称，也可以是IP地址
        InetAddress address = InetAddress.getByName("192.168.1.101");
        // String getHostName()]获取此IP地址的主机名
        String name = address.getHostName();
        // String getHostAddress() 返回文本显示的IP地址字符串
        String ip = address.getHostAddress();
        System.out.println("主机名："+name);
        System.out.println("ip地址: "+ip);
    }
}

端口

设备上应用程序的唯一标识

端口号:用两个字节表示的整数，它的取值范围是0-65535,。其中，0~1023之间的端口号用于一些知名的网络服务和应用，普通的应用程序需要使用1024以上的端口号。如果端口号被另外一个服务或应用所占用，会导致当前程序启动失败

协议

协议:计算机网络中，连接和通信的规则被称为网络通信协议

UDP协议:

·用户数据报协议(User Datagram Protocol)
·UDP是无连接通讯协议，即在数据传输时，数据的发送端和接收端不建立逻辑联系。简单来说，当一台
计算机向另外一台计算机发送数据时，发送端不会确认接收端是否存在，就会发出数据，同样接收端在收到数据时
也不会向发送端反馈是否收到数据
由于使用UDP协议消耗资源少，通信效率高，所以通常都会用于音频，视频和普通数据的传输
·例如视频会议通常采用UDP协议，因为这种情况即使偶尔丢失一两个数据包，也不会对接收结果产生
太大影响。但是在使用UDP协议传输数据时，由于UDP的面向无连接性，不能保证数据的完整性，因此在传输重要数据时不建议
使用UDP协议

TCP协议

·传输协议(Transmission Control Protocol)
·TCP协议是面向连接的通信协议，即传输数据之前，在发送端和接收端建立逻辑相连，然后再传输数据，
它提供了两台计算机之间可靠无差错的数据传输。在TCP连接中必须要明确客户端与服务器端，由客户端向
服务器端发出连接请求，每次连接的创建都需要经过"三次握手"

·三次握手

:TCP协议中，在发送数据的准备阶段，客户端和服务器之间的三次交互，以保证连接的可靠
第一次握手:客户端向服务器端发出连接请求，等待服务期确认
第二次握手:服务器端向客户端回送一个响应，通知客户端收到了连接请求
第三次握手:客户端再次向服务器端发送确认信息，确认连接

完成三次握手，连接了建立后，客户端和服务器就可以开始进行数据传输了。由于这种面向连接的
的特性，TCP协议可以保证传输数据的安全，所以应用十分广泛。例如上传文件，下载文件，浏览网页等。

UDP通信原理

UDP协议是一种不可靠的网络协议，它在通信端各建立一个Socket对象，但是这两个Socket只是发送，接受数据的对象

因此基于UDP协议的通信双方而言，没有所谓的客户端和服务器的概念
Java提供了DatagramSocket类作为基于UDP协议的Socket

UDP发送数据

发送数据的步骤

①创建发送端的Socket对象(DatagramSocket)
②创建数据，并把数据打包
③调用DatagramSocket对象的方法发送数据
④关闭发送端

import java.io.IOException;
import java.net.*;
import java.nio.charset.StandardCharsets;

public class day1UDP发送数据 {
    public static void main(String[] args) throws IOException {
        //①创建发送端的Socket对象(DatagramSocket)
        //DatagramSocket()
        //构建一个数据报套接字绑定到本地主机的任何可用的端口。
        DatagramSocket ds = new DatagramSocket();
        //②创建数据，并把数据打包
        //DatagramPacket(byte[] buf, int length, InetAddress address, int port)
        //指定主机上的指定端口发送数据包的长度 length数据报包结构。
        byte[] bys = "hello,udp,我来了".getBytes();
//        int length = bys.length;
//        InetAddress address = InetAddress.getByName("192.168.1.66");
//        int port = 10086;
        DatagramPacket dp = new DatagramPacket(bys,bys.length,InetAddress.getByName("192.168.1.66"),10086);
        //③调用DatagramSocket对象的方法发送数据
        //public void send(DatagramPacket p) 从这个套接字发送数据报包。
        ds.send(dp);
        //④关闭发送端
        ds.close();//close() 关闭该数据报套接字。
    }
}

UDP接收数据

接收数据的步骤

①创建接收端的Socket对象(DatagramSocket)
②创建一个数据包，用于接收数据
③调用DatagramSocket对象的方法接收数据
④解析数据包，并把数据在控制台显示
⑤关闭接收端

先接收，后发送

import java.io.IOException;
import java.net.DatagramPacket;
import java.net.DatagramSocket;
import java.net.SocketException;

public class day2UDP接收数据 {
    public static void main(String[] args) throws IOException {
        //①创建接收端的Socket对象(DatagramSocket)
        //DatagramSocket(int port)
        //构建一个数据报套接字绑定到本地主机的指定端口。
        DatagramSocket ds = new DatagramSocket(10086);
        //②创建一个数据包，用于接收数据
        //DatagramPacket(byte[] buf, int length)
        //接收数据包长度 length DatagramPacket构建。
        byte[] bys = new byte[1024];
        DatagramPacket dp = new DatagramPacket(bys,bys.length);
        //③调用DatagramSocket对象的方法接收数据
        ds.receive(dp);
        //④解析数据包，并把数据在控制台显示
        //getData()
        //返回数据缓冲区。
        byte[] datas = dp.getData();
        int len = dp.getLength();
//        String dataString = new String(datas,0,len);
//        System.out.println("数据是:"+dataString);
        System.out.println("数据是:"+new String(datas,0,len));
        //⑤关闭接收端
        ds.close();
    }
}

TCP通信原理

TCP通信协议是一种可靠的网络协议，它在通信的两端各建立一个Socket对象，从而在通信的两端形成网络虚拟链路

一旦建立了虚拟的网络链路，两端的程序就可以通过虚拟链路进行通信
Java对基于TCP协议的网络提供了良好的封装，使用Socket对象来代表两端的通信端口，并通过Socket产生io流来进行网络通信

Java为客户端提供了Socket类，为服务器端提供了ServerSocket类

TCP发送数据

发送数据的步骤：

①创建客户端的Socket对象(Socket)
②获取输出流，写数据
③释放资源

import java.io.IOException;
import java.io.OutputStream;
import java.net.InetAddress;
import java.net.Socket;
import java.net.UnknownHostException;
import java.nio.charset.StandardCharsets;

public class day2TCP发送数据 {
    public static void main(String[] args) throws IOException {
        //①创建客户端的Socket对象(Socket)
        //Socket(InetAddress address, int port)
        //创建一个流套接字，并将其与指定的IP地址中的指定端口号连接起来。

        //Socket s = new Socket(InetAddress.getByName("192.168.1.101"),10000);

        //Socket(String host, int port)
        //创建一个流套接字，并将其与指定的主机上的指定端口号连接起来。
        Socket s = new Socket("192.168.1.101",10000);
        //获取输出流，写数据
        //getOutputStream()
        //返回此套接字的输出流。
        OutputStream os = s.getOutputStream();
        os.write("hello,tcp,扬哥来啦".getBytes());
        //释放资源
        s.close();
    }
}

TCP接收数据

接收数据的步骤：

①创建服务器端的Socket对象(ServerSocket)
②监听客户端连接，返回一个Socket对象
③获取输入流，读数据，并把数据显示在控制台
③释放资源

import java.io.IOException;
import java.io.InputStream;
import java.net.ServerSocket;
import java.net.Socket;

public class day3TCP接收数据 {
    public static void main(String[] args) throws IOException {
        //①创建服务器端的Socket对象(ServerSocket)
        //ServerSocket(int port)
        //创建一个服务器套接字，绑定到指定的端口。
        ServerSocket ss = new ServerSocket(10000);
        Socket s = ss.accept();
        //②监听客户端连接，返回一个Socket对象
        //accept()
        //监听要对这个套接字作出的连接并接受它。
        //③获取输入流，读数据，并把数据显示在控制台
        InputStream is = s.getInputStream();
        byte[] bys = new byte[1024];
        int len = is.read(bys);
        String data = new String(bys,0,len);
        System.out.println("数据是:"+data);
        //释放资源
        s.close();
        ss.close();
    }
}

MySQL

Created2021-12-19Updated2021-12-19

1、初始MySQL

JavaEE:企业级开发 web

前端(页面:展示，数据!)

后台(连接点:连接数据库JDBC，连接前端（控制，控制试图跳转，和给前端传递数据）)

数据库（存数据，TXT，Excel，Word）

只会写代码，学好数据库，基本混饭吃；

操作系统，数据结构与算法，当一个不错的程序猿！

离散数学，数字电路，体系结构，编译原理，实战经验，优秀程序猿

1.1、为什么学习数据库

1、岗位需求
2、现在的世界，大数据时代~，得数据者得天下
3、被迫需求：存数据
4、数据库是所有软件体系中最核心的存在 DBA

1.2、什么是数据库

数据库(DB DataBase)

概念：数据仓库，软件，安装在操作系统(windows,linux,mac…)之上，SQL，可以存储大量数据。500万以内。

作用：存储数据，管理数据

1.3、数据库分类

关系型数据库：（SQL）

MySQL、Oracle、SQL Server，DB2、SQLlite
通过表和表之间，行和列之间的关系进行数据的存储。学员表，考勤表…

非关系型数据库：（NoSQL）Not only SQL

Redis，MongoDB
非关系型数据库，对象存储，通过对象的自身属性来决定。

DBMS（数据库管理系统）

数据库的管理软件，科学有效的管理我们的数据。维护和获取数据
MySQL，数据库管理系统！

1.4、MySQL

MySQL是一个关系型数据库管理系统

前世：瑞典MySQL AB公司

今生：属于Oracle旗下产品

MySQL是最好的 RDBMS (Relational Database Management System，关系数据库管理系统) 应用软件之一

开源的数据库软件~

体积小，速度快，总体应用成本低，招人成本比较低，所有人必须会

中小型网站、或者大型网站，集群

官网：https://www.mysql.com

5.7 稳
8.0 用的还不是很多

安装建议：
1、尽量不要使用exe，注册表
2、尽可能使用压缩包

1.5、安装MySQL

详细过程点这里
1.解压
2.把这个包放到自己的电脑环境目录下
3.配置环境变量
4.新建MySQL配置文件 ini结尾

[mysqld]
#目录一定要换成自己的
basedir=D:\MySQL5.7\mysql-5.7.19-winx64\
datadir=D:\MySQL5.7\mysql-5.7.19-winx64\data\
port=3307
skip-grant-tables

5.启动管理员模式下的cmd，运行所有的命令
6.安装MySQL服务
7.初始化数据库文件
8.启动MySQL，进去修改密码
9.进入MySQL通过命令行（-p后面不要加空格），修改密码（sql语句后面一定要加分号）

问题：

1、缺少组件 .dll
2、命令输出

1	sc delete mysql

1.6、安装SQLyog

1.无脑安装
2.注册
3.打开连接数据库
4.新建一个数据库 school
每一个sqlyog的执行操作，本质就是对应了一个sql，可以在软件的历史记录中查看
5.新建一张表 student

1	字段:id,name,age

在这里插入图片描述
6.查看表
7.自己尝试添加多条记录

1.7、连接数据库

命令行连接

mysql -u root -p123456 --连接数据库
update mysql.user set authentication_string=password('123456') where user='root' and Host = 'localhost'; --修改用户密码
flush privileges; --刷新权限
------------------------------------------------
--所有的语句都使用分号结尾
show databases; --查看所有的数据库
mysql> use school;  --切换数据库
Database changed
show tables; --查看数据库中所有的表
describe student; --显示数据库中所有的表的信息
create database westos; --创建一个数据库
exit; --退出链接
--单行注释
/*（sql的多行注释）
hello
world
mysql
*/

数据库 xxx 语言 CRUD 增删改查！ CV 程序猿 API程序猿 CRUD程序猿（业务）
DDL 定义
DML 操作
DQL 查询
DCL 控制

2、操作数据库（了解）

操作数据库>操作数据库中的表>操作数据库中表的数据

MySQL语句不区分大小写

2.1、操作数据库

1、创建数据库

1	CREATE DATABASE (IF NOT EXISTS) westos;

2、删除数据库

1	DROP DATABASE (IF EXISTS) hello；

3、使用数据库

1 2	--tab键的上面，如果你的表名或者字段名是一个特殊字符，就需要带 USE `westos`

4、查看数据库

1	SHOW DATABASES --查看所有的数据库

对比：sqlyog的可视化操作

2.2、数据库的列类型

数值

tinyint 十分小的数据 1个字节
smallint 较小的数据 2个字节
mediumint 中等大小的数据 3个字节
int 标准的整数 4个字节 常用的
bigint 较大的数据 8个字节
float 单精度浮点数 4个字节
double 双精度浮点数 8个字节
decimal 字符串形式的浮点数 金融计算的时候，一般使用

字符串

char 字符串固定大小的 0-255
varchar 可变字符串 0-65535
tinytext 微型文本 2^8-1
text 文本串 2^16-1

事件日期

java.util.Date

date YYYY-MM-DD，日期
time HH：mm：ss 时间格式
datetime YYYY-MM-DD HH：mm：ss 最常用的时间格式
timestamp 时间戳 1970.1.1到现在的毫秒数！也较为常用
year 年份标识

null

没有值，未知
注意，不要使用null进行运算，结果为null

2.3、数据库的字段属性（重点）

Unsigned：

无符号的整数
声明了该列不能为负数

zerofill：

0填充的
不足的位数，使用0来填充，in（3），5,005

自增：

通常理解为自增，自动在上一条记录的基础上+1（默认）
通常用来设计唯一的住建~index，必须是整数类型
可以自定义设置主键自增的起始值和步长

非空:

NUll 和 not null

假设设置为not null，如果不给他赋值，就会报错
NUll，如果不填写值，默认就是null

默认：

设置默认值
sex，默认值为男，如果不指定该列的值，则会有默认的值！

扩展：目前看看就行

/*每一个表都必须存在以下五个字段
id 主键
`version` 乐观锁
is_delete 伪删除
gmt_create 创建时间
gmt_update 修改时间
*/

2.4、创建数据库表

-- 目标：创建一个school数据库
-- 创建学生表(列，字段) 使用SQL创建
-- 学号int 登录密码varchar(20) 姓名，性别varchar(2),出生日期()
-- 注意点，使用英文()，表的名称 和 字段 尽量使用``括起来
-- AUTO_INCREMENT 自增
-- 字符串使用单引号括起来
-- 所有的语句后面加逗号 英文的 最后一个不用加
-- PRIMARY KEY 主键 一般一个表只有一个
CREATE DATABASE school
CREATE TABLE IF NOT EXISTS `student` (
	`id` INT(4) NOT NULL AUTO_INCREMENT COMMENT '学号',
	`name` VARCHAR(30) NOT NULL DEFAULT '匿名' COMMENT '姓名',
	`pwd` VARCHAR(20) NOT NULL DEFAULT '123456' COMMENT '密码',
	`sex` VARCHAR(2) NOT NULL DEFAULT '女' COMMENT '性别',
	`birthday` DATETIME DEFAULT NULL COMMENT '出生日期',
	`address` VARCHAR(100) DEFAULT NULL COMMENT '家庭住址',
	`email` VARCHAR(50) DEFAULT  NULL COMMENT '邮箱',
	PRIMARY KEY(id)
)ENGINE=INNODB DEFAULT CHARSET=utf8

格式：

create table[if not exists] `表名`(
`字段名` 列类型 [属性][索引][注释],
`字段名` 列类型 [属性][索引][注释],
.......
`字段名` 列类型 [属性][索引][注释],
)[表类型][字符集][注释]

常用命令

1
2
3

SHOW CREATE DATABASE school -- 查看创建数据库的语句
SHOW CREATE TABLE student -- 查看student数据表的定义语句
DESC student -- 显示表的结构

2.5、数据库表的类型

INNODB 默认使用
MYISAM 早些年使用

	MYISAM	INNODN
事务支持	不支持	支持
数据行锁定	不支持	支持
外键约束	不支持	支持
全文索引	支持	不支持
表空间大小	较小	较大，约为2倍

常规使用操作：

MYISAM 节约空间，速度较快
INNODB 安全性高，事务的处理，多表多用户操作

在物理空间存在的位置

所有的数据库文件都存在data目录下，一个文件夹就对应一个数据库
本质还是文件的存储
MySQL引擎在物理文件上的区别

INNODB在数据库表中只有一个*.frm文件，以及上级目录下的ipdata1文件

MYISAM对应文件

 ○*.frm     表结构定义文件
 ○*.MYD 数据文件(data)
 ○*.MYI   索引文件(index)

设置数据库表的字符集编码

1	charset=utf8

不设置的话，会是MySQL默认的字符集编码（不支持中文）

MySQL的默认编码是Latin1，不支持中文

在my.ini中配置默认的编码

1	character-set-server=utf8

2.6、修改和删除

修改

删除

GUI编程

Created2021-12-19Updated2021-12-19

1、简介

GUI的核心技术: Swing AWT，界面不美观

不流行的原因：

因为界面不美观
需要JRE环境

为什么我们要学习？

可以写出自己心中想要的小工具
工作时候也可能维护swing界面
了解MVC架构，了解监听

2、AWT

2.1、AWT介绍

包含了很多类和接口！GUI！
元素：窗口，按钮，文本窗
java.awt

2.2、组件和容器

1.Frame

package GUI.lesson1;

//GUI的第一个界面

import java.awt.*;

public class TestFrame {
    public static void main(String[] args) {
        //Frame,JDK
        Frame frame = new Frame("我的第一个Java图形界面窗口");
        //需要设置可见性
        frame.setVisible(true);
        //设置窗口大小
        frame.setSize(400,400);
        //设置背景颜色 Color
        frame.setBackground(new Color(69, 108, 41));
        //弹出的初始位置
        frame.setLocation(200,200);
        //设置大小固定
        frame.setResizable(false);
    }
}

回顾封装:

package GUI.lesson1;

import java.awt.*;

public class TestFrame2 {
    public static void main(String[] args) {
        //展示多个窗口
        MyFrame myFrame1 = new MyFrame(100, 100, 200, 200, Color.blue);
        MyFrame myFrame2 = new MyFrame(300, 100, 200, 200, Color.yellow);
        MyFrame myFrame3 = new MyFrame(100, 300, 200, 200, Color.red);
        MyFrame myFrame4 = new MyFrame(300, 300, 200, 200, Color.MAGENTA);
    }
}
class MyFrame extends Frame{
    static int id = 0; //可能有多个窗口，我们需要一个计数器
    public MyFrame(int x,int y,int w,int h,Color color){
        super("MyFrame"+(++id));
        setBackground(color);
        setBounds(x,y,w,h);
        setVisible(true);
    }
}

在这里插入图片描述

2.面板Panel

解决了关闭事件

package GUI.lesson1;

//Panel 可以看成是一个空间，但是不能单独存在

import java.awt.*;
import java.awt.event.WindowAdapter;
import java.awt.event.WindowEvent;

public class TestPanel {
    public static void main(String[] args) {
        Frame frame = new Frame();
        //布局的概念
        Panel panel = new Panel();
        //设置布局
        frame.setLayout(null);
        //坐标
        frame.setBounds(300,300,500,500);
        frame.setBackground(new Color(0x81CE90));
        //panel设置坐标，相对于frame
        panel.setBounds(50,50,400,400);
        panel.setBackground(new Color(0xDBE04452, true));
        //frame.add(panel)
        frame.add(panel);

        frame.setVisible(true);
        //监听事件，监听窗口关闭事件 System.exit(0)
        //适配器模式
        frame.addWindowListener(new WindowAdapter() {
            //窗口点击关闭时候需要做的事情
            @Override
            public void windowClosing(WindowEvent e) {
                //结束程序
                System.exit(0);
            }
        });
    }
}

在这里插入图片描述

2.3、布局管理器

流式布局

package GUI.lesson1;

import java.awt.*;

public class TestFlowLayout {
    public static void main(String[] args) {
        Frame frame = new Frame();
        //组件-按钮
        Button button1 = new Button("button1");
        Button button2 = new Button("button2");
        Button button3 = new Button("button3");
        //设置为流式布局
//        frame.setLayout(new FlowLayout());
        frame.setLayout(new FlowLayout(FlowLayout.LEFT));
        frame.setSize(200,200);
        frame.setVisible(true);
        //把按钮添加上去
        frame.add(button1);
        frame.add(button2);
        frame.add(button3);
    }
}

东西南北中

package GUI.lesson1;

import java.awt.*;

public class TestBorderLayout {
    public static void main(String[] args) {
        Frame frame = new Frame("TestBorderLayout");
        Button east = new Button("east");
        Button west = new Button("west");
        Button south = new Button("south");
        Button north = new Button("north");
        Button center = new Button("center");
        frame.add(east,BorderLayout.EAST);
        frame.add(west,BorderLayout.WEST);
        frame.add(center,BorderLayout.CENTER);
        frame.add(south,BorderLayout.SOUTH);
        frame.add(north,BorderLayout.NORTH);
        frame.setSize(200,200);
        frame.setVisible(true);
    }
}

表格布局

package GUI.lesson1;

import java.awt.*;
import java.awt.event.WindowAdapter;
import java.awt.event.WindowEvent;

public class TestGridLayout {
    public static void main(String[] args) {
        Frame frame = new Frame("TestBorderLayout");

        Button btn1 = new Button("btn1");
        Button btn2 = new Button("btn2");
        Button btn3 = new Button("btn3");
        Button btn4 = new Button("btn4");
        Button btn5 = new Button("btn5");
        Button btn6 = new Button("btn6");

        frame.setLayout(new GridLayout(3,2));

        frame.add(btn1);
        frame.add(btn2);
        frame.add(btn3);
        frame.add(btn4);
        frame.add(btn5);
        frame.add(btn6);

        frame.pack();//自动布局
        frame.setVisible(true);

        frame.addWindowListener(new WindowAdapter() {
            @Override
            public void windowClosing(WindowEvent e) {
                System.exit(0);
            }
        });
    }
}

练习

在这里插入图片描述
在每块空格处加上按钮

package GUI.lesson1;

import javax.swing.*;
import java.awt.*;
import java.awt.event.WindowAdapter;
import java.awt.event.WindowEvent;
import java.awt.event.WindowListener;

public class Work {
    public static void main(String[] args) {
        //总frame窗 上下两层
        Frame yang = new Frame("Yang");
        yang.setVisible(true);
        yang.setSize(400,300);
        yang.setLocation(300,400);
        yang.setBackground(Color.CYAN);
        yang.setLayout(new GridLayout(2,1));
        //4个面板
        Panel p1 = new Panel(new BorderLayout());
        Panel p2 = new Panel(new GridLayout(2,1));
        Panel p3 = new Panel(new BorderLayout());
        Panel p4 = new Panel(new GridLayout(2,2));
        p1.add(new Button("East-1"),BorderLayout.EAST);
        p1.add(new Button("West-1"),BorderLayout.WEST);
        p2.add(new Button("p2-btn-1"));
        p2.add(new Button("p2-btn-2"));

        p1.add(p2,BorderLayout.CENTER);

        p3.add(new Button("East-2"),BorderLayout.EAST);
        p3.add(new Button("West-2"),BorderLayout.WEST);
        for (int i = 0; i < 4; i++) {
            p4.add(new Button("for-"+i));
        }
        p3.add(p4,BorderLayout.CENTER);

        yang.add(p1);
        yang.add(p3);

        yang.addWindowListener(new WindowAdapter() {
            @Override
            public void windowClosing(WindowEvent e) {
                System.exit(0);
            }
        });
    }
}

在这里插入图片描述
总结：

1.Frame是一个顶级窗口
2.Panel 无法单独显示，必须添加到某个容器中
3.布局管理器
1.流式布局
2.东西南北中
3.表格布局

2.4、事件监听

事件监听:当某个事情发生的时候，干什么？

package GUI.lesson2;

import java.awt.*;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.event.WindowAdapter;
import java.awt.event.WindowEvent;

public class TestActionEvent {
    public static void main(String[] args) {
        //按下按钮，触发一些事件
        Frame frame = new Frame();
        Button button = new Button();
        //因为addActionListener()需要一个ActionListener，所以我们需要构造一个ActionListener
        MyActionListener myActionListener = new MyActionListener();
        button.addActionListener(myActionListener);
        frame.add(button,BorderLayout.CENTER);
        frame.pack();
        frame.setVisible(true);
        windowClose(frame);
    }
    //关闭窗体的事件
    private static void windowClose(Frame frame){
        frame.addWindowListener(new WindowAdapter() {
            @Override
            public void windowClosing(WindowEvent e) {
                System.exit(0);
            }
        });
    }
}
//事件监听
class MyActionListener implements ActionListener{

    @Override
    public void actionPerformed(ActionEvent e) {
        System.out.println("aaa");
    }
}

多个按钮共享一个事件

package GUI.lesson2;

import java.awt.*;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;

public class TestActionTwo {
    public static void main(String[] args) {
        //两个按钮,实现同一个监听
        //开始 停止
        Frame frame = new Frame("开始-停止");
        Button button1 = new Button("start");
        Button button2 = new Button("stop");

        button2.setActionCommand("button-stop");

        MyMonitor myMonitor = new MyMonitor();
        button1.addActionListener(myMonitor);
        button2.addActionListener(myMonitor);

        frame.add(button1,BorderLayout.NORTH);
        frame.add(button2,BorderLayout.SOUTH);
        frame.pack();
        frame.setVisible(true);
    }
}
class MyMonitor implements ActionListener{

    @Override
    public void actionPerformed(ActionEvent e) {
        //
        System.out.println("按钮被点击了:msg"+e.getActionCommand());
    }
}

2.5、输入框TextField

package GUI.lesson2;

import java.awt.*;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;

public class TestText01 {
    public static void main(String[] args) {
        //启动
        new MyFrame();
    }
}
class MyFrame extends Frame{
    public MyFrame(){
        TextField textField = new TextField();
        add(textField);
        //监听这个文本框输入的文字
        MyActionListener2 my2 = new MyActionListener2();
        textField.addActionListener(my2);
        //设置替换编码
        textField.setEchoChar('*');
        pack();
        setVisible(true);
    }
}
class MyActionListener2 implements ActionListener{

    @Override
    public void actionPerformed(ActionEvent e) {
        TextField field = (TextField) e.getSource();//获得一些资源,返回一个对象
         //获得输入框中的文本
        System.out.println(field.getText());
        field.setText("");//null
    }
}

2.6、简易计算器，组合内部类回顾复习

目前代码

package GUI.lesson2;

//简易计算器

import java.awt.*;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;

public class TestCalc {
    public static void main(String[] args) {
        new Caculator();
    }
}
//计算器类
class Caculator extends Frame{
    public Caculator(){
        //3个文本框
        TextField num1 = new TextField(10);//字符数
        TextField num2 = new TextField(10);//字符数
        TextField num3 = new TextField(20);//字符数
        //1个按钮
        Button button = new Button("=");
        button.addActionListener(new MyCalculatorListener(num1,num2,num3));
        //1个标签
        Label label = new Label("+");
        //布局
        setLayout(new FlowLayout());
        add(num1);
        add(label);
        add(num2);
        add(button);
        add(num3);

        pack();
        setVisible(true);
    }
}
//监听器类
class MyCalculatorListener implements ActionListener{

    private TextField num1,num2,num3;
    public MyCalculatorListener(TextField num1,TextField num2,TextField num3){
        this.num1 = num1;
        this.num2 = num2;
        this.num3 = num3;
    }
    @Override
    public void actionPerformed(ActionEvent e) {
        //1.获得加数和被加数
        int n1 = Integer.parseInt(num1.getText()); //String类型
        int n2 = Integer.parseInt(num2.getText()); //String类型
        //2.将这两个值加法运算后放到第三个框
        num3.setText(""+(n1+n2));
        //3.清楚前两个框
        num1.setText("");
        num2.setText("");
    }
}

1023 组个最小数 (20 分

Created2021-12-19Updated2021-12-19

给定数字 0-9 各若干个。你可以以任意顺序排列这些数字，但必须全部使用。目标是使得最后得到的数尽可能小（注意 0 不能做首位）。例如：给定两个 0，两个 1，三个 5，一个 8，我们得到的最小的数就是 10015558。

现给定数字，请编写程序输出能够组成的最小的数。

输入格式：

输入在一行中给出 10 个非负整数，顺序表示我们拥有数字 0、数字 1、……数字 9 的个数。整数间用一个空格分隔。10 个数字的总个数不超过 50，且至少拥有 1 个非 0 的数字。

输出格式：

在一行中输出能够组成的最小的数。

输入样例：

1
2
3

2 2 0 0 0 3 0 0 1 0

结尾无空行

输出样例：

1
2
3

10015558

结尾无空行

题解：

z = {}
scan = list(map(int,input().split()))
if scan[0] != 0:
    for i in range(1,10):
        if scan[i] != 0:
            print(i,end='')
            flag = i
            break
    for i in range(0,10):
        if i!=flag:
            for j in range(0,scan[i]):
                print(i,end='')
        else:
            for j in range(0,scan[i]-1):
                print(i,end='')
else:
    for i in range(0,10):
        for j in range(0,scan[i]):
            print(i,end='')

1022 D进制的A+B (20 分)

Created2021-12-19Updated2021-12-19

输入两个非负 10 进制整数 A 和 B (≤2^30−1)，输出 A+B 的 D (1<D≤10)进制数。

输入格式：

输入在一行中依次给出 3 个整数 A、B 和 D。

输出格式：

输出 A+B 的 D 进制数。

输入样例：

123 456 8

输出样例：

题解：

#include<stdio.h>
int main(){
	int a,b,num,d,i=0;
	scanf("%d %d %d",&a,&b,&d);
	num = a + b;
	int arr[100];
	while(num>=d){
		arr[i] = num%d;
		num /= d;
		i++;
	}
	arr[i] = num%d;
	for(int j = i;j>=0;j--){
		printf("%d",arr[j]);
	}
	return 0;
}