---
# System prepended metadata

title: 南大資料結構
tags: [南大, 教學, 資料結構]

---

---
tags: 教學,南大,資料結構
###### tags:'教學','南大','資料結構'
---

<!--
# 南大資料結構 
## 練習15 鏈結串列 參考答案

```
#include <stdio.h>
#include <stdlib.h>

typedef struct element *linkedlist;
typedef struct element
{
	char key;
	linkedlist link;
};

linkedlist top=NULL,front=NULL,rear=NULL,avail=NULL;

int capacity = 0;

ret_node(linkedlist ptr)
{
	linkedlist tmp;
	if(avail == NULL)
		avail = ptr;
	else
	{
		ptr->link = avail;
		avail = ptr;
	}
}

element* get_node()
{
	linkedlist tmp;
	if(avail != NULL)
	{
		tmp = avail;
		tmp->link = NULL;
		tmp->key = ' ';
		avail = avail->link;
	
	
	}else
	{
		tmp = (element*) malloc(sizeof(element));
	}
		return tmp;
}
void Empty(char mode)
{ 
	if(mode=='s')
		printf("stack is empty，No elements!\n");
	else if(mode=='q')
		printf("queue is empty，No elements!\n");
	else
		printf("mode error!\n");
		
	exit;
}
	
void Push( char inputchar, char mode)
{ 
	//配置指標
	linkedlist tmp;
	
	tmp = get_node();
		
	
	if(mode == 's'){
		tmp->key = inputchar;
		tmp->link = top;
		top=tmp;
		capacity++;
	}
	else if(mode == 'q')
	{
		tmp->key = inputchar;
		tmp->link = NULL;
		if(front)
			rear->link = tmp;
		else //第一個元素 
			front = tmp;
		rear = tmp;
		capacity++;
	}
	else
	{
		printf("mode error!! \n");
	}
	

	
}



element* Pop(char mode)
{ 
	//配置指標
	linkedlist tmp,outputitem;
//	element outputitem;
	
	if(mode == 's')
	{
		tmp = top;
		if (!tmp ) //空 
	    	 Empty(mode);
	    else
		{
			outputitem->key = tmp->key;
			top = 	tmp->link; 
			capacity--;
			ret_node(tmp);
			return outputitem;
		}   	
	}
	else if(mode=='q')
	{
		tmp = front;
		if (!tmp ) //空 
	    	Empty(mode);
	    else
		{
			outputitem->key = tmp->key;
			front =	tmp->link; 
			capacity--;
			ret_node(tmp);
			
			return outputitem;
		}   
	}
	else
	{
		printf("mode error!! \n");
	}

}

void Print(char mode)
{
	if(mode=='s')
	{
		printf("stack are : \n");
		linkedlist tmp;
		tmp = top;
		printf( "stack={" );
		while(tmp)
		{
			printf("%c, ",tmp->key );
			tmp = tmp->link;
		}
		printf( "} \n " );	
	}
	else if(mode=='q')
	{
		printf("queue are : \n");
		linkedlist tmp;
		tmp = front;
		printf( "queue={" );
		while(tmp)
		{
			printf("%c, ",tmp->key );
			tmp = tmp->link;
		}	
		printf( "} \n " );
	}
	else
	{
		printf("mode error!! \n");
		
	}

	printf("目前容量:%d \n",capacity);						
}


int main(void)
{
	
	linkedlist letter;
	char action, mode;
	int i, end;
	
	printf("Please push a 's'(stack) or 'q'(queue) to use this struct ! \n");
	scanf(" %c", &mode);
//	queue = (element*) calloc(capacity, sizeof(element*));
	
	
	if(mode == 's'){
		do{
			printf("This is a stack! Please push a letter or '=' for pop or '!' for exit ! \n");
			scanf(" %c", &action);
			
			if(action > 64 && action < 123)
			{
				Push(action, mode);
				Print(mode);
			
			}
			else if(action == 61){
		
				printf("'%c'  \n", Pop(mode)->key);
				Print(mode);					
			}
			else
			{
				printf("Please input a letter ! \n");
				
			}
		}while(action != 33 );
	}
	else if(mode =='q'){
		do{
			printf("This is a queue! Please push a letter or '=' for pop! \n");
			scanf(" %c", &action);
			
			if(action > 64 && action < 123)
			{
				Push(action, mode);
				Print(mode);
			
			}
			else if(action == 61){
		
				printf("'%c'  \n", Pop(mode)->key);
				Print(mode);					
			}
			else
			{
				printf("Please input a letter ! \n");
				
			}
	
		}while(action != 33 );
	}
	else
	{
		printf("Don't input other letters! try again! press 'e' to exit! ");
	}
	
	

		
	printf("\n目前容量:%d ", capacity);		
		
	return 0;
	
}
	

```
 -->
 
 

