数据结构课程的实践方法指导-阿里云开发者社区

　　有不少人说数据结构课程抽象，学习起来感到困难。有些同学放弃了，有些同学拿出了高中学习时练熟的功夫，强行理解，死记硬背，结果辛苦不少，效果不佳，反倒得到很多枯燥的感受。
　　其实，数据结构课中有不少理论性分析的内容，但对于本科生学习的内容，以及要达到目标，还是以实践性为主的。在学习的方法上做出改变，这门课程就可以展示出生动的实践性味道来。这就要求在学习过程中，将实践学习有效地开展下去，诸多的困境即可以破解。
　　学习数据结构和算法的过程中做出的这些实践，也便成了程序设计能力提高中的重要部分。
　　本文就以数据结构课程开篇的“线性表的顺序存储”部分为例，给出两种实践路线的示例。

一、在一个程序文件中验证算法

　　参考教材中的讲解，我们可以将教材中需要掌握的算法合并成一个程序，让程序在计算上跑起来。在输入、调试、测试的过程中，完成了掌握算法的目的。
　　本文示例基于李春葆老师的《数据结构教程（第4版）》给出，使用其他教材的做法类似：
　　第一步：定义数据的存储结构
　　例如，对于线性结构，可以写下：

#define MaxSize 50    //Maxsize将用于后面定义存储空间的大小
typedef int ElemType;  //ElemType在不同场合可以根据问题的需要确定，在此取简单的int
typedef struct
{
    ElemType data[MaxSize];  //利用了前面MaxSize和ElemType的定义
    int length;
} SqList;

　　第二步：实现各种基本操作
　　例如，对于线性表的顺序存储

//用数组创建线性表
void CreateList(SqList *&L, ElemType a[], int n)
{
    int i;
    L=(SqList *)malloc(sizeof(SqList));
    for (i=0; i<n; i++)
        L->data[i]=a[i];
    L->length=n;
}

//初始化线性表InitList(L)
void InitList(SqList *&L)   //引用型指针
{
    L=(SqList *)malloc(sizeof(SqList));
    //分配存放线性表的空间
    L->length=0;
}

//销毁线性表DestroyList(L)
void DestroyList(SqList *&L)
{
    free(L);
}

//判定是否为空表ListEmpty(L)
bool ListEmpty(SqList *L)
{
    return(L->length==0);
}

//求线性表的长度ListLength(L)
int ListLength(SqList *L)
{
    return(L->length);
}

//输出线性表DispList(L)
void DispList(SqList *L)
{
    int i;
    if (ListEmpty(L)) return;
    for (i=0; i<L->length; i++)
        printf("%d ",L->data[i]);
    printf("\n");
}

//求某个数据元素值GetElem(L,i,e)
bool GetElem(SqList *L,int i,ElemType &e)
{
    if (i<1 || i>L->length)  return false;
    e=L->data[i-1];
    return true;
}

//按元素值查找LocateElem(L,e)
int LocateElem(SqList *L, ElemType e)
{
    int i=0;
    while (i<L->length && L->data[i]!=e) i++;
    if (i>=L->length)  return 0;
    else  return i+1;
}

//插入数据元素ListInsert(L,i,e)
bool ListInsert(SqList *&L,int i,ElemType e)
{
    int j;
    if (i<1 || i>L->length+1)
        return false;   //参数错误时返回false
    i--;            //将顺序表逻辑序号转化为物理序号
    for (j=L->length; j>i; j--) //将data[i..n]元素后移一个位置
        L->data[j]=L->data[j-1];
    L->data[i]=e;           //插入元素e
    L->length++;            //顺序表长度增1
    return true;            //成功插入返回true
}

//删除数据元素ListDelete(L,i,e)
bool ListDelete(SqList *&L,int i,ElemType &e)
{
    int j;
    if (i<1 || i>L->length)  //参数错误时返回false
        return false;
    i--;        //将顺序表逻辑序号转化为物理序号
    e=L->data[i];
    for (j=i; j<L->length-1; j++) //将data[i..n-1]元素前移
        L->data[j]=L->data[j+1];
    L->length--;              //顺序表长度减1
    return true;              //成功删除返回true
}

　　 第三步，编写测试函数，对于每一个基本运算的实现进行测试
　　首先，应该在程序头部加上必要的头文件（如果不加，出现编译错误倒是也会对付）。

#include <stdio.h>
#include <malloc.h>

