# **資料結構實習**
###### tags: `資結`
### 1.聖誕樹(week1)
Description
輸入n
輸出聖誕樹
Input:
n
n>3
Output:
由 * 組成聖誕樹
樹葉部分: (高 : n，寬 : n*2-1)
樹幹部分 : 3 *3
樹葉和樹幹中間要對齊
### 2.二元搜尋(week2)
Description
我們可以先設定搜索範圍，每次都用這範圍最中間的元素來與要查找的目標元素比大小，如果要查找的目標元素比較大，表示如果目標元素存在於該序列中的話，其一定是位在目前範圍的後半段(值大的那段)；反之，如果要查找的目標元素比較小，表示如果目標元素存在於該序列中的話，其一定是位在目前範圍的前半段(值小的那段)。在下次搜尋的時候，也是一樣拿目標元素與前半段或是後半段的正中央元素進行比較，如此反覆動作，直到找出相同的元素為止；或者直到查找範圍只有一個元素時，表示要找的元素並不存在於序列中。
當總數為偶數，中間值有2種，則以第一個為主。例如:有10個數字，無法取中間值 ，有兩個4或5，我們設定為第一個4
本題需以C語言解題並且使用遞迴 未使用者0分計算
Input:
首先輸入陣列大小
輸入一個排序好的數字陣列
並且輸入一個數字當作搜尋目標
Output:
將每一輪的頭尾以及中間值印出來
第一排為陣列位置
第二排為實際數字
如最後找到數字，則印出他所在的陣列位置
```c=
#include<stdio.h>
int correct;
void reuse(int max,int min,int* number){
int med=(max+min)/2;
if(number[med]==correct){
printf("%d %d %d\n%d %d %d\n",min,med,max,number[min],number[med],number[max]);
printf("%d",med);
}
else if(number[med]<correct){
printf("%d %d %d\n%d %d %d\n",min,med,max,number[min],number[med],number[max]);
reuse(max,med+1,number);
}
else if(number[med]>correct){
printf("%d %d %d\n%d %d %d\n",min,med,max,number[min],number[med],number[max]);
reuse(med-1,min,number);
}
}
int main(void) {
int num,i,j;
scanf("%d",&num);
int number[num];
for(i=0;i<num;i++){
scanf("%d",&number[i]);
}
int min=0,max=num-1;
int med;
scanf("%d",&correct);
reuse(num-1,0,number);
}
```
### 3. 稀疏矩陣相乘(week4)
Description
如果在矩陣中，多數的元素並沒有資料，稱此矩陣為稀疏矩陣（sparse matrix），由於矩陣在程式中常使用二維陣列表示，二維陣列的大小與使用的記憶體空間成正比，如果多數的元素沒有資料，則會造成記憶體空間的浪費，為此，必須設計稀疏矩陣的陣列儲存方式，利用較少的記憶體空間儲存完整的矩陣資訊。
請輸入2個稀疏矩陣來進行相乘 最後得到新的矩陣並將其印出來
Input：
請第一行輸入3個數字 分別為A矩陣的列數、行數與非零元素個數，再來依序輸入非零元素的列索引、行索引與值，輸入完A矩陣後再來輸入B矩陣輸入3個數字 分別為B矩陣的列數、行數與非零元素個數，再來依序輸入非零元素的列索引、行索引與值
Output：
輸出第一行 為相乘後的列數、行數與非零元素個數
```c=
#include<stdio.h>
int main(void) {
int arow=0,acol=0,p1=0; //arow acol為矩陣大小，p1非零元素有幾個
scanf("%d %d %d",&arow,&acol,&p1);
int arr1[arow][acol]; //待歸零的變數矩陣
int i,j;
memset(arr1,0,sizeof(arr1)); //歸零
int a,b,num; //填入的行列
for(i=0;i<p1;i++){ //arr1的矩陣填入
scanf("%d %d %d",&a,&b,&num);
arr1[a][b]=num;
}
int brow=0,bcol=0,p2=0;
scanf("%d %d %d",&brow,&bcol,&p2);
int arr2[brow][bcol];
memset(arr2,0,sizeof(arr2)); //歸零
for(i=0;i<p2;i++){
scanf("%d %d %d",&a,&b,&num);
arr2[a][b]=num;
}
int ans[arow][bcol],MID=acol,k;
memset(ans,0,sizeof(ans)); //答案歸零
num=0;
for(i=0;i<arow;i++){ //相乘
for(j=0;j<bcol;j++){
int sum=0;
for(k=0;k<MID;k++){
sum=sum+(arr1[i][k]*arr2[k][j]);
}
ans[i][j]=sum; //填入數字
if(ans[i][j]!=0){ //計算有幾個非0數字
num++;
}
}
}
printf("%d %d %d\n",arow,bcol,num); //印出答案格式
for(i=0;i<arow;i++){
for(j=0;j<bcol;j++){
if(ans[i][j]!=0){
printf("%d %d %d\n",i,j,ans[i][j]);
}
}
}
}
```
### 4.河內塔(week5)
Description
河內塔是由法國數學家盧卡斯引進的數學謎題：在 3 根桿子中，有 1 桿上有 N 個從下數起由大而小的穿孔圓盤。在每次只能移動一個圓盤，且大盤不能疊在小盤之上的規則之下，你需要以最少的次數將這 N 個圓盤全部移到另一根桿子上。
本題目須將盤子由左(Tower1)移至右(Tower3)並使用課堂所學的stack來完成請學生將自己stack的程式碼(加入新項目及刪除項目)說明清楚是在那個地方,如沒有加入項目及刪除項目功能者則視為0分,沒有註解這兩個功能在那也算0分.
Input:
請輸入盤子數量
Output:
將每次盤子移動後 將三個塔所擁有的盤子印出來
Tower1:
Tower2:
Tower3:
```c=
#include<stdio.h>
void hanoi(int,int*,int*,int*);
void push(int*);
void pop(int*);
int towerA[20]={},towerB[20]={},towerC[20]={}; //每座塔含的數字
int moved=0,move_num;
int input_number=0;
void pop(int *tower_out){
for(int i=input_number-1;i>=0;i--){
if(tower_out[i]!=0){
move_num=tower_out[i];
tower_out[i]=0;
break;
}
}
}
void push(int *tower_in){
for(int i=0;i<input_number;i++){
if(tower_in[i]==0){
tower_in[i]=move_num;
break;
}
}
}
void print_tower(){
printf("\nTower1:");
for(int i=0;i<input_number;i++){
if(towerA[i]!=0){
printf("%d",towerA[i]);
if(towerA[i+1]!=0){
printf(" ");
}
}
}
printf("\n");
printf("Tower2:");
for(int i=0;i<input_number;i++){
if(towerB[i]!=0){
printf("%d",towerB[i]);
if(towerB[i+1]!=0){
printf(" ");
}
}
}
printf("\n");
printf("Tower3:");
for(int i=0;i<input_number;i++){
if(towerC[i]!=0){
printf("%d",towerC[i]);
if(towerC[i+1]!=0){
printf(" ");
}
}
}
printf("\n");
}
void hanoi(int n,int *tower_out,int *tower_in,int *temp) {
if(n == 1) {
pop(tower_out);
push(tower_in);
print_tower();
moved++;
}
else {
hanoi(n-1,tower_out,temp,tower_in);
hanoi(1,tower_out,tower_in,temp);
hanoi(n-1,temp,tower_in,tower_out);
}
}
int main() {
int n;
scanf("%d", &n);
input_number=n;
for(int i=n;i>0;i--){
towerA[n-i]=i;
}
printf("Tower1:");
for(int i=0;i<input_number;i++){
if(towerA[i]!=0){
printf("%d",towerA[i]);
if(i!=input_number-1){
printf(" ");
}
}
}
printf("\n");
printf("Tower2:");
for(int i=0;i<input_number;i++){
if(towerB[i]!=0){
printf("%d",towerB[i]);
if(i!=input_number-1){
printf(" ");
}
}
}
printf("\n");
printf("Tower3:");
for(int i=0;i<input_number;i++){
if(towerC[i]!=0){
printf("%d",towerC[i]);
if(i!=input_number-1){
printf(" ");
}
}
}
printf("\n");
hanoi(n,towerA,towerC,towerB);
}
```
### 5.解迷宮(week6)
Description
輸入一個有解的迷宮 迷宮外圍是牆壁
迷宮由1和0組成
1為牆壁不可通過
0為道路
迷宮被牆壁圍住
起點為右上角(1, 1)
終點為右下角(R-2,C-2)
輸出從起點到終點的解法
可以使用的移動方向為八個方位
D0 : R -1 C 0 向上
D1 : R -1 C 1 向右上
D2 : R 0 C 1 向右
D3 : R 1 C 1 向右下
D4 : R 1 C 0 向下
D5 : R 1 C -1 向左下
D6 : R 0 C -1 向左
D7 : R -1 C -1 向左上
Input:
1.先輸入迷宮大小 大小限制 3<=R,C <=9
5 5
2.輸入迷宮內容
11111
10111
11011
11101
11111
Output:
最後到終點時移動方向為 *
RO CO DO中間空一格空格
R1 C1 D3 (起點開始移動)
R2 C2 D3
R3 C3 D* (到達終點不移動)
```c=
#include<stdio.h>
#include<stdbool.h>
int R,C; //整個迷宮的大小
int now_r,now_c; //現在的位置
int stack_len=0; //stack的長度
typedef struct{
int r; //row位置
int c; //col的位置
int dir; //走的方向
struct LinkNode *next; //指向下一個
}LinkNode;
void delete(LinkNode *obj,int rr,int cc){ //把stack pop出去死路的部分
stack_len--; //先減
for(int i=0;i<stack_len;i++){ //找到位置
obj=obj->next;
}
if(obj->r==rr && obj->c==cc){ //free掉
free(obj);
}
}
void add_stack(LinkNode *obj,LinkNode *move_top,int road[R][C]){ //相當於push 進 stack
int i,j; //變數
now_r=move_top->r; //先把現在的位置更新
now_c=move_top->c;
for(i=0;i<8;i++){ //找8個方位
LinkNode *new=(LinkNode*)malloc(sizeof(LinkNode)); //創建一個新的new的stack裝新的位置
if(road[now_r-1][now_c]==0 && (move_top->r!=now_r-1 && move_top->c!=now_c)){ //如果位置是0，且不是最後一個位置
new->r=now_r-1; //換座標
new->c=now_c;
new->dir=0; //N-->0
road[new->r][new->c]=2; //設定走過的為2
move_top->next=new; //把new裝上去
move_top=move_top->next; //後移一格就為new
if((now_r-1==R-2) && (now_c==C-2)){ //如果等於最後就停止遞迴
return 0;
}
return add_stack(obj,move_top,road); //重複做
}
else if(road[now_r-1][now_c+1]==0 && (move_top->r!=now_r-1 && move_top->c!=now_c+1)){
new->r=now_r-1;
new->c=now_c+1;
new->dir=1; // NE-->1
road[new->r][new->c]=2;
move_top->next=new;
move_top=move_top->next;
stack_len++;
if((now_r-1==R-2) && (now_c+1==C-2)){
return 0;
}
return add_stack(obj,move_top,road);
}
else if(road[now_r][now_c+1]==0 && move_top->c!=now_c+1){
new->r=now_r;
new->c=now_c+1;
new->dir=2; //E-->2
road[new->r][new->c]=2;
move_top->next=new;
move_top=move_top->next;
stack_len++;
if((now_r==R-2) && (now_c+1==C-2)){
return 0;
}
return add_stack(obj,move_top,road);
}
else if(road[now_r+1][now_c+1]==0 && (move_top->r!=now_r+1 && move_top->c!=now_c+1)){
new->r=now_r+1;
new->c=now_c+1;
new->dir=3; //SE-->3
road[new->r][new->c]=2;
move_top->next=new;
move_top=move_top->next;
stack_len++;
if((now_r+1==R-2) && (now_c+1==C-2)){
return 0;
}
return add_stack(obj,move_top,road);
}
else if(road[now_r+1][now_c]==0 && move_top->r!=now_r+1){
new->r=now_r+1;
new->c=now_c;
new->dir=4; //S-->4
road[new->r][new->c]=2;
move_top->next=new;
move_top=move_top->next;
stack_len++;
if((now_r+1==R-2) && (now_c==C-2)){
return 0;
}
return add_stack(obj,move_top,road);
}
else if(road[now_r+1][now_c-1]==0 && (move_top->r!=now_r+1 && move_top->c!=now_c-1)){
new->r=now_r+1;
new->c=now_c-1;
new->dir=5; //SW-->5
road[new->r][new->c]=2;
move_top->next=new;
move_top=move_top->next;
stack_len++;
if((now_r+1==R-2) && (now_c-1==C-2)){
return 0;
}
return add_stack(obj,move_top,road);
}
else if(road[now_r][now_c-1]==0 && move_top->c!=now_c-1){
new->r=now_r;
new->c=now_c-1;
new->dir=6; //W-->6
road[new->r][new->c]=2;
move_top->next=new;
move_top=move_top->next;
stack_len++;
if((now_r==R-2) && (now_c-1==C-2)){
return 0;
}
return add_stack(obj,move_top,road);
}
else if(road[now_r-1][now_c-1]==0 && (move_top->r!=now_r-1 && move_top->c!=now_c-1)){
new->r=now_r-1;
new->c=now_c-1;
new->dir=7; //NW-->7
road[new->r][new->c]=2;
move_top->next=new;
move_top=move_top->next;
stack_len++;
if((now_r-1==R-2) && (now_c-1==C-2)){
return 0;
}
return add_stack(obj,move_top,road);
}
else{
road[now_r][now_c]=1; //如果是錯的路-->變成牆壁
delete(obj,now_r,now_c); //刪除
move_top=obj;
for(int i=0;i<stack_len;i++){ //找到目前的位置
move_top=move_top->next;
}
return add_stack(obj,move_top,road); //回傳
}
}
}
int main(void) {
int i,j,n; //變數
scanf("%d",&R); //讀取大小
scanf("%d",&C);
int road[R][C]; //建立
for(i=0;i<R;i++){ //讀取迷宮
scanf("%d",&n);
for(j=C-1;j>=0;j--){
road[i][j]=n%10;
n/=10;
}
}
LinkNode *obj=(LinkNode*)malloc(sizeof(LinkNode)); //頭
LinkNode *move_top=(LinkNode*)malloc(sizeof(LinkNode)); //變動的
obj->r=1; //第一個
obj->c=1;
obj->dir=-1;
move_top=obj; //先指到頭，慢慢往後動
add_stack(obj,move_top,road); //呼叫函式
for(i=0;i<stack_len;i++){ //依序印出
printf("R%d C%d",obj->r,obj->c);
obj=obj->next;
printf(" D%d\n",obj->dir);
}
printf("R%d C%d D*",obj->r,obj->c);
}
```
### 6. Linked list
Description
Linked list(連結串列)是一種常見的資料結構，其使用node(節點)來記錄、表示、儲存資料(data)，並利用每個node中的pointer指向下一個node，藉此將多個node串連起來，形成Linked list，並以NULL來代表Linked list的終點
這次題目有3個 1.請同學將一串數字存進list中 2.請輸入1個數字 並印出它的位置 3.請輸入一個數字 並插入問題2的位置後並印出整個list
這次請同學使用Linked list完成 如未使用將視為0分
Input:
請輸入一個數字 代表這串有幾個數字
再來輸入一個數字 代表要從list中尋找的字
最後輸入一個數字 代表要插入的字
Output:
第一個題目不會輸出
第二個題目將輸出找到數字之位置
第三個題目 請輸出插入數字後的整串數字
```c=
#include<stdio.h>
int find_number;
int stack_len=0; //stack的長度
typedef struct{
int data;
struct LinkNode *next; //指向下一個
}LinkNode;
void add(LinkNode *obj,int num){
LinkNode *new=(LinkNode*)malloc(sizeof(LinkNode));
for(int i=0;i<stack_len;i++){ //找到位置
obj=obj->next;
}
new->data = num;
obj->next = new;
stack_len++; //後++
}
int find(LinkNode *obj,int num){
LinkNode *new=(LinkNode*)malloc(sizeof(LinkNode));
new->data=num;
for(int i=0;i<stack_len;i++){
obj=obj->next;
if(obj->data==find_number){ //找到要插入的數字前面
new->next=obj->next;
obj->next=new;
return i; //回傳位址
}
}
return 0;
}
int main(void) {
int quantity,n;
scanf("%d",&quantity); //這串的數字個數
LinkNode *head=(LinkNode*)malloc(sizeof(LinkNode)); //頭
head->data=0;
for(int i=0;i<quantity;i++){ //讀取插入鏈結串列
scanf("%d",&n);
add(head,n); //呼叫函式
}
int insert;
scanf("%d",&find_number); //要找的數字
scanf("%d",&insert); //要插入的數字
int re=find(head,insert); //接收要插入的索引值
printf("%d\n",re);
for(int i=0;i<stack_len+1;i++){ //依序印出
head=head->next;
printf("%d ",head->data);
}
}
```
### 7.二元樹搜索
Description
建立一顆full二元樹
使用3種方式走訪 並輸出結果
1.DLR:前序(Preorder)
2.LDR:中序(Inorder)
3.LRD:後序(Postorder)
Input：
先輸入樹的節點數量再按照順序輸入節點的內容
例:
7
12345 7 6(數字隨機排序)
輸入後建立的樹如下:
Output：
使用3種方式走訪 並輸出結果(數字中間用一個空格隔開)
DLR:1 2 4 5 3 7 6
LDR:4 2 5 1 7 3 6
LRD:4 5 2 7 6 3 1
```c=
// (陣列)
#include <stdio.h>
#define Num 20
int BinaryTree[Num]={0};
int count1=0,count2=0,count3=0;
int n;
void Preorder_BinaryTree(int node) { //走訪前序-->中前後
if (BinaryTree[node]!=0) {
printf("%d",BinaryTree[node]); //先印數字-->中
count1++; //計算跑了幾個數字了-->最後一個不用空格
if(count1<n){ //判斷是否為最後一個數
printf(" ");
}
Preorder_BinaryTree(2*node); //走左子樹
Preorder_BinaryTree(2*node+1); //走右子樹
}
}
void Inorder_BinaryTree(int node) { //走訪中序-->前中後
if (BinaryTree[node] != 0) {
Inorder_BinaryTree(2*node); //走左子樹
printf("%d", BinaryTree[node]); //印出中間的數
count2++;
if(count2<n){ //判斷是否為最後一個數
printf(" ");
}
Inorder_BinaryTree(2*node+1); //走右子樹
}
}
void Postorder_BinaryTree(int node) { //走訪後序-->前後中
if (BinaryTree[node] != 0) {
Postorder_BinaryTree(2*node); //走左子樹
Postorder_BinaryTree(2*node+1); //走右子樹
printf("%d",BinaryTree[node]); //後印-->"中"的位置
count3++; //計算跑了幾個數字了-->最後一個不用空格
if(count3<n){ //判斷是否為最後一個數
printf(" ");
}
}
}
int main(void) {
scanf("%d", &n);
for (int i=0; i<n+1; i++) {
scanf("%d", &BinaryTree[i+1]);
}
printf("DLR:");
Preorder_BinaryTree(1); //呼叫前序
printf("\nLDR:");
Inorder_BinaryTree(1); //呼叫中序
printf("\nLRD:");
Postorder_BinaryTree(1); //呼叫後序
}
```
```c=
// (Linked_list)
#include<stdio.h>
#include<stdlib.h>
struct node{
int val;
struct node *left,*right;
};
int number = 1;
struct node *insert(struct node *node,int num,int i){
if(node == NULL){
struct node *new = (struct node*)malloc(sizeof(struct node));
new -> val = num;
new -> left = NULL;
new -> right = NULL;
node = new;
}
else if(node -> left == NULL && i == 2*number){
node -> left = insert(node -> left, num, i);
}
else if(node -> right == NULL && i == 2*number+1){
node -> right = insert(node -> right, num, i);
}
else if(i > 2 * number + 1){
number++;
if(i <= 2 * number + 1){
number--;
node -> left = insert(node -> left, num, i%2+2);
}
else if(i > 2*number+1){
number--;
node -> right = insert(node -> right, num, i%2+2);
}
}
return node;
}
int a = 1;
void preorder(struct node *root,int n){
if(root != NULL){
printf("%d",root -> val);
if(a < n){
printf(" ");
}
a++;
preorder(root -> left,n);
preorder(root -> right,n);
}
}
int b = 1;
void inorder(struct node *root,int n){
if(root != NULL){
inorder(root -> left,n);
printf("%d",root -> val);
if(b < n){
printf(" ");
}
b++;
inorder(root -> right,n);
}
}
int c = 1;
void postorder(struct node *root,int n){
if(root != NULL){
postorder(root -> left,n);
postorder(root -> right,n);
printf("%d",root -> val);
if(c < n){
printf(" ");
}
c++;
}
}
int main(){
struct node *root = NULL;
int n;
scanf("%d",&n);
int num[n];
for(int i = 0 ; i < n ; i++){
scanf("%d",&num[i]);
}
for(int i = 0 ; i < n ; i++){
root=insert(root,num[i],i+1);
}
printf("DLR:");
preorder(root,n);
printf("\n");
printf("LDR:");
inorder(root,n);
printf("\n");
printf("LRD:");
postorder(root,n);
printf("\n");
}
```
### 8.二元樹刪除
Description
建立一顆full二元樹，並刪除最後一排的其中1個值，最後以前序DLR輸出結果
Input：
先輸入 樹的節點數量，再按照順序輸入節點的內容，再來輸入要刪去的值
Output：
輸出刪除後的樹(以DLR走訪)
```c=
#include<stdio.h>
#include<stdlib.h>
struct node{
int val;
struct node *left,*right;
};
int number = 1;
struct node* delete(struct node* root, int key){
if(root==NULL){ //如果
return NULL;
}
else if(key == root->val){ //如果找到了-->刪除的四種狀況
free(root);
root=NULL;
}
else{
root->left=delete(root->left,key);
root->right=delete(root->right,key);
}
return root;
}
struct node *insert(struct node *node,int num,int i){
if(node == NULL){
struct node *new = (struct node*)malloc(sizeof(struct node));
new -> val = num;
new -> left = NULL;
new -> right = NULL;
node = new;
}
else if(node -> left == NULL && i == 2*number){
node -> left = insert(node -> left, num, i);
}
else if(node -> right == NULL && i == 2*number+1){
node -> right = insert(node -> right, num, i);
}
else if(i > 2 * number + 1){
number++;
if(i <= 2 * number + 1){
number--;
node -> left = insert(node -> left, num, i%2+2);
}
else if(i > 2*number+1){
number--;
node -> right = insert(node -> right, num, i%2+2);
}
}
return node;
}
int a = 1;
void inorder(struct node *root,int n){
if(root != NULL){
printf("%d",root -> val);
if(a < n){
printf(" ");
}
a++;
inorder(root -> left,n);
inorder(root -> right,n);
}
}
int main(){
struct node *root = NULL;
int n;
scanf("%d",&n);
int num[n];
for(int i = 0 ; i < n ; i++){
scanf("%d",&num[i]);
}
for(int i = 0 ; i < n ; i++){
root=insert(root,num[i],i+1);
}
int delete_num = 0;
scanf("%d",&delete_num);
root=delete(root,delete_num);
inorder(root,n);
}
```
### 9. Binary Search Tree
Description
建立一個 Binary Search Tree，對這棵樹刪除一個節點後(刪除的節點由左邊子樹的最大節點替補)，再新增一個節點，最後用DLR:前序走訪(Preorder) 輸出走訪結果
範例 :
Input：建立樹
1.input樹的節點數
2.輸入樹的節點
3.刪除樹中的一個節點
4.新增一個節點
Output：
經過上述處理的樹前序走訪(Preorder)結果
```c=
#include<stdio.h>
#include<stdlib.h>
struct node{
int val;
struct node *left,*right;
};
int number = 1;
struct node* maxfind(struct node* root){
while (root->right != NULL) { //如果左邊不等於NULL
root = root->right; //就一直往左邊跑
}
return root;
}
struct node* delete(struct node* root, int key){
struct node* temp=(struct node*)malloc(sizeof(struct node));
if(root==NULL){ //如果
return NULL;
}
else if(key < root->val){
root->left=delete(root->left,key);
}
else if(key > root->val){
root->right=delete(root->right,key);
}
else if(key == root->val){ //如果找到了-->刪除的四種狀況
if(root->left == NULL && root->right == NULL){ //如果底下都沒東西
free(root);
root=NULL;
}
else if(root->left == NULL){ //如果只有右邊有東西
temp=root->right;
free(root);
root=temp;
}
else if(root->right ==NULL){ //如果只有左邊有東西
temp=root->left;
free(root);
root=temp;
}
else{
temp=maxfind(root->left); //從右邊開始找，因為是找右邊的最小值
root->val=temp->val; //存值
root->left=delete(root->left,root->val); //刪掉那個點
}
}
return root;
}
struct node* insert(struct node* root, int val){
if(root==NULL){ //如果沒東西-->建議個new裝val
struct node* new=(struct node*)malloc(sizeof(struct node));
new->val=val;
new->left=NULL; //左右都是NULL
new->right=NULL;
root=new; //接上去
}
else if(val>root->val){ //如果數值比較大-->就往右邊
root->right=insert(root->right, val);
}
else if(val<root->val){ //如果較小-->就往左邊
root->left=insert(root->left, val);
}
return root; //回傳最後的root
}
int a = 1;
void preorder(struct node *root,int n){
if(root != NULL){
printf("%d",root -> val);
if(a < n){
printf(" ");
}
a++;
preorder(root -> left,n);
preorder(root -> right,n);
}
}
int main(){
struct node *root = NULL;
int n;
scanf("%d",&n);
int num[n];
for(int i = 0 ; i < n ; i++){
scanf("%d",&num[i]);
}
for(int i = 0 ; i < n ; i++){
root=insert(root,num[i]);
}
int delete_num = 0;
scanf("%d",&delete_num);
root=delete(root,delete_num);
int add_num=0;
scanf("%d",&add_num);
root=insert(root,add_num);
preorder(root,n);
}
```
### 10.DFS走訪
Description
Depth-First Search(DFS，深度優先搜尋)的核心精神便如同Pre-Order Traversal：「先遇到的vertex就先Visiting」，並且以先遇到的vertex作為新的搜尋起點，直到所有「有edge相連的vertex」都被探索過。
本次題目為無向圖 並以第一個點為開頭進行走訪
Input：
輸入一個數字 代表有幾個點
輸入矩陣 為點所連接的關係
Output：
輸出dfs走訪結果
```c=
#include<stdio.h>
int number,visited[10],map[10][10]; //數字個數，判斷數字是否印出，scanf的 0 1表
void DFS_order(int out){
printf("%d ",out); //丟出來的先印
visited[out]=1; //如果印過了就賦值1
for(int in_stack=0;in_stack<number;in_stack++) //for迴圈跑每格
if(visited[in_stack]==0 && map[out][in_stack]==1) //判斷，如果出現過或是沒有相連就不能進入DFS_order
DFS_order(in_stack);
}
int main(){
scanf("%d",&number); //讀取數字總個數
for(int i=0;i<number;i++){ //讀取0 1表
for(int j=0;j<number;j++){
scanf("%d",&map[i][j]);
}
}
// for(int i=0;i<number;i++){ //先把拜訪的部分歸零
// visited[i]=0;
// }
DFS_order(0);
}
```
### 11.Kruskal演算法
Description
Input：
先輸入圖有多少節點 --> 5
再輸入圖的連接內容與權重，0 代表沒有連接，其他數字代表邊的權重
0 3 0 0 1
3 0 5 0 4
0 5 0 2 6
0 0 2 0 7
1 4 6 7 0
Output：
輸出要連接的邊
```c=
#include<stdio.h>
#include<stdlib.h>
int parent[9];
int find(int);
int uni(int,int);
int main(){
int number=0,count=1,min; //幾乘幾的方陣 , main 裡跑 while 計算的變數，min紀錄目前最小的權重
int i,j,left,right,check_0,check_1;
//(上)i、j是for迴圈的變數，right、check_1紀錄陣列的位置，check_0,、check_1用來確認是否相等-->if相等，為circle
scanf("%d",&number); //讀取方陣大小
int path[number+1][number+1]; //建一個number*number的方陣
for(i=1;i<=number;i++){ //讀取方陣內容，如果等於0 --> 變成999
for(j=1;j<=number;j++){ //if 從 path[0][0] 開始讀取會出事
scanf("%d",&path[i][j]);
if(path[i][j]==0){path[i][j]=999;}
}
}
while(count < number){ //從最小的權重開始跑，判斷是否circle
for(i=1,min=999;i<=number;i++){
for(j=1;j<=number;j++){
if(path[i][j]<min){ //找到最小的先賦值，再往下判斷
min=path[i][j];
left=check_0=i;
right=check_1=j;
}
}
}
check_0=find(check_0); //先找到源頭0
check_1=find(check_1); //找到源頭1
if(uni(check_0,check_1)){ //如果源頭不同，印出此次的權重
if(count==1){ //格式部分印出
printf("%d",min);
}
else{
printf(" %d",min);
}
count++; //累計
}
path[left][right]=path[right][left]=999; //如果沒有變成最大，下次還會再跑一次-->沒完沒了
}
}
int find(int n){ //找源頭，如果parent裡面有東西就會一直找
while(parent[n]){n=parent[n];}
return n;
}
int uni(int n,int m){
if(n!=m){ //如果不同就填到parent裡面
parent[m]=n;
return 1; //源頭不同為true
}
return 0;
}
```
### 12.Quick Sort(快速排序法)
Description：
Quick Sort是一種「把大問題分成小問題處理」的Divide and Conquer方法，概念如下：
在數列中任意挑選一個數，稱為pivot，然後調整數列，使得「所有在pivot左邊的數，都比pivot還小」，而「在pivot右邊的數都比pivot大」。
接著，將所有在pivot左邊的數視為「新的數列」，所有在pivot右邊的數視為「另一個新的數列」，「分別」重複上述步驟(選pivot、調整數列)，直到分不出「新的數列」為止。
本題以數列最左為PIVOT
Input：
請輸入一個數 代表數列有多少數字
請輸入數列
Output：
將PIVOT做完排序後的數列輸出
```c=
#include<stdio.h>
int num=0;
int sort_num[10]={0};
void quick_sort(int head,int len){
int pivot,i,j;
if(head<len){
i=head+1,j=len;
pivot=sort_num[head]; //把最前面一個數存起來判斷
while(i<j){
while(sort_num[i]<pivot){
i++;
}
while(sort_num[j]>pivot){
j--;
}
if(i<j){
int temp=sort_num[i];
sort_num[i] = sort_num[j];
sort_num[j] = temp;
}
}
int temp=sort_num[head];
sort_num[head] = sort_num[j];
sort_num[j] = temp;
for(int r=0;r<num-1;r++){
printf("%d ",sort_num[r]);
}
printf("%d\n",sort_num[num-1]);
quick_sort(head,j-1); //左
quick_sort(j+1,len); //右
}
}
int main() {
scanf("%d",&num);
for(int i=0;i<num;i++){
scanf("%d",&sort_num[i]);
}
quick_sort(0,num-1);
}
```
Sign in with Wallet
Connect another wallet