The advantage of list

链表的优点

       尽管一列数据可以存储在数组中,但是存储在链表中有更多的优点。特别是在要表示的数据元素的个数事先未知的情况下,链表就大有用武之地了,由于链表时动态变化的,所以,链表的长度可以根据需要增加或缩短。而对于数组二样,一旦内存分配完毕,数组的大小就不能改变了。为数组分配的存储空间在程序运行期间全部是被占用的,而链表只有在系统没有足够的内存空间来满足动态内存分配的要求时,才会出现全部内存空间都被占用的情况。

       链表的节点在内存中通常都不是连续存储的,但是在逻辑上,链表的节点是以连续的形式出现的。

       使用动态内存分配(而不是固定长度的数组)来实现数据结构在程序执行过程中增大或缩小,这能够节约内存空间。但是,引入的指针也要占用内存空间,同时,动态内存分配会带来额外的函数调用开销。

示例:

//operating and mainting a list

#include <stdio.h>

#include <stdlib.h>



//self-referential structure

struct listNode

{

char data;//each listNode contains a character

struct listNode *nextPtr;//pointer to next node

};



typedef struct listNode ListNode;//synonym for struct listNode

typedef ListNode *ListNodePtr;//synonym for ListNode



//prototypes

void insert(ListNodePtr *sPtr, char value);

char delete(ListNodePtr *sPtr, char value);

int isEmpty(ListNodePtr sPtr);

void printList(ListNodePtr currentPtr);

void instructions(void);



int main(void)

{

ListNodePtr startPtr = NULL;//initially there are no nodes

int choice;//user's choice

char item;//char entered by user



instructions();//display the menu

printf("? ");

scanf("%d",&choice);



//loop while user does not choose 3

while(choice != 3)

{

switch(choice)

{

case 1:

printf("Enter a character: ");

scanf("\n%c",&item);

insert(&startPtr,item);//insert item in list

printList(startPtr);

break;

case 2://delete an element

//if list is not empty

if(!isEmpty(startPtr))

{

printf("Enter character to be deleted: ");

scanf("\n%c",&item);



//if character is found , remove it

if(delete(&startPtr,item))//remove item

{

printf("%c deleted.\n",item);

printList(startPtr);

}

else

{

printf("%c not found.\n\n",item);

}

}

else

printf("List is empty.\n\n");

break;

default:

printf("Invalid choice.\n\n");

instructions();

break;

}



printf("? ");

scanf("%d",&choice);

}

printf("End of run.\n");



return 0;//indicates successful termination.

}



void instructions(void)

{

printf("Enter your choice: \n"

" 1 to insert an element into the list.\n"

" 2 to delete an element from the list.\n"

" 3 to end.\n");

}



void insert(ListNodePtr *sPtr, char value)

{

ListNodePtr newPtr;//pointer to new node

ListNodePtr previousPtr;//pointer to previous node in list

ListNodePtr currentPtr;//pointer to current node in list



newPtr = malloc(sizeof(ListNode));//create node



if(newPtr != NULL)//is space available

{

newPtr -> data = value;//place value in node

newPtr -> nextPtr = NULL;//node dose not link to another node



previousPtr = NULL;

currentPtr = *sPtr;



//loop to find the correct location in the list

while(currentPtr != NULL && value > currentPtr -> data)

{

previousPtr = currentPtr;//walk to

currentPtr = currentPtr -> nextPtr;//next node

}



if(previousPtr == NULL)

{

newPtr -> nextPtr = *sPtr;

*sPtr = newPtr;

}

else

{

previousPtr -> nextPtr = newPtr;

newPtr -> nextPtr = currentPtr;

}

}

else

{

printf("%c not inserted . No memory available.\n",value);

}

}



//delete a list emlement

char delete(ListNodePtr * sPtr, char value)

