数据结构基础

重拾数据结构

我认为数据结构相关的东西都是同一套模板，只不过是使用了不同的数据存储方式，所以看懂代码思路很重要，看懂思路后面的不论是顺序表，链表还是树，其实性质大差不差。

顺序表

#include<stdio.h>	 //若用printf,scanf,getchar,putchar,gets,puts函数需包含该头文件
#include<malloc.h>	//用malloc,free,realloc函数需包含该头文件
#include <iostream>

#define MAXSIZE 100	 //设线性表初始分配空间大小
typedef int ElemType;  //先设定数据元素的类型为整型

//0：定义顺序表的结构类型
typedef struct {
	ElemType* elem;
	int length;
	int listsize;
}SqList;

//1：初始化顺序表
int InitList_Sq(SqList& L)
{
	L.elem = (ElemType*)malloc(sizeof(ElemType) * MAXSIZE);
	if (!L.elem) return 0;
	L.length = 0;
	L.listsize = MAXSIZE;
	return 1;
}

malloc :动态内存分配，用法是（数据类型*）malloc(sizeof(要分配的地址块大小) * 块数量)

补充：realloc 动态修改内存

用法是 (数据类型* )realloc(原地址指针,新地址大小)

realloc的使用存在三种情况，一是如果后面的空间足够扩展，则会直接扩展；二是后面的空间不足扩展，realloc会调用malloc重新开辟一块大小为所需大小的内存空间，然后把原内容拷贝进来，并释放原空间；三是内存不足，扩展失败，此时原空间不会发生改变，realloc返回一个空地址。

//2：打印顺序表中所有元素
void PrintList(SqList& L)
{
	int i;
	for (i = 0; i < L.length; i++)
		printf("%d\n", L.elem[i]);
}

//*****3：在顺序表中第i个位置(i=1~n)插入元素*****
int ListInsert_Sq(SqList& L, int i, ElemType e) {
	if (i<1 || i>L.length + 1)
		return 0;
	
	for (int p = L.length - 1; p >= i; p--) {
		L.elem[p] = L.elem[p - 1];
	}
	L.elem[i - 1] = e;
	L.length++;
	return 1;
}

//*****4：删除顺序表中第i(i=1~n)个元素，用e返回删除的元素*****
int ListDelete_Sq(SqList& L, int i, ElemType& e)
{
	if (i<1 || i>L.length + 1)
		return 0;
	e = L.elem[i - 1];

	for (int p = i - 1; p < L.length - 1; p++) {
		L.elem[p] = L.elem[p + 1];
	}

	L.length--;

	return e;
}

这里遇到的坑无非就是何为length，插入位置，下标之间的关系，因为下标是从0开始，所以如果要使用下标，就要考虑length和插入位置都要减1，这就要牵扯出一些边界条件，对于拿不准的我比较喜欢简单画一下图，或者举一点数据量小的例子。

// 顺序表合并
void MergeList(SqList La, SqList Lb, SqList& Lc)
{
	int end_La = La.length;
	int end_lb = Lb.length;
	int i = 0, j = 0, c = 0;

	Lc.elem = (ElemType*)malloc(sizeof(ElemType) * MAXSIZE);
	Lc.length = end_La + end_lb;
	Lc.listsize = MAXSIZE;

	while (i < end_La && j < end_lb) {
		if (La.elem[i] < Lb.elem[j]) {
			Lc.elem[c] = La.elem[i];
			c++;
			i++;
		}
		else {
			Lc.elem[c] = Lb.elem[j];
			c++;
			j++;
		}
	}
	if (i < end_La) {
		while (La.elem[i]) {
			Lc.elem[c] = La.elem[i];
			i++;
			c++;
		}
	}
	if (j < end_lb) {
		while (Lc.elem[j]) {
			Lc.elem[c] = Lb.elem[j];
			j++;
			c++;
		}
	}
}
//主函数
int main()
{

}

单链表

单链表结点结构体:

typedef struct LNode {
    ///===============补充代码======================== 
    ElemType data;
    LNode* next;

}LNode, * LinkList;      // 定义节点类型以及链表类型（链表类型实际上是一个节点指针类型）

