橘生淮南

记录学习中的点点滴滴

0%

发表于
本文字数： 3k 阅读时长 ≈ 3 分钟

我们把数据类型分为基本数据类型与高级数据类型，基本数据类型中有：整数，浮点数，字符，指针，数组（已经定义好的），而高级数据类型：像结构体，共用体，枚举等。

链表与数组
相同点：
链表与数组都是按顺序存储若干个相同数据类型或相同成员的结构体
不同点：
●数组各个元素的空间必须连续，而链表各个元素的空间不一定连续，可以分散存储在内存中。
●查找数组元素，只需要给出下标，而查找链表元素，需要根据链表的首结点记录地址，顺序查找下去；
●删除数组一个非尾部的元素，就要将后面的元素依次向前移动，以保证数组空间的连续性，而删除链表中的一个节点，只需要修改删除节点前后的指针。

【链表的好处】
●不需要预先分配存储空间；
●分配的空间可以根据程序的需要扩大和缩小；
●如果数据的数量不确定，或者经常变化，就要优先考虑使用链表；
●节约内存空间；

如果元素个数确定，优先使用数组，如果元素个数不确定，优先使用链表

【链表的存储结构】
链表的节点不仅包括元素值，也包括下一个元素的地址（数据域，指针域），即（元素，地址）
举个例子：如果链表包含四个元素，而首地址是1255，则：
在这里插入图片描述

结点的表示：元素值与下一个元素的地址

如上图：地址1255是结点自身的地址，不是指针域，Link1是数据域，1356是指向下一个结点的地址。

【链表是一个结构体】

1
2
3
4
5
6
struct LinkNode
{
char data;//存放数据（数据域）
struck LinkNode *next; //存放下一个结点的地址（指针域）
};
struct LinkNode *head;//*head是为了存放链表的首地址，必须声明表头指针

在这里插入图片描述
同数组一样，链表名称即为首地址，不过链表是个指针类型的结构体变量

来个例子：用链表存放三个学生的信息
在这里插入图片描述
【遍历链表】
1.将链表h的各个节点的数据域输出
2.从第一个结点开始，只要p非空，就输出这个结点，并将p后移
在这里插入图片描述
我们为什么要把struct Link *h（头结点）作为函数的参数，因为我们在遍历链表的时候的顺序是从头到尾的，然后我们再将游标指针指向头结点struct Link *p=h;

【声明链表】
在这里插入图片描述
我们用head=NULL;或是用 !head，判断链表为空；用p=p->next；//把下一个地址的值赋给本身

【链表的插入操作】
当将一个值为x的结点s插入链表中，我们先用malloc函数动态申请内存，再赋值给s，s是插入点的指针；
在这里插入图片描述
【插入到链表的头部】
在这里插入图片描述
如图：头指针*head为1255，当把链表插入到头部后，我们的操作：

1
2
3
s->next=head;//将s的下一个结点指向head
head=s;//首结点赋值为s的值
//head总是表示头结点，当插入链表后，s变为头结点，所以我们要将s的值还给head

【插入到链表的中部】
在这里插入图片描述
假如有一个指针p，p原先保存的地址是1356，而p->next是1475，但我们当将一个值为x的结点s插入链表中，如图：
在这里插入图片描述

1
2
s->next=p->next;//s指针域指向原先p的指针域
p->next=s;//插入后，p的指针域指向s

【插入到链表的尾部】
如何把一个链表插入非空链表尾部？
在这里插入图片描述
我们先要判断尾部！
直到p->next（指针域）为空值时，则到了链表的尾部，这是我们再将链表插入非空链表尾部。
在这里插入图片描述
具体实现：
在这里插入图片描述

1
2
p=p->next;//如果p不是尾结点就往后移动
p->next=s;//最后让p的next结点指向p

【删除链表的结点】
1.【删除表头结点，直接更改头指针head】
在这里插入图片描述
原head是头结点，地址是1255，指针域是1356，当我们删除第一个链表时，现在的head的地址变成1356，指针域是1475。即head=head->next;

2.【删除非表头结点】
在这里插入图片描述
删除前，假设指针p的地址是1475，pre(p的前驱结点)->next等价于p，也就是地址1475，而p->next==1008，当我们删除p的时候，于是pre(p的前驱结点)->next，从指向地址1475变为指向地址1008，即（pre->next=p->next)，这时指针p变成野指针，应该释放掉。

【尾插法操作】
在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <stdio.h>
#include <stdlib.h>
struct link
{
	int data;//数据域
	struct link *next;//指针域

};//注意分号

//创建链表
struct link *creat_link(int arr[],int n)
{
	struct link *h=NULL;//声明头结点
	struct link *s;//声明插入结点
	struct link *r;//声明尾结点
	int i=0;
	for(i=0;i<n;i++)
	{
	s=(struct link *)malloc(sizeof(struct link));//对s进行动态内存分配
	s->data=arr[i];//数据域来自数组
    s->next=NULL;//尾插法

//判断链表是不是空链表
	if(h==NULL)
	{
	h=s;//将h赋上插入点的值
	}
	else
	{
	r->next=s;//不是空链表，将尾指针赋上空链表的值
	}
	r=s;
	}
	return h;
}

//遍历链表函数
void output(struct link *h)
{
struct link *p=h;
while(p!=NULL)
{
printf("%d\t",p->data);
p=p->next;
}
printf("\n");
}

int main(void)
{
	int arr[6]={0};
	int i=0;
	struct link *head;
	srand(time(NULL));
	for(i=0;i<6;i++)
	{
		a[i]=(int)(rand()%100);
	}
	head=creat_link(arr,6);
	printf("arr values:"\n);
	for(i=0;i<6;i++)
	{
	printf("%d",arr[i]);//输出数组的值
	}
printf("\n");
printf("输出链表的值:\n");
output(head);
return 0;
}

【头插法操作】
在这里插入图片描述
【共用体】
●使用共用体，使多个变量共享一块内存
●目地是为了节约内存空间

【共用体声明】

1
2
3
4
5
union 共用体名
{
成员列表....
};
//共用体使用字节最长的成员所占的内存空间

注意：初始化共用体只能给一个值的序列
在这里插入图片描述
另外共用体中不要包含指针成员，因为共用体的成员值很容易发生改变。

发表于
本文字数： 4k 阅读时长 ≈ 4 分钟

如果说可以用循环队列解决队列的虚假满的状态，那么什么是虚假满状态？

假设当前顺序队列分配的最大空间是6，当队尾指针从5下标指向6下标时(6下标实际不存在)，说明此时队列已满，然而依然可以进行出队的操作，顺序队不能像顺序栈那样进行存储再分配扩大数组空间，所以队列的实际可用空间并未占满。

循环队列就是将顺序队列构造成为一个环状的队列空间，如图：
在这里插入图片描述

注意：

此时当指针front=指针rear时，无法判断队列空间是满还是空，有两种解决思路：
1.另设一个标志位区分队列空间是满还是空；
2.少用一个空间，约定以“队列头指针在队列尾指针的下一位置”作为队列满的状态标志。

来吧！举个栗子吧，如图：
【情况1】
在这里插入图片描述
初始化，队头指针front，队尾指针rear都指向0下标；
当存入数据元素1后，队尾指针rear从0下标指向1下标；
当存入数据元素2后，队尾指针rear从1下标指向2下标；
当存入数据元素3后，队尾指针rear从2下标指向3下标；
当存入数据元素4后，队尾指针rear从3下标指向4下标；
…
当存入数据元素8后，队尾指针rear从7下标指向0下标；(队列已满)
如何判断队头指针front与队尾指针rear重合时，队列是空还是满呢？我们假如用flag来标记队头指针front与队尾指针rear的重合状态，于是规定当flag=0时：队列为空；当flag=1时，队列为满。

【情况2】
在这里插入图片描述
我们把7下标的空间空出不存放数据，当数据元素7进为6下标的空间后，队尾指针rear就指向了为7下标的空间(此时7下标空间是空的)，理论上8个空间只用了7个空间，但在逻辑上我们规定此时队列已满。当rear+1后，队头指针front与队尾指针rear重合，说明此时队列空间逻辑已满，我们先将队头指针所指空间的元素出队，队头指针前移指向1下标，此时再将元素进下标为7的空间，队尾指针rear前移(指向0下标)，当rear+1后，队头指针front与队尾指针rear又重合，说明此时队列空间逻辑又已满，依次循环往复，出队—>队头指针front前移——>后面入队——>队尾指针rear前移(判断条件是rear+1后，队头指针front与队尾指针rear是否重合，不重合则可继续入队)。

但是，计算机是没有环状的存储空间的，依然是以线性存储的方式，那计算机如何判断什么时候队尾指针再次与队头指针重合呢？

—————OK！那就是：进行模运算—————

具体模运算是怎么实现的，文字显得苍白无力，还是那句话，把代码跑起来，慢慢体会！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <stdio.h>
#include <malloc.h>
#include <assert.h>

#define MAXSIZE 8//定义队列初始化存放8个数据元素
typedef int ElmeType;