{

ListNodePtr previousPtr;

ListNodePtr currentPtr;

ListNodePtr tempPtr;



//delete first node

if(value == (*sPtr) -> data)

{

tempPtr = *sPtr;

*sPtr = (*sPtr)->nextPtr;

free(tempPtr);

return value;

}

else

{

previousPtr = *sPtr;

currentPtr = (*sPtr)->nextPtr;



//loop to find the correct location in the list

while(currentPtr != NULL && currentPtr->data != value)

{

previousPtr = currentPtr;

currentPtr = currentPtr -> nextPtr;

}



if(currentPtr != NULL)

{

tempPtr = currentPtr;

previousPtr -> nextPtr = currentPtr -> nextPtr;

free(tempPtr);

return value;

}

}

return '\0';

}



//return 1 if the list is empty, 0 otherwise

int isEmpty(ListNodePtr sPtr)

{

return sPtr == NULL;

}



void printList(ListNodePtr currentPtr)

{

if(currentPtr == NULL)

{

printf("List is empty.\n\n");

}

else

{

printf("The list is : \n");



while(currentPtr != NULL)

{

printf("%c --> ",currentPtr->data);

currentPtr = currentPtr->nextPtr;

}

printf("NULL\n\n");

}

}



clip_image002

the style of program

 程序的风格

clip_image001

程序设计风格的原则根源于由实际经验中得到的常识,它不是随意的规则或者处方。代码应该是清楚的和简单的具有直截了当的逻辑、自然的表达式、通行的语言使用方式、有意义的名字和有帮助作用的注释等,应该避免耍小聪明的花招,不使用非正规的结构。一致性是非常重要的东西,如果大家都坚持同样的风格,其他人就会发现你的代码很容易读,你也容易读懂其他人的。

名字

全局变量使用具有说明性的名字,局部变量用短名字。

三元操作符?:的妙用

       比如我们打印有多少个条目的时候,中文到时没有什么差别,而对于英语就会涉及到单复数的区别,此时就可以使用如下所示的三元符来自动判断是否需要加上复数的s

clip_image003

注意malloc的使用

clip_image004

strlen求出的值没有计入串结尾的\ 0字符,而strcpy却将复制它。所以这里分配的空间实际上是不够的,这将使strcpy的写入超过所分配空间的界限。习惯写法是:

clip_image006

所以,如果没有+1,就要特别注意了。

函数宏

clip_image008

老的C语言程序员中有一种倾向,就是把很短的执行频繁的计算写成宏,而不是定义为函数。完成I / Ogetchar,做字符测试的isdigit都是得到官方认可的例子。人们这样做最根本的理由就是执行效率:宏可以避免函数调用的开销。实际上,即使是在C语言刚诞生时(那时的机器非常慢,函数调用的开销也特别大),这个论据也是很脆弱的,到今天它就更无足轻重了。有了新型的机器和编译程序,函数宏的缺点就远远超过它能带来的好处。

所以应该避免函数宏。在C++ 里,在线函数更削减了函数宏的用武之地,在J a v a里根本就没有宏这种东西。即使是在C语言里,它们带来的麻烦也比解决的问题更多。

函数宏最常见的一个严重问题是:如果一个参数在定义中出现多次,它就可能被多次求值。如果调用时的实际参数带有副作用,结果就会产生一个难以捉摸的错误。

 

other tools

其他工具

       精通调试代码并不是说学会使用GDB这样的调试器就行了这只是开端。

       为了增强调试技能,初学者程序员最好学会其中的集中调试工具,了解那种工具适合于调试那种程序错误,并识别发生程序错误时使用其中那个工具可以节省时间和精力。

充分利用文本编辑器

       最好的调试方法是一开始就不要有编程错误,而简单地充分利用一种支持编程的编辑器就可以达到这个效果。因为:

l  精通强大的编辑器可以缩短编写代码所需的时就爱你,具有自动缩排、单词补充和全文代码查询等特殊功能的编辑器对程序员是非常有利的;