单链表有两种插入方法，一种头插法，一种尾插法，前者结果是倒序，后者为正序

头插法(i为1时)：

Status ListInsert_L(LinkList& L, int i, ElemType e) { // 算法2.9
    // 在带头结点的单链线性表L的第i个元素之前插入元素e   
  ///===============补充代码========================


    LNode* new_node = (LNode*)malloc(sizeof(LNode));
    new_node->data = e;
    new_node->next = NULL;
    LNode* per_node = L;
    for (int j = 0; j < i - 1; j++) {
        per_node = per_node->next;
    }

    new_node->next = per_node->next;
    per_node->next = new_node;

    return 1;
} // LinstInsert_L

尾插法：

Status ListInsert_N(LinkList& L) {

    int n;
    LNode* per_node = L;
    while (per_node->next != NULL && per_node != NULL) {
        per_node = per_node-> next;
    }
    std::cin >> n;
    int e;
    while (n) {
        std::cin >> e;
        LNode* new_node = (LNode*)malloc(sizeof(LNode));
        new_node->data = e;
        new_node->next = NULL;

        per_node->next = new_node;
        per_node = per_node->next;
        n--;
    }
    return OK;
}

单链表有一个容易被忽略的点是在new_node分配内存后一定要给其中的data，next赋初值，不然会越界。

队列

“先进先出”

队列结构体：

typedef struct
{
	ElemType* base;
	int front;
	int rear;
}SqQueue;

谈及队列一般都是指循环队列，因为普通队列在使用时，如果发生出队操作，那对头所在的空间就无法再返回使用了，导致空间的浪费，而使用循环队列，当队尾到达分配的MAXSIZE上限时，通过取余操作重新利用到已经出队的空间，具体操作在入队，出队，以及计算队长等均有体现：

//求队列的长度
int QueueLength(SqQueue& Q)
{
	return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}

//插入元素e作为Q的新的队尾元素，队满则返回0，否则返回1
int EnQueue(SqQueue& Q, ElemType e)
{
	if ((Q.rear + 1) % MAXQSIZE == Q.front) return 0;
	Q.base[Q.rear] = e;
	Q.rear = (Q.rear + 1) % MAXQSIZE;

	return 1;
}

//若队列不空，则删除Q的队头元素，用e返回其值，并返回1,否则返回0
int DeQueue(SqQueue& Q, ElemType& e)
{
	if (QueueEmpty(Q)) return 0;
	e = Q.base[Q.front];
	Q.front = (Q.front + 1) % MAXQSIZE;
	return 1;
}

栈

“后进先出”

栈结构体：

typedef struct STACK
{
	ElemType* base;
	ElemType* top;
	int size;
}SqStack;

栈所有的操作都只变化top指针，这点不同于队列，因为其后进先出的性质，栈在回溯算法利用的比较多，他可以实现“后退”操作，比如回到树的上一结点。栈的本质我认为就是个只能对末尾操作的数组，同理队列可以理解为可以两边同时操作的数组。

判空操作：

//判栈空
int StackEmpty(SqStack S)
{
	if (S.top == S.base) return 1;
	else return 0;
}

栈中元素个数：

//求栈中元素个数
int StackLength(SqStack S)
{
	if (StackEmpty) return 0;
	else
	 return S.top - S.base ;
}

这里S.top - S.base就能得到栈中元素个数，因为指针值相减的结果是两个指针之间的距离，即它们所指向的内存地址之间的偏移量。这个偏移量的单位取决于指针所指向的数据类型的大小。例如，在C语言中，如果两个指针指向相同类型的数组元素，那么它们之间的距离就是数组元素的个数乘以每个元素的大小。

入栈：

int Push(SqStack& s, ElemType e)
{
	if (StackLength(s) == MAXSIZE) {
		s.base = (ElemType*)realloc(s.base, sizeof(ElemType) * (s.size + STACKINCREMENT));
		s.size = s.size + STACKINCREMENT;
	}
	*(s.top++) = e;
	return 1;
}

这里加了一个扩容（其实之前都可以加，不过懒得都没加），栈的top一般都停在最近的一个空位，而不是指向栈尾，因此入栈后top要后移。

//出栈
int Pop(SqStack& s, ElemType& e)
{
	e = *(--s.top);
	return  1;
}

