Java数据结构重点知识有哪些

这篇“Java数据结构重点知识有哪些”文章的知识点大部分人都不太理解，所以小编给大家总结了以下内容，内容详细，步骤清晰，具有一定的借鉴价值，希望大家阅读完这篇文章能有所收获，下面我们一起来看看这篇“Java数据结构重点知识有哪些”文章吧。

成都创新互联公司是一家以网络技术公司，为中小企业提供网站维护、成都网站制作、做网站、网站备案、服务器租用、域名注册、软件开发、微信小程序开发等企业互联网相关业务，是一家有着丰富的互联网运营推广经验的科技公司，有着多年的网站建站经验，致力于帮助中小企业在互联网让打出自已的品牌和口碑，让企业在互联网上打开一个面向全国乃至全球的业务窗口：建站服务热线：18980820575

1 线性表的合并（编程题）

1.1 有序表的合并

算法步骤：

1. 创建表长为m+n的空表LC。

2. 指针pc初始化，指向LC的第一个元素。

3. 指针pa和pb初始化，分别指向LA和LB的第一个元素。

4. 当指针pa和pb均为到达相应表尾时，则依次比较pa和pb所指向的元素值，从LA或LB中摘取元素值较小的结点插入到LC的最后。

5. 如果pb已到达LB的表尾，依次将LA的剩余元素查到LC的最后。

6. 如果pa已到达LA的表尾，依次将LB的剩余元素查到LC的最后。

算法代码：

void MergeList_Sq(SqList LA,SqList LB,SqList &LC){
  LC.length = LA.length+LB.length;  // 新表长度为两表长度之和
  LC.elem = new ElemType[LC.length];  // 为合并后的新表分配空间
  pc = LC.elem;  // 指针pc新表的第一个元素
  pa = LA.elem;  // 指针pa和pb的初值分别指向两个表的第一个元素
  pb = LB.elem;
  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){  // LA和LB均未达到表尾
    if(*pa<=*pb){
      *pc++ = *pa++;  // 依次摘取两表中值较小的结点插入到LC的最后
    }else{
      *pc++ = *pb++;
    }
  }
  while(pa<=pa_last){  // LB到达表尾
    *pc++ = *pa++;
  }
  while(pb<=pb_last){  // LA到达表尾
    *pc++ = *pb++;
  }
}

1.2 链表的合并

算法步骤:

1. 指针pa和pb初始化，分别指向LA和LB的第一个结点

2. LC的结点取值为LA的头结点

3. 指针pc初始化，指向LC的头结点

4. 当指针pa和pb均未到达相应表尾，则依次比较pa和pb所指向的元素值，从LA或LB中摘取元素值较小的结点插入到LC的最后

5. 将非空表的剩余段插入到pc所指结点后。

6. 释放LB的头结点。

算法代码：

void MergeList_L(LinkList &LA,LinkList &LB,LinkList &LC){
  pa = LA->next;  pb=LB->next;  // pa和pb的初值分别指向两个表的第一个结点
  LC=LA;  // 用LA的头结点作为LC的头结点
  pc=LC;  // pc的初值指向LC的头结点
  while(pa&&pb){
    if(pa->data<=pb->data){
      pc->next = pa;  // 将pa所指结点链接到pc所指结点之后
      pc=pa;  // pc指向pa
      pa = pa->next;  // pa指向下一结点
    }else{
      pc->next = pb;  // 将pb所指结点链接到pc所指结点之后
      pc = pb;  // pc指向pb
      pb = pb->next;  // pb指向下一结点
    }
  }
  pc->next = pa?pa:pb;  // 将非空表的剩余段插入到pc所示结点之后
  delete LB;  // 释放LB的头结点
}

2 栈和队列

2.1 栈的基本操作

栈：限定仅在表尾进行插入和删除操作的线性表。

允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)，不含任何数据元素的栈称为空栈。栈又被称为后进先出(Last In First Out)的线性表，简称LIFO结构。

栈的插入操作，叫做进栈，也称压栈、入栈。

栈的删除操作，叫做出栈，有的也叫作弹栈。

2.1.1 入栈、进栈

单栈栈空条件：S->top==-1

