数据结构与算法(一)：线性表、栈、队列

数据结构导论

数据结构诞生于1968年，克努特教授《计算机程序设计技巧》中系统阐述了数据逻辑结构的概述和思想，开创了数据结构概念，甚至比C（1972）、C++（1980）等语言出现还早，编程语言只是底层工具，半个世纪过去数据结构和算法的思想经久不衰，值得记录和学习。本文回顾了两年前初识数据结构的笔记、算法记录、代码等，根据参考视频、博客等重新补充、整理，以C语言为编程语言，介绍了各自数据结构和算法。

数据

数据：一个总称，例如生产日期、身高体重 数据元素：是数据处理的基本单位，即数据的记录，例如某月某日、170kg等。

逻辑结构

集合结构：数据元素同属一个集合，一个类，散乱的装载，没有其他关系了。 线性结构：数据元素间是一对一的关系。 树形结构：从根结点出发，一对多、多对一的关系。 图形结构：复杂的网状结构，一对多、多对一、多对多关系。

存储结构

数据元素的存储结构有两种： 顺序存储结构：数据元素存放在地址连续的存储单元中，数据的逻辑关系和物理关系是一致的。
链式存储结构：数据元素被存储在存储单元中，可以连续，也可以不连续的，存在一个指针域指向下一个数据地址。

抽象数据类型（Abstract Date Type）

抽象数据类型是对数据类型进行抽象的概念，是数据结构重要的概念之一。用户无需关心不同或同一的数据类型在不同CPU的计算指令和运算逻辑，甚至可以定义自己的数据类型，标准的抽象数据类型伪代码：

ADT 抽象数据类型名
Data 
    数据元素之间逻辑关系定义
Operation
    操作
endADT

1. 线性表

1.线性表的抽象数据类型定义

ADT List
Data 		
    线性表数据对象集合为{a1，.....an}，每个元素的数据类型是DataType，除了第一个元素，每个元素有且只有一个直接前驱元素，除了最后一个元素，每个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。
Operation
    初始化
    判断是否空表
    清空表
    返回线性表第i个元素
    查找元素e
    插入元素e
    删除元素e
    返回线性表元素个数
endADT  

2. 顺序表：顺序存储结构

#define MAXSIZE 50
typedef int ElemType;
type struct
{
    ElemType data[MAXSIZE];
    int length; //顺序表长度
}SqList;

优点：
1. 逻辑相邻、存储物理位置相邻
2. 对数据元素的存取为随机存储或按地址存储 3. 存储密度高，使用率高。

缺点：
1. 表的插入、删除等运算时间复杂度表现差。
综上：顺序表结构适用于查找多、删除插入少的数据管理。

1. 头文件概述

定义了一个顺序表结构体，包含了顺序存储结构数组、数组末位索引last成员，声明了一系列顺序表操作函数，包含初始化、判断空表、清空表、获取表长、按元素名查找元素、按索引插入元素、打印元素、删除表、按索引删除元素、融合两个表、删除线性顺序表的重复元素。

头文件：

//sqlist.h
#ifndef SQLIST_H
#define SQLIST_H

#include "stdio.h"
typedef int data_t;  //给int起别名data_t
#define MAXSIZE 128

typedef struct sqlist_t{

	data_t data[MAXSIZE]; //数组s
	int last;
}sqlist,*sqlink; //sqlist=struct sqlist_t,sqlink=struct sqlist_t*

sqlink list_create();//初始化
int list_isempty(sqlink L); //判断是否空表
int list_clear(sqlink L); //清空表
int list_length(sqlink L);//计算长度
int list_locate(sqlink L,data_t value);//查找元素
int list_insert(sqlink L,data_t value,int pos);//在pos位置插入元素value
int list_show(sqlink L);//打印所有顺序表元素
int list_delete(sqlink *L);//删除表
int list_deleteElem(sqlink L,int pos);//删除某个元素

//复合功能函数
int merge_list(sqlink L1,sqlink L2);//把两个表去除重复元素后融合并且放在L1
int deleteRept_list(sqlink L);//删除线性表的重复元素

#endif

2. 初始化

malloc开辟空间，使用memset函数进行0字节填充，意味着数组、last都被初始化为0，但是last初始化为0会有歧义，因此应该被置为-1；

#include <string.h> //memset
#include <stdlib.h>//malloc
sqlink list_create(){
 	sqlink L;
	L=(sqlink)malloc(sizeof(sqlist));
	if(L==NULL){
		printf("list mallor error!\n");
		return L;
	}
	//if malloc ok:initialize
	memset(L,0,sizeof(sqlist));//使用常量0填充指针L内存，大小为开辟空间
	L->last=-1;
	return L;
}

3. 按索引插入元素

实现思路： 1. 判读非法情况
2. 从最后开始，往后移位，留出空位；这里的pos和last含义是一样的，取值0到L->last+1;
3. 填入值，更新L->last;

int list_insert(sqlink L,data_t value,int pos)
{	//是否表满
	if(L->last==MAXSIZE-1){
		printf("Insert Fail:FULL\n");
		return -1;
	}
	//插值是否合法
	if(pos<0||pos>L->last+1){
		printf("Pos is invalid!\n");
		return -1;
	}
	//从后往前移值
	for(int i=L->last;i>=pos;i--){
		L->data[i+1]=L->data[i];
	}
	//插入新值
	L->data[pos]=value;
	L->last++;
	return 0;
}

4. 清空表

实际上是半个初始化，无需申请空间而已，直接使用memset填充，last置-1；

int list_clear(sqlink L)
{	if(L==NULL)
		return -1;
	memset(L,0,sizeof(sqlist));
	L->last=-1;
		return 0;
}

5. 判断是否空表

通过last判断即可，-1为空；

int list_isempty(sqlink L)
{	if(L->last==-1)
		return 1;
	else 
		return 0;
}

6. 获取表长

长度=last+1；

int list_length(sqlink L)
{	if(L->last==-1)
		return 0;
	else
		return(L->last+1);
}

7. 按元素名查找元素(第一次出现位置)

遍历判断是否相等即可。

int list_locate(sqlink L,data_t value)
{	if(L==NULL){
		printf("NULL\n");
		return-1;
	}
	if(L->last==-1){
		printf("Empty!\n");
		return -1;
	}
	for(int i=0;i<=L->last;i++){
		if(L->data[i]==value){
			return i;
		}		
	}
	return -1;
}

8. 打印元素

遍历输出

int list_show(sqlink L){
	if(L==NULL){
		printf("NULL Object\n");
		return -1;
	}
	if(L->last==-1){
		printf("Empty!\n");
		return -1;
	}
	for(int i=0;i<=L->last;i++){
		printf("%d\n",L->data[i]);
	}
	return 0;
}

9. 按索引删除元素

思路：
1. 判断非法情况
2. 删除第pos位，也即pos+1位开始的元素往前移动，覆盖填充，更新L-last即可。（尽管是删除末尾的元素，因为last已经--了，last外的元素无需关心填充了什么新值，仍采取这种方法）

