- 前言
- sqStack.cpp(顺序栈)
- linkStack.cpp(链栈)
- 总结
- 参考资料
- 作者的话
数据结构中顺序栈和链栈的C/C++语言描述实现模板,有详细的步骤解析及使用示例。
sqStack.cpp(顺序栈)
//头文件———————————————————— #include//命名空间———————————————————— using namespace std; //宏———————————————————— #define MaxSize 100 //栈的最大大小 //自定义数据类型———————————————————— typedef int ElemType; //数据的(数据)类型 依据数据的实际类型定义 //结构体 //顺序栈 typedef struct SqStack { ElemType data[MaxSize]; //数据 int topPointer; //栈顶指针 //注意:定义为指向栈顶位置而不是栈顶位置的后一位置 //值是索引,取值范围:-1——MaxSize-1,可作为判断栈空和栈满条件 } SqStack; //函数声明———————————————————— void use_example(); //使用示例 void init(SqStack &sqStack); //初始化 bool push(SqStack &sqStack, ElemType elem); //入栈 bool pop(SqStack &sqStack, ElemType &elem); //出栈 //主函数———————————————————— int main() { use_example(); //使用示例 return 0; } //函数定义———————————————————— //使用示例 void use_example() { //创建 SqStack sqStack; //初始化 init(sqStack); cout << sqStack.topPointer << endl; //输出:-1 //入栈 ElemType elem1 = 100; ElemType elem2 = 200; ElemType elem3 = 300; push(sqStack, elem1); push(sqStack, elem2); push(sqStack, elem3); //元素在栈中的排列:100,200,300 //出栈 ElemType elem4 = 0; ElemType elem5 = 0; pop(sqStack, elem4); pop(sqStack, elem5); cout << elem4 << endl; //输出:300 cout << elem5 << endl; //输出:200 return; } //初始化 void init(SqStack &sqStack) //参数:栈 { sqStack.topPointer = -1; //栈顶指针的值,即索引为-1,不存在元素 } //入栈 //时间复杂度:O(1) bool push(SqStack &sqStack, ElemType elem) //参数:栈,元素 { //注意:判断合法条件 if (sqStack.topPointer == MaxSize - 1) //栈满 { return false; } ++sqStack.topPointer; //栈顶指针+1 sqStack.data[sqStack.topPointer] = elem; //元素入栈 return true; } //出栈 //时间复杂度:O(1) bool pop(SqStack &sqStack, ElemType &elem) //参数:栈,元素 { if (sqStack.topPointer == -1) //栈空 { return false; } elem = sqStack.data[sqStack.topPointer]; //获取、保存元素 --sqStack.topPointer; //栈顶指针-1 元素出栈 return true; }
linkStack.cpp(链栈)
//头文件———————————————————— #include//命名空间———————————————————— using namespace std; //自定义数据类型———————————————————— typedef int ElemType; //数据的(数据)类型 依据数据的实际类型定义 //结构体 //链栈结点 typedef struct LinkNode { ElemType data; //数据 struct LinkNode *next; //指针 } LinkNode; //函数声明———————————————————— void use_example(); //使用示例 void init(LinkNode *&head); //初始化 void push(LinkNode *&head, ElemType elem); //入栈 bool pop(LinkNode *&head, ElemType &elem); //出栈 //主函数———————————————————— int main() { use_example(); //使用示例 return 0; } //函数定义———————————————————— //使用示例 void use_example() { //创建 LinkNode *head; //头结点指针 //初始化 init(head); //入栈 ElemType elem1 = 100; ElemType elem2 = 200; ElemType elem3 = 300; push(head, elem1); push(head, elem2); push(head, elem3); //元素在栈中的排列:100,200,300 //出栈 ElemType elem4 = 0; ElemType elem5 = 0; pop(head, elem4); pop(head, elem5); cout << elem4 << endl; //输出:300 cout << elem5 << endl; //输出:200 return; } //初始化 void init(LinkNode *&head) //参数:头结点指针 { head = (LinkNode *)malloc(sizeof(LinkNode)); //创建头结点 头结点指针指向头结点 head->next = nullptr; //头结点的指针指向空 } //入栈 //时间复杂度:O(1) void push(LinkNode *&head, ElemType elem) //参数:头结点指针,元素 { LinkNode *newNode; //新结点指针 newNode = (LinkNode *)malloc(sizeof(LinkNode)); //创建新结点 newNode->data = elem; //初始化新结点的数据 //入栈 newNode->next = head->next; head->next = newNode; } //出栈 //时间复杂度:O(1) bool pop(LinkNode *&head, ElemType &elem) //参数:头结点指针,元素 { if (head->next == nullptr) //栈空 { return false; } LinkNode *tempNode = nullptr; //临时结点指针 elem = head->next->data; //获取、保存数据 //出栈 tempNode = head->next; head->next = tempNode->next; free(tempNode); //释放结点空间 return true; }
总结
不同参考资料中,顺序栈和链栈的描述实现各不相同,但基本思想是一致的。作者使用规范的变量命名、提供详细的步骤解析及使用示例,应用C/C++语言将其整合成模板,以帮助理解记忆。
参考资料
- 《2023版数据结构高分笔记》主编:率辉
- 《2023年计算机组成原理考研复习指导》组编:王道论坛
- 《大话数据结构》作者:程杰
作者的话
- 感谢参考资料的作者/博主
- 作者:夜悊
- 版权所有,转载请注明出处,谢谢~
- 如果文章对你有帮助,请点个赞或加个粉丝吧,你的支持就是作者的动力~
- 文章在描述时有疑惑的地方,请留言,定会一一耐心讨论、解答
- 文章在认识上有错误的地方, 敬请批评指正
- 望读者们都能有所收获