同理出栈top先前移。

数制转换

扩展一下栈的一个用法：数制转换

因为数制转换一般是使用短除法，最后将余数反向组合，反向组合就可以利用栈后进先出的性质，通过取整取余操作，就能实现简单的进制转换

//数制转换函数
void conversion()
{
	ElemType e;
	SqStack S;
	InitStack(S);
	int num;
	int jinzhi;
	std::cin >> num;
	std::cin >> jinzhi;
	while (num) {
		Push(S, num % jinzhi);
		num = num / jinzhi;
	}
	while (!StackEmpty(S)) {
		Pop(S,num);
		if (num <= 9) {
			std::cout << num << " ";
		}
		else {
			std::cout << (char)(num - 10 + 65) << std::endl;
		}
	}
	printf("\n");
}

因为16进制比较特殊，他会出现大于等于10的情况，这种情况要输出“ABC。。。”，所以在输出时加了一个判断，

else {
	std::cout << (char)(num - 10 + 65) << std::endl;
}

树

二叉树结构体：

typedef struct BiTNode
{
    ElemType data;
    BiTNode* left;
    BiTNode* right;

}BiTNode, * BiTree;

创建树：

void CreateBiTree(BiTree& T)//按先序次序输入，以"#"表示空树
{
    char input;
    std::cin >> input;
    if (input != '#') {
        T = (BiTree)malloc(sizeof(BiTNode));
        T->data = input;
        CreateBiTree(T->left);
        CreateBiTree(T->right);
    }
    else {
        T = NULL;
    }
}

这里注意点就是记得给空结点赋值为NULL（并不是默认为NULL，他会指向0FFFFF。。。）

void PreOrderTraverse(BiTree T)//先序遍历
{
    if (T != nullptr) {
        cout << T->data << endl;
        PreOrderTraverse(T->left);
        PreOrderTraverse(T->right);
    }
}
void InOrderTraverse(BiTree T)//中序遍历
{
    if (T != NULL) {

        InOrderTraverse(T->left);
        cout << T->data << endl;
        InOrderTraverse(T->right);
    }
}
void PostOrderTraverse(BiTree T)//后序遍历
{
    if (T != NULL) {

        PostOrderTraverse(T->left);
        PostOrderTraverse(T->right);
        cout << T->data << endl;
    }
}

求树深：

int BTDepth(BiTree T)//求二叉树的深度
{
    int Lheight;
    int Rheight;

    if (T != NULL) {
        Lheight = BTDepth(T->left);
        Rheight = BTDepth(T->right);    
    }
    else {
        return 0; 
    }
    return Lheight > Rheight ? Lheight + 1 : Rheight + 1;
}

遇到的问题：在树为NULL的时候忘记return 0了，在向上层return的时候忘记在当前深度的基础上加1

求叶结点个数：

void Leaf(BiTree T)//求二叉树的叶子数, 使用全局变量
{
    if (T != NULL) {
        Leaf(T->right);
        Leaf(T->left);
        if (T->left == NULL && T->right == NULL) {
            LEAFCOUNT++;
        }
    }
}

前两个递归调用的终点是每个叶节点，只需要判断是否递归到叶节点，条件就是左右子树都是空。

求总结点个数：

void NodeCount(BiTree T)
{
    stack<BiTree> st;
    while (T || !st.empty()) {
        if (T) {
            NODECOUNT++;
            st.push(T);
            T = T->left;
        }
        else {
            T = st.top();
            st.pop();
            T = T->right;
        }
    }
}

栈和while循环搭配使用的方法很适合遍历，如果树不为空就入栈继续遍历，如果树为空了那就栈顶出栈，继续走右节点，这种遍历方式或许还可以用到一些迷宫小游戏里。

非递归的遍历也是使用这种结构：

void Traverse_By_Stack(BiTree T) {
    stack<BiTree> sta;

    while (T || !sta.empty()) {
        if (T) {
            cout << T->data << endl; // 先序遍历
            sta.push(T);
            T = T->left;
        }
        else {
            T = sta.top();
            //cout << T->data << endl; // 后序遍历
            sta.pop();
            T = T->right;
        }
    }
}