首页 C&C++ 数据结构与算法分析

事先声明，我并没有把所有源代码贴出来，太多了，而且一篇文章压根讲不完，只好粗略写写了，其次，还有我懒，想看完整源代码可以去我 github 仓库看。

# 只调整指针来交换两个相邻的元素 (单链表和双链表)

需要考虑三种情况：交换节点处于中间、队首或队尾、只有一个节点。
双链表虽然有些不同，但大致情况差不多。

交换相邻元素
// 单链表
List SwapNode(List pos, List head)
{
    if(pos->next==NULL)
       return head;
    if(head == pos)
    {
        List pos1 = pos->next;
        List pos2 = pos1->next;
        pos1->next = pos;
        pos->next = pos2;
        head = pos1;
        return head;
    }
    else
    {
        List prev = FindPreviousNode(pos, head);
        List pos1 = pos->next;
        List pos2 = pos1->next;
        pos1->next = pos;
        pos->next = pos2;
        prev->next = pos1;
        return head;
    }
}
// 双链表
DoubleList SwapDoubleNode(DoubleList pos,DoubleList start)
{
    // 只有一个节点
    if(start->next == NULL&&start->prev == NULL)
       return start;
    // 有多个节点
    if(pos==start)// 交换位于头节点
    {
        if(pos->prev == NULL)// 尾插法
        {
            DoubleList pos1 = pos->next;
            DoubleList pos2 = pos1->next;
            pos->next = pos2;
            pos->prev = pos1;
            pos1->next = pos;
            pos1->prev =NULL;
            pos2->prev = pos;
            start = pos1;
            return start;
        }
        else if(pos->next == NULL)// 头插法
        {
            DoubleList pos1 = pos->prev;
            DoubleList pos2 = pos1->prev;
            pos->next = pos1;
            pos->prev = pos2;
            pos1->next = NULL;
            pos1->prev = pos;
            pos2->next = pos;
            start = pos1;
            return start;
        }
    }
    else// 处于中间交换
    {
        DoubleList pos1 = pos->prev;
        DoubleList pos2 = pos1->prev;
        DoubleList prev = pos->next;
        prev->prev = pos1;
        pos1->next = prev;
        pos1->prev = pos;
        pos->next = pos1;
        pos->prev = pos2;
        pos2->next = pos;
        return start;
    }
    return NULL;
}
# 给定两个已排序的表 L1 和 L2, 使用基本的表操作编写计算L1∪L2L1\cup L2 和L1∩L2L1\cap L2 的过程
说白了是写并查集，当时我憨憨了，没有考虑到重复元素，而且写了重复的代码片段。
这里假设 L1 是长链表，L2 是短链表，目标链表为 L3。
交集大致思路如下:
  1. 取 L1 的一个值 L1.num
  2. 遍历 L2 的值和 L1.num 比较
  3. 如果有相同的，L1.num 存入 L3
  4. L1 指向下一个节点，返回第一步，为空则结束，返回 L3
并集大致思路如下:
  1. 取 L1 的一个值 L1.num
  2. 遍历 L2 的值和 L1.num 比较
  3. 如果有相同的，L1.num 存入 L3
  4. L1 指向下一个节点，返回第一步，为空则结束
  5. 取 L2 的一个值 L2.num 存入 L3
  6. L2 指向下一个节点，返回第五步，为空则结束，返回 L3
并集与交集
// 链表交集
void Intersection(List head1,List head2,int* arr)
{
    List pos1 = head1;
    List pos2 = head2;
    int i = 0;
    if(Length(head1)>=Length(head2))
    {
        while(pos1!= NULL)
        {
            if(pos2->num==pos1->num)
            {
                arr[i++] = pos1->num;
                pos2 = pos2->next;
            }
            pos1 = pos1->next;
        }
    }
    else
    {
        while(pos2!= NULL)
        {
            if(pos2->num==pos1->num)
            {
                arr[i++] = pos1->num;
                pos1 = pos1->next;
            }
            pos2= pos2->next;
        }
    }
}
// 链表并集
void Union(List head1,List head2,int* arr)
{
    List pos1,pos2;
    pos1 = head1;
    int i = 0;
    while(pos1 != NULL)
    {
        pos2 = head2;
        while(pos2 !=NULL&&pos2->num!=pos1->num)// 遍历 head2 链表匹配
              pos2 = pos2->next;
        if(pos2==NULL)// 当两个元素不相同时 存入数组 arr
        {
            arr[i++] = pos1->num;
        }
        pos1 = pos1->next;
    }
    pos2 = head2;
    while(pos2!= NULL)// 把 head2 链表接到 arr 后面
    {
        arr[i++] = pos2->num;
        pos2 = pos2->next;
    }
}
之所以返回时 void 是因为当时写的时候没有想到，以下是我认为更标准的函数声明
List Union (const List head1, const List head2, const int* arr);
List Intersection(const List head1, const List head2, const int* arr);
# 编写将两个多项式相加的函数。不要毁坏输入数据。用一个链表实现。如果这两个多项式分别有 M 项和 N 项，那么你的程序的时间复杂度是多少？
这里假设第一个链表为 y1, 第二个链表为 y2, 复制的链表为 y, 后面多项式相乘的题的同理。
多项式相加大致思路如下:
  1. 复制链表 y1 为链表 y
  2. 取 y2 的指数 y2.Exponent
  3. 遍历 y1 的指数值和 y2.Exponent 比较
  4. 指数相同，y1 和 y 系数相加
  5. 指数不相同，该元素插入 y
  6. y2 指向下一个节点，返回第二步，为空则结束
  7. 返回 y 的头节点