# 南大資料結構 
## 4-1 鏈結串列練習

```

#include <stdio.h>
#include <stdlib.h>
#define max_size 10

typedef struct listNode *listPointer;
typedef struct listNode{
	int data;
	listPointer link;
};


void insert(listPointer *first ,listPointer x, int num);
void del(listPointer *first ,listPointer trail,listPointer x);
void print(listPointer *first);
int main()
{

	listPointer ptr;
	
	listPointer node[max_size];
	int i;

	for( i=0 ;i<=5; i++)
	{
		node[i]= (listPointer) malloc(sizeof(listNode));
		node[i]->data = 20 + i*10;
	
		printf("node[%d]=%u, ", i, node[i]); //印出節點的位址 
	  	printf("node[%d].data=%d \n", i,node[i]->data); //印出節點的資料 
	  	
	}
	for( i=0 ;i<5; i++)
	{
		node[i]->link = node[i+1];
	  	printf("node[%d].link=%u\n", i,node[i]->link); //印出下一個節點位址 
		
	}
	
	ptr=node[0];
	node[i-1]->link = NULL;


//  while(ptr != NULL){
//  	
//  	printf(" ptr=%u, ", ptr); 
//  	printf("data=%d ", ptr->data); 
//  	printf("link=%u\n", ptr->link); 
//  	
//  	ptr=ptr->link;  //將ptr指向下一個節點 
//
//  } 
  
	 
  return 0;
};

void insert(listPointer *first ,listPointer x , int num)
{
	listPointer tmp;
	tmp =  (listPointer) malloc(sizeof(*tmp));
	tmp->data=num;
	
	if(*first)
	{
		tmp->link = x->link;
		x->link = tmp;
	}
	else
	{
		tmp->link = NULL;
		*first = tmp;
	}
	
}
void del(listPointer *first ,listPointer trail,listPointer x)
{
	
	if(trail)
		trail->link = x->link;
	else
		*first= (*first)->link;
		
	free(x);
}

```
## 3-2 結構陣列 queue
```
#include <stdio.h>
#include <stdlib.h>

struct element
{
	char key;
};
element *queue;

int capacity = 5;
int front=0, rear=0;	

void queueFull()
{ 

	int old_capacity=capacity;
	capacity *=2;
	queue = (element*) realloc(queue , capacity*sizeof(element*)) ;
	printf("倍增容量，目前容量:%d \n",capacity);
	
	printf("front:%d，rear:%d \n",front, rear);
	if( front > 0 )//捲繞
	{
		for(int i =front+1 ; i<old_capacity; i++)
		{
			queue[i+old_capacity] = queue[i];
			queue[i].key = ' ';
			
		}		
		front += old_capacity;
		
	}
	else
	{
//		front = capacity-1;	
		rear = rear+old_capacity;
	}
	
//	printf("queue is full!\n");	 
//	exit(EXIT_FAILURE);	
}

void queueEmpty()
{ 
	printf("queue is empty，No elements!\n");
	exit(EXIT_FAILURE);
	
}
	
void queuePush( element item)
{ 
	rear = (rear+1) % capacity;
	if (rear ==  front)
	 	queueFull();
	 	
	queue [rear] = item;
}

element queuePop()
{ 
	element item;
	if (front == rear ) 
    	queueEmpty();
    else
	{
		front = (front+1 ) % capacity;
		item = 	queue[front]; 
		queue[front].key = ' ';  //清空 
		return item;
	}   
}

void queuePrint()
{
	printf("queue are : \n");
	for(int i=0; i<capacity; i++)
		printf("queue[%d]= %c \n",i, *(queue+i) );
	
	printf("front:%d  rear:%d \n",front, rear);			
	printf("目前容量:%d \n",capacity);						
}


int main(void)
{
	
	element letter;
	char action;
	int i, end;
	
	queue = (element*) calloc(capacity, sizeof(element*));
	
	do{
		printf("Please push a letter or '=' for pop! \n");
		scanf(" %c", &action);
		
		if(action > 64 && action < 123)
		{
			letter.key = action;
			queuePush(letter);
			queuePrint();
		
		}
		else if(action == 61){
	
			printf("'%c'  \n", queuePop().key);
			queuePrint();					
		}
		else
		{
			printf("stop the program! \n");
			queuePrint();
		}
		
	
	}while(action == 61 || (action > 64 && action < 123));
	
	
		
	printf("\n目前容量:%d ",capacity);		
		
	return 0;
	
}
```