/*给出顺序队列的结构*/
typedef struct Queue
{
	ElmeType *base;//指针base指向有效的队列空间
	int      front;//队头指针
	int      rear;//队尾指针指向下一个有效的空间
}Queue;

/*初始化顺序队列*/
void InitQueue(Queue *Q)
{
	Q->base=(ElmeType *)malloc(sizeof(ElmeType)*MAXSIZE);//开辟队列空间
	assert(Q->base!=NULL);//断言——是否开辟空间成功
	Q->front=Q->rear=0;//队头指针和队尾指针都指向队列的0下标,此时队列为空
}

/*入队*/
void EnQueue(Queue *Q,ElmeType x)
{
//数据入队后,队尾指针从当前空间指向下一个有效的空间,此时称队尾指针是伪指针;
//当伪指针所指下标+1后正好等于队列空间容量时,此时我们希望伪指针可以重新指向队头,而不是出界,于是进行模运算;

//(Q->rear+1)%MAXSIZE——若模为0,则伪指针恰好指向队列的最后一个有效空间,我们需要让此时的伪指针重新指向0下标而不是最后一个有效空间;
//(始终都要将队列最后一个有效空间空出)循环开始:
	if((Q->rear+1)%MAXSIZE==Q->front)//若伪指针所指下标+1与队头指针指向相同的下标,此时判断为队列逻辑已满
	return;//返回,理论上队列保留了队列最后一个有效空间
	Q->base[Q->rear]=x;//否则队列逻辑不满,继续在队尾指针所指下标进行入队,入队完成后,队尾指针又从当前空间指向下一个有效的空间
	Q->rear=(Q->rear+1)%MAXSIZE;//当逻辑空间满后,模运算实现队尾指针重新指向0下标而不是最后一个有效空间;
}

/*展示顺序队列元素*/
void ShowQueue(Queue *Q)
{
	printf("顺序队列中存放的元素:");
	for(int i=Q->front;i!=Q->rear;)
	{
		printf("%d ",Q->base[i]);//依次打印队头指针所指下标中的数据到队尾指针所指下标中的数据
		i=(i+1)%MAXSIZE;//循环打印,7下标不能打印,重新回到0下标(循环时,队尾下标-队头下标=-1)
	}
	printf("\n");
}

/*出队*/
void DeQueue(Queue *Q)
{
//出队一个元素,队头指针指向下一个有效的数据元素
	if(Q->front==Q->rear)//队头队尾指向相同,队列为空
		return;
	Q->front=(Q->front+1)%MAXSIZE;//队头指针循环,模运算实现队头指针重新指向0下标而不是最后一个有效空间;
}

/*取队头元素*/
void GetHead(Queue *Q,ElmeType *v)//指针v带回队头元素
{
//要获取队头,前提是队列不空
	if(Q->front==Q->rear)//队列为空
	return;
	*v=Q->base[Q->front];//必须在base所指的空间里取元素
}

/*顺序队列的长度*/
int Length(Queue *Q)
{
	return (Q->rear - Q->front);
	//下标0开始存放数据,进队后,队尾指针指向下一个有效的新空间
	//队列中元素的个数正好是队尾队头所指的下标之差
	//但是当队列逻辑空间满后,再存储数据需要先出队,再进行入队,此时队尾队头所指的下标之差为-1
}

/*清除顺序队列*/
void ClearQueue(Queue *Q)
{
	Q->front=Q->rear=0;//队列置为空
}

/*销毁顺序队列*/
void DestroyQueue(Queue *Q)
{
	free(Q->base);//释放base所指的队列空间
	Q->base=NULL;//预防野指针
}
/**/

void main()
{
	Queue Q;
	ElmeType e;//定义队头元素
	InitQueue(&Q);//&Q是传入队列的地址
	printf("将1,2,3,4,5,6,7,8依次入队\n");
	for(int i=1;i<=8;++i)
	{
		EnQueue(&Q,i);
	}
	ShowQueue(&Q);
	printf("顺序队的长度为:%d\n",Length(&Q));
	printf("\n");
	printf("进行出队\n");
	DeQueue(&Q);
	ShowQueue(&Q);
	GetHead(&Q,&e);
	printf("队头元素为:%d\n",e);
	printf("\n");
	printf("将元素10入队\n");
	EnQueue(&Q,10);
	ShowQueue(&Q);
	printf("\n");
	printf("进行出队\n");
	DeQueue(&Q);
	ShowQueue(&Q);
	GetHead(&Q,&e);
	printf("队头元素为:%d\n",e);
	printf("\n");
	printf("将元素20入队\n");
	EnQueue(&Q,20);
	ShowQueue(&Q);
	printf("\n");
	ClearQueue(&Q);
	DestroyQueue(&Q);
}

运行结果：
在这里插入图片描述

发表于
本文字数： 3.6k 阅读时长 ≈ 3 分钟

顺序栈是分配一段连续的内存空间，需要两个指针，即指针top与指针base，指针top指向栈顶，指针base指向栈底，而链栈每个结点的地址是不连续的，所以只需要一个栈顶指针即可，相比于单链表，栈链的操作只能在栈顶进行。

入栈前，旧的栈顶结点是新入栈结点的后继结点，栈顶指针重新指向新入栈的结点；
出栈前，新的栈顶结点是即将出栈结点的后继结点，栈顶指针指向出栈结点的后继(即指向新的栈顶结点，把出栈结点释放)；

空口无凭，纸上的概念都显得苍白无力，让我们把代码开起来，慢慢细品！！！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include <stdio.h>
#include <malloc.h>
#include <assert.h>//断言——如果条件返回错误，则终止程序执行
typedef int ElemType;//定义元素类型为int型，即为存放整型数据的栈链
/*给出结点结构*/
typedef struct StackNode
{
	ElemType data;//数据域
	struct StackNode *next;//指针域(指向下一个结点的地址)
}ListNode,*pNode;//定义结点类型,定义结点的指针类型

/*给出链栈结构*/
typedef struct ListStack
{
	pNode top;//指针top指向栈顶元素
	size_t size;//结点的个数
}ListStack;

/*初始化链栈*/
void InitStack(ListStack *s)
{
    s->top=(StackNode*)malloc(sizeof(StackNode)); //栈顶指针指向新申请的结点  
	assert(s->top!=NULL);//判断申请空间是否为空
	s->top = NULL;//栈顶指针初始化
	s->size=0;//栈中元素初始化为0个
}

/*链栈是否为空*/
bool IsEmptyStack(ListStack *s)//给出链栈的位置
{
	if(s->size == 0)
		return true;
	else
		return false;
}

/*入链栈*/
void PushStack(ListStack *s, ElemType x)//给出链栈的位置和即将入栈的元素
{
	StackNode *p=(StackNode*)malloc(sizeof(StackNode));//指针p指向申请的新结点
	assert(p!=NULL);
	p->data = x;//入栈的元素保存新结点的数据域
    p->next = s->top;//新结点的指针域保存栈顶指针的地址
    s->top = p;//栈顶指针重新指向新结点
	s->size++;//栈中元素增加
  }

/*出链栈*/
void PopStack(ListStack *s, ElemType *v)
{
		StackNode *p=s->top;//指针p指向栈顶
		*v=s->top->data;//指针v带回栈顶元素
		s->top=s->top->next;//栈顶指针指向栈顶结点的后继结点
		free(p);//释放栈顶结点
	    s->size--;//栈中元素减少
}

/*展示链栈*/
void ShowStack(ListStack *s)
{
		StackNode *p=s->top;//指针p指向栈顶
		printf("链栈中的数据元素:");
		while(p!=NULL)//栈不为空,执行
		{
			printf("%d->",p->data);
			p = p->next;//p指向下一个结点
		}
			printf("\n");
}

/*取栈顶指针*/
void GetTopStack(ListStack *s,ElemType *v)
{
	if(s->top==NULL)
		return;
	else
		*v=s->top->data;//指针v带回栈顶元素
}

/*栈长*/
int LengthStack(ListStack *s)
{
	return s->size;
}

/*清空栈链*/
void ClearStack(ListStack *s)
{
	StackNode *p=s->top;//指针p指向栈顶结点
	while(p!=NULL)
	{
		s->top=p->next;//栈顶指针指向栈顶结点的后继结点
		free(p);//释放栈顶结点
		p=s->top;//指针p重新指向栈顶结点
	}
	s->top = NULL;//否则栈顶指针置空
	s->size = 0;//栈中长度置0
}

/*销毁栈链*/
void DestroyStack(ListStack *s)
{
	ClearStack(s);
	free(s->top);//销毁最初创建的结点
	s->top=NULL;//预防野指针
}