单栈栈满条件：S->top==MAXSIZE-1

对于栈的插入，即进栈操作，其实就是做了如下处理：

Status Push(SqStack *S.SElemType e){
    if(S -> top == MAXSIZE -1){ // 栈满
        return ERROR;
    }
    S->top++; // 栈顶指针加一
    S->data[S->top] = e;  // 将新插入元素复制给栈顶空间
    return OK;
}

出栈操作pop，代码如下：

Status Pop(SqStack *S,SElemType *e){
    if(S->top==-1){ // 栈为空
        return ERROR;
    }
    *e = S->data[S->top];  // 将要删除的栈顶元素复制给e
    S->top--;  // 栈顶指针减一
    return OK;
}

2.1.2 共享栈(重要)

栈的顺序存储还是很方便的，因为它只准栈顶进出元素，所以不存在线性表插入和删除时需要移动元素的问题。不过它有一个很大的缺陷，就是必须事先确定数组存储空间大小，万—不够用了，就需要用编程手段来扩展数组的容量，非常麻烦。

共享栈就可以很好的解决这个问题。如果我们有两个相同类型的栈，我们为它们各自开辟了数组空间，极有可能是第—个栈已经满了，再进栈就溢出了，而另一个栈还有很多存储空间空闲，我们完全可以用—个数组来存储两个栈，充分利用这个数组占用的内存空间。

设置数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标为0处，另—个栈为数组的末端，即下标为数组长度n-1处。这样两个栈如果增加元素，就是两端点向中间延伸。

栈空条件：S->top=-1或top[i]=bot[i]

栈满条件：S->top1+1=S->top2

共享栈的结构定义：

typedef struct{
    SElemType data[MAXSIZE];
    int top1; // 栈1栈顶指针
    int top2;  // 栈2栈顶指针
}SqDoubleStack;

2.1.2.1 共享栈进栈

对于共享栈的push方法，除了要插入元素值参数外，还需要有一个参数判断是栈1还是栈2的栈号参数StackNumber。

Status Push(SqDoubleStack *S,SElemType e,int stackNumber){
    if(S->top1+1=S->top2){  // 栈满
        return ERROR;
    }
    if(stackNumber==1){ // 栈1元素进栈
        S->data[++S->top1]=e; // 若是栈1则先top1+1后给数组元素赋值
    }else if(stackNumber==2){ // 栈2元素进栈
        S->data[--S->top2]=e;  // 若是栈2则先top2-1后给数组元素赋值
    }
}

2.1.2.2 共享栈出栈

对于共享栈的pop方法，参数就只是判断栈1栈2的参数stackNumber，代码如下：

Status Pop(SqDoubleStack *S,SElemType *e.int stackNumber){
    if(stackNumber==1){
        if(S->top1==-1){  // 栈1是空栈
            return ERROR;
        }
        *e = S->data[S->top--];  // 将栈1的栈顶元素出栈
    }else if(stackNumber==2){
        if(S->top2==MAXSIZE){  // 栈2是空栈
            return ERROR;
        }
        *e = S->data[S->top2++] // 将栈2的栈顶元素出栈
    }
}

2.2 表达式求值——中缀表达式转后缀表达式(编程题)

本内容分成两块：

1. 将中缀表达式转化为后缀表达式（栈用来进出运算的符号）。

2. 将后缀表达式进行运算得出结果（栈用来进出运算的数字）。

2.2.1 中缀表达式转后缀表达式

中缀表达式“9＋(3+1)×3＋10÷2”转化为后缀表达式“9 3 1 - 3＊＋10 2 ／ ＋”

方法：从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的—部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级不高于栈顶符号（乘除优先加减）则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。

思路：

1. 初始化一空栈，用来对符号进出栈使用。

2. 第—个字符是数字9，输出9，后面是符号‘‘＋’’ ，进栈。

3. 第三个字符是”（ “ ，依然是符号，因其只是左括号，还未配对，故进栈。

4. 第四个字符是数字3，输出，总表达式为9  3，接着是“-”，进栈。