l  优秀的编辑器确实可以帮到编码者在编写代码时捕获某些类型的程序错误。

 

MarkMakefile中可以使用patsubst关键字来进行文本查找和替换命令。

 

       vim中调用make非常方便,不需要退出编辑器,直接:make 即可,同时vim可以捕获编译器发出的所有消息,编辑器理解GCC输出内容的语法,知道何时发生编辑器警告或错误。发生错误时可以直接定位到第一个错误,然后使用:cnext或者:cprevious来显示下一个或上一个错误或者警告。

       Vim中可以使用K来查询man页面中的函数

充分利用编译器

       如果说编辑器是对抗程序错误的第一个武器,那么编译器就是第二个武器了,所有编译器都有能力扫描代码并查找常见错误,但是通常必须通过调用适当的选项来启用这种错误检查。

       对于GCC而言,如果不适用-Wall,就几乎没有必要使用GCC了,所以任何编译最好都加上-Wall选项。

C语言中的错误报告

       C语言中的错误报告是使用名为errno的老式机制完成的。系统与库调用的失败通常是由于设置了名为errno的全局定义整数变量,在大多数GNU/Linux系统上,error是在/usr/include/errno.h上声明的,因此,只要包含了这个头文件,就不必在源代码中声明extern int errno

       当一个系统或库调用失败时,它将errno设置为一个指示失败类型的值。检查errno的值,并采取适当的动作可以判断错误类型。比如可以使用函数perror或者strerror

       errno可以通过任何库函数或系统调用设置,无论它是成功还是失败。因为即便成功的函数调用能够设置errno,让人不能依赖errno告诉你是否发生了错误。因此使用errno最安全的方式为:

l  执行对库或者系统函数的调用;

l  使用函数的返回值判断时候发生了某个错误;

l  如果发生了某个错误,使用errno确定为什么发生这个错误。

库函数和系统调用的区别

       库函数是更高级别的,完全在用户空间里运行,并未程序员提供了更方便的做实际工作的函数接口。

       系统调用代表用户以内核模式工作,由操作系统本身的内核提供。

       库函数printf看上去类似于一般输出函数,但是它实际上只是格式化你提供给字符串的数据,并用低级系统调用write编写字符串数据,然后将数据发送到一个与终端的标准输出关联的文件中。

更好地使用straceltrace

       strace跟踪系统调用而ltrace跟踪库调用,这两个使用程序,有时比深度调试代码还快。

静态代码检查器:lint与其衍生

       静态代码检查器:扫描代码的工具,不编译代码,仅仅警告错误、可能的错误和与严格C语言编码标准的差距。

       衍生版本为splint:该软件的目标是帮助编写大部分有防御性、安全和尽可能少出错的程序,当然,改程序对组成有效代码的内容非常挑剔。

       很多程序员将splint没有报告警告看做一种极大的荣誉。当出现这种情况是,代码被声明为无lint的。

调试动态分配的内存

       动态分配的内存(Dynamically Allocated Memory, DAM)是程序用malloccalloc这样的函数从堆中请求的内存。

       查找DAM问题分麻烦,分为以下几类:

l  没有释放动态分配的内存;内存泄漏

l  malloc的调用失败;

l  DAM段之外的地址执行读写操作;访问错误

l  释放DAM段之后对DAM区域中的内存进行读写操作;访问错误

l  对动态内存的同一段调用两次free重复释放double free

Electric Fence

       Bruce Perens1988年写的,当EFence链接到代码中时,导致程序在发生下列情况之一时立即发生段错误并转出核心:

l  DAM边界之外执行读写操作;

l  对已经释放的DAM执行读写操作;

l  对没有指向malloc分配的DAM的指针执行free,包括重复释放的特殊情况。

比如,

gcc –g3 –Wall –std=c99 test.c –o test_with_efence outOfBound_with_efence  –lefence

gcc –g3 –Wall –std=c99 test.c –o test_with_efence outOfBound_without_efence  -lefence

