第八章結構，列舉型別，二元樹

列舉

把一些數值用字串表示, 方便記憶, 並設定某個變數只能是這個列舉中的值. 這個型態比較聰明, 會自動幫使用者累加

   enum Color{
      Red=1,
      Green,
      Blue
   };
   enum Color pen;
   pen=Blue;
   printf("%d \n", pen);

pen 只能設定為Red, Green, Blue其中一種而己，其他都不行

精簡法

   enum Color{
      Black,
      Red=5,
      Green,
      Blue
   }pen=Blue, pencil=Black;

Black為0, Green為6, Blue 為7

結構

struct 為自訂資料型態, 集合各個不同的資料為一種新的資料型態

宣告 :

   struct Student{
      char name[10];
      int math;
      int chinese;
   };
   struct Student thomas={"Thomas", 90, 80 };
   Student thomas={"Thomas", 90, 80};//二者都可以

printf(“%s\n%d\n%d\n”, thomas.name, thomas.math, thomas.chinese);//使用 “.” 存取

精簡

   struct Student{
      char name[10];
      int math;
      int chinese;
   }thomas, john={"john", 50,100};;

thomas.name= “Thomas”;//error, 因為此陣列己指定給10byte的空間，不能再移位，只能用strcpy(thomas.name, “Thomas”);

另類初始值

   struct Student{
      char name[10]="default";
      int math=0;
      int chinese=0;
   }thomas;//以上ok，可以初始化

但

   struct Student{
      char name[10]="default";
      int math=0;
      int chinese=0;
   }thomas{"Thomas", 90, 100};//一定掛掉, 需一個一個指定  thomas.math=100;

另人抓狂但又需記住的東西

   struct Student{
      char name[10];
      int math;
      int chinese;
   }a;
   Student *thomas=&a;//宣告為指標，並指向己宣告的struct, 此時需用 -> 來存取，不能用 "."
   strcpy(thomas->name, "Thomas");
   thomas->math=100;

等等，為什麼要用 Student *thomas=&a ?? 如果用Student thomas=a可以嗎!!
Ans : 可以，此時就會由a複製一個新的結構給thomas, 二者完全獨立

新生物件

Student *thomas=new Student();產生一個新的結構, 物件觀念開始成形了

單向連結

#include <iostream>
#include <time.h>
#include <stdlib.h>
using namespace std;
int n=10;
struct Node{
	Node *next=NULL;
	int data=0;
};
int main(){
	Node *root=new Node();
	Node *current=root;
	srand(time(NULL));
	for (int i=0;i<n;i++){ current->data=rand();
		current->next=new Node(); 
		current=current->next;
	}
	current=root;
	while(current->next!=NULL){
		printf("%d ", current->data);
		current=current->next;
	}
}

雙向連結

#include <iostream>
#include <time.h>
#include <stdlib.h>
using namespace std;
int n=10;
struct Node{
	Node *prev=NULL;
	int data=0;
	Node *next=NULL;
};
int main(){
	srand(time(NULL));
	Node *root=new Node();
	Node *current=root;
	//建立雙向連結節點 
	for(int i=0;i<n;i++){ current->data=rand();
		current->next=new Node();
		current->next->prev=current;
		current=current->next;
	}

	//正向列印 
	current=root;
	while(current->next!=NULL){
		printf("%d ", current->data);
		current=current->next;
	}
	printf("\n");

	//返回啟點, 並將指標移到最後一個節點 
	current=root;
	while(current->next!=NULL){
		current=current->next;
	}

	//反向列印 
	while(current->prev!=NULL){
		current=current->prev;
		printf("%d ", current->data);
	}	
}

二元樹排序法

#include <iostream>
#include <time.h>
#include <stdlib.h>
using namespace std;
int n=10;
int index=0;
struct Node{
	Node *left=NULL;
	int data=0;
	Node *right=NULL;
};
void getData(int *r){
	srand(time(NULL));
	for (int i=0;i<n;i++){
		r[i]=rand();		
	}
}
void printData(int *d){
	for (int i=0;i<n;i++){
		printf("%d ", d[i]);
	}
	printf("\n");
}
Node *buildTree(int d, Node *node){
	if (node==NULL){
		node=new Node();
		node->data=d;
		return node;
	}
	else if(d<=node->data){
		node->left=buildTree(d, node->left);
	}
	else{
		node->right=buildTree(d, node->right);
	}
}
void sort(Node *node, int *r){
	if(node->left!=NULL)sort(node->left, r);
	r[index++]=node->data;
	if(node->right!=NULL)sort(node->right, r);
}
int main(){
	int *rawArray=new int[n];
	int *sortArray=new int[n];	
	srand(time(NULL));
	getData(rawArray);
	printData(rawArray);

	Node *root=NULL;
	for (int i=0;i<n;i++){
		root=buildTree(rawArray[i], root);
	}
	timespec t1, t2;
	
	clock_gettime(CLOCK_REALTIME, &t1);
	sort(root, sortArray);
	clock_gettime(CLOCK_REALTIME, &t2);
	printData(sortArray);
	
	printf("總花費時間 : %0.3f 微秒", ((t2.tv_sec-t1.tv_sec)*1000000000+(t2.tv_nsec-t1.tv_nsec))/1000.0f);
	system("pause");
	return 0;
}

列舉

結構

新生物件

單向連結

雙向連結

二元樹排序法

發佈留言