栈
顺序栈
#define MaxSize 50
typedef struct
{int data[MaxSize];int top;
} SqStack;// 1.(S.top == -1)
void InitStack(SqStack &S)
{S.top = -1;
}// 2.(S.top == -1)
bool Push(SqStack &S, int x)
{if (S.top = MaxSize - 1)return false;S.data[++S.top] = x;return true;
}// 3.(S.top == -1)
bool GetTop(SqStack &S, int &x)
{if (S.top == -1)return false;x = S.data[S.top];return true;
}// 4. (S.top == -1)
bool StackEmpty(SqStack &S)
{if (S.top == -1)return true;return false;
}// 5.(S.top == -1)
bool Pop(SqStack *S, int &x)
{if (S->top == -1)return false;x = S->data[S->top--];return true;
}// // 1.(S.top == 0)
// void InitStack(SqStack &S)
// {
// S.top = 0;
// }// // 2.(S.top == 0)
// bool Push(SqStack &S, int x)
// {
// if (S.top = MaxSize)
// return false;
// S.data[S.top++] = x;
// return true;
// }// // 3.(S.top == 0)
// bool GetTop(SqStack &S, int &x)
// {
// if (S.top == 0)
// return false;
// x = S.data[S.top];
// return true;
// }// // 4. (S.top == 0)
// bool StackEmpty(SqStack &S)
// {
// if (S.top == 0)
// return true;
// return false;
// }// // 5.(S.top == 0)
// bool Pop(SqStack *S, int &x)
// {
// if (S->top == 0)
// return false;
// x = S->data[--S->top];
// return true;
// }链栈
typedef struct LinkNode
{int data;struct LinkNode *next;
} LiStack;共享栈
#define MaxSize 50
typedef struct
{int data[MaxSize];int top0;int top1;
} ShStack;void InitStack(ShStack &S)
{S.top0 = -1;S.top1 = MaxSize;
}队列
循环队列
#define MaxSize 50
typedef struct
{int data[MaxSize];int front, rear;
} SqQueue;// 1.初始化
void InitQueue(SqQueue &Q)
{Q.rear = Q.front = 0;
}// 2.循环队列入队
bool EnEmmpty(SqQueue &Q, int x)
{if ((Q.rear + 1) % MaxSize == Q.front)return false;Q.data[Q.rear] = x;Q.rear = (Q.rear + 1) % MaxSize;return true;
}// 3.判断队列为空
bool isEmpty(SqQueue &Q)
{if (Q.rear == Q.front)return true;return false;
}// 4. 循环队列出队
bool DeEmpty(SqQueue &Q, int &x)
{if (Q.rear == Q.front)return false;x = Q.data[Q.front];Q.front = (Q.front + 1) % MaxSize;return true;
}// 5. 获取队头元素值
bool Gethead(SqQueue Q, int &x)
{if (Q.rear == Q.front)return false;x = Q.data[Q.front];return true;
}带头结点的链式队列
typedef struct LinkNode
{int data;struct LinkNode *next;
} LinkNode;typedef struct
{LinkNode *front, *rear;
} LinkNode;// 带头结点的实现方式// 1.初始化
void InitQueue(LinkNode &Q)
{Q.front = Q.rear = (LinkNode *)malloc(sizeof(LinkNode));Q.front->next = NULL;
}// 2.判断是否为空
bool isEmpty(LinkNode &Q)
{if (Q.front == Q.rear)return true;return false;
}// 3.入队
bool EnEmpty(LinkNode &Q, int x)
{LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));s->data = x;s->next = NULL;Q.rear->next = s;Q.rear = s;return true;
}// 4.出队
bool DeEmpty(LinkNode &Q, int &x)
{if (Q.rear == Q.front)return false;LinkNode *p = Q.front->next;x = p->data;Q.front->next = Q.front->next->next;if (Q.rear == p)Q.rear = Q.front;free(p);return true;
}不带头结点的链式队列
typedef struct LinkNode
{int data;struct LinkNode *next;
} LinkNode;typedef struct
{LinkNode *front, *rear;
} LinkNode;// 不带头结点的实现方式// 1.初始化
void InitQueue(LinkNode &Q)
{Q.front = Q.rear = NULL;
}// 2.判断是否为空
bool isEmpty(LinkNode &Q)
{if (Q.front == NULL)return true;return false;
}// 3.入队
bool EnEmpty(LinkNode &Q, int x)
{LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));s->data = x;s->next = NULL;if (Q.front == NULL){Q.front = s;Q.rear = s;}else{Q.rear->next = s;Q.rear = s;}return true;
}// 4.出队
bool DeEmpty(LinkNode &Q, int &x)
{if (Q.rear == NULL)return false;LinkNode *p = Q.front;x = p->data;Q.front = p->next;if (Q.rear == p){Q.rear = NULL;Q.front = NULL;}free(p);return true;
}串
顺序串
#define MAXSIZE 50
// 静态分配
typedef struct
{char str[MAXSIZE];int length;
} SeqString;// 1.
void StrAssign(SeqString *S, char cstr[])
{int i = 0;for (i = 0; cstr[i] != '\0'; i++){S->str[i] = cstr[i];}S->length = i;
}// 2.
int StrEmpty(SeqString S)
{if (S.length == 0)return 1;return 0;
}// 3.
int StrLength(SeqString S)
{return S.length;
}// 4.
void StrCopy(SeqString *T, SeqString S)
{int i = 0;for (i = 0; i < S.length; i++){T->str[i] = S.str[i];}T->length = S.length;
}// 5. 比较两个串的大小
int StrCompare(SeqString S, SeqString T)
{int i;for (i = 0; i < S.length && i < T.length; i++){if (S.str[i] == T.str[i])return (S.str[i] - T.str[i]);}return (S.length - T.length);
}// 6. 在串S的第pos位置插入串T。若成功，返回1；失败，返回0
int StrInsert(SeqString *S, int pos, SeqString T)
{int i;if (pos < 0 || pos >= S->length){printf("插入位置错误");return 0;}if (S->length + T.length <= MAXSIZE){for (i = S->length + T.length - 1; i >= pos + T.length - 1; i--)S->str[i] = S->str[i - T.length];for (i = 0; i < T.length; i++)S->str[pos + i] = T.str[i];S->length += T.length;return 1;}else if (pos + T.length <= MAXSIZE) // 子串可以完整插入S中，但是S中的字符会被截掉{for (i = MAXSIZE - 1; i > T.length + pos - 1; i--)S->str[i] = S->str[i - T.length];for (i = 0; i < T.length; i++)S->str[i + pos - 1] = T.str[i];S->length = MAXSIZE;return 0;}else // 子串T不能被完全插入S中，T中会有字符被舍弃{for (i = 0; i < MAXSIZE - pos; i++)S->str[i + pos - 1] = T.str[i];S->length = MAXSIZE;return 0;}
}// 7. 删除串S中pos开始的len个字符
int StrDelete(SeqString *S, int pos, int len)
{int i;if (pos < 0 || len < 0 || pos + len - 1 > S->length)return 0;else{for (i = pos + len - 1; i <= S->length - 1; i++)S->str[i - len] = S->str[i];S->length -= len;return 1;}
}// 8.将串S连接到串T的末尾
int StrConcat(SeqString *T, SeqString S)
{int i, flag;if (T->length + S.length <= MAXSIZE){for (i = T->length; i < T->length + S.length; i++)T->str[i] = S.str[i - S.length];T->length += S.length;flag = 1; // S完整连接到T后面}else if (T->length <= MAXSIZE){for (i = T->length; i < MAXSIZE; i++)T->str[i] = S.str[i - T->length];T->length = MAXSIZE;flag = 0;}return flag;
}// 9. 清空串
void StrClear(SeqString *S)
{S->length = 0;
}
模式匹配KMP
// 模式匹配KMP
void get_next(SeqString T, int next[])
{int i = 1, j = 0;next[1] = 0;while (i < T.length){if (j == 0 || T.str[i] == T.str[j]){++i;++j;next[i] = j;}else{j = next[j];}}
}int Index_KMP(SeqString S, SeqString T, int next[])
{int i = 1, j = 1;while (i <= S.length && j <= T.length){if (j == 0 || S.str[i] == T.str[j]){++i;++j;}elsej = next[j];}if (j > T.length) // 匹配成功return i - T.length;return 0;
}
