[数据结构与算法]栈，队列，链表

第二章 栈，队列，链表

#include<stdio.h>
int main(){
	int q[102]={0,6,3,1,7,5,8,9,2,4},head,tail;
	int i;
	//初始化队列
	head=1;
	tail=10;//队列中已经有9个元素了，指向队尾的后一个位置
	while(head<tail)//当队列不为空时执行
	{
		//打印队首并将队首出队
		printf("%d",q[head]);
		head++;
		//先将新队首的数添加到队尾
		q[tail]=q[head];
		tail++;
		//再将队首出队
		head++;
	}
	getchar();getchar();
	return 0;
}
最后输出：6 1 5 9 4 7 2 8 3

使用结构体来实现队列操作

#include<stdio.h>
struct queue
{
	int data[100];//队列的主体，用来存储内容
	int head;//队首
	int tail;//队尾
};
int main()
{
	struct queue q;
	int i;
	//初始化队列
	q.head=1;
	q.tail=1;
	for(i=1;i<=9;i++)
	{
		//依次向队列插入9个数
		scanf("%d",&q.data[q.tail]);
		q.tail++;
	}
	while(q.head<q.tail)
	{
		//打印队首并将队首出队
		printf("%d ",q.data[q.head]);
		q.head++;
		//先将新队首的数添加到队尾
		q.data[q.tail]=q.data[q.head];
		q.tail++;
		//再将队首出队
		q.head++;
	}
	getchar();getchar();
	return 0;
}

用栈来判断回文字符

#include<stdio.h>
#include<string.h>
int main()
{
	char a[101],s[101];
	int i,len,mid,next,top;
	gets(a);//读入一行字符串
	len=strlen(a);//求字符串的长度
	mid=len/2-1;//求字符串的中点
	top=0;//栈的初始化
	//将mid前的字符依次入栈
	for(i=0;i<=mid;i++)
		s[++top]=a[i];
	//判断字符串的长度是奇数还是偶数，并找出需要进行字符匹配的下标
	if(len%2==0)
		next=mid+1;
	else
		next=mid+2;
	
	//开始匹配
	for(i=next;i<=len-1;i++)
	{
		if(a[i]!=s[top])
			break;
		top--;
	}
	//如果top的值为0，则说明栈内所有的字符都被一一匹配了
	if(top==0)
		printf("YES");
	else
		printf("NO");
	getchar();getchar();
	return 0;
}
输入
ahaha
运行结果是
YES

纸牌游戏
规则：将一副扑克牌平均分成两份，每人拿一份。小恒先拿出手中的第一张扑克牌放在桌上，然后小哈也拿出手中的第一张扑克牌，并放在小恒刚打出的扑克牌上面，就像这样两人交替出牌。出牌时，如果某人打出的牌与桌上某张牌的牌面相同，即可将两张相同的牌及其中所夹的牌全部取走，并依次放到自己手中牌的末尾。当任意一人手中的牌全部出完时，游戏结束，对手获胜。

