【C++数据结构面试题】

链表

特殊线性表，它并不是按线性顺序存储数据的线性表，它在每个节点里面包含了下一个节点的指针，来记录下一个节点的位置。
链表节点结构： 数据+next指针

【题1】 链表和数组有什么区别
链表和指针有以下几点不同：
1）存储形式
数组是一块连续的空间，声明时就要确定长度。链表是一块可不连续的动态空间，长度可变，每个节点要保存相邻节点指针。
2）数据查找
数组的线性查找速度快，查找操作直接使用偏移地址。链表需要按顺序检索节点，效率低。
3）数据插入和删除
链表可以快速插入和删除节点，而数组则可能需要大量数据移动。
4）越界问题
链表不存在越界问题，数组有越界问题。
说明：在选择数组或链表数据结构体时，一定要根据实际需要进行选择。数组便于查询，链表便于插入删除。数组节省空间但是长度是固定的，链表虽然变长但是占了更多的存储空间。

【题2】寻找单链表中间节点
如果是个双链表，可以首位并行，利用两个指针一个从头到尾，一个从尾到头，当两个指针相遇时就找到了中间元素。
受此启发可以想到单链表也可以用双指针来实现中间节点的快速查找：
1）有两个指针同时从头开始遍历
2）一个快指针一次走两步，一个慢指针一次走一步
3）快指针先到链表尾部，而慢指针应该则恰好到达链表的中部
注意：快指针到链表尾部时，当链表长度为奇数时，慢指针指向的即是链表中间指针。当链表长度为偶数时，慢指针指向的节点和慢指针指向的节点的下个节点都是链表的中间节点。

typedef struct NODE
{
	int a;
	struct node *next;
}NODE;
NODE* middle(lnode *head)
{
	NODE *fast,*slow,*p;
	if(head == NULL)
	{
		return NULL;
	}
	fast = slow = head;  //慢指针、快指针同时指向链表首节点
	while(!(p=fast->next)&&!p->next) //循环，直到快指针下个节点或下下个节点为空
	{
		slow = slow->next; //慢指针走一步
		fast = p->next;    //快指针走两步
	}
	return slow;  //f返回中间节点
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

【题3】怎么把一个单链表反序

单循环链表

双向链表

栈和队列

【题9】简述队列和栈的异同
队列和栈都是线性存储结构，但是两者的插入和删除数据的操作不同，队列是“先进先出”，栈是“后进先出”。
注意：区别栈区和堆区
堆区的存取是“顺序随意”，而栈区是“后进先出”。栈由编译器自动分配释放，存放函数的参数值、局部变量等。其操作方法类似于数据结构中的栈。堆一般由程序员分配释放，若程序员不释放，程序结束时可能由OS回收。分配方式类似于链表。
它与本体的堆和栈是两回事。堆栈只是一种数据结构，而堆区和栈区是程序的不同内存存储区域。

【题10】建立一个链式栈
涉及：栈、指针、结构体

//首先创建一个节点结构体
typedef struct node
{
	int data;
	node *next;
}node,*LinkStack;

//创建空栈
void CreateNullStack(S)
{
	LinkStack S = (LinkStack)malloc(sizeof(node));
	S->data = 0;
	S->next = NULL;
}
void Push(LinkStack &S, int data)
{
	LinkStack p = (LinkStack)malloc(sizeof(node));
	p->data = data;
	S->next = p;
}
void Pop(LinkStack &S)
{
	LinkStack p = S->next;
	S->next = S->next->next;
	//栈顶指针下移
	free(p);
	//释放栈顶节点
	p = NULL;
}

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

【题11】建立一个链式队列

//节点结构体
typedef struct node
{
	int data;
	node *next;
}node,*LinkQueue;
//构建一个由队首、队尾节点及队列长度构成的**队列结构体**
typedef struct Queue
{
	LinkQueue head;  //队首指针
	LinkQueue tail;  //队尾指针
	int size;	
}Queue,*pQueue;

//创建一个空队列
pQueue CreateNullQueue(pQueue &Q)
{
	Q = (pQueue)malloc(sizeof(Queue)); //申请一个队列
	if(NULL == Q->head)
	{
		printf("Fail to malloc the head of Queue!\n");
		return NULL;
	}
	Q->head = (LinkQueue)malloc(sizeof(node)); //申请队首节点
	if(NULL == Q->head)
	{
		printf("Fail to malloc the head of Queue！\n");
		return NULL;
	}
	Q->tail = (LinkQueue)malloc(sizeof(node)); //申请队尾节点
	if(NULL == Q->tail)
	{
		printf("Fail to malloc the head of Queue!\n");
		return NULL;
	}
	Q->head->next = Q->tail;  //队列初始化
	Q->tail->next = NULL;
	Q->head->data = 0;
	Q->tail->data = 0l
	Q->size = 0;
	return Q;
}

//队列插入函数
pQueue Push(pQueue &Q, int data)
{

}

//队列删除函数
node Pop(pQueue& Q)
{


} 

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

二叉树

【题13】建立一个二叉树
编程实现二叉树的创建，二叉树的先序、中序和后序遍历。
二叉树
数据结构
指针
树的每个节点应该包含三个元素：数据元素、左孩子指针元素、右孩子指针元素。

typedef struct BiTNode
{

}
1
2
3
4