int list_deleteElem(sqlink L,int pos){
	if(pos<0||pos>L->last){
		printf("Pos is invalid!\n");
		return -1;
	}
	for(int i=pos+1;i<=L->last;i++){
		L->data[i-1]=L->data[i];
	}
	L->last--;
}

10. 删除表

malloc申请的使用free释放，置NULL防止野指针，是C风格的常规写法。
注意的是，传入参数为一个双重指针，在main函数调用的时候，函数操作的就是根据地址操作实参，能保证最后实参=NULL，而如果不使用双重指针，传入的是sqlink L，那么删除函数置NULL的是形参，也即实参的副本，这样最后的NULL对实参是无效的，我们前面函数所写的检验语句L==NULL全部无效，在链表中和之后的数据结构中也是同理。
此外，C语言除了这种写法，还有一种思路就是传入sqlink L，但是函数返回sqlink L类型，这样就可以通过返回值影响实参，达成置NULL目的。

int list_delete(sqlink *L){
	if(*L==NULL){
		return -1;
	}
	else{
		free(*L);
		*L=NULL; //防止野指针
		return 0;
	}
} 

11. 融合两个表

目的是找出两个表的重合元素，L2只向L1移动L1没有的元素。思路是while遍历L2元素，使用前面的locate函数找出L1是否存在同样的值，如果返回-1（说明不存在），通过插入函数追加到L1末尾（代价最小）。

int merge_list(sqlink L1,sqlink L2)
{	
	int i=0;
	while(i<=L2->last){
		if(list_locate(L1,L2->data[i])==-1){
			//判断插入是否成功
				if(list_insert(L1,L2->data[i],L1->last+1)==-1){
						return -1;
			}
		}
		i++;
	}
	return 0;
}

12. 删除线性顺序表的重复元素

这是比较复杂的情况。思路：
1. 外层循环i=1开始遍历该表，内层循环j=i-1开始递减到0，查找0到i-1是否有等于i位置的元素； 2. 如果有，执行删除元素函数，跳出当此循环，也就是j不用在递减了（尽管有多个重复i的迭代会删除全部的重复），因为如果此时再递减，轻则造成资源浪费，重则删除了第i位的新元素（因为执行删除全部元素都前移了），造成越界、判断出错等问题，同理，i也不用执行自增。 3. 如果没有，j遍历到0递减变成负数跳出循环，i执行自增，开始判断下一位元素直到末尾L->last;

int deleteRept_list(sqlink L){
	if(L->last==-1){
		printf("Empty!\n");
		return -1;
		}
	int i,j;//i负责首先遍历元素，j负责遍历i之前的元素
	i=1;//开始i=1，j=0
	//首层循环，i依次取值
	while(i<=L->last){
		j=i-1;
		//j依次取i前面的元素
		while(j>=0){
			if(L->data[j]==L->data[i]){
				list_deleteElem(L,i);//j和i元素一致删掉
				break;//找到相同，j重新赋值，否则会一直j--，前面如果没有重复会导致计算资源的浪费，有重复则导致删掉了新的i元素，导致越界等不可预料行为
			}
			else{j--;}//找不到一直减，负数结束循环
		}
		if(j<0){
			i++;//j循环完率，没有j和i元素相等，i下一个
		}
	}	
	return 0;
}

3. 链表：链式存储结构

线性表的链式存储结构是使用一组任意未被占用的存储空间存放数据元素和指针（指向表的下一个数据），存放数据的域称为数据域，存放指针的域称为指针域或链，两者组成数据元素存储映像，称为结点（Node）。其中如果每个结点只包含一个指针域，这样的链表称为单链表。链表中除了单链表还有其他链表结构（双链表、循环链表等）。

1. 单链表概述

typedef struct node{
	data_t data;  //数据域
	struct node *next;//指针域
}listnode,*linknode;

1. 指针：头指针是指向头结点的一个地址指针，通过这个指针找到链表所在的位置，所有一般头指针被冠以链表的名字（指针变量名），头指针是链表必要的元素，无论表是否为空，头指针均不为空（表在我在，表亡我亡）。
   

2. 头结点：头结点是链表的第一个结点，一般数据域不存储数据（但也有的用于记录表长），只有指针域指向链表真正的第一个数据。头结点不是必要元素，它的存在是为了统一第一个数据和其他数据插入、删除操作。如果链表为空，头结点的指针域指向NULL。
   

3. 链表的内存策略： 考虑一种写法:

   listnode A;
   linknode p=&A;
   A.data=value;
   ...

   这种初始化方法是把链表放在栈上，当一段代码执行完自动销毁了，这是不太实用的。另一种常见的写法是：

   linknode p;
   p=(linknode)malloc(sizeof(listnode));
   p->data=value;
   p->next=...
   ...

   这种写法的好处是在堆区申请空间，可以动态管理内存，等输入更大的数据时候，再申请多一块内存存储新结点。

4. 特点： 链表适合插入、删除元素多的场合，因为只需要更改指针即可，代价很小。而查找、读取元素代价较大，因为如果要寻找第i个元素，必须从头结点或第一个数据依次往下查找。

2. 头文件概述

头文件中定义了链表的结构体，声明了单链表常用的操作，包括初始化、尾插元素法、数据打印、按位置索引元素、按位置插入元素、按位置删除元素、销毁单链表等，单链表的有趣算法比较多，此处介绍了链表元素倒置、查找相邻元素和最大的第一个结点、有序链表的合并（如1357、2468合成12345678）。

#ifndef LINKLIST_H
#define LINKLIST_H
#include <stdio.h>
#include<stdlib.h>
#include <string.h>

typedef int data_t;
typedef struct node{
	data_t data;
	struct node *next;
}listnode,*linklist;

linklist list_create();
int list_tail_insert(linklist H,data_t value);//尾部插入
int list_show(linklist H);//数据打印
linklist list_getElem(linklist H,int pos);//按序号查找
int list_insert(linklist H,data_t value,int pos);//按序号插入
int list_deleteElem(linklist H,int pos);
int list_deleteList(linklist *H);//双重指针保证释放后为NULL，详见源码linklist *H=struct **node

//单链表常见算法
int invert_list(linklist H);//链表倒置
linklist addmax_list(linklist H);//查找单链表中相邻结点数据之和结果最大的元素指针
int merge_list(linklist H1,linklist H2);//合并两个增序链表，合并后仍然是增序的；
#endif

3. 单链表的初始化

从名字上是初始化一个表，而实际上链表为空时，初始化是一个结点而已，为这个结点申请空间，定义数据和指针就好，我们这里是使用带头结点的单链表，因此初始化一个头结点：

linklist list_create(){
    linklist H;
	//头结点申请空间
    H=(linklist)malloc(sizeof(listnode));
    if(H==NULL){
        printf("Head malloc failed!\n");
		return NULL;
    }
	//初始化数据
    H->data=0;
    H->next=NULL; 
    return H;
}        