5. 接下来是数字1，输出，总表达式为9  3  1，后面是符号“）” ，此时，我们需要去匹配此前的“（ ”，所以栈顶依次出栈，并输出，直到“（ ”出栈为止。此时左括号上方只有“-’’，因此输出“-”。总的输出表达式为9  3  1  -。

6. 紧接着是符号”ד，因为此时的栈顶符号为“+”，优先级低于“×”， 因此不输出，“*”进栈。接着是数字3，输出，总的表达式为9  3  1  -  3。

7. 之后是符号“＋”，此时当前栈元素“*”，比这个“+”的优先级高，因此栈中元素出栈并输出（没有比“+”更低的优先级，所以全部出栈），总输出表达式为9  3  1  -  3  *  +。然后将当前这个符号“+”进栈。也就是说，前6张图的栈底的“＋”是指中缀表达式中开头的9后面那个‘‘＋” ，而左图中的栈底（也是栈顶）的“＋”是指“9＋（3-1）×3＋”中的最后—个“＋”。

8. 紧接着数字10，输出，总表达式变为9  3  1  -  3  *  +  10  2。后是符号“÷“，所以“／”进栈。

9. 最后一个数字2，输出，总的表达式为9  3  1  -  3 ＊＋10  2。

10. 因为巳经到最后，所以将栈中符号全部出栈并输出。最终输出的后缀表达式结果为9  3  1  -  3 ＊＋10  2  /  +。

2.2.2 后缀表达式计算

后缀表达式：9 3 1 - 3＊＋10 2 ／ ＋

1. 初始化空栈，此栈用来对要运算的数字进出使用。

2. 后缀表达式前三个都是数字，所以9、3、1进栈，如图所示。

3. 接下来是“-”，所以将栈中的1出栈作为减数，3出栈被减数，并运算3-1得到2，再将2进栈，如图所示。

4. 接着是数字3进栈，如图所示。

5. 后面是“*”，也就意味着栈中的3和2出栈，2与3相乘得到6，并将6进栈。

6. 下面是‘‘＋” ，所以栈中6和9出栈，9与6相加，得到15，将15进栈。

7. 接着是10与2两数字进栈。

8. 接下来是符号‘‘／”，因此，栈顶的2与10出栈，10与2相除，得到5，将5进栈。

9. 最后—个是符号“＋”，所以15与5出栈，并相加，得到20，将20进栈 。

10. 结果是20出栈，栈变为空。

3 串、数组和广义表

3.1 KMP模式匹配算法

3.1.1 算法原理

假设主串S=“abcdefab”，我们要匹配的子串T=”abcdex“，如果用朴素模式匹配算法，前5个字母，两个串完全相等，直到第6个字母，”f“与“x”不等，如图所示。

接下来按照朴素模式匹配算法，应该是按照上图的步骤2、3、4、5、6，即主串S中当时，首字符与子串T的首字符均不等。

仔细观察就会发现，对于要匹配的子串T来说，“abcdex”首字母“a”与后面串“bcdex”中任意一个字符都不相等。也就是说对于步骤1来说前五位字符分别相等，意味着子串T的首字符“a”不可能与S串的第2位到第5位字符相等。所以，在上图中，步骤2、3、4、5的判断都是多余的。

当我们知道T串中首字符“a”与T中后面的字符均不相等的前提下，T串后面的字符均不相等的前提下，T串的“a”与S串后面的“c”“d”“e”也都可以在步骤1之后就可以确定是不相等的，所以在朴素模式匹配算法中步骤2、3、4、5没有必要，只保留步骤1、6即可，如图所示。

保留步骤6中的判断是因为在步骤1中，虽然我们已经知道了，也不能断定一定不等于，因此只需要保留步骤6这一步。

对于在子串中有与首字符相等的字符，也是可以省略一部分不必要的判断步骤，如图所示，省略T串前两位“a”与“b”同S串中的4、5位置字符匹配操作。

在朴素的模式匹配算法中，主串的i值是不断地回溯来完成的，而这种回溯其实是可以省略的，KMP模式匹配算法就是为了让这没必要的回溯不发生。

既然i值不回溯，也就是不可以变小，那要考虑的变化就是j值了，通过观察可以发现，提到了T串的首字符与自身后面字符的比较，发现如果有相等字符，j值的变化就会不相同。也就是说，j值的变化与主串其实没什么关系，关键取决于T串的结构中是否有重复问题，j值的大小取决于当前字符的串的前后缀的相似度。

