顺序 printf(stus[i+1].name);//直接通过下标找到下一个
链式 printf(n1.next->name);//通过next指针找到下一个
算法特性（有穷性 确定性 可行性 输入 输出）
时间复杂度 : O(1)<O(log n)<O(n)<O(n*log n)<O(n2)<O(n3) O(2?)<O(n!)<O(n?)
就地逆置 O(1) 借助一个辅助数组 O(n)
鉴于运算空间较为充足，常以算法时间复杂度作为算法优劣的衡量指标
线性表中第i个数据元素ai存储位置
LOC(ai)=LOC(a1)+(i-1)*len
顺序存储结构特点：逻辑相邻 物理位置相邻 实现随机存储（访问快速）
顺序表插入位置从1到L->length+1 每个位置插入概率1/n*1 移动次数期望值 E=n/2
顺序表删除位置从1到n 每个位置插入概率1/n 移动次数期望值 E=(n-1)/2
线性表链式结构 ：为了简化插入与删除操作需在第一个结点之前设置一个头节点
建立单链表—头插法：生成一个空表，不断将新节点插入链表表头
void CreateListF(LinkNode *&L，ElemType a[]，int n)
{ LinkNode *s;
int i;
L=new LNode;
L->next=NULL; //创建头结点，其next域置为NULL
for (i=0;i<n;i++) //循环建立数据结点
{
s=new LNode;
s->data=a[i]; //创建数据结点*s
s->next=L->next; //将*s插在原开始结点之前，头结点之后
L->next=s;
}
}
建立单链表—尾插法：将新节点始终插入链表表尾，需要一个尾指针r
void CreateListR(LinkNode *&L，ElemType a[]，int n)
{ LinkNode *s，*r;
int i;
L=new LNode; //创建头结点
r=L; //r始终指向尾结点，开始时指向头结点
for (i=0;i<n;i++) //循环建立数据结点
{
s=new LNode;
s->data=a[i]; //创建数据结点*s
r->next=s; //将*s插入*r之后
r=s;
}
r->next=NULL; //尾结点next域置为NULL
}
有序顺序表插入
oid ListInsert(SqList *&L，ElemType e)
{ int i=0，j;
while (i<L->length && L->data[i]<e)
i++; //查找值为e的元素
for(j=ListLength(L);j>i;j--) //将data[i..n]后移一个位置
L->data[j]=L->data[j-1];
L->data[i]=e;
L->length++; //有序顺序表长度增1
}
有序链式表插入
void ListInsert(LinkNode *&L，ElemType e)
{ LinkNode *pre=L，*p;
while (pre->next!=NULL && pre->next->data<e)
pre=pre->next; //查找插入结点的前驱结点*pre
p=new LNode;
p->data=e; //创建存放e的数据结点*p
p->next=pre->next; //在*pre结点之后插入*p结点
pre->next=p;
}
有序表归并
void UnionList1(LinkList *LA, LinkList *LB,LinkList *&LC)
{ LinkList *pa=LA->next, *pb=LB->next, *r, *s;
LC=new LinkList; //创建LC的头节点
r=LC; // r始终指向LC的尾节点
while (pa != NULL && pb != NULL)
{ if (pa->data < pb->data)
{ s= new LNode;//复制节点
s->data = pa->data;
r->next = s;r = s; //采用尾插法将* s插入到LC中
pa = pa- >next;
}
else
{
s = new LNode;//复制节点
s->data = pb->data;
r->next = s;r = s; //采用尾插法将* s插入到LC中
pb = pb->next;
}
}
while (pa != NULL)
{ s = new LNode; //复制节点
s->data = pa->data;
r->next = s;r = s; //采用尾插法将* s插入到LC中
pa = pa->next;
}
while (pb != NULL)
{ s = new LNode; //复制节点
s->data = pb->data;
r->next=S;r=s; //采用尾插法将* s插入到LC中
pb = pb- >next;
}
r->next = NULL; //尾节点的next域置空
栈：后进先出（LIFO)
顺序栈4要素：
栈空条件：s->top=-1;
栈满条件：s->top=MaxSize-1;
进栈操作：s->top++;
退栈操作：从top处取出元素e; s->top--;
链栈4要素：
栈空条件：s->next=Null;
栈满条件无需考虑
进栈操作：将新数据节点插入头节点后
退栈操作：取出头节点后节点数据赋值并删除
链栈特点：
插入删除（进栈/出栈）只在表头（栈顶）进行
链栈中结点动态产生，可不考虑上溢问题
无需附加头结点
队列：先进先出（FIFO)
顺序队列4要素：
空队列条件：Q.front==Q.rear
队列满：Q.rear-Q.front=m
入队：Q.base[rear++]=x;
出队:x=Q.base[front++];
循环队列：
队空：Q.front==Q.rear
队满：(Q.rear+1)%m=Q.front
入队：Q.rear=(Q.rear+1)%m
出队：Q.front=(Q.front+1)%m
串：由零个或多个字符组成的有限序列
空串≠空格串
串结构与线性表比较：
逻辑结构（串的数据对象为字符）
基本操作（串以整体为造作对象；线性表大多以单个元素为操作对象）
串的模式匹配算法：
BF算法特点：指针i不停回溯 时间复杂度 O(m*n)
KMP算法特点：主串不需要回溯i指针 时间复杂度O(m+n)
求模式串T的next函数值
void get_next(SString &T,int &next[]){
i = 1; next[1] = 0; j = 0;
while(i < T[O]){
if (j = 0||T[i] == T[j])
{++i;++j;next[i] = j;}
else j = next[j];
}
} //get_next
求模式串T的nextval函数值
void get_nextval(SString &T, int &nextval[])
{
i = 1; nextval[1] = 0;j = 0;
while(i < T[O]){
if (j=0||T[i]==T[j]){
++i; ++j;
if (T[i]!= T[j]) nextval［i] = j;
else nextval[i] = nextval[j];
}
else j = nextval[j];
}
}// get_nextval
中缀表达式如何转化为后缀表达式： 从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于栈顶符号（乘除优先加减）则顶元素依次出找并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。
BMP算法中next[j]以及nextval[j]计算：首先找到模式串中的公共前后缀 ，直接挪动模式串使得前缀移动到后缀位置，保证主串和模式串指针前所有字符位置匹配；共前后缀的条件为：1、最长的前后缀；2、长度小于指针前所有字符长度。
则第一位next[j]值设为0，后续next[j]值为最长公共缀＋1。
nextval[j]满足如果t[j]=t[next[j]]，则nextval[j]=nextval[next[j]]；否则nextval[j]=next[j]。
原文：https://www.cnblogs.com/zgz123/p/12588823.html