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

    一直都只是马马虎虎地学着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个字节。

 

 该网页中有详细的内容，且结构体是结构体成员变量时，在运用（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 )查看

 

归根到底，是要弄清结构体指针与结构体变量的区别。