## 3-1結構陣列stack
```
#include <stdio.h>
#include <stdlib.h>

struct element
{
	char key;
};
element *stack;

int capacity;
int top=-1, front=-1, rear=-1;	

void stackFull()
{ 
		
	capacity *=2;
	stack = (element*) realloc(stack, capacity*sizeof(element*)) ;
	printf("倍增容量，目前容量:%d \n",capacity);
//	exit(EXIT_FAILURE);	
}

void stackEmpty()
{ 
	printf("Stack is empty，No elements!\n");
//	exit(EXIT_FAILURE);
	
}
	
void stackPush( element item)
{ 
	if (top >=  (capacity- 1))
		stackFull();
	   
	stack [++top] = item;
}

element stackPop()
{ 
    if (top == -1 ) 
    	stackEmpty();
    else
    	return stack[top--];
}

void statckPrint()
{
	printf("stack are : \n");
	for(int i=top; i>=0; i--)
		printf("stack[%d]= %c \n",i, *(stack+i) );
					
	printf("目前容量:%d \n",capacity);						
}


int main(void)
{
	
	element letter;
	char action;
	int i, end;
	
	capacity=2;
	stack = (element*) malloc( capacity*sizeof(element*));
	
	do{
		printf("Please push a letter or '=' for pop! \n");
		scanf(" %c", &action);
		
		if(action > 64 && action < 123)
		{
			letter.key = action;
			stackPush(letter);
			statckPrint();
		
		}
		else if(action == 61){
	
			printf("'%c'  \n", stackPop().key);
			statckPrint();					
		}
		else
		{
			printf("stop the program! \n");
			statckPrint();
		}
		
	
	}while(action == 61 || (action > 64 && action < 123));
	
	
		
	printf("\n目前容量:%d ",capacity);		
		
	return 0;
	
}
```

<!--

## 期中考 第一題改寫參考範例
```
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void make2Dlist(int **list, int &row, int &col);

int main(void){ 
    //全域變數改成動態配置
    int row, col;
    int **list;
    
    printf("Enter row number to generate:");
    scanf("%d", &row);
    printf("Enter col number to generate:");	
    scanf("%d", &col);

    //二維陣列動態配置法
    list = (int**) malloc(sizeof(int*)*row);
    for(int i=0 ;i < row ; i++)
        list[i] = (int*) malloc(sizeof(int)*col);
    
    //以址傳遞呼叫函式
    make2Dlist(list, row, col);
    
    return 0;
}

void make2Dlist(int **list, int &row, int &col)
{	
    srand(time(NULL));
    for(int i = 0; i < row ; i++)
     for(int j=0; j < col; j++)
        list[i][j] = rand( ) % 100;
}


```
-->


## 2-5 稀疏矩陣 轉置
```
#include <stdio.h>
#include <stdlib.h>
#include <time.h> 

#define MAX_COL 50

typedef struct term
{
	int col;
	int row;
	int value;
};

void transpose (term a[], term b[]);
void fastTranspose(term a[], term b[]);

int main()
{
	int i,j,k,isZero=1;
	
	
	term oring[MAX_COL], trans[MAX_COL];
	
	printf("show array now \n");
	
	oring[0].row= 4;
	oring[0].col= 6;
	oring[0].value= 3;
	
	int col_num = oring[0].row;
	int row_num = oring[0].col;
	int n =	oring[0].value;
	
	srand( time(NULL) );
	for( i=1 ; i<= n ; i++)
	{
		oring[i].col= rand( ) % oring[0].col ;
		oring[i].row= rand( ) % oring[0].row;
		oring[i].value= (rand( ) % 100) -50 ;
		
		printf("oring[%d][%d]=%d  ",oring[i].row , oring[i].col, oring[i].value );
		printf("\n");
	}
	
	printf("\n");
	
	for( i=0 ; i< col_num ; i++)
	{
		printf("%d : ",i);
		
		for( j=0 ; j< row_num ; j++)
		{
			for( k=1; k<=n; k++)
			{
				if(i == oring[k].row && j == oring[k].col)
				{
					printf("[%d]  ",oring[k].value);
					isZero=0;
					break;
				}
				else
				{
					isZero=1;
				}	
			}
			
			if(isZero)
				printf("[0] ");	
		}
		printf("\n");
	}
	
	
	//transpose(oring, trans);
	fastTranspose(oring, trans);
	
	printf("\n  show sparse matrix after transform \n");

	for(i=0 ; i<row_num; i++)
	{
		printf("%d : ",i);
		
		for(j=0; j<col_num; j++)
		{
	
			for(k=1; k<=n; k++)
			{
				if(i == trans[k].row && j == trans[k].col)
				{
					printf("[%d]  ",trans[k].value);
					isZero=0;
					break;
				}
				else
				{
					isZero=1;
				}	
			}
			
			if(isZero)
				printf("[0]  ");
		}
		printf("\n");
	}
	
	
	return 0;
}

void transpose (term a[], term b[])
{ /*  轉置a之後放進b裡  */
	int n,i,j,currentb;
	n = a[0].value;         /*  所有元素的個數  */
	b[0].row = a[0].col;   /*  b的列數等於a的行數  */
	b[0].col = a[0].row;   /*  b的行數等於a的列數  */
	b[0].value = n;
	if (n > 0)  {  /*  非零矩陣  */
		currentb = 1;
		for (i = 0; i < a[0].col; i++)
		/*  依照a的行轉置  */
			for (j = 1; j<= n; j++)
			/*  從目前的行中找元素  */
			if (a[j].col == i)  {
			/*  元素在目前的行裡，把它加入b中  */
				b[currentb].row = a[j].col;
				b[currentb].col = a[j].row;
				b[currentb].value = a[j].value;
				currentb++;
			}
		}
}

void fastTranspose(term a[], term b[])
{  /* 把a轉置後放入b裡 */
	int rowTerms[MAX_COL], startingPos[MAX_COL];
	int i,j, numCols = a[0].col, numTerms = a[0].value;
	b[0].row = numCols;
	b[0].col = a[0].row;
	b[0].value = numTerms;
	
	if (numTerms > 0)  {  /* 非零矩陣 */
		for (i = 0; i < numCols; i++)
			rowTerms[i] = 0;
		
		for (i = 1; i <= numTerms; i++)
		{
			rowTerms[a[i].col]++;
		//	printf("i=%d , col=%d, rowterms=%d ; ",i,a[i].col,rowTerms[a[i].col]);
		}
		
		//	printf("\n");
			
		startingPos[0] = 1;
				
		for (i = 1; i < numCols; i++)
		{
			startingPos[i] = startingPos[i-1] + rowTerms[i-1];
		//	printf("i=%d , startingPos[i-1]=%d, rowTerms[i-1]=%d ,startingPos[i]=%d ;\n ",i,startingPos[i-1],rowTerms[i-1],startingPos[i]);
		}	
		
		for (i = 1; i <= numTerms; i++)  {
			j = startingPos[a[i].col]++;
			b[j].row = a[i].col;
			b[j].col = a[i].row;
			b[j].value = a[i].value;
		}
	}
}
```

## 2-3三元序練習

```
#include <stdio.h>
#include <stdlib.h>
 
typedef struct sp_matrix{
    int row;
	int col; 
    int value;  
};
 
sp_matrix *ptr;
void printsp(int n);
int main(void)
{
    int i,n;
    
	printf("輸入矩陣的個數: ");
    scanf("%d", &n);
    ptr=(sp_matrix*) malloc(sizeof(sp_matrix)*n+1);
    
    printf("輸入矩陣的維度row: ");
    scanf("%d", &ptr[0].row);
    printf("輸入矩陣的維度col: ");
    scanf("%d", &ptr[0].col);
    ptr[0].value = n;
 
    
    for(i = 1 ; i <= n ; i++)
	{
        printf("請輸入 %d 項的row: ", i );
        scanf("%d", &ptr[i].row);
        printf("請輸入 %d 項的col: ", i );
        scanf("%d", &ptr[i].col);	
        printf("請輸入 %d 項的value: ", i);
        scanf("%d", &ptr[i].value);	
	}
 
  printf("印出三元序：\n");
    printf("%5d %5d %5d \n", ptr[0].row,ptr[0].col,ptr[0].value);	
    printf("----------------\n");	
	for(int i = 1 ; i <= n ; i++)
	{
        printf("%5d %5d %5d \n", ptr[i].row,ptr[i].col,ptr[i].value);		
 	}
//	printsp(n);
    return 0;
}

void printsp(int n)
{
	int i;
    printf("印出三元序：\n");
    printf("%5d %5d %5d \n", ptr[0].row,ptr[0].col,ptr[0].value);	
    printf("----------------\n");	
	for(int i = 1 ; i <= n ; i++)
	{
        printf("%5d %5d %5d \n", ptr[i].row,ptr[i].col,ptr[i].value);		
 	}
}

```



## 2-2 多項式練習


```
#include <stdio.h>
#include <stdlib.h>
 
typedef struct polynomial{
    float coef; 
    int expon;  
} ;
 
polynomial*ptr;
void printpoly(int n);
int main(void)
{
    int i,n;
    printf("輸入多項式的項次有幾項: ");
    scanf("%d", &n);
    
    ptr=(polynomial*)malloc(sizeof(polynomial)*n);
 
    
    for(i = 0 ; i < n ; i++)
	{
        printf("請輸入 %d 項的係數: ", i + 1);
        scanf("%f", &ptr[i].coef);
        printf("請輸入 %d 項的指數: ", i + 1);
        scanf("%d", &ptr[i].expon);	
	}
 
	printpoly(n);

    return 0;
}

void printpoly(int n)
{
	int i;
    printf("印出多項式：");
	for(int i = 0 ; i < n ; i++)
	{
        printf("(%1.0f)x^%d", ptr[i].coef,ptr[i].expon);	
        if( i != n-1)
            printf("+"); 
	}
 	printf("\n");
}

```

## 1-4 Struct練習2
```
#include <stdio.h>
#include <stdlib.h >
#include <string.h>
#include <time.h>

struct stu
{
	int age, stu_id;
	char name[10] ;
//	char text[10] = "hello";
//	char text[10] = {'h', 'e', 'l', 'l', 'o', '\0'};
	int score[4] ;
	float average;
};

int main(void)
{	
  	int i;
	float average;
	int age = 6;
	char name[10] = "apple";
	
	stu my , stu1;
	
	my.age = 15;
	strcpy(my.name ,"linda");
	
	stu1.age=20;
	strcpy(my.name ,"John");
	
	my.average = 0;
	stu1.average = 0;
	
	srand(time(NULL));
	for(i=0 ;i<4;i++)
	{
		my.score[i] = rand()%100+1;
		stu1.score[i] =rand()%100+1;
		my.average +=my.score[i];
		stu1.average +=stu1.score[i];
	}
	my.average /= 4;
	stu1.average /= 4;
	
	
	
	printf("my name is: %s\n", my.name);
	printf("my age is: %d\n", my.age);
	printf("my average is: %f\n", my.average);
	
	printf("stu1 name is: %s\n", stu1.name);
	printf("stu1 age is: %d\n", stu1.age);
	printf("stu1 average is: %f\n", stu1.average);
	
	printf("age is: %d\n", age);
	printf("name is: %s\n", name);
	
	return 0;
}
```