　　测试函数一般“宜小不宜大”，也就是说，一次尽可能测试尽可能少的基本操作。不过，在必要的时候，也需要调用别的基本操作，用来完成辅助性的工作。例如，下面的main函数，目标是测试创建顺序表的函数CreateList，创建中需要的数组x可以在程序中直接初始化，而创建的结果，希望通过输出进行观察，于是，调用DispList成为必要。
　　用于测试CreateList的测试函数写作：

int main()
{
    SqList *sq;
    ElemType x[6]= {5,8,7,2,4,9};
    CreateList(sq, x, 6);
    DispList(sq);
    return 0;
}

　　再例，测试初始化操作InitList时，可以与插入元素的操作ListInsert一起进行。

int main()
{
    SqList *sq;
    InitList(sq);
    ListInsert(sq, 1, 5);
    ListInsert(sq, 2, 3);
    ListInsert(sq, 1, 4);
    DispList(sq);
    return 0;
}

　　接下来，可以更换测试函数，用于测试别的基本操作。“宜小不宜大”的原则简化了工作的难度，但是可能需要编制多个测试函数，分多次运行，才能将多个测试函数测试完。

二、构建自己的“算法库”

　　数据结构课程的主线就是各种逻辑结构，在不同的存储结构下，基本运算的实现与复杂度分析。这些基本数据结构的定义，以及各种基本运算的实现，可以构成“算法库”。建立起来的算法库，可以作为即将要解决问题时，所依托的“基础设施”。事实上，在工程中用到的系统库，或第三方的算法库，也是将通用的模块集中起来而形成的。
　　为有效地组织，程序将用多文件的方式组织，其中的头文件和提供自定函数实现的文件，组成的就是算法库。
　　对于线性表的顺序存储，算法库的头文件可以定义为：
list.h

#ifndef LIST_H_INCLUDED
#define LIST_H_INCLUDED

#define MaxSize 50
typedef int ElemType;
typedef struct
{
    ElemType data[MaxSize];
    int length;
} SqList;
void CreateList(SqList *&L, ElemType a[], int n);//用数组创建线性表
void InitList(SqList *&L);//初始化线性表InitList(L)
void DestroyList(SqList *&L);//销毁线性表DestroyList(L)
bool ListEmpty(SqList *L);//判定是否为空表ListEmpty(L)
int ListLength(SqList *L);//求线性表的长度ListLength(L)
void DispList(SqList *L);//输出线性表DispList(L)
bool GetElem(SqList *L,int i,ElemType &e);//求某个数据元素值GetElem(L,i,e)
int LocateElem(SqList *L, ElemType e);//按元素值查找LocateElem(L,e)
bool ListInsert(SqList *&L,int i,ElemType e);//插入数据元素ListInsert(L,i,e)
bool ListDelete(SqList *&L,int i,ElemType &e);//删除数据元素ListDelete(L,i,e)#endif // LIST_H_INCLUDED
#endif

　　配套地，在list.cpp中实现这些基本操作。
　　
list.cpp

#include <stdio.h>
#include <malloc.h>
#include "list.h"

//用数组创建线性表
void CreateList(SqList *&L, ElemType a[], int n)
{
    int i;
    L=(SqList *)malloc(sizeof(SqList));
    for (i=0; i<n; i++)
        L->data[i]=a[i];
    L->length=n;
}

//初始化线性表InitList(L)
void InitList(SqList *&L)   //引用型指针
{
    L=(SqList *)malloc(sizeof(SqList));
    //分配存放线性表的空间
    L->length=0;
}

//销毁线性表DestroyList(L)
void DestroyList(SqList *&L)
{
    free(L);
}

//判定是否为空表ListEmpty(L)
bool ListEmpty(SqList *L)
{
    return(L->length==0);
}

//求线性表的长度ListLength(L)
int ListLength(SqList *L)
{
    return(L->length);
}

//输出线性表DispList(L)
void DispList(SqList *L)
{
    int i;
    if (ListEmpty(L)) return;
    for (i=0; i<L->length; i++)
        printf("%d ",L->data[i]);
    printf("\n");
}

//求某个数据元素值GetElem(L,i,e)
bool GetElem(SqList *L,int i,ElemType &e)
{
    if (i<1 || i>L->length)  return false;
    e=L->data[i-1];
    return true;
}

//按元素值查找LocateElem(L,e)
int LocateElem(SqList *L, ElemType e)
{
    int i=0;
    while (i<L->length && L->data[i]!=e) i++;
    if (i>=L->length)  return 0;
    else  return i+1;
}