多项式相加
Polynomial Addition(Polynomial head1, Polynomial head2)
{
    Polynomial y1, y2;
    y1 = head1; y2 = head2;
    Polynomial y = Copy(y1);// 复制一个链表
    while (y2 != NULL)
    {
        y1 = y;
        while (y1 != NULL && y1->Exponent != y2->Exponent)//y2 链表每个元素遍历一遍 y1 链表匹配元素
            y1 = y1->next;
        if (y1 == NULL){// 没有相同元素插入
            y = Insert(y, y2);
        }
        else {// 有则系数相加
            y1->Coefficient = y1->Coefficient + y2->Coefficient;
        }
        y2 = y2->next;
    }
    return y;
}
时间复杂度为O(N2)O(N^2)
# 编写一个函数将两个多项式相乘，用一个链表实现。你必须保证输出的多项式按幂次排列，并且任意幂次最多只有一项
  • a. 给出以O(M2N2)O(M^2N^2) 时间求解该问题的算法。
  • b. 写一个以O(M2N)O(M^2N) 时间执行乘法的程序，其中 M≤N。
我直接写的时 b 题，a 题不做解释。
多项式相乘大致思路如下:
  1. y2 第一个节点多项式与与 y1 所以多项式相乘的链表 y
  2. y2 指向下一个节点
  3. 遍历 y1 多项式与 y2 当前节点多项式相乘的多项式 temp
  4. 遍历 y 的多项式与 temp 比较
  5. 指数相同，temp 与 y 的系数相加
  6. 指数不同，temp 插入 y
  7. y2 指向下一个节点，返回第三步，为空则结束
  8. 返回 y 的头节点
多项式相乘
Polynomial Multiply(Polynomial head1, Polynomial head2)
{
    Polynomial y1, y2, y,head;
    head = y = NULL;
    y1 = head1;
    y2 = head2;
    while(y1!= NULL)// 先得到一个链表
    {
        Polynomial temp = malloc(sizeof(struct Node));
        temp->Coefficient = y1->Coefficient*y2->Coefficient;
        temp->Exponent  = y1->Exponent+y2->Exponent;
        temp->next = NULL;
        if(y==NULL){
            y = head = temp;
        }
        else{
            y->next = temp;
            y = temp;
        }
        y1 = y1->next;
    }
    y2 = y2->next;// 从第二个节点开始
    while(y2 != NULL)
    {
        y1 = head1;
        while(y1 != NULL)
        {
            Polynomial temp = malloc(sizeof(struct Node));
            temp->Coefficient = y1->Coefficient*y2->Coefficient;
            temp->Exponent  = y1->Exponent+y2->Exponent;
            temp->next = NULL;
            // 比较
            y = head;
            while(y!= NULL&& y->Exponent!=temp->Exponent)
                y = y->next;
            if(y==NULL){
                head = Insert(head,temp);
                free(temp);
            }
            else{
                y->Coefficient = y->Coefficient+temp->Coefficient;
                free(temp);
            }
            y1 = y1->next;
        }
        y2 = y2->next;
    }
    return head;
}
时间复杂度为O(M2N)O(M^2N)。
# 编写任意精度整数运行包。要使用类似于多项式运算的方法。计算在240002^4000 内数字 0 到 9 的分布
别被任意精度整数运行包吓到了，说白了就是让你写个大整数存储、比较和加减乘除，还有更难得操作我也不会，具体可以参考大整数运算和大整数除法这两篇文章。
举个例子，unsigned long long 类型最大值为 18446744073709551615(264−1)(2^{64} - 1), 比这大得数就是大整数。
以下是大整数常规操作思路 (双链表):
  • 大整数存储
    1. 输入设备依次读取字符
    2. 字符转换为对应得数值，存入链表
    3. 返回第一步，字符为 EOF 则结束
  • 大整数比较
    1. 比较链表 L1 和 L2 长度
    2. L1 长度大于 L2 长度，返回 MORE
    3. L1 长度小于 L2 长度，返回 LESS
    4. L1 长度等于于 L2 长度，L1 和 L2 指针有低位移向高位
    5. 由最高位开始，遍历 L1 和 L2 同位数字比较，大于返回 MORE, 小于返回 LESS
    6. 否则最终返回 EQUAL
  • 大整数加法
    1. 大整数比较得长链表 L1 和短链表 L2
    2. 由低位开始，同时遍历 L1 和 L2,L1 和 L2 同位数字和进位相加，保留进位 1, 存入另一链表 L
    3. 若遍历完仍有进位，头插法插入 L
    4. 返回 L 的头节点
  • 大整数减法
    1. 大整数比较得长链表 L1 和短链表 L2
    2. 由低位开始，同时遍历 L1 和 L2
    3. 第一次借位时，借位 carry 为 10
    4. 第二次以上借位时，carry 为 9
    5. 最后一次借位时，carry 为 - 1
    6. L1 和 L2 同为相减时，存储值为 L1->num-L2->num+carry 并存入链表 L
    7. 返回第二步，L1 为空则结束
    8. 清除 L 前面的零
  • 大整数乘法
    1. 大整数比较得长链表 L1 和短链表 L2
    2. 由低位开始，L2 第一位与 L1 所有元素相乘得链表 L
    3. L2 指向上一位，L2 元素与 L1 所有元素相乘得到链表 temp
    4. L 和 temp 相加，销毁链表 temp
    5. L 指向要向前移动一位，返回第三步
    6. 返回 L 得头节点
  • 大整数除法
    1. 计算除数 L1 的长度和被除数 L2 的长度
    2. 若被除数长度小于除数长度，返回 0
    3. 若被除数长度等于除数长度，返回除数减大整数 (大整数减法) 的次数
    4. 若被除数长度大于除数长度
    5. 计算被除数与除数长度之差 diff
    6. 除数补 diff 个零
    7. 被除数减除数，所得值存入链表 L
    8. diff 减一，返回第六步，diff 为 0 则结束
    9. 返回链表 L 的头节点
