c语言进阶15-数据结构总结

数据结构结论

1.阿基米德说过：“给我一个支点，我就能翘起地球”。

数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。记为：Data_Structure=(D,R)

2、数据：是能被计算机识别，并输入给计算机处理的符号集合。

3、数据元素：是数据的的基本单位，也被称为记录。

4、数据项：一个数据元素可以由若干个数据项组成。数据项是数据不可分割的最小单位。

5、数据对象：是性质相同的数据元素的集合，是数据的子集。

7、 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

8、数据结构：（1）逻辑结构 是数据元素之间的相互关系

（2）物理结构 是指数据的逻辑结构在计算机中的存储形式。

逻辑结构：①集合结构②线性结构（一对一）③树形结构（一对多）④图形结构（多对多）

物理结构包含：①顺序存储结构在逻辑上相邻的元素在物理上也相邻。

②链式存储结构把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。

9、 抽象数据类型：是一个数据模型，以及定义在该模型上一组操作。

第十二单元：值传递与地址传递

1**、**当参数为基本类型时，属于值传递，注意以下几点：

（1）**函数的实参和形参分别占有存储单元**

（2）**函数的实参复制一份值传给形参**

（3）**实参不会随着形参的变化而变化**

2**、**函数的地址传递是指参数是：数组或指针类型时，传递的是地址，而不是值。注意地址传递有以下特点：

（1）**函数的实参和形参共享存储单元**

（2）**函数是将实参的地址传给形参**

（3）**实参会随着形参的变化而变化，参数类型为：数组和指针**

3**、**数组做参数特点：

（1）**数组做参数传递的是数组的首地址。**

（2）**数组名表示数组的首地址（因此调用时候只写数组名）**

（3）**数组做参数属于地址传递，传递的是数组的首地址，或数组第一个元素的地址。**

4**、**数组做参数属于地址传递，数组可以是基本类型的数组：整型数组、浮点型数组、字符数组，当然数组也可以复杂类型的数组--结构体数组。当参数为结构体数组时，仍是地址传递。

算法

1、算法是程序设计的的灵魂。

2、 数据结构就是编程的思维，编程的灵魂

3、算法就是解决问题的方法和步骤**。**在计算机中表现为指令的有限序列。

4、著名计算机科学家（沃斯）提出一个公式：程序=数据结构+算法。

5、 经典算法：①分治算法（12枚硬币，找假硬币）②穷举算法（百钱买百鸡）③递推算法（猴子吃桃子）④迭代算法（斐波那契数列）

5**、算法的特性**

（1）有穷性:指算法在执行有限的步骤后自动结束、不会出现无限循环。

（2）确定性:算法的每一步骤都具有确定的含义，不会出现二义性。

（3）可行性:算法的每一步都必须是可行的，也就是说，每一步都能够通过执行有限次数完成。

（4）输入:算法可以具有零个或多个输入

（5）输出:算法至少有一个或多个输出

算法设计思想

1**、算法的设计要求**

（1）正确性:算法应当满足具体问题的需求。

（2）可读性:算法设计的另一目的是为了便于阅读、理解和交流。

（3）健壮性:当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果。

（4）时间效率高和存储量低

2. 算法的时间复杂度

O(1)叫做常数阶、O(n)叫线性阶、O(n2)叫平方阶。O(logn)叫对数阶

3.算法效率的度量方法：

①**事后统计方法**

②事前分析估算的方法

4. 高级程序语言编写的程序在计算机上运行时所消耗的时间取决于下列因素：

①算法采用的策略、方法。

②编译产生的代码质量。

③问题的输入规模。

④机器执行指令的速度

4.常用的时间复杂度所耗费的时间从小到大依次是：

O(1)<O(logn)< O(n)< O(nlogn)< O(n^2)< O(n^3)< O(2^n)< O(n!)<O(n^n)

5**．时间效率**用时间复杂度来衡量，存储量低用空间复杂度来衡量

\6. 时间复杂度 T（n）=O（f(n)） 空间复杂度 S（n）=O（f(n)）

n 输入规模 f（n）规模的函数 O 渐进符号

第十六七单元-线性表之顺序表

1、线性结构特点：存在唯一的一个称为“第一个”的元素，存在唯一的一个称为“最后一个”的元素，除第一个元素每个元素都要唯一的前驱，除最后一个元素每一个元素都有唯一的后继。

（唯一的头，唯一的尾，唯一前驱，唯一后继，头无前驱，尾无后继）

2、线性表：n个元素的有限序列。

3、线性表采用顺序存储称为顺序表。