在需要查找字符串前，先对要查找的字符串做一个分析，这样可以大大减少我们查找的难度，提高查找的速度。

KMP算法：不回溯，从最长相等前后缀后面一个字符开始比较。

3.1.2 KMP算法字符串的前缀、后缀、最长相等前后缀

前缀：包含第一个字符，但不包含最后一个字符的子串。

后缀：包含最后一个字符，但不包含第一个字符的子串。

最长相等前后缀：前缀和后缀相等的最长子串。

例如字符串“abca”

• 前缀：{a,ab,abc}

• 后缀：{a,ca,bca}

• 最长相等前后缀：a

字符串“ababa”

• 前缀：{a,ab,aba,abab}

• 后缀：{a,ba,aba,baba}

• 最长相等前后缀：aba

3.1.2 next数组

当和发生失配时，i不回溯，下一趟让j指向最长相等前后缀的后一个位置，用数组将这一位置记录下来，即为next数组。

假设模式串T=“ababaaaba”，如图所示。

1. 当j=1时，第一位默认为0或-1，next[1]=0。

2. 当j=2时，next[2]=1。

3. 当j=3时，next[3]=1。

4. 当j=4时，j由1到j-1的串是“aba”，next[4]=2。
   前缀字符：{a,ab}
   后缀字符：{a,ba}
   最长相等前后缀：{a}

5. 当j=5时，j由1到j-1的串是“abab”，next[5]=3。
   前缀字符：{a,ab,aba}
   后缀字符：{b,ab,bab}
   最长相等前后缀：{ab}

6. 当j=6时，j由1到j-1的串是“ababa”，next[6]=4。
   前缀字符：{a,ab,aba,abab}
   后缀字符：{a,ba,aba,baba}
   最长相等前后缀：{aba}

7. 当j=7时，j由1到j-1的串是“ababaa”，next[7]=2。
   前缀字符：{a,ab,aba,abab,ababa}
   后缀字符：{a,aa,baa,abaa,babaa}
   最长相等前后缀：{a}

8. 当j=8时，j由1到j-1的串是“ababaaa”，next[8]=2。
   前缀字符：{a,ab,aba,abab,ababa,ababaa}
   后缀字符：{a,aa,aaa,baaa,abaaa,babaaa}
   最长相等前后缀：{a}

9. 当j=9时，j由1到j-1的串是“ababaaab”，next[9]=3。
   前缀字符：{a,ab,aba,abab,ababa,ababaa,ababaaa}
   后缀字符：{b,ab,aab,aaab,baaab,abaaab,babaaab}
   最长相等前后缀：{ab}

3.1.2 时间复杂度

3.2 广义表

1. 取表头GetHead(LS)：取出的表头为非空广义表中的第一个元素，它可以是一个单原子，也可以是一个子表。

2. 取表尾GetTail(LS)：**取出的表尾为除去表头之外，由其他元素构成的表。**即表尾一定是一个广义表。

例如：

GetHead(B)=e GetTail(B)=()

GetHead(D)=A GetTail(D)=(B,C)，

由于B,C是广义表，则可继续分解得到：

GetHead(B,C)=B GetTail(B,C)=C

广义表()和(())不同，前者为空表，长度n=0；后者长度n=1，可继续分解得到其表头，表尾均为空表()。

4 树和二叉树

4.1 二叉树的存储结构

4.1.1 二叉树的顺序存储结构

**二叉树的顺序存储结构就是用一维数组存储二叉树的结点存储二叉树中的结点，并且结点的存储位置，**也就是数组的下标要体现结点之间的逻辑关系，比如双亲与孩子的关系，左右兄弟的关系等。

一棵完全二叉树如图所示：

将这棵二叉树存入数组中，相应的下标对应其同样的位置，如图所示。

完全二叉树定义的严格用顺序结构也可以体现出二叉树的结构，对于一般的二叉树，虽然层序编号不能反映逻辑关系，但完全可以按完全二叉树的编号，把不存在的结点设置为“^”即可，如图所示。