大整数常规操作
// 大整数存储
void BigIntegerStorage(Position head, Position L)
{
	int ch;
	while ((ch = getchar()) != '\n')
		*L = CreateNode(ch - 48, head, L);
}
// 大整数比较
Judge BigIntegerCompare(List head1, List head2)
{
	if (Length(head1) > Length(head2))
		return MORE;
	else if (Length(head1) < Length(head2))
		return LESS;
	else if (Length(head1) == Length(head2)) {
		List L1 = head1;
		List L2 = head2;
		if (L1->next == NULL)// 若是低位从高位开始
		{
			for (int i = 0; i < Length(head1) - 1; i++)
				L1 = L1->prev;
		}
		if (L2->next == NULL)// 若是低位从高位开始
		{
			for (int i = 0; i < Length(head1) - 1; i++)
				L2 = L2->prev;
		}
		while (L1 != NULL)
		{
			if (L1->num > L2->num)
				return MORE;
			else if (L1->num < L2->num)
				return LESS;
			else if (L1->num == L2->num) {
				L1 = L1->next;
				L2 = L2->next;
			}
		}
	}
	return EQUAL;
}
// 大整数加法
List BigIntegerAdd(List rear1, List rear2)
{
	List L1 = NULL, L2 = NULL;
	List head = NULL;
	int carry = 0;
	if (BigIntegerCompare(rear1, rear2) == MORE || BigIntegerCompare(rear1, rear2) == EQUAL) {
		L1 = rear1;
		L2 = rear2;
	}
	else if (BigIntegerCompare(rear1, rear2) == LESS) {
		L1 = rear2;
		L2 = rear1;
	}
	while (L1 != NULL)
	{
		List temp = malloc(sizeof(struct Node));
		if (L2 == NULL) {
			temp->num = L1->num + carry;
		}
		else
			temp->num = L1->num + L2->num + carry;
		carry = 0;
		temp->next = NULL;
		temp->prev = NULL;
		if (temp->num >= 10)
		{
			carry = 1;
			temp->num = temp->num % 10;// 取个位数
		}
		if (head == NULL)
		{
			head = temp;
		}
		else {// 头插法
			head->prev = temp;
			temp->next = head;
			head = temp;
		}
		L1 = L1->prev;
		if (L2 != NULL) {
			L2 = L2->prev;
		}
	}
	if (carry == 1)
	{
		List temp = malloc(sizeof(struct Node));
		temp->num = carry;
		temp->next = NULL;
		temp->prev = NULL;
		head->prev = temp;
		temp->next = head;
		head = temp;
	}
	return head;
}
// 大整数减法
List BigIntegerSubtract(List rear1, List rear2)
{
	List L1 = NULL, L2 = NULL;
	List head = NULL;
	if (BigIntegerCompare(rear1, rear2) == MORE || BigIntegerCompare(rear1, rear2) == EQUAL) {
		L1 = rear1;
		L2 = rear2;
	}
	else if (BigIntegerCompare(rear1, rear2) == LESS) {
		L1 = rear2;
		L2 = rear1;
		SIGN = 0;
	}
	int carry = 0;
	int flag = 0;
	while (L1 != NULL)
	{
		List temp = malloc(sizeof(struct Node));
		if (L2 != NULL) {
			if (L1->num < L2->num && flag == 0) {
				carry = 10;
				flag = 1;
			}
			else if (L1->num < L2->num && flag == 1) {
				carry = 9;
			}
			else if (L1->num > L2->num && flag == 1) {
				carry = -1;
				flag = 0;
			}
		}
		else if (L2 == NULL && flag == 1) {
			carry = -1;
			flag = 0;
		}
		if (L2 != NULL) {
			temp->num = L1->num - L2->num + carry;
		}
		else if (L2 == NULL) {
			temp->num = L1->num + carry;
		}
		carry = 0;
		temp->next = NULL;
		temp->prev = NULL;
		if (head == NULL)
		{
			head = temp;
		}
		else {// 头插法
			head->prev = temp;
			temp->next = head;
			head = temp;
		}
		L1 = L1->prev;
		if (L2 != NULL) {
			L2 = L2->prev;
		}
	}
	if (Length(head) != 1)// 长度不为 1 时
	{
		while (head->num == 0&&Length(head)!=1)// 若最高位前面有零
		{
			List temp = head;
			head = head->next;
			head->prev = NULL;
			free(temp);
		}
	}
	return head;
}
// 大整数乘法
List BigIntegerMultiply(List rear1, List rear2)
{
	List L1 = NULL, L2 = NULL;
	List head = NULL, rear = NULL;
	if (BigIntegerCompare(rear1, rear2) == MORE || BigIntegerCompare(rear1, rear2) == EQUAL) {
		L1 = rear2;
		L2 = rear1;
	}
	else if (BigIntegerCompare(rear1, rear2) == LESS) {
		L1 = rear1;
		L2 = rear2;
	}
	List ret = L2;
	/** 先得到一个链表 START**/
	int carry = 0;
	while (ret != NULL)
	{
		List temp = malloc(sizeof(struct Node));
		temp->num = L1->num * ret->num + carry;
		temp->next = NULL;
		temp->prev = NULL;
		carry = 0;
		if (temp->num >= 10)
		{
			carry = temp->num / 10;
			temp->num = temp->num % 10;
		}
		if (head == NULL)
		{
			rear = head = temp;
		}
		else {// 头插法
			head->prev = temp;
			temp->next = head;
			head = temp;
		}
		ret = ret->prev;
	}
	if (carry != 0)
	{
		List temp = malloc(sizeof(struct Node));
		temp->num = carry;
		temp->next = NULL;
		temp->prev = NULL;
		head->prev = temp;
		temp->next = head;
		head = temp;
	}
	/** 先得到一个链表 END**/
	L1 = L1->prev;
	while (L1 != NULL)
	{
		/** 再得到另外一个链表 START****/
		carry = 0;
		List head1 = NULL, rear3 = NULL;
		ret = L2;
		while (ret != NULL)
		{
			List temp = malloc(sizeof(struct Node));
			temp->num = L1->num * ret->num + carry;
			temp->prev = NULL;
			temp->next = NULL;
			carry = 0;
			if (temp->num >= 10)
			{
				carry = temp->num / 10;
				temp->num = temp->num % 10;
			}
			if (head1 == NULL)
			{
				rear3 = head1 = temp;
			}
			else {// 头插法
				head1->prev = temp;
				temp->next = head1;
				head1 = temp;
			}
			ret = ret->prev;
		}
		if (carry != 0)
		{
			List temp = malloc(sizeof(struct Node));
			temp->num = carry;
			temp->next = NULL;
			temp->prev = NULL;
			head1->prev = temp;
			temp->next = head1;
			head1 = temp;
		}
		/** 再得到另外一个链表 END****/
		/** 两链表相加 START **/
		List pos = rear->prev;
		carry = 0;
		while (rear3 != NULL)
		{
			if (pos != NULL)
			{
				pos->num = pos->num + rear3->num + carry;
				carry = 0;
				if (pos->num >= 10)
				{
					carry = 1;
					pos->num = pos->num % 10;
				}
			}
			else {
				List temp = malloc(sizeof(struct Node));
				temp->num = head1->num + carry;
				carry = 0;
				temp->next = NULL;
				temp->prev = NULL;
				head->prev = temp;
				temp->next = head;
				head = temp;
			}
			rear3 = rear3->prev;
			if (pos != NULL)
				pos = pos->prev;
		}
		Delete(head1);// 销毁临时链表
		/** 两链表相加 END **/
		rear = rear->prev;// 目标指针向前移一位
		L1 = L1->prev;
	}
	return head;
}
// 大整数除法
List BigIntegerDivision(List rear1, List rear2)
{
	int len1 = Length(rear1);
	int len2 = Length(rear2);
	List head = NULL;
	if (len1 < len2)
	{
		head = malloc(sizeof(struct Node));
		head->num = 0;
		head->next = NULL;
		head->prev = NULL;
	}
	else if (len1 == len2) {
		head = malloc(sizeof(struct Node));
		head->num = 0;
		head->next = NULL;
		head->prev = NULL;
		List L1 = Copy(rear1);
		while (BigIntegerCompare(L1, rear2) == MORE || BigIntegerCompare(L1, rear2) == EQUAL)
		{
			head->num++;// 次数加 1
			while (L1->next != NULL)// 头指针转向尾指针
			{
				L1 = L1->next;
			}
			L1 = BigIntegerSubtract(L1, rear2);
		}
		Delete(L1);
	}
	else if (len1 > len2) {
		int diff = len1 - len2 + 1;
		List rear = NULL;
		List L1 = Copy(rear1);
		while (diff)
		{
			/** 目标链表 START**/
			List temp1 = malloc(sizeof(struct Node));
			temp1->next = NULL;
			temp1->prev = NULL;
			temp1->num = 0;
			if (head == NULL)
			{
				head = rear = temp1;
			}
			else {
				rear->next = temp1;// 尾插法
				temp1->prev = rear;
				rear = temp1;
			}
			/** 目标链表 END**/
			/** 补零 START**/
			List L2 = Copy(rear2);
			for (int i = 0; i < diff - 1; i++)
			{
				List temp = malloc(sizeof(struct Node));
				temp->num = 0;
				temp->next = NULL;
				temp->prev = NULL;
				L2->next = temp;// 尾插法
				temp->prev = L2;
				L2 = temp;
			}
			/** 补零 END**/
			while (BigIntegerCompare(L1, L2) == MORE || BigIntegerCompare(L1,L2) == EQUAL)
			{
				rear->num++;// 次数加 1
				while (L1->next != NULL)// 头指针转向尾指针
				{
					L1 = L1->next;
				}
				L1 = BigIntegerSubtract(L1, L2);
			}
			Delete(L2);
			diff--;
		}
		Delete(L1);
	}
	if (Length(head) != 1)// 长度不为 1 时
	{
		while (head->num == 0 && Length(head) != 1)// 若最高位前面有零
		{
			List temp = head;
			head = head->next;
			head->prev = NULL;
			free(temp);
		}
	}
	return head;
}
# 约瑟夫 (Josephus) 问题
Josephus 问题是下面的游戏: N 个人从 1 到 N 编号，围坐成一个圆圈。从一号开始传递一个热土豆。经过 M 次传递后拿着热土豆的人被清除离座，围坐的圆圈缩紧，由坐在被清除的人后面的人拿起热土豆继续进行游戏。最后剩下的人获胜。因此，如果 M=0 和 N=5，则依次被清除后，5 号获胜。如果 M=1 和 N=5, 那么被清除的人的顺序是 2,4,1,5。
  • a. 编写一个程序解决 M 和 N 在一般值下的 Josephus 问题，应使你的程序尽可能地高效，要确保能够清除单元。
  • b. 你的程序的运行时间是多少？
