---
# System prepended metadata

title: 程式設計Ⅰ【筆記Ⅲ】
tags: [Programming]

---

**程式設計Ⅰ【筆記Ⅲ】**
===
* [name=Ivy Lin]
* [筆記1](https://hackmd.io/NPFilj4fSNu020tfh5s3TQ)
* [筆記2](https://hackmd.io/50cD9oibROGhAn2loo5v6g)


## 第十三週<2023.5.9>

### 指標

1. **不同的指標type，用++符號的差別**
    * 令指標變數時，會依照不同型別來區分一個資料
    * 因此，每個指標type加上的值都不一樣
       (char:1|int:4|float:4|double:8|long long:8)
       
2. **等價指標寫法**
    * 取值: a[i] <=> * (a+i)
    * 取址: &a[i] <=> (a+i)

3. **定義新type:**
```clike=
//typedef 可以定義新的型別名稱以利辨識
typedef (型別) (名字) ;
```
4. **指標的門牌號碼要先定義好才可以定義它的值**

5. **二維陣列的指標**
    * a[0][0]的地址和a[0]地址相同
    
    * 對大指標+1 =>位移整個格數
    * 對小指標+1 =>位移一格
        Ex. a[5][5] 
        (1) a+1 = a[1][0]
        (2) a[0]+1 = a[0][1]
        
    * 二微陣列指標變數宣告
        ```clike=
        //定義一指標，所指的整數陣列包含n個整數元素
        //若定義int z[4][2],則指標變數要訂int (*ptr)[2]
        //對陣列指標變數做+1，會跳到下一個位元組(意即:z[0]->z[1])
            int (*指標名稱)[陣列數量n]
            
        //定義一個陣列、每個元素均為指向整數的指標
            int *指標名稱[陣列數量n] 
        ```
        
## 第十四週<2023.5.16>

### 指標

1. **指標變數宣告**
```clike=
int *pt; //儲存int型別地址的指標
int **p2; //儲存int*型別地址的指標
int (*pa)[3]; //二維陣列一次跳過三格int的指標
int a[2][3], b[3][2]; 

pt=&a[0][0]; //<=> pt=&a; <=> pt=a; 
pt=a[0]; // <=>t=&a[0];
pa=a; // 單位為三的int指標(陣列)
pa=b; // 會出現錯誤(單位不同)
p2=&pt; // 指向int型別指標的指標www
*p2=b[0]; // *p2=>位址 可以指向b[0](指標位置)
p2=b; // p2(指向指標的指標) != b(指標) 錯誤
```

2. **傳遞二維陣列到函數**
```clike=
int function(int (*arr)[COLS]);
// int function(int [][COLS]); 
// int function(int arr[][COLS]); 
```
3. **應用陣列來排序**

```clike=
//pseudo code => Insertion Sort
/*又稱插牌法，將元素一個一個比較後插入陣列中*/

void insesertion(int *arr,int size){
    
    for(int i=1;i<size;i++){
        int v=arr[i],j=i-1;
        
        while(j>=0 && arr[j]>v){
            arr[j+1]=arr[j];
            j--;
        }
        arr[j+1]=v;
    }
    
}
```

4. **指標v.s遞迴v.s陣列**
    =>利用指標做陣列的遞迴
    
```clike=
#include <stdio.h>
void permutation(char * a, int n);
void swap( char *, char *);
int main(void)
{
   char str[] = "cats";
   permutation(str, 4);
   return 0;
}

void permutation(char *a,  int n)
{
   int i; 
   if (n == 1) {
      printf("%s\n", a);
   } 
    
   else {
      for (i = 0; i < n; i++) {  
         swap(&a[i], &a[n-1]);  // 交換元素
         permutation(a, n-1);     
         swap(&a[i], &a[n-1]);  //遞迴回到原狀態
      }
   } 
}
void swap(char *x, char *y)
{
   char tmp;

   tmp = *x;
   *x = *y;
   *y = tmp;
}
```
5. 字串處理<string.h>
    * strcmp
        * 比較字串長度是否相等
    ```clike=
    int strcmp ( const char * str1, const char * str2 );
    ```
    >str1 : the first string to be compared
    >str2 : the second string to be compared
    
    > < 0 : str1 is less than str2 lexicographically
    > 0 : str2 is less than str1
    > == 0 : str1 is equal to str2

    * strcpy
      * 複製字串from到字串to(會覆蓋)
    ```clike=
    char * strcpy ( char *restrict to, const char *restrict from );
    ```
    * strncpy
        * 從字串from複製n個元素到自串to(會覆蓋)
    ```clike=
    char * strncpy ( char *restrict to, const char *restrict from, size_t count );
    ```
    * strcat
        * 將字串from接到字串to後面
    ```clike=
    char *strcat( char *restrict to, const char *restrict from );
    ```
    * strncat
        * 從字串from複製n個元素接到自串to後面
    ```clike=
    char *strncat( char *restrict to, const char *restrict from, size_t count );
    ```
    * memset
        * 設定開頭，可以將count個字元填上想要的ch
    ```clike=
    void *memset( void *dest, int ch, size_t count );
    ```
    * memcpy
        * 複製count個字元從from複製到to
    ```clike=
    void* memcpy( void *to, const void *from, size_t count );
    ```
    
6. 實作strcpy strcat

```clike=
#include <stdio.h>
#include <string.h>
void Strncpy(char *to, char *from, int n) {
    while (*from != '\0' && n>0) {
        *to = *from;
        to++;
        from++;
        n--;
    }
}
void Strncat(char *to, char *from, int n) {
    while(*to != '\0') to++;
    Strncpy(to, from, n);
} 
int main(void)
{
    char str1[] = "abc";
    char str2[10] = {0};
    Strncat(str2, str1, 2);
    Strncat(str2, str1, 2);
    printf("str1: %s\n", str1);
    printf("str2: %s\n", str2);
 
}
```

7. 反轉字串

```clike=
#include <stdio.h>
#include <string.h>

void reverse(char *start, char *end) {
    char tmp;
    while (start < end) {
        tmp = *start;
        *start = *end;
        *end = tmp;
        start++;
        end--;
    }
}
int main(void)
{
  char str[256];
  int i;
  char *start;
  fgets(str, 255, stdin);
  // this is a book \0
  str[strlen(str)-1] = ' ';
  start = str;
  for (i=0; i<strlen(str); ++i) {
    if (str[i] == ' ') {
        reverse(start, str + i - 1);
        start = str + i + 1;
    }
  }
  reverse(str, str+strlen(str)-2);
  str[strlen(str)-1] = '\0';
  printf("%s\n", str);
}
```


## 第十五週<2023.5.23>

### 指標

#### Qsort

```clike=
void qsort( void *ptr, size_t count, size_t size, int (*comp)(const void *, const void *) )
    
//Qsort在main函數中的寫法
qsort((int *)input, n, sizeof(input[0]), compare);
qsort(input, n, sizeof(input[0]), compare);
```
* ptr
    >指向要排序的陣列的起始位置的指標
    >也可以直接寫陣列名字!
* count
    >在陣列中有幾個元素要排序
* size
    >在陣列中每個元素的大小，以 byte 為單位
    >sizeof是可以求大小的函數，記得要是"元素"大小
* comp
    >比較

>要注意的一點是:compare需要自己寫!

```clike=
//簡單int比較
qsort(input, n, sizeof(int), compare);
int compare(const void *a, const void *b)
{
    //下面這句就是說將a改成(int *的指標)然後在對a取值
    int x = *(int *)a;
    int y = *(int *)b;
    if (x < y)
        return -1;
    else if (x > y)
        return 1;
    else
        return 0;
}

//比較複雜的char比較
//x代表一筆資料有幾個元素EX.char input[5][4];=>x=4
qsort(input, n, x*sizeof(char), compare);
int compare(const void *a,const void *b){
    char c=*(char *)a;
    char d=*(char *)b;
    //strcmp就是比較字串大小
    return strcmp(c,d);
}
```


#### 一些指標的tips

```clike=
//陣列指標=>型別 名稱 [size][size]
//int陣列
int input[10][2];
int (*ptr)[2]; //指位元2的指標變數

//char陣列
char arr[10][5];
char (*pt)[5];

//函數指標=>記得函數的位址
int f(int *,int);
int (*p)(int *,int);
p=f;
```


### 實作一個可以存函數的指標

```clike=
# include <stdio.h>
# include <stdlib.h>
int sum(int a[], int n)
{
    int i, ans = 0;
    for (i=0; i<n; i++) {
        ans += a[i];
    }
    return ans;
}
int sum_squared(int a[], int n)
{
    int i, ans = 0;
    for (i=0; i<n; i++) {
        ans += a[i]*a[i];
    }
    return ans;
}

int middle(int a[], int n)
{
    return a[n/2];
}

int run (  int  (*fp) (int *, int )  , int * a, int n)
{
    return fp(a, n);
}

int main(void)
{
    int a[] = {1, 2, 3, 4};
    printf("%d\n", run(sum, a, 4));
    printf("%d\n", run(sum_squared, a, 4));
    printf("%d\n", run(middle, a, 4));
    return 0;
}
```

### 取得記憶體的方法

```clike=
void* malloc( size_t size );
void free( void* ptr );
```

>size
要分配的記憶體大小，以 byte 為單位
>回傳值
如果成功的話，回傳的指標是指向分配的的記憶體的開頭位址
如果失敗的話，回傳一個空指標

>ptr
要釋放的記憶體的指標，必須是當初分配某塊空間時拿到的那個位址；如果ptr為NULL，則此函式不會做任何事情

```clike=
//令一個指標變數來存放malloc回傳的指標(記得轉型別)

//動態一維
int *ptr;
ptr=(int *)malloc(arr_size*(sizeof(int)));
//ptr有可能會是NULL
free(ptr);


//動態二維(第一種方式)
//直接數全部的陣列
int row,column;
double *pt;
pt=(double *)malloc((sizeof(double)*row*column));
//使用上就只能自己來換算index了!
//比如說pt[i*column+j];
for (int i=0; i<rows; ++i) {
    for (int j=0; j<columns; ++j) {
       pt[i*columns+j]=某個你想放的資料;
    }
}

free(pt);


//動態二維(第二種方式)
//記住每個row的開頭地址
int row,col;
char p = (int**) malloc(row*sizeof(int*));

//使用=>利用創建的二維空間記住原本陣列的開頭地址
char array = (int*) malloc(row*col*sizeof(int));
for (i=0; i<row; ++i) {
      p[i] = &array[i*col];
}
//然後再一一填入後面的資料
for (i=0; i<row; ++i) {
   for (j=0; j<col; ++j) {
        p[i][j] = 某個你想放的資料;
    }
}
free(p);
```


### 字串與指標


* 在傳遞字串時，會用指向字串的第一個字元的指標作為該字串的代表

1. string literal 的型別是 char[]
2. 如果是用指標去指向某個 string literal，那麼其指向的內容是不可寫的
```clike=
const char* str = "string"; // 如果寫出 str[0]='t'，在編譯時就會出錯
char str[] = "string"; // str[0]='S' 是可以的
```

>const char* str = "string";
>char str[] = "string";
>兩種是不同的!


### 更改指標值的函數

* 為了更改指標(本身有一層* 了!)，函數會傳入指標的地址(&指標名)，為了存取這個變數，在宣告函數時需要多一層*(也就是宣告成"型別**指標名)

>因為在收地址時，會使用到取址運算子(&)，為了消除它的作用，需要額外加上星號來抵銷，剩下就是指標原本宣告的型別

```clike=
//實作
void malloc_float2( float* * q , size_t sz)  // q = &ptr
{
    *q = (float *) malloc(sz*sizeof(float));  // *q => *&ptr => ptr
}

int main(void)
{
    float * ptr = NULL;
    int i;
    int n = 100;

    malloc_float2(&ptr, n);
}
```


## 結構structure

Structures 是可以由使用者自己定義，由其他型別 (甚至是 structure) 的變數所組成的一個資料型別
這樣的方式在使用上較方便，也會讓程式更簡潔易懂

```clike=
//定義x,y是平面上的座標
struct point{
  int x;
  int y;
};
//使用要加上 struct point

//不想加struct的寫法=>
typedef struct {
    int x;
    int y;
} point;

//pt會包含x和y兩個 members，要更改 members 的內容，使用 . 來存取
//如果是指標變數，則可以透過->來存取
point a={5,10};
a.x=20;//將a點的x座標改成20

point* b=&a; //point變成新的型別，所以可以令一個point*的指標
(*b).x=20; //*b==a
b->x=20; //指標要直接改數值就用->
```

* 小撇步:宣告函數變數是指標時，傳入的值一定是地址(也救世會需要取址運算子&)