4. 单链表尾插法插入元素

尾插法，也即每次都在单链表的尾部插入数据元素，链表每次都需要循环到最后一个元素，使用q从头结点开始循环，q->next==NULL，代表以及到达最后的元素，把新节点P链接到q即可。

int list_tail_insert(linklist H,data_t value)
{	if(H==NULL){
		printf("Head failed!\n");
		return -1;
	}
	//new node,这是尾部需要插入的结点 
	linklist P;
	P=(linklist)malloc(sizeof(listnode));
		if(P==NULL){
		printf("Node malloc failed\n");
		return -1;
	}
	P->next=NULL;
	P->data=value;
	//找到链表尾结点，特征是尾结点指向的地址为空
	linklist q=H; //从头结点开始
	while(q->next!=NULL){
		q=q->next;
	}//完成循环后，q是最后一个节点
	q->next=P;
	return 0;
}

5. 打印单链表所有数据

p从头结点开始遍历输出，直到p->next==NULL,即遍历到最后的元素。

int list_show(linklist H)
{	if(H==NULL){
		printf("show Head NULL!\n");
		return -1;
	}
	linklist p=H;
	while(p->next!=NULL){
		printf("%d\t",p->next->data);
		p=p->next;
	}
	puts("");//空行美观
	return 0;
}

6. 按位置索引结点

用索引次数代替p->next!=NULL条件，如果提前遇到尾结点，则返回查找失败。

linklist list_getElem(linklist H,int pos)
{	if(H==NULL){
	printf("Get Head NULL");
	return NULL;
	}
	//-1的时候返回头结点
	if(pos==-1){
		return H;
	}
	if(pos<-1){  //小于-1认为是不合法值
		printf("invalid pos!\n");
		return NULL;
	}
	linklist p=H;
	int i=0;
	while(i<pos+1){
		i++;
		p=p->next;
		if(p->next==NULL){  //如果pos太大，提前遇到尾结点，那就退出
			printf("pos is invalid!\n");
			return NULL;//这里返回了空，如果还去读p->data会导致段错误，可以在测试函数、主函数判断是否空。
		}
	}
	return p;
}

7. 按序号位置插入

链表插入的操作是很简便的，时间复杂度为o(1),假设我们要在pos位置插入元素，首先利用6的按位置索引找到pos前的结点q，把q->next交给新结点p->next，把q->next重定向为需要插入的结点p。

int list_insert(linklist H,data_t value,int pos){
	if(H==NULL){
		printf("Insert Head NULL\n");
		return -1;
	}
	//新结点
	linklist p=(linklist)malloc(sizeof(listnode));
	if(p==NULL){
		printf("malloc failed!\n");
		return -1;
	}
	p->data=value;

	linklist q=list_getElem(H,pos-1);//pos-1，在第三个插，在第二个就要处理它的next
	if(q==NULL){         //排除段错误，也即索引导致查找不成功
		printf("pos is invalid\n");
		return -1;
	}
	p->next=q->next;
	q->next=p;
	return 0;
}

8. 按序号删除元素

首先需要查找pos前的一个结点记为q，当pos结点为NULL（找不到结点）或者已经是最后一个结点，删除操作不合法；若合法，使用辅助指针q指向pos以及后面的结点，把q->next交给p->next,释放q结点的空间。因为链表的空间是动态分配的，插入一个，申请一块，删除时需要free。

//按序号删除
int list_deleteElem(linklist H,int pos){
	if(H==NULL){
		printf("delete Head NULL\n");
		return -1;
	}
	linklist p=list_getElem(H,pos-1);//查找pos前的一个元素
	if(p==NULL||p->next==NULL){//p==NULL说明没有找到合适序号的，p->next==NULL说明找到的是最后一个
		printf("pos is invalid!\n");
		return -1;
	}
	//p是pos的前一个结点
	linklist q=p->next;//q存储pos结点和之后的结点
	p->next=q->next; //把pos结点之后的交给p->next
	free(q); //q之后的结点已经备份，释放q即可
	q=NULL; //避免野指针
	return 0;
}

9. 单链表的销毁

单链表的销毁实际上就是释放每个结点空间，那么就涉及到顺序问题。对于单链表而言，如果涉及到批量操作，必然是从头结点处入手会更加方便，因为头指针是找到一个单链表的唯一方式，在找到这个头指针前，都无法获知这个链表的长度，因此销毁思路是从头结点开始，使用temp保存头结点，p指针往后走，销毁temp，temp保存p指针，p往后走，销毁temp......直到p==NULL。

int list_deleteList(linklist* H){ //传入的是linklist对象的地址值，通过地址访问对象，而不是形参
	if(*H==NULL){ //解引用，通过linklist地址访问，这里*H地位等于前文的H，只是前文是形参，这里是解引用访问
		printf("deletelist Head NULL");
		return -1;
	}
	linklist p=*H; //这里的p代替*H,为了代码的可读性和美观
	while(p!=NULL){
		linklist temp=p;
		printf("%d\n",p->data);
		p=p->next;
		free(temp);
	}
	*H=NULL;//这是传入地址的目的，通过地址才可以真正把linklist对象置为NULL
			//如果是H=NULL，只能把形参置为NULL，没有影响实参地址的值。
	return 0;
}

10. 单链表元素的倒置

这是一个有关迭代的复杂算法，目的是在不新建一个新链表的前提下，把链表中的所有元素按颠倒的顺序组成一个新链表。这个操作涉及三个指针：头指针H、遍历指针p，头插元素指针q。 1. 一刀两断：拆解两部分：一部分来自头结点+第一个数据结点，另一部分是第二歌数据结点以及后续结点。因为第一个结点最后是变成最后的结点的。因此第一步用p保存第二个结点及以后的结点（p=H->next->next），把第一个数据节点的next置空(H->next->next=NULL)。
2. 头插法插入元素：把第二部分的元素逐个按头插法插入第一部分，对第二部分而言，需要两个指针p、q，一个做插入、一个做保存后续指针，直到保存指针p==NULL。

int invert_list(linklist H){
	if(H==NULL){ //链表不存在
		printf("invert Head NULL!\n");
		return -1;
	}
	if(H->next==NULL||H->next->next==NULL){ //链表为空或者有且只有一个数据元素
		printf("H needen't invert!\n'");
	}
	//第一个元素和第二个元素分离，因为第一个元素的next要变为NULL，用p指向第二位元素
	linklist p=H->next->next;
	H->next->next=NULL;
	linklist q;//辅助指针
	while(p!=NULL){
		q=p ;//q承担指引要头插的结点
		p=p->next;//p来保留结点后面的元素
		q->next=H->next;//头插法，q的next指向现在H的next
		H->next=q;//H的next指向q
	}
	return 0;
}

11. 查找使相邻两个数据之和最大的第一个结点