void main()
{
		ListStack  st;
		ElemType e;
		InitStack(&st);
		if(IsEmptyStack(&st))
			printf("栈为空,初始化成功\n\n");
		else
			printf("栈非空!\n\n");
 		printf("入栈\n");
		for(int i=0;i<5;i++)
		{
			PushStack(&st,i);
		}
	    ShowStack(&st);
		printf("\n");
		int k=LengthStack(&st);
		printf("栈的长度为:%d \n\n",k);
		GetTopStack(&st,&e);
		printf("栈顶元素为:%d \n",e);
		printf("\n");
  		printf("出栈\n");
		PopStack(&st,&e);
		printf("出栈的元素为:%d \n",e);
		ShowStack(&st);
		printf("\n");
		PopStack(&st,&e);
		printf("出栈的元素为:%d \n",e);
		ShowStack(&st);
		printf("\n");
		PopStack(&st,&e);
		printf("出栈的元素为:%d \n",e);
		ShowStack(&st);
		printf("\n");
		PopStack(&st,&e);
		printf("出栈的元素为:%d \n",e);
		ShowStack(&st);
		printf("\n");
		PopStack(&st,&e);
		printf("出栈的元素为:%d \n",e);
		ShowStack(&st);
		printf("\n");
		PopStack(&st,&e);
		printf("出栈的元素为:%d \n",e);
		ShowStack(&st);
		ClearStack(&st);
		DestroyStack(&st);
}

运行结果：
在这里插入图片描述

发表于
本文字数： 2.9k 阅读时长 ≈ 3 分钟

栈是限定仅在表面进行插入或删除操作的线性表。因此，对栈来说，表尾端有其特殊含义，称为栈顶，相应地，表头端称为栈底，不含元素的空表称为空栈。

顺序栈，即栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置，通常的习惯做法是以top=0表示空栈。

话不多说，把代码跑起来！！！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <stdio.h>
#include <malloc.h>
#include <assert.h>//断言

typedef int ElemType;//定义元素类型为int型，即为存放整型数据的顺序栈
#define STACK_INIT_SIZE 8//初始化顺序栈可以存放8个数据元素

/*顺序栈的结构*/
typedef struct SeqStack
{
	ElemType *base;//指针base指向开辟的栈空间
	int capacity;//定义顺序栈的容量(最大容量)
	int top;//定义栈顶指针(同时表示当前栈中的元素个数)
}SeqStack;//定义结构体变量

/*初始化顺序栈*/
void InitStack(SeqStack *s)//给出顺序栈的位置
{
//申请顺序栈的空间(元素类型)
	s->base=(ElemType *)malloc(sizeof(ElemType)*STACK_INIT_SIZE);
	assert(s->base!=NULL);//不为空时空间申请成功
	s->capacity=STACK_INIT_SIZE;//栈的容量为初始化大小
	s->top=0;//栈顶指针top指向0下标的位置,表示此时栈中一个数据元素都没有
}

bool IsFull(SeqStack *s)//入栈判断栈是否满
{
	return s->top >= s->capacity;//指针top所指的下标正好与栈的容量相等,此时栈已满
}

bool IsEmpty(SeqStack *s)//出栈判断栈是否空
{
	return s->top==0;//指针top所指的下标正好是0下标
}

/*入栈*/
void Push(SeqStack *s,ElemType x)
{
	if(IsFull(s))
	{
		printf("栈空间已满,%d不能入栈\n",x);
		return;
	}
	s->base[s->top]=x;//当前指针top所指的位置来存放数据,指针base指向真实的栈空间
	s->top++;//指针top指向下一个可用的栈空间
}

/*出栈*/
void Pop(SeqStack *s)
{
	if(IsEmpty(s))
	{
		printf("栈空间已空,不能出栈\n");
		return;
	}
	s->top--;//指针top指向上一个可用的栈空间
}

/*取栈顶元素*/
bool GetTop(SeqStack *s,ElemType *v)
{
	if(IsEmpty(s))
	{
		printf("栈空间已空,不能取栈顶元素\n");
		return false;
	}
	*v=s->base[s->top-1];//把栈顶元素存放在元素v的地址里,传回元素v
//因为入栈一个元素后,指针top就指向下一个空的栈空间,所以取栈顶元素,应该读取上一个栈空间里的元素,即用top-1的结果作为base的下标
	return true;
}

/*显示栈中元素*/
void Show(SeqStack *s)
{
	for(int i=s->top-1;i>=0;i--)
//因为入栈一个元素后,指针top就指向下一个空的栈空间,所以显示元素时,应该读取上一个栈空间里的元素
	{
	printf("%d\n",s->base[i]);
	}
	printf("\n");
}

/*栈的长度*/
int Length(SeqStack *s)
{
	return s->top;//返回0则为空栈,返回1则栈的长度为1(此时栈中有1个元素)
}

/*清除栈*/
void Clear(SeqStack *s)
{
	s->top=0;//栈顶指针指向0下标
}

/*销毁栈*/
void Destory(SeqStack *s)
{
	free(s->base);//释放栈空间
	s->base=NULL;//预防野指针
	s->capacity=s->top=0;//栈容量,栈中的数据元素都置0
}

void main()
{
	SeqStack st;//定义一个名为st的顺序栈
	InitStack(&st);
	ElemType  v;//定义临时元素v
	printf("入栈\n");
	for(int i=1;i<=5;++i)
	{
	Push(&st,i);//把1,2,3,4,5依次入栈	
	}
	Show(&st);
	printf("栈的长度为%d\n",Length(&st));
	printf("\n");
	GetTop(&st,&v);//给出临时元素v的地址
	printf("%d 是栈顶元素\n",v);//临时元素v就是栈顶元素,实现取栈顶元素
	printf("\n");
	printf("出栈\n");
	Pop(&st);
	Show(&st);
	printf("栈的长度为%d\n",Length(&st));
	printf("\n");
	printf("清除栈\n");
	Clear(&st);
	Show(&st);
	printf("栈的长度为%d\n",Length(&st));
	Destory(&st);
}

运行结果：
在这里插入图片描述

发表于
本文字数： 7.4k 阅读时长 ≈ 7 分钟

一.树的定义
从数据结构角度看，树包含n（n≥0）个结点，当n=0时，称为空树；非空树的定义如下： T=(D，R)
其中，D为树中结点的有限集合，关系R满足以下条件：
●有且仅有一个结点d0∈D，它对于关系R来说没有前驱结点，结点d0称作树的根结点
●除根结点d0外，D中的每个结点有且仅有一个前驱结点，但可以有多个后继结点
●D中可以有多个终端结点

假如我们有一棵树T=(D，R)，其中：D={A，B，C，D，E，F，G，H}，R={r}
r={<A,B>，<A,C>，<A,D>，<C,E>，<C,F>，<D,G>，<E,H>}，那我们该如何画出其逻辑结构图呢？

解：A是根结点，其余结点分成三个互不相交的子集：　 T1={B}，T2={C，E，F，H}，T3={D，G}； T1、T2、T3都是根结点A的子树，且各自本身也是一棵树

于是我们得到了逻辑结构图，如下：
在这里插入图片描述
说明：树中结点之间的关系应为有向关系，在上图中，结点之间的连线即分支线都是有向的，默认箭头向下的。

二.树的逻辑结构表示
1.树形表示法：使用一棵倒置的树表示树结构，非常直观和形象
2.文氏图表示法：使用集合以及集合的包含关系描述树结构，如图：
在这里插入图片描述
3.凹入表示法：使用线段的伸缩关系描述树结构
在这里插入图片描述
4.括号表示法：将树的根结点写在括号的左边，除根结点之外的其余结点写在括号中并用逗号分隔
在这里插入图片描述
三.树的基本术语
1.什么是结点的度？

树中每个结点具有的子树数或者后继结点数称为该结点的度

在这里插入图片描述
2.什么是树的度？

树中所有结点的度的最大值称之为树的度

在这里插入图片描述
3.什么是分支结点？

度大于0的结点称为分支结点或非终端结点。 度为1的结点称为单分支结点，度为2的结点称为双分支结点，依次类推…

在这里插入图片描述
4.什么是叶子节点？

度为零的结点称为叶子结点或终端结点

在这里插入图片描述
5.什么是孩子结点？

一个结点的后继称之为该结点的孩子结点

在这里插入图片描述
6.什么是双亲结点？

一个结点称为其后继结点的双亲结点

在这里插入图片描述
7.什么是子孙结点？

一个结点的子树中除该结点外的所有结点称之为该结点的子孙结点

在这里插入图片描述
8.什么是祖先结点？

从树根结点到达某个结点的路径上通过的所有结点称为该结点的祖先结点（不含该结点自身）

在这里插入图片描述
9.什么是兄弟结点？

具有同一双亲的结点互相称之为兄弟结点

在这里插入图片描述
10.什么是结点层次？

树具有一种层次结构，根结点为第一层，其孩子结点为第二层，如此类推得到每个结点的层次

在这里插入图片描述
11.什么是树的高度？

树中结点的最大层次称为树的高度或深度

在这里插入图片描述
12.什么是森林？

零棵或多棵互不相交的树的集合称为森林

在这里插入图片描述
四.树的性质
性质1： 树中的结点数等于所有结点的度数加1

性质2：度为m的树中第i层上至多有m^(i-1)个结点，这里应有i≥1

推广：当一棵m次树的第i层有m^(i-1)个结点（i≥1）时，称该层是满的，若一棵m次树的所有叶子结点在同一层，除该层外其余每一层都是满的，称为满m次树。显然，满m次树是所有相同高度的m次树中结点总数最多的树。也可以说，对于n个结点，构造的m次树为满m次树或者接近满m次树，此时树的高度最小。

