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

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诊断代码有一定的好处,但是作为一种通用目的的工具,它远远不足以用来跟踪实际代码中发生的大部分程序错误。