| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 676 人关注过本帖, 1 人收藏
标题:《大话数据结构》读书笔记之栈抽象数据类型(链表实现)
只看楼主 加入收藏
巧若拙
Rank: 4
来 自:宁波余姚
等 级:业余侠客
威 望:1
帖 子:159
专家分:273
注 册:2014-8-24
结帖率:46.15%
收藏(1)
已结贴  问题点数:5 回复次数:2 
《大话数据结构》读书笔记之栈抽象数据类型(链表实现)
/*
    Name: 栈抽象数据类型(使用链表实现)
    Copyright:
    Author: 巧若拙
    Date:13-09-14 19:02
    Description:
*/

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<math.h>

#define MAXSIZE 10
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int ElemType;
typedef int Status; //函数类型,其值是函数结果状态代码,如OK等

typedef struct StackNode{
    ElemType data;//数据域
    struct StackNode *next;//直接后继指针
} StackNode, *LinkStackPtr;

typedef struct LinkStack{
    LinkStackPtr top;//栈顶指针
    int count;//栈元素个数
} LinkStack;

Status InitStack(LinkStack *L);//建立一个空的栈S
Status StackEmpty(LinkStack L);//若栈为空,返回TRUE,否则返回FALSE
Status ClearStack(LinkStack *L);//将栈清空
int StackLength(LinkStack L);//返回栈S的元素个数
Status DisplayStack(LinkStack L);//输出栈S的所有元素
Status GetTop(LinkStack L, ElemType *e);//用e返回栈S的栈顶元素
Status LocateElem(LinkStack L, ElemType e);//在栈S中查找是否存在与给定值e相等的元素
Status Push(LinkStack *L, ElemType e);//在栈S中插入新元素e
Status Pop(LinkStack *L, ElemType *e);//删除栈S的栈顶元素,并将该元素值赋给e  


int main(void)
{
    LinkStack a;
    ElemType *p, e = 0;
    int i;
   
    InitStack(&a);//建立一个空的栈
   
    for (i=0; i<MAXSIZE; i++)
    {
        Push(&a, i+1);//在栈S中插入新元素e
    }
   
    DisplayStack(a);
   
    for (i=1; i<StackLength(a); i+=2)
    {
        Pop(&a, &e);//删除栈S的栈顶元素,并将该元素值赋给e
    }
    printf("e = %d\n", e);
   
    DisplayStack(a);
 
    e = 50;
    if (LocateElem(a, e))//在栈S中查找是否存在与给定值e相等的元素
    {
        printf("存在%d\n", e);
    }
    else
    {
        printf("不存在%d\n", e);
        Push(&a, e);//在栈S中插入新元素e
    }
   
    DisplayStack(a);
   
    ClearStack(&a);//将栈清空
    DisplayStack(a);
   
    return 0;
}

/*
函数功能:建立一个空的栈S
初始条件:无
操作结果:初始化栈S。操作成功返回OK,否则返回ERROR  
*/
Status InitStack(LinkStack *S)
{
    S->top = NULL;
    S->count = 0;
   
    return OK;
}

/*
函数功能:判断栈是否为空
初始条件:链栈S已经存在
操作结果:若栈为空,返回TRUE,否则返回FALSE
*/
Status StackEmpty(LinkStack S)
{
    return (S.top == NULL) ? TRUE : FALSE;
}

/*
函数功能:将栈清空
初始条件:链栈S已经存在
操作结果:将栈清空。操作成功返回OK,否则返回ERROR  
*/
Status ClearStack(LinkStack *S)
{
    LinkStackPtr p;
   
    if (S == NULL)
    {
        return ERROR;
    }
   
    while (S->top)
    {
        p = S->top;
        S->top = p->next;
        free(p);
    }
    S->count = 0;
   
    return OK;
}

/*
函数功能:返回栈S的元素个数
初始条件:链栈S已经存在
操作结果:返回栈S的元素个数
*/
int StackLength(LinkStack S)
{
    return S.count;
}

/*
函数功能:输出栈S的所有元素
初始条件:链栈S已经存在
操作结果:输出栈S的所有元素。操作成功返回OK,否则返回ERROR
*/
Status DisplayStack(LinkStack S)
{
    int i = 0;
    LinkStackPtr p = S.top;
   
    if (S.top == NULL)
    {
        printf("none!\n");   
        return ERROR;
    }
   
    while (p)
    {
        printf("data[%d] = %d, ", i++, p->data);
        p = p->next;
    }
    printf("\n");
        
    return OK;
}

/*
函数功能:用e返回栈S的栈顶元素
初始条件:链栈S已经存在
操作结果:用e返回栈S的栈顶元素。操作成功返回OK,否则返回ERROR
*/
Status GetTop(LinkStack S, ElemType *e)
{
    if (S.top == NULL)
    {
        return ERROR;
    }
   
    *e = S.top->data;
    return OK;
}

/*
函数功能:在栈S中查找是否存在与给定值e相等的元素
初始条件:链栈S已经存在
操作结果:在栈S中查找是否存在与给定值e相等的元素。找到返回TRUE,否则返回FALSE
*/
Status LocateElem(LinkStack S, ElemType e)
{
    LinkStackPtr p = S.top;
   
    while (p)
    {
        if (p->data == e)
        {
            return TRUE;
        }
        p = p->next;
    }
   
    return FALSE;
}

/*
函数功能:在栈S中插入新元素e
初始条件:链栈S已经存在
操作结果:在栈S中插入新元素e。操作成功返回OK,否则返回ERROR  
*/
Status Push(LinkStack *S, ElemType e)
{
    LinkStackPtr p = (LinkStackPtr)malloc(sizeof(StackNode));
   
    if (!p)
    {
        printf("Out of space!");
        return ERROR;
    }

    p->data = e;
    p->next = S->top;
    S->top = p;
    S->count++;
   
    return OK;
}

/*
函数功能:删除栈S的栈顶元素,并将该元素值赋给e
初始条件:链栈S已经存在
操作结果:删除栈S的栈顶元素,并将该元素值赋给e。
操作成功返回OK,否则返回ERROR  
*/
Status Pop(LinkStack *S, ElemType *e)
{
    LinkStackPtr p = S->top;
   
    if (S->top == NULL)
    {
        return ERROR;
    }
   
    *e = S->top->data;
    S->top = S->top->next;
    free(p);
    S->count--;
   
    return OK;
}
搜索更多相关主题的帖子: Copyright 读书笔记 include 
2014-09-13 19:44
yuccn
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:何方
等 级:版主
威 望:167
帖 子:6815
专家分:42393
注 册:2010-12-16
收藏
得分:5 
在论坛写笔记,呵呵,弄个博客吧

我行我乐
公众号:逻辑客栈
我的博客:
https://blog.yuccn. net
2014-09-15 12:58
巧若拙
Rank: 4
来 自:宁波余姚
等 级:业余侠客
威 望:1
帖 子:159
专家分:273
注 册:2014-8-24
收藏
得分:0 
贴笔记的动机是希望有同好之人关注一下,帮忙看看是否有理解错误的地方,帮我指出来
谢谢你的回复
2014-09-17 14:41
快速回复:《大话数据结构》读书笔记之栈抽象数据类型(链表实现)
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.017190 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved