数据结构与算法分析--学习笔记（1）

时间：2010-11-28 来源：controlqsw

一直都只是马马虎虎地学着C，现在感觉这样做肯定以后会留下很多弊病，所以开这个博客，争取让自己能够系统地再学一次C,当然，数据结构是相当重要的，清华大学严蔚敏的那本数据结构C语言版刚看完，但是感觉很多地方写得并不是非常清楚。这次开始认真学下数据结构与算法分析这本书，并把学习过程中的一些想法记录下来，方便以后查阅。 1.关于各类型的长度 short int, int, long int, 其中short int 也就是short占16位，int按照编译环境及硬件环境而不同，有16位也有32位，而long int也就是long则一直都是32位，当然，我们可以用sizeof(int)来确定长度。 float占32位，double占64位，char占8位。 2.结构体中储存变量地址的对齐原则（1）结构体变量的成员的偏移量必须是成员大小的整数倍原则（2）结构体大小必须是所有成员大小的整数倍举个例子 struct stu{ int num; char name[20]; char sex; float score; }; 这个例子中，假设int是32位，则简单相加总长是32+8*20+8+32，也就是4+1*20+1+4=29个字节，而为了符合对齐原则，显然在存储score之前，总共是25个字节，不是4的倍数，所以，char sex这里实际占了4个字节，再加上float的4个字节，最后总共是32个字节。 http://wenku.baidu.com/view/2058b6db6f1aff00bed51e4f.html 该网页中有详细的内容，且结构体是结构体成员变量时，在运用（1）（2）规则时，认为是最大长度的存储变量的长度。 3.删除链表元素的方法与严蔚敏的方法相对比，严蔚敏的方法是用两个指针，一前一后，当前面那个指针指向了要删除的元素后，令后面那个指针所指向的结构的next域指向要删除元素的next域。相当于前面那个指针作用是查找，后面那个指针的作用是连接链表。而数据结构与算法分析35页中，则是使用了一个FindPrevious的函数，这个函数的原型如下： Pos FindPrevious( ElemType X, List L ){ Pos P; P = L; while( P->next != NULL && P->next->Elem != X ) P = P->next; return P; } 与查找Find函数相比： Pos Find( ElemType X, List L ){ Pos P; P = L->next; while( P != NULL && P->Elem != X ) P = P->next; return P; } Pos是结构体指针类型可以看到，本书使用这种方法的确使代码更加简明，本来删除操作就是一个查找删除两步的过程，在我们编写的时候，尽量让函数的功能能够保持单一作用，这样以后修改起来也更简单。比如插入操作，这也是两部分组成，我们可以先查找，再插入，而还有一点特殊的地方，我是插入在查找到的结构体前面还是后面呢？因此，使用Find类型的函数来查找，可以同时满足前插入和后插入的需求，而若使用严蔚敏那本书的方法，可能就显得不好维护了。 4.分配结构体内存的问题定义结构体指针是没有同时分配结构体内存的，只是分配了指针的内存。 struct Node; typedef struct Node *ProToNode; Pos TmpCell; TmpCell = malloc( sizeof( struct Node ) ); 这样是可行的 TmpCell = malloc( sizeof( PtrToNode ) ); 这不会出错，但是这只是分配了指针大小的内存，可以用sizeof( PtrToNode )查看归根到底，是要弄清结构体指针与结构体变量的区别。