## 1-4 Struct練習1
```
#include <stdio.h>
#include <stdlib.h >
#include <string.h>

struct data
{
	int age;
	char name[6] = "vicky";
//	char text[10] = "hello";
	char text[10] = {'h', 'e', 'l', 'l', 'o', '\0'};
	int score;
};

int main(void)
{	
  	char name[10] = "apple";
	int i, age;
	data my;
	strcpy(my.name ,"linda");
//	my.name[6] = "apple";
	my.age = 5;
	my.score = 90;
	
	age = 6;
	
	printf("my name is: %s\n", my.name);
	printf("my name is: %s\n", my.text);
	printf("my name is: %s\n", name);
	printf("my age is: %d\n", my.age);
		printf("age is: %d\n", age);
	printf("my score is: %d\n", my.score);
	
	return 0;
}
``` 



### 1-5 Magic Square

```
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void magic_square(int **square, int size);

int main(void)
{/* 反覆地產生一個大小為n的魔術方陣 */
    //int square[15][15];
    int **square;
    int i, j;   /* 索引 */
    //int count;           /* 計數值 */
    int size;            /* 方陣大小 */

    printf("Enter the size of the square: ");
    scanf("%d", &size);
    
    
    /* 檢查錯誤的輸入 
    if ( (size < 1) || (size > MAX_SIZE ) ) {
        fprintf(stderr, "Error! Size is out od range\n");
        exit(EXIT_FAILURE);
    }*/
    
    if (!(size %2) || size < 0) {
        fprintf(stderr, "Error! Size is even or smaller than zero!\n");
        exit(EXIT_FAILURE);
    }

	square = (int**) malloc(size*sizeof(int*));
	
	
    for (i = 0; i < size; i++ ) 
          square[i] = (int*) calloc(size , sizeof(int));
   
   printf("Magic Square of size %d : \n\n", size);   
    for ( i = 0 ; i < size; i++) {
        for ( j = 0 ; j < size; j++)
        {
            printf("%3d", square[i][j] );
        } 
        printf("\n");
    }
    printf("\n\n");
    
    /*函式呼叫*/ 
	magic_square(square, size);
	
    /*輸出魔術方陣*/
	printf("Magic Square of size %d : \n\n", size);   
    for ( i = 0; i < size; i++) {
        for ( j = 0; j < size; j++)
	      printf("%5d", square[i][j]);
        printf("\n");
    }
    printf("\n\n");
    
    return 0;
}

void magic_square(int **square, int size)
{
    int i,j,row, column;
    square[0][(size-1)/2] = 1; /* 第一列的中間 */
    /* i 跟 j 是目前的位置*/
    i = 0; 
    j = (size -1)/2;
   for ( int count = 2; count <= size* size; count ++) {
        row = (i - 1<0) ? (size - 1) : (i - 1) ; /* 上面 */
	    column = (j - 1<0) ? (size - 1) : (j - 1) ; /* 左邊 */
        if(square[row][column])  /* 下面 */
           i = (++i) % size;
        else {
           i = row;
           j = (j - 1<0) ? (size - 1) : --j;
         }
     square[i][j] = count;
	}
	
}

```


### 動態配置 建立二維陣列
```
int** make2dArray(int rows, int cols)
{ /* 建立一個 rows × cols的二維陣列 */
	int **x, i;
 
	/* 取得列指標所需的記憶體 */
	//MALLOC( x, rows * sizeof(*x));
	x = (int**) malloc( rows * sizeof(int*)); //rows * 8 bytes
 
	/* 取得每列需要的記憶體 */
	for ( i = 0; i < rows; i++)
            x[i] = (int*) malloc( cols * sizeof(int)); //cols * 4bytes
    return x;
}

```


## 練習5：Selection sort and binary search (遞迴版)

