8.2.2 算法设计的步骤
描述问题——建立模型——设计算法——验证算法正确性——算法实现—— 算法分析
程序 = 算法 + 数据结构

8.2.3 几种基本的算法设计方法
1 枚举法：从问题的所有可能答案中找出满足条件的解。
e.g   买鸡问题：公鸡每只5元，母鸡每只3元，小鸡3只一元，100元买100只鸡，有多少种买法？
main()
{int x,y,z;
    for(x=1;x<=20;x++)
       for(y=1;y<=33;y++)
          { z=100-x-y;                     /*百鸡*/
             if(5*x+3*y+z/3= =100)
                 printf(“cock=%3d, hen=%3d,  
                          Chicken=%3d\n”, x,y,z);
}

2   归纳法：找出问题的规律
e.g   高斯计算1到100之和。
（1） 递推：逐次推求中间结果和最后结果
e.g 计算Fibonacci数列：数列第1项为1，第2项为1，从第三项开始，每一项等于前两项之和。
      f = (1,1,2,3,5,8,13,21,34,…… )

实现途径：利用数组
      请大家自己编程实现
（2）递归：自己调用自己
e.g 计算阶乘
       F(n)=F(n-1)*n,     F(1)=1
main()
{int fn();
    int f, n;
    scanf(“%d”,&n);
    f=fn(n);
   printf(“the result is %d”,f);   
}

int fn(int n)
{ if(n= =0||n= =1)
       return(1);
    else
      return(n*fn(n-1));
}

3   回溯法：通过“试”找到问题的解。
      如在一些游戏中，找出一个解决问题的途径，然后选出一条“试走”，若此路不通，退回换路线重走。

4   数字模拟法：数字仿真
问题很难建立数学模型，用随机数模拟随机现象。
计算时间复杂度的例子
# define n 4
matrixmlt(A,B,C)
float A[n][n],B[n][n],C[n][n];
   {int i,j,k;
     for(i=0;i<n;i++)                                          n+1
        for(j=0;j<n;j++)                                     n(n+1)
          {C[i][j]=0;                                              n2  
            for(k=0;k<n;k++)                               n2 (n+1)
               C[i][j]=C[i][j]+A[i][k]*B[k][j];         n3
           }
}
T(n)=2n3+3n2+2n+1   T(n)=2n3+3n2+2n+1
当n趋于无穷时T(n)和n3同阶，数量级相同         T(n)=O(n3): 算法的渐近时间复杂度
一般都用频度最大的语句来进行度量

本节重点：
1 基本概念：习题1
2 数据的逻辑结构、存储结构区别与联系

在各种程序设计与软件开发中都要涉及到对数据的组织、存储、管理和处理
在环境领域：不同环境监测点的监测指标统计
在土地领域：不同宗地的属性
在测绘领域：外业测绘信息的存储，各测点三维坐标的存储
最常见的数据组织方式：表格形式的数据

9.1.2 线性表的运算
运算；定义在逻辑结构上，通过存储结构实现
•   置空表 SETNULL(L)
• 求长度 LENGTH(L)
• 定位 LOCATE(L,x)
   已知x=84, i=LOCATE(L, 84) = 3
• 插入 INSERT(L,x,i)：在i位置插入值为x的元素   INSERT(L, 87, 3)
• 删除DELETE(L,i)     DELETE(L,3)
• 取直接前趋 PRIOR(L, ai)
• 取直接后继 NEXT(L, ai)
e.g 清除线性表L中多余的重复结点
PURGE(L)
Linear_List *L;
{ int i=1, j, x, y;
   while(i<LENGTH(L))
     {x=GET(L, i);
      j=i+1;
     while(j<LENGTH(L))
        {y=GET(L,j);
           if(x==y) DELETE(L,j);
           else j++;
         }
       i++;
      }
}

用C语言中的向量（一维数组）描述顺序表
Typedef   int datatype;
#define maxsize 1024
Typedef struct
{ datatype data[maxsize];
     int last;
}sequenlist;
以物理位置的紧邻表示线性表中数据元素之间相邻的逻辑关系。
int INSERT(sequenlist *L, int x, int i)
{int j;
   if(L->last)>=maxsize-1
   {printf(“overflow”; return 0); }
   else
   if((i<1)||(i>(L->last)+2))
   {printf(“error”);return(NULL);}
   else
   {for(j=L->last;j<=i-1;j--)
       L->data[j+1]=L->data[j];
       L->data[i-1]=x;
       L->last=L->last+1;
   }
   return(1);
}
2 删除运算
int DELETE(sequenlist *L, int i)
{int j;
   if((i<1)||(i>L->last+1))
   {printf(“error”);return(0);}
     else
   {for(j=i;j<=L->last;j--)
       L->data[j-1]=L->data[j];
       L->last--;
   }
   return(1);
}
单链表可以用头指针的名字来命名。
typedef int datatype;
typedef struct node
{ datatype data;
    struct node *next;
}linklist;
Linklist *head,*p;

P=malloc(sizeof(linklist));        free(p);

9.3.2 单链表的基本运算
1 建立单链表
（1）头插法建表
Linklist *CREATLISTF( )
{char ch;
   linklist *head, *s;
   head=NULL;
   ch=getchar();
   while(ch!=‘$’)
      {s=(linklist*)malloc(sizeof(linklist));
        s->data=ch;
        s->next=head;
       head=s;
       ch=getchar();
      }
   return head;
}

(2) 尾插法建表
Linklist *CREATLISTR( )
{char ch;
   linklist *head, *s, *r;
   head=NULL;   r=NULL;
   ch=getchar();
   while(ch!=‘$’)
      {s=(linklist*)malloc(sizeof(linklist));
        s->data=ch;
       if (head=NULL) head=s;
       else r->next=s;
        r=s;
       ch=getchar();
      }
if (r!=NULL) r->next=NULL;
return head;
}
带头结点的单链表
Linklist *CREATLISTR1( )
{char ch;
   linklist *head, *s, *r;
   head= (linklist*)malloc(sizeof(linklist));
   r=head;
   ch=getchar();
   while(ch!=‘$’)
      {s=(linklist*)malloc(sizeof(linklist));
        s->data=ch;
   &