精华内容
参与话题
问答
  • 数据结构详解

    千次阅读 2015-05-14 23:19:14
    第一课:数据结构的基本概念和术语 第二课:抽象数据类型的表示与实现 第三课:算法及算法设计要求 第四课:算法效率的度量和存储空间需求 第五课:线性表的类型定义 第六课:线性表的顺序表示和实现 第七课:...
    第一课:数据结构的基本概念和术语
    第二课:抽象数据类型的表示与实现
    第三课:算法及算法设计要求
    第四课:算法效率的度量和存储空间需求
    第五课:线性表的类型定义
    第六课:线性表的顺序表示和实现
    第七课:实验一线性表的顺序存储实验
    第八课:线性表的链式表示与实现
    第九课:循环链表与双向链表
    第十课:栈的表示与实现
    第十一课:栈的应用
    第十二课:实验二循环链表实验
    第十三课:队列
    第十四课:串的定义
    第十五课:串的表示和实现
    第十六课:串操作应用举例
    第十七课:实验三:栈的表示与实现及栈的应用
    第十八课:数组的顺序表示与实现
    第十九课:实验四串的实现实验
    第二十课:广义表
    第二十一课:树、二叉树定义及术语
    第二十二课:实验五数组实验
    第二十三课:二叉树的存储结构
    第二十四课:遍历二叉树
    第二十五课:单元测验
    第二十六课:图的定义与术语
    第二十七课:实验六二叉树实验
    第二十八课:图的存储结构
    第二十九课:静态查找表(一)顺序表的查找
    第三十课:静态查找表(二)有序表的查找
    第三十一课:动态查找表
    第三十二课:哈希表(一)
    第三十三课:哈希表(二)
    第三十四课:插入排序,快速排序
    第三十五课:实验七查找
    第三十六课:选择排序,归并排序
    第三十七课:实验八排序实验
    第三十八课:文件概念,顺序文件
    第三十九课:索引文件
    第四十课:总复习
     
     
     
    第一课
    本课主题:数据结构的基本概念和术语
    教学目的:了解数据结构的基本概念,理解常用术语
    教学重点:基本概念:数据与数据元素
    教学难点:数据元素间的四种结构关系。
    授课内容:
    一、数据、数据元素、数据对象、数据结构的定义
    1、数据的定义
    定义一:数据是客观事物的符号表示。
    学号
    姓名
    语文
    数学
    C语言
    6201001
    张三
    85
    54
    92
    6201002
    李四
    92
    84
    64
    6201003
    王五
    87
    74
    73
    6201004
     
     
     
     
    ...
     
     
     
     
    例:张三的C语言考试成绩为92分,92就是该同学的成绩数据。
    定义二:能输入到计算机中并被计算机程序处理的符号的总称。
    例:图像、声音等。
    总结:现实世界信息的分析、复制、传播首先要符号化,这样才便于处理,尤其是便于计算机的处理。家长、社会要了解一个学生的学习成绩和能力,要看他的学习档案,而学习档案即是说明该学生学习情况的数据。
    2、数据元素、数据项
    数据元素是数据的基本单位,它也可以再由不可分割的数据项组成。如图示:
    3、数据对象
    是性质相同的数据元素的集合。如上例:一个班级的成绩表可以看作一个数据对象。
    4、数据结构
    定义一、数据元素集合(也可称数据对象)中各元素的关系。
    定义二、相互之间存在特定关系的数据元素集合。
    数据结构的种类:
     
    特征
    示例
    集合
    元素间为松散的关系
    线性结构
    元素间为严格的一对一关系
    如上面的成绩表中各元素
    树形结构
    元素间为严格的一对多关系
    图状结构(或网状结构)
    元素间为多对多关系
    数据结构的形式定义:
    数据结构名称=(D,S)
    其中D为数据元素的有限集,S是D上关系的有限集
    逻辑结构
     
    “数据结构”定义中的“关系”指数据间的逻辑关系,故也称数据结构为逻辑结构。
    存储结构
     
    数据结构在计算机中的表示称为物理结构。又称存储结构。
    顺序存储结构
    链式存储结构
    存储结构详解:
    计算机中存储信息的最小单位:,8位为一字节,两个字节为一字,字节、字或更多的二进制位可称为位串。在逻辑描述中,把位串称为元素或结点
    当数据元素由若干数据项组成时,位串中对应于各个数据项的子位串称为数据域(Data Field)。
    例:上述成绩表数据用C语言的结构体数组classonestu[50]来存储:
    struct stu {
    int stuno;/*数据项,也称stu位串中的一个子位串,或叫做数据域*/ 
    char name[20];
    int maths;
    int language;
    int c_language;
    } classonestu[50];
    二、数据类型
    1、定义:数据类型是一个值的集合和定义在这个值集上的一组操作的总称。
    例:C语言中的整型,其内涵为一定范围的自然数集合,及定义在该集合上的加减乘除及取模、比较大小操作。而实型则无取模操作。当然整型也不需四舍五入。
    2、数据类型的种类:
     
    特征
    原子类型
    值在逻辑上不可分解
    int float
    结构类型
    值由若干成分按某种结构组成
    struct stu
    数据类型封装了数据存储与操作的具体细节。
    三、总结
    数据->数据元素
    具有特定关系的数据元素集合->数据结构
    数据结构的逻辑表示与物理存储->逻辑结构与存储结构
    人们不仅关心数据的逻辑结构、存储结构,还关心数据的处理方法(算法)与处理结果->数据类型
    数据类型->分类
    第二课
    本课主题: 抽象数据类型的表示与实现
    教学目的: 了解抽象数据类型的定义、表示和实现方法
    教学重点: 抽象数据类型表示法、类C语言语法
    教学难点: 抽象数据类型表示法
    授课内容:
    一、抽象数据类型定义(ADT)
    作用:抽象数据类型可以使我们更容易描述现实世界。例:用线性表描述学生成绩表,用树或图描述遗传关系。
    定义:一个数学模型以及定义在该模型上的一组操作。
    关键:使用它的人可以只关心它的逻辑特征,不需要了解它的存储方式。定义它的人同样不必要关心它如何存储。
    例:线性表这样的抽象数据类型,其数学模型是:数据元素的集合,该集合内的元素有这样的关系:除第一个和最后一个外,每个元素有唯一的前趋和唯一的后继。可以有这样一些操作:插入一个元素、删除一个元素等。
    抽象数据类型分类
    原子类型
    值不可分解,如int
    固定聚合类型
    值由确定数目的成分按某种结构组成,如复数
    可变聚合类型
    值的成分数目不确定如学生基本情况
    抽象数据类型表示法:
    一、
    三元组表示:(D,S,P)
    其中D是数据对象,S是D上的关系集,P是对D的基本操作集。
    二、书中的定义格式:
    ADT 抽象数据类型名{
    数据对象:<数据对象的定义>
    数据关系:<数据关系的定义>
    基本操作:<基本操作的定义>
    }ADT 抽象数据类型名
    例:线性表的表示
    名称
    线性表
     
    数据对象
    D={ai| ai(-ElemSet,i=1,2,...,n,n>=0}
    任意数据元素的集合
    数据关系
    R1={<ai-1,ai>| ai-1,ai(- D,i=2,...,n}
    除第一个和最后一个外,每个元素有唯一的直接前趋和唯一的直接后继
    基本操作
    ListInsert(&L,i,e)
    L为线性表,i为位置,e为数据元素。
    ListDelete(&L,i,e)
    ...
    二、类C语言语法
    类C语言语法示例
       
    1、预定义常量和类型
    #define TRUE 1
    #define FALSE 0
    #define OK 1
    #define ERROR 0
    #define INFEASIBLE -1
    #define OVERFLOW -2
    typedef in Status; //Status是函数的类型,其值是函数结果状态代码。
     
    2、数据结构的存储结构
    typedef ElemType first;
     
    3、基本操作的算法
    函数类型 函数名(函数参数表){
    //算法说明
    语句序列
    }//函数名
     
    4、赋值语句
    简单赋值:
    变量名=表达式;
     
    串联赋值:
    变量名1=变量名2=...=变量名k=表达式;
     
    成组赋值:
    (变量名1,...,变量名k)=(表达式1,...,表达式k);
    结构名=结构名;
    结构名=(值1,...,值k);
    变量名[]=表达式;
    变量名[起始下标..终止下标]=变量名[起始下标..终止下标];
    交换赋值:
    变量名<-->变量名;
     
     
    条件赋值:
    变量名=条件表达式?表达式?表达式T:表达式F
     
     
    5、选择语句
    1、if(表达式) 语句;
    2、if(表达式) 语句;
    else 语句;
    3、switch(表达式){
    case 值1:语句序列1;break;
    ...
    case 值n:语句序列n;break; 
    default:语句序列n+1;break; 
    }
    4、switch{
    case 条件1:语句序列1;break;
    ...
    case 条件n:语句序列n;break; 
    default:语句序列n+1;break; 
    }
     
     
    6、循环语句
    for(赋初值表达式;条件;修改表达式序列)语句;
    while(条件)语句;
    do{ 语句序列}while(条件);
     
     
    7、结束语句
    return [表达式];
    return; //函数结束语句
    break; //case结束语句
    exit(异常代码); //异常结束语句
     
     
    8、输入和输出语句
    scanf([格式串],变量1,...,变量n);
     
     
    9、注释
    //文字序列
     
     
    10、基本函数
    max(表达式1,...,表达式n)
    min,abs,floor,ceil,eof,eoln
     
     
    11、逻辑运算
    &&与运算;||或运算
     
     
    例:线性表的实现:
    ADT List{
    数据对象: D={ai| ai(-ElemSet,i=1,2,...,n,n>=0}
    数据关系: R1={<ai-1,ai>| ai-1,ai(- D,i=2,...,n}
    基本操作:
    InitList(&L)
    DestroyList(&L)
    ListInsert(&L,i,e)
    ListDelete(&L,i,&e)
    }ADT List
    ListInsert(List &L,int i,ElemType e)
    {if(i<1||i>L.length+) return ERROR;
    q=&(L.elem[i-1]);
    for(p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p;
    *q=e;
    ++L.length;
    return OK;
    }
    #define ERROR 0 
    #define OK 1 
    struct STU
    { char name[20];
    char stuno[10]; 
    int age; int score; 
    }stu[50]; 
    struct LIST 
    { struct STU stu[50]; 
    int length; 
    }L; 

    int printlist(struct LIST L)
    { int i;
    printf("name stuno age score/n"); 
    for(i=0;i<L.length;i++) 
    printf("%s %s/t%d/t%d/n", L.stu[i].name, L.stu[i].stuno, L.stu[i].age, L.stu[i].score); 
    printf("/n"); 
    }

    int listinsert(struct LIST *L,int i,struct STU e) 
    { struct STU *p,*q; 
    if (i<1||i>L->length+1) 
    return ERROR; 
    q=&(L->stu[i-1]); 
    for(p=&L->stu[L->length-1];p>=q;--p) 
    *(p+1)=*p; *q=e; ++L->length; 
    return OK; 
    }/*ListInsert Before i */

    main() 
    { struct STU e; 
    L.length=0; 
    strcpy(e.name,"zmofun"); 
    strcpy(e.stuno,"100001"); 
    e.age=80; 
    e.score=1000; 
    listinsert(&L,1,e); 
    printlist(L); 
    printf("List length now is %d./n/n",L.length);
    strcpy(e.name,"bobjin"); 
    strcpy(e.stuno,"100002"); 
    e.age=80; 
    e.score=1000; 
    listinsert(&L,1,e); 
    printlist(L); 
    printf("List length now is %d./n/n",L.length); 
    }
     
    E:/ZM/Zmdoc/datastru/class02>listdemo
    name stuno age score
    zmofun 100001 80 1000
    List length now is 1.
    name stuno age score
    bobjin 100002 80 1000
    zmofun 100001 80 1000
    List length now is 2.

    三、总结
    抽象数据类型实现方法:一、类C语言实现 二、C语言实现
    第三课
    本课主题: 算法及算法设计要求
    教学目的: 掌握算法的定义及特性,算法设计的要求
    教学重点: 算法的特性,算法设计要求
    教学难点: 算法设计的要求
    授课内容:
    一、算法的定义及特性
    1、定义:
    ispass(int num[4][4])
    { int i,j; 
    for(i=0;i<4;i++)
    for(j=0;j<4;j++)
    if(num[i][j]!=i*4+j+1)/*一条指令,多个操作*/
    return 0;
    return 1; 
    }/*上面是一个类似华容道游戏中判断游戏是否结束的算法*/
    算法是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示一个或多个操作;此外,一个算法还具有下列五个重要特性:
    2、算法的五个特性:
    有穷性
    一个算法必须总是(对任何合法的输入值)在执行有穷步之后结束,且每一步都可在有穷时间内完成;
    确定性
    算法中每一条指令必须有确切的含义,读者理解时不会产生二义性。有任何条件下,算法只有唯一的一条执行路径,即对于相同的输入只能得出相同的输出。
    可行性
    一个算法是能行的,即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。
    输入
    一个算法有零个或多个的输入,这些输入取自于某个特定的对象的集合。
    输出
    一个算法有一个或多个的输出。这些输出是同输入有着某些特定关系的量。
    例:
    有穷性
    haha()
    {/*only a joke,do nothing.*/

    main()
    {printf("请稍等...您将知道世界的未日...");
    while(1)
    haha(); 
    }
    确定性
    float average(int *a,int num)
    {int i;long sum=0;
    for(i=0;i<num;i++)
    sum+=*(a++);
    return sum/num;
    }
    main()
    {int score[10]={1,2,3,4,5,6,7,8,9,0};
    printf("%f",average(score,10);
    }
    可行性
     
    输入
     
    输出
    getsum(int num)
    {
    int i,sum=0;
    for(i=1;i<=num;i++)
    sum+=i; 
    } /*无输出的算法没有任何意义,
    二、算法设计的要求
    1、正确性
    算法正确性的四个层次
    程序不含语法错误。
    max(int a,int b,int c)
    {
    if (a>b)
    {if(
    a>c) return c;
    else return 
    a;

    }
    程序对于几组输入数据能够得出满足规格说明要求的结果。
    max(int a,int b,int c)
    {
    if (a>b)
    {if(a>c) return a;
    else return c;

    } /* 
    8,6,7 */ /* 9,3,2 */
    程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果。
    max(int a,int b,int c)
    {
    if (a>b)
    {if(a>c) return a;
    else return c;

    else
    {if(b>c) return b;
    else return c;

    }
    程序对于一切合法的输入数据都能产生满足规格说明要求的结果。
     
    2、可读性
    3、健壮性
    4、效率与低存储量需求
    效率指的是算法执行时间。对于解决同一问题的多个算法,执行时间短的算法效率高。
    存储量需求指算法执行过程中所需要的最大存储空间。
    两者都与问题的规模有关。
     
    算法一
    算法二
    在三个整数中求最大者
    max(int a,int b,int c)
    {if (a>b)
    {if(a>c) return a;
    else return c;

    else
    {if(b>c) return b;
    else return c; 
    }/*无需额外存储空间,只需两次比较*/
    max(int a[3])
    {int c,int i;
    c=a[0]; 
    for(i=1;i<3;i++)
    if (a[i]>c) c=a[i];
    return c;

    /*需要两个额外的存储空间,两次比较,至少一次赋值*/

    /*共需5个整型数空间*/
    求100个整数中最大者
    同上的算法难写,难读
    max(int a[100])
    {int c,int i;
    c=a[0]; 
    for(i=1;i<
    100;i++)
    if (a[i]>c) c=a[i];
    return c;
    }
    /*共需102个整型数空间*/
    三、总结
    2、算法设计要求:正确性、可读性、健壮性、效率与低存储量需求。
    第四课
    本课主题: 算法效率的度量和存储空间需求
    教学目的: 掌握算法的渐近时间复杂度和空间复杂度的意义与作用
    教学重点: 渐近时间复杂度的意义与作用及计算方法
    教学难点: 渐近时间复杂度的意义
    授课内容:
    一、算法效率的度量
    算法执行的时间是算法优劣和问题规模的函数。评价一个算法的优劣,可以在相同的规模下,考察算法执行时间的长短来进行判断。而一个程序的执行时间通常有两种方法:
    1、事后统计的方法。
    缺点:不利于较大范围内的算法比较。(异地,异时,异境)
    2、事前分析估算的方法。
    程序在计算机上运行所需时间的影响因素
    算法本身选用的策略
     
    问题的规模
    规模越大,消耗时间越多
    书写程序的语言
    语言越高级,消耗时间越多
    编译产生的机器代码质量
     
    机器执行指令的速度
     
    综上所述,为便于比较算法本身的优劣,应排除其它影响算法效率的因素。
    从算法中选取一种对于所研究的问题来说是基本操作的原操作,以该基本操作重复执行的次数作为算法的时间量度。(原操作在所有该问题的算法中都相同)
    T(n)=O(f(n))
    上示表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度,简称时间复杂度
    求4*4矩阵元素和,T(4)=O(f(4))
    f=n*n;
    sum(int num[4][4])
    { int i,j,r=0; 
    for(i=0;i<4;i++)
    for(j=0;j<4;j++)
    r+=num[i][j]; /*原操作*/
    return r; 
    }
    最好情况:
    T(4)=O(0)
    最坏情况:
    T(4)=O(n*n)
    ispass(int num[4][4])
    { int i,j; 
    for(i=0;i<4;i++)
    for(j=0;j<4;j++)
    if(num[i][j]!=i*4+j+1)
    return 0;
    return 1; 
    }
    原操作执行次数和包含它的语句的频度相同。语句的频度指的是该语句重复执行的次数。
    语句
    频度
    时间复杂度
    {++x;s=0;}
    1
    O(1)
    for(i=1;i<=n;++i)
    {++x;s+=x;}
    n
    O(n)
    for(j=1;j<=n;++j)
    for(k=1;k<=n;++k)
    {++x;s+=x;}
    n*n
    O(n*n)
     
     
    O(log n)
     
     

     
    基本操作的执行次数不确定时的时间复杂度
    平均时间复杂度
    依基本操作执行次数概率计算平均
    最坏情况下时间复杂度
    在最坏情况下基本操作执行次数
     
    二、算法的存储空间需求
    类似于算法的时间复杂度,空间复杂度可以作为算法所需存储空间的量度。
    记作:
    S(n)=O(f(n))
    若额外空间相对于输入数据量来说是常数,则称此算法为原地工作
    如果所占空间量依赖于特定的输入,则除特别指明外,均按最坏情况来分析。
    三、总结
    渐近时间复杂度
    空间复杂度
    第五课
    本课主题: 线性表的类型定义
    教学目的: 掌握线性表的概念和类型定义
    教学重点: 线性表的类型定义
    教学难点: 线性表的类型定义
    授课内容:
    线性结构的特点:
    在数据元素的非空有限集中,
    (1)存在唯一的一个被称做“第一个”的数据元素;
    (2)存在唯一的一个被称做“最后一个”的数据元素;
    (3)除第一个之外,集合中的每个数据元素均只有一个前驱;
    (4)除最后一个之外,集合中每个数据元素均只有一个后继。
     
    一、线性表的定义
    线性表是最常用且最简单的一种数据结构。
    一个线性表是n个数据元素的有限序列。
    数据元素可以是一个数、一个符号、也可以是一幅图、一页书或更复杂的信息。
    线性表例:
    1、
    1
    2
    3
    4
    5
    6
    7
    2、
    3、
    学号
    姓名
    语文
    数学
    C语言
    6201001
    张三
    85
    54
    92
    6201002
    李四
    92
    84
    64
    6201003
    王五
    87
    74
    73
    6201004
     
     
     
     
    ...
     
     
     
     
    数据元素也可由若干个数据项组成(如上例3)。这时常把数据元素称为记录。含有大量记录的线性表又称文件
    线性表中的数据元素类型多种多样,但同一线性表中的元素必定具有相同特性,即属同一数据对象,相邻数据元素之间存在着序偶关系。
    a1
    ...
    ai-1
    ai
    ai+1
    ...
    an
    aiai+1直接前驱元素,ai+1ai直接后继元素。
    线性表中元素的个数n定义为线性表的长度,为0时称为空表。在非空表中的每个数据元素都有一个确定的位置。ai是第i个元素,把i称为数据元素ai在线性中的位序
    二、线性表的类型定义
    1、抽象数据类型线性表的定义如下:
    ADT List{
    数据对象: D={ai| ai(-ElemSet,i=1,2,...,n,n>=0}
    数据关系: R1={<ai-1,ai>| ai-1,ai(- D,i=2,...,n}
    基本操作:
    InitList(&L)
    DestroyList(&L)
    ClearList(&L)
    ListEmpty(L)
    ListLength(L)
    GetElem(L,i,&e)
    LocateElem(L,e,compare())
    PriorElem(L,cur_e,&pre_e)
    NextElem(L,cur_e,&next_e) 
    ListInsert(&L,i,e)
    ListDelete(&L,i,&e)
    ListTraverse(L,visit()) 
    union(List &La,List &Lb)
    }ADT List
    2、部分操作的类C实现:
    InitList(&L)
    {L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
    if(!L.elem)exit(OVERFLOW);
    L.length=0;
    L.listsize=LIST_INIT_SIZE;
    return OK;
    }//InitList
    GetElem(L,i,&e)
    {*e=L.lem[i]
    }//GetElem
    ListInsert(List &L,int i,ElemType e)
    {if(i<1||i>L.length+) return ERROR;
    q=&(L.elem[i-1]);
    for(p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p;
    *q=e;
    ++L.length;
    return OK;
    }//ListInsert
    void union(List &La,List &Lb)
    {La_len=ListLength(La);Lb_len=ListLength(Lb);
    for(i=1;i<=Lb_len;i++){
    GetElem(Lb,i,e);
    if(!LocateElem(La,e,equal))
    ListInsert(La,++La_len,e);
    }//union
    void MergeList(List La,List Lb,List &Lc)
    {InitList(Lc);
    i=j=1;k=0;
    La_len=ListLength(La);Lb_len=ListLength(Lb);
    while((i<=La_len)&&(j<Lb_len)){
    GetElem(La,i,ai);GetElem(Lb,j,bj);
    if(ai<=bj){ListInsert(Lc,++k,ai);++i;}
    else{ListInsert(Lc,++k,bj);++j;}
    }
    while(k<=La_len){
    GetElem(La,i++,ai);ListInsert(Lc,++k,ai);
    }
    while(j<=Lb_len){
    GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);
    }
    }//MergeList
    3、部分操作的C语言实现,下面是程序运行的结果
    -------------------List Demo is running...---------------- 
    First is InsertList function. 
    name stuno age score 
    stu1 100001 80 1000 
    stu2 100002 80 1000 
    List A length now is 2. 
    name stuno age score 
    stu1 100001 80 1000 
    stu2 100002 80 1000 
    stu3 100003 80 1000 
    List A length now is 3. 
    name stuno age score 
    zmofun 100001 80 1000 
    bobjin 100002 80 1000 
    stu1 100001 80 1000 
    List B length now is 3.
    Second is UnionList function. 
    Now union List A and List B..... 
    name stuno age score 
    stu1 100001 80 1000 
    stu2 100002 80 1000 
    stu3 100003 80 1000 
    zmofun 100001 80 1000 
    bobjin 100002 80 1000 
    List A length now is 5.
    Welcome to visit http://zmofun.heha.net !
    三、总结
    第六课
    本课主题: 线性表的顺序表示和实现
    教学目的: 掌握线性表的顺序表示和实现方法
    教学重点: 线性表的顺序表示和实现方法
    教学难点: 线性表的顺序存储的实现方法
    授课内容:
    复习
    1、存储结构
    逻辑结构
     
    “数据结构”定义中的“关系”指数据间的逻辑关系,故也称数据结构为逻辑结构。
    存储结构
     
    数据结构在计算机中的表示称为物理结构。又称存储结构。
    顺序存储结构
    链式存储结构
    一、线性表的顺序表示
    用一组地址连续的存储单元依次存储线性表的数据元素。C语言中的数组即采用顺序存储方式。
    2000:0001
    2000:0003
    2000:0005
    2000:0007
    2000:0009
    2000:0011
    2000:0013
    2000:0015
    2000:0017
    ...
    2000:1001
    2000:1003
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    1
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    1
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    1
    1
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    1
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    1
    0
    1
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    1
    1
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    1
    1
    1
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    1
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    1
    0
    0
    1
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
    a[9]
    1
    2
    3
    4
    5
    6
    7
    8
    9
     
     
     
    假设线性表的每个元素需占用l个存储单元,并以所占的第一个单元的存储地址作为数据元素的存储位置。则存在如下关系:
    LOC(ai+1)=LOC(ai)+l
    LOC(ai)=LOC(a1)+(i-1)*l
    式中LOC(a1)是线性表的第一个数据元素的存储位置,通常称做线性表的起始位置基地址。常用b表示。
    线性表的这种机内表示称做线性表的顺序存储结构或顺序映象。
    称顺序存储结构的线性表为顺序表。顺序表的特点是以元素在计算机内物理位置相邻来表示线性表中数据元素之间的逻辑关系。
    二、顺序存储结构的线性表类C语言表示:
    线性表的动态分配顺序存储结构
    #define LIST_INIT_SIZE 100 
    #define LISTINCREMENT 10 

    typedef struct{
    ElemType *elem; //存储空间基址
    int length; //当前长度
    int listsize; //当前分配的存储容量以一数据元素存储长度为单位
    }SqList;
    三、顺序存储结构的线性表操作及C语言实现:
    顺序表的插入与删除操作:
    序号
    数据元素
    序号
    数据元素
     
    序号
    数据元素
    序号
    数据元素
    1
    2
    3
    4
    5
    6
    7
    8
    9
     
     
     
    12
    13
    21
    24
    28
    30
    42
    77
     
     
     
     
     
     

    <-
    25
     
    1
    2
    3
    4
    5
    6
    7
    8
    9
     
     
     
    12
    13
    21
    24
    25
    28
    30
    42
    77
     
     
     
     
    1
    2
    3
    4
    5
    6
    7
    8
    9
     
     
     
    12
    13
    21
    24
    28
    30
    42
    77
     
     
     
     
     
     
    ->24
    1
    2
    3
    4
    5
    6
    7
    8
    9
     
     
     
    12
    13
    21
    28
    30
    42
    77
     
     
     
     
     
    插入前n=8;插入后n=9;
     
    删除前n=8;删除后n=7;
     
    顺序表的插入算法
    status ListInsert(List *L,int i,ElemType e) {
    struct STU *p,*q;
    if (i<1||i>L->length+1) return ERROR;
    q=&(L->elem[i-1]);
    for(p=&L->elem[L->length-1];p>=q;--p)
    *(p+1)=*p;
    *q=e;
    ++L->length;
    return OK;
    }/*ListInsert Before i */
    顺序表的合并算法
    void MergeList(List *La,List *Lb,List *Lc) {
    ElemType *pa,*pb,*pc,*pa_last,*pb_last;
    pa=La->elem;pb=Lb->elem;
    Lc->listsize = Lc->length = La->length + Lb->length;
    pc = Lc->elem =
    (ElemType *)malloc(Lc->listsize * sizeof(ElemType));
    if(!Lc->elem) exit(OVERFLOW);
    pa_last = La->elem + La->length - 1;
    pb_last = Lb->elem + Lb->length - 1;
    while(pa<=pa_last && pb<=pb_last) {
    if(Less_EqualList(pa,pb)) *pc++=*pa++;
    else *pc++=*pb++;
    }
    while(pa<=pa_last) *pc++=*pa++;
    while(pb<=pb_last) *pc++=*pb++;
    }
    顺序表的查找算法
    int LocateElem(List *La,ElemType e,int type) {
    int i;
    switch (type) {
    case EQUAL:
    for(i=0;i<length;i++)
    if(EqualList(&La->elem[i],&e))
    return 1;
    break;
    default:
    break;
    }
    return 0;
    }
    顺序表的联合算法
    void UnionList(List *La, List *Lb) {
    int La_len,Lb_len; int i; ElemType e;
    La_len=ListLength(La); Lb_len=ListLength(Lb);
    for(i=0;i<Lb_len;i++) {
    GetElem(*Lb,i,&e);
    if(!LocateElem(La,e,EQUAL))
    ListInsert(La,++La_len,e);
    }
    }
    四、总结
     
    第七课
    本课主题: 实验一 线性表的顺序存储实验
    教学目的: 掌握顺序表的定义及操作的C语言实现方法
    教学重点: 顺序表的操作的C语言实现方法
    教学难点: 顺序表的操作的C语言实现方法
    实验内容:
    利用顺序表完成一个班级的一个学期的所有课程的管理:能够增加、删除、修改学生的成绩记录。
    实验要求:
    在上机前写出全部源程序。
    第八课
    本课主题: 线性表的链式表示与实现
    教学目的: 掌握线性链表、单链表、静态链表的概念、表示及实现方法
    教学重点: 线性链表之单链表的表示及实现方法。
    教学难点: 线性链表的概念。
    授课内容:
    一、复习顺序表的定义。
    二、线性链表的概念:
    以链式结构存储的线性表称之为线性链表。
    特点是该线性表中的数据元素可以用任意的存储单元来存储。线性表中逻辑相邻的两元素的存储空间可以是不连续的。为表示逻辑上的顺序关系,对表的每个数据元素除存储本身的信息之外,还需存储一个指示其直接衙继的信息。这两部分信息组成数据元素的存储映象,称为结点。
    2000:1000
    2000:1010
    2000:1020
    2000:1030
    2000:1040
    2000:1050
    2000:1060
    ...
    2000:4000
    头指针2000:1006
    2000:1030
    a3
    2000:1040
    a6
    NULL
    a1
    2000:1060
    a4
    2000:1050
    a5
    2000:1020
    a2
    2000:1010
    数据域
    指针域
     
     
     
     
     
    <-数据域+指针域
     
     
     
     
     
    例:下图是若干抽屉,每个抽屉中放一个数据元素和一个指向后继元素的指针,一号抽屉中放线性表的第一个元素,它的下一个即第二个元素的位置标为5,即放在第5个抽屉中,而第三个放在2号抽屉中。第三个元素即为最后一个,它的下一个元素的指针标为空,用0表示。
    用线性链表表示线性表时,数据元素之间的逻辑关系是由结点中的指针指示的
    二、线性链表的存储实现
    struct LNODE{
    ElemType data;
    struct LNODE *next;
    };
    typedef struct LNODE LNode;
    typedef struct LNODE * LinkList;
    头指针与头结点的区别:
    头指针只相当于结点的指针域,头结点即整个线性链表的第一个结点,它的数据域可以放数据元素,也可以放线性表的长度等附加信息,也可以不存储任何信息。
    三、线性表的操作实现(类C语言)
    1初始化操作
    Status Init_L(LinkList L){
    if (L=(LinkList *)malloc(sizeof(LNode)))
    {L->next=NULL;return 1;}
    else return 0;
    }
    2插入操作
    Status ListInsert_L(LinkList &L,int i,ElemType e){
    p=L,j=0;
    while(p&&j<i-1){p=p->next;++j;}
    if(!p||j>i-1) return ERROR;
    s=(LinkList)malloc(sizeof(LNode));
    s->data=e;s->next=p->next;
    p->next=s;
    return OK;
    }//ListInsert_L
    3删除操作
    Status ListDelete_L(LinkList &L,int i,ElemType &e){
    p=L,j=0;
    while(p&&j<i-1){p=p->next;++j;}
    if(!p->next||j>i-1) return ERROR;
    q=p->next;p->next=q->next;
    e=q->data;free(q);
    return OK;
    }//ListDelete_L
    4取某序号元素的操作
    Status GetElem_L(LinkList &L,int i,ElemType &e){
    p=L->next,j=1;
    while(p&&j<i){p=p->next;++j;}
    if(!p||j>i) return ERROR;
    e=p->data;
    return OK;
    }//GetElem_L
    5归并两个单链表的算法
    void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){
    //已知单链线性表La和Lb的元素按值非递减排列
    //归并后得到新的单链线性表Lc,元素也按值非递减排列
    pa=La->next;pb=Lb->next;
    Lc=pc=La;
    while(pa&&pb){
    if(pa->data<=pb->data){
    pc->next=pa;pc=pa;pa=pa->next;
    }else{pc->next=pb;pc=pb;pb=pb->next;}
    }
    pc->next=pa?pa:pb;
    free(Lb);
    }//MergeList_L
    四、总结
    1、线性链表的概念。
    2、线性链表的存储
    3、线性链表的操作
    第九课
    本课主题: 循环链表与双向链表
    教学目的: 掌握循环链表的概念,掌握双向链表的的表示与实现
    教学重点: 双向链表的表示与实现
    教学难点: 双向链表的存储表示
    授课内容:
    一、复习线性链表的存储结构
    二、循环链表的存储结构
    循环链表是加一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点。
    循环链表的操作和线性链表基本一致,差别仅在于算法中的循环条件不是p或p->next是否为空,而是它们是否等于头指针。
    三、双向链表的存储结构
    提问:单向链表的缺点是什么?
    提示:如何寻找结点的直接前趋。
    双向链表可以克服单链表的单向性的缺点。
    在双向链表的结点中有两个指针域,其一指向直接后继,另一指向直接前趋。
    1、线性表的双向链表存储结构
    typedef struct DulNode{
    struct DulNode *prior;
    ElemType data;
    struct DulNode *next;
    }DulNode,*DuLinkList;
    对指向双向链表任一结点的指针d,有下面的关系:
    d->next->priou=d->priou->next=d
    即:当前结点后继的前趋是自身,当前结点前趋的后继也是自身。
    2、双向链表的删除操作
    Status ListDelete_DuL(DuLinkList &L,int i,ElemType &e){
    if(!(p=GetElemP_DuL(L,i)))
    return ERROR;
    e=p->data;
    p->prior->next=p->next;
    p->next->prior=p->pror;
    free(p);
    return OK;
    }//ListDelete_DuL
    3、双向链表的插入操作
    Status ListInsert_DuL(DuLinkList &L,int i,ElemType &e){
    if(!(p=GetElemP_DuL(L,i)))
    return ERROR;
    if(!(s=(DuLinkList)malloc(sizeof(DuLNode)))) return ERROR;
    s->data=e;
    s->prior=p->prior;
    p->prior->next=s;
    s->next=p;
    p->prior=s;
    return OK;
    }//ListInsert_DuL
    四、一个完整的带头结点的线性边表类型定义:
    typedef struct LNode{
    ElemType data;
    struct LNode *next;
    }*Link,*Position;
     
    typedef struct{
    Link head,tail;
    int len;
    }LinkList;
     
    Status MakeNode(Link &p,ElemType e);
    //分配由p指向的值为e的结点,并返回OK;若分配失败,则返回ERROR
    void FreeNode(Link &p);
    //释放p所指结点
    Status InitLinst(LinkList &L);
    //构造一个空的线性链表L
    Status DestroyLinst(LinkList &L);
    //销毁线性链表L,L不再存在
    Status ClearList(LinkList &L);
    //将线性链表L重置为空表,并释放原链表的结点空间
    Status InsFirst(Link h,Link s);
    //已知h指向线性链表的头结点,将s所指结点插入在第一个结点之前
    Status DelFirst(Link h,Link &q);
    //已知h指向线性链表的头结点,删除链表中的第一个结点并以q返回
    Status Append(LinkList &L,Link s);
    //将指针s所指(彼此以指针相链)的一串结点链接在线性链表L的最后一个结点
    //之后,并改变链表L的尾指针指向新的尾结点
    Status Remove(LinkList &L,Link &q);
    //删除线性链表L中的尾结点并以q返回,改变链表L的尾指针指向新的尾结点
    Status InsBefore(LinkList &L,Link &p,Link s);
    //已知p指向线性链表L中的一个结点,将s所指结点插入在p所指结点之前,
    //并修改指针p指向新插入的结点
    Status InsAfter(LinkList &L,Link &p,Link s);
    //已知p指向线性链表L中的一个结点,将s所指结点插入在p所指结点之后,
    //并修改指针p指向新插入的结点
    Status SetCurElem(Link &p,ElemType e);
    //已知p指向线性链表中的一个结点,用e更新p所指结点中数据元素的值
    ElemType GetCurElem(Link p);
    //已知p指向线性链表中的一个结点,返回p所指结点中数据元素的值
    Status ListEmpty(LinkList L);
    //若线性链表L为空表,则返回TRUE,否则返回FALSE
    int ListLength(LinkList L);
    //返回线性链表L中的元素个数
    Position GetHead(LinkList L);
    //返回线性链表L中头结点的位置
    Position GetLast(LinkList L);
    //返回线性链表L中最后一个结点的位置
    Position PriorPos(LinkList L,Link p);
    //已知p指向线性链表L中的一个结点,返回p所指结点的直接前趋的值
    //若无前趋,返回NULL
    Position NextPos(LinkList L,Link p);
    //已知p指向线性链表L中的一个结点,返回p所指结点的直接后继的值
    //若无后继,返回NULL
    Status LocatePos(LinkList L,int i,Link &p);
    //返回p指示线性链表L中第i个结点的位置并返回OK,i值不合法时返回ERROR
    Position LocateElem(LinkList L,ElemType e,
    Status(*compare)(ElemType,ElemType));
    //返回线性链表L中第1个与e满足函数compare()判定关系的元素的位置,
    //若下存在这样的元素,则返回NULL
    Status ListTraverse(LinkList L,Status(*visit)());
    //依次对L的每个元素调用函数visit()。一旦visit()失败,则操作失败。
    五、总结本课内容
    循环链表的存储结构
    双向链表的存储结构
    第十课
    本课主题: 栈的表示与实现
    教学目的: 栈的数据类型定义、栈的顺序存储表示与实现
    教学重点: 栈的顺序存储表示与实现方法
    教学难点: 栈的定义
    授课内容:
    一、栈的定义
    是限定仅在表尾进行插入或删除操作的线性表。
    栈的表尾称为栈顶,表头称为栈底,不含元素的空表称为空栈
    栈的抽象数据类型定义:
    ADT Stack{
    数据对象:D={ai|ai(- ElemSet,i=1,2,...,n,n>=0}
    数据关系:R1={<ai-1,ai>|ai-1,ai(- D,i=2,...,n}
    基本操作:
    InitStack(&S) 构造一个空栈S
    DestroyStack(&S) 栈S存在则栈S被销毁
    ClearStack(&S) 栈S存在则清为空栈
    StackEmpty(S) 栈S存在则返回TRUE,否则FALSE
    StackLength(S) 栈S存在则返回S的元素个数,即栈的长度
    GetTop(S,&e) 栈S存在且非空则返回S的栈顶元素
    Push(&S,e) 栈S存在则插入元素e为新的栈顶元素
    Pop(&S,&e) 栈S存在且非空则删除S的栈顶元素并用e返回其值
    StackTraverse(S,visit())栈S存在且非空则从栈底到栈顶依次对S的每个数据元素调用函数visit()一旦visit()失败,则操作失败
    }ADT Stack
    二、栈的表示和实现
    栈的存储方式:
    1、顺序栈:利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针top指示栈顶元素在顺序栈中的位置
    2、链栈:利用链表实现
    顺序栈的类C语言定义:
    typedef struct{
    SElemType *base;
    SElemType *top; //设栈顶栈底两指针的目的是便于判断栈是否为空
    int StackSize; //栈的当前可使用的最大容量.
    }SqStack;
    顺序栈的的模块说明:
    struct STACK {
    SElemType *base;
    SElemType *top;
    int stacksize;
    };
    typedef struct STACK Sqstack;
    Status InitStack(SqStack &S);
    Status DestroyStack(SqStack &S);
    Status ClearStack(SqStack &S);
    Status StackEmpty(SqStack S);
    int StackLength(SqStack S);
    Status GetTop(SqStack S,SElemType &e);
    Status Push(SqStack &S,SElemType e);
    Status Pop(SqStack &S,SElemType &e);
    Status StackTraverse(SqStack S,Status (*visit)());
     
    Status InitStack(SqStack &S) {
    S.base=(SelemType *)malloc(STACK_INIT_SIZE *sizeof(ElemType));
    if(!S.base)exit(OVERFLOW);
    S.top=S.base;
    S.stacksize=STACK_INI_SIZE;
    return OK;
    }//IniStack
    Status DestroyStack(SqStack &S); {
    }//DestroyStack
    Status ClearStack(SqStack &S); {
    S.top=S.base;
    } //ClearStack
    Status StackEmpty(SqStack S); {
    if(S.top==S.base) return TRUE;
    else return FALSE;
    } //StackEmpty
    int StackLength(SqStack S); {
    int i; SElemType *p;
    i=0;
    p=S.top;
    while(p!=S.base) {p++; i++; }
    } //stackLength
    Status GetTop(SqStack S,SElemType &e); {
    if(S.top==S.base) return ERROR;
    e=*(S.top-1);
    return OK;
    } //GetTop
    Status Push(SqStack &S,SElemType e); {
    if(S.top - s.base>=S.stacksize) {
    S.base=(ElemType *) realloc(S.base,
    (S.stacksize + STACKINCREMENT) * sizeof(ElemType));
    if(!S.base)exit(OVERFLOW);
    S.top=S.base+S.stacksize;
    S.stacksize+=STACKINCREMENT;
    }
    *S.top++=e;
    return OK;
    } //Push
    Status Pop(SqStack &S,SElemType &e); {
    if(S.top==S.base)
    return ERROR;
    e=*--S.top;
    return OK;
    }//Pop
    Status StackTraverse(SqStack S,Status (*visit)()); {
    }//StackTraverse
    三、总结
    栈的定义
    栈的顺序存储实现
    第十一课
    本课主题: 栈的应用
    教学目的: 掌握栈的应用方法,理解栈的重要作用
    教学重点: 利用栈实现行编辑,利用栈实现表达式求值
    教学难点: 利用栈实现表达式求值
    授课内容:
    一、栈应用之一:数制转换
    将十进制数转换成其它进制的数有一种简单的方法:
    例:十进制转换成八进制:(66)10=(102)8
    66/8=8 余 2
    8/8=1 余 0
    1/8=0 余 1
    结果为余数的逆序:102 。先求得的余数在写出结果时最后写出,最后求出的余数最先写出,符合栈的先入后出性质,故可用栈来实现数制转换:
    void conversion() {
    pSqStack S;
    SElemType e;
    int n;
    InitStack(&S);
    printf("Input a number to convert to OCT:/n");
    scanf("%d",&n);
    if(n<0)
    { printf("/nThe number must be over 0.");
    return;}
    if(!n) Push(S,0);
    while(n){
    Push(S,n%8);
    n=n/8; }
    printf("the result is: ");
    while(!StackEmpty(*S)){
    Pop(S,&e); printf("%d",e);}
    }
    二、栈应用之二:行编辑
    一个简单的行编辑程序的功能是:接受用户从终端输入的程序或数据,并存入用户的数据区。允许用户输入出错时可以及时更正。可以约定#为退格符,以表示前一个字符无效,@为退行符,表示当前行所有字符均无效。
    例:在终端上用户输入为
    whli##ilr#e(s#*s) 应为
    while(*s)
    void LineEdit() {
    pSqStack S,T; char str[1000];
    int strlen=0; char e; char ch;
    InitStack(&S);
    InitStack(&T);
    ch=getchar();
    while(ch!=EOFILE) {
    while(ch!=EOFILE&&ch!='/n') {
    switch(ch){
    case '#': Pop(S,&ch); break;
    case '@': ClearStack(S); break;
    default: Push(S,ch); break; }
    ch=getchar();
    }
    if(ch=='/n') Push(S,ch);
    while(!StackEmpty(*S)) { Pop(S,&e); Push(T,e); }
    while(!StackEmpty(*T)) { Pop(T,&e); str[strlen++]=e; }
    if(ch!=EOFILE) ch=getchar();
    }
    str[strlen]='/0';
    printf("/n%s",str);
    DestroyStack(S);
    DestroyStack(T);
    }
     
    三、栈应用之三:表达式求值
    一个程序设计语言应该允许设计者根据需要用表达式描述计算过程,编译器则应该能分析表达式并计算出结果。表达式的要素是运算符、操作数、界定符、算符优先级关系。例:1+2*3有+,*两个运算符,*的优先级高,1,2,3是操作数。 界定符有括号和表达式结束符等。
    算法基本思想:
    1首先置操作数栈为空栈,表达式起始符#为运算符栈的栈底元素;
    2依次讲稿表达式中每个字符,若是操作数则进OPND栈,若是运算符,则和OPTR栈的栈顶运算符比较优先权后作相应操作,直至整个表达式求值完毕。
    char EvaluateExpression() {
    SqStack *OPND,*OPTR;
    char c,x,theta; char a,b;
    InitStack(&OPTR); Push(OPTR,'#');
    InitStack(&OPND);
    c=getchar();
    while(c!='#'||GetTop(*OPTR)!='#') {
    if(!In(c,OP)) {Push(OPND,c);c=getchar();}
    else
    switch(Precede(GetTop(*OPTR),c)) {
    case '<': Push(OPTR,c); c=getchar(); break;
    case '=': Pop(OPTR,&x); c=getchar(); break;
    case '>': Pop(OPTR,&theta);
    Pop(OPND,&b); Pop(OPND,&a);
    Push(OPND,Operate(a,theta,b));
    break;
    }
    }
    c=GetTop(*OPND);
    DestroyStack(OPTR);
    DestroyStack(OPND);
    return c;
    }
    四、总结
    栈的先进后出、后进先出的特性。
    第十二课
    本课主题: 实验二 循环链表实验
    教学目的: 掌握单向链表的实现方法
    教学重点: 单向链表的存储表示及操作
    教学难点: 单向链表的操作实现
    授课内容:
    一、单向链表的存储表示
    二、单向链表的基本操作
    第十三课
    本课主题: 队列
    教学目的: 掌握队列的类型定义,掌握链队列的表示与实现方法
    教学重点: 链队列的表示与实现
    教学难点: 链队列的表示与实现
    授课内容:
    一、队列的定义:
    队列是一种先进先出的线性表。它只允许在表的一端进行插入,而在另一端删除元素。象日常生活中的排队,最早入队的最早离开。
    在队列中,允许插入的的一端叫队尾,允许删除的一端则称为队头
    抽象数据类型队列:
    ADT Queue{
    数据对象: D={ai| ai(-ElemSet,i=1,2,...,n,n>=0}
    数据关系: R1={<ai-1,ai> | ai-1,ai(- D,i=2,...,n}
    基本操作:
    InitQueue(&Q) 构造一个空队列Q
    Destroyqueue(&Q) 队列Q存在则销毁Q
    ClearQueue(&Q) 队列Q存在则将Q清为空队列
    QueueEmpty(Q) 队列Q存在,若Q为空队列则返回TRUE,否则返回FALSE
    QueueLenght(Q) 队列Q存在,返回Q的元素个数,即队列的长度
    GetHead(Q,&e) Q为非空队列,用e返回Q的队头元素
    EnQueue(&Q,e) 队列Q存在,插入元素e为Q的队尾元素
    DeQueue(&Q,&e) Q为非空队列,删除Q的队头元素,并用e返回其值
    QueueTraverse(Q,vivsit()) Q存在且非空,从队头到队尾,依次对Q的每个数据元素调用函数visit()。一旦visit()失败,则操作失败
    }ADT Queue
    二、链队列-队列的链式表示和实现
    用链表表示的队列简称为链队列。一个链队列显然需要两个分别指示队头和队尾的指针。
     
     
     
     
    Q.front ->
     
    |
     
     
     
    /|/
     
     
    1
    |
    队头
     
     
    /|/
     
     
    2
    |
     
     
     
    /|/
     
     
    3
    |
     
     
     
    /|/
    /|/
     
    Q.rear ->
    9
    //
    队尾
     
     
     
     
    Q.front ->
     
    |
     
     
     
    /|/
     
     
    1
    |
    队头
     
     
    /|/
     
     
    2
    |
     
     
     
    /|/
     
     
    3
    |
     
     
     
    /|/
    /|/
     
    Q.rear ->
    9
    //
    队尾
     
    链队列表示和实现:
    //存储表示
    typedef struct QNode{
    QElemType data;
    struct QNode *next;
    }QNode,*QueuePtr;
    typedef struct{
    QueuePtr front;
    QueuePtr rear;
    }LinkQueue;
    //操作说明
    Status InitQueue(LinkQueue &Q)
    //构造一个空队列Q
    Status Destroyqueue(LinkQueue &Q)
    //队列Q存在则销毁Q
    Status ClearQueue(LinkQueue &Q)
    //队列Q存在则将Q清为空队列
    Status QueueEmpty(LinkQueue Q)
    // 队列Q存在,若Q为空队列则返回TRUE,否则返回FALSE
    Status QueueLenght(LinkQueue Q)
    // 队列Q存在,返回Q的元素个数,即队列的长度
    Status GetHead(LinkQueue Q,QElemType &e)
    //Q为非空队列,用e返回Q的队头元素
    Status EnQueue(LinkQueue &Q,QElemType e)
    //队列Q存在,插入元素e为Q的队尾元素
    Status DeQueue(LinkQueue &Q,QElemType &e)
    //Q为非空队列,删除Q的队头元素,并用e返回其值
    Status QueueTraverse(LinkQueue Q,QElemType vivsit())
    //Q存在且非空,从队头到队尾,依次对Q的每个数据元素调用函数visit()。一旦visit()失败,则操作失败
    //操作的实现
    Status InitQueue(LinkQueue &Q) {
    //构造一个空队列Q
    Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
    if(!Q.front)exit(OVERFLOW);
    Q.front->next=NULL;
    return OK;}
    Status Destroyqueue(LinkQueue &Q) {
    //队列Q存在则销毁Q
    while(Q.front){
    Q.rear=Q.front->next;
    free(Q.front);
    Q.front=Q.rear;
    }
    return OK;}
    Status EnQueue(LinkQueue &Q,QElemType e) {
    //队列Q存在,插入元素e为Q的队尾元素
    p=(QueuePtr)malloc(sizeof(QNode));
    if(!p) exit(OVERFLOW);
    p->data=e;p->next=NULL;
    Q.rear->next=p;
    Q.rear=p;
    return OK;}
    Status DeQueue(LinkQueue &Q,QElemType &e) {
    //Q为非空队列,删除Q的队头元素,并用e返回其值
    if(Q.front==Q.rear)return ERROR;
    p=Q.front->next;
    e=p->data;
    Q.front->next=p->next;
    if(Q.rear==p)Q.rear=Q.front;
    free(p);
    return OK;}
    三、总结
    链队列的存储表示
    链队列的操作及实现
    第十四课
    本课主题: 串的定义
    教学目的: 掌握串的定义及作用
    教学重点: 串的类型定义
    教学难点: 串的类型定义
    授课内容:
    一、串定义
    (或字符串),是由零个或多个字符组成的有限序列。一般记为:
    s='a1a2...an'(n>=0)
    其中s是串的名,用单引号括起来的字符序列是串的值;串中字符的数目n称为串的长度。零个字符的串称为空串,它的长度为零。
    串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。通常称字符在序列中的称为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。
    例:a='BEI',b='JING',c='BEIJING',d='BEI JING'
    串长分别为3,4,7,8,且a,b都是c,d的子串。
    称两个串是相等的,当且仅当这两个串的值相等。
    二、串的抽象数据类型的定义:
    ADT String{
    数据对象:D={ai|ai(-CharacterSet,i=1,2,...,n,n>=0}
    数据关系:R1={<ai-1,ai>|ai-1,ai(-D,i=2,...,n}
    基本操作:
    StrAssign(&T,chars)
    chars是字符常量。生成一个其值等于chars的串T。
    StrCopy(&T,S)
    串S存在则由串S复制得串T
    StrEmpty(S)
    串S存在则若S为空串,返回真否则返回假
    StrCompare(S,T)
    串S和T存在,若S>T,则返回值大于0,若S=T,则返回值=0,若S<T,则返回值<0
    StrLength(S)
    串S存在返回S的元素个数称为串的长度.
    ClearString(&S)
    串S存在将S清为空串
    Concat(&T,S1,S2)
    串S1和S2存在用T返回由S1和S2联接而成的新串
    SubString(&Sub,S,pos,len)
    串S存在,1<=pos<=StrLength(S)且0<=len<=StrLength(S)-pos+1
    Index(S,T,pos)
    串S和T存在,T是非空,1<=pos<=StrLength(S),若主串S中存在和串T值相同的子串,则返回它在主串S中第pos个字符之后第一次出现的位置,否则函数值为0
    Replace(&S,T,V)
    串S,T和V存在,T是非空串,用V替换主串S中出现的所有与T相等的不重叠的子串
    StrInsert(&S,pos,T)
    串S和T存在,1<=pos<=StrLength(S)+1,在串S的第pos个字符之前插入串T
    StrDelete(&S,pos,len)
    串S存在,1<=pos<=StrLength(S)-len+1从串中删除第pos个字符起长度为len的子串
    DestroyString(&S)
    串S存在,则串S被销毁
    }ADT String
    三、串操作应用举例:
    1文字处理中常用的:串的查找(比较,定位)与替换
    在TC集成环境中可用^QF快速查找变量 在WORD中可用搜索与替换批量改变文本
    2串的截断与连接
    可用求子串及串连接的方法进行文字处理
    四、总结
    找出几个自己亲自做过的串操作例子。
     
    第十五课
    本课主题: 串的表示和实现
    教学目的: 掌握串的几种实现方法
    教学重点: 定长顺序存储表示法堆分配存储表示法
    教学难点: 堆分配存储表示法
    授课内容:
    一、复习串的定义
    二、定长顺序存储表示
    类似于线性表的顺序存储结构,用一组地址连续的存储单元存储串值的字符序列.
    #define MAXSTRLEN 255
    typedef unsigned char SString[MAXSTRLEN+1] //0号单元存放串长
    串的实际长度可在这予定义长度的范围内随意,超过予定义长度的串值则被舍去
    串长可用下标为0的数组元素存储,也可在串值后设特殊标记
    a[0]
    a[1]
    a[2]
    a[3]
    a[4]
    a[5]
    ...
    a[n]
     
    3
    a
    b
    c
     
     
     
    pascal
     
    a
    b
    c
    /0
     
     
     
    c
    1串联接的实现Concat(&T,S1,S2)
    假设S1,S2和T都是SString型的串变量,且串T是由串S1联结串S2得到的,即串T的值的前一段和串S1的值相等,串T的值的后一段和串S2的值相等,则只要进行相应的"串值复制"操作即可,对超长部分实施"截断"操作
    以下是串联接可能出现的三种情况:
    S1
    S2
    T
    4
    2
    6
    a
    d
    a
    b
    e
    b
    c
     
    c
    d
     
    d
     
     
    e
     
     
    f
     
     
     
     
     
     
    S1,S2串长和小于最大值
    S1
    S2
    T
    6
    6
    8
    a
    g
    a
    b
    h
    b
    c
    i
    c
    d
    j
    d
    e
    k
    e
    f
    l
    f
     
     
    g
     
     
    h
    S1,S2串长和超过最大串长
    S1
    S2
    T
    8
    2
    8
    a
    i
    a
    b
    j
    b
    c
     
    c
    d
     
    d
    e
     
    e
    f
     
    f
    g
     
    g
    h
     
    h
    S1串长已等于最大串长
    算法描述如下:
    Status Concat(SString &T,SString S1,SString S2){
    if(S1[0]+S2[0]<=MAXSTRLEN){
    T[1..S1[0]]=S1[1..S1[0]];
    T[S1[0]+1..S1[0]+S2[0]]=S2[1..S2[0]];
    T[0]=S1[0]+S2[0]uncut=TRUE;
    }
    else if(S1[0]<MAXSTRSIZE){
    T[1..S1[0]]=S1[1..S1[0]];
    T[S1[0]+1..MAXSTRLEN]=S2[1..MAXSTRLEN-S1[0]];
    T[0]=MAXSTRLEN;uncut=FALSE;
    }
    else{
    T[0..MAXSTRLEN]=S1[0..MAXSTRLEN];
    uncut=FALSE;
    }
    return uncut;
    }
    三、堆分配存储表示
    这种存储表示的特点是,仍以一组地址连续的存储单元存放串值字符序列,但它们的存储空间是在程序执行过程中动态分配而得
    在C语言中,存在一个称之为堆的自由存储区,并由C语言的动态分配函数malloc()和free()来管理.利用函数malloc()为每个新产生的串分配一块实际串长所需存储空间,为处理方便,约定串长也作为存储结构的一部分
    typedef struct{
    char *ch;//若是非空串,则按串长分配存储区,否则ch为NULL
    int length; //串长度
    }HString
    Status StrInsert(HString &S,int pos,HString T){
    if(pox<1||pos>S.length+1) return ERROR;
    if(T.length){
    if(!(S.ch=(char *)realloc(S.ch,(S.length+T.length)*sizeof(char))))
    exit(OVERFLOW);
    for(i=S.length-1;i>=pos-1;--i)
    S.ch[i+T.length]=S.ch[i];
    S.ch[pos-1..pos+T.lenght-2]=T.ch[0..T.length-1];
    S.length+=T.length;
    }
    return OK;
    }
    四、总结
    思考两种存储表示方法的优缺点
    第十六课
    本课主题: 串操作应用举例
    教学目的: 掌握文本编辑的基本原理及方法
    教学重点: 简单文本编辑
    教学难点: 串的存储管理
    授课内容:
    一、复习串的堆分配存储表示
    二、文本编辑基本原理
    图一
    文本编辑可以用于源程序的输入和修改(如图一),也可用于报刊和书籍的编辑排版以及办公室的公文书信的起草和润色(如图二)。
    图二
    可用于文本编辑的程序很多,功能强弱差别很大,但基本操作是一致的:都包括串的查找插入删除等基本操作。
    对用户来讲,一个文本(文件)可以包括若干页,每页包括若干行,每行包括若干文字。
    对文本编辑程序来讲,可把整个文本看成一个长字符串,称文本串,页是文本串的子串,行又是页的子串。为简化程序复杂程度,可简单地把文本分成若干行。
    例:下面的一段源程序可以看成一个文本串,
    main(){
    float a,b,max;
    scanf("%f,%f",&a,&b);
    if (a>b) max=a;
    else max=b;
    };
    这个文本串在内存中的存储映像可为:
    m
    a
    i
    n
    (
    )
    {
    /n
     
     
    f
    l
    o
    a
    t
     
    a
    ,
    b
    ,
    m
    a
    x
    ;
    /n
     
     
    s
    c
    a
    n
    f
    (
    "
    %
    f
    ,
    %
    f
    "
    ,
    &
    a
    ,
    &
    b
    )
    ;
    /n
     
     
    i
    f
     
    a
    >
    b
     
     
    m
    a
    x
    =
    a
    ;
    /n
     
     
    e
    l
    s
    e
     
     
    m
    a
    x
    =
    b
    ;
    /n
    }
    /n
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
    在编辑时,为指示当前编辑位置,程序中要设立页指针、行指针、字符指针,分别指示当前页,当前行,当前字符。因此程序中要设立页表、行表便于查找。
    三、简单行编辑程序例
     
    第十七课
    本课主题: 实验三:栈的表示与实现及栈的应用
    教学目的: 掌握栈的存储表示方式和栈基本操作的实现方法
    教学重点: 栈的基本操作实现方法,栈的应用
    教学难点: 栈的存储表示
    实验内容:
    一、栈的实现
    实现栈的顺序存储。
    二、栈的应用
    1、利用栈实现数制转换 2、利用栈实现单行编辑
    以上任选一题。
    这里是实现栈的头文件
    第十八课
    本课主题: 数组的顺序表示与实现
    教学目的: 掌握数组的定义,数组的顺序表示方法
    教学重点: 数组的定义,数组的顺序表示方法
    教学难点: 数组的顺序表示方法
    授课内容:
    一、数组的定义
    几乎所有的程序设计语言都把数组类型设定为固有类型。
    以抽象数据类型的形式讨论数组的定义和实现,可以让我们加深对数组类型的理解。
    数组的定义:
    ADT Array{
    数据对象:ji=0,...,bi-1,i=1,2,...,n;
    D={aj1j2...jn|n(>0)称为数组的维数,bi是数组第i维的长度,ji是数组元素的第i维下标,aj1j2...jn (-ElemSet}
    数据关系:R={R1,R2,...Rn|
    Ri={<aj1...ji...jn,aj1...ji+1 ...jn>|
    0<=jk<=bk-1,1<=k<=n且k<>i,
    0<=ji<=bi-2,aj1...ji...jn,
    aj1...ji+1 ...jn(-D,i=2,...n}
    基本操作:
    InitArray(&A,n,bound1,...,boundn)
    若维数和各维长度合法,则构造相应的数组A,并返回OK.
    DestroyArray(&A)
    操作结果:销毁数组A.
    Value(A,&e,index1,...,indexn)
    初始条件:A是n维数组,e为元素变量,随后是n个下标值.
    操作结果:若各下标不超界,则e赋值为所指定的A的元素值,并返回OK.
    Assign(&A,e,index1,...,indexn)
    初始条件:A是n维数组,e为元素变量,随后是n个下标值.
    操作结果:若下标不超界,则将e的值赋给 所指定的A的元素,并返回OK.
    }ADT Array
    列向量的一维数组:
    a00
    a01
    a02
    ...
    a0,n-1
    a10
    a11
    a12
    ...
    a1,n-1
    ...
    ...
    ...
    ...
    ...
    am-1,0
    am-1,1
    am-1,2
    ...
    am-1,n-1
    行向量的一维数组:
    把二维数组中的每一行看成是一个数据元素,这些数据元素组成了一个一维数组A.
    A0
    a00
    a01
    a02
    ...
    a0,n-1
    a10
    a11
    a12
    ...
    a1,n-1
    ...
    ...
    ...
    ...
    ...
    am-1,0
    am-1,1
    am-1,2
    ...
    am-1,n-1
    A1
    ...
    Am
     
    二、数组的顺序表示和实现
    以行序为主序的存储方式:
    a00
    a01
    a02
    ...
    a0,n-1
    a10
    a11
    a12
    ...
    a1,n-1
    ...
    am-1,0
    am-1,1
    am-1,2
    ...
    am-1,n-1
    数组的顺序存储表示和实现:
    #include<stdarg.h>
    #define MAX_ARRAY_DIM 8
    typedef struct {
    ElemType *base;
    int dim;
    int *bounds;
    int *constants;
    }Array;
    Status InitArray(Array &A,int dim,...);
    Status DestroyArray(Array &A);
    Status Value(Array A,ElemType &e,...);
    Status Assign(Array &A,ElemType e,...);
    基本操作的算法描述:
    Status InitArray(Array &A,int dim,...){
    if(dim<1||dim>MAX_ARRAY_DIM) return ERROR;
    A.dim=dim;
    A.bounds=(int *)malloc(dim *sizeof(int));
    if(!A.bounds) exit(OVERFLOW);
    elemtotal=1;
    va_start(ap,dim);
    for(i=1;i<dim;++i){
    A.bounds[i]=va_arg(ap,int);
    if(A.bounds[i]<0) return UNDERFLOW;
    elemtotal*=A.bounds[i];
    }
    va_end(ap);
    A.base=(ElemType *)malloc(elemtotal*sizeof(ElemType));
    if(!A.base) exit(OVERFLOW);
    A.constants=(int *)malloc(dim*sizeof(int));
    if(!A.constants) exit(OVERFLOW);
    A.constants[dim-1]=1;
    for(i=dim-2;i>=0;--i)
    A.constants[i]=A.bounds[i+1]*A.constants[i+1];
    return OK;
    }
    Status DestoyArray(Array &A){
    if(!A.base) return ERROR;
    free(A.base); A.base=NULL;
    if !(A.bounds) return ERROR;
    free(A.bounds); A.bounds=NULL;
    if!(A.constatns) return ERROR;
    free(A.constants); A.constants=NULL;
    return OK;
    }
    Status Locate(Array A,va_list ap,int &off){
    off=0;
    for(i=0;i<A.dim;++i){
    ind=va_arg(ap,int);
    if(ind<0||ind>=A.bounds[i]) return OVERFLOW;
    off+=A.constants[i]*ind;
    }
    return OK;
    }
    Status Value(Array A,ElemType &e,...){
    va_start(ap,e);
    if((result=Locate(A,ap,off))<=0 return result;
    e=*(A.base+off);
    return OK;
    }
    Status Assign(Array &A,ElemType e,...){
    va_start(ap,e);
    if((result=Locate(A,ap,off))<=0) return result;
    *(A.base+off)=e;
    return OK;
    }
    三、小结
    数组的存储方式。
    数组的基本操作种类。
    第十九课
    本课主题: 实验四 串的实现实验
    教学目的: 掌握PASCAL串类型的实现方法
    教学重点: 串的操作
    教学难点: 串的联接操作
    授课内容:
    一、PASCAL串类型的存储表示:
    #define MAXSTRLEN 255
    typedef char SString[MAXSTRLEN+1];
    二、串的操作:
    1、串的联接
    mystrcat(SString s1,SString s2,SString t);
    2、求子串
    mysubstr(SString t,int pos,int len,SString sub);
    3、子串定位
    mystrindex(SString t,SString sub,int *index);
    第二十课
    本课主题: 广义表
    教学目的: 广义表的定义及存储结构
    教学重点: 广义表的操作及意义
    教学难点: 广义表存储结构
    授课内容:
    一、广义表的定义
    广义表是线性表的推广,其表中的元素可以是另一个广义表,或其自身.
    广义表的定义:
    ADT GList{
    数据对象:D={i=1,2,...,n>=0;ei(-AtomSet或ei(-GList,
    AtomSet为某个数据对象}
    数据关系:R1={<ei-1,ei>|ei-1,ei(-D,2=<i<=n}
    基本操作:
    InitGlist(&L);
    操作结果:创建空的广义表L
    CreateGList(&L,S);
    初始条件:S是广义表的书写形式串
    操作结果:由S创建广义表L
    DestroyGlist(&L);
    初始条件:广义表L存在
    操作结果:销毁广义表L
    CopyGlist(&T,L);
    初始条件:广义表L存在
    操作结果:由广义表L复制得到广义表T
    GListLength(L);
    初始条件:广义表L存在
    操作结果:求广义表L的长度,即元素个数
    GListDepth(L);
    初始条件:广义表L存在
    操作结果:求广义表L的深度
    GlistEmpty(L);
    初始条件:广义表L存在
    操作结果:判断广义表L是否为空
    GetHead(L);
    初始条件:广义表L存在
    操作结果:取广义表L的头
    GetTail(L);
    初始条件:广义表L存在
    操作结果:取广义表L的尾
    InsertFirst_GL(&L,e);
    初始条件:广义表L存在
    操作结果:插入元素e作为广义表L的第一元素
    DeleteFirst_GL(&L,&e);
    初始条件:广义表L存在
    操作结果:删除广义表L的第一元素,并用e返回其值
    Traverse_GL(L,Visit());
    初始条件:广义表L存在
    操作结果:遍历广义表L,用函数Visit处理每个元素
    }ADT GList
    广义表一般记作:LS=(a1,a2,...,an)
    其中LS是广义表的名称,n是它的长度,ai可以是单个元素也可是广义表,分别称为原子子表,当广义表非空时,称第一个元素a1为LS的表头称其余元素组成的广义表为表尾.
    二、广义表的存储结构
    广义表的头尾链表存储表示
    typedef emnu{ATOM,LIST} ElemTag;
    typedef struct GLNode{
    ElemTag tag;
    union{
    AtomType atom;
    struct{struct GLNode *hp,*tp;}ptr;
    }
    }
    有A、B、C、D、E五个广义表的描述如下:
    A=() A是一个空表,它的长度为零
    B=(e) 列表B只有一个原子e,B的长度为1.
    C=(a,(b,c,d)) 列表C的长度为2,两个元素分别为原子a和子表(b,c,d)
    D=(A,B,C) 列表D的长度为3,三个元素都是列表,显然,将子表的值代入后,则有D=((),(e),(a,(b,c,d)))
    E=(a,E) 这是一个递归的表,它的长度为2,E相当于一个无限的列表E=(a,(a,(a,...)))
    上述五个广义表用以上的存储结构的存储映像如下:
     
    第二十一课
    本课主题: 树、二叉树定义及术语
    教学目的: 掌握树、二叉树的基本概念和术语,二叉树的性质
    教学重点: 二叉树的定义、二叉树的性质
    教学难点: 二叉树的性质
    授课内容:
    一、树的定义:
    树是n(n>=0)个结点的有限集。在任意一棵非空树中:
    (1)有且仅有一个特定的称为根的结点;
    (2)当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,...Tm,其中每一个集合本身又是一棵树,并且称为根的子树.
    二、树的基本概念:
    树的结点包含一个数据元素及若干指向其子树的分支。
    结点拥有的子树数称为结点的
    度为0的结点称为叶子终端结点
    度不为0的结点称为非终端结点分支结点
    树的度是树内各结点的度的最大值。
    结点的子树的根称为该结点的孩子,相应地,该结点称为孩子的双亲
    同一个双亲的孩子之间互称兄弟
    结点的祖先是从根到该结点所经分支上的所有结点。
    以某结点为根的子树中的任一结点都称为该结点的子孙
    结点的层次从根开始定义起,根为第一层,根的孩子为第二层。其双亲在同一层的结点互为堂兄弟。树中结点的最大层次称为树的深度,或高度。
    如果将树中结点的各子树看成从左至右是有次序的,则称该树为有序树,否则称为无序树。
    森林是m(m>=0)棵互不相交的树的集合。
     
    三、二叉树的定义
    二叉树是另一种树型结构,它的特点是每个结点至多只有二棵子树(即二叉树中不存在度大于2的结点),并且,二叉树的子树有左右之分,其次序不能任意颠倒。
    一棵深度为k且有2(k)-1个结点的二叉树称为满二叉树,如图(a),按图示给每个结点编号,如果有深度为k的,有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时,称之为完全二叉树
    二叉树的定义如下:
    ADT BinaryTree{
    数据对象D:D是具有相同特性的数据元素的集合。
    数据关系R:
    基本操作P:
    InitBiTree(&T);
    DestroyBiTree(&T);
    CreateBiTree(&T,definition);
    ClearBiTree(&T);
    BiTreeEmpty(T);
    BiTreeDepth(T);
    Root(T);
    Value(T,e);
    Assign(T,&e,value);
    Parent(T,e);
    LeftChild(T,e);
    RightChild(T,e);
    LeftSibling(T,e);
    RightSibling(T,e);
    InsertChild(T,p,LR,c);
    DeleteChild(T,p,LR);
    PreOrderTraverse(T,visit());
    InOrderTraverse(T,visit());
    PostOrderTraverse(T,visit());
    LevelOrderTraverse(T,Visit());
    }ADT BinaryTree
    三、二叉树的性质
    性质1:
    在二叉树的第i层上至多有2的i-1次方个结点(i>=1)。
     
    性质2:
    深度为k的二叉树至多有2的k次方减1个结点(k>=1)。
     
    性质3:
    对任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1。
     
    性质4:
    具有n个结点的完全二叉树的深度为|log2n|+1
     
    性质5:
    如果对一棵有n个结点的完全二叉树的结点按层序编号,则对任一结点i(1=<i=<n)有:
    (1)如果i=1,则结点i是二叉树的根,无双亲;如果i>1,则双亲PARENT(i)是结点i/2
    (2)如果2i>n,则结点i无左孩子(结点i为叶子结点);否则其左孩子LCHILD(i)是结点2i
    (3)如果2i+1>n,则结点i无右孩子;否则其右孩子RCHILD(i)是结点2i+1
     
    四、总结
    第二十二课
    本课主题: 实验五 数组实验
    教学目的: 掌握二维数组的实现方法
    教学重点: 二维数组的存储表示,二维数组的基本操作
    教学难点: 二维数组的基本操作
    授课内容:
    数组的顺序存储表示和实现:
    #include<stdarg.h>
    #define MAX_ARRAY_DIM 8
    typedef struct {
    ElemType *base;
    int dim;
    int *bounds;
    int *constants;
    }Array;
    Status InitArray(Array &A,int dim,...);
    Status DestroyArray(Array &A);
    Status Value(Array A,ElemType &e,...);
    Status Assign(Array &A,ElemType e,...);
    基本操作的算法描述:
    Status InitArray(Array &A,int dim,...){
    if(dim<1||dim>MAX_ARRAY_DIM) return ERROR;
    A.dim=dim;
    A.bounds=(int *)malloc(dim *sizeof(int));
    if(!A.bounds) exit(OVERFLOW);
    elemtotal=1;
    va_start(ap,dim);
    for(i=1;i<dim;++i){
    A.bounds[i]=va_arg(ap,int);
    if(A.bounds[i]<0) return UNDERFLOW;
    elemtotal*=A.bounds[i];
    }
    va_end(ap);
    A.base=(ElemType *)malloc(elemtotal*sizeof(ElemType));
    if(!A.base) exit(OVERFLOW);
    A.constants=(int *)malloc(dim*sizeof(int));
    if(!A.constants) exit(OVERFLOW);
    A.constants[dim-1]=1;
    for(i=dim-2;i>=0;--i)
    A.constants[i]=A.bounds[i+1]*A.constants[i+1];
    return OK;
    }
    Status DestoyArray(Array &A){
    if(!A.base) return ERROR;
    free(A.base); A.base=NULL;
    if !(A.bounds) return ERROR;
    free(A.bounds); A.bounds=NULL;
    if!(A.constatns) return ERROR;
    free(A.constants); A.constants=NULL;
    return OK;
    }
    Status Locate(Array A,va_list ap,int &off){
    off=0;
    for(i=0;i<A.dim;++i){
    ind=va_arg(ap,int);
    if(ind<0||ind>=A.bounds[i]) return OVERFLOW;
    off+=A.constants[i]*ind;
    }
    return OK;
    }
    Status Value(Array A,ElemType &e,...){
    va_start(ap,e);
    if((result=Locate(A,ap,off))<=0 return result;
    e=*(A.base+off);
    return OK;
    }
    Status Assign(Array &A,ElemType e,...){
    va_start(ap,e);
    if((result=Locate(A,ap,off))<=0) return result;
    *(A.base+off)=e;
    return OK;
    }
    第二十三课
    本课主题: 二叉树的存储结构
    教学目的: 掌握二叉树的两种存储结构
    教学重点: 链式存储结构
    教学难点: 链式存储二叉树的基本操作
    授课内容:
    一、复习二叉树的定义
    二叉树的基本特征:每个结点的度不大于2。
    二、顺序存储结构
    #define MAX_TREE_SIZE 100
    typedef TElemType SqBiTree[MAX_TREE_SIZE];
    SqBiTree bt;
    结点编号
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    结点值
    1
    2
    3
    4
    5
    0
    0
    0
    0
    6
    7
    0
    0
    0
    0
    第i号结点的左右孩子一定保存在第2i及2i+1号单元中。
    缺点:对非完全二叉树而言,浪费存储空间
    三、链式存储结构
    一个二叉树的结点至少保存三种信息:数据元素、左孩子位置、右孩子位置
    对应地,链式存储二叉树的结点至少包含三个域:数据域、左、右指针域。
    也可以在结点中加上指向父结点的指针域P。
    对结点有二个指针域的存储方式有以下表示方法:
    typedef struct BiTNode{
    TElemType data;
    struct BitNode *lchild,*rchild;
    }BiTNode,*BiTree;
    基于该存储结构的二叉树基本操作有:
    Status CreteBiTree(BiTree &T);
    //按先序次序输入二叉树中结点的值(一个字符),空格字符表示空树,
    //构造二叉链表表示的二叉树T。
    Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e));
    //采用二叉链表存储结构,Visit是对结点操作的应用函数
    //先序遍历二叉树T,对每个结点调用函数Visit一次且仅一次
    //一旦visit()失败,则操作失败
    Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e));
    //采用二叉链表存储结构,Visit是对结点操作的应用函数
    //中序遍历二叉树T,对每个结点调用函数Visit一次且仅一次
    //一旦visit()失败,则操作失败
    Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType e));
    //采用二叉链表存储结构,Visit是对结点操作的应用函数
    //后序遍历二叉树T,对每个结点调用函数Visit一次且仅一次
    //一旦visit()失败,则操作失败
    Status LevelOrderTraverse(BiTree T,Status(*Visit)(TElemType e));
    //采用二叉链表存储结构,Visit是对结点操作的应用函数
    //层序遍历二叉树T,对每个结点调用函数Visit一次且仅一次
    //一旦visit()失败,则操作失败
    四、总结本课内容
    顺序存储与链式存储的优缺点。
    第二十四课
    本课主题: 遍历二叉树
    教学目的: 掌握二叉树遍历的三种方法
    教学重点: 二叉树的遍历算法
    教学难点: 中序与后序遍历的非递归算法
    授课内容:
    一、复习二叉树的定义
    二叉树由三个基本单元组成:根结点、左子树、右子树
    问题:如何不重复地访问二叉树中每一个结点?
    二、遍历二叉树的三种方法:
    先序
    1
    访问根结点
    2
    先序访问左子树
    3
    先序访问右子树
    中序
    1
    中序访问左子树
    2
    中序访问根结点
    3
    中序访问右子树
    后序
    1
    后序访问左子树
    2
    后序访问右子树
    3
    访问根结点
    三、递归法遍历二叉树
    先序:
    Status(PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e)){
    if(T){
    if(Visit(T->data))
    if(PreOrderTraverse(t->lchild,Visit))
    if(PreOrderTraverse(T->rchild,Visit)) return OK;
    return ERROR;
    }else return OK;
    }
    遍历结果:1,2,4,5,6,7,3
    四、非递归法遍历二叉树
    中序一:
    Status InorderTraverse(BiTree T,Status(*Visit)(TElemType e)){
    InitStack(S);Push(S,T);
    while(!StackEmpty(S)){
    while(GetTop(S,p)&&p)Push(S,p->lchild);
    Pop(S,p);
    if(!StackEmpty(S)){
    Pop(S,p); if(!Visit(p->data)) return ERROR;
    Push(S,p->rchild);
    }
    }
    return OK;
    }
    中序二:
    Status InorderTraverse(BiTree T,Status(*Visit)(TElemType e)){
    InitStack(S);p=T;
    while(p||!StackEmpty(S)){
    if(p){Push(S,p);p=p->lchild;}
    else{
    Pop(S,p); if(!Visit(p->data)) return ERROR;
    p=p->rchild);
    }//else
    }//while
    return OK;
    }
    五、总结
    二叉树遍历的意义
    第二十五课
    本课主题: 单元测验
    教学目的: 复习前面所学的内容,检验学习效果,拾遗补缺
    教学重点:
    教学难点:
    授课内容:
    测验题:
    一,填空:
    1.    基本数据结构有____,____,____,____四种。
    2.    存储结构可根据数据元素在机器中的位置是否连续分为____,____。
    3.    算法的基本要求有_____,_____,____,____。
    4.    度量算法效率可通过_______,_______两方面进行。
    5.    栈的定义:_______________________。
    二,简答:
    1.    举例说明数据对象、数据元素、数据项的定义。
    2.    类C语言和C语言有哪些主要区别?
    3.    线性表的基本操作有哪些?
    4.    写出类C语言定义的线性表的静态分配顺序存储结构。
    三,算法设计:
    1.    下面是线性表的存储结构和插入算法,请补充算法中空缺部分。
    #define LIST_INIT_SIZE 100
    #define LISTINCREMENT 10
    typedef struct{
    ElemType *elem; //存储空间基址
    int length; //当前长度
    int listsize; //当前分配的存储容量以一数据元素存储长度为单位
    }SqList;
    status ListInsert(List *L,int i,ElemType e) {
    ____________ *p,*q;
    if (i<1||i>L->length+1) return ERROR;
    q=&(L->elem[i-1]);
    for(p=&L->elem[L->length-1];p>=q;--p)
    ________________;
    *q=e;
    __________________;
    return OK;
    }/*ListInsert Before i */
    2.    下面是栈的顺序存储结构和入栈、出栈算法,请补充算法中空缺部分。
    typedef struct{
    SElemType *base;
    SElemType *top; //设栈顶栈底两指针的目的是便于判断栈是否为空
    int StackSize; //栈的当前可使用的最大容量.
    }SqStack;
    Status Push(SqStack &S,SElemType e); {
    if(S.top - s.base>=S.stacksize) {
    S.base=(ElemType *) realloc(S.base,
    (S.stacksize + STACKINCREMENT) * sizeof(ElemType));
    if(!S.base)exit(OVERFLOW);
    S.top=S.base+S.stacksize;
    S.stacksize+=STACKINCREMENT;
    }
    *S.top++=_____;
    return OK;
    } //Push
    Status Pop(SqStack &S,SElemType &e); {
    if(________)
    return ERROR;
    _____=*--S.top;
    return OK;
    }//Pop
    四,问答:
    1.    用图示法说明在单向线性链表中插入结点的过程。
    2.    有一学生成绩单,画出用链式存储结构时的成绩单数据的存储映像。
    3.    用C语言实现单向线性链表。写出存储结构定义及基本算法。
     
    第二十六课
    本课主题: 图的定义与术语
    教学目的: 掌握图的定义及常用术语
    教学重点: 图的常用术语
    教学难点: 图的常用术语
    授课内容:
    一、图的定义
    图是一种数据元素间为多对多关系的数据结构,加上一组基本操作构成的抽象数据类型。
    ADT Graph{
    数据对象V :V是具有相同特性的数据元素的集合,称为顶点集。
    数据关系R:
    R={VR}
    VR={<v,w>|v,w(-V且P(v,w),<v,w>表示从v到w的弧,谓词P(v,w)定义了弧<v,w>的意义或信息}
    基本操作P:
    CreateGraph(&G,V,VR);
    初始条件:V是图的顶点集,VR是图中弧的集合。
    操作结果:按V和VR的定义构造图G
    DestroyGraph(&G);
    初始条件:图G存在
    操作结果:销毁图G
    LocateVex(G,u);
    初始条件:图G存在,u一G中顶点有相同特征
    操作结果:若G中存在顶点u, 则返回该顶点在图中位置;否则返回其它信息。
    GetVex(G,v);
    初始条件:图G存在,v是G中某个顶点
    操作结果:返回v的值。
    PutVex(&G,v,value);
    初始条件:图G存在,v是G中某个顶点
    操作结果:对v赋值value
    FirstAdjVex(G,v);
    初始条件:图G存在,v是G中某个顶点
    操作结果:返回v的第一个邻接顶点。若顶点在G中没有邻接顶点,则返回“空”
    NextAdjVex(G,v,w);
    初始条件:图G存在,v是G中某个顶点,w是v的邻接顶点。
    操作结果:返回v的(相对于w的)下一个邻接顶点。若w是v的最后一个邻接点,则返回“空”
    InsertVex(&G,v);
    初始条件:图G存在,v和图中顶点有相同特征
    操作结果:在图G中增添新顶点v
    DeleteVex(&G,v);
    初始条件:图G存在,v是G中某个顶点
    操作结果:删除G中顶点v及其相关的弧
    InsertAcr(&G,v,w);
    初始条件:图G存在,v和w是G中两个顶点
    操作结果:在G中增添弧<v,w>,若G是无向的,则还增添对称弧<w,v>
    DeleteArc(&G,v,w);
    初始条件:图G存在,v和w是G中两个顶点
    操作结果:在G中删除弧<v,w>,若G是无向的,则还删除对称弧<w,v>
    DFSTraverser(G,v,Visit());
    初始条件:图G存在,v是G中某个顶点,Visit是顶点的应用函数
    操作结果:从顶点v起深度优先遍历图G,并对每个顶点调用函数Visit一次。一旦Visit()失败,则操作失败。
    BFSTRaverse(G,v,Visit());
    初始条件:图G存在,v是G中某个顶点,Visit是顶点的应用函数
    操作结果:从顶点v起广度优先遍历图G,并对每个顶点调用函数Visit一次。一旦Visit()失败,则操作失败。
    }ADT Graph
    二、图的常用术语
    对上图有:G1=(V1,{A1})
    其中:V1={v1,v2,v3,v4} A1={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}
    如果用n表示图中顶点数目,用e表示边或弧的数目,则有:
    对于无向图,e的取值范围是0到n(n-1)/2,有n(n-1)/2条边的无向图称为完全图
    对于有向图,e有取值范围是0到n(n-1)。具有n(n-1)条弧的有向图称为有向完全图
    有很少条边或弧的图称为稀疏图,反之称为稠密图
    v1与v2互为邻接点
    e1依附于顶点v1和v2
    v1和v2相关联
    v1的度为3
    对有向图,如果每一对顶点之间都有通路,则称该图为强连通图。
    三、总结
    图的特征
    有向图与无向图的主要区别
    第二十七课
    本课主题: 实验六 二叉树实验
    教学目的: 掌握二叉树的链式存储结构
    教学重点: 二叉树的链式存储实现方法
    教学难点:
    授课内容:
    生成如下二叉树,并得出三种遍历结果:
    一、二叉树的链式存储结构表示
    typedef struct BiTNode{
    TElemType data;
    struct BitNode *lchild,*rchild;
    }BiTNode,*BiTree;
    二、二叉树的链式存储算法实现
    CreateBiTree(&T,definition);
    InsertChild(T,p,LR,c);
    三、二叉树的递归法遍历
    PreOrderTraverse(T,Visit());
    InOrderTraverse(T,Visit());
    PostOrderTraverse(T,Visit());
     
     
    第二十八课
    本课主题: 图的存储结构
    教学目的: 掌握图的二种存储表示方法
    教学重点: 图的数组表示及邻接表表示法
    教学难点: 邻接表表示法
    授课内容:
    一、数组表示法
    用两个数组分别存储数据元素(顶点)的信息和数据元素之间的关系(边或弧)的信息。
    // 图的数组(邻接矩阵)存储表示
    #define INFINITY INT_MAX //最大值无穷大
    #define MAX_VERTEX_NUM 20 //最大顶点个数
    typedef enum{DG,DN,AG,AN} GraphKind;//有向图,有向网,无向图,无向网
    typedef struct ArcCell{
    VRType adj; //VRType是顶点关系类型。对无权图,用1或0表示相邻否,对带权图,则为权值类型
    InfoType *info; //该弧相关停息的指针
    }ArcCell,AdjMatrix[max_vertex_num][max_vertex_num];
    tpyedef struct{
    VertexType vexs[MAX_VERTEX_NUM]; //顶点向量
    AdjMatrix arcs; //邻接矩阵
    int vexnum,arcnum; //图的当前顶点数和弧数
    GraphKind kind; //图的种类标志
    }MGraph;
    二、邻接表
    邻接表是图的一种链式存储结构。
    在邻接表中,对图中每个顶点建立一个单链表,第i个单链表中的结点表示依附于顶点vi的边(对有向图是以顶点vi为尾的弧)。每个结点由三个域组成,其中邻接点域(adjvex)指示与顶点vi邻接的点在图中的位置,链域(nextarc)指示下一条边或弧的结点;数据域(info)存储和边或弧相关的信息,如权值等。每个链表上附设一个表头结点,包含链域(firstarc)指向链表中第一个结点,还设有存储顶点vi的名或其它有关信息的数据域(data)。如:
    表结点
    adjvex
    nextarc
    info
    头结点
    data
    firstarc
    #define MAX_VERTEX_NUM 20
    typedef struct ArcNode{
    int adjvex; //该弧所指向的顶点的位置
    struct ArcNode *nextarc; //指向下一条弧的指针
    InfoType *info; //该弧相关信息的指针
    }ArcNode;
    typedef struct VNode{
    VertexType data; //顶点信息
    ArcNode *firstarc; //指向第一条依附该顶点的弧的指针
    }VNode,AdjList[MAX_VERTEX_NUM];
    typedef struct {
    AdjList vertices; //图的当前顶点数和弧数
    int vexnum,arcnum; //图的种类标志
    int kind;
    }ALGraph;
     
    三、总结
    图的存储包括哪些要素?
    第二十九课
    本课主题: 静态查找表(一)顺序表的查找
    教学目的: 掌握查找的基本概念,顺序表查找的性能分析
    教学重点: 查找的基本概念
    教学难点: 顺序表查找的性能分析
    授课内容:
    一、查找的基本概念
     
    查找表:
    是由同一类型的数据元素(或记录)构成的集合。
    查找表的操作:
    1、查询某个“特定的”数据元素是否在查找表中。
    2、检索某个“特定的”数据元素的各种属性。
    3、在查找表中插入一个数据元素;
    4、从查找表中刪去某个数据元素。
    静态查找表
    对查找表只作前两种操作
    动态查找表
    在查找过程中查找表元素集合动态改变
    关键字
    是数据元素(或记录)中某个数据项的值
    可以唯一的地标识一个记录
    次关键字
    用以识别若干记录
    查找
    根据给定的某个值,在查找表中确定一个其关键字等于给定的记录或数据元素。若表中存在这样的一个记录,则称查找是成功的,此时查找的结果为给出整个记录的信息,或指示该记录在查找表中的位置;若表中不存在关键字等于给定值的记录,则称查找不成功
    一些约定:
    典型的关键字类型说明:
    typedef float KeyType;//实型
    typedef int KeyType;//整型
    typedef char *KeyType;//字符串型
    数据元素类型定义为:
    typedef struct{
    KeyType key; // 关键字域
    ...
    }ElemType;
    对两个关键字的比较约定为如下的宏定义:
    对数值型关键字
    #define EQ(a,b) ((a)==(b))
    #define LT(a,b) ((a)<(b))
    #define LQ(a,b) ((a)<=(b))
    对字符串型关键字
    #define EQ(a,b) (!strcmp((a),(b)))
    #define LT(a,b) (strcmp((a),(b))<0)
    #define LQ(a,b) (strcmp((a),(b))<=0)
    二、静态查找表
    静态查找表的类型定义:
    ADT StaticSearchTable{
    数据对象D:D是具有相同特性的数据元素的集合。各个数据元素均含有类型相同,可唯一标识数据元素的关键字。
    数据关系R:数据元素同属一个集合。
    基本操作P:
    Create(&ST,n);
    操作结果:构造一个含n个数据元素的静态查找表ST。
    Destroy(&ST);
    初始条件:静态查找表ST存在。
    操作结果:销毁表ST。
    Search(ST,key);
    初始条件:静态查找表ST存在,key为和关键字类型相同的给定值。
    操作结果:若ST中在在其关键字等于key的数据元素,则函数值为该元素的值或在表中的位置,否则为“空”。
    Traverse(ST,Visit());
    初始条件:静态查找表ST存在,Visit是对元素操作的应用函数。
    操作结果:按某种次序对ST的每个元素调用函数visit()一次且仅一次。一旦visit()失败,则操作失败。
    }ADT StaticSearchTable
    三、顺序表的查找
    静态查找表的顺序存储结构
    typedef struct {
    ElemType *elem;
    int length;
    }SSTable;
    顺序查找:从表中最后一个记录开始,逐个进行记录的关键字和给定值的比较,若某个记录的关键字和给定值比较相等,则查找成功,找到所查记录;反之,查找不成功。
    int Search_Seq(SSTable ST,KeyType key){
    ST.elme[0].key=key;
    for(i=ST.length; !EQ(ST.elem[i].key,key); --i);
    return i;
    }
    查找操作的性能分析:
    查找算法中的基本操作是将记录的关键字和给定值进行比较,,通常以“其关键字和给定值进行过比较的记录个数的平均值”作为衡量依据。
    平均查找长度:
    为确定记录在查找表中的位置,需用和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度。
    其中:Pi为查找表中第i个记录的概率,且
    Ci为找到表中其关键字与给定值相等的第i个记录时,和给定值已进行过比较的关键字个数。
    等概率条件下有:
    假设查找成功与不成功的概率相同:
    四、总结
    什么是查找表
    顺序表的查找过程
    第三十课
    本课主题: 静态查找表(二)有序表的查找
    教学目的: 掌握有序表的折半查找法
    教学重点: 折半查找
    教学难点: 折半查找
    授课内容:
    一、折半查找的查找过程
    以有序表表示静态查找表时,Search函数可用折半查找来实现。
    先确定待查记录所在的范围(区间),然后逐步缩小范围直到找到或找不到该记录为止。
    二、折半查找的查找实现
    int Search_Bin(SSTable ST,KeyType key){
    low=1;high=ST.length;
    while(low<=high){
    mid=(low+high)/2;
    if EQ(key,ST.elem[mid].key) return mid;
    else if LT(key,ST.elem[mid].key) high=mid -1;
    else low=mid +1 ;
    }
    return 0;
    }//Search_Bin;
    三、折半查找的性能分析
    折半查找在查找成功时和给定值进行比较的关键字个数至多为
    第三十一课
    本课主题: 动态查找表
    教学目的: 掌握二叉排序树的实现方法
    教学重点: 二叉排序树的实现
    教学难点: 构造二叉排序树的方法
    授课内容:
    一、动态查找表的定义
    动态查找表的特点是:
    表结构本身是在查找过程中动态生成的,即对于给定值key,若表中存在其关键字等于key的记录,则查找成功返回,否则插入关键字等于key的记录。以政是动态查找表的定义:
    ADT DymanicSearchTable{
    数据对象D:D是具有相同特性的数据元素的集合。各个数据元素均含有类型相同,可唯一标识数据元素的关键字。
    数据关系R:数据元素同属一个集合。
    基本操作P:
    InitDSTable(&DT);
    DestroyDSTable(&DT);
    SearchDSTable(DT,key);
    InsertDSTable(&DT,e);
    DeleteDSTable(&DT,key);
    TraverseDSTable(DT,Visit());
    }ADT DynamicSearchTable
    二、二叉排序树及其查找过程
    二叉排序树或者是一棵空树;或者是具有下列性质的二叉树:
    1、若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
    2、若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
    3、它的左、右子树了分别为二叉排序树。
    如果取二叉链表作为二叉排序树的存储结构,则上述查找过程如下:
    BiTree SearchBST(BiTree T,KeyType key){
    if(!T)||EQ(key,T->data.key)) return (T);
    else if LT(key,T->data.key) return (SearchBST(T->lchild,key));
    else return (SearchBST(T->rchild.key));
    }//SearchBST
    三、二叉排序树的插入和删除
    二叉排序树是一种动态树表,其特点是,树的结构通常不是一资生成的,面是在查找过程中,当树中不存在关键字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点,并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。
    Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree &p){
    if(!T) {p=f;return FALSE;}
    else if EQ(key,T->data.key){ p=T;return TRUE;}
    else if LT(key,T->data.key) SearchBsT(T->lchild,key,T,p);
    else SearchBST(T->rchild,key,T,p);
    }//SearchBST
    插入算法:
    Status InsertBST(BiTree &T,ElemType e){
    if(!SearchBST(T,e.key,NULL,p){
    s=(BiTree)malloc(sizeof(BiTNode));
    s->data=e;s->lchild=s->rchild=NULL;
    if(!p) T=s;
    else if (LT(e.key,p->data.key) p->lchild=s;
    else p->rchild=s;
    return TRUE;
    }
    else return FALSE;
    }//InsertBST
    在二叉排序树中删除一个节点的算法:
     
    Status DeleteBST(BiTree &T,KeyType key){
    if(!T) return FALSE;
    else{
    if EQ(key,T->data.key) Delete(T);
    else if LT(key,T->data.key) DeleteBST(T->lchild,key);
    else DeleteBST(T->rchild,key);
    return TRUE;
    }
    }
    void Delete(BiTree &p){
    if(!p->rchild){
    q=p; p=p->lchild; free(q);
    }
    else if(!p->lchild){
    q=p;p=p->rchild; free(q);
    }
    else{
    //方法一:如图示
    q=p;s=p->lchild;
    while(s->rchild){q=s;s=s->rchild}//转左,然后向右到尽头
    p->data=s->data; //s指向被删结点的"前驱"
    if(q!=p)q->rchild=s->lchild; //重接*q的右子树
    else q->lchild=s->lchild;//重接*q的左子树(方法一结束)
    //或可用方法二:
    //q=s=(*p)->l;
    //while(s->r) s=s->r;
    //s->r=(*p)->r;
    //free(*p);
    //(*p)=q;
    }
    }
    四、总结
    第三十二课
    本课主题: 哈希表(一)
    教学目的: 掌握哈希表的概念作用及意义,哈希表的构造方法
    教学重点: 哈希表的构造方法
    教学难点: 哈希表的构造方法
    授课内容:
    一、哈希表的概念及作用
    一般的线性表,树中,记录在结构中的相对位置是随机的,即和记录的关键字之间不存在确定的关系,因此,在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较“的基础上,查找的效率依赖于查找过程中所进行的比较次数。
    理想的情况是能直接找到需要的记录,因此必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使每个关键字和结构中一个唯一的存储位置相对应。
    哈希表最常见的例子是以学生学号为关键字的成绩表,1号学生的记录位置在第一条,10号学生的记录位置在第10条...
    如果我们以学生姓名为关键字,如何建立查找表,使得根据姓名可以直接找到相应记录呢?
    a
    b
    c
    d
    e
    f
    g
    h
    i
    j
    k
    l
    m
    n
    o
    p
    q
    r
    s
    t
    u
    v
    w
    x
    y
    z
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
     
     
    刘丽
    刘宏英
    吴军
    吴小艳
    李秋梅
    陈伟
    ...
    姓名中各字拼音首字母
    ll
    lhy
    wj
    wxy
    lqm
    cw
    ...
    用所有首字母编号值相加求和
    24
    46
    33
    72
    42
    26
    ...
    最小值可能为3 最大值可能为78 可放75个学生
    用上述得到的数值作为对应记录在表中的位置,得到下表:
     
     
    成绩一
    成绩二...
    3
    ...
     
     
    ...
    ...
     
     
    24
    刘丽
    82
    95
    25
    ...
     
     
    26
    陈伟
     
     
    ...
    ...
     
     
    33
    吴军
     
     
    ...
    ...
     
     
    42
    李秋梅
     
     
    ...
    ...
     
     
    46
    刘宏英
     
     
    ...
    ...
     
     
    72
    吴小艳
     
     
    ...
    ...
     
     
    78
    ...
     
     
    上面这张表即哈希表
    如果将来要查李秋梅的成绩,可以用上述方法求出该记录所在位置:
    李秋梅:lqm 12+17+13=42 取表中第42条记录即可。
    问题:如果两个同学分别叫刘丽 刘兰 该如何处理这两条记录?
    这个问题是哈希表不可避免的,即冲突现象:对不同的关键字可能得到同一哈希地址。
    二、哈希表的构造方法
    1、直接定址法
    例如:有一个从1到100岁的人口数字统计表,其中,年龄作为关键字,哈希函数取关键字自身。
    地址
    01
    02
    ...
    25
    26
    27
    ...
    100
    年龄
    1
    2
    ...
    25
    26
    27
    ...
    ...
    人数
    3000
    2000
    ...
    1050
    ...
    ...
    ...
    ...
    ...
     
     
     
     
     
     
     
     
    2、数字分析法
    有学生的生日数据如下:
    年.月.日
    75.10.03
    75.11.23
    76.03.02
    76.07.12
    75.04.21
    76.02.15
    ...
    经分析,第一位,第二位,第三位重复的可能性大,取这三位造成冲突的机会增加,所以尽量不取前三位,取后三位比较好。
    3、平方取中法
    取关键字平方后的中间几位为哈希地址。
    4、折叠法
    将关键字分割成位数相同的几部分(最后一部分的位数可以不同),然后取这几部分的叠加和(舍去进位)作为哈希地址,这方法称为折叠法。
    例如:每一种西文图书都有一个国际标准图书编号,它是一个10位的十进制数字,若要以它作关键字建立一个哈希表,当馆藏书种类不到10,000时,可采用此法构造一个四位数的哈希函数。如果一本书的编号为0-442-20586-4,则:
     
    5864
     
    5864
     
    4220
     
    0224
    +)
    04
    +)
    04
     
    -----------
     
    -----------
     
    10088
     
    6092
     
    H(key)=0088
     
    H(key)=6092
     
     
     
     
     
    (a)移位叠加
     
    (b)间界叠加
    5、除留余数法
    取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。
    H(key)=key MOD p (p<=m)
    6、随机数法
    选择一个随机函数,取关键字的随机函数值为它的哈希地址,即
    H(key)=random(key) ,其中random为随机函数。通常用于关键字长度不等时采用此法。
    三、总结
    哈希表的优缺点
    四、作业
     
    预习如何处理冲突及哈希表的查找。
    第三十三课
    本课主题: 哈希表(二)
    教学目的: 掌握哈希表处理冲突的方法及哈希表的查找算法
    教学重点: 哈希表处理冲突的方法
    教学难点: 开放定址法
    授课内容:
    一、复习上次课内容
    什么是哈希表?如何构造哈希表?
    提出问题:如何处理冲突?
    二、处理冲突的方法
     
     
    成绩一
    成绩二...
    3
    ...
     
     
    ...
    ...
     
     
    24
    刘丽
    82
    95
    25
    ...
     
     
    26
    陈伟
     
     
    ...
    ...
     
     
    33
    吴军
     
     
    ...
    ...
     
     
    42
    李秋梅
     
     
    ...
    ...
     
     
    46
    刘宏英
     
     
    ...
    ...
     
     
    72
    吴小艳
     
     
    ...
    ...
     
     
    78
    ...
     
     
    如果两个同学分别叫刘丽 刘兰,当加入刘兰时,地址24发生了冲突,我们可以以某种规律使用其它的存储位置,如果选择的一个其它位置仍有冲突,则再选下一个,直到找到没有冲突的位置。选择其它位置的方法有:
    1、开放定址法
    Hi=(H(key)+di) MOD m i=1,2,...,k(k<=m-1)
    其中m为表长,di为增量序列
    如果di值可能为1,2,3,...m-1,称线性探测再散列
    如果di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,...k*k,-k*k(k<=m/2)
    二次探测再散列
    如果di取值可能为伪随机数列。称伪随机探测再散列
    例:在长度为11的哈希表中已填有关键字分别为17,60,29的记录,现有第四个记录,其关键字为38,由哈希函数得到地址为5,若用线性探测再散列,如下:
    0
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
     
     
     
     
     
    60
    17
    29
     
     
     
    (a)插入前
    0
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
     
     
     
     
     
    60
    17
    29
    38
     
     
    (b)线性探测再散列
    0
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
     
     
     
     
     
    60
    17
    29
     
     
     
    (c)二次探测再散列
    0
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
     
     
     
    38
     
    60
    17
    29
     
     
     
    (d)伪随机探测再散列
    伪随机数列为9,5,3,8,1...
    2、再哈希法
    当发生冲突时,使用第二个、第三个、哈希函数计算地址,直到无冲突时。缺点:计算时间增加。
    3、链地址法
    将所有关键字为同义词的记录存储在同一线性链表中。
    4、建立一个公共溢出区
    假设哈希函数的值域为[0,m-1],则设向量HashTable[0..m-1]为基本表,另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录。
    三、哈希表的查找
    //开放定址哈希表的存储结构
    int hashsize[]={997,...};
    typedef struct{
    ElemType *elem;
    int count;
    int sizeindex;
    }HashTable;
    #define SUCCESS 1
    #define UNSUCCESS 0
    #define DUPLICATE -1
    Status SearchHash(HashTable H,KeyType K,int &p,int &c){
    p=Hash(K);
    while(H.elem[p].key!=NULLKEY && !EQ(K,H.elem[p].key))
    collision(p,++c);
    if(EQ(K,H.elem[p].key)
    return SUCCESS;
    else return UNSUCCESS;
    }
    Status InsertHash(HashTable &H,EleType e){
    c=0;
    if(SearchHash(H,e.key,p,c))
    return DUPLICATE;
    else if(c<hashsize[H.sizeindex]/2){
    H.elem[p]=e; ++H.count; return OK;
    }
    else RecreateHashTable(H);
    }
    四、总结
    处理冲突的要求是什么?
    第三十四课
    本课主题: 插入排序,快速排序
    教学目的: 掌握排序的基本概念,插入排序、快速排序的算法
    教学重点: 插入排序、快速排序的算法
    教学难点: 快速排序算法
    授课内容:
    一、排序概述
    排序:将一个数据元素的无序序列重新排列成一个按关键字有序的序列。
    姓名
    年龄
    体重
    1李由
    57
    62
    2王天
    54
    76
    3七大
    24
    75
    4张强
    24
    72
    5陈华
    24
    53
    上表按年龄无序,如果按关键字年龄用某方法排序后得到下表:
    姓名
    年龄
    体重
    3七大
    24
    75
    4张强
    24
    72
    5陈华
    24
    53
    2王天
    54
    76
    1李由
    57
    62
    注意反色的三条记录保持原有排列顺序,则称该排序方法是稳定的
    如果另一方法排序后得到下表:
    姓名
    年龄
    体重
    4张强
    24
    72
    3七大
    24
    75
    5陈华
    24
    53
    2王天
    54
    76
    1李由
    57
    62
    原3,4,5记录顺序改变,则称该排序方法是不稳定的
    内部排序:待排序记录存放在计算机随机存储器中进行的排序过程;
    外部排序:待排序记录的数量很大,以致内存一次不能容纳全部记录,在排序过程中尚需对外存进行访问的排序过程。
    二、插入排序
    1、直接插入排序
    基本操作是将一个记录插入到已排好序的有序表中,从而得到一个新的、记录数增1的有序表。排序过程:
    38
    49
    65
    97
    76
    13
    27
    49
    ...
     
     
    38
    49
    65
    76
    97
    13
    27
    49
    ...
     
     
    13
    38
    49
    65
    76
    97
    27
    49
    ...
     
     
    13
    27
    38
    49
    65
    76
    97
    49
    ...
     
     
    13
    27
    38
    49
    49
    65
    76
    97
    ...
     
    2、折半插入排序
    在直接插入排序中,为了找到插入位置,采用了顺序查找的方法。为了提高查找速度,可以采用折半查找,这种排序称折半插入排序。
    3、2-路插入排序
    为减少排序过程中移动记录的次数,在折半插入排序的基础上加以改进:
    49
    38
    65
    97
    78
    13
    27
    49
    ...
     
     
    i=1
    49
     
     
     
     
     
     
     
     
    first
     
     
     
     
     
     
     
    i=2
    49
     
     
     
     
     
     
    38
     
    final
     
     
     
     
     
     
    first
    i=3
    49
    65
     
     
     
     
     
    38
     
     
    final
     
     
     
     
     
    first
    i=4
    49
    65
    97
     
     
     
     
    38
     
     
     
    final
     
     
     
     
    first
    i=5
    49
    65
    76
    97
     
     
     
    38
     
     
     
     
    final
     
     
     
    first
    i=6
    49
    65
    76
    97
     
     
    13
    38
     
     
     
     
    final
     
     
    first
     
    i=7
    49
    65
    76
    97
     
    13
    27
    38
     
     
     
     
    final
     
    first
     
     
    i=8
    49
    49
    65
    76
    97
    13
    27
    38
     
     
     
     
     
    final
    first
     
     
    三、快速排序
    1、起泡排序
    首先将第一个记录的关键字和第二个记录的关键字进行比较,若为逆序,则将两个记录交换之,然后比较第二个记录和第三个记录的关键字。直至第n-1个记录和第n个记录的关键字进行过比较为止。
    然后进行第二趟起泡排序,对前n-1个记录进行同样操作。
    ...直到在某趟排序过程中没有进行过交换记录的操作为止。
    49
    38
    38
    38
    38
    13
    13
    38
    49
    49
    49
    13
    27
    27
    65
    65
    65
    13
    27
    38
    38
    97
    76
    13
    27
    49
    49
     
    76
    13
    27
    49
    49
     
     
    13
    27
    49
    65
     
     
     
    27
    49
    78
     
     
     
     
    49
    97
     
     
     
     
     
    初始
    第一趟
    第二趟
    第三趟
    第四趟
    第五趟
    第六趟
    2、快速排序
    通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。
    初始关键字
    49
    38
    65
    97
    76
    13
    27
    49
     
    i
     
     
     
     
     
    j
    j
    1次交换之后
    27
    38
    65
    97
    76
    13
     
    49
     
    i
     
    i
     
     
     
    j
     
    2次交换之后
    27
    38
     
    97
    76
    13
    65
    49
     
     
     
    i
     
     
    j
    j
     
    3次交换之后
    27
    38
    13
    97
    76
     
    65
    49
     
     
     
    i
    i
     
    j
     
     
    4次交换之后
    27
    38
    13
     
    76
    97
    65
    49
     
     
     
     
    ij
     
    j
     
     
    完成一趟排序
    27
    38
    13
    49
    76
    97
    65
    49
     
     
     
     
     
     
     
     
     
    初始状态
    49
    38
    65
    97
    76
    13
    27
    49
    一次划分
    27
    38
    13
    49
    76
    97
    65
    49
    分别进行
    13
    27
    38
     
     
     
     
     
     
    结束
     
    结束
     
    49
    65
    76
    97
     
     
     
     
     
    49
    65
     
    结束
     
     
     
     
     
     
    结束
     
     
    有序序列
    13
    27
    38
    49
    49
    65
    76
    97
     
     
     
     
     
     
     
     
     
     
    四、总结
    几种排序的简单分析与比较。(时间、空间复杂度)
    五、作业
    实现直接插入排序、起泡排序、快速排序算法。
    第三十五课
    本课主题: 实验七 查找
    教学目的: 练习顺序查找、折半查找及二叉排序树的实现
    教学重点:
    教学难点:
    授课内容:
    顺序查找
    折半查找
    二叉排序树
    第三十六课
    本课主题: 选择排序,归并排序
    教学目的: 掌握选择排序,归并排序算法
    教学重点: 选择排序之堆排序,归并排序算法
    教学难点: 堆排序算法
    授课内容:
    一、选择排序
    每一趟在n-i+1(i=1,2,...n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。
    二、简单选择排序
    算法:
    Smp_Selecpass(ListType &r,int i)
    {
    k=i;
    for(j=i+1;j<n;i++)
    if (r[j].key<r[k].key)
    k=j;
    if (k!=i)
    { t=r[i];r[i]=r[k];r[k]=t;}
    }
    Smp_Sort(ListType &r)
    {
    for(i=1;i<n-1;i++)
    Smp_Selecpass(r,i);
    }
    三、树形选择排序
    又称锦标赛排序,首先对n个记录的关键字进行两两比较,然后在其中一半较小者之间再进行两两比较,如此重复,直到选出最小关键字的记录为止。
    四、堆排序
    只需要一个记录大小的辅助空间,每个待排序的记录仅占有一个存储空间。
    什么是堆?n个元素的序列{k1,k2,...,kn}当且仅当满足下列关系时,称之为堆。关系一:ki<=k2i 关系二:ki<=k2i+1(i=1,2,...,n/2)
    堆排序要解决两个问题:1、如何由一个无序序列建成一个堆?2、如何在输出堆顶元素之后,调整剩余元素成为一个新的堆?
    问题2的解决方法:
    sift(ListType &r,int k,int m)
    {
    i=k;j=2*i;x=r[k].key;finished=FALSE;
    t=r[k];
    while((j<=m)&&(!finished))
    {
    if ((j<m)&&(r[j].key>r[j+1].key)) j++;
    if (x<=r[j].key)
    finished:=TRUE;
    else {r[i]=r[j];i=j;j=2*i;}
    }
    r[i]=t;
    }
    HeapSort(ListType &r)
    {
    for(i=n/2;i>0;i--) sift(r,i,n);
    for(i=n;i>1;i--){
    r[1]<->r[i];
    sift(r,i,i-1)
    }
    }
    五、归并排序
    将两个或两个以上的有序表组合成一个新的有序表的方法叫归并。
    假设初始序列含有n个记录,则可看成是n个有序的子序列,每个子序列的长度为1,然后两两归并,得到n/2个长度为2或1的有序子序列;再两两归并,如此重复。
    merge(ListType r,int l,int m,int n,ListType &r2)
    {
    i=l;j=m+1;k=l-1;
    while(i<=m) and(j<n) do
    {
    k=k+1;
    if (r[i].key<=r[j].key) {r2[k]=r[i];i++;}
    else {r2[i]=r[j];j++}
    }
    if (i<=m) r2[k+1..n]=r[i..m];
    if (j<=n) r2[k+1..n]=r[j..n];
    }
    mergesort(ListType &r,ListType &r1,int s,int t)
    {
    if (s==t)
    r1[s]=r[s];
    else
    {
    mergesort(r,r2,s,s+t/2);
    mergesort(r,r2,s+t/2+1,t);
    merge(r2,s,s+t/2,t,r1);
    }
    ]
    六、总结
    第三十七课
    本课主题: 实验八 排序实验
    教学目的: 掌握简单插入排序、快速排序、堆排序的算法并加以应用。
    教学重点:
    教学难点:
    授课内容:
    实现下述三种算法,并用以下无序序列加以验证:
    49,38,65,97,76,13,27,49
    一、简单插入排序
    二、快速排序
    三、堆排序
    第三十八课
    本课主题: 文件概念,顺序文件
    教学目的: 掌握文件基本概念,顺序文件的概念。
    教学重点: 文件基本概念
    教学难点: 逻辑结构与物理结构的关系。
    授课内容:
    一、表与文件
    和表类似,文件是大量记录的集合。习惯上称存储在主存储器(内存储器)中的记录集合为表,称存储在二级存储器(外存储器)中的记录集合为文件。
    二、文件基本概念
    文件:是由大量性质相同的记录组成的集合。
    文件按记录类型不同分类
    操作系统的文件
    一维的连续的字符序列
    数据库文件
    带有结构的记录的集合,每条记录是由一个或多个数据项组成的集合。
    姓名
    准考证号
    政治
    语文
    数学
    外语
    刘青
    1501
    78
    90
    100
    95
    张朋
    1502
    64
    88
    90
    74
    崔永
    1503
    90
    100
    85
    89
    郑琳
    1504
    85
    73
    90
    91
    ...
     
     
     
     
     
     
    文件按记录长度是否相同分类
    定长记录文件
    文件中每个记录含有信息长度相同。
    不定长记录文件
    文件中每个记录含有信息长度不等。
    记录的逻辑结构是指记录在用户或应用程序员面前呈现的方式,是用户对数据的表示和存取方式。
    姓名
    准考证号
    政治
    语文
    数学
    外语
    刘青
    1501
    78
    90
    100
    95
    张朋
    1502
    64
    88
    90
    74
    崔永
    1503
    90
    100
    85
    89
    郑琳
    1504
    85
    73
    90
    91
    ...
     
     
     
     
     
    这张成绩表呈现的结构即是逻辑结构。
    记录的物理结构是数据在物理存储器上存储的方式。一条物理记录指的是计算机用一条I/O命令进行读写的基本数据单位。
    三、顺序文件
    顺序文件中的物理记录的顺序和逻辑记录的顺序是一致的。
    四、总结
    第三十九课
    本课主题: 索引文件
    教学目的: 掌握索引文件的有关概念
    教学重点: 索引文件的基本概念,索引文件的重要意义
    教学难点: 索引文件的建立
    授课内容:
    一、索引文件的基本概念
    除了文件本身(称作数据区)之外,别建立一张指示逻辑记录和物理记录之间一一对应关系的表--索引表
    索引表中的每一项称作索引项。不论主文件是否按关键字有序,索引表中的索引项总是按关键字(或逻辑记录号)顺序排列。
    若数据区中的记录也按关键字顺序排列,则称索引顺序文件。反之,若数据区中记录不按关键字顺序排列,则称非顺序文件
    数据区:
    物理记录号
    姓名
    年龄
    体重(关键字)
    1
    李由
    57
    62
    2
    王天
    54
    76
    3
    七大
    24
    75
    4
    张强
    24
    72
    5
    陈华
    24
    53
     
    索引表:
    体重(关键字)
    物理记录号
    53
    5
    62
    1
    72
    4
    75
    3
    76
    2
    有了按体重索引的索引表后,按体重查找学生可先在索引表中查找(因索引表中按体重有序,所以可用效率高的查找算法)然后得到对应的物理记录号后到数据区取出对应物理记录。
    索引文件可以大大提高表查找的速度。因为索引表容量小,且索引表按关键字有序。
    二、索引文件的建立
    在记录输入建立数据区的同时建立一个索引表,表中的索引项按记录输入的先后次序排列,待全部记录输入完毕后再对索引表进行排序。
    第四十课
    本课主题: 总复习
    教学目的: 数据结构综述
    教学重点: 数据结构课程的核心
    教学难点: 理解概念
    授课内容:
    一、学习数据结构的意义
    设想一下,你决定向一个公司投资,而你对某个公司的了解只限于该公司的一条生产线每分钟可生产2000件产品,你会作出投资的决定吗?如果你是一个公司的管理者,这个公司日常的每笔交易的详细情况对你来讲的确重要,但如果你把时间花在这些数据上面,你就无法站在宏观的高度上把握公司的经营方向。
    不管是经营一个公司,还是管理一个国家,对描述事物特征的数据必须加以分析与加工,现实事物是普遍联系的,描述这些事物属性及特征的数据之间也是普遍联系的,把这些数据之间的关系进行总结,得到集合、线性、树、图这四种基本关系,由此得到四类基本数据结构。而每种结构类型的数据,相同的操作(如遍历、查找等)需要采用不同的方法(算法),不同结构类型可进行的操作也有区别。通过应用这些算法,可得到事物的总体抽象特征。如:一个公司的年产值,年利润总额,利润率等。
    反过来,为了描述一个复杂的事物,必须分析它的组成部分,既要描述每个部分的特征,又要描述各个部分之间的关系,如此细分下去,便于最终用计算机进行处理,而计算机的基本数据类型不适合描述复杂的结构,且仅用基本数据类型也不便于人的理解与记忆,所以使用介于两者之间的抽象数据类型成了计算机语言描述现实事物的纽带。人可以方便的把事物用抽象数据类型描述,也可以方便的把抽象数据类型用基本数据类型来实现,为用计算机处理现实问题提供了解决方法。
    二、数据结构的学习重点
    如何描述一种新的抽象数据类型?
    如何分析算法的优劣?
    线性表的主要特征。
    线性表的存储表示(顺序表示、单向链表、循环链表、双向链表)
    特殊的线性表:栈、队列、串
    二叉树的定义、性质、存储结构、遍历算法
    图的定义、术语、存储结构
    静态查找表、二叉排序树、哈希函数的构造及冲突处理方法。
    插入排序、快速排序、选择排序
    展开全文
  • Redis内部数据结构详解(1)——dict Redis内部数据结构详解(2)——sds Redis内部数据结构详解(3)——robj Redis内部数据结构详解(4)——ziplist Redis内部数据结构详解(5)——quicklist Redis内部数据结构详解(6)——...
    展开全文
  • Pandas数据结构详解.pdf

    2020-07-16 15:33:22
    Pandas数据结构详解.pdf
  • 主要介绍了Lua教程(七):数据结构详解,本文讲解了数组、二维数组、链表、队列与双向队列、 集合和包(Bag)、StringBuilder等内容,需要的朋友可以参考下
  • redis 五种数据结构详解 string,list,set,zset,hash

    redis 五种数据结构详解

    string,list,set,zset,hash

    展开全文
  • 5种Redis数据结构详解

    万次阅读 2018-08-25 14:51:52
    本文我们主要和大家分享 5种Redis数据结构详解,希望文中的案例和代码,能帮助到大家。 2.1.1 全局命令 1 查看所有键 key* 2 键总数 dbsize (dbsize命令在计算键总数的时候不会遍历所有键,而是直接获取Redis内置...

    http://www.php.cn/php-weizijiaocheng-388126.html

    本文我们主要和大家分享 5种Redis数据结构详解,希望文中的案例和代码,能帮助到大家。

    2.1.1 全局命令

    1 查看所有键 key*

    2 键总数 dbsize (dbsize命令在计算键总数的时候不会遍历所有键,而是直接获取Redis内置的键总数变量,时间复杂度为O(1),而keys命令会遍历所有键,时间复杂度为O(n),当Redis保存了大量键时,线上环境禁止使用)

    3 检查键是否存在 exists key 存在返回1,不存在返回0

    4 删除键 del key 返回成功删除键的个数,不存在的返回0

    5 键过期 expire key seconds ttl 命令会返回剩余过期时间 -1 键没设置过期时间 -2 键不存在

    6 键的数据类型结构 type key 返回类型,不存在返回none 

    2.1.2 数据结构和内部编码

    每种数据结构都有自己的底层的内部编码实现,而且是多种实现,这样Redis会在合适的场景选择合适的内部编码

    每种数据结构都有两种以上的内部编码实现,例如list数据结构包含了linkedlist和ziplist两种内部编码,可以通过object encoding命令查询内部编码

     

     

    Redis这样设计有两个好处:第一:可以改进内部编码,而对外的数据结构和命令没有影响。第二 多种内部编码实现可以在不同的场景下发挥各自的优势。比如,ziplist比较节省内存,但是列表元素比较多的情况下,性能有所下降,这时候Redis会根据配置选项将列表类型的内部实现转换为linkedlist

    2.1.3 单线程架构

    Redis使用了单线程架构和I/O多路复用模型来实现高性能的内存数据库服务

    1 引出单线程模型

    调用客户端的过程:发送命令,执行命令,返回结果

    所有的命令在一个队列里排队等待被执行,不存在多个命令被同时执行的情况

    2 为什么单线程还能跑这么快

    第一,纯内存访问,Redis将所有数据放在内存中,内存的响应时间长约100纳秒,这是Redis达到每秒万级别访问的重要基础

    第二,非阻塞I/O,Redis使用epoll作为I/O多路复用技术的实现,再加上Redis自身的事件处理模型将epoll中的连接、读写、关闭都转换为事件,不在网络I/O上浪费过多的时间

    第三 单线程避免了线程切换和竟态产生的消耗

    单线程带来几个好处:第一,单线程简化数据结构和算法的实现。第二,单线程避免了线程切换和竟态产生的消耗。但是对于每个命令的执行命令是有要求的,如果某个命令执行时间过长,就会造成其他命令的阻塞,Redis是面向快速执行场景的数据库,单线程是理解Redis的核心

    2.2 字符串

    Redis的字符串类型是其他几种的基础,值可以是字符串(简单,复杂的json,xml),数字(整型,浮点),二进制(图片,音频,视频),最大值不能超过512MB

     

    2.2.1 命令

    1 常用命令

    1 设置值 set key value 秒级过期时间 毫秒级过期时间 nx|xx

    setnx setxx同上

    应用场景:由于Redis是单线程命令处理机制,如果多个客户端同时执行setnx key value,根据特性,只有一个客户端能设置成功,可以作为分布式锁的一种实现方案

    2 获取值 get key 不存在返回nil

    3 批量设置值 mset key value 

    4 批量获取值 mget key

    学会使用批量操作,有助于提高业务处理效率,但要注意每次批量操作所发送的命令不是无节制的,数量过多造成Redis阻塞或网络拥塞

    5 计数 incr key

    返回结果有三种情况

    值不是整数 返回错误

    值是整数,返回自增后的结果

    键不存在,按照值为0自增,返回结果为1

    还有decr(自减),incrby(自增指定数字),decrby(自减指定数字),incrbyfloat(自增浮点数)

    2 不常用命令

    1 追加值 append key value

    2 字符串长度 strlen key

    3 设置并返回原值 getset key value

    4 设定指定位置的字符 setrange key offset value

    5 获取部分字符串 getrange key start end

    2.2.2 内部编码

    字符串内部编码有3种:int 8个字节的长整型 embstr 小于等于39个字节的字符串 raw 大于39个字节的字符串。Redis会根据当前值的类型和长度决定使用哪种内部编码实现

    2.2.3 典型使用场景

    1 缓存功能

    Redis作为缓存层,Mysql作为存储层,绝大部分的请求的数据都是从Redis中获取。由于Redis具有支持并发的特性,所以缓存通常能起到加速读写和降低后段压力的作用

     

    开发提示:键名命名方式:业务名:对象名:id:[属性]作为键名

    伪代码实现:

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    UserInfo getUserInfo(long id){

        userRedisKey="user:info:"+id

        value=redis.get(userRedisKey);

        UserInfo userInfo;

        if(value!=null){

            userInfo=deserialize(value)

        }else{

            userInfo=mysql.get(id)

            if(userInfo!=null)

            redis.setex(userRedisKey,3600,serizelize(userInfo))

            }

    return userInfo

    1

    }

    2 计数

    1

    2

    3

    4

    long incrVideoCounter(long id){

    key="video:playCount:"+id;

    return redis.incr(key)

    }

    开发提示:防作弊,按照不同维度计数,数据持久化到底层数据源

    3 共享Session

     

    4 限速

     

    1

    2

    3

    4

    5

    6

    7

    8

    9

    phoneNum="13800000000";

    key="shortMsg:limit:"+phoneNum;

     

    isExists=redis.set(key,1,"EX 60",NX);

    if(isExists !=null ||redis.incr(key)<=5){

    通过

    }else{

    限速

    }

    某一些网站限制一个ip地址不能在一秒钟之内访问超过n次也可以采用类似的思路

    2.3 哈希

    哈希类型是指键值本身又是一个键值对结构

    2.3.1 命令

    1 设置值

    hset key field value

    2 获取值 hget key field

    3 删除field hdel key field

    4 计算field的个数 hlen key

    5 批量设置或获取field-value hmget key field hmset key field value 

    6 判断field是否存在 hexists key field

    7 获取所有field hkeys key 

    8 获取所有的value hvals key

    9 获取所有的field-value hgetall key

    开发提示:如果一定要获取全部的field-value,可以使用hscan命令,该命令会渐进式遍历哈希类型

    10 hincrby hincrby float

    11 计算value的字符串长度 hstrlen key field

    2.3.2 内部编码

    内部编码有两种:

    ziplist(压缩列表) 哈希元素个数<hash-max-ziplist-entries,所有值<hash-max-ziplist-value配置时,Redis会使用ziplist作为hash的内部实现,ziplist使用更加紧凑的结构实现多个元素存储,节省内存方面比hashtable更加优秀

    hashtable(哈希表) 当hash类型无法满足ziplist 条件时,选择,因为hashtable的读写时间度为O(1)

    2.3.3 使用场景

     

     

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    UserInfo getUserInfo(long id){

    userRedisKey="user:info:"+id;

    userInfoMap=redis.hgetAll(userRedisKey);

    userInfoMap userInfo;

     

    if(userInfoMap!=null){

    userInfo=transferMapToUserInfo(userInfoMap);

    }else{

    userInfo=mysql.get(id);

    redis.hmset(userRedisKey,tranferUserInfoToMap(userInfo));

    redis.expire(userRedisKey,3600);

    }

    return userInfo;

    }

    哈希类型和关系型数据库两点不同:

    1 哈希类型是稀疏的,而关系型数据库是完全结构化的

    2 关系型数据库可以做复杂的查询,而Redis去模拟关系型复杂查询开发困难,维护成本高

    三种方法缓存用户信息

    1 原声字符串类型:每个属性一个键

     

    优点:简单直观,每个属性都支持更新操作

    缺点:占用过多的键,内存占用量较大,同时用户信息内聚性比较差,所以一般不会在生产环境用

    2 序列化字符串类型:将用户信息序列化后用一个键保存

     

    优点:简化编程,如果合理的使用序列化可以提高内存的使用效率

    缺点:序列化和反序列化有一定的开销,同时每次更新属性,都需要把数据取出来反序列化,更新后再序列化到Redis中

    3 哈希类型:每个用户属性使用一对field-value,但是只用一个键保存

    优点:简单直观,如果使用合理,可以减少内存空间的使用

    缺点:要控制哈希在ziplist和hashtable两种内部编码的转换,hashtable会消耗更多的内存

    2.4 列表

    列表类型用来存储多个有序的字符串,一个列表最多存储2的32次方-1个元素,列表是一种比较灵活的数据结构,它可以灵活的充当栈和队列的角色,在实际开发上有很多应用场景

    列表有两个特点:第一、列表中的元素是有序的,这就意味着可以通过索引下标获取某个元素或者某个范围内的元素列表。第二、列表中的元素可以是重复的

    2.4.1 命令

    1 添加操作

    1.1 从右边往左插入元素 rpush key value

    1.2 从左往右插入元素 lpush key value

    1.3 向某个元素前或者后插入元素 linsert key before|after pivot value

     

    2 查找

    1 获取指定范围内的元素列表 lrange key start end 

    索引下标有两个特点:第一,索引下标从左到右分别是0-n-1,从右到左是-1--n,第二,lrange的end选项包含了自身,这个和很多编程语言不包含end不太相同

    2 获取列表指定索引下标的元素 lindex key index

    3 获取列表长度 llen key

    3 删除

    1 从列表左侧弹出元素 lpop key

    2 从列表右侧弹出 rpop key

    3 删除指定元素 lrem key count value

    4 按照索引范围修剪列表 ltrim key start end

    4 修改

    修改指定索引下标的元素 lset key index newValue

    5 阻塞操作 brpop blpop key timeout

    1 列表为空:如果timeout=3,那么客户端要等到3s后返回,如果timeout=0,客户端则阻塞等下去,如果添加了数据,客户端立刻返回

    2 列表不为空:客户端立即返回

    2.4.2 内部编码

    列表类型的内部编码有两种

    ziplist(压缩列表):当列表元素个数<list-max-ziplist-entries,同时list-max-ziplist-value(64字节),Redis会选用列表的内部实现来减少内存的使用

    linkedlist(链表) 当列表类型无法满足ziplist的条件时,Redis会使用linkedlist作为列表的内部实现

    2.4.3 使用场景

    1 消息队列 

    Redis的lpush+brpop命令组合即可实现阻塞队列

     

    2 文章列表 

    两个问题:第一,如果每次分页获取的文章个数较多,需要执行多次hgetall操作,此时考虑使用pipeline批量获取,或者考虑将文章数据序列化为字符串类型,使用mget批量获取。第二,分页获取文章列表时,lrange命令在列表两端性能较好,但是如果列表较大,获取列表中间范围元素的性能会变差,此时可以考虑二级拆分

    开发提示:

    lpush+lpop=Stack(栈)

    lpush+rpop=Queue(队列)

    lpsh+ltrim=Capped Collection(有限集合)

    lpush+brpop=Message Queue(消息队列)

    2.5 集合

    集合用来保存多个字符串元素,和列表不同的是不允许有重复元素,并且集合中元素是无序的

    2.5.1 命令

    1 集合内操作

    1.1 添加元素 sadd key element 

    1.2 删除元素 srem key element

    1.3 计算元素个数 scard key 

    1.4 判断元素是否在集合中 sismember key element

    1.5 随机从集合返回指定个数元素 srandmember key 

    1.6 从集合随机弹出元素 spop key

    1.7 获取所有元素 smembers key

    2 集合间操作

    1 求多个集合的交集 sinter key ...

    2 求多个集合的并集 suinon key..

    3 求多个集合的差集 sdiff key ..

    4 将交集、差集、并集结果保存

    sinterstore destination key 

    sdiffstore destination key 

    suionstore destionation key

     

    2.5.2 内部编码

    集合类型的内部有两种:

    intset(整数集合):当集合中的元素都是整数且元素个数小于set-max-intset-entries配置(默认512个)时,Redis会选用intset来作为集合内部的实现,从而减少内存的使用

    hashtable(哈希表) 当集合类型无法满足intset的条件时,Redis会使用hashtable作为集合的内部实现

    2.5.3 使用场景

    集合类型比较典型的应用场景是标签。

    1 给用户添加标签

    sadd user:1:tags tag1 tag2

    2 给标签添加用户 

    sadd tag1:users user:1 user:3

    开发提示:用户和标签的关系维护应该在一个事务内执行,防止部分命令失败造成的数据不一致

    3 删除用户下的标签

    srem user:1:tags tag1 tag5

    4 删除标签下的用户

    srem tag1:users user:1

    5 计算用户共同感兴趣的标签

    sinter user:1 tags user:2 tags

    开发提示:sadd=Tagging(标签) spop/srandmember=Random item(生成随机数,比如抽奖)

    spop/srandmember=Random item(生成随机数,比如抽奖) sadd+sinter=Social Graph(社交需求)

    2.6 有序集合

    有序集合就是在集合之上加了个score作为排序的依据 

     

    2.6.1 命令

    1 集合内

    1添加成员 zadd key score memeber

    nx xx ch 返回此次操作后,有序集合元素和分数发生变化的个数,incr:对score做增加

    有序集合相比集合提供了排序字段,但是也产生了代价,zadd的时间复杂度为O(log(n)),sadd的时间复杂度为O(1)

    2 计算成员个数

    scard key

    3 计算某个成员的分数 zscore key member

    4 计算成员的排名 zrank key member

    5 删除成员 zrem key member

    6 增加成员的分数 zincrby key increment member

    7 返回指定排名范围的成员 zrange key start end

    8 返回指定分数范围的成员 zrangebysore key min max 

    9 返回指定分数范围成员个数 zcount key min max

    10 删除指定排名内的升序元素 zremrangebyrank key start end

    11 删除指定分数范围的成员 zremrangebyscore key min max

    2 集合间的操作

    1 交集 zinterstore destination numkeys key 

    2 并集 zunionstore destionation numkeys key

    2.6.2 内部编码

    有序集合类型的内部编码有两种:

    ziplist(压缩列表) 当有序集合的元素个数小于zset-max-ziplist-entries配置,同时每个元素的值都小于zset-max-ziplist-value配置时,Redis会用ziplist来作为有序集合的内部实现,ziplist可以有效的减少内存的使用

    skiplist(跳跃表) 当ziplist条件不满足时,有序集合会使用skiplist作为内部实现,因此此时ziplist的读写效率会下降

    2.6.3 使用场景

    有序集合比较典型的使用场景是排行榜系统。例如视频网站需要对用户上传的视频做排行榜榜

    1 添加用户赞数 zdd user:ranking:2016_03_15 mike 3

    之后 zincrby user:ranking:2016_03_15 mike 1

    2 取消用户赞数

    zrem user:rank:2016_03_15 mike

    3 展示获取赞数最多的十个用户

    zrevrangebyrank user:ranking:2016_03_15 0 9

    4 展示用户信息以及用户分数

    此功能可以将用户名作为键后缀,将用户信息保存在哈希类型中,至于用户的分数和排名可以使用zcore和zrank两个功能 

     

    2.7 键管理

    2.7.1 单个键管理

    1 键重命名 rename key newkey

    2 随机返回一个键 randomkey

    3 键过期 -1 键没有设置过期时间 -2 键不存在

    expire key seconds:键在seconds秒后过期

    expire key itmestamp 键在秒级时间戳timestamp后过期

    1 如果expire key的键不存在,返回结果为0

    2 如果过期时间为负值,键会立即被删除,就如使用使用del命令一样

    3 persist 命令可以将键的过期时间清除

    4 对于字符串类型键,执行set命令会去掉过期时间,这个问题很容易在开发中被忽视

    5 Redis不支持二级数据结构内部元素的过期功能,例如不能这列表类型的一个元素做过期时间设置

    6 setex命令作为set+expire组合,不但原子执行,同时减少了网络通讯的时间

    4 迁移键

    迁移键功能非常重要,有move、dump+restore、migrate三组迁移键的方法,它们的实现方式以及使用场景不太相同

    1 move 用于在Redis内部进行数据迁移

    2 dump+restore 实现在不同的Redis实例之间进行数据迁移的功能,这个迁移分两步

    1 在源Redis上,dump命令会将键值序列化,格式采用的是RDB格式

    2 在目标Redis上,restore命令将上面的序列化的值进行复原,其中ttl参数代表过期时间

    3 migrate 命令用于在Redis实例间进行数据迁移的

    2.7.2 遍历键

    Redis提供了两个命令遍历所有的键分别是keys和scan

    1 全量遍历键 keys pattern

    * 代表匹配任意字符

    .代表匹配一个字符

    [] 代表匹配一个字符

    \x用来转义,例如要匹配星号,问号需要进行转义

    大量容易造成阻塞

    2 渐进式遍历

     

    scan可以想象成只扫描一个字典中的一部分键,直到将字典中所有键遍历完毕

    对应的命令还有hsan、sscan、zcan

    渐进式遍历可以有效解决keys命令可能产生的阻塞问题,在有增删的时候,新来的键无法保证遍历到

    2.7.3 数据库管理

    1 切换数据库 select dbIndex

    2 flushdb/flushall 用于清除数据库 数据多的时候会出现阻塞

    2.8 本章终点回顾

    相关推荐:

    Redis数据结构

    以上就是 5种Redis数据结构详解的详细内容,更多请关注php中文网其它相关文章!

    展开全文
  • hashmap数据结构详解(一)之基础知识奠基 hashmap数据结构详解(二)之走进JDK源码 hashmap数据结构详解(三)之hashcode实例及大小是2的幂次方解释 hashmap数据结构详解(四)之hashmap过程综述 hashmap数据...
  • hashmap数据结构详解(一)之基础知识奠基 hashmap数据结构详解(二)之走进JDK源码 hashmap数据结构详解(三)之hashcode实例及大小是2的幂次方解释 hashmap数据结构详解(四)之hashmap过程综述 hashmap数据...
  • 在提到数据结构和非数据结构时,好多人都有这样的意识,概念可能说不上来,接下来就来说说结构化数据和非结构化数据的概念以及不同:结构化数据、非结构化数据是对存储形式的一种数据类型分析,有助于企业细分行业...
  • hashmap数据结构详解(一)之基础知识奠基 hashmap数据结构详解(二)之走进JDK源码 hashmap数据结构详解(三)之hashcode实例及大小是2的幂次方解释 hashmap数据结构详解(四)之hashmap过程综述 hashmap数据...
  • Redis内部数据结构详解(1)

    千次阅读 2018-01-10 10:36:37
    Redis内部数据结构详解(1)——dict 如果你使用过Redis,一定会像我一样对它的内部实现产生兴趣。《Redis内部数据结构详解》是我准备写的一个系列,也是我个人对于之前研究Redis的一个阶段性总结,着重讲解Redis在...
  • 通过上节我们知道,数据结构是学习数据存储方式的一门学科,那么,数据存储方式有哪几种呢?本节将对数据结构的学习内容做一个简要的总结。 数据结构大致包含以下几种存储结构: 线性表,还可细分为顺序表、链表、栈...
  • hashmap数据结构详解(一)之基础知识奠基 hashmap数据结构详解(二)之走进JDK源码 hashmap数据结构详解(三)之hashcode实例及大小是2的幂次方解释 hashmap数据结构详解(四)之hashmap过程综述 hashmap数据...
  • Redis内部数据结构详解(1)——dict 2016-05-31 如果你使用过Redis,一定会像我一样对它的内部实现产生兴趣。《Redis内部数据结构详解》是我准备写的一个系列,也是我个人对于之前研究Redis的一个阶段性总结,...
  • Redis内部数据结构详解(5)——quicklist

    千次阅读 2018-08-25 19:34:04
    本文是《Redis内部数据结构详解》系列的第五篇。在本文中,我们介绍一个Redis内部数据结构——quicklist。Redis对外暴露的list数据类型,它底层实现所依赖的内部数据结构就是quicklist。 我们在讨论中还会涉及到两...
  • Redis内部数据结构详解(6)——skiplist 2016-10-05本文是《Redis内部数据结构详解》系列的第六篇。在本文中,我们围绕一个Redis的内部数据结构——skiplist展开讨论。Redis里面使用skiplist是为了实现sorted set...
  • Redis内部数据结构详解(4)——ziplist

    千次阅读 2018-01-10 10:49:04
    本文是《Redis内部数据结构详解》系列的第四篇。在本文中,我们首先介绍一个新的Redis内部数据结构——ziplist,然后在文章后半部分我们会讨论一下在robj, dict和ziplist的基础上,Redis对外暴露的hash结构是怎样...
  • java 数据结构详解

    2019-12-17 18:09:16
    前文 :数据结构基础 常见集合 Collection接口 Collection派生出三个子接口,Set代表不可重复的无序集合、List代表可重复的有序集合、Queue是java提供的队列实现。 Collection提供了很多的基础方法,供它的...
  • Redis内部数据结构详解(6)——skiplist

    千次阅读 2018-01-10 10:50:48
    本文是《Redis内部数据结构详解》系列的第六篇。在本文中,我们围绕一个Redis的内部数据结构——skiplist展开讨论。 Redis里面使用skiplist是为了实现sorted set这种对外的数据结构。sorted set提供的操作非常...
  • Redis内部数据结构详解之字典dict  对于redis的Dict(字典),虽说算法上跟市面上一般的Dict实现没有什么区别,但是redis的Dict有2个特殊的地方那就是它的rehash(重新散列)和它的字典节点单向链表。 以下是dict...
  • 本文是《Redis内部数据结构详解》系列的第五篇。在本文中,我们介绍一个Redis内部数据结构——quicklist。Redis对外暴露的list数据类型,它底层实现所依赖的内部数据结构就是quicklist。 我们在讨论中还会涉及到两...
  • hashmap数据结构详解(一)之基础知识奠基 hashmap数据结构详解(二)之走进JDK源码 hashmap数据结构详解(三)之hashcode实例及大小是2的幂次方解释 hashmap数据结构详解(四)之hashmap过程综述 hashmap数据...
  • 树状数组 数据结构详解与模板(可能是最详细的了)

    万次阅读 多人点赞 2018-06-25 08:49:41
    目录 转载请注明出处:bestsort.cn 树状数组基础 单点更新: 区间查询: 高级操作 求逆序对 操作 原理 求区间最大值 区间修改+单点查询 查询 修改 区间修改+区间查询 ...树状数组是一个...
  • 本文是《Redis内部数据结构详解》系列的第二篇,讲述Redis中使用最多的一个基础数据结构:sds。 不管在哪门编程语言当中,字符串都几乎是使用最多的数据结构。sds正是在Redis中被广泛使用的字符串结构,它的全称...
  • 首页 > 服务器架构 > 栏目 2019 2019-02-07» Redis源码从哪里读起? 2018 2018-01-22» 漫谈分布式系统、拜占庭将军问题与区块链 2017 2017-02-24» 基于...2016-11-22» Redis内部数据结构详解(7)——in...
  • 本文是《Redis内部数据结构详解》系列的第七篇。在本文中,我们围绕一个Redis的内部数据结构——intset展开讨论。 Redis里面使用intset是为了实现集合(set)这种对外的数据结构。set结构类似于数学上的集合的概念...
  • HBase数据结构详解

    2020-06-28 08:41:33
    RowKey 与nosql数据库们一样,RowKey是用来检索记录的主键。访问HBASE table中的行,只有三种方式: 通过单个RowKey访问(get) 通过RowKey的range(正则)(like) 全表扫描(scan) RowKey行键 (RowKey)可以是任意字符串...
  • Redis数据结构详解

    2018-07-28 11:28:42
    valueObject通用结构 string 基本操作 内存结构 SDS结构 buf 的扩容与缩容 字节串与字符串 SDS编码的优化 使用场景 List 基本操作 内存结构