让我们来道经典例题巩固一下：
若一棵三次树中度为3的结点为2个，度为2的结点为1个，度为1的结点为2个，则该三次树中总的结点个数和度为0的结点个数分别是多少？

解：设该三次树中总结点个数、度为0的结点个数、度为1的结点个数、度为2的结点个数和度为3的结点个数分别为n、n0、n1、n2和n3。
显然，每个度为i的结点在所有结点的度数之和中贡献i个度。依题意有：n1=2，n2=1，n3=2。
由树的性质1可知：n = 所有结点的度数之和+1　
= 0×n0+1×n1+2×n2+3×n3+1
= 1×2+2×1+3×2+1
=11 　　
又因为n=n0+n1+n2+n3 　　
即：n0=n-n1-n2-n3=11-2-1-2=6 　　
所以该三次树中总的结点个数和度为0的结点个数分别是11和6。

五.二叉树
1.二叉树的递归定义
二叉树或者是一棵空树，或者是一棵由一个根结点和两棵互不相交的分别称做根结点的左子树和右子树所组成的非空树，左子树和右子树又同样都是一棵二叉树。

注意：二叉树与度为2的树是不同的！
度为2的树至少有3个结点，而二叉树的结点数可以为0；
度为2的树不区分子树的次序，而二叉树中的每个结点最多有两个孩子结点，且必须要区分左右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树

2.二叉树的5种形态
在这里插入图片描述
3.二叉树的性质
性质1：非空二叉树上叶结点数等于双分支结点数加1，即n0=n2+1
（我们约定：二叉树上叶结点数为n0，单分支结点数为n1，双分支结点数为n2）

例如：一棵二叉树中总结点个数为200，其中单分支结点个数为19，求其叶子结点个数。
解：n=200，n1=19。又n=n0+n1+n2，由性质1得，n2=n0-1，所以有： n=2n0-1+n1
即n0=(n-n1+1)/2=91，所以这样的二叉树中叶子结点个数为91。

性质2：非空二叉树上第i层上至多有2^(i-1)个结点，这里应有i≥1

性质3：高度为h的二叉树至多有2^h-1个结点（h≥1）

性质4：对完全二叉树中编号为i的结点（1≤i≤n，n≥1，n为结点数）有：
（1）若i≤|n/2|，即2i≤n，则编号为i的结点为分支结点，否则为叶子结点；
（2）若n为奇数，则每个分支结点都既有左孩子结点，也有右孩子结点。若n为偶数，则编号最大的分支结点只有左孩子结点，没有右孩子结点，其余分支结点都有左、右孩子结点。
（3）若编号为i的结点有左孩子结点，则左孩子结点的编号为2i；若编号为i的结点有右孩子结点，则右孩子结点的编号为(2i+1)。
（4）除树根结点外,若一个结点的编号为i，则它的双亲结点的编号为|i/2|，也就是说，当i为偶数时，其双亲结点的编号为i/2，它是双亲结点的左孩子结点，当i为奇数时，其双亲结点的编号为(i-1)/2，它是双亲结点的右孩子结点。

4.满二叉树
在一棵二叉树中，当第i层的结点数为2^(i-1)个时，则称此层的结点数是满的，当一棵二叉树中的每一层都满时，且叶子结点在同一层上，则称此树为满二叉树。
在这里插入图片描述

满二叉树特性：除叶子结点以外的其他结点的度皆为2。

5.完全二叉树
在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干个结点，则称此树为完全二叉树。
在这里插入图片描述

完全二叉树特性：二叉树中至多只有最下边两层结点的度数小于2。

6.层序编号
从根结点为1开始，按照层次从小到大、同一层从左到右的次序顺序编号。如图：
在这里插入图片描述
六.二叉树的遍历
二叉树的遍历运算是指按一定的次序访问树中的所有结点，使每个结点恰好被访问一次。其中遍历次序保证了二叉树上每个结点均被访问一次且仅有一次。

1.先序遍历
① 访问根结点
② 先序遍历左子树
③ 先序遍历右子树

2.中序遍历
① 中序遍历左子树
② 访问根结点
③ 中序遍历右子树

3.后序遍历
① 后序遍历左子树
② 后序遍历右子树
③ 访问根结点

4.层次遍历
层次遍历是从根结点出发，按照从上向下，同一层从左向右的次序访问所有的结点，采用层次遍历得到的访问结点序列称为层次遍历序列。
层次遍历序列的特点：其第一个元素值为二叉树中根结点值。

七.二叉树的存储结构
1.顺序存储结构
在这里插入图片描述
用一组连续的存储单元存放二叉树中的结点
在这里插入图片描述
在这里插入图片描述
用“#”补齐为一个完整二叉树
在这里插入图片描述
2.二叉链存储结构
链表中的每个结点包含两个指针，分别指向对应结点的左孩子和右孩子（注意在树的孩子兄弟链表存储结构中，每个结点的两个指针分别指向对应结点的第一个孩子和下一个兄弟）

1
2
3
4
typedef struct tnode
{  ElemType data;			//数据域
   struct tnode *lchild,*rchild;	//指针域
} BTNode;

●data表示数据域，用于存储放入结点值（默认情况下为单个字母）
●lchild 和 rchild 分别表示左指针域和右指针域，分别存储左孩子和右孩子结点（即左、右子树的根结点）的存储地址
●当某结点不存在左或右孩子时，其 lchild 或 rchild 指针域取特殊值NULL
在这里插入图片描述
八.二叉树基本运算实现算法
采用括号表示法表示的二叉树字符串str，且每个结点的值是单个字符。
用ch扫描str，其中只有4类字符，各类字符的处理方式：
1.若ch=’(‘：表示前面刚创建的p结点存在着孩子结点，需将其进栈，以便建立它和其孩子结点的关系。然后开始处理该结点的左孩子，因此置k=1，表示其后创建的结点将作为这个结点（栈顶结点）的左孩子结点；

2.若ch=’)’：表示以栈顶结点为根结点的子树创建完毕，将其退栈；

3.若ch=’,’：表示开始处理栈顶结点的右孩子结点，置k=2；

4.其他情况：只能是单个字符，表示要创建一个新结点p，根据k值建立p结点与栈顶结点之间的联系，当k=1时，表示p结点作为栈顶结点的左孩子结点，当k=2时，表示p结点作为栈顶结点的右孩子结点。

（1）创建二叉树

1
2
3
4
5
6
void CreateBTree(BTNode * &bt,char *str)
{  BTNode *St[MaxSize],*p=NULL;
   int top=-1,k,j=0;
   char ch;
   bt=NULL;		//建立的二叉树初始时为空
   ch=str[j];
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
   while (ch!='\0')			    //str未扫描完时循环
   {	switch(ch)
	{
	case '(':top++;St[top]=p;k=1; break;    //为左孩子结点
	case ')':top--;break;
	case ',':k=2; break;		     //为右孩子结点
	default:p=(BTNode *)malloc(sizeof(BTNode));
		p->data=ch;p->lchild=p->rchild=NULL;
		if (bt==NULL)		     //p为二叉树的根结点
		　　bt=p;
		else			     //已建立二叉树根结点
		{   switch(k) 
		　　{
		　　case 1:St[top]->lchild=p;break;
		　　case 2:St[top]->rchild=p;break;
		　　}
		}
      }
      j++;　ch=str[j];
   }
}

（2）销毁二叉树

1
2
3
4
5
6
7
8
void DestroyBTree(BTNode *&bt)
{   if (bt!=NULL)
　　{	
　　	DestroyBTree(bt->lchild);
		DestroyBTree(bt->rchild);
        free(bt);
　　}
}

（3）求二叉树高度

1
2
3
4
5
6
7
8
9
10
11
int BTHeight(BTNode *bt) 
{  
	int lchilddep,rchilddep;
    if (bt==NULL) return(0); 		   //空树的高度为0
    else
   {  
		lchilddep=BTHeight(bt->lchild);  //求左子树的高度
		rchilddep=BTHeight(bt->rchild);  //求右子树的高度
		return (lchilddep>rchilddep)? (lchilddep+1):(rchilddep+1);
   }
}

（4）求二叉树结点个数

1
2
3
4
5
6
7
8
9
10
11
12
int NodeCount(BTNode *bt)		//求二叉树bt的结点个数
{  
	int num1,num2;
	if (bt==NULL)			//为空树时返回0
	return 0;
	else
  	 {   
		num1=NodeCount(bt->lchild);	//求左子树结点个数
		num2=NodeCount(bt->rchild);	//求右子树结点个数
		return (num1+num2+1);		//返回和加上1
     }
}

（5）求二叉树叶子结点个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int LeafCount(BTNode *bt)	//求二叉树bt的叶子结点个数
{  
	int num1,num2;
	if (bt==NULL)		//空树返回0
	return 0;
	else if (bt->lchild==NULL && bt->rchild==NULL) 
	return 1;		//为叶子结点时返回1
	else
	 {	
		num1=LeafCount(bt->lchild);	//求左子树叶子结点个数
		num2=LeafCount(bt->rchild); 	//求右子树叶子结点个数
		return (num1+num2);		//返回和
   }
}

