- quack.h
- // quack.h: an interface definition for a queue/stack
- #include <stdio.h>
- #include <stdlib.h>
- 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 <limits.h>
- // INT_MAX means largest int
- // if using this value, you need to include <limits.h>
- #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);
- }
运行下面命令实现编译
- [email protected]: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: <<>>
来源: http://www.bubuko.com/infodetail-3109016.html