4、顺序表每个元素占L字节，则第i个元素的位置为：

Loc(ai)=Loc(a1)+(i-1)*L （定位公式）

5、（1）顺序表中，插入、删除要平均移动约表中一半（n/2）的元素。

长度为n的顺序表	对第i 位置进行操作	平均移动次数	T（n）
插入	n-i+1	n/2	O(n)
删除	n-i	(n-1)/2	O(n)
修改	无	无	O(1)
查找	无	无	O(1)

7**、顺序表的优缺点**

优点：①可以随机存取任意位置的元素，即查找、修改方便。②存储密度大为1

缺点：（1）插入、删除要移动大量的元素。

（2）设置最大容量时过大容易浪费，过小容易溢出。

（3）造成存储空间的碎片。

线性表之链表

1、线性表的链式存储结构称为：链表。

链式存储结构：在逻辑上相邻的元素在物理上不一定相邻。

2、每个结点都包含两部分：数据域和指针域。

3、每个结点只含有一个指针域的链表称为单链表。链表为空条件head->next==NULL

4、单链表中，在p指针指向的结点后插入s指针指向的结点的语句序列是：

s->next=p->next; p->next=s;

5、在单链表中，删除p指针指向的直接后继的语句是：

p->next=p->next->next;

删除p指针指向结点的后继结点并回收空间，指针域为next，语句序列是

q=p->next; p->next=p->next->next; free(q);

6、单链表操作时间复杂度分析

插入 O（1） //在p指针指向的结点后插入s指针指向的结点

删除 O（1） //删除p指针指向的直接后继

查找 O（n） //查找链表的第i个元素

修改 O（n） //修改链表的第i个元素为e

7、链表的优缺点：

优点：（1）插入、删除元素方便，避免移动大量的元素。

（2）几乎不存在溢出的状况

缺点：需要额外的空间来存储指针域，所以存储密度小于1

8、线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。

若需要频繁插入和删除时，宜采用单链表结构。

英文日历

#include "stdio.h"

#include "string.h"

#include "windows.h"

int year;

int mothday(int moth)

{

    switch (moth)

    {

        case :

        case :

        case :

        case :

        case :

        case :

        case :

        return ;

        break;

        case :

        case :

        case :

        case :

        return ;

        break;

        case :

        if(year%==&&year%!=||year%==)

        {

            return ;

        }else

        {

            return ;

        }

        break;

        }

    }

void main()

{

    int i,d,j,days,weekDay;//days为

    printf("请输入年份:");

    scanf("%d",&year);

    days=year-+(year-)/+(year-)/-(year-)/;

    system("cls");

    for(i=;i<;i++)

    {

         printf("\t\t\t%d-%d\n",year,i);

         printf("Sun\tMon\tTues\tWed\tThur\tFir\tSat\n");

         d=,j=;

           weekDay=(days+)%;//只为把它隔开

        /* printf("\t\t\t%d\n",weekDay);*/

         while(j<=weekDay)

         {

             printf("\t");

             j++;

         }

         weekDay=days;

         while(d<=mothday(i))

         {

             printf("%3d\t",d);

             d++;

             days++;

                 if((d+weekDay)%==)

             {

                 printf("\n");

                 }    

         }

         printf("\n");

    }

}

万通水世界

/* Note:Your choice is C IDE */

#include "stdio.h"

#include "stdlib.h"

#include "string.h"

void tickets()

    {

            char mc[],lx[];//名称 类型

            int ps,i,z,x=;//票数 变量 o或1  差

            printf("请输入水世界名称:");

            scanf("%s",mc);

            printf("\n");

    for(i=;i<=;i++)

    {

            printf("请输入购买票数:");

            scanf("%d",&ps);

            printf("请选择票务类型通票/单票:");

            scanf("    %s",lx);

            printf("顾客您好,请您确认信息:\n");

    if(strcmp(lx,"单票")==)

    {

            printf("您选择水世界的名称是%s,票数是%d张,类型是%s\n",mc,ps,lx);

            printf("确认请输入1,取消请输入0:");

            scanf("%d",&z);

            if(z==)

            {

            printf("顾客您好,本次购票需支付票务金额为70元\n");

            printf("是否继续购0/1:");

            scanf("%d",&z);

            }

            printf("\n");

    }

    else if(strcmp(lx,"通票")==)

    {

            printf("您选择水世界的名称是%s,票数是%d张,类型是%s\n",mc,ps,lx);

            printf("确认请输入1,取消请输入0:");

            scanf("%d",&z);

            if(z==)

            {

            printf("本次订票需支付票务金额是115元\n");

            printf("顾客支付金额:");

            scanf("%d",&z);

            x=z-;

            printf("欢迎您光临万通水世界,找零金额为%d元",x);

            }

            printf("\n");

    }

    }//for运行结束

    }//调用函数结束