可以对一个内存泄露但是没有编译失败的程序做测试。

GNU C库工具调试DAM问题

l  在调用任何与堆有关的函数钱调用函数mcheck

l  使用mtrace函数捕获内存泄露和重复释放;

程序崩溃处理

程序崩溃处理

       有人说C语言是低级语言,这有一部分原因是因为应用程序的内存管理大部分需要由程序员来实现。虽然这种方法非常有用,但是也给程序员添加了很多的麻烦。

       也有人说,C语言是相对较小且容易学习的语言,然而,只有不考虑标准C语言库的典型实现时,C语言才比较小,这个库相当庞大,很多程序员认为C语言是易用语言,那是因为他们还没有遇到指针。

       一般而言,程序错误会导致下面两件事情的发生:

l  导致程序做一些程序员没有打算做的事情;

l  导致程序崩溃

 

相信很多调试过程序的兄弟都碰到过段错误即segmentation fault,则合格主要原因是试图在未经允许的情况下访问一个内存单元。硬件会感知这件事并执行对操作系统的跳转。

堆区域

       调用malloc函数分配的内存;

栈区域

       用来动态分配数据的空间,函数调用的数据(包括参数、局部变量和返回地址)都存储在栈上。

查看程序在Linux上的精确内存布局情况

       可以通过使用info proc mappings来详细查看该程序在Linux上的精确内存布局情况,例如:

clip_image002

此时我们还可以看到这个进程号为14455,所以我们还可以通过文件/proc/14455/maps来查看该信息。通过这些信息,我们有可能看到文本和数据区域,以及堆和栈。

分配页策略

       操作系统不会将不完整的页分配给程序,例如,如果要运行的程序总共大约有10000字节,如果完全加载,会占用3个内存页(一个页占4096个字节),它不会仅占用2.5个页,因为页是虚拟内存系统能够操作的最小内存单元,这是调试时要着重了解的情况,这也导致了程序的一些错误内存访问不会触发段错误,换言之,在调试会话期间,没有引起段错误并不能直接说明代码是没有问题的。

页的角色细节

       当程序执行时,它会连续访问程序中的各个区域,导致硬件按照以下几种情况所示处理页表:

l  每次程序使用全局变量时,需要具有对数据区域的读写访问权限;

l  每次程序访问局部变量时,程序会访问栈,需要对栈区域具有读写访问权限;

l  每次程序进入或离开函数时,对该栈进行一次或多次访问,需要对栈区具有读写访问权限;

l  每次程序访问通过调用malloc或者new创建的存储器时,都会发生堆访问,也需要读写访问权限;

l  程序执行的每个机器指令是从文本区域取出的,因此需要具有读和执行文件;

信号

       这里需要注意的是,进程抛出的信号,实际上没有任何内容发送给进程。所发生的事情只不过是操作系统将信号记录到进程表中,以便下次进程接收信号时得到CPU上的时间片,执行恰当的信号处理程序。

自定义信号的复杂性

       使用GDB/DDD/Eclipse调试时,自定义信号处理程序可能会使程序变得复杂,无论是直接使用还是通过DDD GUI,每当发出任何信号时,GDB都会停止进程,所以,有可能意味着GDB会因为与调试无关的工作而频繁的停止,此时可以使用handle命令告诉GDB在某些信号发生时不要停止。

总线错误的原因

l  访问不存在的物理地址;

l  在很多架构上,要求访问32位量的机器指令要求字对齐,而导致视图在奇数号地址上访问具有4字节的数的指针错误可能引起总线错误。

总线错误是处理器层的异常,导致在Unix系统上发出SIGBUS信号,默认情况下,SIGBUS会导致转储内存并终止。

核心文件

       有些信号表示让某个进程继续是不妥当的,甚至是不可能的,在这些情况中,默认动作是提前终止进程,并编写一个名为核心文件core file文件,俗称转储核心

       核心文件包含程序崩溃时对程序状态的详细描述:栈的内容、CPU寄存器的内容、程序的静态分配变量的值。

       我们可以通过file命令来查看文件的详细信息。