//插入数据元素ListInsert(L,i,e)
bool ListInsert(SqList *&L,int i,ElemType e)
{
    int j;
    if (i<1 || i>L->length+1)
        return false;   //参数错误时返回false
    i--;            //将顺序表逻辑序号转化为物理序号
    for (j=L->length; j>i; j--) //将data[i..n]元素后移一个位置
        L->data[j]=L->data[j-1];
    L->data[i]=e;           //插入元素e
    L->length++;            //顺序表长度增1
    return true;            //成功插入返回true
}

//删除数据元素ListDelete(L,i,e)
bool ListDelete(SqList *&L,int i,ElemType &e)
{
    int j;
    if (i<1 || i>L->length)  //参数错误时返回false
        return false;
    i--;        //将顺序表逻辑序号转化为物理序号
    e=L->data[i];
    for (j=i; j<L->length-1; j++) //将data[i..n-1]元素前移
        L->data[j]=L->data[j+1];
    L->length--;              //顺序表长度减1
    return true;              //成功删除返回true
}

　　大功告成。如果这些函数的实现还没有经过测试的话，编制main.cpp，在其中写测试函数完成测试工作。
　　例如，为测试CreateList，写
　　
main.cpp

#include "list.h"
int main()
{
    SqList *sq;
    ElemType x[6]= {5,8,7,2,4,9};
    CreateList(sq, x, 6);
    DispList(sq);
    return 0;
}

三、应用数据结构求解问题

　　要实现的内容必定是要基于特定的存储结构，可能利用各基本操作的组合就可以完成，也可能需要在数据结构上，自己设计算法完成。也不排除主要部分是专门设计的算法，但有些环节，也需要基本操作的支持。总之，可以看出，从解决问题的角度，需要综合运用知识了，同时，前面建的算法库，有了用武之地。
　　例如：设顺序表有10个元素，其元素类型为整型。设计一个算法，以第一个元素为分界线，将所有小于它的元素移到该元素的前面，将所有大于它的元素移到该元素的后面。
　　设计出的算法是：

void move1(SqList *&L)
{
    int i=0,j=L->length-1;
    ElemType pivot=L->data[0];
    ElemType tmp;
    while (i<j) 
    {
        while (i<j && L->data[j]>pivot)
            j--;    
        while (i<j && L->data[i]<=pivot)
            i++;    
        if (i<j)
        {
            tmp=L->data[i];
            L->data[i]=L->data[j];
            L->data[j]=tmp;
        }
    }
    tmp=L->data[0]; 
    L->data[0]=L->data[j];
    L->data[j]=tmp;
}

　　为了将其作为一个程序，通过运行观察程序的执行过程，可以写出如下的main.cpp。可以看出，前面编制好的头文件list.h和list.cpp正在支持着这些工作。
　　
main.cpp

#include "list.h"
void move1(SqList *&L)  //定义解决问题的算法
{
    int i=0,j=L->length-1;
    ElemType pivot=L->data[0];
    ElemType tmp;
    while (i<j)
    {
        while (i<j && L->data[j]>pivot)
            j--;
        while (i<j && L->data[i]<=pivot)
            i++;
        if (i<j)
        {
            tmp=L->data[i];
            L->data[i]=L->data[j];
            L->data[j]=tmp;
        }
    }
    tmp=L->data[0];
    L->data[0]=L->data[j];
    L->data[j]=tmp;
}
int main()   //在main函数中调用，保证程序能运行，解决问题
{
    SqList *sq;
    ElemType x[10]= {3, 8, 2, 7, 1, 5, 3, 4, 6, 0};
    CreateList(sq, x, 10);
    DispList(sq);
    move1(sq);
    DispList(sq);
    return 0;
}

程序运行结果：

3 8 2 7 1 5 3 4 6 0
1 0 2 3 3 5 7 4 6 8

四、运行程序，观察算法法过程

　　作为学习算法的过程，建议在需要的时候，通过单步执行的方式，观察程序的执行过程，以此来理解算法的执行细节。例如，下图是上面例子在单步执行过程中的一个截屏。
这里写图片描述
　　很显然，这种将运行过程“可视化”的方式，对于算法的学习而言，是非常有效的。

数据结构课程的实践方法指导

一、在一个程序文件中验证算法

二、构建自己的“算法库”

三、应用数据结构求解问题

四、运行程序，观察算法法过程

热门文章

最新文章

相关课程

相关电子书

相关实验场景

数据结构课程的实践方法指导

一、在一个程序文件中验证算法

二、构建自己的“算法库”

三、应用数据结构求解问题

四、运行程序，观察算法 法过程

热门文章

最新文章

相关课程

相关电子书

相关实验场景

四、运行程序，观察算法法过程