void activity()

{

        int nl,i,fs,x;//年龄 变量 分数 大于四十  小于四十

        int nlcount=,fscount=;

        double zs=0.0,ff=0.0;//小于等于四十占得人数

        printf("随即五位游客调查查满意度\n");

        for(i=;i<=;i++)

        {

            printf("请输入您的年龄:");

            scanf("%d",&nl)    ;

            printf("请您为本次服务打分0-100 80为合格线:");

            scanf("%d",&fs);

            if(nl<=)//小于40岁的累积

            {

                nlcount++;

                }

            if(fs>=)//及格人数的累积

            {

                fscount++;

                }

        }//for运行结束

            zs=nlcount/5.00*;

            ff=fscount/5.00*;

        printf("本次调查显示万通水世界年龄<=40的游客占%.2f%%,合格率为%.2f%%",zs,ff);

}//调用函数运行结束

void main()

{

       int i,bh;//变量 编号

       for(;;)

       {

               printf("\n\t\t万通水世界\n");

               printf("\t\t1.购票结算\n");

               printf("\t\t2.投票活动\n");

               printf("\t\t0.退出\n");

               printf("请输入功能编号:");

               scanf("%d",&bh);

               switch(bh)

               {

                   case :tickets();break;//编号1结束

                   case :activity();

                   break;//编号2结束

                   case :exit();

                   default:printf("您输入的功能编号有误,请重新输入\n");break;

               }

       }//for循环结束

}//最后结束

小游戏推箱子

/* Note:Your choice is C IDE */

#include "stdio.h"

#include "string.h"

#include "stdlib.h"

char arr[][];

void main()

{

    int i;

    int p,q;

    int x=,y=;

    char b;

        char arr[][]={

        "##########",

        "##     ###",

        "##o###   #",

        "#  so  o #",

        "# **# o ##",

        "##**#   ##",

        "##########",

        };

          system ( "mode con cols=60 lines=28" );

        for(i=;i<;i++){

        puts(arr[i]);

        }

  for(;;){

      b=getch();

      switch(b){

      case 'w':

      if(arr[x-][y]!='#'){

          arr[x][y]=' ';

          x--;

          if(arr[x][y]=='o'){

              if(arr[x-][y]!='#'){

              arr[x][y]='s';

              arr[x-][y]='o';}else{

              x++;

              arr[x][y]='s';

              }

              }else{

           arr[x][y]='s';

          }

          system("cls");

          for(i=;i<;i++){

        puts(arr[i]);

       }

      }break;

      case 's':

      if(arr[x+][y]!='#'){

          arr[x][y]=' ';

          x++;

          if(arr[x][y]=='o'){

              if(arr[x+][y]!='#'){

              arr[x][y]='s';

              arr[x+][y]='o';}else{

              x--;

              arr[x][y]='s';

              }

              }else{

           arr[x][y]='s';

          }

          system("cls");

          for(i=;i<;i++){

        puts(arr[i]);

       }

      }break;

      case 'd':

      if(arr[x][y+]!='#'){

          arr[x][y]=' ';

          y++;

          if(arr[x][y]=='o'){

              if(arr[x][y+]!='#'){

              arr[x][y]='s';

              arr[x][y+]='o';}else{

              y--;

              arr[x][y]='s';

              }

              }else{

           arr[x][y]='s';

          }

          system("cls");

          for(i=;i<;i++){

        puts(arr[i]);

       }

      }break;

      case 'a':

      if(arr[x][y-]!='#'){

          arr[x][y]=' ';

          y--;

          if(arr[x][y]=='o'){

                  if(arr[x][y-]!='#'){

              arr[x][y]='s';

              arr[x][y-]='o';}else{

                  y++;

              arr[x][y]='s';

              }

              }else{

           arr[x][y]='s';

          }

          system("cls");

          for(i=;i<;i++){

        puts(arr[i]);

       }

      }

      }

      for(p=;p<;p++){

          for(q=;q<;q++){

            if(arr[p][q]==' '){

             arr[p][q]='*';

                 }

           }

      }

    system("cls");

          for(i=;i<;i++){

        puts(arr[i]);

       }

      if(arr[][]=='o'&&arr[][]=='o'&&arr[][]=='o'&&arr[][]=='o'){

          printf("\t\t恭喜通关\n");

          break;

          }

      }

}

巴特西