双向链表是一种常见的数据结构，链表中的每一个节点都保存了上一个和下一个元素的位置，所以表现为增删元素效率较高，查找元素效率较低，但是都能很容易的查找指定节点的前后节点。
//
// BookNode.h
// c_study
//
// Created by VV on 2019/2/23.
// Copyright © 2019年 SGQ. All rights reserved.
//
#ifndef BookNode_h
#define BookNode_h
#include <stdio.h>
#include <stdbool.h>
typedef struct BookNode_{
char *name;
struct BookNode_ *pre;
struct BookNode_ *next;
} BookNode;
typedef struct BookList_ {
BookNode *firstBook;
BookNode *lastBook;
int length;
} BookList;
// init a book with name
BookNode *createBookNode(char *bookName);
// print bookNode's name
void printBookName(BookNode *book);
// print bookList
void printBookListWithOrder(BookList *list, bool headToTail);
// print bookNode's name is bookList at a specified postion
void printTargetIndexBookNameInBookList(BookList *list, int position);
// insert a bookNode to head of a bookList
int insertBookToHead(BookList *list, char *bookName);
// insert a bookNode to tail of a bookList
int insertBookToTail(BookList *list, char *bookName);
// delete a bookNode from head
void popHeadBookInBookList(BookList *bookList);
// delete a bookNode from tail
void popTailBookInBookList(BookList *bookList);
#endif /* BookNode_h */
//
// BookNode.c
// c_study
//
// Created by VV on 2019/2/23.
// Copyright © 2019年 SGQ. All rights reserved.
//
#include "BookNode.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
BookNode *createBookNode(char *bookName) {
if (!strlen(bookName)) {
printf("bookName is empty!!\n");
return NULL;
}
BookNode *bookNode = malloc(sizeof(BookNode));
bookNode->name = bookName;
bookNode->next = NULL;
bookNode->pre = NULL;
return bookNode;
}
void printBookName(BookNode *book) {
if (book != NULL) {
printf("%s\n", book->name);
} else {
printf("book is NULL!!\n");
}
}
void printTargetIndexBookNameInBookList(BookList *list, int position) {
if (list == NULL) {
printf("list is NULL!!\n");
return;
}
if (list->length == 0) {
printf("list is empty !!\n");
}
if (position < 0 || position >= list->length) {
printf("postion should be bigger than zero and less than list's length");
}
int length = list->length;
if (position < length / 2) {
int index = 0;
BookNode *node = list->firstBook;
while (true) {
if (index == position) {
// found
printBookName(node);
break;
} else {
index ++;
node = node->next;
}
}
} else {
position = list->length - 1 - position;
int index = 0;
BookNode *node = list->lastBook;
while (true) {
if (index == position) {
// found
printBookName(node);
break;
} else {
index ++;
node = node->pre;
}
}
}
}
void printBookListWithOrder(BookList *list, bool headToTail) {
if (list == NULL) {
printf("list is NULL!!\n");
return;
}
if (list->length == 0) {
printf("list is empty !!\n");
}
BookNode *book = headToTail ? list->firstBook : list->lastBook;
while (book != NULL) {
printBookName(book);
book = headToTail ? book->next : book->pre;
}
}
int insertBookToHead(BookList *list, char *bookName) {
if (list == NULL) {
return -1;
}
BookNode *bookNode = createBookNode(bookName);
if (bookNode == NULL) {
return -1;
}
bookNode->next = list->firstBook;
bookNode->pre = NULL;
if (list->firstBook != NULL) {
list->firstBook->pre = bookNode;
}
list->firstBook = bookNode;
if (list->length == 0) {
list->lastBook = bookNode;
}
list->length ++;
return 1;
}
int insertBookToTail(BookList *list, char *bookName) {
if (list == NULL) {
return -1;
}
BookNode *bookNode = createBookNode(bookName);
if (bookNode == NULL) {
return -1;
}
bookNode->pre = list->lastBook;
bookNode->next = NULL;
if (list->lastBook != NULL) {
list->lastBook->next = bookNode;
}
list->lastBook = bookNode;
if (list->firstBook == NULL) {
list->firstBook = bookNode;
}
list->length ++;
return 1;
}
void popHeadBookInBookList(BookList *bookList) {
if (bookList == NULL) {
printf("booklist is empty!!\n");
return;
}
if (bookList->length == 0) {
printf("booklist is empty!!\n");
return;
}
printf("------ [%s] has been deleted-------\n", bookList->firstBook->name);
if (bookList->firstBook->next != NULL) {
bookList->firstBook = bookList->firstBook->next;
free(bookList->firstBook->pre);
bookList->firstBook->pre = NULL;
} else {
free(bookList->firstBook);
bookList->firstBook = NULL;
}
bookList->length --;
if (bookList->length == 0) {
bookList->lastBook = NULL;
}
}
void popTailBookInBookList(BookList *bookList) {
if (bookList == NULL) {
printf("booklist is NULL!!\n");
return;
}
if (bookList->length == 0) {
printf("booklist is empty!!\n");
return;
}
printf("------ [%s] has been deleted-------\n", bookList->lastBook->name);
if (bookList->lastBook->pre != NULL) {
bookList->lastBook = bookList->lastBook->pre;
free(bookList->lastBook->next);
bookList->lastBook->next = NULL;
} else {
free(bookList->lastBook);
bookList->lastBook = NULL;
}
bookList->length --;
if (bookList->length == 0) {
bookList->firstBook = NULL;
}
}
#include <stdio.h>
#include "BookNode.h"
int main(int argc, const char * argv[]) {
// insert code here...
BookList list = {NULL, NULL, 0, };
insertBookToTail(&list, "0");
insertBookToTail(&list, "1");
insertBookToTail(&list, "2");
insertBookToTail(&list, "3");
insertBookToTail(&list, "4");
printBookListWithOrder(&list, true);
printf("----------");
printTargetIndexBookNameInBookList(&list, 4);
// popTailBookInBookList(&list);
// popTailBookInBookList(&list);
// popTailBookInBookList(&list);
// popTailBookInBookList(&list);
// popTailBookInBookList(&list);
return 0;
}
网友评论