简单链表
Introduction¶
List a a kind of data structure that is a linear collection of data elements, called nodes pointing to the next node by means of pointer. It is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of data and a reference (in other words, a link) to the next node in the sequence; more complex variants add additional links. This structure allows for efficient insertion or removal of elements from any position in the sequence.
List Operation¶
1. Insert¶
2.Deletion¶
3. Element Access¶
Some Contracts¶
1. Position for Insertion¶
2. Position for Deletion¶
Some Knowledge In C for Last Semester¶
1. Memory distribution map for a runtime program (very important for your 4-year study)¶
From Professor Wan Hai's courseWare
This 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. Code area: This area is used to store program codes(instructions for cpu to execute) Static area: This area is for the ralatively ‘static’ variables. Global variables, static local variables, static global variables are allocated in the static storage area. Heap: 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 Stack: The stack is a area of memory that allocated by the compile. All variables declared in stack. Notice that stack and heap in operating system are totally different in data structure (注意：这里所说的堆和栈是操作系统的概念，跟数据结构中的堆和栈不同)
For example:
#include <malloc.h>
int main() {
int a; // allocated in stack
int * b = (int *)malloc(sizeof(int)); // allocated in heap
free(b);
return;
}
```
Notice 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).
For example:
```c
int main() {
int * a = (int *)malloc(sizeof(int)); // allocated in heap, memory area1
int * a = (int *)malloc(sizeof(int)); // allocated in heap, memory area2
return;
}
The example above cause a memory leak problem because pointer point to another memory area and the previous memory area1 is lost.
2. Malloc() to get memory from the heap¶
The two examples above show how to get memory in heap. In fact, we it's a serial of functions. C language with the memory of the functions are mainly calloc, alloca, malloc, free, realloc and so on. <1> alloca is the application of the stack to the memory, so there is no need to release. <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. <3> calloc will initialize this part of the memory, set to 0 <4> realloc is the size of the memory of the malloc application. <5> The heap needs to be released by the function free.
Notice that everytime you apply memory from heap, you should remember it and delete it(free) when your use of it is end.
int main() {
int * a = malloc(sizeof(int));
// code using a
free(a);
}
Function Prototype
extern void *malloc(unsigned int num_bytes);
注意，对于一个函数，一定要看函数原型，函数原型里面包含了这个函数接口功能的很多信息。 这个函数的名称是malloc，动态分配内存 参数是unsigned int num_bytes，意思是分配的内存的字节数。 返回值是void 指针，理论是就是应该指向被分配的内存。
由于返回的指针是一种泛型编程思想中的无类型指针，所以应该强制转换为你需要的类型。
注意：在一次malloc函数调用中，返回的一段内存是连续的
3. Memory Leak¶
From Wikipedia, the free encyclopedia 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.
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.
Consequences¶
A 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.
Memory 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.
Much more serious leaks include those:
where 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 where new memory is allocated frequently for one-time tasks, such as when rendering the frames of a computer game or animated video where the program can request memory — such as shared memory — that is not released, even when the program terminates where memory is very limited, such as in an embedded system or portable device where the leak occurs within the operating system or memory manager when a system device driver causes the leak running 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
From 百度百科
内存泄漏也称作“存储渗漏”，用动态存储分配函数动态开辟的空间，在使用完毕后未释放，结果导致一直占据该内存单元。直到程序结束。（其实说白了就是该内存空间使用完毕之后未回收）即所谓内存泄漏。
内存泄漏形象的比喻是“操作系统可提供给所有进程的存储空间正在被某个进程榨干”，最终结果是程序运行时间越长，占用存储空间越来越多，最终用尽全部存储空间，整个系统崩溃。所以“内存泄漏”是从操作系统的角度来看的。这里的存储空间并不是指物理内存，而是指虚拟内存大小，这个虚拟内存大小取决于磁盘交换区设定的大小。由程序申请的一块内存，如果没有任何一个指针指向它，那么这块内存就泄漏了。
从用户使用程序的角度来看，内存泄漏本身不会产生什么危害，作为一般的用户，根本感觉不到内存泄漏的存在。真正有危害的是内存泄漏的堆积，这会最终消耗尽系统所有的内存。从这个角度来说，一次性内存泄漏并没有什么危害，因为它不会堆积，而隐式内存泄漏危害性则非常大，因为较之于常发性和偶发性内存泄漏它更难被检测到。
简单来讲，内存泄露就是动态分配的内存没有在使用完之后进行释放，导致内存垃圾堆积。
这样的危害有可能直接让你的操作系统崩溃掉（可以自己做下实验）
For example:
int main() {
int * c = (int *)malloc(sizeof(int) * 100);
c = NULL;
while(1);
}
上述代码分配了100个int类型大小的连续内存单元，我们可以通过这个方式分配动态数组。上述代码分配的就是可以理解成100个int的数组。
运行上述程序，在运行到while(1)时候发生了内存泄露，因为原来动态分配的内存地址丢失了！你的程序无法再获得那100个在堆中申请的内存单元。可是这些内存单元仍然占据着内存，也就是内存垃圾。在编写动态分配的程序时，很容易出现这样的错误。正确做法是在这个指针不用的情况下，将其free。
int main() {
int * c = (int *)malloc(sizeof(int) * 100);
free(c);
c = NULL;
while(1);
}
有时候有些内存泄露是自己看不出来的，特别当函数变得复杂起来的时候。 下列程序为死亡程序，可以试试运行看看自己电脑的内存变化。
#include <stdio.h>
#include <malloc.h>
int main() {
while(1) {
malloc(100);
}
return 0;
}
3. List（链表或线性表）¶
An introduction to List¶
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.
A singly linked list structure, implementing a list with 3 integer elements. The name list is also used for several concrete data structures that can be used to implement abstract lists, especially linked lists.
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.
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]
From wikipedia
The operations about list are appending, deleting, modifying, querying.
we use this simple list again:
-
If delete the second node:
node* save = head->next; head->next = head->next->next; free(save);
2.If append a node at the end of the list
node* last = head;
while(last->next != NULL) {
last = last->next;
}
last->next = (node*)malloc(sizeof(node));
last->next->data = data;
last->next->next = NULL;
3.Traversal
node * temp = head;
while(temp != NULL) {
Traversal(temp);
temp = temp->next;
}
Deep Thinking(120pts, 20 for each)¶
1.Look at the following function:
static void myFunction() { int a; }
(1) Which area in memory does the function store? And which dose the variable int a?
function store : Code Area
variable 'int a': (function) stack
(2) What's the advantages of using static functions?
static says the function has internal linkage. This means it will not be linked with other uses of the same identifier in other files (translation units). For example, suppose in Tree.c I have a function that operates on Tree structures, and I have some local subroutine called UpdateNode that operates on part of the Tree. Further suppose that in List.c, I have a function that operates on List structures, and it also has some local subroutine called UpdateNode that is just for List structures, not for Tree structures. If I left both of these subroutines with external linkage, the linker would complain about multiple definitions. By marking them with internal linkage with static, this problem is avoided. From stack overflow
2. Look at the following program which is attempt to allocate a dynamic array.
#include <malloc.h>
int main() {
char ** strs;
int n ,m;
int i;
scanf("%d%d", &n, &m);
strs = (char **)malloc(sizeof(char *) * n);
for(i = 0; i < n; i++) {
strs[i] = (char *)malloc(sizeof(char) * m);
}
// code for the 2d array
// free operations omited
return 0;
}
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 No, the 2D dynamic array is discontinuous in 1D memory space which does not fit the accurate 2D array definition.
issues:
1. When call memset or other memory operation on the whole block of memory, you can not get your expected result.
2. When pass the array into a function as parameter.
Look at the following program:
#include <malloc.h>
void test(char strs[][20], int m, int n) {
int i, j;
for(i = 0; i < m; i++) {
for(j = 0; j < n; j++) {
printf("%p ", &strs[i][j]);
}
printf("\n");
}
}
int main() {
char ** strs;
int n ,m;
int i, j;
scanf("%d%d", &n, &m);
strs = (char **)malloc(sizeof(char *) * n);
printf("%p\n", strs);
for(i = 0; i < n; i++) {
strs[i] = (char *)malloc(sizeof(char) * m);
}
for(i = 0; i < n; i++) {
for(j = 0; j < m; j++) {
printf("%p ", &strs[i][j]);
}
printf("\n");
}
printf("\n");
test(strs, 10, 20);
printf("\n");
// free operations omited
return 0;
}
Result:
10 20 0xe04010 0xe04070 0xe04071 0xe04072 0xe04073 0xe04074 0xe04075 0xe04076 0xe04077 0xe04078 0xe04079 0xe0407a 0xe0407b 0xe0407c 0xe0407d 0xe0407e 0xe0407f 0xe04080 0xe04081 0xe04082 0xe04083 0xe04090 0xe04091 0xe04092 0xe04093 0xe04094 0xe04095 0xe04096 0xe04097 0xe04098 0xe04099 0xe0409a 0xe0409b 0xe0409c 0xe0409d 0xe0409e 0xe0409f 0xe040a0 0xe040a1 0xe040a2 0xe040a3 0xe040b0 0xe040b1 0xe040b2 0xe040b3 0xe040b4 0xe040b5 0xe040b6 0xe040b7 0xe040b8 0xe040b9 0xe040ba 0xe040bb 0xe040bc 0xe040bd 0xe040be 0xe040bf 0xe040c0 0xe040c1 0xe040c2 0xe040c3 0xe040d0 0xe040d1 0xe040d2 0xe040d3 0xe040d4 0xe040d5 0xe040d6 0xe040d7 0xe040d8 0xe040d9 0xe040da 0xe040db 0xe040dc 0xe040dd 0xe040de 0xe040df 0xe040e0 0xe040e1 0xe040e2 0xe040e3 0xe040f0 0xe040f1 0xe040f2 0xe040f3 0xe040f4 0xe040f5 0xe040f6 0xe040f7 0xe040f8 0xe040f9 0xe040fa 0xe040fb 0xe040fc 0xe040fd 0xe040fe 0xe040ff 0xe04100 0xe04101 0xe04102 0xe04103 0xe04110 0xe04111 0xe04112 0xe04113 0xe04114 0xe04115 0xe04116 0xe04117 0xe04118 0xe04119 0xe0411a 0xe0411b 0xe0411c 0xe0411d 0xe0411e 0xe0411f 0xe04120 0xe04121 0xe04122 0xe04123 0xe04130 0xe04131 0xe04132 0xe04133 0xe04134 0xe04135 0xe04136 0xe04137 0xe04138 0xe04139 0xe0413a 0xe0413b 0xe0413c 0xe0413d 0xe0413e 0xe0413f 0xe04140 0xe04141 0xe04142 0xe04143 0xe04150 0xe04151 0xe04152 0xe04153 0xe04154 0xe04155 0xe04156 0xe04157 0xe04158 0xe04159 0xe0415a 0xe0415b 0xe0415c 0xe0415d 0xe0415e 0xe0415f 0xe04160 0xe04161 0xe04162 0xe04163 0xe04170 0xe04171 0xe04172 0xe04173 0xe04174 0xe04175 0xe04176 0xe04177 0xe04178 0xe04179 0xe0417a 0xe0417b 0xe0417c 0xe0417d 0xe0417e 0xe0417f 0xe04180 0xe04181 0xe04182 0xe04183 0xe04190 0xe04191 0xe04192 0xe04193 0xe04194 0xe04195 0xe04196 0xe04197 0xe04198 0xe04199 0xe0419a 0xe0419b 0xe0419c 0xe0419d 0xe0419e 0xe0419f 0xe041a0 0xe041a1 0xe041a2 0xe041a3 0xe04010 0xe04011 0xe04012 0xe04013 0xe04014 0xe04015 0xe04016 0xe04017 0xe04018 0xe04019 0xe0401a 0xe0401b 0xe0401c 0xe0401d 0xe0401e 0xe0401f 0xe04020 0xe04021 0xe04022 0xe04023 0xe04024 0xe04025 0xe04026 0xe04027 0xe04028 0xe04029 0xe0402a 0xe0402b 0xe0402c 0xe0402d 0xe0402e 0xe0402f 0xe04030 0xe04031 0xe04032 0xe04033 0xe04034 0xe04035 0xe04036 0xe04037 0xe04038 0xe04039 0xe0403a 0xe0403b 0xe0403c 0xe0403d 0xe0403e 0xe0403f 0xe04040 0xe04041 0xe04042 0xe04043 0xe04044 0xe04045 0xe04046 0xe04047 0xe04048 0xe04049 0xe0404a 0xe0404b 0xe0404c 0xe0404d 0xe0404e 0xe0404f 0xe04050 0xe04051 0xe04052 0xe04053 0xe04054 0xe04055 0xe04056 0xe04057 0xe04058 0xe04059 0xe0405a 0xe0405b 0xe0405c 0xe0405d 0xe0405e 0xe0405f 0xe04060 0xe04061 0xe04062 0xe04063 0xe04064 0xe04065 0xe04066 0xe04067 0xe04068 0xe04069 0xe0406a 0xe0406b 0xe0406c 0xe0406d 0xe0406e 0xe0406f 0xe04070 0xe04071 0xe04072 0xe04073 0xe04074 0xe04075 0xe04076 0xe04077 0xe04078 0xe04079 0xe0407a 0xe0407b 0xe0407c 0xe0407d 0xe0407e 0xe0407f 0xe04080 0xe04081 0xe04082 0xe04083 0xe04084 0xe04085 0xe04086 0xe04087 0xe04088 0xe04089 0xe0408a 0xe0408b 0xe0408c 0xe0408d 0xe0408e 0xe0408f 0xe04090 0xe04091 0xe04092 0xe04093 0xe04094 0xe04095 0xe04096 0xe04097 0xe04098 0xe04099 0xe0409a 0xe0409b 0xe0409c 0xe0409d 0xe0409e 0xe0409f 0xe040a0 0xe040a1 0xe040a2 0xe040a3 0xe040a4 0xe040a5 0xe040a6 0xe040a7 0xe040a8 0xe040a9 0xe040aa 0xe040ab 0xe040ac 0xe040ad 0xe040ae 0xe040af 0xe040b0 0xe040b1 0xe040b2 0xe040b3 0xe040b4 0xe040b5 0xe040b6 0xe040b7 0xe040b8 0xe040b9 0xe040ba 0xe040bb 0xe040bc 0xe040bd 0xe040be 0xe040bf 0xe040c0 0xe040c1 0xe040c2 0xe040c3 0xe040c4 0xe040c5 0xe040c6 0xe040c7 0xe040c8 0xe040c9 0xe040ca 0xe040cb 0xe040cc 0xe040cd 0xe040ce 0xe040cf 0xe040d0 0xe040d1 0xe040d2 0xe040d3 0xe040d4 0xe040d5 0xe040d6 0xe040d7
This is the Problem.
One possible way:
strs=(char (*)[10])malloc(n*10*sizeof(int)); // n rows and 10 cols
3.Why use a list instead of an array? What's the advantages and disadvantages of them respectively? Both store a sequence of elements, but using different techniques. An array stores elements in successive order in memory, i.e. it looks like follows:
-------------------------------------------------------------------------------------- | item 1 | item 2 | item 3 | ... ... | item x | //here comes other stuff --------------------------------------------------------------------------------------
This means, elements are one after another consecutive in memory.
A ((doubly) linked) list, on the other hand, stores the items the following way: It creates an own "list item" for each element; this "list item" holds the actual element and a pointer/reference/hint/etc to the next "list item". If it is doubly linked, it also contains a pointer/reference/hint/etc to the previous "list item":
------------
------------ ---------- | item 4 |
| item 1 | | item 2 | | next ---+----...
| next ---+------->| next | ------------
------------ ---+------ ^
| |
| |
v |
---------- |
| item 3 | |
| next --+---+
----------
Both store a sequence of elements, but using different techniques.
An array stores elements in successive order in memory, i.e. it looks like follows:
-------------------------------------------------------------------------------------- | item 1 | item 2 | item 3 | ... ... | item x | //here comes other stuff --------------------------------------------------------------------------------------
This means, elements are one after another consecutive in memory.
A ((doubly) linked) list, on the other hand, stores the items the following way: It creates an own "list item" for each element; this "list item" holds the actual element and a pointer/reference/hint/etc to the next "list item". If it is doubly linked, it also contains a pointer/reference/hint/etc to the previous "list item":
------------
------------ ---------- | item 4 |
| item 1 | | item 2 | | next ---+----...
| next ---+------->| next | ------------
------------ ---+------ ^
| |
| |
v |
---------- |
| item 3 | |
| next --+---+
----------
This means, the elements can be spread all over the memory and are not stored at specific memory locations.
Now that we know this, we can compare some usual operations on sequences of elements:
-
Accessing an element at a specific index: Using an array, we simply compute the offset for this index and have the element at the index. This is very cheap. With a list on the other hand, we do not know a priori where the element at index is stored (since all elements can be anywhere in memory), so we have to walk the list item by item until we find the element at the index. This is an expensive operation.
-
Adding a new element at the end of the sequence: Using an array this can lead to the following problem: Arrays are usually of fixed size, so if we have the situation that our array is already completely filled (see //here comes other stuff), we probably cant put the new element there because there might already be something else. So, maybe we have to copy the whole array. However, if the array is not filled, we can simply put the element there. Using a list, we have to generate a new "list item", put the element into it and set the next pointer of the currently last element to this new list item. Usually, we store a reference to the currently last element so that we don't have to search through the whole list to find it. Thus, inserting a new element is no real problem with lists.
-
Adding a new element somewhere in the middle: Let's first consider arrays: here, we might get into the following situation: We have an array with elements 1 to 1000:
1 | 2 | 3 | 4 | 5 | 6 | … | 999 | 1000 | free | free
Now, we want to insert 4.5 between 4 and 5: This means, we have to move all elements from 5 to 1000 one position right in order to make space for the 4.5:
1 | 2 | 3 | 4 | free | 5 | 6 | ... | 999 | 1000 | free
||
vv
1 | 2 | 3 | 4 | 4.5 | 5 | 6 | ... | 999 | 1000 | free
Moving all these elements, is a very expensive operation. So better don't do this too often. Now we consider, how a list can perform this task: Let's say we have currently the following list:
1 -> 2 -> 3 -> 4 -> 5 -> ... -> 999 -> 1000
Again, we want to insert 4.5 between 4 and 5. This can be done very easily: We generate a new list item and update the pointers/references:
1 -> 2 -> 3 -> 4 5 -> ... -> 999 -> 1000
| ^
+-> 4.5 -+
We have simply created a new list element and generated sort of "bypass" to insert it - very cheap (as long as we have a pointer/reference to the list item the new element will be inserted after).
So, let's sum up: Linked lists are really nice when it comes to inserting at random positions (as long as you have a pointer to the adequate list item). If your operation involves adding lots of elements dynamically and traversing all elements anyway, a list might be a good choice.
An array is very good when it comes to index accesses. If your application needs to access elements at specific positions very often, you should rather use an array.
Notable things:
-
Solving the fixed-size problem for arrays: As mentioned before, (raw) arrays are usually of fixed size. However, this problem is nowadays no real point anymore, since almost all programming languages provide mechanisms to generate arrays that grow (and possibly shrink) dynamically - just as needed. This growing and shrinking can be implemented such that we have amortized runtime of O(1) for inserting and removing elements (at the end of the array) and such that the programmer doesn't have to call grow and shrink explicitly.
-
Since lists provide such nice properties for insertions, they can be used as underlying data structures for search trees, etc. I.e. you construct a search tree, whose lowest level consists of the linked list.
4. (1)Why is it necessary to have a heap, i.e. why not use stack only? The stack is the memory set aside as scratch space for a thread of execution. When a function is called, a block is reserved on the top of the stack for local variables and some bookkeeping data. When that function returns, the block becomes unused and can be used the next time a function is called. The stack is always reserved in a LIFO (last in first out) order; the most recently reserved block is always the next block to be freed. This makes it really simple to keep track of the stack; freeing a block from the stack is nothing more than adjusting one pointer.
The heap is memory set aside for dynamic allocation. Unlike the stack, there's no enforced pattern to the allocation and deallocation of blocks from the heap; you can allocate a block at any time and free it at any time. This makes it much more complex to keep track of which parts of the heap are allocated or free at any given time; there are many custom heap allocators available to tune heap performance for different usage patterns.
Each thread gets a stack, while there's typically only one heap for the application (although it isn't uncommon to have multiple heaps for different types of allocation).
To answer your questions directly:
-
To what extent are they controlled by the OS or language runtime? The OS allocates the stack for each system-level thread when the thread is created. Typically the OS is called by the language runtime to allocate the heap for the application.
-
What is their scope? The stack is attached to a thread, so when the thread exits the stack is reclaimed. The heap is typically allocated at application startup by the runtime, and is reclaimed when the application (technically process) exits.
-
What determines the size of each of them? The size of the stack is set when a thread is created. The size of the heap is set on application startup, but can grow as space is needed (the allocator requests more memory from the operating system).
-
What makes one faster? The stack is faster because the access pattern makes it trivial to allocate and deallocate memory from it (a pointer/integer is simply incremented or decremented), while the heap has much more complex bookkeeping involved in an allocation or free. Also, each byte in the stack tends to be reused very frequently which means it tends to be mapped to the processor's cache, making it very fast. Another performance hit for the heap is that the heap, being mostly a global resource, typically has to be multi-threading safe, i.e. each allocation and deallocation needs to be - typically - synchronized with "all" other heap accesses in the program.
(2)What's the max size of the stack or the heap for a c program in your computer? Can you revise it? In linux,
xinyuan@xinyuan-pc:~/Desktop/testAll$ ulimit -a core file size (blocks, -c) 0 data seg size (kbytes, -d) unlimited scheduling priority (-e) 0 file size (blocks, -f) unlimited pending signals (-i) 15333 max locked memory (kbytes, -l) 64 max memory size (kbytes, -m) unlimited open files (-n) 1024 pipe size (512 bytes, -p) 8 POSIX message queues (bytes, -q) 819200 real-time priority (-r) 0 stack size (kbytes, -s) 8192 cpu time (seconds, -t) unlimited max user processes (-u) 15333 virtual memory (kbytes, -v) unlimited file locks (-x) unlimited
revise stack example
ulimit -s 1000
max heap size is usually the virtual memory of your computer.
(3)Will deep recursive program really lead to stack overflow?Why? (The answer is no)
No, not really. The following program will cause stack overflow in normal mode compile.
But if we add compile parameter gcc -O1 -foptimize-sibling-calls recursion.c, there will not be stack overflow.
#include <stdio.h>
typedef unsigned long long int RES;
RES recursion(RES a) {
if(a == 1000000000) {
return a;
} else {
return recursion(a+1);
}
}
int main(int argc, char const *argv[]) {
recursion(0);
return 0;
}
Also we can calculate how large is it in one function stack, think about it.
5.(optional) How to use an array to create a list know as a static list in logic? For example:
node a[100]; head = a[0]; a[0]->next = 2; // an array index