我是用一个循环链表解决的，有的人是用递归解决的，运行时间为 0.01827S。
约瑟夫(Josephus)问题参考链接
// 循环链表解决约瑟夫问题 O (MN)
void Josephus(int* arr,int length, int N)
{
    List pos = malloc(sizeof(struct Node));
    pos->num = arr[0];
    pos->next = pos;
    for (int i = 1; i < length; i++)
    {
        List temp = malloc(sizeof(struct Node));
        temp->num = arr[i];
        temp->next = pos->next;
        pos->next = temp;
        pos = temp;
    }
    int total = length-1;
    pos = pos->next;
    while(total--)
    {
        for(int i = 0; i <N-1;i++ )
        {
            pos = pos->next;
        }
        List temp = pos->next;
        pos->next = pos->next->next;
        pos = pos->next;
        free(temp);
    }
    printf("%d\n",pos->num);
    free(pos);
}
# 编写查找一个单链表特定元素的程序。分别使用递归和非递归方法实现，并比较它们的运行时间。链表必须达到多大才能使使用递归的程序崩溃
挺简单的，我觉得不需要说明都能看懂，用 vscode 我的计算机 40000 以上递归崩溃。
查找单链表特定元素
// 找到特定元素的节点并返回位置 (非递归版)
List FindNode(int Element, List head)
{
    List point = head;
    while (point != NULL)
    {
        if (point->num == Element)
        {
            return point;
        }
        point = point->next;
    }
    return NULL;
}
// 找到特定元素的节点并返回位置 (递归版)
List ReFindNode(int Element, List head)
{
    if(head)
    {
        if(head->num==Element)
        return head;
        else{
            head = head->next;
            return ReFindNode(Element, head);
        }
    }
    return NULL;
}
# 反转单链表
  • a. 编写一个非递归程序以 O (N) 时间反转单链表
  • b. 使用常数附加空间编写一个非递归程序以 O (N) 时间反转单链表
