基本语法
-
预定义常量及类型
函数结果状态代码
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
-
数据结构的表示(存储结构)类型定义( typedef )描述;数据元素类型约定为ElemType,由用户在使用该数据类型时自行定义。
-
基本操作的算法都用如下格式的函数来描述:
函数类型函数名(函数参数表){
语句序列
}
当函数返回值为函数结果状态代码时,函数定义为Status 类型。为了便于描述算法,除了值调用方式外,增加了C++语言引用调用的参数传递方式。在形参表中,以“&”打头的参数即为引用参数。传递引用给函数与传递指针的效果是-样的,形参变化实参也发生变化,但引用使用起来比指针更加方便、高效。
-
内存的动态分配与释放。
使用new和delete动态分配和释放内存空间:
分配空间 指针变量=new 数据类型;
释放空间 delete指针变量;
-
赋值语句:
简单赋值 变量名 = 表达式;
串联赋值 变量名1 = 变量名2 = ... = 变量名n = 表达式;
成组赋值 (变量名1, ..., 变量名n) = (表达式1, ..., 表达式n);
结构赋值 结构名1 = 结构名2;
结构名 = (值1,值2,....值n);
条件赋值 变量名 = 条件表达式?表达式T:表达式F;
交换赋值 变量名1 <-->变量名2;
-
选择语句:
条件语句1 if (表达式)语句;
条件语句2 if (表达式) 语句;
else语句;
开关语句 switch (表达式)
{
case值1: 语句序列1 ;break;
case值2: 语句序列2 ;break;
...
case值n: 语句序列n ;break;
default: 语句序列n+1;
}
-
循环语句:
for语句 for (表达式1; 条件; 表达式2)语句;
while语句 while (条件) 语句;
do-while语句 do {
语句序列;
} while (条件);
-
结束语句:
函数结束语句 return 表达式;
return;
case 或循环结束语句 break;
异常结束语句 exit (异常代码);
-
输入输出语句使用C++流式输人输出的形式:
输入语句 cin>>变量1>>..>>变量n;
输出语句 cout<<表达式1<<...<<表达式n;
-
基本函数:
求最大值 Max (表达式1, ..., 表达式n)
求最小值 Min (表达式1, ..., 表达式n)
线性表
线性表的顺序表示和实现
线性表的顺序存储结构:
#define MAXSIZE 100
typedef struct
{
ElemType *elem;
int length;
}SqList;
初始化:
Status InitList(SqList &L)
{
L.elem = new ElemType[MAXSIZE];
if (!L.elem) exit(OVERFLOW);
L.length = 0;
return OK;
{
取值:
Status GetElem(SqList L, int i, ElemType &e)
{
if (i<1 || i>L.length) return ERROR;
e = L.elem[i-1];
return OK;
}
查找
int LocateElem(SqList L, ElemType e)
{
for (int i = 0; i < L.length; i++)
if (L.elem[i] == e) return i+1;
return 0;
}
插入
Status ListInsert(SqList &L, int i, ElemType e)
{
if ((i<1) || (i>L.length+1)) return ERROR;
if (L.length == MAXSIZE) return ERROR;
for int j = L.length - 1; j >= i - 1; j--)
L.elem[j+1] = L.elem[j];
L.elem[i-1] = e;
++L.length;
return OK;
}
删除
Status ListDelete(SqList &L, int i)
{
if ((i < 1) || (i > L.length)) return ERROR;
for (int j = i; j <= L.length - 1; j++)
L.elem[j - 1] = L.elem[j];
--L.length;
return OK;
}
多项式的顺序存储结构:
#define MAXSIZE 100
typedef struct
{
float coef;
int expn;
}Polynomial;
typedef struct
{
Polynmial *elem;
int length;
}SqList
图书表的顺序春初结构类型定义:
#define MAXSIZE 1000
typedef struct
{
char no[20];
char name[50];
float price;
}Book;
typedef struct
{
Book *elem;
int length;
}SqList;
线性表的链式表示和实现
顺序表的初始化:
Status InitList(SqList &L)
{
L.elem = new ElemType[MAXSIZE];
if(!L.elem) exit(OVERFLOW);
L.length = 0;
return OK;
}
顺序表的取值:
Status GetElem(SqList L, int i, ElemType &e)
{
if (i < 1 || i > L.length) return ERROR;
e = L.elem[i - 1];
return OK;
}
顺序表的查找:
int LocateElem(SqList L, ElemType e)
{
for (i=0; i<L.length; i++)
if (L.elem[i] == e) return i+1;
return 0;
}
顺序表的插入:
Status ListInsert(SqList &L, int i, ElemType e)
{
if ((i<1) || (i>L.length+1)) return ERROR;
if (L.length == MAXSIZE) return ERROR;
for (j=L.length-1; j>=1-1; j--)
L.elem[j+1] = L.elem[j];
L.elem[i-1] = e;
++L.length;
return OK;
}
顺序表的删除:
Status ListDelete(SqList &L, int i)
{
if ((i<1) || (i>L.length)) return ERROR;
for (j=i; j<=L.length-1; j++)
L.elem[j-1] = L.elem[j];
--L.length;
return OK;
}
线性表的链式表示和实现
单链表的存储结构:
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
初始化:
Status InitList(LinkList &L)
{
L = new LNode;
L->next = NULL;
return OK;
}
单链表的取值:
Status GetElem(LinkList L, int i, ElemType &e)
{
p = L->next;
j = 1;
while (p&&j < i)
{
p = p->next;
++j;
}
if (!p || j>i) return ERROR;
e = p->data;
return OK;
}
单链表的按值查找:
LNode *LocateElem(LinkList L, ElemType e)
{
p = L->next;
while (p && p->data != e)
p = p->next;
return p;
}
单链表的插入
Status ListInsert(LinkList &L, int i, ElemType e)
{
p = L;
j = 0;
while (p && (j < i - 1))
{
p = p->next;
j++;
}
s = new LNode;
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}
单链表删除:
Status ListDelete(LinkList &L, int i)
{
p = L;
j = 0;
while (p && (j < i - 1))
{
p = p->next;
++j;
}
if (!(p->next) || (j>i-1)) return ERROR;
q = q->next;
p->next = q->next;
delete q;
return OK;
}
前插法创建单链表:
void CreateList_H(LinkList &L, int n)
{
L = new LNode;
L->next = NULL;
for (i=0; i<n; i++)
{
p = new LNode;
cin>>p->data;
p->next = L->next;
L->next = p;
}
}
后插法创建单链表
void CreateList_R(LinkList &L, int n)
{
L = new LNode;
L->next = NULL;
r = L;
for (i=0; i<n; ++i)
{
p = new LNode;
cin>>p->data;
p->next = NULL;
r->next = p;
r = p;
}
}
循环链表
循环链表的存储结构:
typedef struct DulNode
{
ElemType data;
struct DulNode *prior;
struct DulNode *next;
}
双向链表的插入:
Status ListInsert_DuL(DuLinkList &L, int i, ElemType e)
{
if(!(p = GetElem_DuL(L,i)))
return ERROR;
s = new DuLNode;
s->data = e;
s->prior = p->prior;
p->prior->next = s;
s->next = p;
p->prior = s;
return OK;
}
双向链表的删除:
Status ListDelete_DuL(DuLinkList &L, int i)
{
if (!(p = GetElem_DuL(L,i)))
return ERROR;
p->prior->next = p->next;
p->next->prior = p->prior;
delete p;
return OK;
}
算法实例
顺序有序表的合并
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;
pa = LA.elem;
pb = LB.elem;
pa_last = LA.elem + LA.length - 1;
pb_last = LB.elem + LB.length - 1;
while ((pa<=pa_last) && (pb<=pb_last))
{
if (*pa <= *pb) *pc++ = *pa++;
else *pc++ = *pb++;
}
while (pa<=pa_last) *pc++=*pa++;
while (pb<=pb_last) *pc++=*pb++;
}
链式有序表的合并
void MergeList_L(LinkList &LA, LinkList &LB, LinkList &LC)
{
pa = LA->next;
pb = LB->next;
pc = 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;
delete LB;
}
多项式相加
void AddPolyn(Polynomial &Pa, Polynomia &Pb)
{
p1 = Pa->next;
p2 = Pb->next;
p3 = Pa;
while (p1 && p2)
{
if (p1->expn == p2->expn)
{
sum = p1->coef + p2->coef;
if (sum != 0)
{
p1->coef = sum;
p3->next = p1;
p3 = p1;
p1 = p1->next;
r = p2; p2 = p2->next; delete r;
}
else
{
r = p1; p1 = p1->next; delete r;
r = p2; p2 = p2->next; delete r;
}
}
else if (p1->expn < p2->expn)
{
p3->next = p1;
p3 = p1;
p1 = p1->next;
}
else
{
p3->next = p2;
p3 = p2;
p2 = p2->next;
}
}
pe->next = p1 ? p1 : p2;
delete Pb;
}
栈
顺序栈的存储结构
#define MAXSIZE 100
typedef struct
{
SElemType *base;
SElemType *top;
int stcksize;
}SqStack;
顺序栈初始化
StatusInitStack(SqStack &S)
{
S.base = new SElemType[MAXSIZE];
if (!S.base) exit(OVERFLOW);
S.top = S.base;
S.stacksize = MAXSIZE:
return OK;
}
顺序栈的入栈
StatusPush(SqStack &S, SElemType e)
{
if(S.top-S.base == S.stacksize) return ERROR;
*S.top++ = e;
return OK:
}
顺序栈的出栈
StatusPop(SqStack &S, SElemTyp e)
{
if (S.top == S.base) return ERROR;
e = *--S.top;
return OK;
}
顺序栈取栈顶元素
ElemTypeGetTop(SqStackS)
{
if (S.top != S.base)
return *(S.top - 1);
}
链式栈的初始化
Status InitStack(LinkStack &S)
{
S = NULL;
return OK;
}
链式栈入栈
StatusPush (LinkStack &S, SElemType e)
{
p = new StackNode;
p->data = e;
p->next = S;
S = p;
return OK;
}
链式栈出栈
Status Pop (LinkStack &S, SElemType &e)
{
if(S == NULL) return ERROR;
e = S->data;
p = S;
S = S->next;
delete p;
return OK;
}
链式栈取栈顶元素
SElemType GetTop (LinkStack S)
{
if (S != NULL)
return S->data;
}
队列:
循环队列的顺序存储结构
#define MAXQSIZE 100
typedef struct
{
QElemType *base;
int front;
int rear;
}
循环队列的初始化
Status InitQueue (SqQueue &Q)
{
Q.base = new QElemType[MAXQSIZE];
if (!Q.base) exit(OVERFLOW);
Q.front = Q.rear = 0;
return OK;
}
求循环队列长度
int QueueLength (SqQueue Q)
{
return (Q.rear - Q.front + MAXSIZE) % MAXQSIZE;
}
循环队列入队
Status EnQueue (SqQueue &Q, QElemType e)
{
if ((Q.rear+1) % MAXQSIZE == Q.front) return ERROR;
Q.base[Q.rear] = e;
Q.rear = (Q.rear+1)%MAXQSIZE;
return OK;
}
循环队列出队
Status DeQueue (SqQueue &Q, QElemType &e)
{
if (Q.front == Q.rear) return ERROR;
e = Q.base[Q.front];
Q.front = (Q.front+1) % MAXQSIZE;
return OK;
}
取循环队列的队头元素
SElemType GetHead (SqQueue Q)
{
if (Q.front != Q.rear)
return Q.base[Q.front];
}
链队存储结构:
typedef struct QNode
{
QElemType data;
struct QNode *next;
}QNode, *QueuePtr;
typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue
链队初始化:
status InitQueue (LinkQueue &Q)
{
Q.front = Q.rear = new QNode;
Q.front->next = NULL;
return OK;
}
链队入队:
Status EnQueue (LinkQueue &Q, QElemType e)
{
p = new QNode;
p->data = e;
p->next = NULL;
Q.rear->next = p;
Q.rear = p;
return OK;
}
链队出队:
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;
delete p;
return OK;
}
链队取队头元素的值:
SelemType GetHead (LinkQueue Q)
{
if (Q.front != Q.rear)
return Q.front->next->data;
}
案例 - 数制的转换:
将一个十进制整数N转换为八进制数
void conversion (int N)
{
InitStack(S);
while(N)
{
Push(S, N%8);
N = N/8;
}
while (!StackEmpty(s))
{
Pop(S, e);
cout<<e;
}
}
案例 - 括号的匹配:
Status Matching()
{
InitStack(S);
flag = 1;
cin>>ch;
while (!='#' && flag)
{
switch (ch)
{
case '[' || '(':
Push(S,ch);
break;
case ')':
if (!StackEmpty(S) && GetTop(S) == '(')
Pop(S,x);
else flag = 0;
break;
case ']':
if (!StackEmpty(S) && GetTop(S) == '[')
Pop(S,x);
else flag = 0;
break;
}
cin>>ch;
}
if (StackEmpty(S) && flag) return true;
else return false;
}
树
二叉树结点的存储表示
typedef struct BiTNode {
TElemType data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree
二叉树中序遍历
void InOrderTraverse (BiTree T)
{
if (T)
{
InOrderTraverse(T->lchild);
cout<<T->data;
InOrderTraverse(T->rchild);
}
}
void InOrderTraverse (BiTree T)
{
InitStack(S);
p = T;
q = new BiTNode;
while (p || !StackEmpty(S))
{
if (p)
{
Push(S,p);
p = p->lchild;
}
else
{
Pop(S,q);
cout<<q->data;
p = q->rchild;
}
}
}
计算二叉树的深度
int Depth (BiTree T)
{
if (T == NULL) return 0;
else
{
m = Depth(T->lchild);
n = Depth(T->rchild);
if (m>n) return m+1;
else return n+1;
}
}
统计二叉树中节点的个数
int NodeCount (BiTree T)
{
if (T==NULL) return 0;
else return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
}
B-树和B+树的区别
- B+树内节点不存储数据,所有 data 存储在叶节点导致查询时间复杂度固定为 log n。而B-树查询时间复杂度不固定,与 key 在树中的位置有关,最好为O(1)。
- B+树叶节点两两相连可大大增加区间访问性,可使用在范围查询等,而B-树每个节点 key 和 data 在一起,则无法区间查找。
- B+树更适合外部存储。由于内节点无 data 域,每个节点能索引的范围更大更精确
字符串匹配
BF算法(暴力)
int Index_BF(SString S, SString T, int pos)
{
i = pos; j = 1;
while (i <= S.length && j <= T.legth)
{
if (S[i].ch == T[j].ch) { ++i; ++j; }
else { i=i-j+2; j=1; }
}
if (j > T.length) return i-T.length;
else return 0;
}
KMP
来源:https://blog.csdn.net/m0_60598323/article/details/123696693
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
void my_next(int* next,int n,const char* p)
{
int j = 0, k = -1;
next[0] = -1;
while(j<n)
{
if (k == -1 || p[j] == p[k])
{
next[j + 1] = k + 1;
j++;
k++;
}
else
{
k = next[k];
}
}
}
int kmp(const char* str1, const char* str2)
{
int i = 0, j = 0;
int len = (int)strlen(str2);
int* next = (int*)malloc(len * sizeof(int));
assert(next);
my_next(next,len-1,str2);
while (str2[j])
{
if(j==-1||str1[i] == str2[j])
{
i++;
j++;
}
else
{
j = next[j];
}
if (str1[i] == '\0')
{
free(next);
next = NULL;
return -1;
}
}
free(next);
next = NULL;
return i;
}
int main()
{
char arr[] = "abaabcdabcab";
char brr[] = "ef";
printf("%d\n",kmp(arr, brr));
return 0;
}
散列表
散列表处理冲突的办法
-
线性探测法
发生冲突时,从冲突地址的下一单元顺序寻找空单元
-
二次探测法
d
i
=
1
2
,
−
1
2
,
2
2
,
−
2
2
,
.
.
.
,
k
2
,
−
k
2
(
k
<
=
m
/
2
)
d_i = 1^2,-1^2,2^2,-2^2,...,k^2,-k^2(k<=m/2)
di=12,−12,22,−22,...,k2,−k2(k<=m/2)
-
伪随机探测法
(插入位置 + 随机数)% 数组长度 = 要插入位置
二分查找
void Search_Bin(SSTsble ST, KeyType key)
{
low = l; high = ST.length;
while (low <= high)
{
mid = (low + high) / 2;
if (key == ST.R[mid].key) return mid;
else if (key > ST.R[mid].key) low = mid + 1;
else high = mid - 1;
}
return 0;
}
参考:
https://blog.csdn.net/qq_53436105/article/details/127296815
https://blog.csdn.net/weixin_52811588/category_11973986.html
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)