（6）以括号表示法输出二叉树
1.对于非空二叉树bt，先输出其元素值；
2.当存在左孩子结点或右孩子结点时，输出一个“(”符号；
3.递归处理左子树；
4.有右子树时输出一个“,”符号；
5.递归处理右子树；
6.最后输出一个“)”符号；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void DispBTree(BTNode *bt) 
{ 
 if (bt!=NULL)
   {  
   		printf("%c",bt->data);
        if (bt->lchild!=NULL || bt->rchild!=NULL)
         { 
          printf("(");			//有子树时输出'('
	　    DispBTree(bt->lchild);	//递归处理左子树
		  if (bt->rchild!=NULL)	//有右子树时输出','
	   	  printf(",");
		　DispBTree(bt->rchild);	//递归处理右子树
		　printf(")");			//输出一个')'
    	 }
   }
}

（7）先序遍历

1
2
3
4
5
6
7
8
9
void PreOrder(BTNode *bt)
{   
	if (bt!=NULL)
　	　{	
　		printf("%c ",bt->data);
		PreOrder(bt->lchild);
		PreOrder(bt->rchild);
　　  }
}

先序遍历序列的特点：其第一个元素值为二叉树中根结点值。

（8）中序遍历

1
2
3
4
5
6
7
8
9
void InOrder(BTNode *bt)
{   
	if (bt!=NULL)
　	　{	
　　	InOrder(bt->lchild);
		printf("%c ",bt->data);
		InOrder(bt->rchild);
　　  }
}

中序遍历序列的特点：若已知二叉树的根结点值，以该值为界，将中序遍历序列分为两部分，前半部分为左子树的中序遍历序列，后半部分为右子树的中序遍历序列。

（9）后序遍历

1
2
3
4
5
6
7
8
9
void PostOrder(BTNode *bt)
{  
	 if (bt!=NULL)
　	　{	
　　	PostOrder(bt->lchild);
		PostOrder(bt->rchild);
		printf("%c ",bt->data);
　    }
}

后序遍历序列的特点：最后一个元素值为二叉树中根结点值

（10）层次遍历
层次遍历算法的实现过程：
1.先将根结点进队；
2.在队不空时循环：从队列中出队一个结点p，访问它；若它有左孩子结点，将左孩子结点进队；若它有右孩子结点，将右孩子结点进队。
3.如此操作直到队空为止。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void LevelOrder(BTNode *bt)
{   
	BTNode *p;
　　BTNode *qu[MaxSize];	//定义循环队列,存放二叉链结点指针
　　int front,rear;		//定义队头和队尾指针
　　front=rear=0;		//置队列为空队列
　　rear++; 
　　qu[rear]=bt;	//根结点指针进入队列
　　while (front!=rear)		//队列不为空循环
　　{	
　　	front=(front+1)%MaxSize;
		p=qu[front];			//出队结点p
		printf("%c ",p->data);	//访问该结点
		if (p->lchild!=NULL)		//有左孩子时将其进队
		{   
			rear=(rear+1)%MaxSize;
	　		qu[rear]=p->lchild;
		}
		if (p->rchild!=NULL)		//有右孩子时将其进队
		{   
			rear=(rear+1)%MaxSize;
	　　	qu[rear]=p->rchild;
		}
　　}
}

（11）二叉树的拷贝

1
2
3
4
5
6
7
8
9
10
11
12
void CopyBTree(BTNode *bt,BTNode *&nt)
//由二叉树bt复制产生二叉树nt
{   
	if (bt!=NULL)
　	　{	
　　		nt=(BTNode *)malloc(sizeof(BTNode));	//复制根结点
			nt->data=bt->data;
			CopyBTree(bt->lchild,nt->lchild);	//递归复制左子树
			CopyBTree(bt->rchild,nt->rchild);	//递归复制左子树
　	　}
　　else nt=NULL;		//bt为空树时nt也为空树
}

发表于
本文字数： 6.9k 阅读时长 ≈ 6 分钟

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储，即通过数据元素物理存储的连续性来反应元素之间逻辑上的相邻关系。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
#include <stdio.h>
#include <malloc.h>
#include <assert.h>//断言————如果条件返回错误，则终止程序执行

#define SEQLIST_INT_SIZE 8//初始化顺序表大小为存放8个元素
typedef int ElemType;//定义元素类型为int型，即为存放整型数据的顺序表

/*给出顺序表结构*/
typedef struct SeqList
{
	ElemType *base;//指针base指向一个真实开辟的顺序表空间
	int capacity;//顺序表的空间容量大小
	int size;//顺序表中的实际存放元素的个数(顺序表的长度)
}SeqList;//SeqList为结构体变量

/*初始化顺序表*/
void InitSeqList(SeqList *list)//给出顺序表的位置
{
	list->base=(ElemType *)malloc(sizeof(ElemType)*SEQLIST_INT_SIZE);//为顺序表开辟空间，指针base指向开辟的空间
	assert(list->base !=NULL);//判断空间是否开辟成功
	list->capacity=SEQLIST_INT_SIZE;//初始化顺序表的容量大小(可以存放8个元素)
	list->size=0;//定义顺序表的实际存放元素的个数为0(此时size是当前数组下标为0的地址)
}

/*尾部插入*/
//先判断空间是否已满
void push_back(SeqList *list,ElemType x)//给出顺序表的位置和要插入的元素
{
	if(list->size  >=  list->capacity)//顺序表的实际存放元素的个数大于等于顺序表的开辟容量
	{
		printf("顺序表空间已满\n");
		return;
	}
	list->base[list->size]=x;//插入元素的位置是当前size指向的位置(即当前下标的位置)
	list->size++;//插入元素后，顺序表的实际存放元素的个数加一
}

/*显示顺序表*/
void show_list(SeqList *list)
{
	for(int i=0;i<list->size;++i)//循环顺序表的长度
	{
		printf("%d",list->base[i]);//指针base取出下标为i的元素
	}
    printf("\n");
}

/*头部插入*/
//先判断空间是否已满
void push_front(SeqList *list,ElemType x)
{
	if(list->size  >=  list->capacity)//顺序表的实际存放元素的个数大于等于顺序表的开辟容量
	{
		printf("顺序表空间已满，不能头部插入数据\n");
		return;
	}
	for(int i=list->size;i>0;--i)//循环实现插入新元素前，包括0下标以后的所有元素均后移
	{
	list->base[i]=list->base[i-1];//把下标为i-1的元素放在下标为i的位置上(后移)	
	}
	list->base[0]=x;//此时0下标空出，把新插入的元素放在顺序表的0下标位置上
	list->size++;//插入元素后，顺序表的长度加一
}

/*尾删*/
//先判断空间是否为空
void pop_back(SeqList *list)
{
	if(list->size==0)
	{
		printf("顺序表已空，不能尾部删除数据");
		return;
	}
    list->size--;//顺序表的实际元素的个数减一，即有效数据减少一个，实现尾删
}

/*头删*/
//先判断空间是否为空
void pop_front(SeqList *list)
{
	if(list->size==0)
	{
		printf("顺序表已空，不能头部删除数据");
		return;
	}
	for(int i=0;i<list->size-1;++i)//除0下标存放的元素不动，其他所有元素依次向前移动，共移动size-1次
	{
	list->base[i]=list->base[i+1];//把下标为i+1的元素放在下标为i的位置上
	}
    list->size--;//删除元素后，顺序表的长度减一
}

/*按位置插入*/
void insert_pos(SeqList *list,int pos,ElemType x)//给出顺序表的位置，插入元素的位置，插入元素
{
	if(pos<0 || pos>list->size)//插入位置小于0或大于当前位置
//(假如顺序表中此时有4个元素，size=4，如果在下标为4的位置插入，实际上此时顺序表下标才为3，可以插入也就是尾插)
	{
		printf("插入的位置非法\n");
		return;
	}
	for(int i=list->size;i>pos;--i)//i是当前在顺序表的位置，i如果大于要插入的位置，i就减一
	{
		list->base[i]=list->base[i-1];//把下标为i-1的元素放在下标为i的位置上(后移)
	}
	list->base[pos]=x;//包括pos位置在内，pos及之后的元素都向后移动，直到i=pos时(此时循环结束)，插入新元素
	list->size++;//插入元素后，顺序表的实际元素的个数加一
}

/*按位置查找*/
int find(SeqList *list,ElemType x)//给出顺序表的位置，查找的元素
{
	for(int i=0;i<list->size;++i)//遍历顺序表
	{
		if(list->base[i]==x)//查找的元素等于表中下标为i的元素
			return i;//返回下标
	}
	return -1;//否则返回-1
}

/*顺序表长度*/
int length(SeqList *list)
{
	return list->size;//返回顺序表的长度
}