这和寻找序列中最大值的思路是一致的:假设最大值为第一个数据加第二个数据，记为max，p、q移动，计算第二个+第三个，如果相加结果reg大于max，替换max，并更新指向最大值第一个数据的max_pointer指针，直到q==NULL，遍历完成，返回max_pointer指针。

linklist addmax_list(linklist H){
	if(H==NULL){ //链表不存在
		printf("Add Head NULL!\n");
		return NULL;
	}
	if(H->next==NULL||H->next->next==NULL){ //链表为空或者有且只有一个数据元素
		printf("H needen't calculate!\n'");
		return NULL;
	}
	linklist p=H->next;
	linklist q=p->next;
	linklist max_pointer=p;
	int max=p->data+q->data;
	while(q!=NULL){
		int reg=p->data+q->data;
		if(reg>max){
				max=reg;
				max_pointer=p;
		}
		p=q;
		q=q->next;
	}
	printf("Max_addresult=%d\n",max);
	return max_pointer;
}

12. 两个增序单链表合成新增序的单链表

目的是把两个增序的单链表，合成到第一个单链表中。思路和链表的倒置差不多，只不过需要插值的单链表变成了两个，比较后逐个使用尾插法插入元素。步骤概括： 1. 一刀两断：p、q分别保存两个链表的数据元素，r保存H1的头结点，断开两个链表头结点和数据元素的链接。得到三部分：单链表头结点r、表一数据元素p，表二数据元素q；
2. 比较并尾插：当p、q都不是空链表情况下，比较p、q指向的数据，尾插、更新p或q，r始终指向链表的最后一位数据。
3. p或者q为空，即一个链表已经插完了，直接把另一个链表剩下数据（本身就是有序的）插入即可。

int merge_list(linklist H1,linklist H2){
	if(H1==NULL||H2==NULL){ //链表不存在
		printf("Head1 or Head2 NULL!\n");
		return -1;
	}
	if(H1->next==NULL&&H2->next==NULL){ //两个链表均为空
		printf("All Empty\n'");
		return -1;
	}
	linklist p=H1->next;
	linklist q=H2->next;
	linklist r=H1;
	H1->next=NULL;
	H2->next=NULL;
	while(p&&q){
		if(p->data<=q->data){//尾插
			r->next=p; //把p链接到r
			p=p->next;//p继续后移下一位比较
			r=r->next; //更新r指针，指向尾部的元素
			r->next=NULL; //最后的元素next都要为空
		}
		else{ //q小插q，原理同上
			r->next=q;
			q=q->next;
			r=r->next;
			r->next=NULL;
		}
	}
	if(p==NULL){ //p首先排序完了
		r->next=q; //q本身就是增序的，直接全部插入
	}
	else{  //q先为NULL，插入p
		r->next=p;
	}
	return 0;
} 

拓展：C++版本部分操作

#include <iostream>
using namespace std;
typedef struct node
{   int val;
    struct node* next;
    node():val(0),next(nullptr){}
    node(int x):val(x),next(nullptr){}
    node(int x,struct node* next):val(x),next(next){}
}ListNode;

class Linkedlist{
private:
    ListNode* head;
public:
    //无头结点的写法是    Linkedlist(nullptr){} 这里head=nullptr
    //习惯使用带头结点
    Linkedlist(){
        head=new ListNode(0,nullptr);
    }
    ~Linkedlist(){
        ListNode* temp=head;
        ListNode* temp1;
        while(temp!=nullptr){
            temp1=temp;
            temp=temp->next;
            delete temp1;
        }
        head=nullptr;
    }
    int Linkedlist_insert(int val){ //尾插元素
        ListNode *temp=head;
        if(temp!=nullptr){
            ListNode *new_node=new ListNode(val,nullptr);
            while(temp->next!=nullptr){
                temp=temp->next;
            }
            temp->next=new_node;
            return 0;
        }
        return -1;
    }
    void printInfo()const{
        ListNode *temp=head;
        if(temp!=nullptr){
            while(temp!=nullptr){
                cout<<temp->val<<'\t';
                temp=temp->next;
            }
            cout<<endl;
        }
    }
    int Linkedlist_deleteval(int val){ //删除元素==val的全部值,但是没有检索头结点的值
        if(head==nullptr){
            return -1;
        }
        if(head->next==nullptr){
            if(head->val==val){
                delete head;
                head=nullptr;
            }
            return 0;
        }
        ListNode *slow=head;
        ListNode *fast=slow->next;
        while(fast!=nullptr)
        {   
            if(fast->val==val){
                slow->next=fast->next;
                delete fast;
                fast=slow->next;    
            }
            else{
                slow=slow->next;
                fast=fast->next;
            }

        }
        return 0;
    }
};

int main(){
    Linkedlist L1;
    L1.Linkedlist_insert(1);
    L1.Linkedlist_insert(2);
    L1.Linkedlist_insert(3);
    L1.Linkedlist_insert(1);
    L1.Linkedlist_insert(2);
    L1.Linkedlist_insert(3);
    L1.Linkedlist_insert(1);
    L1.Linkedlist_insert(2);
    L1.Linkedlist_insert(3);
    L1.Linkedlist_insert(6);
    L1.printInfo();
    L1.Linkedlist_deleteval(0);
    L1.printInfo();
    return 0;
}

4.静态链表

对目前的高级程序语言设计语言，基本上都具备了指针的功能，因此单链表这种动态分配内存策略容易实现。而数据结构出现的时间早于C语言，在古早的程序设计中并没有指针来完成元素链接的任务，因此有这样的一种链表是基于数组模拟实现的，称为静态链表。静态链表灵活性不如单链表，一般只在特殊的场合有使用（如不想动态管理内存实现链表、避免内存碎片化、数据结构大小需要不变等），但是其思想仍有重要参考价值。
结构定义如下：

#define MAXSIZE 128
typedef int data_t;
typedef struct node{
	data_t data; //数据
	int cursor; //游标
}stclist,stclink[MAXSIZE]

静态链表使用游标来代替指针功能，其规则如下： 1. 数组第一位（下标为0）相当于头结点，不存放数据，游标指向第一个不存放数据的下标。
2. 数组最后一位（下标最大的），指向真实数据的第一位下标。
3. 其余游标大小按照链表顺序决定，而不是下标。

值得注意的是，尽管链表使用了数组来描述，但是其下标只是相对于内存分配而言的，静态链表不具备随机存储特性，也即不能通过下标访问数据，这和单链表特性是一致的。

2. 栈

栈（stack）是一种特殊的线性表，是一种后进先出(LIFO)的结构，只在表尾进行插入和删除操作，这个表尾称为栈的栈顶（top），而相应的表头称为栈底（bottom）。栈的存储结构也分为顺序结构和链式结构，一般以顺序结构较为常用。

顺序栈

在之前顺序表的情况下，如果把所有操作都转移到表尾(数组下标大的一端)进行，那么就是一个简单的栈结构。为了降低代码重复造轮子的感觉，这次的顺序栈将采取另一种结构定义如下：

