数组、单向链表和双向链表

DoubleLink.c

//
//  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

//
//  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

//
//  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;
}

数组、单向链表和双向链表.md

1. 数组

数组有上界和下界，数组内的元素在上下界内是连续的。

数组的特点是：数据是连续的；随机访问速度快

数组中稍微复杂一点的是多维数组和动态数组。对于C语言，多维数组本质上也是通过一维数组实现的。动态数组，是指数组的容量能动态增长，对于C语言需要手动实现；对于C++而言, STL提供了Vector；对于Java而言，Collection集合提供了ArrayList和Vector。

2. 单向链表

单向链表（单链表）是链表的一种，它由节点组成，每个节点都包含下一个节点的指针。

单向链表的特点是：节点的链接放心是单向的，相对于数组，单向链表的随机访问速度慢，但是单向链表删除、添加数据的效率很高。

3. 双向链表

双向链表（双链表）是链表的一种。和单链表一样，双链表也是由节点组成，它的每个数据节点中都有两个指针，分别指向直接后继和直接前驱。所以，从双链表中的任意一个节点开始，都可以很方便地访问它的前驱节点和后继节点。一般我们都构造双向循环链表。