/*按位置删除*/
void delete_pos(SeqList *list,int pos)
{
		if(pos<0 || pos>=list->size)//插入位置小于0或大于等于当前位置
//(假如顺序表中此时有4个元素，size=4，如果在下标为4的位置删除，实际上此时顺序表下标才为3，所以删不到)
	{
		printf("插入的位置非法\n");
		return;
	}
		for(int i=pos;i<list->size-1;++i)//pos下标之前(包括pos)存放的元素不动，pos之后的元素依次向前移动，共移动size-pos-1次
	{
		list->base[i]=list->base[i+1];//把下标为i+1的元素放在下标为i的位置上(前移)
	}
		list->size--;
}

/*按值删除*/
void dele_val(SeqList *list,ElemType x)//给出顺序表的位置，删除的元素
{
	int pos=find(list,x);
	if(pos==-1)
	{
		printf("要删除的数据不存在\n");
		return;
	}
	delete_pos(list,pos);
}

/*冒泡排序*/
void sort(SeqList *list)
{
	for(int i=0;i<list->size-1;++i)//size-1相当于下标
	{
		for(int j=0;j<list->size-i-1;++j)
//第0趟比较,j保证了循环到下标为size-1的元素,即最后一个元素
//第1趟比较,j保证了循环到下标为size-2的元素(最后一个元素沉底，不再进行比较)
//第2趟比较,j保证了循环到下标为size-3的元素
//第3趟比较,j保证了循环到下标为size-4的元素
//........
//第i趟比较,j保证了循环到下标为size-i-1的元素
		{
			if(list->base[j]>list->base[j+1])//相邻元素交换
			{
			ElemType t=	list->base[j];
			list->base[j]=list->base[j+1];
			list->base[j+1]=t;
			}
		}
	}
}

/*清除顺序表中的数据*/
void clear(SeqList *list)
{
	list->size=0;//顺序表的长度置为0
}

/*摧毁顺序表*/
void destory(SeqList *list)
{
	free(list->base);//把指针base所指的顺序表空间释放掉
	list->base=NULL;//把指针base初始化,预防野指针
	list->capacity=0;//顺序表的容量大小为0
	list->size=0;//顺序表的实际存放元素的个数为0
}


void main()
{
	SeqList mylist;//定义一个名为mylist的顺序表
	InitSeqList(&mylist);//初始化mylist顺序表，&为地址传递
	ElemType item;//定义插入的元素
	int pos;//定义插入的位置
	int select=1;
	while(select)
	{
		printf("***************************************************\n");
		printf("* [1]push_back(尾插)         [2]push_front(头插)  *\n");
		printf("* [3]show_list(显示)         [4]pop_back(尾删)    *\n");
		printf("* [5]pop_front(头删)         [6]insert_pos(随插)  *\n");
		printf("* [7]find(查找)              [8]length(求长度)    *\n");
		printf("* [9]delete_pos(按位置删)    [10]dele_val(按值删) *\n");
		printf("* [11]sort(排序)             [12]clear(清除)      *\n");
		printf("* [13]destory(销毁)          [0]quit(退出系统)    *\n");
		printf("***************************************************\n");
		printf("请选择:");
		scanf("%d",&select);
		if(select==0)
		break;//退出系统
		
		switch(select)
		{
		case 1:
			printf("请输入要插入的数据(-1结束):");
			while(scanf("%d",&item),item!=-1)//逗号表达式
			{
			push_back(&mylist,item);
			}break;

		case 2:
			printf("请输入要插入的数据(-1结束):");
			while(scanf("%d",&item),item!=-1)
			{
			push_front(&mylist,item);
			}break;

		case 3:
			show_list(&mylist);
		break;

		case 4:
		pop_back(&mylist);
		break;

		case 5:
		pop_front(&mylist);
		break;

        case 6:
		printf("请输入要插入的数据:");
		scanf("%d",&item);
		printf("请输入要插入的位置:");
		scanf("%d",&pos);
	    insert_pos(&mylist,pos,item);
		break;

		case 7:
		printf("请输入要查找的数据:");
		scanf("%d",&item);
		pos=find(&mylist,item);
		if(pos==-1)
		printf("查找的数据%d不存在\n");
		else
		printf("查找的数据%d在顺序表中的%d下标位置\n",item,pos);
		break;

		case 8:
		printf("顺序表的长度为:%d\n",length(&mylist));
		break;

		case 9:
		printf("请输入要删除的位置:");
		scanf("%d",&pos);
		delete_pos(&mylist,pos);
		break;

		case 10:
		printf("请输入要删除的数据:");
		scanf("%d",&item);
		dele_val(&mylist,item);
		break;

		case 11:
		sort(&mylist);
		break;

		case 12:		
		clear(&mylist);
		break;

		case 13:
		destory(&mylist);
		break;

		default:
		printf("输入的选择错误，请重新输入:\n");
		break;
		}	
	}
}

运行程序：
在这里插入图片描述

发表于
本文字数： 3.4k 阅读时长 ≈ 3 分钟

和顺序栈类似，在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素外，尚需附设两个指针front和rear分别指示队列头元素及队列尾元素的位置。

为了在C语言中描述方便起见，初始化建空队列的时候，令front=rear=0，每次插入新的队列尾元素时，“队尾针增1”；每当删除队列头元素时，“头指针增1”；

因此，在非空队列中，头指针始终指向队列头元素，而队尾指针始终指向队列尾元素的下一个位置，即队尾指针指向的空间是下一个能正常入队的空间，如图：
在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include <stdio.h>
#include <malloc.h>
#include <assert.h>

#define MAXSIZE 8//定义队列初始化存放8个数据元素
typedef int ElmeType;

/*给出顺序队列的结构*/
typedef struct Queue
{
	ElmeType *base;//指针base指向有效的队列空间
	int      front;//队头指针记录队头元素的下标
	int      rear;//队尾指针记录队尾元素的下一个元素的下标
}Queue;

/*初始化顺序队列*/
void InitQueue(Queue *Q)
{
	Q->base=(ElmeType *)malloc(sizeof(ElmeType)*MAXSIZE);//开辟队空间
	assert(Q->base!=NULL);
	Q->front=Q->rear=0;//队头指针和队尾指针都指向队列的0下标,此时队列为空
}

/*入队*/
void EnQueue(Queue *Q,ElmeType x)
{
//入队时,新入队元素是在队尾指针指向当前下标地址进行入队,入队完成后,队尾指针指向下一个下标地址	
	if(Q->rear >= MAXSIZE)//当队尾指针指向的下标与队空间大小相同时,队已满
	return;
	Q->base[Q->rear]=x;
	Q->rear++;
}

/*展示顺序队列元素*/
void ShowQueue(Queue *Q)
{
	printf("顺序队列中存放的元素:");
	for(int i=Q->front;i<Q->rear;++i)
	{
		printf("%d ",Q->base[i]);
	}
	printf("\n");
}

/*出队*/
void DeQueue(Queue *Q)
{
//进队一个元素,队尾指针指向下一个有效的空间(新空间)
//出队一个元素,队头指针指向下一个有效的数据元素
//当某一时刻,出队了一个元素后,队头指针指向下一个(新空间)时,此时说明队头指针和队尾指针都指向队列的同一个下标地址
	if(Q->front==Q->rear)//队列为空
		return;
	Q->front++;
}

/*取队头元素*/
void GetHead(Queue *Q,ElmeType *v)//指针v带回队头元素
{
//要获取队头,前提是队列不空
	if(Q->front==Q->rear)//队列为空
	return;
	*v=Q->base[Q->front];//必须在base所指的空间里取元素
}

/*顺序队列的长度*/
int Length(Queue *Q)
{
	return (Q->rear - Q->front);//下标0开始存放数据,进队后,队尾指针指向下一个有效的新空间
	//队列中元素的个数正好是队尾队头所指的下标之差
	//例如队头指针指向0下标,队尾指针指向3下标,此时队中有3(3-0)个元素,即已存放数据在0,1,2下标中
}

/*清除顺序队列*/
void ClearQueue(Queue *Q)
{
	Q->front=Q->rear=0;//队列置为空
}

/*销毁顺序队列*/
void DestroyQueue(Queue *Q)
{
	free(Q->base);//释放base所指的队列空间
	Q->base=NULL;//预防野指针
}
/**/

void main()
{
	Queue Q;
	ElmeType e;//定义队头元素
	InitQueue(&Q);//&Q是传入队列的地址
	printf("入队\n");
	for(int i=1;i<=5;++i)
	{
		EnQueue(&Q,i);
	}
	ShowQueue(&Q);
	printf("出队列	");
	DeQueue(&Q);
	GetHead(&Q,&e);
	printf("队头元素为:%d\n",e);
	printf("顺序队的长度为:%d\n",Length(&Q));
	printf("\n");
	ShowQueue(&Q);
	printf("出队列	");
	DeQueue(&Q);
	GetHead(&Q,&e);
	printf("队头元素为:%d\n",e);
	printf("顺序队的长度为:%d\n",Length(&Q));
	printf("\n");
	ShowQueue(&Q);
	printf("出队列	");
	DeQueue(&Q);
	GetHead(&Q,&e);
	printf("队头元素为:%d\n",e);
	printf("顺序队的长度为:%d\n",Length(&Q));
	printf("\n");
	ShowQueue(&Q);
	printf("出队列	");
	DeQueue(&Q);
	GetHead(&Q,&e);
	printf("队头元素为:%d\n",e);
	printf("顺序队的长度为:%d\n",Length(&Q));
	printf("\n");
	ShowQueue(&Q);
	printf("出队列	");
	DeQueue(&Q);
	GetHead(&Q,&e);
	printf("队头元素为:%d\n",e);
	printf("顺序队的长度为:%d\n",Length(&Q));
	printf("\n");
	ShowQueue(&Q);
	printf("出队列	");
	DeQueue(&Q);
	GetHead(&Q,&e);
	printf("队头元素为:%d\n",e);
	printf("顺序队的长度为:%d\n",Length(&Q));
	printf("\n");
	ClearQueue(&Q);
	DestroyQueue(&Q);
}

