week 5A & 5B

freyasnow 2016-08-30 11:43


1.pointer

  1. int* x;
    declare variable x,as a int pointer;
    没有malloc即没有初始化,所以没有存入实际意义的address,可能指向某些garbage value
  2. malloc 请求分配内存
    x=malloc((sizeof)int)
    x=(int*) malloc((sizeof)int)
    malloc return:the address of the chunk of 4 bytes
  3. *x = 42;
    go to the address(x point to),put 42 in there.
  4. *y = 15;
    error:因为y还没有初始化,即y还没有指向的地址。你说go to this address,但系统不知道这个address在哪里
  5. segmentation fault:touched 一部分不属于你的memory;array外延

2.cs50 library

  1. GetInt… functions from cs50 library
  2. scanf

    第二个参数: &x —地址
    目的:得到一些string并存在指定地址的memory中
  3. getc
    从文件中每次得到一个char
  4. array和pointer
    • array name = array的pointer
    • char buffer[16]; buffer就是这个array的pointer,存储第一个元素的地址
    • int* x=malloc(10* sizeof(int));
      x[9] = 0;
      这样就得到一个int array的pointer。而且也可以用x来表示array。其实int array pointer和int pointer本质相同,都是指向第一个int。
  5. unsigned int n = 0;
    即对于n而言符号无所谓,比如非负数,因此将存储正负号的bit用来存储更多的数字
  6. GetString的理念:初建buffer=32bits,根据键入字符数,如果大于buffer空间,加倍。realloc
    realloc 可以将已经存在的chunk of memory变得更大或更小
  7. sscanf
    sscanf(line,” %i %c”,&n,&c)
    得到string中的特定types的values

3.Memory and Valgrind

  1. 用完的memory如果没有give back:memory leak
    一般程序exit会自动给回;但如果程序运行了很长的时间,memory leak就会侵占很多空间
  2. valgrind —-leak-check=full ./program
  3. invalid write of size 4:表示4字节写入了不属于自己的memory(segmentation fault)
    40 bytes are definitely lost :没有还会(free(pointer))

4.linked lists

  1. array总是固定size的
  2. linked list是动态的。因为每一个box不需要在memory中相邻。每一个node记录了下一个node的memory 位置
  3. node:an element in a data structure
  4. typedef struct node 		{ 		    int n; 		    struct node* next; 		} 		node; 		
  5. self-referential;每一个node存储一个数值,及下一个node的地址。list中最后一个node指向null
  6. insert新的数值时候:注意顺序;如果不是最低端的node,直接改变指针会丢失其下方的所有node。
  7. trandoff:占据两倍空间;不能random access(array),不能直接访问any element。每次只能linear search。

5.Stacks & Queues

  1. stack,LIFO:last in ,first out 想想食堂的餐盘
  2. queue,FIFO:first in,first out

Week 5B

1.临时笔记

  1. 关于linked list
    • twice space
    • 不能直接访问一个数据。每次都必须从头开始,linear search
    • 优势:can dynamically resize it
  2. ptr -> n:ptr指针指向的struct中的n
    pt -> next:ptr指针指向的struct中的next指针 (而不是i++)
  3. 从size-1(index)知道最后一个数字,然后pop。再将size update - 1
    computer just forget where sth is(not delete it)
  4. stack(pointer),numbers中存入数字array的第一个byte的address
    因为malloc分配的内存是连续的
  5. queue:增加参数front,需要一直记住那个是begin。
    如果out of space,可能会转向最开始pop的数据。用modulo运算符。
    可以想成一个circle
  6. stack,memory:swap function return之后,main不知道它的任何工作,除非传回arguments by pointer
  7. char c [12] allocate memory for 12 bytes for 12 chars

2.linked list

  1. singly linked list
  2. 优势:dynamic size
  3. 劣势:失去了random access,只能iterate(即一一迭代,线性search)

3.hash table

  1. hash function:
    将input压缩成简短的index。类似分组。
    比如string,按照首字母index。apple(0),banana(1)
  2. 问题:collison(key hashes the same index 已经store a key)
    • linear probing:下一个空的index装入。很容易cluster。O(n)
    • separate chaining: hash之后,同一个index用linked list O(n/k)
  3. 一开始就设计好hash table,避免collison
    • 利用好key的所有info, 最大化可能的given hash value
    • uniformly distributes output across table
    • map similar keys to very different hash values
    • use only very fast operations

所有评论(0)

你的评论

课程全部笔记
Introduction to Computer Science

Introduction to Computer Science计算机科学导论

评分:
9 (27人评价)
时间:
时间自主
难度:
一般

京ICP证100430号    京网文[2015] 0609-239号    新出发京零字东150005号     京公网安备11010502007133号 ©2017果壳网

关于我们 新手指南