```
void sort(int [], int );  /*選擇排序*/
int compare( int x, int y );
int binarysearch (int list[], int searchnum, int left, int right);
int binarysearch_re(int list[], int searchnum, int left, int right, int &count);
int Sequentialsearch(int list[],int n, int searchnum);
void swap(int &a , int &b);


int main(void)
{ 
	int i, n, searchnum, left, right,key;
	int* list ;
    printf("Enter the number of numbers to generate: ");
    scanf("%d", &n);
    
    if( n < 1 ){
        printf("Improper value of n , system exit! \n");        
         exit(EXIT_FAILURE);
	}
	else{
		list = (int*) malloc(n*sizeof(int));
	}
	
	/*隨機產生數值*/
	srand (time(NULL));
	for(i = 0; i < n ; i++) {  
        list[i] = rand() % 1000;
        printf("%d ",list[i]);
	}
	
	/*呼叫排序函式*/
	sort(list,n);
	
	 /*印出已排好序的數值*/
	printf("\n Sorted array:\n ");
	for(i = 0; i < n ; i++) 
		printf("%d ",list[i]);
	printf("\n");
	
	
	int answer1, answer2,answer3, number;
	printf("Enter a serach number: ");
    scanf("%d", &number);
	
	answer1 = binarysearch(list, number, 0, n-1);
	if(answer1==-1)
		printf("無此數");
	else
		printf("在數列的第%d位置 ",answer1);
	
		printf("\n");
		
		
	answer2 = Sequentialsearch(list, n, number);
	if(answer2==-1)
		printf("無此數");
	else
		printf("在數列的第%d位置 ",answer2);
			
	printf("\n");
	
	
	printf("遞迴法：\n");
	int count=0;
	answer3 = binarysearch_re(list, number, 0, n-1, count);
	if(answer3==-1)
		printf("無此數");
	else
		printf("在數列的第%d位置 ",answer3);
			
		printf("\n");
	
	return 0;
}


void sort(int list[], int n)
{
   int i, j, min, temp;
   for(i = 0; i < n ; i++)  {
      min = i;
      for(j = i+1 ; j < n ; j++) 
        if(list[j] < list[min])
          min = j;
      //SWAP(list[i],list[min],temp);
      
      swap(list[i],list[min]);
      
   }
}

int compare( int x, int y )
{ /* 比較x和y ,若是x小於y，則傳回-1;等於則傳回0;大於則傳回1*/

	if(x < y) 
		return -1;
	else if(x == y)
		return 0;
	else
		return 1;
}


int binarysearch (int list[], int searchnum, int left, int right)
{ 

	int middle,a=-1, count=0 ;
	while (left <= right)
	{
		middle = (left + right)/2;
		switch(compare(list[middle], searchnum)) {
			case -1: left = middle+1;
			break;
			case 0 : a= middle;
			case 1 : right = middle-1;
		}
		if(a != -1)
		{
			count++;
		break;
		}
		else
			count++;
	}
	printf("\n search times:%d \n",count);
	
	if(a==-1)
		return -1; 
	else
	   return a;
}


int Sequentialsearch(int list[], int n, int searchnum)
{
	int a=-1,count=0;
	for(int i=0; i<n; i++)
	{
		count++;
		if(list[i] == searchnum)
		{
			a= i;
			break;
		}	
			
	}
	printf("\n search times:%d \n",count);
	
	if(a==-1)
		return -1;
	else
		return a;
}

int binarysearch_re(int list[], int searchnum, int left, int right, int &count)
{ 
   
	int a=-1,middle ;
	if (left <= right)
	{
		count++;
		printf("\n search times:%d \n",count);
	
		middle = (left + right)/2;
        switch(compare(list[middle], searchnum)) {
		  case -1 : return binarysearch_re(list, searchnum, middle+1, right,count);
          case  0 : return middle;
		  case  1 : return binarysearch_re(list, searchnum, left, middle-1,count);	    
		}
	} 

	return -1;

}

void swap(int &a , int &b)
{
	int tmp;
	tmp =a;
	a=b;
	b=tmp;
}

```


## 練習4：Selection sort and binary search (正常版)

