数据结构的一些问题
in 学习笔记 with 0 comment

数据结构的一些问题

in 学习笔记 with 0 comment

关于栈

栈的数据结构如下所示:

typedef struct{
  int *top;
  int *base;
  int StackSzie;
}SqList;

其中要注意的是,若使用以下方法构造栈、压栈、删除栈中元素

typedef int Status;

Status InitStack(SqStack &S) {    //构造栈
    S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));  //申请存储空间
    if (!S.base) exit(OVERFLOW);  //如果申请失败
    S.top = S.base;
    S.StackSize = STACK_INIT_SIZE;
    return OK;
}
Status Push(SqStack &S, SElemType e) {
    //插入元素e为新的栈顶元素
    if (S.top - S.base >= S.StackSize) {//栈满,追加申请空间
        S.base = (SElemType *)realloc(S.base, (S.StackSize + STACKINCREMENT) * sizeof(SElemType));
        if (!S.base) exit(OVERFLOW);
        S.top = S.base + S.StackSize;
        S.StackSize += STACKINCREMENT;
    }
    *S.top = e;
    S.top++;
    return OK;
}
Status Pop(SqStack &S) {
    //若栈不空,则删除栈顶元素并返回OK,否则返回ERROR
    if (S.top == S.base) return ERROR;
    --S.top;
    return OK;
}

S.top指向的是压栈元素的后一项,是一个“空的空间”,如下图所示:
S.top指向图示
所以在输出栈元素的时候,要将S.top-1才能正常输出,否则输出结果会多一个“内存地址”。在S.top-1的情况下,在使用while循环时,若用S.top!=S.base做条件,循环次数会比栈中元素个数少一次(因为S.top=S.base时就退出循环了即最后一个元素没有输出),所以在后面还要再加一句while中的输出语句:

printf("%d",*S.top);

如果目的不是输出栈中元素而是仅仅想用栈中元素的个数来作为循环次数,可以不将S.top-1。

有无typedef的区别

typedef struct{
    ...
}example;

声明的时候直接用以下方法声明:

example a;

若没有则需要用以下方法声明:

struct example a;

结构体的构造使用 .与->的不同

简单来说,“.”是给结构体成员赋值,“->”是给结构体指针赋值。以以下结构体为例:

typedef struct{
    String name;
    int id;
    String sex;
    int classid;
}Student;

如果我们直接声明一个结构体a,然后我们给a赋值,一般用“a.name、a.id、a.sex”这种方式,例如

Student a;
a.name="Bob";
a.id=00001;
a.sex="男";
a.classid=2;

但是如果我们要将结构体声明为指针的话,则需要用“->”方式对其赋值,如

Student *b;
b->name="Joy";
b->id=00000;
b->sex="女";
b->classid=4;
Responses