说真的，常数附加空间我没懂，思路是使用双指针迭代法反转单链表
反转单链表
List Reverse(List head)
{
    if(head == NULL||head->next == NULL)
    {
        return head;
    }
    List cur = head;
    List pre = NULL;
    while (cur != NULL)
    {
        List temp = cur->next;
        cur->next = pre;
        pre = cur;  
        cur = temp;
    }
    return pre;
}
# 利用社会安全号码对学生记录构成的数组排序。1000 个桶的基数排序并分三趟进行。
核心思想是桶排序，只不过排序用的桶做了点变化，是一个数组链表。
大致思路如下:
  1. 分配 1000 个桶并初始化 (0~999)
  2. 取社会安全号码低三位数
  3. 放入相应的桶，遍历桶，把号码重新放回数组中，重新初始化桶
  4. 取号码中三位，重复第三步
  5. 取号码前三位，重复第三步
  6. 返回数组
桶排序
void BucketSort(int *arr,int length)
{
    struct Node stu[1000];
    // 结构体数组初始化
    for (int i = 0; i <1000;i++)
    {
        stu[i].next = NULL;
        stu[i].num = 0;
    }
    for (int n = 0; n <3;n++)
    {
        // 放入桶中
        for (int i = 0; i <length;i++)
        {
            CreateNode(arr[i],&stu[three(arr[i],n)]);
        }
        // 重新放入数组 arr
        int k = 0;
        for (int i = 0; i <1000;i++)
        {
            // 如果桶中有数
            if(stu[i].num!=0)
            {
                List head = &stu[i]; 
                while(head!=NULL)
                {
                    arr[k++] = head->num;
                    head = head->next;
                }
                // 初始化有数的桶
                head = &stu[i];
                if(Length(head)==1)
                {
                    stu[i].next = NULL;
                    stu[i].num = 0;
                }
                else{
                    DeleteNode(head->next);
                    stu[i].next = NULL;
                    stu[i].num = 0;
                }
            }
        }
    }
    for (int i = 0; i <length; i++)
    {
        printf("%d ",arr[i]);
    }
}
# 编写检测平衡符号的程序 (/* */,(),[ ],{ })
栈的典型应用，深入下去可以写个语法分析器。参考文章有 java 版本和 C++ 版本。
大致思路如下:
  1. 打开文件
  2. 依次读取文件的字符
  3. 如果是 (,[,{入栈，若是 /, 下一个符号时 * 入栈，否则报错
  4. 检测),],} 出栈，若是 *, 下一个符号时 / 出栈，否则报错
  5. 返回第二步，字符为 EOF 则结束
  6. 关闭文件
