数据结构之线性表

一、概述

线性表的顺序表示，特点是逻辑关系上相邻的两个元素物理位置上也相邻，这种数据结构的优点是可以随机读取表中的任意元素；缺点是做插入或者删除时，需要移动大量的元素。

与之相对的链式表示，不要求逻辑上相连的元素物理位置也相邻，每个元素除了存储其本身的数据之外，还存储了一个指示其后继元素位置的信息。因此在插入和删除时，不需要移动大量的元素，但是也不支持随机读取表中的任意元素。

二、线性链表的实现

#include typedef struct Node {    int data;    struct Node * next;} Node;int initLinkList(Node *node) {    node->data = 0;    node->next = NULL;    return 0;}int getLinkListLen(Node *node){    int i = 0;    for (i=0; node->next != NULL; i++) {        node = node -> next;    }    return i;}int getLinkListElm(Node *node, int num, int * data){    int i = 0;    int len;    len = getLinkListLen(node);    if (num > len) {        printf("the number exceed link list lenth\n");        return -1;    }    for (i=0; i next;    }    *data = node->data;    return 0;}int insertLinkList(Node *node, int num, int *data){    int i = 0;    int len;    Node * newNode = (Node *)malloc(sizeof(Node));    newNode->data = *data;    newNode->next = NULL;        len = getLinkListLen(node);        if (num > len) {        printf("the number exceed link list lenth\n");        return -1;    }    for (i=0; i next;    }    newNode->next = node->next;    node->next = newNode;    return 0;}int delLinkList(Node *node, int num){    int i = 0;    int len = 0;    Node *delNode = (Node *)malloc(sizeof(Node));    len = getLinkListLen(node);    if (num > len) {        printf("the number exceed link list lenth\n");        return -1;    }    for (i=0; i next;    }    delNode = node->next;    node -> next = delNode -> next;    free(delNode);    return 0;}void printLinkList(Node *node){    int i = 0;    for (i=0; node->next != NULL; i++) {        printf("%d ", node->next->data);        node = node->next;    }    printf("\n");}int main(int argc, char argv[]){    testInsertLinkList();    testDelLinkList();    testGetLinkListElm();    return 0;}void testInsertLinkList(){    Node *node = (Node *)malloc(sizeof(Node));    initLinkList(node);    int num = 8;    insertLinkList(node, 0, &num);    printf("the link list should be: 8, and it is: ");    printLinkList(node);    num = 9;    insertLinkList(node, 0, &num);    printf("the link list should be: 9 8, and it is: ");    printLinkList(node);    num = 1;    insertLinkList(node, 2, &num);    printf("the link list should be: 9 8 1, and it is: ");    printLinkList(node);}void testDelLinkList(){    Node *node = (Node *)malloc(sizeof(Node));    initLinkList(node);    int num = 8;    insertLinkList(node, 0, &num);    num  = 9;    insertLinkList(node, 0, &num);    num = 122;    insertLinkList(node, 1, &num);    printf("the link list should be: 9 122 8, and it is: ");    printLinkList(node);    delLinkList(node, 1);    printf("the link list should be: 122 8, and it is: ");    printLinkList(node);    }void testGetLinkListElm(){    int data = 0;    Node *node = (Node *)malloc(sizeof(Node));    initLinkList(node);    int num = 8;    insertLinkList(node, 0, &num);    getLinkListElm(node, 1, &data);    printf("data should be 8, and it is: %d\n", data);    num = 9;    insertLinkList(node, 1, &num);    num = 10;    insertLinkList(node, 2, &num);    getLinkListElm(node, 3, &data);    printf("data should be 10, and it is: %d\n", data);}