{"action":"created","issue":{"url":"https://api.github.com/repos/wujr5/c-and-cpp-language-learning/issues/46","labels_url":"https://api.github.com/repos/wujr5/c-and-cpp-language-learning/issues/46/labels{/name}","comments_url":"https://api.github.com/repos/wujr5/c-and-cpp-language-learning/issues/46/comments","events_url":"https://api.github.com/repos/wujr5/c-and-cpp-language-learning/issues/46/events","html_url":"https://github.com/wujr5/c-and-cpp-language-learning/issues/46","id":121979309,"number":46,"title":"软件：第13周额外作业","user":{"login":"ghostbody","id":8371330,"avatar_url":"https://avatars.githubusercontent.com/u/8371330?v=3","gravatar_id":"","url":"https://api.github.com/users/ghostbody","html_url":"https://github.com/ghostbody","followers_url":"https://api.github.com/users/ghostbody/followers","following_url":"https://api.github.com/users/ghostbody/following{/other_user}","gists_url":"https://api.github.com/users/ghostbody/gists{/gist_id}","starred_url":"https://api.github.com/users/ghostbody/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ghostbody/subscriptions","organizations_url":"https://api.github.com/users/ghostbody/orgs","repos_url":"https://api.github.com/users/ghostbody/repos","events_url":"https://api.github.com/users/ghostbody/events{/privacy}","received_events_url":"https://api.github.com/users/ghostbody/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/wujr5/c-and-cpp-language-learning/labels/%E8%BD%AF%E4%BB%B6%E7%8F%AD","name":"软件班","color":"006b75"}],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":6,"created_at":"2015-12-14T05:57:45Z","updated_at":"2015-12-19T04:26:25Z","closed_at":null,"body":"## Dynamic Memory Allocation\r\n\r\n### 1. Memory distribution map for a runtime program (very important for your 4-year study)\r\n![image](https://cloud.githubusercontent.com/assets/8371330/11582981/d162d666-9a8f-11e5-810c-c394d0b5318c.png)\r\n*From Professor Wan Hai's courseWare*\r\n\r\nThis is an overview for a program when it's loaded into the memory of the computer. There are totally 4 area for it, Code area, Static area, Heap and stack.\r\nCode area: This area is used to store program codes(instructions for cpu to execute)\r\nStatic area: This area is for the ralatively ‘static’ variables. Global variables, static local variables, static global variables are allocated in the static storage area.\r\nHeap: This area is management by the operating system and it's shared by other programs. You can get dynamic memory allocations in this area. **This is the area we need to use in list**\r\nStack: The stack is a area of memory that allocated by the compile. All variables declared in stack.\r\n**Notice that stack and heap in operating system are totally different in data structure**\r\n(注意：这里所说的堆和栈是操作系统的概念，跟数据结构中的堆和栈不同)\r\n\r\nFor example:\r\n```c\r\n#include <malloc.h>\r\nint main() {\r\n   int a;  // allocated in stack\r\n   int * b = (int *)malloc(sizeof(int));  // allocated in heap\r\n   free(b);\r\n   return;\r\n}\r\n```\r\n\r\nNotice that we have a operation before the program end. `free(b)`. Because we use the memory in the heap which means that these memory should be managed by the programmer. Even though the memory will be free by a mordern operating system, we should prevent memory lost (memory leak).\r\nFor example:\r\n```c\r\nint main() {\r\n   int * a = (int *)malloc(sizeof(int));  // allocated in heap, memory area1\r\n   int * a = (int *)malloc(sizeof(int));  // allocated in heap, memory area2\r\n   return;\r\n}\r\n```\r\nThe example above cause a memory leak problem because pointer point to another memory area and the previous memory area1 is lost.\r\n\r\n### 2. Malloc() to get memory from the heap\r\nThe two examples above show how to get memory in heap. In fact, we it's a serial of functions.\r\nC language with the memory of the functions are mainly calloc, alloca, malloc, free, realloc and so on.\r\n<1> alloca is the application of the stack to the memory, so there is no need to release.\r\n<2> malloc allocates memory is located in the heap, and there is no memory of the contents of the initial memory, so after the basic malloc, call the function memset to initialize this part of the memory space.\r\n<3> calloc will initialize this part of the memory, set to 0\r\n<4> realloc is the size of the memory of the malloc application.\r\n<5> The heap needs to be released by the function free.\r\n\r\nNotice that everytime you apply memory from heap, you should remember it and delete it(free) when your use of it is end.\r\n```c\r\nint main() {\r\n   int * a = malloc(sizeof(int));\r\n\r\n   // code using a\r\n\r\n   free(a);\r\n}\r\n```\r\n\r\nFunction Prototype\r\n```c\r\nextern void *malloc(unsigned int num_bytes);\r\n```\r\n\r\n注意，对于一个函数，一定要看函数原型，函数原型里面包含了这个函数接口功能的很多信息。\r\n这个函数的名称是malloc，动态分配内存\r\n参数是unsigned int num_bytes，意思是分配的内存的字节数。\r\n返回值是void 指针，理论是就是应该指向被分配的内存。\r\n\r\n由于返回的指针是一种泛型编程思想中的无类型指针，所以应该强制转换为你需要的类型。\r\n\r\n**注意：在一次malloc函数调用中，返回的一段内存是连续的**\r\n\r\n### 3. Memory Leak\r\n>From Wikipedia, the free encyclopedia\r\n>In computer science, a memory leak is a type of resource leak that occurs when a computer program incorrectly manages memory allocations[1] in such a way that memory which is no longer needed is not released. In object-oriented programming, a memory leak may happen when an object is stored in memory but cannot be accessed by the running code.[2] A memory leak has symptoms similar to a number of other problems (see below) and generally can only be diagnosed by a programmer with access to the program's source code.\r\n\r\n>Because they can exhaust available system memory as an application runs, memory leaks are often the cause of or a contributing factor to software aging.\r\n\r\n### Consequences\r\nA memory leak can diminish the performance of the computer by reducing the amount of available memory. Eventually, in the worst case, too much of the available memory may become allocated and all or part of the system or device stops working correctly, the application fails, or the system slows down vastly due to thrashing.\r\n\r\nMemory leaks may not be serious or even detectable by normal means. In modern operating systems, normal memory used by an application is released when the application terminates. This means that a memory leak in a program that only runs for a short time may not be noticed and is rarely serious.\r\n\r\nMuch more serious leaks include those:\r\n\r\nwhere the program runs for an extended time and consumes additional memory over time, such as background tasks on servers, but especially in embedded devices which may be left running for many years\r\nwhere new memory is allocated frequently for one-time tasks, such as when rendering the frames of a computer game or animated video\r\nwhere the program can request memory — such as shared memory — that is not released, even when the program terminates\r\nwhere memory is very limited, such as in an embedded system or portable device\r\nwhere the leak occurs within the operating system or memory manager\r\nwhen a system device driver causes the leak\r\nrunning on an operating system that does not automatically release memory on program termination. Often on such machines if memory is lost, it can only be reclaimed by a reboot, an example of such a system being AmigaOS.[citation neede\r\n\r\n>From 百度百科\r\n\r\n>内存泄漏也称作“存储渗漏”，用动态存储分配函数动态开辟的空间，在使用完毕后未释放，结果导致一直占据该内存单元。直到程序结束。（其实说白了就是该内存空间使用完毕之后未回收）即所谓内存泄漏。\r\n\r\n>内存泄漏形象的比喻是“操作系统可提供给所有进程的存储空间正在被某个进程榨干”，最终结果是程序运行时间越长，占用存储空间越来越多，最终用尽全部存储空间，整个系统崩溃。所以“内存泄漏”是从操作系统的角度来看的。这里的存储空间并不是指物理内存，而是指虚拟内存大小，这个虚拟内存大小取决于磁盘交换区设定的大小。由程序申请的一块内存，如果没有任何一个指针指向它，那么这块内存就泄漏了。\r\n\r\n>从用户使用程序的角度来看，内存泄漏本身不会产生什么危害，作为一般的用户，根本感觉不到内存泄漏的存在。真正有危害的是内存泄漏的堆积，这会最终消耗尽系统所有的内存。从这个角度来说，一次性内存泄漏并没有什么危害，因为它不会堆积，而隐式内存泄漏危害性则非常大，因为较之于常发性和偶发性内存泄漏它更难被检测到。\r\n\r\n**简单来讲，内存泄露就是动态分配的内存没有在使用完之后进行释放，导致内存垃圾堆积。**\r\n\r\n**这样的危害有可能直接让你的操作系统崩溃掉（可以自己做下实验）**\r\n\r\nFor example:\r\n```c\r\nint main() {\r\n    int * c = (int *)malloc(sizeof(int) * 100);\r\n    c = NULL;\r\n    while(1);\r\n}\r\n```\r\n\r\n上述代码分配了100个int类型大小的**连续**内存单元，我们可以通过这个方式分配动态数组。上述代码分配的就是可以理解成100个int的数组。\r\n\r\n运行上述程序，在运行到while(1)时候发生了内存泄露，因为原来动态分配的内存地址丢失了！你的程序无法再获得那100个在堆中申请的内存单元。可是这些内存单元仍然占据着内存，也就是内存垃圾。在编写动态分配的程序时，很容易出现这样的错误。正确做法是在这个指针不用的情况下，将其free。\r\n\r\n```c\r\nint main() {\r\n    int * c = (int *)malloc(sizeof(int) * 100);\r\n    free(c);\r\n    c = NULL;\r\n    while(1);\r\n}\r\n```\r\n\r\n有时候有些内存泄露是自己看不出来的，特别当函数变得复杂起来的时候。\r\n下列程序为**死亡程序**，可以试试运行看看自己电脑的内存变化。\r\n\r\n```c\r\n#include <stdio.h>\r\n#include <malloc.h>\r\nint main() {\r\n while(1) {\r\n    malloc(100);\r\n  }\r\n  return 0; \r\n}\r\n```\r\n\r\n### 3. List（链表或线性表）\r\n\r\n#### An introduction to List\r\n>In computer science, a list or sequence is an abstract data type that represents an ordered sequence of values, where the same value may occur more than once. An instance of a list is a computer representation of the mathematical concept of a finite sequence; the (potentially) infinite analog of a list is a stream.[1]:§3.5 Lists are a basic example of containers, as they contain other values. If the same value occurs multiple times, each occurrence is considered a distinct item.\r\n>![](https://upload.wikimedia.org/wikipedia/commons/thumb/3/37/Singly_linked_list.png/220px-Singly_linked_list.png)\r\n\r\n>A singly linked list structure, implementing a list with 3 integer elements.\r\nThe name list is also used for several concrete data structures that can be used to implement abstract lists, especially linked lists.\r\n\r\n>Many programming languages provide support for list data types, and have special syntax and semantics for lists and list operations. A list can often be constructed by writing the items in sequence, separated by commas, semicolons, or spaces, within a pair of delimiters such as parentheses '()', brackets '[]', braces '{}', or angle brackets '<>'. Some languages may allow list types to be indexed or sliced like array types, in which case the data type is more accurately described as an array. In object-oriented programming languages, lists are usually provided as instances of subclasses of a generic \"list\" class, and traversed via separate iterators. List data types are often implemented using array data structures or linked lists of some sort, but other data structures may be more appropriate for some applications. In some contexts, such as in Lisp programming, the term list may refer specifically to a linked list rather than an array.\r\n\r\n>In type theory and functional programming, abstract lists are usually defined inductively by two operations: nil that yields the empty list, and cons, which adds an item at the beginning of a list.[2]\r\n\r\n*From wikipedia*\r\n\r\n\r\nThe operations about list are appending, deleting, modifying, querying.\r\n\r\nwe use this simple list again:\r\n![](https://upload.wikimedia.org/wikipedia/commons/thumb/3/37/Singly_linked_list.png/220px-Singly_linked_list.png)\r\n\r\n1. If delete the second node:\r\n```c\r\nnode* save = head->next;\r\nhead->next = head->next->next;\r\nfree(save);\r\n```\r\n\r\n2.If append a node at the end of the list\r\n```c\r\nnode* last = head;\r\nwhile(last->next != NULL) {\r\n    last = last->next;\r\n}\r\n\r\nlast->next = (node*)malloc(sizeof(node));\r\nlast->next->data = data;\r\nlast->next->next = NULL;\r\n```\r\n\r\n3.Traversal\r\n```c\r\nnode * temp = head;\r\nwhile(temp != NULL) {\r\n    Traversal(temp);\r\n    temp = temp->next;\r\n}\r\n```\r\n\r\n### Deep Thinking(120pts, 20 for each)\r\n**1.Look at the following function:**\r\n```c\r\nstatic void myFunction() { int a; }\r\n```\r\n**(1) Which area in memory does the function store? And which dose the variable `int a`?**\r\n**(2) What's the advantages of using static functions?**\r\n\r\n**2. Look at the following program which is attempt to allocate a dynamic array.**\r\n```c\r\n#include <malloc.h>\r\n\r\nint main() {\r\n    char ** strs;\r\n    int n ,m;\r\n    int i;\r\n\r\n    scanf(\"%d%d\", &n, &m);\r\n    \r\n    strs = (char **)malloc(sizeof(char *) * n);\r\n\r\n    for(i = 0; i < n; i++) {\r\n        strs[i] = (char *)malloc(sizeof(char) * m);\r\n    }\r\n\r\n\r\n   // code for the 2d array\r\n   // free operations omited\r\n    return 0;\r\n}\r\n\r\n```\r\n**Can we create an 2D array in the heap using this way? Give your explanations and give another way that can allocate a dynamic 2D array**\r\n\r\n**3.Why use a list instead of an array? What's the advantages and disadvantages of them respectively?**\r\n\r\n**4.** \r\n(1)Why is it necessary to have a heap, i.e. why not use stack only?\r\n(2)What's the max size of the stack or the heap for a c program in your computer? Can you revise it?\r\n(3)Will deep recursive program really lead to stack overflow?Why? (The answer is no)\r\n\r\n**5.(optional) How to use an array to create a list know as a static list in logic?**\r\nFor example:\r\n```c\r\nnode a[100];\r\nhead = a[0];\r\na[0]->next = 2;   // an array index\r\n```\r\n\r\n**6. (optional) Think about that can we use an int_64 (long long) to create a list using the high 32 bits to store an int data and use the low 32 bits to store the next address pointer? If so, write a program to test. If not, write a program to explain your reasons.**\r\n\r\n## Deadline and Submit\r\nDec 19th, 2015 18:00\r\n\r\nSubmit to ftp\r\n\r\nFilename : 13331314_叶嘉祺_DMA.pdf\r\n\r\n"},"comment":{"url":"https://api.github.com/repos/wujr5/c-and-cpp-language-learning/issues/comments/165946583","html_url":"https://github.com/wujr5/c-and-cpp-language-learning/issues/46#issuecomment-165946583","issue_url":"https://api.github.com/repos/wujr5/c-and-cpp-language-learning/issues/46","id":165946583,"user":{"login":"DengXj95","id":15196820,"avatar_url":"https://avatars.githubusercontent.com/u/15196820?v=3","gravatar_id":"","url":"https://api.github.com/users/DengXj95","html_url":"https://github.com/DengXj95","followers_url":"https://api.github.com/users/DengXj95/followers","following_url":"https://api.github.com/users/DengXj95/following{/other_user}","gists_url":"https://api.github.com/users/DengXj95/gists{/gist_id}","starred_url":"https://api.github.com/users/DengXj95/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/DengXj95/subscriptions","organizations_url":"https://api.github.com/users/DengXj95/orgs","repos_url":"https://api.github.com/users/DengXj95/repos","events_url":"https://api.github.com/users/DengXj95/events{/privacy}","received_events_url":"https://api.github.com/users/DengXj95/received_events","type":"User","site_admin":false},"created_at":"2015-12-19T04:26:24Z","updated_at":"2015-12-19T04:26:24Z","body":"交到ftp的哪个文件夹下？"}}