Fundamental

Ch 1¶

数据元素是数据的基本单位, 数据项是不可分割的最小单位。构成数据元素的最小单位是数据项。常作为一个整体来进行处理。数据元素通常由若干个数据项组成，数据项具有原子性，是不可分割的最小单位。
数据的逻辑结构是指数据的数据元素之间的逻辑关系；数据元素是数据的基本单位；数据项是组成数据元素、有独立含义的、不可分割的最小单位；数据对象是性质相同的数据元素的集合，是数据的一个子集
数据结构概念包括数据之间的逻辑结构、数据在计算机中的存储方式和数据的运算三个方面。
数据结构从逻辑上可分为两大类： 线性结构和非线性结构 。
数据结构的逻辑结构独立于其存储结构，数据结构的存储结构不能说它是独立于该数据结构的逻辑结构的存储结构: 数据的逻辑结构用计算机语言的实现顺序存储，比如数组实现的线性表，则存储结构和逻辑结构是一致的；链式存储，同样是实现线性表，其逻辑连续的节点在空间上是独立的；而对于树、图等非线性的数据结构，其逻辑和储存一定是独立的。
数据结构相同，逻辑结构要相同，但逻辑结构的实现可以用不同的存储结构；
以下属于逻辑结构的是（ C） A. 顺序表 B. 散列表 C. 有序表 D. 单链表

顺序表、哈希表和单链表表示几种数据结构，既描述逻辑结构，也描述存储结构和数据运算，而有序表是指关键字有序的线性表，可以链式存储也可以顺序存储，仅描述了元素之间的逻辑关系，故它属于逻辑结构。

因为A顺序表已经表示了他是按照顺序存储的方式存储，B哈希表使用散列存储，D单链表表明是链式存储。这三个选项都是根据它的物理存储方式命名的，所以都属于存储结构，或是物理结构。只有C有序表，既可以用链式存储又可以用顺序存储，所以只是一种逻辑上的有序而不是实际存储的方式。

算法的时间复杂度取决于待处理数据的状态以及问题的规模

Assignment 2¶

Assignment 3¶

循环队列会损失一个空间

Assignment 4¶

线索二叉树

Exp 4.3¶

下列代码的功能是计算给定二叉树T的宽度。二叉树的宽度是指各层结点数的最大值。函数Queue_rear和Queue_front分别返回当前队列Q中队尾和队首元素的位置。

typedef struct TreeNode *BinTree;
struct TreeNode
{
   int Key;
   BinTree  Left;
   BinTree  Right;
};

int Width( BinTree T )
{
   BinTree  p;
   Queue Q;
   int Last, temp_width, max_width;

   temp_width = max_width = 0;
   Q = CreateQueue(MaxElements);
   Last = Queue_rear(Q);
   if ( T == NULL) return 0;
   else {
      Enqueue(T, Q);
      while (!IsEmpty(Q)) {
         p = Front_Dequeue(Q); 
         ++temp_width; // 3分
         if ( p->Left != NULL )  Enqueue(p->Left, Q);
         if ( p->Right != NULL )  Enqueue(p->Right, Q); // 3分;  
         if ( Queue_front(Q) > Last ) {
            Last = Queue_rear(Q);
            if ( temp_width > max_width ) max_width = temp_width;
            temp_width = 0; // 3分;
         } /* end-if */
      } /* end-while */
      return  max_width;
   } /* end-else */
}

Exam 链表¶

#include <stdio.h>
void func(int *p) {
    p = p + 1;
}
int main() {
    int *p = (int *)malloc(20 * sizeof(int));
    for (int i = 0; i < 20; i++)
        p[i] = i + 1;
    printf("%d\n", *p);
    func(p);
    printf("%d\n", *p);
}