Реализация стека с помощью связанного списка - PullRequest
Новая
       1

Реализация стека с помощью связанного списка

0 голосов
/ 08 марта 2011

Вот моя реализация стека со связанным списком. Программа работает правильно. Хотели бы вы прокомментировать функциональность / производительность / использование памяти? 

#include <stdafx.h>
#include <stdlib.h>
#include <stdio.h>

struct node
{
int data;
struct node * next;
};

int length(struct node * current)
{
int len = 0;
while(current)
{
len++;
current = current->next;
}
return len;
}

struct node* push(struct node* stack, int data)
{
    struct node * current = stack;
    struct node * newNode = (node*)(malloc(sizeof(node*)));
    newNode->data = data;
    newNode->next = NULL;
    //length(current);
    //single element case
    if(stack == NULL)
    {           
    stack = newNode;
    }
    else// multiple element case
    {
        while(current!=NULL)
        {
            if(current->next==NULL){
                current->next = newNode;
                break;
                }
            else
            {
            current = current->next;
            }
        }
    }

    return stack;
}

bool isemp(struct node * stack)
{
    if(stack == NULL)
    {
    printf("Stack is empty");
    return true;
    }
    else{
        return false;
    }
}

struct node * pop(struct node * stack)
{

struct node * current = stack;
struct node * previous = NULL;
bool isempty = false;
while(!isemp(stack)&& current)
    {
        if(current->next==NULL)
        {
        //delete previous;

            if(previous)
            {
            previous->next = NULL;
            printf("Popped element is %d ", current->data);
            current = current->next;
            }
            else if(length(stack)==1)
            {
            printf("Pop last element %d",stack->data);
            stack = NULL;
            current = NULL;
            }
        }

        else
        {
        previous = current;
        current = current->next;
        //stack = current;
        }
    }
    return stack;
}


void main()
{
    struct node * stack = NULL;
    int data =  1;
    int index = 5;
    while(index)
    {       
        stack = push(stack,data );
        data++;
        index--;
    }
    while(stack!=NULL)
    {
    stack = pop(stack);
    }

}

Ответы [ 2 ]

3 голосов
/ 08 марта 2011

В вашем коде огромное количество проблем . В методе push () вы делаете это: 

      while(current!=NULL)

    {
        if(current->next==NULL){
            current->next = newNode; //This is also Wrong .You are not making Head pointing to newly created  node
            break;
            }
        else
        {
        current = current->next; //This is Wrong For Stack Implementation
        }
    }`

Что вы на самом деле делаете, так это вставляете вновь созданный узел в конец связанного списка. Таким образом, очередь реализуется через связанный список .

0 голосов
/ 01 апреля 2011

Один из способов реализовать то же самое осуществляется по ссылке
http://codepad.org/dRMwSOuO
где новый элемент добавляется в начальный конец списка и извлекается с того же конца. Однако граничные условия не обрабатываются должным образом. Тем не менее сложность по времени будет лучше, так как вам не придется проходить в списке до конца.

...