运行结果：
在这里插入图片描述

发表于
本文字数： 8k 阅读时长 ≈ 7 分钟

链表中的数据是以结点来表示的，每个结点的构成：**元素(数据元素的映象) + 指针(指示后继元素存储位置)**，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

●头结点是在链表的开始结点之前附加的一个结点(结点没有有效的数据元素)
●第一个结点（或称首元结点）是链表中存储第一个有效数据元素的结点

在链表这里，小萌新想说一定要把’’指针的指向，谁是谁的前驱结点，谁是谁的后继结点‘’搞清楚，多画图，慢慢领会！

话不多说，把代码敲起来!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
#include <stdio.h>
#include <malloc.h>
#include <assert.h>//断言——如果条件返回错误，则终止程序执行

typedef int ElemType;//定义元素类型为int型，即为存放整型数据的单链表

/*给出结点结构*/
typedef struct ListNode
{
	ElemType data;//数据域
	struct ListNode *next;//指针域(指向下一个结点的地址)
}ListNode,*pNode;//定义结点类型,定义结点的指针类型

/*给出单链表结构*/
typedef struct List
{
	pNode first;//first指向头结点(单链表中有效结点的前一个结点,即头结点)
	pNode last;//last指向最后一个结点(尾结点)
	size_t size;//结点的个数
}List;//定义结构体变量


/*初始化单链表*/
void InitList(List *list)
{
	list->first=list->last=(ListNode*)malloc(sizeof(ListNode));//申请一个结点,同时用指针first和指针last指向这个结点
	assert(list->first!=NULL);//判断申请空间是否为空
	list->first->next=NULL;//头结点的指针域初始化为空(头结点的指针域存放第一个有效结点的地址)
	list->size=0;//初始化有效结点个数为0个
}

/*尾部插入*/
void push_back(List *list,ElemType x)
{
	ListNode *s=(ListNode*)malloc(sizeof(ListNode));//申请一个结点,用指针s指向这个结点(用指针s保存这个结点的地址)
	assert(s!=NULL);//判断是否申请空间成功
	s->data=x;//x存放在新结点的数据域
	s->next=NULL;//新结点的指针域为空
//链接
	list->last->next=s;
//list->last代表最后一个结点,list->last->next代表最后一个结点的指针域,该指针域保存指针s(即保存新结点地址)
	list->last=s;//last指针后移,用last指针代替s指针指向最后一个结点(即新插入的结点)
	list->size++;//插入后,结点数增加
}

/*显示单链表*/
void show_list(List *list)
{
	ListNode *p=list->first->next;//定义指针p指向单链表中的第一个有效结点(注意不是头结点)
	while(p!=NULL)//如果结点不为空
	{
	printf("%d-->",p->data);//打印该结点的数据域
    p=p->next;//p指向下一个结点
	}
	printf("该结点已空\n");
}

/*头部插入*/
void push_front(List *list,ElemType x)
{
	ListNode *s=(ListNode*)malloc(sizeof(ListNode));
	assert(s!=NULL);
	s->data=x;//x存放在新结点的数据域
	s->next=list->first->next;//新结点指针域保存第一个有效结点的地址(本来第一个有效结点的地址是让头结点的next保存的)
	list->first->next=s;//用头结点的指针域保存指针s(即新结点的地址)
	if(list->size==0)//如果此时只有头结点，当插入第一个有效结点时
	{
	list->last=s;//则更改last指针，让其指向第一个有效结点
	}
	list->size++;//插入后,结点数增加
}

/*尾删*/
void pop_back(List *list)
{
	if(list->size==0)//除头结点外，一个有效结点都没有，无法进行删除操作
		return;
	ListNode *p=list->first;//定义一个指针p指向头结点
	while(p->next!=list->last)//当头结点后(即list->first->next)不是尾结点时
	p=p->next;//p指向下一个结点
	free(list->last);//当头结点后是尾结点时,释放尾结点
    list->last=p;//此时指针last指向p指针所指的结点
	list->last->next=NULL;//last结点的指针域置为空
	list->size--;//删除后，结点数减少
}

/*头删*/
void pop_front(List *list)
{
	if(list->size==0)//除头结点外，一个有效结点都没有
		return;
	ListNode *p=list->first->next;//定义一个指针p指向头结点后第一个有效结点
	list->first->next=p->next;//头结点的后继结点是第二个有效结点(即p->next),头结点的指针域保存第二个有效结点的地址
	free(p);//释放p指针所指的结点,实现头删
    if(list->size==1)//如果此时只有头结点和最后一个结点,删除last结点时,需要把last指针指向头结点
	{
	list->last=list->first;
	}
	list->size--;//删除后，结点数减少
}

/*按值插入(从小到大)*/
void insert_val(List *list,ElemType x)
{
	//申请要插入的数据
	ListNode *s=(ListNode*)malloc(sizeof(ListNode));//申请一个结点,用指针s指向这个结点(指针s保存了这个结点的地址)
	assert(s!=NULL);//判断是否申请空间成功
	s->data=x;//x存放在新结点的数据域
	s->next=NULL;//新结点的指针域为空

	ListNode *p=list->first;//定义一个p指针指向头结点
	while(p->next!=NULL && p->next->data < x)//当头结点有后继结点并且后继结点的数据域小于要插入的数值
	p=p->next;//p指向下一个结点
	if(p->next==NULL)//如果头结点后无其他结点
	{
		list->last=s;//把last指针指向新的结点
	}
	s->next=p->next;//否则新结点的指针域保存第一个有效结点的地址(本来第一个有效结点的地址是让头结点的next保存的)
    p->next=s;//头结点的指针域保存新结点的地址,实现插入
    list->size++;
}

/*按值查找*/
ListNode* find(List *list,ElemType x)
{
	ListNode *p=list->first->next;//定义一个指针p指向头结点后第一个有效结点(即头结点的后继)
	while(p!=NULL && p->data!=x)//如果后继结点不为空并且结点的数据域不为要查找的数值
	p=p->next;//则p指向下一个结点
	return p;//返回当前结点的地址
}

/*单链表长度*/
int length(List *list)
{
	return list->size;
}

/*按值删除*/
void dele_val(List *list,ElemType x)
{
	if(list->size==0)//除头结点外，一个有效结点都没有
		return;
	ListNode *p=find(list,x);//定义指针p保存find函数返回的当前结点的地址
	if(p==NULL)//如果结点的地址为空
	{
		printf("要删除的数据不存在\n");
		return;
	}
	if(p==list->last)//如果结点地址正好是尾结点
	{
		pop_back(list);//通过pop函数进行尾部删除
	}
	else//否则
	{
			ListNode *q=p->next;//定义指针q指向当前结点(要删除数据的结点)的后继结点
			p->data=q->data;//用下一个结点的数据域覆盖当前要删除结点的数据域
			p->next=q->next;//删除当前要删除结点的下一个结点(p->next=p->next->next)
			free(q);//释放要删除数据结点的后继结点
			list->size--;
	}
}

/*排序*/
void sort(List *list)
{
	if(list->size==0 || list->size==1)//只有头结点或只有头尾两个结点
		return;
	ListNode *s=list->first->next;//定义一个指针s指向头结点的后继结点
	ListNode *q=s->next;//定义指针q指向s指针指向结点的后继结点
//断开链表
	list->last=s;//last指针指向s
	list->last->next=NULL;//尾结点的指针域为空
//按值插入
	while(q!=NULL)//判断指针q指向s指针指向结点的后继结点是否为空
	{
		s=q;//若不为空,指针s下移结点(指针s指向断开链表后的第一个结点)
		q=q->next;//q指针下移(指针q指向s指向断开链表后的第一个结点的后继)
	ListNode *p=list->first;//定义一个p指针指向头结点
	while(p->next!=NULL && p->next->data < s->data)//当头结点有后继结点并且后继结点的数据域小于断开链表后的第一个结点
	p=p->next;//p指向下一个结点
	if(p->next==NULL)//如果p所指结点的next为空,则此时p指向尾结点,相当于尾插(更改last指针的指向)
	{
		list->last=s;
	}
	s->next=p->next;//否则断开的结点在头结点与第一个有效结点之间比较,若不满足while,则进行插入
	//指针s指向那个断开的结点,断开的结点的指针域保存第一个有效结点的地址
    p->next=s;//头结点的指针域保存断开结点的地址
	//此时断开的结点成为第一个有效结点,实现数据域从小到大排序
	}
}

