17网络《数据结构》课程相关事项列表-白红宇

17网络《数据结构》课程相关事项列表

阅读量：4606 次

发布时间：2019-06-09

本文共 4686 字，大约阅读时间需要 15 分钟。

网络工程1-2班《数据结构》上机安排：如课表

http://www.cnblogs.com/4bytes/p/3664941.html

网上课程：

麻省理工学院公开课：算法导论

http://open.163.com/special/opencourse/algorithms.html

浙江大学《数据结构》，需要注册

http://www.icourse163.org/course/ZJU-93001

清华大学《数据结构》，需要注册

http://www.xuetangx.com/courses/course-v1:TsinghuaX+30240184X+sp/about

刷数据结构题好的站点：

https://leetcode.com/

https://www.nowcoder.com/kaoyan

实验要注意的问题：

1. OJ提交编译器要用C++编译器，不能用C。

2.自己实现书上的算法所有的局部变量要自己定义并初始化。例如算法3.8，需要如下的代码

void conversion ( ) {

//对于输入的任意一个非负十进制数，打印输出与其等值的八进制数

LinkStack S;

int N,e;

InitStack(S); //构造空栈

3. 数据结构里面的SElemType要指定一个确定类型

typedef int SElemType;

typedef struct{

SElemType *base;

SElemType *top;

int stacksize;

}SqStack;

4. 对于多组数据的情况，要注意对象的释放。有两种典型的做法。

做法一：针对每组数据，定义一个对象（如栈），初始化后使用，最后销毁，示例如下

Sqstack S;

InitStack(s);

使用栈

DestroyStack(s); // 这里忘掉会导致memory leak

做法二：定义一个全局对象，然后针对每一组数据，使用对象，然后清空；最后再销毁。这种做法从效率上说要高一些。示例如下

Sqstack S; //全局对象

int main(void)

{

　 int T;

InitStack(s);

cin >> T;

while(T--){

使用栈

ClearStack(S);

}

　　DestroyStack(s);

}

完整示例：

问题 C: 算法3-1：八进制数

方法一：

/***链栈实现数制的转换***/#include
     
      using namespace std;#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;typedef struct SNode{    int data;    struct SNode *next;}SNode,*LinkStack;Status InitStack(LinkStack &S){    S = NULL;    return OK;}bool StackEmpty(LinkStack S){    if(!S)        return true;    return false;}Status Push(LinkStack &S,int e){    SNode *p = new SNode;    if(!p)    {        return OVERFLOW;    }    p->data = e;    p->next = S;    S = p;    return OK;}Status Pop(LinkStack &S,int &e){    SNode *p;    if(!S)        return ERROR;    e = S->data;    p = S;    S = S->next;    delete p;    return OK;}void ClearStack(LinkStack &S){    SNode *p;    while(S){
    　　　　 p = S;        S = S->next;        delete p;    }}void DestroyStack(LinkStack &S){    ClearStack(S);}//算法3.8　数制的转换(链栈实现)void conversion (int N) {   //对于输入的任意一个非负十进制数，打印输出与其等值的八进制数    LinkStack S;    int e;    InitStack(S); //构造空栈    //cout<<"输入一个非负十进制数:"<
      
       >N){        conversion(N);    }    return 0;}

方法二：

/***链栈实现数制的转换***/#include
     
      using namespace std;#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;typedef struct SNode{    int data;    struct SNode *next;}SNode,*LinkStack;LinkStack S;Status InitStack(LinkStack &S){    S = NULL;    return OK;}bool StackEmpty(LinkStack S){    if(!S)        return true;    return false;}Status Push(LinkStack &S,int e){    SNode *p = new SNode;    if(!p)    {        return OVERFLOW;    }    p->data = e;    p->next = S;    S = p;    return OK;}Status Pop(LinkStack &S,int &e){    SNode *p;    if(!S)        return ERROR;    e = S->data;    p = S;    S = S->next;    delete p;    return OK;}void ClearStack(LinkStack &S){    SNode *p;    while(S){
            p = S;        S = S->next;        delete p;    }}void DestroyStack(LinkStack &S){    ClearStack(S);}//算法3.8　数制的转换(链栈实现)void conversion (int N) {   //对于输入的任意一个非负十进制数，打印输出与其等值的八进制数    int e;    while(N)    {        Push(S,N%8);        N=N/8;    }    //cout<<"与其等值的八进制数是:"<
      
       >N){        conversion(N);        ClearStack(S);    }    DestroyStack(S);    return 0;}

方法三：使用顺序栈的实现

#include
     
      #include 
      
       using namespace std;#define OK 1#define ERROR 0#define OVERFLOW -2#define MAXSIZE  100//顺序栈存储空间的初始分配量typedef int Status;typedef int SElemType;typedef struct {   SElemType *base;//栈底指针   SElemType *top;//栈顶指针   int stacksize;//栈可用的最大容量} SqStack;//算法3.1　顺序栈的初始化Status InitStack(SqStack &S){   //构造一个空栈S   S.base = new SElemType[MAXSIZE];//为顺序栈动态分配一个最大容量为MAXSIZE的数组空间   if(!S.base)      exit(OVERFLOW); //存储分配失败   S.top = S.base; //top初始为base，空栈   S.stacksize = MAXSIZE; //stacksize置为栈的最大容量MAXSIZE   return OK;}bool StackEmpty(SqStack S){   return S.base == S.top;}//算法3.2　顺序栈的入栈Status Push(SqStack &S, SElemType e){   // 插入元素e为新的栈顶元素   if(S.top - S.base == S.stacksize)      return ERROR; //栈满   *(S.top++) = e; //元素e压入栈顶，栈顶指针加1   return OK;}//算法3.3　顺序栈的出栈Status Pop(SqStack &S, SElemType &e){   //删除S的栈顶元素，用e返回其值   if(S.base == S.top)      return ERROR;//栈空   e = *(--S.top); //栈顶指针减1，将栈顶元素赋给e   return OK;}//算法3.4　取顺序栈的栈顶元素char GetTop(SqStack S)  //返回S的栈顶元素，不修改栈顶指针{   if(S.top != S.base)  //栈非空      return *(S.top - 1); //返回栈顶元素的值，栈顶指针不变}void ClearStack(SqStack &S){   S.top = S.base;}void DestroyStack(SqStack &S){   delete []S.base;   S.base = S.top = NULL;   S.stacksize = 0;}//算法3.8　数制的转换(链栈实现)void conversion(int N){   //对于输入的任意一个非负十进制数，打印输出与其等值的八进制数   SqStack S;   int e;   InitStack(S); //构造空栈   //cout<<"输入一个非负十进制数:"<
       
        > N) {      conversion(N);   }   return 0;}