检测平衡符号
// check the balance symbol
int CheckSymbol(const char* path)
{
    FILE *fp = fopen(path, "r");
    char ch,ch2;
    Stack S = CreatStack(10);
    while ((ch = fgetc(fp)) != EOF)
    {
        //detect open symbols
        if(ch=='('||ch=='{'||ch=='[')
           Push(S,ch);
        else if(ch=='/')
        {
            ch2 = fgetc(fp);
            if(ch2!=EOF&&ch2=='*')
              Push(S,ch);
        }
        // detect close symbols
        switch(ch)
        {
            case ')': if(IsEmpty(S)||Pop(S)!='(')
                      {
                        printf("No find a pair of ()\n");
                        return 0;
                      }
                      break;
            case '}': if(IsEmpty(S)||Pop(S)!='{')
                      {
                        printf("No find a pair of {}\n");
                        return 0;
                      }
                      break;
            case ']': if(IsEmpty(S)||Pop(S)!='[')
                      {
                        printf("No find a pair of []\n");
                        return 0;
                      }
                      break;
            case '*': ch2 = fgetc(fp);
                      if(ch2=='/')
                      {
                        if(IsEmpty(S)||Pop(S)!='/')
                        {
                            printf("No find a pair of //* *//\n");
                            return 0;
                        }
                      }
                      break;
            default: break;
        }
    }
    if(!IsEmpty(S)) 
    {
        printf("the stack is not empty\n");
        return 0;
    }
    fclose(fp);
    ClearStack(S);
    return 1;
}
# 编写一个程序计算后缀表达式的值
不懂后缀表达式戳此。
大致思路 (数字栈):
  1. 读取字符
  2. 若检测到数字入栈
  3. 若检测到运算符出两次栈，做对应运算，得到的数入栈
  4. 返回第一步，字符为空则结束
  5. 出栈，返回计算值