typedef int data_t;
typedef struct{
	data_t *data;//数据数组指针
	int maxlen;//数组最大空间
	int top;//栈顶下标
}sqstack;

这里用data_t *data来代替data_t data[MAXSIZE]的，实际上两者是一致的，只是这次我们把内存大小控制交给了用户，而不是宏。top和之前顺序表的last的含义是一致的，指向栈顶元素（顺序表的最后一个数据元素）下标，maxlen是用户初始化时需要指定的数组大小。

1. 头文件概述

关于结构体在上文已经解释，不再赘述，栈的基础操作比顺序表还要简单，包括初始化、压栈、出栈、打印栈顶元素、判断满栈、空栈、清空栈、销毁栈等。

#ifndef SQSTACK_H
#define SQSTACK_H

typedef int data_t;
typedef struct{
	data_t *data;//数据数组指针
	int maxlen;//数组最大空间
	int top;//栈顶下标
}sqstack;

sqstack* stack_create(int length);
int stack_push(sqstack* s,data_t value);
data_t stack_pop(sqstack* s);
int stack_showtop(sqstack* s);
int stack_isfull(sqstack *s);
int stack_isempty(sqstack *s);
int stack_clear(sqstack* s);
int stack_delete(sqstack** s);
#endif 

2. 顺序栈的初始化

顺序栈申请空间，其次由于我们没有使用data[MAXSIZE]的形式，因此data指针需要手动申请空间，大小是数组长度+数组类型占用的数据。使用memset填充数组数据，栈顶指向-1表示空。传入length是用户定义的数组长度。

sqstack* stack_create(int length){
	sqstack* s=(sqstack*)malloc(sizeof(sqstack));
	if(s==NULL){
		printf("stack malloc failed!\n");
		return NULL;
	}
	s->data=(data_t*)malloc(length*sizeof(data_t));//malloc单位是字节，不能直接填length
	if(s->data==NULL){
		printf("data_array malloc failed!\n");
		free(s); //data分配失败，s也不要了 
		s=NULL;
		return NULL;
	}
	memset(s->data,0,length*sizeof(data_t));
	s->maxlen=length;
	s->top=-1;
	return s;
}

3. 顺序栈的压栈

满栈不填，合法则把栈下标后移一位，数据填入s->data[s->top]。

int stack_push(sqstack* s,data_t value){
	if(s==NULL){  //栈对象不存在
		printf("Push Stack NULL!\n");
		return -1;
	}
	if(s->top==s->maxlen-1){ //满栈
		printf("Full Stack!\n");
		return -1;
	}
	s->top++; //栈顶下标后移
	s->data[s->top]=value;//元素入栈
	return 0;
}

4. 顺序栈的出栈

数组的出栈是比较任性的，无论你后面填充了什么，只要栈顶指针搜索不到，就认为数据元素不存在，所以只移动栈的下标即可。

data_t stack_pop(sqstack* s){
	if(s==NULL){
		printf("Pop Stack NULL!\n");
		return -1;
	}
	if(s->top==-1){
		printf("Empty Stack!\n");
		return -1;
	}
	printf("Pop:%d",s->data[s->top]);
	s->top--;   //直接降低top即可
	return s->data[s->top+1];//虽然top不指向了，但内存还在，允许返回
}

5. 打印顺序栈栈顶元素

栈顶元素是s->data[s->top]，打印即可。

int stack_showtop(sqstack* s){
	if(s==NULL){
		printf("Show Stack NULL!\n");
		return -1;
	}
	if(s->top==-1){
		printf("Empty Stack!\n");
		return -1;
	}
	printf("Top Elem=%d\n",s->data[s->top]);
	return 0;
}

6. 判断顺序栈释放满栈

满栈标记：栈顶下标==数组最大长度-1

