Data Structure Outline

---

对中等规模、大规模的图书摆放，你有什么更好的建议？

考虑大规模数据存储的时候会遇到的问题，以及根据功能（也就是关联的算法，最常见的就是插入、查找、删除）需要设计存储方式。

---

  方案1：线性排列
  Character：插入方便，查找困难，删除困难

---

  方案2：首字母排列
  Character：插入困难，查找方便，删除困难

---

  方案3：分类/多级分类
  Character：插入中等，查找中等，删除中等

Conclusion:数据的存储结构影响算法效率

---

Designing a function PrintN，Comparing the characteristics of loop and recursion.

void PrintN(N)
Input:Integer N
Output:Print 0 to N on screen.

---

  void PrintN1(int N)
  {
        int i;
        for(i=0;i<=N;i++) 
              printf("%d\n",i);
  }//Character:The memory of a variable.

---

  void PrintN2(int N)
  {
        if (N)
        {
              PrintN(N - 1);
              printf("%d\n", N);
        }
  }//Character:Occupies so much space,but read eazy maybe?

Conclusion:Efficiency of memory space affects algorithm efficiency.

---

Solve polynomial

---

  double function1(int n,double x)
  {
        int i;
        double result;
        result=1;
        for(i=1;i<=n;i++)
        {
              result+=pow(x,i)/i;
        }
        return result;
  }//Character:So much exponent operation.

---

Simplify polynomial to f(x) = 1+x(a+x(...(a+xa)...))

  double function2(int n,double x)
  {
        int i;
        double result=0;
        for(i=n;i>=1;i--)
        {
              result=(result+1/i)*x;
        }
        return result+1;
  }//Character:Only n times multiplication.

---

  #define TIMES 1e7
  typedef double (*function)(int,double);
  void Runtime(function fun，int n,double x)
  {
        int start,end,time;
        start=clock();
        for(i=0;i<TIMES;i++)
        fun(n,x);
        end=clock();
        time=end-start;
        printf("%d",time);
        return;
  }//Use to calculate the time of function run ten million times.

Conclusion:The ingenuity of the algorithm affects efficiency

---

数据结构的定义

• 数据对象的组织方式
  逻辑结构(线，树，图)
  存储结构(连续，随机，哈希)
  数据对象的处理方式(算法)

• 抽象数据类型
  数据类型（类）= 数据对象集合+操作算法集合
  抽象 ->
  +与存放数据的机器无关
  +与数据存储的物理结构无关
  +与实现操作的算法和编程语言无关

---

  ADT Matrix{
        Data element:D = {a[i][j]|a[i][j]∈A[M`*`N],i=1,2,...,M,j=1,2,...,N,A为M`*`N的矩阵}
        Stucture relation:R = {<a[i][j],a[i][j+1]>|a[i][j],a[i][j+1]∈A[M`*`N],i=1,2,...,M,j=1,2,...,N-1}
        Opration:
        1.MatrixCreat(M,N)
        Premise:M and N both are intager greater than zero.
        Result:Return an empty MxN Matrix.
        2.GetMaxRow(A)
        Premise:Matrix A is existence.
        Result:Return number of rows. 
        3.GetMaxCol(A)
        Premise:Matrix A is existence.            
        Result:Return number of columns.
        4.GetEntry(A,i,j)
        Premise:Matrix A is existence,and 1<=i<=GetMaxRow(A),1<=i<=GetMaxCol(A)
        Result:Return value of element in Matrix A ith row and jth columns. 
        5.MaxAdd(A,B)
        Premise:Matrix A and B are existence.
        Result:If the bumber of A's rows and columns is equal with B.return Matrix C=A+B,else return error sign.
        6.MaxMul(A,B)
        Premise:Matrix A and B are existence.
        Result:If A's columns is equal with B's rows,return Matrix C=AB,else return error sign.
        ...
  }

---

抽象数据类型的好处

• 类比于写作前的提纲，理清思路
• 抽象无关实现方式，帮助人们在理解这个数据类型的同时，不被具体实现的算法困扰。
• 实现数据类型时，对照着ADT可以保证代码的效率和准确度