为什么需要核心文件

l  只有在运行了一段长时间后才发生段错误,所以在调试器中无法重新创建该错误;

l  程序的行为取决于随机的环境事件,因此再次运行程序可能不会再现段错误;

l  当新手用户运行程序时发生的段错误,需要发送核心文件给开发人员。

重载功能

       GDB注意到重新编译了程序后,它会自动加载新的可执行文件,因此不需要退出和重启GDB

调试设计的内容

l  确认原则;

l  使用核心文件进行崩溃进程的“死后”分析;

l  纠正、编译并重新运行程序后,甚至不需要退出GDB

l  Printf()风格调试的不足之处;

l  利用你的智慧,这是无可替代的;

l  如果你过去使用printf风格调试的,就会发现使用printf跟踪这些程序错误中的部分错误原来有多难,虽然在调试中使用printf诊断代码有一定的好处,但是作为一种通用目的的工具,它远远不足以用来跟踪实际代码中发生的大部分程序错误。

 

动态内存分配

动态内存分配

为什么使用动态内存分配

       比如,我们计算年级学生的平均成绩,但是不知道有多少学生,可以定义一个很大的数组,确保学生个数不会超出数组定义范围,但是如果学生人数很少,就会造成巨大的浪费。所以会有如下缺点:

l  数组声明中引入了人为的限制,如果程序需要使用的元素数量超过了声明的长度,它就无法处理这种情况;

l  要避免上述情况,需要把数组声明的更大些,但这也导致如果元素数据比较少时,巨型数组的绝大部分内存空间都浪费了;

l  如果输入的数据超过了数组的容纳范围,程序必须以一种合理的方式作出响应,而不应该由于一个异常而失败,也不应该打印出看上去正确但实际上错误的结果。

mallocfree

       c函数库提供了两个函数,mallocfree,分别用于执行内存分配和释放。这些函数维护一个可用内存池。当一个程序另外需要一些内存时,它就调用malloc函数,malloc从内存池中提取一块合适的内存,并向该程序放回一个指向这块内存的指针。注意,现在这块内存并没有以任何方式进行初始化

       free的参数要么是NULL,要么是一个先前从malloccallocrealloc返回的值。向free传递一个NULL参数不会产生任何效果。

       And我们知道malloc的返回值为void *,所以malloc可以指向任何类型的整数、浮点值、结构或者数组,这个需要我们自己定义。

callocrealloc

       malloccalloc之间的主要区别是后者在返回指向内存的指针之前把它初始化为0。这个初始化常常能带来方便,但是如果你的程序只是想把一些值存储到数组中,那么这个初始化过程就纯属浪费时间;两者的另外一个较小的区别是它们请求内存数量的方式不同,calloc的参数包括所需元素的数量和每个元素的字节数。

       realloc函数用于修改一个原先已经分配的内存块的大小。如果原先的内存块无法改变大小,realloc将分配另一块正确大小的内存,并把原先那块内存的内容复制到新的块上。

       如果realloc函数的第一个参数是NULL,那么它的行为就和malloc一摸一样。

常见的动态内存错误

       使用动态内存常犯的错误就是忘记检查所请求的内存是否成功分配?第二大错误是操作内存时超出了分配内存的边界。

       分配内存但在使用完毕后如果不释放将引起内存泄露memory leak

内存分配实例

       动态内存分配一个常见的用途就是为那些长度在运行时才知的数组分配内存空间

总结

l  当数组被声明时,必须在编译时知道它的长度。动态内存分配允许程序为一个长度在运行时才知道的数组分配内存空间;

l  动态内存分配时必须判断返回值是否为NULL

l  动态内存分配有助于消除程序内部存在的限制;

使用sizeof计算数据类型的长度,可以提高程序的可移植性。