```
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>


void sort(int [], int );  /*選擇排序*/
int binsearch(int [], int , int, int); /*二元搜尋*/
int compare(int x, int y);

int swap(int &x,int &y)
{
	int temp;
	temp = x;
	x=y;
	y=temp;
	
}

int main(void)
{
    int i, n, searchnum, left, right,key;
    int i, n;
	int* list ;
    printf("Enter the number of numbers to generate: ");
    scanf("%d", &n);
    
    if( n < 1){
        fprintf(stderr, "Improper value of n\n");        
         exit(EXIT_FAILURE);
	}
	else{
		list = (int*) malloc(n*sizeof(int));
	}
	
	/*for(i = 0; i < n ; i++) {  /*隨機產生數值*/
        list[i] = rand( ) % 1000;
        printf("%d ",list[i]);
	}*/
	
    srand(time(NULL));
    for(i = 0; i < n ; i++) {  /*隨機產生數值*/
        list[i] = rand( ) % 100;
        printf("%d ",list[i]);
    }

    sort(list,n);
	
    printf("\n Sorted array:\n ");
    for(i = 0; i < n ; i++)  /*印出已排好序的數值*/
        printf("%d ",list[i]);
    printf("\n");
    
    
    printf("Enter the number of numbers to search : ");
    scanf("%d", &key);

    int num =  binsearch(list, key, 0, n-1);
    printf("\n Sorted: %d the number is %d \n ", num, list[num] );
	
	
	return 0;

}


void sort(int list[], int n)
{
   int i, j, min;
   for(i = 0; i < n ; i++)  {
      min = i;
      for(j = i+1 ; j < n ; j++) 
        if(list[j] < list[min])
          min = j;
    	
        swap(list[i],list[min]);
        //SWAP(list[i],list[min],temp);
   }
}

int binsearch(int list[], int searchnum, int left, int right)
{
	int middle;
	
	while(left <= right){
		
		middle = (left+right)/2;
		printf("m:%d\n", middle);
		
		if(list[middle]== searchnum)
			return middle;
		else{
			switch (compare(list[middle], searchnum))
			{
				case -1 :
					left = middle+1;
					break;
				case 0:
					return middle;
					break;
				case 1:
					right = middle-1;
					break;
			
			}
		}
	
	}
	
	return -1;
}

int compare(int x, int y)
{
	if(x < y)
		return -1;
	else if(x==y)
		return 0;
	else
		return 1;
}
```

### 練習二：selection sort 改寫

```
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void sort(int [], int );  /*選擇排序*/
void swap(int &a, int &b);  /*交換*/
int main()
{
	int i, n;
	int* list ;
    printf("Enter the number of numbers to generate: ");
    scanf("%d", &n);
    
    if( n < 1){
        fprintf(stderr, "Improper value of n\n");        
         exit(EXIT_FAILURE);
	}
	else{
		list = (int*) malloc(n*sizeof(int));
	}
	
	for(i = 0; i < n ; i++) {  /*隨機產生數值*/
        list[i] = rand( ) % 1000;
        printf("%d ",list[i]);
	}

	sort(list,n);

	printf("\n Sorted array:\n ");
	for(i = 0; i < n ; i++)  /*印出已排好序的數值*/
	printf("%d ",list[i]);
	printf("\n");
	
}


void sort(int list[], int n)
{
   int i, j, min ;
   for(i = 0; i < n ; i++)  {
      min = i;
      for(j = i+1 ; j < n ; j++) 
        if(list[j] < list[min])
          min = j;
      swap(list[i],list[min]);
   }
}

void swap(int &a, int &b){
	int tmp;
	tmp = a;
	a =  b;
	b =tmp;
}
```

### 練習一：二維陣列練習 範例的參考答案

```
#include <stdio.h>
#include <stdlib.h>


int main(void)
{
	char sys;
	for(int i=0 ; i<5 ;i++)
	{
		for(int j=0 ; j<5 ;j++)
		{
			sys = i<j ? '*': ' '; 
			printf("%c", sys);
			
//			if(i<j)
//				printf("*");
//			else
//				printf(" ");
		}
		printf("\n");
	}
	
	
	for(int i=0 ; i<5 ;i++)
	{
		for(int j=0 ; j<5 ;j++)
		{
			if(i%2 == 0 )
				printf("*");
			else
				printf("%d", (j+1)%2);
		}
		printf("\n");
	}
	
	printf("\n");
	
	for(int i=0 ; i<5 ;i++)
	{
		for(int j=0 ; j<5 ;j++)
		{
			if(i*5+j+1 < 10 )
				printf("%2d", i*5+j+1 );
			else
				printf("%d", i*5+j+1);
		
		}
		printf("\n");
	}
	
	return 0;
}

```

