精华内容
下载资源
问答
  • 数据结构

    2019-05-14 00:06:55
    但是在物理结构上并不一定是连续,线性表在物理存储,通常以数组和链式结构的形式存储。 2.顺序表 顺序表是用一段物理地址连续存储单元依次存储数据元素线性结构一般情况下采用数组存储。在数组上完成数据...

    1.线性表
    线性表是n个具有相同特征的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、队列、字符串…
    线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理存储时,通常以数组和链式结构的形式存储。
    2.顺序表
    顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删改查。
    顺序表一般可以分为:

    1. 静态顺序表:使用定长数组存储。顺序表的容量,实在静态时期确定(编译期间,代码里写死)
    typedef struct SeqList {
    	int array[100];  // 容量是 100
    	int size;  // 顺序表实际存储的数据个数
    }   SeqList;
    
    1. 动态顺序表:使用动态开辟的数组存储。容量在动态时期确定(运行时期)
    typedef struct SeqList {
    	int *array;  // 指向动态开辟的数组
    	int capacity;  // 容量
    	int size;  // 1. 有效数据的个数
    	           // 2. 尾插时,可用位置的下标
    }   SeqList;
    

    接口实现:静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组定大了,空间开多了浪费,开少了不够用。所以现实中基本都是使用动态顺序表,根据需要动态的分配空间大小,所以下面我们实现动态顺序表。

    // 初始化
    void SeqListInit(SeqList *ps, int capacity);
    
    
    // 销毁
    void SeqListDestroy(SeqList *ps);
    

    增、删、改、查

    // 尾插
    void SeqListPushBack(SeqList *ps, int v);
    // 头插
    void SeqListPushFront(SeqList *ps, int v);
    // 根据 pos 下标做插入
    void SeqListInsert(SeqList *ps, int pos, int v);
    
    // 尾删
    void SeqListPopBack(SeqList *ps);
    // 头删
    void SeqListPopFront(SeqList *ps);
    // 根据 pos 下标做删除
    void SeqListErase(SeqList *ps, int pos);
    
    // 查找
    int SeqListFind(SeqList *ps, int v);
    
    // 更新
    int SeqListModify(SeqList *ps, int pos, int v);
    
    // 删除第一个遇到的 v
    void SeqListRemove(SeqList *ps, int v);
    // 删除所有遇到的 v
    void SeqListRemoveAll(SeqList *ps, int v);
    

    注意

    1. 中间/头部的插入删除,时间复杂度为O(N);
    2. 增容需要申请新空间,拷贝数据,释放旧空间;
    3. 增容一般是呈 2 倍的增长,势必会有一定的空间浪费。
    展开全文
  • 学习计算机网络我们一般采用五层协议体系结构。 1. 应用层 应用层(application-layer)任务是通过应用进程间交互来完成特定网络应用。 包含主要协议有文件传输协议(FTP)、简单邮件传送协议(SMTP)、...

    五层协议的体系结构

    常见的网络的划分形式有三种协议,划分形式如下图所示:
    在这里插入图片描述
    学习计算机网络时我们一般采用五层协议的体系结构。

    1. 应用层

    应用层(application-layer)的任务是通过应用进程间的交互来完成特定网络应用。 包含的主要协议有文件传输协议(FTP)、简单邮件传送协议(SMTP)、远程登陆协议、域名服务协议(DNS)、网络新闻传送协议(NNTP)和超文本传输协议(HTTP)等。

    2. 运输层

    运输层(transport layer)的主要任务就是负责向两台主机进程之间的通信提供通用的数据传输服务。 由于一台主机可同时运行多个线程,因此运输层有复用和分用的功能。所谓复用就是指多个应用层进程可同时使用下面运输层的服务,分用则是运输层把收到的信息分别交付给上面应用层中的相应进程。

    2.1 运输层协议介绍

    运输层主要使用两种协议:传输控制协议TCP(Transmisson Control Protocol)和用户数据协议UDP(User Datagram Protocol)。

    2.1.1 UDP协议

    UDP协议的特点

    • 无连接;
    • 尽最大努力交付,即不保证可靠交付,因此主机不需要维持复杂的链接状态(这里面有许多参数);
    • 面向报文;
    • 无拥塞控制,因此网络出现拥塞不会使源主机的发送速率降低(对实时应用很有用,如IP电话,实时视频会议等);
    • 支持一对一、一对多、多对一和多对多的交互通信;
    • 首部开销小(只有四个字段:源端口、目的端口、长度、检验和),只有8个字节,比TCP的20个字节的首部要短。

    UDP首部格式
    在这里插入图片描述
    用户数据报UDP有两个字段:数据字段和首部字段。首部很简单,只有8个字节。有四个字段组成,每个字段长度都是2个字节。各个字段的意义如下:

    • 源端口:在需要对方回信时选用。不需要时可用全0。
    • 目的端口:在终点交付报文时必须使用到。
    • 长度:UDP用户数据报的长度,其最小值为8(仅包含首部)。
    • 检验和:检验UDP用户数据报在传输中是否有错,有错就丢弃。

    2.1.2 TCP协议

    TCP协议的特点

    • 面向连接。通信之前必须建立连接;
    • 每一条TCP连接只能有两个端点,每一条TCP连接只能是点对点的(一对一);
    • 提供可靠交付的服务。通过TCP连接传送的数据,无差错、不丢失、不重复、并且按序到达;
    • TCP提供全双工通信。连接建立的双方可以互相发消息,A可以给B发消息,B也可以给A发消息;
    • 面向字节流。TCP中的“流”(stream)指的是流入进程或从进程流出的字节序列。“面向字节流”的含义是:虽然应用程序和TCP的交互是一次一个数据块(大小不等),但TCP把应用程序交下来的数据仅仅看成是一连串的无结构的字节流。
    • 首部开销较大,占20字节。

    TCP首部格式
    在这里插入图片描述
    各个字段的作用与含义:

    • 源端口和目的端口: 各占2个字节,分别写入源端口号和目的端口号。

    • 序号: 占4字节,表示在这个报文段中的第一个数据字节序号。

    • 确认号: 占4字节,是期望收到对方下一个报文段的第一个数据字节的序号。

        若确认号=N,则表明:到序号N-1为止的所有数据都已正确收到。
      
    • 数据偏移: 占4位,它指出TCP报文段的数据起始处距离TCP报文段的起始处有多远。

    • 保留: 占6位,保留为今后使用,但目前应置为0。

    • 标志位: 占6位,他们中有多个位置为1,依次为:URG、ACK、PSH、RST、SYN、FIN。

      • 紧急 URG: 当URG=1,表明紧急指针字段有效,用来保证TCP连接不断中断,并督促上层应用赶快处理这些数据。
      • 确认 ACK: 仅当ACK=1时确认号才有效。当ACK=0时,确认号无效。
      • 推送 PSH: 接收方应尽快将这个报文交给应用层,叫做push。所谓push操作就是指在数据包到达接收端以后,立即传送给应用程序,而不是在缓冲区中排队。
      • 复位 RST: 连接复位,复位因主机崩溃或其他原因而出现的错误连接,也可以用于拒绝非法的分段或拒绝连接请求,这个用处还是比较多的。
      • 同步 SYN: 是一个同步序号,通常与ACK合用用来建立连接,也就是常说的三次握手。
      • 终止 FIN: 用来释放一个连接。当FIN=1时,表明此报文段的发送方的数据已发送完毕,并要求释放运输连接。
    • 窗口: 占2字节。窗口指的是发送报文段的一方的接收窗口。窗口值作为接收方让发送方设置其发送窗口的依据。

    • 检验和: 用于对分段首部和数据进行校验。正常情况下一定为0。

    • 禁止指针: 占2字节。当URG=1,表明紧急指针字段有效,用来保证TCP连接不断中断,并督促上层应用赶快处理这些数据。

    • 选项: 长度可变,最长可达40字节。当没有使用“选项”时,TCP的首部长度是20字节。

    2.1.3 运输层协议使用场景

    UDP的使用场景: UDP由于不保证消息的可靠性,所以UDP适合发送一些消息不需要保证每条都准确无误到达接收者。例如:视频通信。
    TCP的使用场景: 由于TCP能够保证消息的准确性,所有例如游戏信息、文字信息等适用于TCP通信。

    3. 网络层

    网络层(network layer)负责为分组交换网上的不同主机提供通信服务。 在发送数据时,网络层把运输层产生的报文段或用户数据报封装成分组和包进行传送。在TCP/IP体系结构中,由于网络层使用IP协议,因此分组也叫IP数据报,简称数据报。

    网络层的另一个任务就是选择合适的路由,使源主机运输层所传下来的分株,能通过网络层中的路由器找到目的主机。

    4.数据链路层

    数据链路层(data link layer)通常简称为链路层。两台主机之间的数据传输,总是在一段一段的链路上传送的,这就需要使用专门的链路层的协议。 在两个相邻节点之间传送数据时,数据链路层将网络层交下来的IP数据报组装程帧,在两个相邻节点间的链路上传送帧。每一帧包括数据和必要的控制信息(如同步信息,地址信息,差错控制等)。

    5.物理层

    物理层(physical layer)的作用是实现相邻计算机节点之间比特流的透明传送,尽可能屏蔽掉具体传输介质和物理设备的差异。 使其上面的数据链路层不必考虑网络的具体传输介质是什么。在物理层上所传送的数据单位是比特。

    展开全文
  • Java数据结构

    2021-01-17 18:22:55
    但是在物理结构上并不一定是连续,线性表在物理上存储,通常以数组和链式结构的形式存储 顺序表 顺序表是用一段物理地址连续存储单元依次存储数据元素线性结构一般情况下采用数组存储。在数组上完成数据...


    线性表

    线性表是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串…

    线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储

    顺序表

    顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删查改

    示例代码:

    import java.util.Arrays;
    public class MyArrayList {
        private int[] elem;
        private int usedSize;
        public MyArrayList(){
            this.elem = new int[5];
        }
        public MyArrayList(int capacity){
            this.elem = new int[capacity];
        }
        // 打印顺序表
        public void display() {
            for (int i = 0; i < usedSize; i++) {
                System.out.print(this.elem[i]+" ");
            }
            System.out.println();
        }
        //判断是否已满
        public Boolean isFull(){
            if(this.elem.length==this.usedSize){
                return true;
            }
            return false;
        }
        //调整大小
        public void resize(){
            this.elem=Arrays.copyOf(this.elem,2*this.elem.length);
        }
        // 在 pos 位置新增元素
        public void add(int pos, int data) {
            if (isFull()) {
                resize();
            }
            if (pos < 0 || pos >this.usedSize) {
            System.out.println("pos位置不合法!");
            return;
            }
            for (int i = this.usedSize-1; i >= pos ;i--) {
                this.elem[i+1] = this.elem[i];
            }
            this.elem[pos] = data;
            this.usedSize++;
        }
        // 判定是否包含某个元素
        public boolean contains(int toFind) {
            for (int i = 0; i < this.usedSize; i++) {
                if (this.elem[i]==toFind)
                    return true;
            }
            return false;
        }
        // 查找某个元素对应的位置
        public int search(int toFind) {
            for (int i = 0; i < usedSize; i++) {
                if(this.elem[i]==toFind)
                    return i;
            }
            return -1;
        }
        // 获取 int 位置的元素
        public int getPos(int pos) {
            if (pos < 0 || pos >= this.usedSize) {
                return -1;
            }
            return this.elem[pos];
        }
        // 给 pos 位置的元素设为 value
        public void setPos(int pos, int value) {
            if(pos<0||pos>=this.usedSize){
                return ;
            }
            this.elem[pos]=value;
        }
        //删除第一次出现的关键字key
        public void remove(int toRemove) {
            int index = search(toRemove);
            if(index == -1) {
                System.out.println("未找到");
                return;
            }
            for(int i = index;i < this.usedSize-1;i++) {
                this.elem[i] = this.elem[i+1];
            }
                this.usedSize--;
        }
        // 获取顺序表长度
        public int size() {
            return this.usedSize;
        }
        // 清空顺序表
        public void clear() {
            this.usedSize=0;
            System.out.println("已清空!");
        }
    }
    

    链表

    链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的

    单向链表:

    class Node {
        public int data;
        public Node next;
        public Node(){
    
        }
        public Node head;
        public Node(int data){
            this.data = data;
        }
            }
    public class MyLinkList {
        public Node head;
        public Node headA;
        public Node headB;
    
        //输出
        public void display() {
            Node cur = this.head;
            while (cur != null) {
                System.out.print(cur.data + " ");
                cur = cur.next;
            }
            System.out.println();
        }
    
        //任意位置输出
        public void display(Node newHead) {
            Node cur = newHead;
            while (cur != null) {
                System.out.print(cur.data + " ");
                cur = cur.next;
            }
            System.out.println();
        }
    
        //得到长度
        public int size() {
            Node cur = this.head;
            int count = 0;
            while (cur != null) {
                count++;
                cur = cur.next;
            }
            return count;
        }
    
        public int size(Node head) {
            Node cur = head;
            int count = 0;
            while (cur != null) {
                count++;
                cur = cur.next;
            }
            return count;
        }
    
        //头插法
        public void addFirst(int data) {
            Node cur = new Node(data);
            cur.next = this.head;
            this.head = cur;
        }
    
        //尾插法
        public void addLast(int data) {
            Node node = new Node(data);
            if (this.head == null) {
                this.head = node;
            } else {
                Node cur = this.head;
                while (cur.next != null) {
                    cur = cur.next;
                }
                cur.next = node;
            }
        }
    
        public void addLastA(int data) {
            Node node = new Node(data);
            if (this.headA == null) {
                this.headA = node;
            } else {
                Node cur = this.headA;
                while (cur.next != null) {
                    cur = cur.next;
                }
                cur.next = node;
            }
        }
    
        public void addLastB(int data) {
            Node node = new Node(data);
            if (this.headB == null) {
                this.headB = node;
            } else {
                Node cur = this.headB;
                while (cur.next != null) {
                    cur = cur.next;
                }
                cur.next = node;
            }
        }
    
        //找最后一个
        public Node findLastNode() {
            if (this.head == null) {
                System.out.println("链表为空!");
            }
            Node cur = this.head;
            while (cur.next != null) {
                cur = cur.next;
            }
            return cur;
        }
    
        //找倒数第二个
        public Node findTLastNode() {
            if (this.head == null) {
                System.out.println("链表为空!");
            }
            Node cur = this.head;
            while (cur.next.next != null) {
                cur = cur.next;
            }
            return cur;
        }
    
        //找第n个
        public Node findNode(int n) {
            Node cur = this.head;
            if (this.head == null || n <= 0 || n > this.size()) {
                return null;
            }
            int count = 0;
            while (count != n) {
                cur = cur.next;
                count++;
            }
            return cur;
        }
    
        //找key是否存在
        public boolean contains(int key) {
            Node cur = this.head;
            if (cur == null) {
                System.out.println("链表为空!");
            } else {
                cur = cur.next;
            }
            if (cur.data == key)
                return true;
            else
                return false;
        }
    
        //下标为index的节点
        public Node findIndex(int index) {
            if (index < 0 || index > size()) {
                System.out.println("index不合法!");
                return null;
            }
            Node cur = this.head;
            int count = 0;
            while (count != index) {
                count++;
                cur = cur.next;
            }
            return cur;
        }
    
        //任意位置插入,第一个数据节点为0号下标
        public void addIndex(int index, int data) {
            Node node = new Node(data);
            if (index < 0 || index > size()) {
                System.out.println("index不合法!");
            }
            if (index == 0) {
                addFirst(data);
            }
            if (index == size()) {
                addLast(data);
            } else {
                Node cur = findIndex(index);
                node.next = cur.next;
                cur.next = node;
            }
        }
    
        //找key的前驱
        public Node searchPrev(int key) {
            Node cur = this.head;
            if (cur == null) {
                return null;
            }
            while (cur.next != null) {
                if (cur.next.data == key) {
                    return cur;
                }
                cur = cur.next;
            }
            return null;
        }
    
        //删除第一次出现关键字为key的节点
        public void remove(int key) {
            if (this.head == null) {
                return;
            }
            if (this.head.data == key) {
                this.head = this.head.next;
                return;
            }
            Node prev = searchPrev(key);
            if (prev == null) {
                System.out.println("无当前key前驱");
            } else {
                prev.next = prev.next.next;
            }
        }
    
        //删除所有值为key的节点
        public void removeAllKey(int key) {
            Node prev = this.head;
            Node cur = prev.next;
            while (cur != null) {
                if (cur.data == key) {
                    prev.next = cur.next;
                    cur = cur.next;
                } else {
                    prev = cur;
                    cur = cur.next;
                }
            }
            if (this.head.data == key) {
                this.head = this.head.next;
            }
        }
    
        //删除所有值为key的节点2
        public void removeKey(int key) {
            Node p;
            Node q = null;
            for (p = this.head; p != null && p.data != key; q = p, p = p.next) ;
            if (p != null) {
                if (p == this.head) {
                    this.head = this.head.next;
                } else {
                    q.next = p.next;
                }
            }
        }
    
        //反转链表
        public Node reverseList() {
            Node cur = this.head;//cur 代表当前要反转的节点
            Node prev = null;//prev 代表当前需要反转的节点的前驱
            Node newHead = null;
            while (cur != null) {
                Node curNext = cur.next;//curNext 代表当前需要反转的下一个节点
                if (curNext == null) {
                    newHead = cur;
                }
                cur.next = prev;
                prev = cur;
                cur = curNext;
            }
            this.head = newHead;
            return newHead;
    
        }
    
        //反转链表头插法
        public Node reverseList2() {
            Node prev = null;
            while (head != null) {
                Node cur = head;
                head = head.next;
                cur.next = prev;
                prev = cur;
            }
            this.head = prev;
            return prev;
        }
    
        //找到中间节点
        //slow一个一个跑,fast两个两个跑
        public Node middleNode() {
            Node fast = this.head;
            Node slow = this.head;
            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;
            }
            return slow;
        }
    
        //倒数第K个
        public Node findKthToTail(int k) {
            if (head == null || k <= 0) {
                return null;
            }
            Node fast = this.head;
            Node slow = this.head;
            while (k - 1 != 0) {
                if (fast.next != null) {
                    fast = fast.next;
                    k--;
                } else {
                    return null;//k过大
                }
            }
            while (fast.next != null) {
                fast = fast.next;
                slow = slow.next;
            }
            return slow;
        }
        //
    
        //将两个升序合并为一个
        public Node mergeTwoLists(Node headA, Node headB) {
            Node newHead = new Node();
            Node tmp = newHead;
            while (headA != null && headB != null) {
                if (headA.data < headB.data) {
                    tmp.next = headA;
                    headA = headA.next;
                } else {
                    tmp.next = headB;
                    headB = headB.next;
                }
                tmp = tmp.next;
            }
            //代码走到这里肯定是一个为空 一个不为空
            if (headA != null) {
                tmp.next = headA;
            }
            if (headB != null) {
                tmp.next = headB;
            }
            return newHead.next;
        }
    
        //删除重复
        public Node deleteDuplication(Node pHead) {
            if (pHead == null) {
                return null;
            }
            Node newHead = new Node();
            Node tmp = newHead;
            Node cur = pHead;
            while (cur != null) {
                if (cur.next != null && cur.data == cur.next.data) {
                    while (cur.next != null && cur.data == cur.next.data) {
                        cur = cur.next;
                    }
                    cur = cur.next;
                } else {
                    tmp.next = cur;
                    tmp = tmp.next;
                    cur = cur.next;
                }
            }
            tmp.next = null;
            return newHead.next;
        }
    
        //小于K在前,大于K在后
        public Node part(Node pHead, int x) {
            if (pHead == null) {
                return null;
            }
            Node bs = null;
            Node be = null;
            Node as = null;
            Node ae = null;
            Node cur = pHead;
            while (cur != null) {
                if (cur.data < x) {
                    if (bs == null) {
                        bs = cur;
                        be = cur;
                    } else {
                        be.next = cur;
                        be = be.next;
                    }
                } else {
                    if (as == null) {
                        as = cur;
                        ae = cur;
                    } else {
                        ae.next = cur;
                        ae = ae.next;
                    }
                }
                cur = cur.next;
            }
            if (bs == null) {
                return as;
            }
            be.next = as;
            if (as != null) {
                ae.next = null;
            }
            return bs;
        }
    
        //链表的回文结构。
        public boolean palindromeLink() {
            Node be = this.head;
            Node prev = middleNode();
            Node cur = prev.next;
            while (cur != null) {
                Node curNext = cur.next;
                cur.next = prev;
                prev = cur;
                cur = curNext;
            }
            while (be != prev) {
                if (be.data != prev.data) {
                    return false;
                }
                be = be.next;
                prev = prev.next;
                if (be.next == prev) {
                    return true;
                }
            }
            return true;
        }
    
        //输入两个链表,找出它们的第一个公共结点。
        public Node commonNode(Node headA, Node headB) {
            Node ll = headA;
            Node ls = headB;
            if (ll == null || ls == null) {
                return null;
            }
            int lenA = size(headA);
            int lenB = size(headB);
            int len = lenA - lenB;
            if (len < 0) {
                ll = headB;
                ls = headA;
                len = -len;
            }
            while (len != 0) {
                ll = ll.next;
                len--;
            }
            if (ll != ls) {
                ll = ll.next;
                ls = ls.next;
            }
            return ls.next;
        }
    
        //给定一个链表,判断链表中是否有环。
        public boolean hasRing() {
            if (this.head == null) {
                return false;
            }
            Node fast = this.head;
            Node slow = this.head;
            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;
                if (fast == slow) {
                    break;
                }
            }
            if (fast == null || fast.next == null) {
                return false;
            }
            return true;
        }
    
        //给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null
        public Node findRing() {
            if (this.head == null) {
                return null;
            }
            Node fast = this.head;
            Node slow = this.head;
            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;
                if (fast == slow) {
                    break;
                }
            }
            if (fast == null || fast.next == null) {
                return null;
            }
            slow = this.head;
            while (fast != slow) {
                slow = slow.next;
                fast = fast.next;
            }
            return fast;
        }
        
        //删除链表中间key节点  O(1)
        public void delNode(int key) {
            Node cur = this.head;
            while (cur.data != key){
                cur = cur.next;
            }
            cur.data = cur.next.data;
            cur.next = cur.next.next;
        }
        
        //清空
        public void clear(){
            this.head=null;
            System.out.println("null");
        }
    }
    
    

    双向链表:

    class ListNode {
        private int val;
        private ListNode next;
        private ListNode prev;
    
        public ListNode(int val) {
            this.val = val;
        }
    
        public int getVal() {
            return val;
        }
    
        public void setVal(int val) {
            this.val = val;
        }
    
        public ListNode getNext() {
            return next;
        }
    
        public void setNext(ListNode next) {
            this.next = next;
        }
    
        public ListNode getPrev() {
            return prev;
        }
    
        public void setPrev(ListNode prev) {
            this.prev = prev;
        }
    }
    public class DoubleLinkList {
        private ListNode head;
        private ListNode last;
        //打印
        public void display() {
            ListNode cur = this.head;
            while(cur !=null) {
                System.out.print(cur.getVal()+" ");
                cur = cur.getNext();
            }
            System.out.println();
        }
        //得到单链表的长度
        public int size() {
            ListNode cur = this.head;
            int count =0;
            while (cur !=null) {
                count++;
                cur =cur.getNext();
            }
            return count;
        }
        //头插
        public void addFirst(int data) {
            ListNode node = new ListNode(data);
            if(this.head == null) {
                this.head = node;
                this.last = node;
            }else{
                node.setNext(this.head);
                this.head.setPrev(node);
                this.head = node;
            }
        }
        //尾插
        public void addLast(int data) {
            ListNode node = new ListNode(data);
            if(this.head == null) {
                this.head = node;
                this.last = node;
            }else{
                this.last.setNext(node);
                node.setPrev(this.last);
                this.last = node;
            }
        }
        //任意位置插入,第一个数据节点为0号下标
        public void addIndex(int index,int data) {
            if(index < 0||index > size()) {
                return;
            }
            if(index == 0){
                addFirst(data);
                return;
            }
            if(index == size()) {
                addLast(data);
                return;
            }
            ListNode cur =this.head;
            while (index != 0) {
                cur = cur.getNext();
                index--;
                }
            ListNode node = new ListNode(data);
            node.setNext(cur);
            node.setPrev(cur.getPrev());
            cur.getPrev().setNext(node);
            cur.setPrev(node);
        }
        //查找是否包含关键字key是否在单链表当中
        public boolean contains(int key) {
            ListNode cur = this.head;
            while (cur != null) {
                if (cur.getVal() == key) {
                    return true;
                }
                cur = cur.getNext();
            }
            return false;
        }
        //删除第一次出现关键字为key的节点
        public void remove(int key) {
            ListNode cur = this.head;
            while (cur != null) {
                if (cur.getVal() == key) {
                    if (cur == this.head) {
                        this.head = this.head.getNext();
                        this.head.setPrev(null);
                    } else if (cur == this.last) {
                        cur.getPrev().setNext(null);
                        this.last = this.last.getPrev();
                    } else {
                        cur.getPrev().setNext(cur.getNext());
                        cur.getNext().setPrev(cur.getPrev());
                    }
                    return;
                }
                cur = cur.getNext();
            }
        }
        //删除所有值为key的节点
        public void removeAllKey(int key) {
            ListNode cur = this.head;
            while (cur != null) {
                if (cur.getVal() == key) {
                    if (cur == this.head) {
                            this.head = this.head.getNext();
                            if(this.head != null) {
                            this.head.setPrev(null);
                        }
                    } else if (cur == this.last) {
                        cur.getPrev().setNext(null);
                        this.last = this.last.getPrev();
                    } else {
                        cur.getPrev().setNext(cur.getNext());
                        cur.getNext().setPrev(cur.getPrev());
                    }
                }
                cur = cur.getNext();
            }
        }
        //清空
        public void clear() {
            this.head = null;
            this.last = null;
            System.out.println("null");
        }
    }
    
    展开全文
  • 隔离电源按照结构形式不同,可分为两大类:正激式和反激式。反激式指在变压器原边导通副边截止,变压器储能。原边截止,副边导通,能量释放到负载工作状态,一般常规反激式电源单管多,双管不常见。正激式指...
  • 隔离电源按照结构形式不同,可分为两大类:正激式和反激式。反激式指在变压器原边导通副边截止,变压器储能。原边截止,副边导通,能量释放到负载工作状态,一般常规反激式电源单管多,双管不常见。正激式指...
  • 数据结构英文版

    2015-05-12 10:58:27
    系统构造关键因素是数据结构而非算法这一深入理解,导致了多种形式设计方法与编程语言出现。绝大多数语言都带有某种程度上模块化思想,通过将数据结构的具体实现封装隐藏于受限接口之后方法,来让...
  • 大话数据结构

    2019-01-10 16:35:22
    定义其实就是我们在讲解栈提到递归方法。也就是在树定义之中还用到了树概念,这是比较新一种定义方法。 6.2.1结点分类 152 6.2.2结点间关系 152 6.2.3树其他相关概念 153 6.3树抽象数据类型 154...
  • 数据结构——顺序表

    2021-01-15 22:12:28
    但是在物理结构上并不一定是连续,线性表在物理上存储,通常以数组和链式结构的形式存储。 2.顺序表 顺序表是用一段物理地址连续存储单元依次存储数据元素线性结构一般情况下采用数组存储。在数组上完成...

    刚开始接触数据结构,我觉得很难,根本理解不了。现在有了前面的基础,重新去学习,再去理解就容易很多。学完知识,总结知识,会有更深的理解。

    1.线性表

    线性表(linear list)是n个具有相同特性的数据元素的有限序列。

    常见的线性表:顺序表、链表、栈、队列、字符串……

    线性表在逻辑上是线性结构。但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储。
    在这里插入图片描述

    2.顺序表

    顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删查改。
    在这里插入图片描述
    静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了,空间开多了浪费,开少了不够用。所以现实中基本都是使用动态顺序表,根据需要动态的分配空间大小。

    2.1 顺序表接口

    typedef int SLDataType;
    
    typedef struct seqList
    {
    	SLDataType* data;
    	int size;//有效元素个数
    	int capacity;//总容量
    }seqList;
    
    //初始化一个空的顺序表
    void initseqList(seqList* sl);
    
    //尾插
    void seqListPushBack(seqList* sl, SLDataType val);
    
    //检查容量
    void seqListCheckCapacity(seqList* sl);
    
    //尾删
    void seqListPopBack(seqList* sl);
    
    //具体位置的元素
    SLDataType seqListAt(seqList* sl, int pos);
    
    //头插
    void seqListPushFront(seqList* sl, SLDataType val);
    
    //头删
    void seqListPopFront(seqList* sl);
    
    //任意位置插入
    void seqListInsert(seqList* sl, int pos, SLDataType val);
    
    //任意位置删除
    void seqListErase(seqList* sl, int pos);
    
    //打印
    void seqListPrint(seqList* sl);
    
    //销毁
    void seqListDestory(seqList* sl);
    

    2.2 接口实现

    //初始化一个空的顺序表
    void initseqList(seqList* sl)
    {
    	if (sl == NULL)
    		return;
    	sl->data = NULL;
    	sl->size = 0;
    	sl->capacity = 0;
    }
    
    //检查容量
    void seqListCheckCapacity(seqList* sl)
    {
    	if (sl->size == sl->capacity)
    	{
    		int newCapacity = sl->capacity == 0 ? 1 : 2 * sl->capacity;
    		//开辟空间
    		SLDataType* newData = (SLDataType*)malloc(newCapacity*sizeof(SLDataType));
    		//拷贝
    		memcpy(newData, sl->data, sl->size*sizeof(SLDataType));
    		//释放原有空间
    		free(sl->data);
    		sl->data = newData;
    		//改变容量
    		sl->capacity = newCapacity;
    	}
    }
    
    
    //尾插:o(1)
    void seqListPushBack(seqList* sl, SLDataType val)
    {
    	if (sl == NULL)
    	{
    		return;
    	}
    	//检查容量
    	seqListCheckCapacity(sl);
    	//尾插
    	sl->data[sl->size] = val;
    	sl->size++;
    }
    
    //尾删:o(1)
    void seqListPopBack(seqList* sl)
    {
    	if (sl == NULL || sl->size == 0)
    		return;
    	sl->size--;
    }
    
    //具体位置的元素
    SLDataType seqListAt(seqList* sl, int pos)
    {
    	return sl->data[pos];
    }
    
    //顺序表的长度
    int seqListSize(seqList* sl)
    {
    	if (sl == NULL || sl->size == 0)
    		return 0;
    	else
    		return sl->size;
    }
    
    //头插
    void seqListPushFront(seqList* sl, SLDataType val)
    {
    	if (sl == NULL)
    		return;
    	seqListCheckCapacity(sl);
    	int end = sl->size;
    	while (end > 0)
    	{
        	sl->data[end] = sl->data[end - 1];
    		end--;
    	}
    	sl->data[0] = val;
    	sl->size++;
    }
    
    //头删
    void seqListPopFront(seqList* sl)
    {
    	if (sl == NULL || sl->size == 0)
    		return;
    	int start = 1;
    	while (start < sl->size)
        {
    		sl->data[start - 1] = sl->data[start];
    		start++;
    	}
    	sl->size--;
    }
    
    //任意位置插入
    void seqListInsert(seqList* sl, int pos, SLDataType val)
    {
    	if (sl == NULL)
    		return;
    	if (pos >= 0 && pos <= sl->size)
    	{
    		seqListCheckCapacity(sl);
    		int end = sl->size;
    		while (end > pos)
    		{
    			sl->data[end] = sl->data[end - 1];
    			end--;
    		}
    		sl->data[pos] = val;
    		sl->size++;
    	}
    }
    
    //任意位置删除
    void seqListErase(seqList* sl, int pos)
    {
    	if (sl->data == NULL || sl->size == 0)
    		return;
    	if (pos >= 0 && pos < sl->size)
    	{
    		int tmp = pos + 1;
    		while (tmp < sl->size)
    		{
    			sl->data[tmp-1] = sl->data[tmp];
    			tmp++;
    		}
    		sl->size--;
    	}
    }
    
    //销毁
    void seqListDestory(seqList* sl)
    {
    	if (sl != NULL && sl->data != NULL)
    	{
    		free(sl->data);
    		sl->data = NULL;
    	}
    }
    
    //打印
    void seqListPrint(seqList* sl)
    {
    	if (sl == NULL)
    		return;
    	int i = 0;
    	for (i = 0; i < sl->size; i++)
    	{
    		printf("%d ", sl->data[i]);
    	}
    	printf("\n");
    }
    
    展开全文
  • 但在物理结构上并不一定是连续,线性表在物理上存储,通常以数组和链式结构的形式存储。 数组存储结构: 链表存储结构: 2 顺序表 2.1 顺序表概念与结构 顺序表是用一段物理地址连续存储单元依次存储...
  • 但是在物理结构上并不一定是连续,线性表在物 理上存储,通常以数组和链式结构的形式存储。 2. 顺序表 顺序表是用一段物理地址连续存储单元依次存储数据元素线性结构一般情况下采用数组存储。在数组上...
  • 但是在物理结构上并不一定是连续,线性表在物理上存储,通常以数组和链式结构的形式存储。 2.顺序表 概念及结构 顺序表是用一段物理地址连续存储单元依次存储数据元素线性结构一般情况下采用数组存储。在...
  • 大话数据结构 程杰

    2018-09-01 10:06:43
    定义其实就是我们在讲解栈提到递归方法。也就是在树定义之中还用到了树概念,这是比较新一种定义方法。 6.2.1结点分类 152 6.2.2结点间关系 152 6.2.3树其他相关概念 153 6.3树抽象数据类型 154...
  • 但是在物理结构上并不一定是连续,线性表在物 理上存储,通常以数组和链式结构的形式存储。 顺序表 顺序表是用一段物理地址连续存储单元依次存储数据元素线性结构一般情况下采用数组存储。在数组 上完成...
  • 但是在物理结构上并不一定是连续,线性表在物理上存储,通常以数组和链式结构的形式存储。   顺序表:顺序表是用一段物理地址连续存储单元依次存储数据元素线性结构一般情况下采用数组存储。在数组上...
  • 通篇以一种趣味方式来叙述,大量引用了各种各样生活知识来类比,并充分运用图形语言来体现抽象内容,对数据结构所涉及到一些经典算法做到逐行分析、多算法比较。与市场上同类数据结构图书相比,本书内容趣味易...
  • 大话数据结构-程杰

    2014-07-13 23:45:52
    定义其实就是我们在讲解栈提到递归方法。也就是在树定义之中还用到了树概念,这是比较新一种定义方法。 6.2.1 结点分类 152 6.2.2 结点间关系 152 6.2.3 树其他相关概念 153 6.3 树抽象数据...
  • 尽管如此,从目前已经完成的部分来看,数据结构与算法在各领域 知识体系中仍然占据着重要位置。比如在 CE 分卷(草案)中, Programming Fundame ntals 共 39 个核心学时,其中 Algorithms and Problem Solving ...
  • 4.2.1 栈定义 89 4.2.2 进栈出栈变化形式 90 4.3 栈抽象数据类型 91 4.4 栈顺序存储结构及实现 92 4.4.1 栈顺序存储结构 92 4.4.2 栈顺序存储结构进栈操作 93 4.4.3 栈顺序存储结构出栈操作 94 4.5 两...
  • 《数据结构 1800题》

    热门讨论 2012-12-27 16:52:03
    3.数据逻辑结构是指(数据组织形式,即数据元素之间逻辑关系总体。而逻辑关系是指数据元素之间关联方式或称) 。【北京邮电大学 2001 二、1(2分)】 4.一个数据结构在计算机中(表示) 称为存储结构。...

空空如也

空空如也

1 2 3 4 5 ... 16
收藏数 301
精华内容 120
关键字:

一般完成时的结构形式