---
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;
}
```
Sign in with Wallet
Connect another wallet