后缀计算
//Evaluate postfix expressions(only consider 0 ~ 9)
ElementType Suffix(const char * expressions,int length, int Stacksize)
{
    Stack S = CreatStack(Stacksize);
    ElementType num = 0;
    for(int i=0;i<length-1; i++)
    {
        if(expressions[i]>='0'&&expressions[i]<='9')
           Push(S,expressions[i]-'0');
        else if(expressions[i]=='+')
        {
            num = Pop(S);
            num +=Pop(S);
            Push(S,num);
        }
        else if(expressions[i]=='-')
        {
            num = Pop(S);
            num -=Pop(S);
            Push(S,num);
        }
        else if(expressions[i]=='*')
        {
            num = Pop(S);
            num *=Pop(S);
            Push(S,num);
        }
        else if(expressions[i]=='/')
        {
            num = Pop(S);
            num /=Pop(S);
            Push(S,num);
        }
    }
    num = Pop(S);
    return num;
}
# 波兰表达式转换
  • a. 编写一个程序将中缀表达式转换为后缀表达式，该中缀表达式包含 "(",")"+","-","*","/"
  • b. 将幂操作符添加到你的指令系统
  • c. 编写一个程序将后缀表达式转换为中缀表达式
a 和 b 其实属于同一个题。
中缀表达式转换为后缀表达式 (字符栈) 大致思路如下:
  1. 给各个运算符设定优先级，由高到低依次是 "^","*","/","+","-","(",")"
  2. 读取字符
  3. 检测数字字母直接输出
  4. 检测运算符入栈，若栈中原本有运算符且优先级更高，出栈，该运算符入栈，"(" 则直接入栈
  5. 若检测 ")" , 则检测到 "(" 之前得运算符全部出栈
  6. 返回第二步，字符为空则结束
  7. 出完栈中的元素，返回字符串
中缀转后缀 参考链接
// Infix expressions convert postfix expressions
void InfixToPostfix(char* expressions,int length)
{
    char output[length];
    Stack S = CreatStack(STACK_SIZE);
    int j = 0;
    for(int i=0;i<length-1;i++)
    {
        if((expressions[i]>='a'&&expressions[i]<='z')||(expressions[i]>='0'&&expressions[i]<='9')
        ||(expressions[i]>='A'&&expressions[i]<='Z'))//is number or letter output
           output[j++] = expressions[i];
        else//not number or letter
        {
            if(IsEmpty(S)) Push(S,expressions[i]); //the stack is empty push stack
            else if(expressions[i]=='(') Push(S,expressions[i]);// is '(' push stack
            else if(expressions[i]==')') //is ')' pop stack when top is ')' stop
            {
                while(Top(S)!='(')
                {
                    output[j++] = Pop(S);
                }
                Pop(S);
            }
            else 
            {
                while(operatorSort(expressions[i])<=operatorSort(Top(S)))
                {
                    output[j++] = Pop(S);
                    if(IsEmpty(S)) break;//when the stack is empty break the loop
                }
                Push(S,expressions[i]);
            }
        }
    }
    while(!IsEmpty(S)) output[j++] = Pop(S);
    ClearStack(S);
    output[j] = '\0';
    for (int i = 0; i <length; i++)
        expressions[i] = output[i];
}
// Implement operator precedence
unsigned int operatorSort(char op)
{
    unsigned int priority;
    if(op == '^')
       priority = 3;
    else if (op == '*'||op=='/')
       priority = 2;
    else if(op=='+'||op=='-')
       priority = 1;
    else if(op=='(')
       priority = 0;
    return priority;
}
后缀表达式转换为中缀表达式 (字符串栈) 大致思路如下:
  1. 读取字符
  2. 检测数字字母入栈
  3. 检测到运算符，出两次栈与运算符构成表达式入栈
  4. 返回第一步，字符为空则结束
  5. 出栈，反转表达式 (reverse)
  6. 返回表达式 (字符串)
