4.1 指针
实际上并不推荐使用malloc和free,使用malloc还简单,但是当指针进行移动的时候,你如何确定在哪个地址上free内存,则是个大难题.
我们写个正常的malloc和free程序:
#include#include #include int main( void ){ int *pi = ( int * )malloc( sizeof( int ) ); *pi = 4; printf("%d\n", *pi ); free( pi ); return 0;}
然后写个比较怪怪的函数:
#include#include #include int main( void ){ char **pstr = ( char ** )malloc( sizeof( char ) * 100 ); *pstr = "hello world"; printf("%s\n", *pstr ); free( pstr ); return 0;}
这段代码至少对目前的我来说,有点怪异(虽然是我自己写出来的).写这段代码有以下的含义:
1. 对于char *,最好理解为字符串,而不是字符指针(虽然操作的时候,可以通过字符指针进行操作)
2. 对于malloc函数,要分配确定的大小,所以程序中为sizeof(char)而不是sizeof(char*),因为指针在特定的机子上的大小不同(一般为4字节)
3. 在free中,一定要找对free的起始地址.比如我如果这样修改,则会报错:
#include#include #include int main( void ){ char **pstr = ( char ** )malloc( sizeof( char ) * 100 ); *pstr = "hello world"; printf("%c---%s---%p\n", **pstr, *pstr, pstr ); pstr++; free( pstr ); return 0;}
程序很恐怖的输出:
你能确保在编写代码中,用到free的时候,不会一不小心的移动了一下指针??至少我基本不敢用free,也是这个原因.这也导致了实际上我也不太敢用malloc.
4.2 链表
简单写一个单链表,数据元素为字符串,支持增加,删除,查找.按字符串的字典顺序排序.
PS:实际上这里的难度在于:C语言只能传值,所以你必须传递指针的指针到函数中去.而传递指针的指针也很麻烦,那么我们可以这样想:用一个固定的节点当作头指针,而实际的头节点当作第二个指针即可:
#include#include #include typedef struct LINK{ char *word; struct LINK *next;}Link;void insert( Link *link, char *word ){ Link *temp = ( Link * )malloc( sizeof( Link ) ); //用于存储新的值 Link *tempLink = ( Link * )malloc( sizeof( Link ) ); //在插入节点时存储上一个节点 temp->word = word; temp->next = NULL; if ( NULL == link->next ){ link->next = temp; } else{ tempLink = link; //存储上一个节点 link = link->next; while ( NULL != link ){ if ( -1 == strcmp( link->word, word ) ){ tempLink = link; link = link->next; } else if ( 0 == strcmp( link->word, word ) ){ return; } else{ temp->next = link; tempLink->next = temp; return; } } if ( NULL == link ){ //判断为尾节点的特殊情况 tempLink->next = temp; } }}int delete( Link *link, char *word ){ Link *tempLink = ( Link * )malloc( sizeof( Link ) ); //用于存储删除元素的上一个节点 tempLink = link; link = link->next; while ( NULL != link ){ if ( 0 != strcmp( link->word, word ) ){ tempLink = link; link = link->next; } else{ tempLink->next = link->next; return 1; } } return 0;}void show( Link *link ){ while ( NULL != link ){ printf("%s-->", link->word ); link = link->next; } printf("NULL\n");}int main( void ){ Link *link = ( Link * )malloc( sizeof( Link ) ); link->next = NULL; link->word = "EOF"; //这里假定没有字符串等于EOF insert( link, "cc" ); insert( link, "dd" ); insert( link, "aa" ); insert( link, "bb" ); insert( link, "ba" ); insert( link, "cb" ); show( link->next ); delete( link, "bb" ); delete( link, "dd" ); delete( link, "ff" ); show( link->next ); return 0;}
程序输出:
有道题比较难(真的写的时候也不难,只是之前我没写出来,现在写出来罢了),就是将链表进行翻转,但不能借助其他的存储空间(如果能的话,相当于对delete一个链表再insert成一个链表),代码如下:
#include#include #include typedef struct LINK{ char *word; struct LINK *next;}Link;void insert( Link *link, char *word ){ Link *temp = ( Link * )malloc( sizeof( Link ) ); //用于存储新的值 Link *tempLink = ( Link * )malloc( sizeof( Link ) ); //在插入节点时存储上一个节点 temp->word = word; temp->next = NULL; if ( NULL == link->next ){ link->next = temp; } else{ tempLink = link; //存储上一个节点 link = link->next; while ( NULL != link ){ if ( -1 == strcmp( link->word, word ) ){ tempLink = link; link = link->next; } else if ( 0 == strcmp( link->word, word ) ){ return; } else{ temp->next = link; tempLink->next = temp; return; } } if ( NULL == link ){ //判断为尾节点的特殊情况 tempLink->next = temp; } }}int delete( Link *link, char *word ){ Link *tempLink = ( Link * )malloc( sizeof( Link ) ); //用于存储删除元素的上一个节点 tempLink = link; link = link->next; while ( NULL != link ){ if ( 0 != strcmp( link->word, word ) ){ tempLink = link; link = link->next; } else{ tempLink->next = link->next; return 1; } } return 0;}void show( Link *link ){ while ( NULL != link ){ printf("%s-->", link->word ); link = link->next; } printf("NULL\n");}void reverse( Link *link ){ Link *tail = ( Link * )malloc( sizeof( Link ) ); Link *mid = ( Link * )malloc( sizeof( Link ) ); Link *prev = ( Link * )malloc( sizeof( Link ) ); Link *head = ( Link * )malloc( sizeof( Link ) ); head = link; tail = NULL; link = link->next; if ( NULL != link ){ mid = link; prev = link->next; while ( NULL != prev ){ mid->next = tail; tail = mid; mid = prev; prev = prev->next; } mid->next = tail; head->next = mid; }}int main( void ){ Link *link = ( Link * )malloc( sizeof( Link ) ); link->next = NULL; link->word = "EOF"; //这里假定没有字符串等于EOF insert( link, "cc" ); insert( link, "dd" ); insert( link, "aa" ); insert( link, "bb" ); insert( link, "ba" ); insert( link, "cb" ); show( link->next ); delete( link, "bb" ); delete( link, "dd" ); delete( link, "ff" ); show( link->next ); reverse( link ); show( link->next ); return 0;}
程序输出:
4.3 动态链栈与动态链队列
动态链栈与动态链队列没什么特别的地方,主要就是多个链栈的集合而已,而传递的时候只要把每个栈的地址传递到函数里面去就可以了.
4.4 多项式
多项式的相加:书上的方法很牛,它是直接返回一个地址的.效率在我看来,是所有多项式相加里面最高的.但是我个人感觉,代码应该简洁,更应该有良好的阅读感.所以我打算是将相加的结果当作一个指针传递进去,而不是从函数内返回回来:
先把自己写的错误的代码粘贴出来,用于铭记(对待C,C++,都要用及其认真的态度来对待):
#include#include #include typedef struct POLYNODE{ int coef; int expon; struct POLYNODE *next;}PolyNode;void padd( PolyNode *exp1, PolyNode *exp2, PolyNode *exp ){ PolyNode *addNode; while ( exp1 && exp2 ){ addNode = ( PolyNode * )malloc( sizeof( PolyNode ) ); if ( exp1->expon < exp2->expon ){ addNode->coef = exp2->coef; addNode->expon = exp2->expon; addNode->next = NULL; exp = addNode; exp = exp->next; exp2 = exp2->next; continue; } else if ( exp1->expon == exp2->expon ){ if ( 0 == ( exp1->coef + exp2->coef ) ){ exp1 = exp1->next; exp2 = exp2->next; continue; } addNode->coef = exp1->coef + exp2->coef; addNode->expon = exp1->expon; addNode->next = NULL; exp = addNode; exp = exp->next; exp1 = exp1->next; exp2 = exp2->next; continue; } else{ addNode->coef = exp1->coef; addNode->expon = exp1->expon; addNode->next = NULL; exp = addNode; exp = exp->next; exp1 = exp1->next; continue; } } while ( exp1 ){ addNode = ( PolyNode * )malloc( sizeof( PolyNode ) ); addNode->coef = exp1->coef; addNode->expon = exp1->expon; addNode->next = NULL; exp = addNode; exp = exp->next; exp1 = exp1->next; } while ( exp2 ){ addNode = ( PolyNode * )malloc( sizeof( PolyNode ) ); addNode->coef = exp2->coef; addNode->expon = exp2->expon; addNode->next = NULL; exp = addNode; exp = exp->next; exp2 = exp2->next; }}void show( PolyNode *exp ){ exp = exp->next; while ( exp ){ printf("%d * x^%d + ", exp->coef, exp->expon ); exp = exp->next; } printf("0\n");}int main( void ){ PolyNode *exp1 = ( PolyNode * )malloc( sizeof( PolyNode ) ); PolyNode *exp2 = ( PolyNode * )malloc( sizeof( PolyNode ) ); PolyNode *exp = ( PolyNode * )malloc( sizeof( PolyNode ) ); PolyNode node1_1, node1_2, node1_3, node2_1, node2_2, node2_3; exp1->next = NULL; exp2->next = NULL; exp->next = NULL; node1_1.coef = 3; node1_1.expon = 14; node1_1.next = &node1_2; node1_2.coef = 2; node1_2.expon = 8; node1_2.next = &node1_3; node1_3.coef = 1; node1_3.expon = 0; node1_3.next = NULL; node2_1.coef = 8; node2_1.expon = 14; node2_1.next = &node2_2; node2_2.coef = -3; node2_2.expon = 10; node2_2.next = &node2_3; node2_3.coef = 10; node2_3.expon = 6; node2_3.next = NULL; exp1->next = &node1_1; exp2->next = &node2_1; padd( exp1->next, exp2->next, exp->next ); show( exp ); return 0;}
之前写的错误有以下:
1. 一定要把头指针传递进去:
padd( exp1, exp2, exp );
但是,如果exp1,exp2只是用来读取而不进行修改,可以传递exp1->next进去.
2. 对链表的插入,不能这样操作:
exp = addNode;exp = exp->next;
在头部可以这样插入,但是在尾部@_@,sorry,空指针会不断的把exp初始化为NULL.
所以代码修改如下(模块化):
#include#include #include typedef struct POLYNODE{ int coef; int expon; struct POLYNODE *next;}PolyNode;void insert( PolyNode *exp, PolyNode *addNode ){ if ( NULL == exp->next ){ exp->next = addNode; } else{ exp = exp->next; while ( NULL != exp->next ){ exp = exp->next; } exp->next = addNode; }}void padd( PolyNode *exp1, PolyNode *exp2, PolyNode *exp ){ PolyNode *addNode; while ( exp1 && exp2 ){ addNode = ( PolyNode * )malloc( sizeof( PolyNode ) ); if ( exp1->expon < exp2->expon ){ addNode->coef = exp2->coef; addNode->expon = exp2->expon; addNode->next = NULL; insert( exp, addNode ); exp2 = exp2->next; continue; } else if ( exp1->expon == exp2->expon ){ if ( 0 == ( exp1->coef + exp2->coef ) ){ exp1 = exp1->next; exp2 = exp2->next; continue; } addNode->coef = exp1->coef + exp2->coef; addNode->expon = exp1->expon; addNode->next = NULL; insert( exp, addNode ); exp1 = exp1->next; exp2 = exp2->next; continue; } else{ addNode->coef = exp1->coef; addNode->expon = exp1->expon; addNode->next = NULL; insert( exp, addNode ); exp1 = exp1->next; continue; } } while ( exp1 ){ addNode = ( PolyNode * )malloc( sizeof( PolyNode ) ); addNode->coef = exp1->coef; addNode->expon = exp1->expon; addNode->next = NULL; insert( exp, addNode ); exp1 = exp1->next; } while ( exp2 ){ addNode = ( PolyNode * )malloc( sizeof( PolyNode ) ); addNode->coef = exp2->coef; addNode->expon = exp2->expon; addNode->next = NULL; insert( exp, addNode ); exp2 = exp2->next; }}void show( PolyNode *exp ){ exp = exp->next; while ( exp ){ printf("%d * x^%d + ", exp->coef, exp->expon ); exp = exp->next; } printf("0\n");}int main( void ){ PolyNode *exp1 = ( PolyNode * )malloc( sizeof( PolyNode ) ); PolyNode *exp2 = ( PolyNode * )malloc( sizeof( PolyNode ) ); PolyNode *exp = ( PolyNode * )malloc( sizeof( PolyNode ) ); PolyNode node1_1, node1_2, node1_3, node2_1, node2_2, node2_3; exp1->next = NULL; exp2->next = NULL; exp->next = NULL; node1_1.coef = 3; node1_1.expon = 14; node1_1.next = &node1_2; node1_2.coef = 2; node1_2.expon = 8; node1_2.next = &node1_3; node1_3.coef = 1; node1_3.expon = 0; node1_3.next = NULL; node2_1.coef = 8; node2_1.expon = 14; node2_1.next = &node2_2; node2_2.coef = -3; node2_2.expon = 10; node2_2.next = &node2_3; node2_3.coef = 10; node2_3.expon = 6; node2_3.next = NULL; exp1->next = &node1_1; exp2->next = &node2_1; padd( exp1->next, exp2->next, exp ); show( exp ); return 0;}
程序输出:
多项式的循环链表中,涉及到一个非常有用的概念:内存池.就是分配一块内存用于存储和删除,这样就不必每次malloc了.但是这里内存池实际上可以用数组来实现(堆栈),这样更加的方便.于是自己写了以下的算法:
PS:这里为了简单的讨论,链表的插入就直接在头部插入了,而且并不是循环链表:
#include#include #include #define MAX_STACK 100typedef struct NODE{ int data; struct NODE *next;}Node;Node stack[ MAX_STACK ];int top = 0;void insert( Node *node, int data ){ Node *tempnode; if ( top == MAX_STACK - 1 ){ printf("sorry. 木有内存空间了\n"); return; } tempnode = &stack[ top++ ]; //这样做只是为了top能及时的++ tempnode->data = data; tempnode->next = NULL; if ( NULL == node->next ){ node->next = tempnode; } else{ tempnode->next = node->next; node->next = tempnode; }}void show( Node *node ){ node = node->next; while ( node ){ printf("%d->", node->data ); node = node->next; } printf("NULL\n");}int main( void ){ Node node = stack[ top++ ]; node.next = NULL; insert( &node, 1 ); insert( &node, 2 ); insert( &node, 3 ); insert( &node, 4 ); insert( &node, 5 ); show( &node ); return 0;}
程序输出:
如果你手贱的话,可能会写出下列的代码(我的第一版本---结果调试的时候发现指针乱窜):
#include你会发现tempnode的地址实际上会指向之前赋值的node,然后tempnode不断的被更改,就是实际上:#include #include #define MAX_STACK 100typedef struct NODE{ int data; struct NODE *next;}Node;Node stack[ MAX_STACK ];int top = 0;void insert( Node *node, int data ){ Node tempnode; if ( top == MAX_STACK - 1 ){ printf("sorry. 木有内存空间了\n"); return; } tempnode = stack[ top++ ]; //这样做只是为了top能及时的++ tempnode.data = data; tempnode.next = NULL; if ( NULL == node->next ){ node->next = &tempnode; } else{ tempnode.next = node->next; node->next = &tempnode; }}void show( Node *node ){ node = node->next; while ( node ){ printf("%d->", node->data ); node = node->next; } printf("NULL\n");}int main( void ){ Node node = stack[ top++ ]; node.next = NULL; insert( &node, 1 ); insert( &node, 2 ); insert( &node, 3 ); insert( &node, 4 ); insert( &node, 5 ); show( &node ); return 0;}
tempnode = stack[ top++ ];
并没有达到你想要的效果.
4.5 链表的其他操作
1. 翻转单链表---在上面已经写过了.
2. 串接单链表---把第二个链表的头节点放在第一个链表的尾节点即可.
4.6 等价关系
关于等价关系,我并不了解书上的那个VLSI的应用场景,所以略过.
4.7 稀疏矩阵
书上用稀疏矩阵的数据结构过于麻烦,直接不想看.在编程的世界里,有几点必须注意:1. 尽量把代码写简单.2.性能没有你想象中的那么重要,可维护性在某些方面更加重要.所以,在做项目的时候,如果性能没有那么重要,推荐使用高级语言,不要使用C.C只是用来打基础的.
4.8 双向链表
最后以一个双向链表的实现来结束本章(这里只是简单的实现,并没有设计到排序等情况.链表的作用是用于存储,如果关联到排序,请使用二叉树.这里要用循环链表实现,否则你得维护两张链表):
#include#include #include typedef struct DLINK{ int data; struct DLINK *prev; struct DLINK *next;}Dlink;void insertFront( Dlink *dlink, int data );void insertTail( Dlink *dlink, int data );void delete( Dlink *dlink, int data );int search( Dlink *dlink, int data );void show( Dlink *dlink );int main( void ){ int i = 0; Dlink *dlinkHead = ( Dlink * )malloc( sizeof( Dlink ) ); dlinkHead->next = dlinkHead->prev = NULL; for ( i = 0; i < 10; i++ ){ insertFront( dlinkHead, i ); insertTail( dlinkHead, i ); } for ( i = 0; i < 10; i += 3 ){ delete( dlinkHead, i ); } if ( search( dlinkHead, 5 ) ){ printf("5 in the double link list\n"); } else{ printf("5 not in the double link list\n"); } if ( search( dlinkHead, 3 ) ){ printf("3 in the double link list\n"); } else{ printf("3 not in the double link list\n"); } show( dlinkHead ); return 0;}void insertFront( Dlink *dlink, int data ){ Dlink *tempDlink = ( Dlink * )malloc( sizeof( Dlink ) ); tempDlink->data = data; if ( ( NULL == dlink->prev ) && ( NULL == dlink->next ) ){ dlink->prev = tempDlink; dlink->next = tempDlink; } else{ dlink->next->prev = tempDlink; tempDlink->prev = NULL; //用于判断链表的头部 tempDlink->next = dlink->next; dlink->next = tempDlink; }}void insertTail( Dlink *dlink, int data ){ Dlink *tempDlink = ( Dlink * )malloc( sizeof( Dlink ) ); tempDlink->data = data; if ( ( NULL == dlink->prev ) && ( NULL == dlink->next ) ){ dlink->prev = tempDlink; dlink->next = tempDlink; } else{ tempDlink->prev = dlink->prev; tempDlink->next = NULL; //用于判断链表的尾部 dlink->prev->next = tempDlink; dlink->prev = tempDlink; }}void delete( Dlink *dlink, int data ){ Dlink *headNode = ( Dlink * )malloc( sizeof( Dlink ) ); headNode = dlink; //用于存储头节点 if ( ( NULL == dlink->prev ) && ( NULL == dlink->next ) ){ return; } dlink = dlink->next; while ( dlink->next ){ if ( data != dlink->data ){ dlink = dlink->next; } else{ if ( NULL == dlink->prev ){ headNode->next = dlink->next; dlink->prev = NULL; } else if ( NULL == dlink->next ){ headNode->prev = dlink->prev; dlink->prev->next = NULL; } else{ dlink->next->prev = dlink->prev; dlink->prev->next = dlink->next; } dlink = dlink->next; } }}int search( Dlink *dlink, int data ){ dlink = dlink->next; while ( dlink ){ if ( data == dlink->data ){ return 1; } dlink = dlink->next; } return 0;}void show( Dlink *dlink ){ dlink = dlink->next; while ( dlink ){ printf("%d-->", dlink->data ); dlink = dlink->next; } printf("NULL\n");}
程序输出:
