应用题：5个（50分）

  • 1.树和森林的转换
  • 2.最小生成树（prim或Kruskal）
  • 3.哈夫曼树，WPL
  • 4.字典，线性探查法（成功的AVL)
  • 5.折半查找有序表
  • 6.二叉排序树生成
  • 7.恢复二叉树

程序阅读题：2个（20分）

（可能程序设计题的二叉树链表方面，搞几个空给你填）

程序设计题：3个（30分）

  • 1.四个排序考一个
  • 2.二叉树递归建立，非递归遍历或层次遍历，递归找右节点个数
  • 3.顺序表，链表（置逆，删插等）

顺序表and链表

顺序表的就地逆置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
typedef int DataType;
struct List { //顺序表结构
    int Max; //顺序表最大长度
    int n; //线性表长度
    DataType* elem;
};
typedef struct List* SeqList;
typedef struct Node* PNode;
typedef struct Node* LinkList;
/*就地逆置顺序表*/
void Reverse(SeqList list)
{
    int j, temp;
    for (j = 0; j < (list->n / 2); j++)
    {
        temp = list->elem[j];
        list->elem[j] = list->elem[list->n - j - 1];
        list->elem[list->n - j - 1] = temp;
    }
}

链表逆置

1
2
3
4
5
6
7
8
9
10
11
12
13
void Reverse(LinkList H)
{
    PNode p,q;
    p=H->next;
    H->next=NULL;
    while(p)
    {
        q=p;
        p=p->next;
        q->next=H->next;
        H->next=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
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
#include<stdio.h>
#include<stdlib.h>

typedef int DataType; 
struct Node {
    DataType      data; 
    struct Node*  next;  
};
typedef struct Node  *PNode;    
typedef struct Node  *LinkList;   

LinkList CreateList_Tail_loop()
{
    LinkList head = (LinkList)malloc(sizeof(struct Node));
    PNode cur = NULL;
    PNode tail = head;
    DataType data;
    scanf("%d", &data);
    while (data != -1)
    {   
        cur = (struct Node*)malloc(sizeof(struct Node));
        cur->data = data;
        tail->next = cur;
        tail = cur;
        scanf("%d", &data);
    }
    tail->next = head;
    return tail;
}

PNode  Move_Odd_Even(LinkList tail)
{
    PNode last = NULL, p = NULL, pre = NULL, temp = NULL;
    last = tail;
    temp = tail->next;
    pre = last->next;
    p = pre->next;
    while (1)
    {
        if (p == tail)
        {
            break;
        }
        if (p->data % 2 == 0)
        {
            pre->next = p->next;
            p->next = NULL;
            last->next = p;
            last = p;
            p = pre->next;
        }
        else
        {
            pre = p;
            p = p->next;
        }
    }
    if (tail->data % 2 == 0)
    {
        pre->next = p->next;
        p->next = NULL;
        last->next = p;
        last = p;
    }
    last->next = temp;
    tail = last;
    return tail;
}

void print(LinkList tail)    
{
    PNode  head = tail->next;
    PNode p = head->next;
    while (p != head)
    {
        printf("%d ", p->data);
        p = p->next;
    }
}

void DestoryList_Link(LinkList tail)
{
    PNode pre = tail->next;
    PNode p = pre->next;
    while (p != tail)
    {
        free(pre);
        pre = p;
        p = pre->next;
    }
    free(pre);
    free(tail);
}

int main()
{
    LinkList tail = NULL;
    LinkList p = NULL;
    tail = CreateList_Tail_loop();
    p = Move_Odd_Even(tail);
    print(p);
    DestoryList_Link(tail);
    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
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
#include<stdio.h>
#include<stdlib.h>

typedef int DataType;      
struct Node
{
    DataType data;
    struct Node * next;
};
typedef struct Node Node;  
typedef struct Node  *PNode;
typedef struct Node  *LinkList;

PNode createEmptyLinkedList()
{
    PNode current;
    current = (PNode)malloc(sizeof(Node));
    current->next = NULL;
    current->data = -1;
    return current;
}

PNode buildCircularLinkedList(int n, PNode tail)
{
    PNode current=NULL, prev;
    prev = tail; 
    for (int i = 0; i < n; i++)
    {
        current = (PNode)malloc(sizeof(Node));
        current->next = NULL;
        scanf("%d", &current->data);
        prev->next = current;
        prev = current;
    }
    current->next = tail->next;
    tail->next = current;
    return tail;
}

PNode mergeNDeduplicateList(PNode tail1, PNode tail2)
{
    int flag, flag1, flag2;
    flag1 = 1;
    flag2 = 1;
    flag = -1;
    PNode current1, current2, last1, last2, temp;
    temp = (PNode)malloc(sizeof(Node));
    last1 = tail1->next;
    current1 = last1->next;
    last2 = tail2->next;
    current2 = last2->next;
    PNode tail = createEmptyLinkedList();
    PNode prev = tail;
    do
    {
        if (current1->data > current2->data)
        {
            if (current2->data != flag)
            {
                temp = (PNode)malloc(sizeof(Node));
                temp->next = NULL;
                prev->next = temp;
                prev = temp;
                temp->data = current2->data;
                flag1 = 0;
            }
            flag = current2->data;
            current2 = current2->next;
            
        }
        else
        {
            if (current1->data != flag)
            {
                temp = (PNode)malloc(sizeof(Node));
                temp->next = NULL;
                prev->next = temp;
                prev = temp;
                temp->data = current1->data;
                flag2 = 0;
            }
            flag = current1->data;
            current1 = current1->next;
        }
    } while ((current1 != last1->next || flag2 == 1) && (current2 != last2->next || flag1 == 1));
    if (current1 == last1->next)
    {
        while (current2 != last2->next)
        {
            if (current2->data != flag)
            {
                temp = (PNode)malloc(sizeof(Node));
                temp->next = NULL;
                prev->next = temp;
                prev = temp;
                temp->data = current2->data;
            }
            flag = current2->data;
            current2 = current2->next;  
        }
    }
    else if (current2 == last2->next)
    {
        while (current1 != last1->next)
        {
            if (current1->data != flag)
            {
                temp = (PNode)malloc(sizeof(Node));
                temp->next = NULL;
                prev->next = temp;
                prev = temp;
                temp->data = current1->data;
            }
            flag = current1->data;
            current1 = current1->next;
        }
    }
    temp->next = tail->next;
    tail->next = temp;
    return tail;
}

void printCircularLinkedList(PNode tail) 
{
    PNode current, last;
    last = tail->next;
    current = last->next;
    do
    {
        printf("%d ", current->data);
        current = current->next;
    } while (current != last->next);
}

int main()
{
    PNode list1, list2;
    int list1_number, list2_number;
    list1 = createEmptyLinkedList();
    list2 = createEmptyLinkedList();
    scanf("%d", &list1_number);
    buildCircularLinkedList(list1_number, list1);
    scanf("%d", &list2_number);
    buildCircularLinkedList(list2_number, list2);
    list1 = mergeNDeduplicateList(list1, list2);
    printCircularLinkedList(list1);
    return 0;
}

二叉树

二叉树递归建立

image-20211129100057471

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
BinTree CreateBinTree_Recursion()
{ 
    char ch;  BinTree bt;
    scanf_s("%c",&ch);
    if(ch=='@')    bt=NULL;
    else{
	   bt = (BinTreeNode *)malloc(sizeof(BinTreeNode));
	   bt->data = ch;
	   bt->leftchild = CreateBinTree_Recursion ();     
                 //递归构造左子树
	  bt->rightchild = CreateBinTree_Recursion ();    
               //递归构造右子树
          }
     return bt;
}

递归遍历

先序递归遍历

image-20211129100247786

1
2
3
4
5
6
7
8
void PreOrder_Recursion(BinTree bt)     //递归先序遍历
{
	if (bt == NULL) return;                           //如果是空则返回
	printf(“%c”, bt->data);                          //访问数据域
	PreOrder_Recursion(bt->leftchild);  //递归遍历左子树
	PreOrder_Recursion(bt->rightchild);//递归遍历右子树
}

中序递归遍历

image-20211129100327339

1
2
3
4
5
6
7
8
void InOrder_Recursion(BinTree bt) //递归中序遍历
{
	if(bt==NULL) return;                           //如果是空则返回
	InOrder_Recursion(bt->leftchild);    //递归遍历左子树
	printf(“%c”,bt->data);                          //访问数据域
	InOrder_Recursion(bt->rightchild);    //递归遍历右子树
}

后序递归遍历

image-20211129100442069

1
2
3
4
5
6
7
8
void PostOrder_Recursion(BinTree bt)//递归后序遍历
{
	if(bt==NULL) return;                              //如果是空则返回
	PostOrder_Recursion(bt->leftchild); //递归遍历左子树
	PostOrder_Recursion(bt->rightchild);//递归遍历右子树
	printf(“%c”,bt->data);                            //访问数据域
}

非递归遍历

先序非递归遍历1

image-20211129100616914

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void PreOrder_NRecursion1(BinTree bt)
{
    LinkStack lstack; //定义链栈
    lstack = SetNullStack_Link(); //初始化栈
    BinTreeNode *p;
    Push_link(lstack, bt); //根结点入栈
    while (!IsNullStack_link(lstack))
    {
	p = Top_link(lstack);
	Pop_link(lstack);
	printf("%c", p->data);          //访问结点
	if (p->rightchild)
		Push_link(lstack, p->rightchild);
	if (p->leftchild)
		Push_link(lstack, p->leftchild);
    }
}

先序非递归遍历2

image-20211129100710406

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void PreOrder_NRecursion2(BinTree bt) 
{
  LinkStack lstack; //定义链栈
  BinTreeNode *p = bt;
  lstack = SetNullStack_Link(); //初始化栈
  if (bt == NULL) 
      return;
  Push_link(lstack, bt);
  while (!IsNullStack_link(lstack)) 
  {
      p = Top_link(lstack);
      Pop_link(lstack);
      while (p) 
      {
          printf("%c", p->data); //访问结点
          if (p->rightchild)     //若右孩子是空，不用进栈
              Push_link(lstack, p->rightchild);  //右孩子进栈
          p = p->leftchild;
      }
  } 
}

中序非递归遍历

image-20211129100737811

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void InOrder_NRecursion1(BinTree bt)//中序遍历非递归实现
{
	LinkStack lstack; //定义链栈
	lstack = SetNullStack_Link(); //初始化栈
	BinTree p;
	p = bt;
	if (p == NULL) return;
	Push_link(lstack, bt); //根结点入栈
	p = p->leftchild; //进入左子树
	while (p||!IsNullStack_link(lstack))
	{
		while (p != NULL)
		{
			Push_link(lstack, p);
			p = p->leftchild;
		}
		p = Top_link(lstack);
		Pop_link(lstack);
		printf("%c", p->data);  //访问结点
		p = p->rightchild;//右子树非空，扫描右子树
	} 
}

后序非递归遍历

image-20211129100816472

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void PostOrder_NRecursion(BinTree bt){
  BinTree p = bt;
  LinkStack lstack; //定义链栈
  if (bt == NULL) return;
  lstack = SetNullStack_Link(); //初始化栈
  while (p != NULL || !IsNullStack_link(lstack))
  {
      while (p != NULL) 
      {
          Push_link(lstack, p); 
          p = p->leftchild? p->leftchild:p->rightchild;
      }
    p = Top_link(lstack);
    Pop_link(lstack);
    printf("%c", p->data);  //访问结点
    if(!IsNullStack_link(lstack)&&(Top_link(lstack)->leftchild==p))
	p = (Top_link(lstack))->rightchild;  //从左子树退回，进入右子树
    else 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
void LevelOrder(BinTree bt)
{
    LinkQueue q = SetNullQueue_Link();    //初始化队列q
    if (bt == NULL)                       //如果根节点为空
    {
        return;                           //返回
    }
    EnQueue_link(q, bt);                   //入队根节点
    while (!IsNullQueue_Link(q))           //队不空
    {
        BinTreeNode* p = FrontQueue_link(q);    //取队头元素
        DeQueue_link(q);                        //出队
        if (p->data != '@')                     //如果节点不为空
            printf("%c ", p->data);             //打印节点
        if (p->leftchild != NULL)               //如果左孩子不为空
        {
            EnQueue_link(q, p->leftchild);      //左孩子入队
        }
        if (p->rightchild != NULL)              //如果右孩子不为空
        {
            EnQueue_link(q, p->rightchild);     //右孩子入队
        }
    }
}

递归统计二叉树右孩子个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int c=0;                                       //初始化计数
int CountRightNode(BinTree bt)
{
    if(bt!= NULL)
    {
        if(bt->rightchild)                     //若是右孩子
        {
        	c++;                               //计数加一
        }
        CountRightNode(bt->rightchild);        //递归右孩子
        CountRightNode(bt->leftchild);         //递归左孩子
        
    }
       return c;
}

排序

直接插入排序

22

二分插入排序

image-20211129221826794

Shell排序

image-20211129222138902

直接选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void  SelectSort(SortArr* sortArr)
{
	int i, j;
	int minPos; //记录最小元素的下标
	for (i = 0; i < sortArr->cnt - 1; i++) // n-1趟选择排序
	{
		minPos = i; //记录下最小的值所在的数组下标
		for (j = i + 1; j < sortArr->cnt; j++) //在无序区中寻找
		{
			if (sortArr->recordArr[j].key < sortArr->recordArr[minPos].key)
				minPos = j;
		}
		if (minPos != i)  //说明需要交换
			Swap(sortArr, minPos, i); //交换记录
	}
}

堆排序

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
void HeapAdjust(SortArr* sortArr, int father, int size) //调整过程
{
	int lchild; int rchild; int max;
	//将father中的值放到堆中正确的位置上
	while (father < size) {
		lchild = father * 2 + 1;  rchild = lchild + 1;     //左孩子,右孩子
		if (lchild >= size)   break;
		//寻找father,lchild,rchild中最大的，将最大值与father值做交换
		max = lchild;
		//右孩子的下标不要越界了
		if (rchild < size && sortArr->recordArr[rchild].key >sortArr->recordArr[lchild].key)
			max = rchild;
		if (sortArr->recordArr[father].key < sortArr->recordArr[max].key)
			Swap(sortArr, father, max); father = max;
		else  break;
	}
}


void HeapSort(SortArr* sortArr, int size) //堆排序
{
	int i;
	for (i = size / 2 - 1; i >= 0; i--)
		//从倒数第一个非叶子结点开始调整,一致调整到根结点，形成堆
		HeapAdjust(sortArr, i, size);
	//每次取树根元素跟未排序尾部交换，之后，再重新调整堆
	for (i = size - 1; i >= 1; i--)
	{
		Swap(sortArr, 0, i); //交换
		//重新调整一个元素的位置就可以了（刚调整到树根位置的那个值）
		HeapAdjust(sortArr, 0, i);
	}
}

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void BubbleSort(SortArr* sortArr)
{
	int i, j;
	int hasSwap = 0; // 标志，用于检测内循环是否还有数据交换 
	for (i = 1; i < sortArr->cnt; i++)
	{
		hasSwap = 0; //每趟开始重新设置交换标志为0
		//注意j是从后往前循环 ,数组的下标是0到cnt-1
		for (j = sortArr->cnt - 1; j >= i; j--)
		{
			//若前者大于后者
			if (sortArr->recordArr[j - 1].key > sortArr->recordArr[j].key)
			{
				Swap(sortArr, j, j - 1); //交换
				hasSwap = 1; //有交换发生，则设置交换标志为1
			}
		}
		if (!hasSwap) //本趟没有发生交换
			break;
	}
}

快速排序

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
void QuickSort(SortArr* sortArr, int left, int right)
{
	int i, j;
	KeyType temp;
	if (left >= right)
		return;               //只有一个记录无序排序
	i = left;
	j = right;
    //将最左边的元素作为基准
	temp = sortArr->recordArr[i].key;
    //寻找基准应存放的最终位置
	while (i != j)
	{
		while (sortArr->recordArr[j].key >= temp && j > i)    //j从右向左扫描
		{
			j--;
		}
		if (i < j)                                            //如果arr[j]<temp
		{
			sortArr->recordArr[i].key = sortArr->recordArr[j].key;
			i++;
		}
		else
			break;
		while (sortArr->recordArr[i].key <= temp && j > i)    //i从左向右扫描
			i++;
		if (i < j)                                            //如果arr[i]>temp
		{
			sortArr->recordArr[j].key = sortArr->recordArr[i].key;
			j--;
		}
		else
			break;
	}
    //找到基准需要存放的位置，此时该位置左边的值都比基准小，右边的值都比基准大
	sortArr->recordArr[i].key = temp;
	QuickSort(sortArr, left, i - 1);                //递归左区间
	QuickSort(sortArr, i + 1, right);               //递归右区间
}