序言
本文记录学习的经典数据结构的实现, 由于原严蔚敏的书中使用的代码为C with &, 因此在真正的实现上是需要依赖于 cpp 的, 因此本文在具体的实现上为了能够"真正使用"有一些细节上的改动.
在本文中的 ElemType 使用以下语句定义:
#ifndef ElemType
#define ElemType int
#endif
List
Static Sequence List
#define MaxSize 50
//数据类型为ElemType, 长度为 MaxSize 的静态线性表
typedef struct{
ElemType data[MaxSize];
int length;//表长
}SqList
int main(){
}
Dynamic Sequence List
Definition
#define InitSize 100
typedef struct{
ElemType *data; //表的地址
int MaxSize; //动态表的最大长度
int length; //当前动态表的长度
}SeqList;
int main(){
SeqList L;
L.data = (ElemType *)malloc(sizeof(ElemType) * InitSize); //动态分配
//
free(L);
return 0;
}
Operations
//初始化动态表L
bool InitList(SeqList &L){
L.data = (ElemType *)malloc(sizeof(ElemType) * InitSize);
if(L.data == NULL){//分配内存失败
return false;
}
L.length = 0;
return true;
}
//在静态顺序表L中的第 i 位插入元素 e
bool ListInsert(SqList &L, int i, ElemType e){
if(i < 1 || i > L.length + 1){ //判断传入的参数 i 是否合法
return false;
}
if(L.length >= MaxSize){ //判断静态表是否已满
return false;
}
for(int j = L.length; j >= i; j--){
L.data[j] = L.data[j - 1]; //依次后移
}
L.data[i - 1] = e;
L.length++;
return true;
}
//删除静态顺序表 L 中的第 i 位元素, 并且通过传入参数 e 保存删除的元素
bool ListDelete(SqList &L, int i, ElemType &e){
if(i < 1 || i > L.length){ //判断传入的参数 i 是否合法
return false;
}
for(int j = i; j < L.lrngth; j++){
L.data[j - 1] = L.data[j];//依次前移
}
L.length--;
return true;
}
//在静态顺序表 L 中查找第一个值为 e 的元素的[位置]
bool LocateElem(SqList &L, int i, ElemType e){
int i;
for(i = 0; i < L.length; i++){
if(L.data[i] == e){
return i + 1;//查找的是位置, 因此数组下标需要+1转换为编号
}
}
return 0;//查找失败
}
Linked List
Definition
//单链表
typedef struct ListNode{
ElemType data; //数据域
struct ListNode *next; //下一结点地址
}ListNode, *LinkList;
Operations
//头插法建立单链表 L
LinkList List_HeadInsert(LinkList &L){
ListNode *s;
int x;
L = (LinkList)malloc(sizeof(ListNode));
L -> next = NULL;
scanf("%d", &x);
while(x != 9999){ //输入9999即代表结束插入
s = (ListNode *)malloc(sizeof(ListNode));
s -> data = x;
s -> next = L -> next;
L -> next = s;
scanf("%d", &x);
}
return L;
}
//尾插法建立单链表 L
LinkList List_TailInsert(LinkList &L){
int x;//接收键盘输入的数值
L = (LinkList)malloc(sizeof(ListNode));
ListNode *new_node, *tail = L; //tail 为表尾指针
scanf("%d", &x);
while(x != 9999){ //输入9999即代表结束插入
new_node = (ListNode *)malloc(sizeof(ListNode));
new_node -> data = x;
tail -> next = new_node;
tail = new_node;
scanf("%d", &x);
}
tail -> next = NULL; //将尾指针置空
return L;
}
//在单链表 L 中按照序号查找结点
ListNode *GetElem(LinkList L, int i){
if(i < 1){//检查传入的参数 i 是否合法
return NULL;
}
int j = 1;
ListNode *ptr = L -> next;
while(ptr != NULL && j < i){
ptr = ptr -> next;
j++;
}
return ptr;
}
//在单链表 L 中按照值查找结点
ListNode *LocateElem(LinkList L, ElemType e){
ListNode *ptr = L -> next;
while(ptr != NULL && ptr -> data != e){
ptr = ptr -> next;
}
return ptr;
}
Stack(template)
template<typename T, int Size>//模板类, 传入参数栈元素的数据类型 T, 和栈的最大深度 Size
class Stack{
private:
T data[size];
int top; //当前栈中的栈顶元素的数组下标
public:
Stack():top(-1){
//初始化函数
}
~Stack(){
//析构函数
}
//向栈进入元素 item
bool push(T item){
if(top == Size - 1){ //检测栈是否已满
return false;
}
data[++top] = item;
return true;
}
//出栈栈顶元素, 并且使用 topElem 记录这个元素
bool pop(T &topElem){
if(top == -1){ //检验栈是否为空
return false;
}
topElem = data[top];
return true;
}
//判断栈是否为空
bool isEmpty(){
return top == -1;
}
//判断栈是否已满
bool isFull(){
return top == Size - 1;
}
}
Queue(Template)
template<typename T, int Size>//模板类, 传入参数队列元素的数据类型 T, 和队列的最大长度 Size
class Queue{
private:
T data[Size];
int front; //队头元素数组下标
int rear; //队尾元素数组下标
int tag; //辅助变量, 判断队列为空/满
public:
Queue(): front(0), rear(0), tag(0){
//构造函数
}
~Queue(){
//析构函数
}
//元素 item 入队
bool EnQueue(T, item){
if(front == rear && tag == 1){ //判断队列是否已满
return false;
}
rear = (rear + 1) % Size;
data[rear] = item;
tag = 1; //进行入队操作后, 将tag = 1, 这样 rear == front时只有可能为满
return true;
}
//队列出队, 并且记录出队元素 item
bool DeQueue(T &item){
if(front == rear && tag == 0){ //判断队列是否为空
return false;
}
rear = (rear + 1) % Size;
tag[rear] = item;
tag = 0; //进行出队操作后, 将tag = 0, 这样 rear == front时只有可能为空
return true;
}
//判断队列是否为空
bool isEmpty(){
return front == rear && tag == 0;
}
//判断队列是否为满
bool isFull(){
return front == rear && tag == 1;
}
}
String
Definition
Static String
static const int MAXLEN = 255;//字符串的最大长度
//静态分配字符串
typedef struct{
char ch[MAXLEN];//数据域
int length; //字符串长度
}SString
Dynamic String
//动态分配字符串
typedef struct{
char *ch; //字符数组的地址
int length; //字符串长度
}HString;
Linked List String
//使用字符串结点存储字符串
typedef struct StringNode{
char ch[4]; //4个字符一组存放在一个结点中
struct StringNode *next; //下一个字符结点的地址
}StringNode, *String;
Operations
Static String
//求静态字符串 S 中, 以 pos 为起点, 长为 len 的子串 sub.
//在这里, 我们设定字符串的S[0]不存储任何元素, 而是从S[1]开始存储字符串的元素
bool SubString(SString &sub, SString S, int pos, int len){
if(pos + len - 1 > S.length){ //检测子串末尾是否已经溢出原串长度
return false;
}
for(int i = pos; i < pos + len; i++){
sub.ch[i - pos + 1] = S.ch[i];
}
}
//比较两个静态串的大小
//串的大小定义:(1)首先比长度(2)长度相等时, 比char对应的int.
bool StrCompare(SString S, SString, T){
for(int i = 1; i <= S.length && i <= T.length; i++){
if(S.ch[i] != T.ch[i]){
return S.ch[i] - T.ch[i];
}
}
//未能在以上循环中完成输出, 说明两个串呈现包含关系(即S 是 T的子串, 或者相反)
//那么就应该使用长度来比较
return S.length - T.length;
}
//查询静态串的长度
int StrLength(SStrng S){
return S.length;
}
//使用朴素便利方法查询子串 T 首次出现在 S 中时的位置
int Index(SString S, SString T){
int i = 1, j = 1;
while(i <= S.length && j <= T.length){
if(S.ch[i] == T.ch[i]){
//匹配成功, i,j同步后移以进行下一位的比较
}
else{
//匹配失败, 则 i 回到原先起点的下一位开始重新匹配
i = i - j + 2;
j = 1;
}
}
if(j > T.length){
return i - T.length;
}
else{
return 0;
}
}
//使用KMP算法, 借助next[]数组查询子串 T 首次出现在 S 中时的位置
int Index_KMP(SString S, SString T, int next[]){
int i = 1, j = 1;
while(i <= S.length && j <= T.length){
if(j == 0 || S.ch[i] = = T.ch[j]){
i++;
j++;
}
else{
j = next[j];
}
}
if(j > T.length){
return i - T.length;
}
else{
return 0;
}
}
//根据next[]数组生成nextval[]数组, 从而优化KMP算法
int *next2nextval(SString T, int next[]){
int *nextval = (int *)malloc(T.length * sizeof(char));
nextval[1] = 0;
for(int j = 2; j <= T.length; j++){
if(T.ch[next[j]] == T.ch[j]){
nextval[j] = nextval[next[j]];
}
else{
nextval[j] = next[j];
}
}
return nextval;
}
Dynamic String
//初始化动态字符串
bool InitHString(HString &S){
S.ch = (char *)malloc(MAXLEN * sizeof(char));
if(S.ch == NULL){ //内存分配失败
return false;
}
S.length = 0;
return true;
}
Tree & Binary Tree
Binary Tree
Definition
#define MAXSIZE 10
//二叉树结点
typedef struct BiTNode{
ElemType data; //数据域
struct BiTNode *lchild; //左子树根结点地址
struct BiTNode *rchild; //右子树根结点地址
}BiTNode, *BiTree;
Operations
//初始化二叉树root
void InitBiTree(BiTree &root){
root = NULL;//通过置空来清洗之间root所在空间中地址
root = (BiTree)malloc(sizeof(BiTNode));
root -> data = 1;
root -> lchild = NULL;
root -> rchild = NULL;
}
//向二叉树root中插入值为 val 的结点
bool InsertBiTNode(BiTree &root, ElemType val){
BiTNode *new_node = (BiTNode *)malloc(sizeof(BiTNode));
if(new_node == NULL){
return false;
}
if(root -> lchild == NULL){
root -> lchild = new_node;
new_node -> data = val;
new_node -> lchild = NULL;
new_node -> rchild = NULL;
}
else if(root -> rchild == NULL){
root -> rchild = new_node;
new_node -> data = val;
new_node -> lchild = NULL;
new_node -> rchild = NULL;
}
else{
std::cout << "Invalid root!" << std::endl;
return false;
}
}
//定义方位二叉树结点的行为
void observe(BiTree T){
std::cout << T -> data << std::endl;
}
//前根遍历二叉树 T
//使用递归定义
void PreOrder(BiTree T){
if(T != NULL){
observe(T);
PreOrder(T -> lchild);
PreOrder(T -> rchild);
}
}
//中根遍历二叉树 T
//使用递归定义
void InOrder(BiTree T){
if(T != NULL){
InOrder(T -> lchild);
observe(T);
InOrder(T -> rchild);
}
}
//后根遍历二叉树 T
//使用递归定义
void PostOrder(BiTree T){
if(T != NULL){
PostOrder(T -> lchild);
PostOrder(T -> rchild);
observer(T);
}
}
//层次遍历二叉树 T
//借助队列模板类实现
void LevelOrder(BiTree T){
Queue<BiTree,20>queue;
BiTree p = NULL;
queue.Enqueue(T);
while(!queue.isEmpty()){
queue.DeQueue(p);
observe(p);
if(p -> lchild != NULL){
queue.EnQueue(p -> lchild);
}
if(p -> rchild != NULL){
queue.EnQueue(p -> rchild);
}
}
}
Thread Tree
Definition
typedef struct ThreadNode{
ElemType data; //数据域
struct ThreadNode *lchild; //左子树的根结点地址
struct ThreadNode *rchild; //右子树的根结点地址
int ltag; //标记左子树根结点是否为线索, 1 为 是, 0 为 非
int rtag; //标记右子树根结点是否为线索, 1 为 是, 0 为 非
}
Operation
//使用全局变量 pre 来指定前驱结点
ThreadNode *pre = NULL;
//访问行为 visit()
void visit(ThreadNode *nodeptr){
//没有左孩子, 则空链域可以用来存储前驱结点地址
if(nodeptr -> lchild == NULL){
nodeptr -> lchild = pre;
nodeptr -> ltag = 1;
}
//没有右孩子, 则空链域可以用来存储后继结点地址
if(pre != NULL && pre -> rchild == NULL){
pre -> rchild = nodeptr;
pre -> rtag = 1;
}
pre = nodeptr;
}