/*清除单链表中的数据*/
void clear(List *list)
{	
	if(list->size==0)//只有头结点不需要清除
		return;
	ListNode *p=list->first->next;//定义指针p指向第一个有效结点
	while(p!=NULL)
	{
		list->first->next=p->next;//头结点后为第二个有效结点
		free(p);//释放第一个有效结点
		p=list->first->next;//p重新指向第一个有效结点(是刚才的第二个有效结点)
	}
	list->last=list->first;//while完毕后,链表中只剩头结点,将尾指针指向头结点
	list->size=0;//结点个数置为0
}

/*摧毁单链表*/
void destory(List *list)
{
	clear(list);
	free(list->first);//释放头结点
	list->first=list->last=NULL;//预防野指针,都置为空
}

void main()
{
	List mylist;//定义一个名为mylist的单链表,内部有三个成员,均为随机值
	InitList(&mylist);//初始化mylist单链表，&为地址传递
	ElemType item;//定义插入的元素
	ListNode *p=NULL;
	int select=1;
	while(select)
	{
		printf("***************************************************\n");
		printf("* [1]push_back(尾插)         [2]push_front(头插)  *\n");
		printf("* [3]show_list(显示)         [4]pop_back(尾删)    *\n");
		printf("* [5]pop_front(头删)         [6]insert_val(按值插)*\n");
		printf("* [7]find(查找)              [8]length(求长度)    *\n");
		printf("* [9]dele_val(按值删除)      [10]sort(排序)       *\n");
		printf("* [11]clear(清除)            [12]destory(销毁)    *\n");
		printf("* [0]quit(退出系统)                               *\n");
		printf("***************************************************\n");
		printf("请选择:");
		scanf("%d",&select);
		if(select==0)
		break;//退出系统
		
		switch(select)
		{
		case 1:
			printf("请输入要插入的数据(-1结束):");
			while(scanf("%d",&item),item!=-1)//逗号表达式,item!=-1时插入
			{
			push_back(&mylist,item);
			}break;

		case 2:
			printf("请输入要插入的数据(-1结束):");
			while(scanf("%d",&item),item!=-1)
			{
			push_front(&mylist,item);
			}break;

		case 3:
			show_list(&mylist);
		break;

		case 4:
		pop_back(&mylist);
		break;

		case 5:
		pop_front(&mylist);
		break;

        case 6:
		printf("请输入要插入的数据:");
		scanf("%d",&item);
	    insert_val(&mylist,item);
		break;

		case 7:
		printf("请输入要查找的数据:");
		scanf("%d",&item);
	    p=find(&mylist,item);
		if(p==NULL)
		{
			printf("要查找的数据在链表中不存在\n");
		}
		break;

		case 8:
		printf("单链表的长度为:%d\n",length(&mylist));
		break;

		case 9:
		printf("请输入要删除的数据:");
		scanf("%d",&item);
    	dele_val(&mylist,item);
		break;

		case 10:
		sort(&mylist);
		break;

		case 11:		
		clear(&mylist);
		break;

		case 12:
		destory(&mylist);
		break;

		default:
		printf("输入的选择错误，请重新输入:\n");
		break;
		}	
	}
}

运行结果：
在这里插入图片描述

发表于
本文字数： 3.8k 阅读时长 ≈ 3 分钟

队列：只允许在一端进行插入，在另一端进行删除的线性表

链队列：使用链表实现的队列，具有队头指针和队尾指针，指示队列元素所在的位置

链队列特性：
●只能队尾插入元素，在队头删除元素
●先进先出（First In First Out）的线性表，先进入的元素出队，后进入的元素才能出队

队列示意图：
在这里插入图片描述
空链队列：
在这里插入图片描述
链队的入栈操作：
在这里插入图片描述
链队的出栈操作：
在这里插入图片描述
————————纸上得来终觉浅，绝知此事要躬行————————

话不多说，把代码开起来，这样晦涩的概念才不会显得苍白无力！！！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include<stdio.h>
#include<malloc.h>
#include<assert.h>//断言

typedef int ElemType;//定义元素类型为int型

/*链队的结点类型*/
typedef struct QueueNode
{
	ElemType data;
	struct QueueNode *next;
}QueueNode,*PNode;

/*定义链队结构*/
typedef struct LinkQueue
{
	PNode front;//队头指针指向头结点
	PNode tail;//队尾指针
}LinkQueue;

/*初始化链队*/
void InitQueue(LinkQueue *Q)
{
//创建头结点
	QueueNode *s=(QueueNode *)malloc(sizeof(QueueNode));
	assert(s!=NULL);
	Q->front=Q->tail=s;//队头指针和队尾指针都指向新结点
	Q->tail->next=NULL;//队尾结点的指针域置空
}

/*入队*/
void EnQueue(LinkQueue *Q,ElemType x)
{
	//队尾指针的next指向新创建的结点(新结点进行尾插)
	//更改尾指针tail的指向
    QueueNode *s=(QueueNode *)malloc(sizeof(QueueNode));
	assert(s!=NULL);
	s->data=x;
	s->next=NULL;//新结点的指针域为空
	Q->tail->next=s;//尾结点的指针域保存新结点的地址
	Q->tail=s;//尾指针指向新结点
}

/*展示链队元素*/
void ShowQueue(LinkQueue *Q)
{
	 QueueNode *p=Q->front->next;//指针p指向头结点后第一个有效结点
	 printf("Front:>");
	 while(p!=NULL)
	 {
		printf("%d ",p->data);
		p=p->next;//指针p指向下一个有效结点
	 }
	 printf("<:Tail\n");
}

/*出队*/
void DenQueue(LinkQueue *Q)
{
//出队相当于头部删除结点的过程:头结点的next指向第一个有效结点的后继,然后释放第一个有效结点
//注意:如果删除队尾结点,需要将队尾指针tail再次指向头结点
	if(Q->front==Q->tail)//空队列
	return;
	QueueNode *p=Q->front->next;//指针p指向头结点后第一个有效结点
	Q->front->next=p->next;//头结点的指针域保存第二个有效结点的地址
	free(p);//释放第一个有效结点
	if(p==Q->tail)//此时删除最后一个结点(尾结点)
	Q->tail=Q->front;//队尾指针指向头结点
}

/*取链队头元素*/
void GetHead(LinkQueue *Q,ElemType *v)//用指针v带回链队头元素
{
	if(Q->front==Q->tail)//空队列
	return;
	QueueNode *p=Q->front->next;//指针p指向头结点后第一个有效结点
	*v=p->data;//p->data等价于Q->front->next->data
}

/*求链队长度*/
int Length(LinkQueue *Q)
{
	int len=0;//初始化长度为0
	QueueNode *p=Q->front->next;//指针p指向头结点后第一个有效结点
	while(p!=NULL)//只有结点不为空,len增加
	{
		len++;
		p=p->next;
	}
	return len;
}

/*清除链队*/
void ClearQueue(LinkQueue *Q)//除头结点外,对所有结点进行清除
{
	if(Q->front==Q->tail)//如果头指针与尾指针指向相同,则链队为空
	return;//无需清除
	QueueNode *p=Q->front->next;//指针p指向头结点后第一个有效结点
	while(p!=NULL)
	{
		Q->front->next=p->next;//头结点的指针域保存第二个有效结点的地址
		free(p);//释放第一个有效结点
		p=Q->front->next;//指针p重新指向头结点后第一个有效结点
	}
//释放完成后,对尾部指针进行修改
	Q->tail=Q->front;//队尾指针指向头结点
}

/*销毁链队*/
void DestroyQueue(LinkQueue *Q)//清除的前提下释放头结点实现销毁
{
	ClearQueue(Q);
	free(Q->front);//释放头结点
	Q->front=Q->tail=NULL;//队头和队尾指针都赋空,预防野指针
}

void main()
{
	LinkQueue Q;
	ElemType e;//链队头元素
	InitQueue(&Q);
	for(int i=1;i<=10;++i)
	{
		EnQueue(&Q,i);
	}
	ShowQueue(&Q);
	printf("出队\n");
	DenQueue(&Q);
	GetHead(&Q,&e);
	printf("链队头元素为:%d\n",e);
	ShowQueue(&Q);
	printf("链队的长度为:%d\n",Length(&Q));
	printf("\n");
	printf("出队\n");
	DenQueue(&Q);
	GetHead(&Q,&e);
	printf("链队头元素为:%d\n",e);
	ShowQueue(&Q);
	printf("链队的长度为:%d\n",Length(&Q));
	printf("\n");
	printf("出队\n");
	DenQueue(&Q);
	GetHead(&Q,&e);
	printf("链队头元素为:%d\n",e);
	ShowQueue(&Q);
	printf("链队的长度为:%d\n",Length(&Q));
	printf("\n");
	printf("出队\n");
	DenQueue(&Q);
	GetHead(&Q,&e);
	printf("链队头元素为:%d\n",e);
	ShowQueue(&Q);
	printf("链队的长度为:%d\n",Length(&Q));
	printf("\n");
	ClearQueue(&Q);
	DestroyQueue(&Q);
}

运行结果：
在这里插入图片描述