软件设计中，最常用的两种数据存储结构就是顺序存储结构和链式存储结构，顺序存储结构中用的最多的便是数组了，而链式存储结构用的比较多的应该是单链表以及它们的变形。
单链表中只有一个指向下一个结点的指针，并且最后一个元素的next指针为NULL;循环链表与单链表的区别就是最后一个指针指向头结点；双向链表中，每个结点不仅有指向下一个结点的next指针，还有一个指向前一个结点的prior指针，头结点的prior和尾结点的next为NULL。因为都是单链表的变形，所以这里主要分析单链表。
与顺序存储空间不同，链式存储空间并不是连续的，数组中，直接通过索引来访问元素。而单链表中它是通过每个结点中的next指针来找到下一个结点的。
1、 单链表的结构体
单链表的结构体中包含两个元素，一个是数据元素，一个是指向下一个结点的地址。下列结构体中data的数据类型可以是基本数据类型，也可以是复杂数据类型。
int data;
struct SingleListNode *next;
}ListNode;
2、单链表的创建
如果返回值为NULL，则创建失败，否则创建成功。
ListNode *pNode;
pNode = (ListNode*)malloc(sizeof(ListNode));
if(NULL != pNode){
memset(pNode,0,sizeof(ListNode));
pNode->data = data;
}
return pNode;
}
3、单链表查找
如果找到对应的元素，返回结点地址，否则返回NULL。
ListNode *pNode;
if(NULL == pListNode)
return NULL;
if(data == pListNode->data)
return (ListNode*)pListNode;
pNode = pListNode->next;
while(pNode){
if(data == pNode->data)
return pNode;
pNode = pNode->next;
}
return NULL;
}
4、单链表的插入
找到链表的最后一个结点，即next为NULL的结点，然后新建一个结点插入。
ListNode *pNode,*ppListNode;
if(NULL == pListNode)
return false;
pNode = createSingleListNode(data);
if(NULL == pNode)
return false;
if(NULL == *pListNode)
*pListNode = pNode;
else{
ppListNode = *pListNode;
while(ppListNode->next)
ppListNode = ppListNode->next;
ppListNode->next = pNode;
}
return true;
}
5、单链表的删除
找到元素等于data的结点pNode，用指针pPre表示pNode的前一个结点，把pPre的next指向pNode的next结点，然后free pNode.
if(NULL == pListNode || NULL == *pListNode)
return false;
ListNode *pNode = *pListNode->next;
if(*pListNode->data == data){
free(*pListNode)；
*pListNode = pNode;
return true;
}
ListNode *pPre = *pListNode;
while(pNode){
if(pNode->data == data){
pPre = pNode->next;
free(pNode);
return true;
}
pPre = pNode;
pNode = pNode->next;
}
return false;
}
6、释放链表
链表是通过mallic动态创建的，所以每次用完以后，必须free，以免内存泄漏。
if(NULL == pListNode)
return ;
ListNode *pNode = NULL;
while(pListNode){
pNode = pListNode->next;
free(pListNode);
pListNode = pNode;
}
}
关于链表的算法：
最常用的就是快慢指针，第7、8、9用的都是这个思想。
还有就是借助第三指针的概念。其实对链表的操作都是对指针的操作，理解链表首先得理解指针。下面举几个常用的链表算法。
7、找出链表的中间结点
用两个快慢指针，快指针每次走两步，慢指针每次走一步，当快指针走到链表尾部时，慢指针所指向的结点即为中间结点。
ListNode *pQuick = pListNode,*pSlow = pListNode:
if(NULL == pListNode)
return NULL;
while(pQuick){
pSlow = pSlow->next;
pQuick = pQuick->next;
if(NULL == pQuick)
break;
pQuick = pQuick->next;
}
return pSlow;
}
8、找出倒数第k个结点
快指针先走k步，然后快慢指针一起走，知道快指针走到链表 末尾，慢指针即为倒数第k个结点。
一、使用make更新静态库
静态库文件是一些.o文件的集合，在Linux中使用ar工具对它进行维护管理。一个静态库通常由多个.o文件组成，这些.o文件可独立的被作为一个规则的目标，库成员作为目标时需要按照如下格式来书写：
ARCHIVE(MEMBER)
注：这种格式只能出现在规则的目标和依赖中，不能出现在命令行中。含有这种表达式的规则的命令行只能是ar命令或者其它可以对库成员进行操作的命令。如下规则用于创建库“foolib”，并将“hack.o”成员加入库中：
ar cr foolib hack.o
如果在规则中同时需要指定库的多个成员，可以将多个成员放在括号中，如下：
foolib(hack.o kludge.o)等价于foolib(hack.o) foolib(kludge.o)
也可以使用shell通配符，例如foolib(*.o)代表库foolib中所有的.o成员。
静态库的更新
模式(%)用来更新目标A(M)，其先将M拷贝到A中，如果之前A不存在，则首先创建A。例如：目标为foo.a(bar.o)，执行时将完成：首先使用隐含规则创建bar.o，之后将bar.o加入到foo.a中。如此，bar.o就作为foo.a中的一个成员了。
静态库中，其所有的成员名是不包含目录描述的，也就是说对于静态库，当使用nm命令查看其成员时，能够获得的信息只是静态库所包含的成员名字而已。
当给一个静态库增加一个成员时，ar将.o文件简单地追加到静态库的末尾，并没有及时更新库的符号表。如果此时我们使用这个库进行链接生成可执行文件，链接程序ld却提示出错，可能原因是：程序使用了刚加入的.o文件中定义的函数或者全局变量，但链接程序无法找到。此时需要使用ranlib来对符号表进行更新。
静态库中存在一个特殊的成员__.SYMDEF，其记录了库中所有成员的符号（函数名、变量名）。使用方法为：
ranlib ARCHIVEFILE
通常在makefile中我们可以这样来实现：
ranlib libfoo.a
二、make隐含规则
使用make的隐含规则，在makefile中就不需要明确给出重建某一目标的命令，甚至可以不需要规则。make会自动根据已存在的源文件类型来启动相应的隐含规则。例如：
cc –o foo foo.o bar.o $(CFLAGS) $(LDFLAGS)
上述并没有给出重建foo.o的规则，make会根据隐含规则来创建这个文件。隐含规则所提供的只是一个最基本的对于关系：例如EXENAME.o对应EXENAME.c，EXENAME对应EXENAME.o。
每一个内嵌的隐含规则都存在一个目标模式和一个依赖模式，而且同一个目标模式可以对应多个依赖模式。通常make会对那些没有命令行的规则、双冒号规则寻找一个隐含规则来执行。
注：即使给一个目标指定了明确的依赖文件，那么隐含规则依然会被执行，如下所示：
foo.o : foo.p
如果当前目录下存在foo.c，那么执行make时并不用pc编译，而是用cc编译。
如果不想让make为一个没有命令行的规则中的目标搜索隐含规则时，可以使用空命令来实现。
1 make隐含规则
自动由.cc或.C生成.o $(CXX) –c $(CPPFLAGS) $(CFLAGS)
自动由.o生成可执行文件，使用链接器GNU ld $(CC) $(LDFLAGS) *.o $(LOADLIBS) $(LDLIBS)
仅适用于由一个源文件直接生成可执行文件的情况；
如果需要由多个源文件共同创建一个可执行文件，需要在makefile中添加隐含规则的依赖文件，如：x : y.o z.o
2 隐含变量
隐含变量分为两类，一类表示命令的名字，一类表示命令使用的参数，多个参数使用空格分隔。
表示命令的名字 | AR | 函数库打包程序，默认是ar，用于创建静态库.a |
| AS | 汇编程序，默认是as |
| CC | C编译器，默认是cc |
| CXX | C++编译器，默认是g++ |
| CO | 从RCS中提取文件的程序，默认是co |
| CPP | C程序的预处理器，默认是$(CC) -E |
| GET | 从SCCS中提取文件，默认是get |
| LEX | 将Lex语言转变为C或Ratfo程序，默认是lex |
| YACC | Yacc文法分析器，默认是yacc |
| MAKEINFO | 转换Texinfo源文件.text到Info文件，默认是makeinfo |
| TEX | 从Tex源文件创建Tex Dvi，默认是tex |
| TEXI2DVI | 从Tex源文件创建Tex Dvi，默认是texi2dvi |
| WEAVE | 转换Web到Tex，默认是weave |
|
订阅：
博文评论 (Atom)
|
没有评论:
发表评论