#include<stdio.h>
struct queue
{
	int data[1000];
	int head;
	int tail;
};
struct stack
{
	int data[10];
	int top;
};
int main()
{
	struct queue q1,q2;
	struct stack s;
	int book[10];
	int i,t;
	//初始化队列
	q1.head=1;q1.tail=1;
	q2.head=1;q2.tail=1;
	//初始化栈
	s.top=0;
	//初始化用来标记的数组，用来标记那些牌已经在桌面上
	for(i=1;i<=9;i++)
		book[i]=0;
	//依次向队列中插入6个数
	//小恒手上的6张牌
	for(i=1;i<=6;i++)
	{
		scanf("%d",&q1.data[q1.tail]);
		q1.tail++;
	}
	//小哈手上的6张牌
	for(i=1;i<=6;i++)
	{
		scanf("%d",&q2.data[tail]);
		q2.tail++;
	}
	while(q1.head<q1.tail&&q2.head<q2.tail)
	{
		t=q1.data[q1.head];//小恒出一张牌
		//判断小恒当前打出的牌是否能赢
		if(book[t]==0)//表明桌上没有牌面为t的牌
		{
			//小恒此轮没有赢牌
			q1.head++;//小恒已经打出一张牌，所以要把打出的牌出队
			s.top++;
			s.data[s.top]=t;//再把打出的牌放到桌上，即入栈
			book[t]=1;//标记桌上现在已经有牌面为t的牌
		}
		else
		{
			//小恒此轮可以赢牌
			q1.head++;//小恒已经打出一张牌，所以要把打出的牌出队
			q1.data[q1.tail]=t;//紧接着把打出的牌放到手中牌的末尾
			q1.tail++;
			while(s.data[s.top]!=t)//把桌上可以赢得的牌依次放到手中牌的末尾
			{
				book[s.data[s.top]]=0;//取消标记
				q1.data[q1.tail]=s.data[s.top];//依次放入队尾
				q1.tail++;
				s.top--;//栈中少了一张牌，所以栈顶要减一
			}
		}
		t=q2.data[q2.head];//小哈出一张牌
		//判断小哈当前打出的牌是否能赢牌
		if(book[t]==0)//表明桌上没有牌面为t的牌
		{
			//小哈此轮没有赢牌
			q2.head++;//小哈已经打出一张牌，所以要把打出的牌出队
			s.top++;
			s.data[s.top]=t;//再把打出的牌放到桌上，即入栈
			book[t]=1;//标记桌上现在已经有牌面为t的牌
		}
		else
		{
			//小哈此轮可以赢牌
			q2.head++;//小哈已经打出一张牌，所以要把打出的牌出队
			q2.data[q2.tail]=t;//紧接着把打出的牌放到手中牌的末尾
			q2.tail++;
			while(s.data[s.top]!=t)//把桌上可以赢得的牌依次放到手中牌的末尾
			{
				book[s.data[s.top]]=0;//取消标记
				q2.data[q2.tail]=s.data[s.top];//依次放入队尾
				q2.tail++;
				s.top--;
			}
		}
	}
	if(q2.head==q2.tail)
	{
		printf("小恒win\n");
		printf("小恒当前手中的牌是");
		for(i=q1.head;i<=q1.tail-1;i++)
			printf(" %d",q1.data[i]);
		if(s.top>0)//如果桌上有牌则依次输出桌上的牌
		{
			printf("\n桌上的牌是");
			for(i=1;i<=s.top;i++)
				printf(" %d",s.data[i]);
		}
		else
			printf("\n桌上已经没有牌了");
	}
	else
	{
		printf("小哈win\n");
		printf("小哈当前手中的牌是");
		for(i=q2.head;i<=q2.tail-1;i++)
			printf(" %d",q2.data[i]);
		if(s.top>0)//如果桌上有牌则依次输出桌上的牌
		{
			printf("\n桌上的牌是");
			for(i=1;i<=s.top;i++)
				printf(" %d",s.data[i]);
		}
		else
			printf("\n桌上已经没有牌了");
	}
	getchar();getchar();
	return 0;
}
输入
2 4 1 2 5 6
3 1 3 5 6 4
运行结果是
小恒win
小恒当前手中的牌是 5 6 2 3 1 4 6 5
桌上的牌是 2 1 3 4

该程序的缺陷：有可能游戏无法结束。

链表

指针的作用：存储一个地址，确切的说是存储一个内存空间的地址

通过操作指针来输出变量的值

#include<stdio.h>
int main()
{
	int a=10;
	int *p;//定义一个指针
	p=&a;//指针p获取变量a的地址
	printf("%d",*p);//输出指针p所指向的内存中的值
	getchar();getchar();
	return 0;
}

