一、数据结构基本概念 1.数据：对客观事物的符号表示 数据元素：数据的基本单位 数据对象：性质相同的 数据元素 的集合 数据结构：相互之间存在一种或多种特定关系的数据元素的集合 2.数据元素之间的关系由两种表示：顺序映像和非顺序映像->顺序存储和链式存储 3.数据类型：是一个 值的集合 和定义在这个值集上的 一组操作 的总称 4.抽象数据类型：指一个数学模型以及定义在该模型上的一组操作 包括：定义，表现和实现三部分。（D,S,P）分别表示数据对象，关系集合，操作集合 分为：原子类型、固定聚合类型、可变聚合类型（长度可变）、多形数据类型 5.算法：指令的有限序列，包括：有序性、确定性、可行性、输入、输出 6.时间复杂度：一般指最坏情况下的时间复杂度 二、.线性表 ①两个线性表LA,LB合并算法(伪代码) ——ExistElem（）执行时间为O(LB),所以总该为O（LA*LB） void union(List &La,List Lb){ La_len = La.length(); Lb_len = Lb.length(); for(i = 1;i<=Lb.length();i++){ Elem e = GetElem(Lb,i); if(!ExistElem(La,e)) ListInsert(La,++La_len,e); } } ②两个递增有序排列，将LA与LB归并成一个LC，使得LC仍然递增——执行时间为O（LA+LB） // 递增排序 private static ArrayList<Integer> unionSort(ArrayList<Integer> la, ArrayList<Integer> lb) { ArrayList<Integer> lc = new ArrayList<>(); int i = 0, j = 0; while (i < la.size() && j < lb.size()) { if (la.get(i) <= lb.get(j)) { lc.add(la.get(i)); i++; } else { lc.add(lb.get(j)); j++; } } //如果la或lb还有剩余未比较的，全部加入即可 while(i<la.size()){ lc.add(la.get(i)); i++; } while(j<lb.size()){ lc.add(lb.get(j)); j++; } return lc; } ③ 线性表的顺序实现： typedef struct{ ElemType *elem; int length; //表长 int listSize; //元素个数 ｝ SqList; 注意： 顺序线性表中插入新的元素在指定位置时，需要将其后的位置统一后移并增长表长； 删除则需要把第i个元素统一向前移动；时间复杂度均为O(n) ④线性表的单链式实现： typedef struct LNode{ ElemType data; struct LNode *next; }LNode , *LinkList; * p = p->next; 用此方法可以找到第i个元素 * 实现插入：1. s->next = p->next; 2.p->next = s; (s为新结点，p为插入位置) * 删除b元素只需 b的前一个结点p 使得 p->next = p->next->next; * 带表头结点的单链表创建（L-游标），使得 p(新结点)->next = L->next ; //插入 L->next=p; //游标移动 ⑤静态链表的结构： #define MAX_SIZE = 1000 ； typedef struct { ElemType data ; int cur ; }Component , StaticLinkList[MAX_SIZE]; 首先是下标为0的结点中不包含有意义的数据，它的cur存储的是备用链表（即没有存储的数据的那些结点）第一个结点的下标。其次是数组最后一个元素，数组最后一个元素的cur存放的是静态链表的第一个结点的下标。最后就是链表的最后一个元素（并不一定是数组的最后一个元素），链表最后一个元素的cur一般存放0，表示它后面的结点为空了。 ⑥循环链表 表中最后一个结点的指针域指向头结点，整个链表形成一个环。与线性链表基本一致，差别在于算法中的循环条件不再是p或p->next是否为空，而是他们是否等于头指针。 ⑦双向链表 typedef struct DuLNode{ ElemType data; struct DuLNode *prior; struct DuLNode *next; }DuLNode,*DuLinkList; 注意：插入、删除时需要修改两个方向上的指针，复杂度为O(n) a,b,c删除时需要把 b.prior.next = b.next; b.next.prior = b.prior; a,c插入x时需要把 s.data = e; s.prior = p.prior; p.prior.next = s ; s.next = p; p.prior = s; 具体画图即明白。 ⑧线性链表 typedef struct LNode{ //结点类型 ElemType data; struct LNode *next; } *Link,*Position; typedef struct { //链表类型 Link head,tail; //链表头尾结点 int len; //线性表中的数据元素个数 }LinkList; 三、栈和队列 1.栈：后进先出（LIFO） 顺序栈： typedef struct { SElemType *base; // 栈底 SElemType *top; // 栈顶 int stackSize; //当前已分配的存储空间 }SqStack; 获取栈顶： e = *(S.top-1); 插入元素 ： *S.top++=e; 弹出元素： e = *--S.top; 2.栈的应用 ①数制转换： 原理：N=(N 整除 d) * d + N (mod) d //关键代码，将N转换为radix进制 public static void getRadix(int N,int radix){ Stack<Integer> stack = new Stack<>(); while(N!=0){ stack.push(N%radix); N=N/radix; } while(!stack.isEmpty()){ System.out.print(stack.pop()); } } ②括号匹配检验（没加入一个封闭括号就看之前是否有开放括号，若检查到空都没则失败；有则消解，继续加入） ③行编译程序 ④迷宫求解（利用栈的可回退）：若当前位置通则纳入当前路径，并朝下一位置探索；若当前不通，则退回到前一位置朝其他方向的下一位置探索，若四周均不同则删除该路径。直到找到出口位置。 ⑤表达式求值 ⑥栈与递归的实现 I.菲波那切数列 public static int fibonacci(int n){ if(n==0){ return 0; }else if(n==1){ return 1; }else{ return fibonacci(n-1)+fibonacci(n-2); } } II.阿克曼函数 public static int ackerman(int n,int m){ if(m==0){ return n+1; }else if(n==0){ return ackerman(m-1, 1); }else{ return ackerman(m-1, ackerman(m, n-1)); } } III.汉诺塔函数 //递归调用，永远是先遍历到最深层，再逆序执行下面未执行的操作 public static void hanoi(int n, char a, char b, char c) { if (n == 1) { System.out.println("将"+n+"号盘子从"+a+"移到"+c); } else { hanoi(n - 1, a, c, b); // 将a上编号为1到n-1的盘子移到b System.out.println("将"+n+"号盘子从"+a+"移到"+c); hanoi(n - 1, b, a, c); // 将b上编号为1到n-1的盘子移到c } } 3.队列 先进先出的线性表（FIFO），典型列子就是操作系统的作业排队。 单链队列——队列的链式存储结构 typedef struct QNode{ QElemType data; struct QNode *next; }QNode,*QueuePtr; typedef struct { QueuePtr front ; //队头指针 QueuePtr rear; //队尾指针 }LinkQueue; 判断队空：Q.front == Q.rear 循环队列——队列的顺序表示和实现 typedef struct{ QElemType data; int front; int rear; }SqQueue; 注意：判断队满： (Q.rear + 1)%MAXQSIZE == Q.front 判断队空：Q.front == Q.rear 4.离散事件模拟 四、串 1.串的模式匹配算法 KMP算法是在已知模式串的next函数值的基础上执行的 *next 数组的求解竟然如此简单：就是找最大对称长度的前缀后缀，然后整体右移一位，初值赋为-1 2 KMP的算法流程： 假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置 如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++，继续匹配下一个字符； 如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]。此举意味着失配时，模式串P相对于文本串S向右移动了j - next [j] 位。 *我们发现如果某个字符匹配成功，模式串首字符的位置保持不动，仅仅是i++、j++；如果匹配失配，i 不变（即 i 不回溯），模式串会跳过匹配过的next [j]个字符。整个算法最坏的情况是，当模式串首字符位于i - j的位置时才匹配成功，算法结束。 所以，如果文本串的长度为n，模式串的长度为m，那么匹配过程的时间复杂度为O(n)，算上计算next的O(m)时间，KMP的整体时间复杂度为O(m + n)。 3.应用：文本编辑、建立 词索引表
