【420】链表实现Quack
阅读原文时间:2023年07月09日阅读:1

quack.h

// quack.h: an interface definition for a queue/stack
#include
#include

typedef struct node *Quack;

Quack createQuack(void); // create and return Quack
void push(int, Quack); // put the given integer onto the top of the quack
void qush(int, Quack); // put the given integer onto the bottom of the quack
int pop(Quack); // pop and return the top element on the quack
int isEmptyQuack(Quack); // return 1 is Quack is empty, else 0
void makeEmptyQuack(Quack);// remove all the elements on Quack
void showQuack(Quack); // print the contents of Quack, from the top down

quackLL.c

// quackLL.c: a linked-list-based implementation of a quack
#include "quack.h"
#include

// INT_MAX means largest int
// if using this value, you need to include
#define HEAD_DATA INT_MAX // dummy data

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

// create a null head
Quack createQuack(void) {
// Actually this head is NULL, it doesn't store
// meaningful data, only store the address.
Quack head;
head = malloc(sizeof(struct node));
if (head == NULL) {
fprintf(stderr, "Out of memory\n");
exit(1);
}

head->data = HEAD\_DATA;  
head->next = NULL;

// return the address of head  
return head;  

}

// push a new node between head and 1st node
void push(int data, Quack qs) {
Quack newnode;

// determine whether this quack is NULL or not  
if (qs == NULL) {  
    fprintf(stderr, "push: quack not initialised\\n");  
}  
else {  
    newnode = malloc(sizeof(struct node));  
      if (newnode == NULL) {  
        fprintf(stderr, "push: no memory, aborting\\n");  
        exit(1);  
    }

    newnode->data = data;  
    newnode->next = qs->next;  
    qs->next = newnode;  
}  
return;  

}

// pop the 1st node
int pop(Quack qs) {
// store data in variable retval
int retval = 0;

if (qs == NULL) {  
    fprintf(stderr, "pop: quack not initialised\\n");  
}  
else {  
    // if qs is empty, you can't pop any nodes  
    if (isEmptyQuack(qs)) {  
        fprintf(stderr, "pop: quack underflow\\n");  
    }  
    else {  
        Quack pop\_node = qs->next;  
        retval = pop\_node->data;

        // link head with 2nd node  
        qs->next = qs->next->next;  
        free(pop\_node);  
        pop\_node = NULL;  
    }  
}  
return retval;  

}

// pop all nodes in qs
void makeEmptyQuack(Quack qs) {
if (qs == NULL) {
fprintf(stderr, "makeEmptyQuack: quack not initialised\n");
}
else {
while (!isEmptyQuack) {
pop(qs);
}
}
return;
}

// only head, head link to NULL
int isEmptyQuack(Quack qs) {
if (qs == NULL) {
fprintf(stderr, "makeEmptyQuack: quack not initialised\n");
}
else {
if (qs->next == NULL) {
return 1;
}
}
return 0;
}

// print all nodes
void showQuack(Quack qs) {
if (qs == NULL) {
fprintf(stderr, "makeEmptyQuack: quack not initialised\n");
}
else {
// ??? maybe head is corrupted by opertions
if (qs->data != HEAD_DATA) {
fprintf(stderr, "showQuack: linked list head corrupted\n");
}
else {
printf("Quack: ");
if (qs->next == NULL) {
printf("<< >>\n");
}
else {
printf("<<"); Quack node = qs->next;
while (node->next != NULL) {
printf("%d ", node->data);
node = node->next;
}
printf("%d ", node->data);
printf(">>\n");
}
}
}
return;
}

clientQuack.c

#include "quack.h"

int main() {
Quack qs = createQuack();
push(1, qs);
showQuack(qs);
push(2, qs);
showQuack(qs);
push(3, qs);
showQuack(qs);
push(4, qs);
showQuack(qs);

pop(qs);  
showQuack(qs);  
pop(qs);  
showQuack(qs);  
pop(qs);  
showQuack(qs);  
pop(qs);  
showQuack(qs);

}

运行下面命令实现编译

alex@ubuntu:Day01$ gcc quackLL.c clientQuack.c && ./a.out
Quack: <<1 >>
Quack: <<2 1 >>
Quack: <<3 2 1 >>
Quack: <<4 3 2 1 >>
Quack: <<3 2 1 >>
Quack: <<2 1 >>
Quack: <<1 >>
Quack: << >>

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章