| // | |
| // DoubleLink.c | |
| // DataStructureAndAlgorithm | |
| // | |
| // Created by wanyakun on 2016/10/27. | |
| // Copyright © 2016年 com.ucaiyuan. All rights reserved. | |
| // | |
| #include "DoubleLink.h" | |
| #include <stdlib.h> | |
| //typedef struct ElementType ElemType; | |
| typedef struct DoubleLinkNode { | |
| struct DoubleLinkNode *preNode; | |
| struct DoubleLinkNode *nextNode; | |
| void *data; | |
| } DLNode; | |
| /// 表头。不存放元素值 | |
| static DLNode *head = NULL; | |
| /// 节点个数 | |
| static int count = 0; | |
| static DLNode * createNode(void *data) { | |
| DLNode *node = NULL; | |
| node = (DLNode *)malloc(sizeof(node)); | |
| if (!node) { | |
| printf("create node error!\n"); | |
| return NULL; | |
| } | |
| // 默认node的前一节点和后一节点都指向自身 | |
| node->preNode = node->nextNode = node; | |
| // 节点的值为data | |
| node->data = data; | |
| return node; | |
| } | |
| int createDLink() { | |
| head = createNode(NULL); | |
| if (!head) { | |
| return -1; | |
| } | |
| count = 0; | |
| return 0; | |
| } | |
| int destroyDLink() { | |
| if (!head) { | |
| printf("%s failed! DLink is null!\n", __func__); | |
| return -1; | |
| } | |
| DLNode *node = head->nextNode; | |
| DLNode *temp = NULL; | |
| while (node != head) { | |
| temp = node; | |
| node = node->nextNode; | |
| free(temp); | |
| } | |
| free(head); | |
| head = NULL; | |
| count = 0; | |
| return 0; | |
| } | |
| int isDLinkEmpty() { | |
| return count == 0; | |
| } | |
| int dLinkSize() { | |
| return count; | |
| } | |
| static DLNode * _getNode(int index) { | |
| if (index < 0 || index >= count) { | |
| printf("%s failed! index out of bound!\n", __func__); | |
| return NULL; | |
| } | |
| if (index <= count/2) { | |
| int i = 0; | |
| DLNode *node = head->nextNode; | |
| while ((i++) < index) { | |
| node = node->nextNode; | |
| } | |
| return node; | |
| } | |
| int j = 0; | |
| int rIndex = count - index - 1; | |
| DLNode *node = head->preNode; | |
| while ((j++) < rIndex) { | |
| node = node->preNode; | |
| } | |
| return node; | |
| } | |
| void* getNodeData(int index) { | |
| DLNode *node = _getNode(index); | |
| if (!node) { | |
| printf("%s failed!\n", __func__); | |
| return NULL; | |
| } | |
| return node->data; | |
| } | |
| void* firstNodeData() { | |
| return getNodeData(0); | |
| } | |
| void* lastNodeData() { | |
| return getNodeData(count-1); | |
| } | |
| int insertData(int index, void *data) { | |
| if (index == 0) { | |
| return insertFirst(data); | |
| } | |
| DLNode *indexNode = _getNode(index); | |
| if (!indexNode) { | |
| return -1; | |
| } | |
| DLNode *node = createNode(data); | |
| if (!node) { | |
| return -1; | |
| } | |
| node->preNode = indexNode->preNode; | |
| node->nextNode = indexNode; | |
| indexNode->preNode->nextNode = node; | |
| indexNode->preNode = node; | |
| count++; | |
| return 0; | |
| } | |
| int insertFirst(void *data) { | |
| DLNode *node = createNode(data); | |
| if (!node) { | |
| return -1; | |
| } | |
| node->preNode = head; | |
| node->nextNode = head->nextNode; | |
| head->nextNode->preNode = node; | |
| head->nextNode = node; | |
| count++; | |
| return 0; | |
| } | |
| int appendData(void *data) { | |
| DLNode *node = createNode(data); | |
| if (!node) { | |
| return -1; | |
| } | |
| node->nextNode = head; | |
| node->preNode = head->preNode; | |
| head->preNode->nextNode = node; | |
| head->preNode = node; | |
| count++; | |
| return 0; | |
| } | |
| int deleteNode(int index) { | |
| DLNode *node = _getNode(index); | |
| if (!node) { | |
| printf("%s failed! the index is out of bound!\n", __func__); | |
| return -1; | |
| } | |
| node->nextNode->preNode = node->preNode; | |
| node->preNode->nextNode = node->nextNode; | |
| free(node); | |
| count--; | |
| return 0; | |
| } | |
| int deleteFirstNode() { | |
| return deleteNode(0); | |
| } | |
| int deleteLastNode() { | |
| return deleteNode(count-1); | |
| } |
| // | |
| // DoubleLink.h | |
| // DataStructureAndAlgorithm | |
| // | |
| // Created by wanyakun on 2016/10/27. | |
| // Copyright © 2016年 com.ucaiyuan. All rights reserved. | |
| // | |
| #ifndef DoubleLink_h | |
| #define DoubleLink_h | |
| #include <stdio.h> | |
| /** | |
| 新建双向链表 | |
| @return 成功返回0；否则返回-1 | |
| */ | |
| extern int createDLink(); | |
| /** | |
| 撤销双向链表 | |
| @return 成功返回0， 否则返回-1 | |
| */ | |
| extern int destroyDLink(); | |
| /** | |
| 双向链表是否为空 | |
| @return 为空返回1，否则返回0 | |
| */ | |
| extern int isDLinkEmpty(); | |
| /** | |
| 双向链表大小 | |
| @return 返回双向链表大小 | |
| */ | |
| extern int dLinkSize(); | |
| /** | |
| 获取双向链表中第index位置的元素 | |
| @param index 位置 | |
| @return 成功返回节点元素指针，否则返回NULL | |
| */ | |
| extern void* getNodeData(int index); | |
| /** | |
| 获取双向链表中第一个位置的元素 | |
| @return 成功返回节点元素指针，否则返回NULL | |
| */ | |
| extern void* firstNodeData(); | |
| /** | |
| 获取双向链表中最后一个位置的元素 | |
| @return 成功返回节点元素指针，否则返回NULL | |
| */ | |
| extern void* lastNodeData(); | |
| /** | |
| 将元素插入到index位置 | |
| @param index 插入位置 | |
| @param data 插入的元素 | |
| @return 成功返回0，否则返回-1 | |
| */ | |
| extern int insertData(int index, void *data); | |
| /** | |
| 插入元素到表头位置 | |
| @param data 插入的元素 | |
| @return 成功返回0，否则返回-1 | |
| */ | |
| extern int insertFirst(void *data); | |
| /** | |
| 插入元素到末尾位置 | |
| @param data 被插入的元素 | |
| @return 成功返回0，否则返回-1 | |
| */ | |
| extern int appendData(void *data); | |
| /** | |
| 删除双向链表index位置的节点 | |
| @param index 删除位置 | |
| @return 成功返回0，否则返回-1 | |
| */ | |
| extern int deleteNode(int index); | |
| /** | |
| 删除双向链表第一个节点 | |
| @return 成功返回0，否则返回-1 | |
| */ | |
| extern int deleteFirstNode(); | |
| /** | |
| 删除双向链表最后一个节点 | |
| @return 成功返回0，否则返回-1 | |
| */ | |
| extern int deleteLastNode(); | |
| #endif /* DoubleLink_h */ |
| // | |
| // DoubleLinkTest.c | |
| // DataStructureAndAlgorithm | |
| // | |
| // Created by wanyakun on 2016/10/27. | |
| // Copyright © 2016年 com.ucaiyuan. All rights reserved. | |
| // | |
| #include "DoubleLink.h" | |
| /** | |
| 双向链表操作int数据 | |
| */ | |
| void intTest() { | |
| int array[4] = {10, 20, 30, 40}; | |
| printf("\n----%s----\n", __func__); | |
| createDLink(); | |
| insertData(0, &array[0]); | |
| insertData(0, &array[1]); | |
| insertData(0, &array[2]); | |
| printf("DLink is empty = %d\n", isDLinkEmpty()); | |
| printf("DLink size = %d\n", dLinkSize()); | |
| //打印全部数据 | |
| for (int i = 0; i < dLinkSize(); i++) { | |
| char *p = (char *)getNodeData(i); | |
| printf("DLink data at index %d = %s\n", i, p); | |
| } | |
| destroyDLink(); | |
| } | |
| void stringTest() { | |
| char *array[4] = {"ten", "twenty", "thirty", "forty"}; | |
| printf("\n----%s----\n", __func__); | |
| createDLink(); | |
| insertData(0, &array[0]); | |
| insertData(0, &array[1]); | |
| insertData(0, &array[2]); | |
| printf("DLink is empty = %d\n", isDLinkEmpty()); | |
| printf("DLink size = %d\n", dLinkSize()); | |
| //打印全部数据 | |
| for (int i = 0; i < dLinkSize(); i++) { | |
| char *p = (char *)getNodeData(i); | |
| printf("DLink data at index %d = %s\n", i, p); | |
| } | |
| destroyDLink(); | |
| } | |
| typedef struct Student { | |
| int id; | |
| char name[20]; | |
| } STU; | |
| static STU stuArray[] = { | |
| {10, "Jack"}, | |
| {20, "Tom"}, | |
| {30, "Willam"}, | |
| {40, "Lucy"}, | |
| }; | |
| #define STU_ARRAY_SIZE (sizeof(stuArray) / sizeof(stuArray[0])) | |
| void objectTest() { | |
| printf("\n----%s----\n", __func__); | |
| createDLink(); | |
| insertData(0, &stuArray[0]); | |
| insertData(0, &stuArray[1]); | |
| insertData(0, &stuArray[2]); | |
| printf("DLink is empty = %d\n", isDLinkEmpty()); | |
| printf("DLink size = %d\n", dLinkSize()); | |
| //打印全部数据 | |
| for (int i = 0; i < dLinkSize(); i++) { | |
| STU *p = (STU *)getNodeData(i); | |
| printf("DLink data at index %d = [%d, %s]\n", i, p->id, p->name); | |
| } | |
| destroyDLink(); | |
| } | |
| int main(int argc, char const *argv[]) | |
| { | |
| intTest(); | |
| stringTest(); | |
| objectTest(); | |
| return 0; | |
| } |
数组有上界和下界，数组内的元素在上下界内是连续的。
数组的特点是：数据是连续的；随机访问速度快
数组中稍微复杂一点的是多维数组和动态数组。对于C语言，多维数组本质上也是通过一维数组实现的。动态数组，是指数组的容量能动态增长，对于C语言需要手动实现；对于C++而言, STL提供了Vector；对于Java而言，Collection集合提供了ArrayList和Vector。
单向链表（单链表）是链表的一种，它由节点组成，每个节点都包含下一个节点的指针。
单向链表的特点是：节点的链接放心是单向的，相对于数组，单向链表的随机访问速度慢，但是单向链表删除、添加数据的效率很高。
双向链表（双链表）是链表的一种。和单链表一样，双链表也是由节点组成，它的每个数据节点中都有两个指针，分别指向直接后继和直接前驱。所以，从双链表中的任意一个节点开始，都可以很方便地访问它的前驱节点和后继节点。一般我们都构造双向循环链表。