数据结构

#数据结构| 来源: 网络整理| 查看: 265

i. 栈与队列和线性表联系

栈和队列同属于线性结构，都是线性表。但是插入和删除操作只能在一端进行的叫做栈——“后进先出”；插入操作在一端进行、删除操作在另一端进行叫做队列——“先进先出”。

栈的基本概念 i. 栈与队列和线性表联系1.栈的定义2.栈的顺序存储结构3.顺序栈的基本操作实现3.1.顺序栈的初始化操作3.2.顺序栈的判断栈空操作3.3.顺序栈的获取栈顶元素操作3.4.顺序栈的求长度操作3.5.顺序栈的进栈操作3.6.顺序栈的出栈操作3.7.顺序栈的遍历操作 4.栈的链式存储结构5.链栈的基本操作实现5.1.链栈的初始化操作5.2.链栈的判断空操作5.3.链栈的获取栈顶元素操作5.4.链栈的求长度操作5.5.链栈的进栈操作5.6.链栈的出栈操作5.7.链表的遍历操作

1.栈的定义

栈的是一种特殊的线性表，限定插入和删除操作只能在一端进行，具有后进先出的特点。其中栈顶是允许插入和删除的一端；栈顶则是不允许插入和删除的一端。

入栈push 出栈pop

栈的抽象数据类型描述如下。

数据对象：D={ai|ai∈ElemSet，i=1,2……，n，n>=0} 数据关系：R={|ai-1,ai∈D，i=2，……，n}，约定an端为栈顶，a1端为栈底基本操作：初始化操作：InitStack（&S）；销毁栈结构：DestroyEmpty（S）；判断栈是否为空：StackEmpty（S）；获取栈顶：GetTop（S，&e）；清空栈：CleaerStack（&S）；求栈的长度：StackLength（S）；进栈：Push（&S，e）；出栈：Pop（&S，&e）；遍历：StackTravers（S）

2.栈的顺序存储结构

栈的存储结构主要有顺序栈和链栈两种。栈的顺序结构存储是指用一片连续的空间存放栈的数据元素，称为顺序栈。由于对顺序栈的操作限制在栈顶，因此因此需要已知栈顶的位置。为了防止溢出，需要已知栈的容量。存储数据元素需要一片连续的空间，因此顺序栈是一个结构体类型的变量，用C语言描述顺序栈类型有两种方法。一个是数组类型，一个是指向数组的指针类型。

3.顺序栈的基本操作实现 3.1.顺序栈的初始化操作

分析：初始化操作是给顺序栈类型变量S的三个成员赋值。第一成员的值是动态申请得到的一片连续空间的首地址；第二个成员的值为-1（表示栈空）；第三个成员的值是申请空间的容量。

初始化操作使得S的成员被改变，申请一片连续的空间需要知道空间的大小。【算法】

int initSqStack(SqStack* LS, int max) { LS->data = (SElemType*)malloc(max * sizeof(SElemType)); if (LS->data == NULL) { perror("initSqStack::"); return 0; } LS->top = -1; LS->stackSize = max; return 1; } 3.2.顺序栈的判断栈空操作

分析：要想判断是否为空，只要判断S.top是否为-1即可。【算法】

int EmptySqStack(SqStack S) { if (S.top == -1) { return 1; } else { return 0; } } 3.3.顺序栈的获取栈顶元素操作

分析：如果栈为空，不存在栈顶元素，否则下标S.top 【算法】

int GetTopSqStack(SqStack S, int* e) { if (S.top == -1) { return 0; } *e = S.data[S.top]; return 1; } 3.4.顺序栈的求长度操作

【算法】

int LengthSqStack(SqStack S) { if (S.top == -1) { return 0; } else { return S.top + 1; } } 3.5.顺序栈的进栈操作 int PushSqStack(SqStack* LS, int e) { if (LS->stackSize == LS->top + 1) { return 0; } LS->data[++LS->top] = e; return 1; } 3.6.顺序栈的出栈操作 int PopSqStack(SqStack* LS, int* e) { if (LS->top == -1) { return 0; } *e = LS->data[LS->top--]; return 1; } 3.7.顺序栈的遍历操作 int TraversSqStack(SqStack S) { int k; if (S.top == -1) { printf("栈空！\n"); return 0; } for (int k = S.top; k >= 0; k--) { printf("%5d", S.data[k]); } printf("\n"); return 1; } 4.栈的链式存储结构

typedef struct snode { SElemType data; struct snode* next; }SNode,*LinkStack;

5.链栈的基本操作实现 5.1.链栈的初始化操作 LinkStack S； S=NULL; 5.2.链栈的判断空操作 if(S==NULL) printf("空栈\n"); 5.3.链栈的获取栈顶元素操作

分析：因为链栈的头指针指向栈顶，所以栈顶元素是S->data。如果栈为空，则不存在栈顶元素。

int GetTopStack(LinkStack S, int* e) { if (S == NULL) { return 0; } *e = S->data; return 1; } 5.4.链栈的求长度操作 int LengthLinkStack(LinkStack S) { int n = 0; while (S) { n++; S = S->next; } return n; } 5.5.链栈的进栈操作

分析：就是链表的头插法

int PushLinkStack(LinkStack* LS, int e) { LinkStack p = (LinkStack)malloc(sizeof(SNode)); if (p == NULL) { perror("PushLinkStack::"); return 0; } p->data = e; p->next = *LS; *LS = p; return 1; } 5.6.链栈的出栈操作

分析：就是链表的头删操作

int PopLinkStack(LinkStack* LS, int* e) { LinkStack p = *LS; if (*LS == NULL) { return 0; } *LS = (*LS)->next; *e = p->data; free(p); return 1; } 5.7.链表的遍历操作 int TraversLinkStack(LinkStack S) { if (S == NULL) { printf("栈空！\n"); return 0; } while (S) { printf("%5d", S->data); S = S->next; } printf("\n"); return 1; }

【本文地址】

数据结构

数据结构

今日新闻

推荐新闻