WEEK 3 Algorithms

1. 搜索

• Notation:

  • $O()$: Upper Bound

  • $\Omega()$: Lower Bound

  • $\Theta()$: If UB = LB

• Linear search, binary search

• Searching with code

2. 结构体

2.1 struct

C 数组允许定义可存储相同类型数据项的变量，结构是 C 编程中另一种用户自定义的可用的数据类型，它允许您存储不同类型的数据项。

结构用于表示一条记录，假设您想要跟踪图书馆中书本的动态，您可能需要跟踪每本书的下列属性：

• Title

• Author

• Subject

• Book ID

为了定义结构，您必须使用struct语句。struct语句定义了一个包含多个成员的新的数据类型，struct语句的格式如下：

struct tag { 
    member-list
    member-list 
    member-list  
    ...
} variable-list;

• tag是结构体标签。

• member-list是标准的变量定义，比如int i，或者其他有效的变量定义。

• variable-list结构变量，定义在结构的末尾，最后一个分号之前，您可以指定一个或多个结构变量。

下面是声明 Books 结构的方式。

struct Books
{
   char  title[50];
   char  author[50];
   char  subject[100];
   int   book_id;
} book;

在一般情况下，tag、member-list、variable-list这 3 部分至少要出现 2 个。以下为实例：

// 此声明声明了拥有3个成员的结构体，分别为整型的a，字符型的b和双精度的c
// 同时又声明了结构体变量s1
// 这个结构体并没有标明其标签
struct 
{
    int a;
    char b;
    double c;
} s1;
 
//此声明声明了拥有3个成员的结构体，分别为整型的a，字符型的b和双精度的c
//结构体的标签被命名为SIMPLE，没有声明变量
struct SIMPLE
{
    int a;
    char b;
    double c;
};
//用SIMPLE标签的结构体，另外声明了变量t1、t2、t3
struct SIMPLE t1, t2[20], *t3;

在上面的声明中，第一个和第二声明被编译器当作两个完全不同的类型，即使他们的成员列表是一样的。

结构体的成员可以包含其他结构体，也可以包含指向自己结构体类型的指针，而通常这种指针的应用是为了实现一些更高级的数据结构如链表和树等。

和其它类型变量一样，对结构体变量可以在定义时指定初始值。

#include <stdio.h>
 
struct Books
{
   char  title[50];
   char  author[50];
   char  subject[100];
   int   book_id;
} book = {"C 语言", "RUNOOB", "编程语言", 123456};
 
int main()
{
    printf("title : %s\nauthor: %s\nsubject: %s\nbook_id: %d\n", book.title, book.author, book.subject, book.book_id);
}

为了访问结构的成员，我们使用成员访问运算符（.）。成员访问运算符是结构变量名称和我们要访问的结构成员之间的一个句号。您可以使用struct关键字来定义结构类型的变量。

#include <stdio.h>
#include <string.h>
 
struct Books
{
   char  title[50];
   char  author[50];
   char  subject[100];
   int   book_id;
};
 
int main( )
{
   struct Books Book1;        /* 声明 Book1，类型为 Books */
  
  /* Book1 详述 */
   strcpy( Book1.title, "C Programming");
   strcpy( Book1.author, "Nuha Ali"); 
   strcpy( Book1.subject, "C Programming Tutorial");
   Book1.book_id = 6495407;

   /* 输出 Book1 信息 */
   printf( "Book 1 title : %s\n", Book1.title);
   printf( "Book 1 author : %s\n", Book1.author);
   printf( "Book 1 subject : %s\n", Book1.subject);
   printf( "Book 1 book_id : %d\n", Book1.book_id);
}

可以把结构作为函数参数，传参方式与其他类型的变量或指针类似。您可以使用上面实例中的方式来访问结构变量。

void printBook( struct Books book )
{
   printf( "Book title : %s\n", book.title);
   printf( "Book author : %s\n", book.author);
   printf( "Book subject : %s\n", book.subject);
   printf( "Book book_id : %d\n", book.book_id);
}

C是面向过程的语言，因此这个自定义类型只包含数据，不包含方法。

In computer science, encapsulation is the idea that related data is grouped together, and here we’ve encapsulated two pieces of information, name and number into the same data structure. The color of a pixel, with red, green, and blue values, might also be well-represented by a data structure as well.

3.2 typedef

C 语言提供了typedef关键字，您可以使用它来为类型取一个新的名字。下面的实例为单字节数字定义了一个术语BYTE：

typedef unsigned char BYTE;

在这个类型定义之后，标识符 BYTE 可作为类型unsigned char的缩写，例如：

BYTE b1, b2;

您也可以使用typedef来为用户自定义的数据类型取一个新的名字。例如，您可以对结构体使用typedef来定义一个新的数据类型名字，然后使用这个新的数据类型来直接定义结构变量，

typedef struct MYTAG{
  string name;
  string number;
}
person;

struct是一系列KV对的集合，不同的K可以有不同类型的V。

#include <stdio.h>
#include <cs50.h>
#include <string.h>

typedef struct MYTAG{
  string name;
  int number;
}
person;

void printPerson(person p){
    printf("Name: %s, ID: %d\n", p.name, p.number);
}

int main(void){
    person people[2];
    people[0].name = "Ray";
    people[0].number = 12345;
    people[1].name = "Allen";
    people[1].number = 54321;
    person other = {"James", 98765};
    printPerson(people[0]);
    printPerson(people[1]);
    printPerson(other);
}

执行结果：

(base) ubuntu@hadoop-node-1:~/C/w2$ ./person 
Name: Ray, ID: 12345
Name: Allen, ID: 54321
Name: James, ID: 98765

这上面相当于struct MYTAG和person等价。

3.3 typedef和#define

#define是 C 指令，用于为各种数据类型定义别名，与typedef类似，但是它们有以下几点不同：

• typedef仅限于为类型定义符号名称，#define不仅可以为类型定义别名，也能为数值定义别名，比如您可以定义 1 为 ONE。

• typedef是由编译器执行解释的，#define语句是由预编译器进行处理的。

3. 排序

• Selection sort：每一次选最小/大的，和剩下的第一个做交换。

  For i from 0 to n–1
      Find smallest number between numbers[i] and numbers[n-1]
      Swap smallest number with numbers[i]

• Bubble sort：不停两两交换，一轮可以把选最小/大的选到末尾。

  Repeat n-1 times
      For i from 0 to n–2
          If numbers[i] and numbers[i+1] out of order
              Swap them
      If no swaps
          Quit

4. 递归

C可以使用递归，以阶乘为例：

#include <stdio.h>

int factorial(int n){
    if (n == 1){
        return n;
    }
    return n * factorial(n - 1);
}

int main(void){
    printf("%d\n", factorial(10));
}

结果：

(base) ubuntu@hadoop-node-1:~/C/w2$ ./factorial
3628800

5. 合并排序

Time Complexity: $O(n\log n)$

Space Complexity: $O(n) + \log n$