数据结构之链表和二叉树前言题目1题目2题目3题目4

148 阅读 0 评论 98 点赞

我是靠谱客的博主大意寒风，这篇文章主要介绍数据结构之链表和二叉树前言题目1题目2题目3题目4，现在分享给大家，希望可以做个参考。

前言

这是之前学习《数据结构》时做过的几个小题目，现整理到这里。

题目1

统计出单链表 HL 中结点的值等于给定值 X 的结点数

复制代码

//定义线性表的单链表存储结构
typedef struct Node
{
ElemType data;
struct Node *next;
}Node,*LinkList;
//单链表初始化
LinkList LinkListInit()
{
LinkList L;
L = (Node *)malloc(sizeof(Node));
if (L == NULL)
cout << "申请内存空间失败！";
L->next = NULL;
L->data = 0;
return L;
}
//用头插法建立单链表

LinkList LinkListCreatHead()
{
Node *L;
L = (Node *)malloc(sizeof(Node));
//申请头结点空间

L->next = NULL;
//初始化一个空链表

ElemType x;
//x为链表数据域中的数据

while (cin >> x)
{
Node *p;
p = (Node *)malloc(sizeof(Node)); //申请新的结点

p->data = x;
//结点数据域赋值

p->next = L->next;
//将结点插入到表头L-->|2|-->|1|-->NULL

L->next = p;
}
return L;
}
//统计单链表 L 中结点的值等于给定值 X 的结点数
int Count_X(Node *L, ElemType X)
{
Node *p;
int count = 0;
if (L == NULL)
return 0;
p = L->next;
while (p != NULL)
{
if (p->data == X)
++count;
p = p->next;
}
return count;
}
//主函数
int _tmain(int argc, _TCHAR* argv[])
{
LinkList L;
cout << "Input the list you want： " << endl;
L = LinkListCreatHead();//建立链表
int x;
cout << "Input the number you want check: ";
cin.clear();
cin.sync();
cin >> x;
int count = 0;
count = Count_X(L, x);
cout << "The number of the figures equal to x is :" << count << endl;
return 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
//定义线性表的单链表存储结构
typedef struct Node
{
ElemType data;
struct Node *next;
}Node,*LinkList;
//单链表初始化
LinkList LinkListInit()
{
LinkList L;
L = (Node *)malloc(sizeof(Node));
if (L == NULL)
cout << "申请内存空间失败！";
L->next = NULL;
L->data = 0;
return L;
}
//用头插法建立单链表

LinkList LinkListCreatHead()
{
Node *L;
L = (Node *)malloc(sizeof(Node));
//申请头结点空间

L->next = NULL;
//初始化一个空链表

ElemType x;
//x为链表数据域中的数据

while (cin >> x)
{
Node *p;
p = (Node *)malloc(sizeof(Node)); //申请新的结点

p->data = x;
//结点数据域赋值

p->next = L->next;
//将结点插入到表头L-->|2|-->|1|-->NULL

L->next = p;
}
return L;
}
//统计单链表 L 中结点的值等于给定值 X 的结点数
int Count_X(Node *L, ElemType X)
{
Node *p;
int count = 0;
if (L == NULL)
return 0;
p = L->next;
while (p != NULL)
{
if (p->data == X)
++count;
p = p->next;
}
return count;
}
//主函数
int _tmain(int argc, _TCHAR* argv[])
{
LinkList L;
cout << "Input the list you want： " << endl;
L = LinkListCreatHead();//建立链表
int x;
cout << "Input the number you want check: ";
cin.clear();
cin.sync();
cin >> x;
int count = 0;
count = Count_X(L, x);
cout << "The number of the figures equal to x is :" << count << endl;
return 0;
}

测试
创建线性表[1,2,3,4,5,2,2,56,9]，统计线性表中2的个数。
运行结果为：

题目2

设计两个有序单链表的合并排序算法

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//采用递归的方法实现

Node *ListMerge1(Node *head1, Node *head2)
{
if (head1 == NULL)
return head2;
if (head2 == NULL)
return head1;
Node *head = NULL;
if (head1->value < head2->value)
{
head = head1;
head->next = ListMerge1(head1->next, head2);
}
else
{
head = head2;
head->next = ListMerge1(head1, head2->next);
}
return head;
}

题目3

设计求结点在二叉排序树中层次的算法

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int lev=0;
typedef struct node
{
int value;
struct node *lchild,*rchild;
}bitree;
void level(bitree *bt,int x)
{
if (bt!=0)
{
lev++;
if (bt->value==x)
return;
else if (bt->value>x)
level(bt->lchild,x);
else
level(bt->rchild,x);
}
}

题目4

求以下二叉树的后序遍历

后序遍历规则：若数为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。
所以后序遍历顺序为：F E G K J I H D C B A

复制代码

1
2
3
4
5
6
7
8
9
//二叉树的后序遍历递归算法
void PostOderTraverse(BiTree T)
{
if(T==NULL)
return;
PostOderTraverse(T->lchild); //先后序遍历左子树
PostOderTraverse(T->rchild); //再后序遍历右子树
printf("%c",T->data); //显示结点数据，可以更改为其他对结点的操作
}