后缀转换为中缀
//  postfix expressions convert Infix expressions
ElementType PostfixToInfix(char* expressions, int length)
{
    Stack S = CreatStack(10);
    for (int i = 0; i < length - 1; i++)
    {
        if ((expressions[i] >= 'a' && expressions[i] <= 'z') || (expressions[i] >= '0' && expressions[i] <= '9')
            || (expressions[i] >= 'A' && expressions[i] <= 'Z'))//is number or letter Push stack
        {
            char* str = malloc(sizeof(char) * 100);
            str[0] = expressions[i], str[1] = '\0';
            Push(S, str);
        }
        else
        {
            char ch[100] = "(";
            char* str = malloc(sizeof(char) * 2);
            str[0] = expressions[i],str[1] = '\0';
            //spilc the expressions
            strcat(ch, Top(S));
            free(Pop(S));
            strcat(ch, str);
            free(str);
            strcat(ch,Top(S));
            strcat(ch, ")");
            strcpy(Top(S), ch);
        }
    }
    char* c = Top(S);
    Pop(S);
    clearStack(S);
    char s[100] = {0};//teh temp string
    reverse(c,s);//reverse the string
    return c;
}
# 如何用一个数组实现两个栈和三个栈
参考链接可以戳此。
一个数组实现两个栈我更喜欢从数组底部和顶部分别延伸得到。
一个数组实现三个栈我倾向于设置三个栈起点分别为 0、1、2, 然后步进 (offest) 为 3 这样设置，答案的两边延伸，中间任意生长的方法我不敢恭维。
一个数组实现两个栈
// 数据结构
#define EmptyTOS -1
#define STACK_SIZE 10
typedef int ElementType;
typedef struct StackRecord* Stack;
struct StackRecord {
    int Capacity;
    int BottomOfStack;
    int TopOfStack;
    ElementType *Array;
};
// 对应函数
// use a array to create two stacks
Stack CreatStack(int MaxStackSize)
{
    Stack S = malloc(sizeof(struct StackRecord)*MaxStackSize);
    S->Array = malloc(sizeof(ElementType)*MaxStackSize);
    S->Capacity = MaxStackSize;
    MakeEmpty(S);
    return S;
}
//Push bottom of stack
ElementType PushBottom(Stack S,ElementType element)
{
    if(IsFull(S))
      printf("two stack is full\n");
    else
      S->Array[++S->BottomOfStack] = element;
    return 0;
      
}
//Push top of stack
ElementType PushTop(Stack S,ElementType element)
{
    if(IsFull(S))
      printf("two stack is full\n");
    else
      S->Array[--S->TopOfStack] = element;
    return 0; 
}
// pop bottom of stack
ElementType PopBottom(Stack S)
{
    if(IsButtomEmpty(S))
       printf("the buttom of stack is empty\n");
    else
       return S->Array[S->BottomOfStack--];
    return 0;
}
// pop top of stack
ElementType PopTop(Stack S)
{
    if(IsTopEmpty(S))
       printf("the top of stack is empty\n");
    else
       return S->Array[S->TopOfStack++];
    return 0; 
}
// check if stack is full
bool IsFull(Stack S)
{
    if(S->BottomOfStack==S->TopOfStack) return true;
    else return false;
}
// check if the top of stack is empty
bool IsTopEmpty(Stack S)
{
    if(S->TopOfStack==S->Capacity) return true;
    else return false;
}
// check if the buttom of stack is empty
bool IsButtomEmpty(Stack S)
{
    if(S->BottomOfStack==EmptyTOS) return true;
    else return false;
}
// clear the top of stack and the bottom of stack
void clearStack(Stack S)
{
    if(S!= NULL)
    {
        free(S->Array);
        free(S);
    }
}
// pop the top element of the top of stack
ElementType TopTop(Stack S)
{
    return S->Array[S->TopOfStack];
}
// pop the top of stack of the buttom of stack 
ElementType BottomTop(Stack S)
{
    return S->Array[S->BottomOfStack];
}
// create a empty stack
void MakeEmpty(Stack S)
{
    S->BottomOfStack = EmptyTOS;//bottom of stack -1
    S->TopOfStack = S->Capacity;//top of stack + 1
}
# 斐波那契数递归例程在 N=50 下运行栈会溢出吗？
证：不会，程序运行是相当快的，它会优先运行完左边的递归再运行右边的递归，而两边的递归最多只有 49 次，所以不会出现栈溢出。
详情可看这篇文章。
# 队列和双端队列
可以看看循环队列和双端队列这两篇文章，都挺不错的。
  • 循环队列:
    1. 队列空:front==rearfront == rear
    2. 队列满:(rear+1)%N==front(rear + 1)\%N==front
    3. 队列元素个数:(rear−front+N)%N(rear - front + N) \%N
  • 双端队列
    1. 队列满:(rear+1)%length==front(rear+1)\%length==front
    2. 队列空:(front+1)%length==rear(front+1)\%length==rear
    3. 插入队首元素:(front−1+length)%length(front-1+length)\%length
    4. 插入队尾元素:(rear+1)%length(rear + 1) \%length
    5. 删除队首元素:(front+1)%length(front + 1) \% length
    6. 删除队尾元素:(rear−1+length)%length(rear-1+length)\%length