int stack_isfull(sqstack *s){
	if(s==NULL){
		printf("Isfull Stack NULL!\n");
		return -1;
	}
	return s->top==s->maxlen-1?1:0;

7. 判断顺序栈是否空栈

空栈标记：栈顶下标s->top==-1;

int stack_isempty(sqstack *s){
	if(s==NULL){
		printf("Isfull Stack NULL!\n");
		return -1;
	}
	return s->top==-1?1:0;
}

8. 清空顺序栈元素

逻辑清空就是清空：s->top==-1

int stack_clear(sqstack* s){
	if(s==NULL){
		printf("Clear Stack NULL!\n");
		return -1;
	}
	s->top=-1;   //逻辑清空就是清空
	return 0;
}

9. 顺序栈的销毁

注意销毁要干净，定义了指针数据data，就要手动free掉，在销毁栈空间。双重指针不再赘述。

int stack_delete(sqstack** s){
	if(*s==NULL){
		printf("Delete Stack NULL!\n");
		return -1;
	}
	if((*s)->data!=NULL){
		free((*s)->data);
		(*s)->data=NULL;
	}
	free(*s);
	*s=NULL;
	return 0;
}

链表栈

链表栈的结构和单链表如出一辙，甚至是简化了操作。结构：

typedef struct node{
	data_t data; //数据元素
	struct node *next; //指向下一个结点
}linkstack;

单链表的操作一般分为头插和尾插两部分，而由于链表头指针在头部，因此插入和删除元素都比较方便，约定链表的头部为栈顶，尾部为栈底，插入、删除等操作均在栈顶进行。

1. 头文件概述

结构体定义和链表保持一致，基本操作包括初始化、压栈、出栈、打印栈顶元素、判断栈为空、销毁栈等。因为链式结构不存在栈溢出问题，因此比顺序栈缺少了判断栈满操作。

#ifndef LINKSTACK_H
#define LINKSTACK_H
typedef int data_t;

typedef struct node{
	data_t data; //数据元素
	struct node *next; //指向下一个结点
}linkstack;

linkstack *stack_create();//链式栈的初始化
int stack_push(linkstack *s,data_t value);//压栈
data_t stack_pop(linkstack *s);//弹栈
data_t stack_showtop(linkstack *s);//返回栈顶元素数据
int stack_isempty(linkstack *s);//判断栈为空
int stack_delete(linkstack **s);//销毁整个栈空间

#endif

2. 链式栈的初始化

和链表的初始化思路一致。初始化的是一个头结点。

linkstack* stack_create(){
	linkstack *s=(linkstack*)malloc(sizeof(linkstack));
	if(s==NULL){
		printf("Stack malloc failed!\n");
		return NULL;
	}
	s->data=0;
	s->next=NULL;
	return s;
}

3. 链式栈压栈

使用头插法： 1. 为新结点开辟空间，填充数据，s->next交给新结点的next；
2. s->next指向新节点。

int stack_push(linkstack *s,data_t value){
	if(s==NULL){
		printf("Push Stack NULL\n");
		return -1;
	}
	linkstack *new_node=(linkstack*)malloc(sizeof(linkstack));
	if(new_node==NULL){
		printf("New Node malloc failed\n");
		return -1;
	}
	new_node->data=value;
	new_node->next=s->next;
	s->next=new_node;
	return 0;
}

4. 链式栈出栈

头插法对应头删法，p用于保留第一个数据元素，把第二个数据接到头结点，p就孤立了，free掉即可。其次因为要返回出栈元素数据，因此使用了temp保存其值的副本。

data_t stack_pop(linkstack *s){
	if(s==NULL){
		printf("Pop Stack NULL\n");
		return -1;
	}
	if(s->next==NULL){
		printf("Pop Empty Stack!\n");
		return -1;
	}
	linkstack *p=s->next; //p指向第一个数据
	s->next=p->next;  //把第二个元素接到头结点
	int temp=p->data; //保存第一个数据元素
	free(p); //释放第一个数据空间
	p=NULL; //避免野指针
	return temp; //值传递释放p不影响返回值
}

5. 打印链式栈栈顶元素

栈顶就是链表头，也即第一个结点的数据元素（s->next->data）。

data_t stack_showtop(linkstack *s){
	if(s==NULL){
		printf("Show Stack NULL\n");
		return -1;
	}
	if(s->next==NULL){
		printf("Show Empty Stack!\n");
		return -1;
	}
	return s->next->data;
}

6. 判断链式栈是否空栈

空栈标记：s->next==NULL，头结点指向空。

int stack_isempty(linkstack *s){
	if(s==NULL){
		printf("IsEmpty Stack NULL\n");
		return -1;
	}
	return s->next==NULL?1:0;
}

7. 链式栈的销毁

从头结点开始依次序释放各个结点空间。

int stack_delete(linkstack **s){
	if(*s==NULL){
		printf("Delete Stack NULL\n");
		return -1;
	}
	linkstack *p=*s;
	linkstack *temp;
	while(p!=NULL){
		temp=p;
		p=p->next;
		free(temp);
	}
	*s=NULL;
	return 0;
}

3. 队列

队列(queue)是一个两端操作结构，只允许在一段删除，另一端进行插入，是一种先进先出(FIFO)的线性结构。队列同样具有顺序、链表两种结构，与栈相反，链式队列较为常用

顺序队列

1. 结构

typedef int data_t;
#define MAXSIZE 64
typedef struct{
	data_t data[MAXSIZE];
	int front; //队头下标
	int rear; //队尾下标
}sequeue；

为了描述队列的操作，引入两个下标，分别指向队头和队尾，约定：
1. 初始化时，队列为空，队头和队尾都指向0下标；
2. 当一个元素入队，队头指向第一个元素位置（如下标0），队尾指向第一个没有元素的位置（下标1）；随着更多元素入队，队头保持不变，队尾持续递增。
3. 当元素出栈，队尾保持不变，队头不断递增；全部元素出栈时，队尾和队头下标重新重合，队列为空。

2. 循环队列

那么这就会出现一个问题，每次入队、出队后，再次为空的时候，尽管队头队尾重合，队标已经不再是0了，前面会有大片空间没有被使用，因此，顺序队列常常引入循环结构，来进行存放，当队尾超出数组范围后，会循环到第一个内存空间（若空闲）进行存放，这就是常用的循环队列。值得注意的是，循环队列的队尾（即rear）一般不存放数据，因为如果存放了数据，刚好所有数据存满时，rear下标循环到队头，即（rear=front），此时就很难判断队列是满还是空。以下讨论的操作都是基于循环队列实现的。

3. 头文件概述

定义了顺序队列的结构体，它的特别之处是多出了一个front来指示队头数据的下标，因为队列表尾、表头都要进行操作。基本操作和顺序表的基本操作一致。

#ifndef SEQUEUE_H
#define SEQUEUE_H
#define MAXSIZE 5
typedef int data_t;

typedef struct{
	data_t data[MAXSIZE];
	int front;
	int rear;
}sequeue;

sequeue *queue_create(); //初始化循环顺序队列
int queue_isempty(sequeue *q); //判断顺序队列是否空
int queue_isfull(sequeue *q); //判断顺序队列是否满
int En_Queue(sequeue *q,data_t data); //顺序序列的入队
data_t De_Queue(sequeue *q); //顺序队列的出队
int queue_clear(sequeue *q); //清空整个顺序队列元素
int queue_delete(sequeue **q); //销毁整个顺序队列

#endif

4. 顺序队列的初始化

申请空间、使用memset进行0数据的填充。

sequeue *queue_create(){
	sequeue *q=(sequeue *)malloc(sizeof(sequeue));
	if(q==NULL){
		printf("Queue malloc failed!\n");
		return NULL;
	}
	memset(q,0,sizeof(sequeue));
	return q;
}

5. 顺序队列的入队

入队操作是在表尾进行的，涉及rear下标：rear数据本身就是指向最后一位数据的后一位，因此直接填入、更新rear指针即可，无需后移。循环更新序号通过取余运算来实现，例如定义一个数组大小为5，0是第一位，4是最后一位，那么下标5也应该和下标0重合：而5%5恰好就是0，这个不难理解。

int En_Queue(sequeue *q,data_t value){
	if(q==NULL){
		printf("Push Queue NULL\n");
		return -1;
	}
	if((q->rear+1)%MAXSIZE==q->front){ //模拟填入后会不会与front重合
		printf("Full Queue!\n");
		return -1;
	}
	q->data[q->rear]=value; //向rear位置填入数据
	q->rear=(q->rear+1)%MAXSIZE;//更新rear下标
	return 0;
}

6. 顺序队列的出队

出队是在队头，涉及的是front下标，根据数组的思想，直接更新front下标即可，这里使用temp仅是为了返回当前要出队的数据。

data_t De_Queue(sequeue *q){
	if(q==NULL){
		printf("Pop Queue NULL\n");
		return -1;
	}
	if(q->front==q->rear){
		printf("Pop Queue Empty!\n");
		return -1;
	}
	data_t temp=q->data[q->front]; //保存出队数据
	q->front=(q->front+1)%MAXSIZE; //更新front下标
	return temp;
}

7. 判断顺序队列是否为空

队列为空标志：front和rear下标重合

int queue_isempty(sequeue *q){
	if(q==NULL){
		printf("IsEmpty Queue NULL\n");
		return -1;
	}
	return q->front==q->rear?1:0;	
}

8. 判读顺序队列是否为满

满队列标志：模拟入队，rear+1刚好会与front重合（此时确实可以填入数据，但是在前文阐述了不能填入的原因，满队的重合情况就不会出现）

int queue_isfull(sequeue *q){
	if(q==NULL){
		printf("IsFull Queue NULL\n");
		return -1;
	}
	return (q->rear+1)%MAXSIZE==q->front?1:0;
}

9. 顺序队列的情况

清空队列，根据数组思想，直接置为空标志即可，也即rear==front。

int queue_clear(sequeue *q){
	if(q==NULL){
		printf("Clear Queue NULL\n");
		return -1;
	}
	q->rear=q->front;
	return 0;
}

10. 顺序队列的销毁

我们仅为整个队列申请了空间，使用双重指针或者返回值（未给出）方法进行队列的销毁即可。

int queue_delete(sequeue **q){
	if(*q==NULL){
		printf("Delete Queue NULL\n");
		return -1;
	}
	free(*q);
	*q=NULL;
	return 0;
}

链式队列

栈是一个简单化的单链表，因为它只可以在一端进行插入删除操作。而队列则不然，规定两端都要进行操作。而对队尾操作时，要反复使用头指针遍历队尾，这是麻烦的。因此在链式队列中，除了头指针外，还引入了一个尾指针。头指针指向头结点（或第一个结点），尾指针指向最后的一个结点。当队列为空时，头尾指针都同时指向头结点（或第一个数据结点）。 链式队列的结构体是特殊的，在单链表的基础上，添加了头尾两个指针，front的作用和单链表的head一致，作为头指针指向头结点（或者第一个数据元素），rear指向最后一个数据，我们使用两个结构体来定义这样的一种结构：

typedef struct node{ //单链表结点
	data_t data;
	struct node *next;
}listnode,*linklist;

typedef struct {  //头指针、尾指针	
	linklist front; //指向头结点
	linklist rear; //指向最后一个数据结点
}linkqueue;

1. 头文件概述

定义了链式队列的结构体定义，包含了链式表的六个基础操作：初始化、入队、出队、判断队列是否为空、清空队列、销毁队列等。

#ifndef LINKQUEUE_H
#define LINKQUEUE_H
typedef int data_t;

typedef struct node{
	data_t data;
	struct node *next;
}listnode,*linklist;

typedef struct {
	linklist front;
	linklist rear;
}linkqueue;

linkqueue *queue_create();
int queue_isempty(linkqueue *q);
int En_Queue(linkqueue *q,data_t value);
data_t De_Queue(linkqueue *q);
int queue_clear(linkqueue *q);
int queue_delete(linkqueue **q);

#endif

2. 链式队列的初始化

链式队列的初始化分为两部分，首先初始化一个链式队列q，链式队列有两个单链表结构类型的指针front和rear；front和rear需要被指向一个对象，此处创建的是带有头结点的链表，因此front=rear=新开辟的头结点，把头结点元素置0，next置空。

linkqueue *queue_create(){
	linkqueue *q=(linkqueue *)malloc(sizeof(linkqueue));
	if(q==NULL){
		printf("Queue malloc falied\n");
		return NULL;
	}
	q->rear=q->front=(linklist)malloc(sizeof(listnode)); //rear和front指向的是同一块空间，因此下面初始化只初始化front或rear即可
	if(q->rear==NULL||q->front==NULL){
		printf("Linklist malloc falied\n");
		return NULL;
	}

	q->front->data=0;
	q->front->next=NULL;
	return q;
}

3. 链式队列的入队

链式队列从尾部插入元素，涉及的是rear指针。首先为新节点开辟空间，同单链表的做法一致，把rear指针的next指向新结点，并且更新rear指针指向即可。

int En_Queue(linkqueue *q,data_t value){
	if(q==NULL||q->front==NULL||q->rear==NULL){
		printf("Push NULL\n");
		return -1;
	}
	linklist new_node=(linklist)malloc(sizeof(listnode));
	if(new_node==NULL){
		printf("New Node malloc failed!\n");
		return -1;
	}
	new_node->next=NULL;
	new_node->data=value;
	q->rear->next=new_node;
	q->rear=new_node;
	return 0;
}

4. 链式队列的出队

链式队列从队头删除元素，涉及的是front指针。考虑一个特殊情况：要从头结点后第一个数据开始删除数据，rear不动，用temp保存要释放的指针，front相继后移，当整个链表头结点后剩下一个数据结点时，我们不但要把front指针需要前移回头结点，因为后面没有元素了，rear指针也需要前移，因为该空间即将被释放。因此这种思路下必须要判断是否遍历到最后的结点。 另一种思路，巧用头结点。我们从一开始就释放头结点，第一个数据就成为了新的头结点，以此类推。问题就来了，我需要出队的是第一个数据元素，头结点出队且释放有什么用呢？但仔细想一想这两种写法是等价的，头结点出队后，释放后，队列成员减少了，返回值可以返回当前新头结点的值（也就是原来第一个的数据元素）。等链表循环到最后一个元素时，最后的数据元素就成了头结点，front和rear都无需前移，唯一的不同是头结点中存储了最后一位元素的值，但事实上头结点值是0还是其他元素都无关紧要。

具体操作和头删法如出一辙，temp保存当前头指针（q->front），把第一个数据元素链接到front，释放temp，此时返回第一个元素值：q->front->data（q->front是头指针，第一个元素此时已经成为头指针了）。

data_t De_Queue(linkqueue *q){
	if(q==NULL||q->front==NULL||q->rear==NULL){
		printf("Pop NULL\n");
		return -1;
	}
	if(q->front->next==q->rear->next){
		printf("Empty Queue\n!");
		return -1;
	}
	linklist temp=q->front;
	q->front=temp->next;
	free(temp);
	temp=NULL;
	return q->front->data;
}

5. 判断队列是否为空

空队列标志：rear和front都重合

int queue_isempty(linkqueue *q){
	if(q==NULL||q->front==NULL||q->rear==NULL){
		printf("Isempty NULL\n");
		return -1;
	}
	return q->front->next==q->rear->next?1:0;
}

6. 链式队列的清空

同出队的思路是一致的，头结点开始执行头删法，删除除头结点以外的所有结点。当头指针（p->front）的next还有元素时，把p给temp（因为从头结点开始删），p后移，释放temp，把新p给temp，释放temp，以此类推。注意删除完成后头结点不再是刚开始的头结点，而是队列的最后一个结点充当的。

int queue_clear(linkqueue *q){
    if(q==NULL||q->front==NULL||q->rear==NULL){
        printf("Clear NULL\n");
        return -1;
    }
    if(q->front==q->rear){
        printf("Empty Queue\n!");
        return -1;
    }
    linklist p;
    printf("clear:");
    p=q->front; //p是第一个数据元素
    linklist temp;
    while(p->next!=NULL){   //头结点后面还有元素的时候
        temp=p; //从头结点开始删除
        p=p->next;
        printf("%d\t",p->data); 
        free(temp);
    }
    q->front->next=NULL; //头结点指向NULL（注意不是头指针指向NULL）
    q->rear=q->front; //rear也指向头结点
    return 0;
}                                                                  

7. 链式队列的销毁

首先要销毁创建的所有结点，链表是动态的内存管理，因此执行前面的清除操作，就释放了除头结点以外的结点，最后释放头结点、释放q即可。

int queue_delete(linkqueue **q){
    if(*q==NULL||(*q)->front==NULL||(*q)->rear==NULL){
    printf("Delete NULL\n");                
    return -1;
    }
    queue_clear(*q);  //释放头结点以外的空间
    if((*q)->front!=NULL){
        free((*q)->front); //释放头结点的空间,front和rear都是同一块空间，就不用free rear了
    }
    (*q)->front=NULL; 
    (*q)->rear=NULL;  //两个指针孤立了，都置空
    free(*q);  //释放队列空间
    *q=NULL;
    return 0;
}

4. 栈和队列的应用：球钟问题

栈和队列原理虽然简单，但是却是很多代码实战使用的场景都需要的，如网页逻辑、聊天框逻辑等等，这也是它们在线性表众多的逻辑结构中脱颖而出的重要原因。其结合能解决的有趣的数学、物理题目有很多，这里通过球钟问题，进一步介绍栈和队列的妙用。

背景概述：通过小球来计算时间，按12h制计时。现在有代表小时、五分钟、一分钟计时杯子，每个杯子里面球的数目代表当前的时间的积累。有四个球的一分钟杯子加入多1个球，可以兑换五分钟杯子一个球，一分钟杯子清空；当有11个球的五分钟杯子加入一个球，五分钟杯子清空，兑换小时杯子一个球。例如11点五十九分，可以在小时杯子放入11个球，在五分钟杯子放入11个球，在一分钟杯子放入4个球，当1分钟杯子再放入一个球，时间重回0.00，所有杯子将清空重新计时。

问题概述：假设刚开始时小球都是有序的，0-26号共27个球形成一个队列，开始放入分钟杯子，随着时间去进位。进位时会发生球位置错乱，例如放入四个球，第五分钟的时候加入分钟杯的四个球会拿出杯子（出栈，和放入的顺序相反）放到队列的末尾，而队列的球（也即一开始队列的第五个球）会进入五分钟计时器，依次类推。问：经过多少分钟，球的顺序会恢复成一开始的样子？

答案：33120分钟。

我的解决方案：首先要先建立一个模型，从循环上看，模型是每12个小时重复的，因此要先考虑如何把这种规则转换为一个代码函数。当然如果不熟悉可以使用枚举法尝试开始，再写入循环，最后发现这其实是一个三级循环问题，每五分钟可以兑换上层循环五分钟一个，每12个五分钟可以兑换上层循环小时一个。换个角度就是小时循环进入12次五分钟循环，五分钟循环内进入分钟循环12次，分钟作为最内层循环，自循环五次。一开始容易被小球的个数迷惑了，小球数是11、11、4，以为分别对应循环11、11、4次，当然打印理论分钟数后就很容易把这个困惑解决掉，因为一次的执行时间必然是12*60=720分钟。

void circulate(sqstack *hour,sqstack *fmin,sqstack *min,linkqueue *q){
    //这是每12个小时执行的结果
    for(int i=0;i<12;i++){  //小时
        for(int j=0;j<12;j++){   //5分钟
            for(int k=0;k<5;k++){  //每分钟                             
                stack_push(min,De_Queue(q)); //分钟入栈             
                ret++;  //分钟数++
            }
            //这是分钟栈满栈后把元素全部移出到队尾
            int a=0;  
            while(a<5){
                En_Queue(q,stack_pop(min));
                a++;
            }
            stack_push(fmin,De_Queue(q)); //移出后兑换一个五分钟球
        }
        //j循环结束，五分钟栈满栈，移出全部元素到队尾
        int b=0;
        while(b<12){
            En_Queue(q,stack_pop(fmin));
            b++;
        }
        //移出完毕，兑换一个小时球
        stack_push(hour,De_Queue(q));       
    }
    //i循环结束，小时栈满栈，把小时栈的球也移到队尾
    int c=0;
    while(c<12){
        En_Queue(q,stack_pop(hour));
        c++;
    }
    //函数结束代表12小时执行一次队列的最终结果
}

接下来问题就变成了执行多少次这个函数，可能恢复到原来的小球顺序，写一个队列和元素的比较即可,检查队列的元素是否依次等于0-26：

int compare_queen(linkqueue *q){
    int num=0;
    while(num<27){
        if(q->front->next->data!=num){
            return 0;
        }
        num++;
        q->front->next=q->front->next->next;
    }
    return 1;
}

在此之前我犯了一个错误，我令

linkqueue *temp=q;

殊不知误用了地址传递，实际上temp和q永远指向一块地址，temp和q当然始终相等，如果需要通过队列的比较，应该重新初始化一块队列复制其元素，后来嫌麻烦就使用了常数的比较方法。至此问题就解决了，以下是完整代码和运行结果，需要顺序栈、链式队列的头文件支持。

#include <stdio.h>
#include "linkqueue.h"
#include "sqstack.h"

void show_queue(linkqueue *q){  //补充实现查看队列元素函数
	if(q==NULL){
		printf("error!\n");
		return;
	}
	linklist i=q->front->next;
	while(i!=NULL){
		printf("%d\t",i->data);
		i=i->next;
	}
}

int ret=0;
void circulate(sqstack *hour,sqstack *fmin,sqstack *min,linkqueue *q){
	//这是每12个小时执行的结果
	for(int i=0;i<12;i++){  //小时
		for(int j=0;j<12;j++){   //5分钟
			for(int k=0;k<5;k++){  //每分钟
				stack_push(min,De_Queue(q)); //分钟入栈				
				ret++;  //分钟数++
			}
			//这是分钟栈满栈后把元素全部移出到队尾
			int a=0;  
			while(a<5){
				En_Queue(q,stack_pop(min));
				a++;
			}
			stack_push(fmin,De_Queue(q)); //移出后兑换一个五分钟球
		}
		//j循环结束，五分钟栈满栈，移出全部元素到队尾
		int b=0;
		while(b<12){
			En_Queue(q,stack_pop(fmin));
			b++;
		}
		//移出完毕，兑换一个小时球
		stack_push(hour,De_Queue(q));		
	}
	//i循环结束，小时栈满栈，把小时栈的球也移到队尾
	int c=0;
	while(c<12){
		En_Queue(q,stack_pop(hour));
		c++;
	}
	//函数结束代表12小时执行一次队列的最终结果
}

int compare_queen(linkqueue *q){
	int num=0;
	while(num<27){
		if(q->front->next->data!=num){   //数据不等于num（0），直接退出
			return 0;
		}
		num++;   // 下一位比较
		q->front->next=q->front->next->next;
	}
	return 1;
}

int main(){
	sqstack* hour=stack_create(12); //初始化小时杯子
	sqstack *fmin=stack_create(12); //初始化五分钟杯子
	sqstack *min=stack_create(5);  //初始化分钟杯子
	linkqueue* q=queue_create(); //初始化小球队列
	for(int i=0;i<=26;i++){
		En_Queue(q,i);          //一共27个小球，顺序0到26
	}
	show_queue(q);      //打印初始队列1-27
	
	while(1){
		circulate(hour,fmin,min,q);  //执行12小时
		show_queue(q);     //查看12小时后的结果
		printf("ret=%d\n",ret);   
		if(compare_queen(q)==1){     //比较相等
			break;   //不用再执行12小时循环了
		}
	}
}