数据结构的总结归纳之——栈

waitwolf

2019-10-25

今天开启数据结构学习的第一章节。

说到数据结构，必须要提的便是结构体了，结构体构建了高级数据结构的框架，在C语言中，结构体(struct)指的是一种数据结构，是C语言中聚合数据类型(aggregate data type)的一类。结构体可以被声明为变量、指针或数组等，用以实现较复杂的数据结构。结构体同时也是一些元素的集合，这些元素称为结构体的成员(member)，且这些成员可以为不同的类型，成员一般用名字访问。

关于结构体，分别有如下几个知识点：定义声明结构体，初始化，访问结构体的成员，结构作为函数的参数，指向结构的指针，还有位域（相对不常用）。下面分别对几个知识点进行复习：

1.定义声明结构体。　

struct Books
{
   char  title[50];
   char  author[50];
   char  subject[100];
   int   book_id;
} book;

Books为结构体的标签，book为结构变量。

结构体里面，可以包含其他结构体，也可以包含指向自己的结构体。用于构建复杂的数据结构。

2.结构体的初始化。　　

struct Books
{
   char  title[50];
   char  author[50];
   char  subject[100];
   int   book_id;
} book = {"C 语言", "RUNOOB", "编程语言", 123456};

3.访问成员。

可以用“.”进行访问。如上面book结构体，可以用book.book_id进行访问。

4.结构作为函数参数。

可以把结构作为函数参数，传参方式与其他类型的变量或指针类似。

5.指向结构的指针。

struct Books* S_pointer;

使用指针访问结构体成员：必须用到“->”运算符

//实例： 1 #include <stdio.h>
#include <string.h>
 
struct Books
{
   char  title[50];
   char  author[50];
   char  subject[100];
   int   book_id;
};
 
/* 函数声明 */
void printBook( struct Books *book );
int main( )
{
   struct Books Book1;        /* 声明 Book1，类型为 Books */
   struct Books Book2;        /* 声明 Book2，类型为 Books */
 
   /* Book1 详述 */
   strcpy( Book1.title, "C Programming");
   strcpy( Book1.author, "Nuha Ali"); 
   strcpy( Book1.subject, "C Programming Tutorial");
   Book1.book_id = 6495407;
 
   /* Book2 详述 */
   strcpy( Book2.title, "Telecom Billing");
   strcpy( Book2.author, "Zara Ali");
   strcpy( Book2.subject, "Telecom Billing Tutorial");
   Book2.book_id = 6495700;
 
   /* 通过传 Book1 的地址来输出 Book1 信息 */
   printBook( &Book1 );
 
   /* 通过传 Book2 的地址来输出 Book2 信息 */
   printBook( &Book2 );
 
   return 0;
}
void printBook( struct Books *book )
{
   printf( "Book title : %s\n", book->title);
   printf( "Book author : %s\n", book->author);
   printf( "Book subject : %s\n", book->subject);
   printf( "Book book_id : %d\n", book->book_id);
}

5.位域（由于不常用，就不写了）

经过结构体知识的梳理，下面开始研究栈。

栈（堆栈），百度词条里面的解释是：限定仅在表尾进行插入和删除操作的线性表（是n个具有相同特性的数据元素的有限序列，元素具有一对一关系）。

为了更好的学习，我把堆栈有关的代码全部贴出来：

typedef int ElemType;//自定义类型

typedef struct
{
    ElemType Element[MaxSize];
    int Top;
} SeqStack;

void Init_SeqStack(SeqStack* S_pointer)//创建空栈
{
    S_pointer->Top = -1;
}


bool  Full_SeqStack(SeqStack* S_pointer)//判断栈满
{
    if (S_pointer->Top ==MaxSize -1) return true;
    else return false;
}

bool Empty_SeqStack(SeqStack* S_pointer)//判断栈空
{
    if (S_pointer->Top == -1) return true;
    else return false;
}

bool Push_SeqStack(SeqStack* S_pointer, ElemType x)//进栈
{
    if (Full_SeqStack(S_pointer) == true)
        return Overflow;
    else
    {
        S_pointer->Top++;
        S_pointer->Element[S_pointer->Top] = x;
        return OK;
    }
}

void SetNull_SeqStack(SeqStack* S_pointer)//清空栈
{
    S_pointer->Top = -1;
}

bool Pop_SeqStack(SeqStack* S_pointer, ElemType* x_pointer)//出栈
{
    if (Empty_SeqStack(S_pointer) == true)
        return Underflow;
    else
    {
        *x_pointer = S_pointer->Element[S_pointer->Top];

        S_pointer->Top--;
        return OK;
    }
}

附上一道经典例题：十进制转换八进制。

void conversion(int Num)
{
    int temp;
    SeqStack ListStack;//定义一个顺序栈
    Init_SeqStack(&ListStack);//创建空栈
    while (Num) {//Num不为0时
        Push_SeqStack(&ListStack, Num % 8);//压入Num%8
        Num = Num / 8;//Num取整
    }
    while (Empty_SeqStack(&ListStack) == false)//栈不为空时
    {
        Pop_SeqStack(&ListStack, &temp);//退栈
        printf("%d", temp);//显示栈顶元素
    }
    SetNull_SeqStack(&ListStack);//清空栈

}

int main()
{
    int Num;
    printf_s("Please input a number:\n");
    scanf_s("%d", &Num);
    conversion(Num);
    return 0;
}

这题本身还有更简单的解法，为了学习栈，我大材小用了。

//解法2：
#include<stdio.h>
#define MaxSize 1001
int main()
{
    int Numb, temp,count=0,i = 0;;
    scanf_s("%d", &Numb);
    int Num[MaxSize];
    while (Numb) { temp = Numb % 8;  Num[i] = temp; i++; Numb = Numb / 8; count++; }
    for (int j = count-1; j >= 0; j--)
        printf_s("%d", Num[j]);
    printf_s("\n");
    return 0;
}

以上，便是今天我学习的内容了。

数据结构结构体类型