这里printf语句中的号叫做间接运算符，作用是获取指针p所指向的内存中的值。在C语言中有三个用途
①乘号，用作乘法运算
②申明一个指针，在定义指针变量时使用，例如int *p
③间接运算符，获取指针所指向的内存中的值，例如printf("%d",*p)

malloc函数的作用就是从内存中申请分配指定字节大小的内存空间。如malloc(4)就申请了4个字节。还可用sizeof(int)来获取类型所占用的字节数。malloc(sizeof(int)).

int *p
p=(int *)malloc(sizeof(int));

malloc函数的返回类型是void * 类型，void *表示未确定类型的指针。在C语言中，void *类型可以强制转换为任何其他类型的指针。
Q：指针就是用来存储内存地址的，为什么要分不同类型的指针
A:因为指针变量存储的是一个内存空间的首地址（第一个字节的地址），但是这个空间占用了多少字节，用来存储什么类型的数据，则是由指针的类型来标明的，这样系统才知道取多少个连续内存作为一个数据。

通过指针对刚才申请的4字节的空间进行操作，项这个空间中存入整数10

#include<stdio.h>
#include<stdlib>
int main()
{
	int *p;//定义一个指针
	p=(int *)malloc(sizeof(int));//指针p获取动态分配的内存空间地址
	*p=10;//向指针p所指向的内存空间中存入10
	printf("%d",*p);//输出指针所指向的内存中的值
	return 0;
}
运行结果是 10

有了malloc函数，方便我们在程序运行过程中根据实际情况来申请空间。

#include<stdio.h>
#include<stdlib.h>
//创建一个结构体用来表示链表的结点类型
struct node
{
	int data;//用于存储具体的数值
	struct node *next;//用来存储指向下一个结点的地址，因为下一个结点的类型是struct node，所以这个指针的类型也必须是struct node *类型的指针
};
int main()
{
	struct node,*head,*p,*q,*t;
	int i,n,a;
	scanf("%d",&n);
	//用一个头指针head指向链表的最开始，当链表还没有建立的时候头指针head为空，即指向空结点
	head=NULL;//头指针初始为空
	for(i=1;i<=n;i++)//循环读入n个数
	{
		scanf("%d",&a);
		//动态申请一个空间，用来存放一个结点，并用临时指针p指向这个结点
		p=(struct node *)malloc(sizeof(struct node));
		p->data=a;//将数据存储到当前结点的data域中
		p->next=NULL;//设置当前结点的后继结点指向空，也就是当前结点的下一个结点为空
		if(head==NULL)
			head=p;//如果这是第一个创建的指针，则将头指针指向这个结点
		else
			q->next=p;//如果不是第一个创建的结点，则将上一个结点的后继指针指向当前结点
		q=p;//指针q也指向当前结点，因为待会临时指针p将会指向新创建的结点
	}

	scanf("%d",&a);//读入待插入数
	t=head;//从链表头部开始遍历
	while(t!=NULL)//没有达到链表尾部的时候循环
	{
		if(t->next->data>a)//如果当前结点下一个结点的值大于待插入数，将数插入到中间
		{
			p=(struct node *)malloc(sizeof(struct node));//动态申请一个空间，用来存放新增结点
			p->data=a;
			p->next=t->next;//新增结点的后继指针指向当前结点的后继指针所指向的结点
			t->next=p;//当前结点的后继指针指向新增结点
			break;//插入完毕退出循环
		}
		t=t->next;//继续下一结点
	}
	//输出链表中的所有数
	t=head;
	while(t!=NULL)
	{
		printf("%d",t->data);
		t=t->next;//继续下一结点
	}
	return 0;
}

设置头指针并设置新创建结点的*next指向空，头指针的作用是方便以后从头遍历整个链表。
输入
9
2 3 5 8 9 10 18 26 32
运行结果
2 3 5 8 9 10 18 26 32

上面这段代码没有释放动态申请的空间，虽然没有错误，但很不安全。