线性表：n个数据元素的有限序列。一般指逻辑结构上的线性结构。当n=0时为空表。——栈、队列、串。

线性表的特点：

1）对于同一线性表的各数据元素必定具有相同的数据类型和长度；

2）数据元素之间的相对位置是线性的。

 

链表（Linked List）：链接方式存储的线性表。

1）用一组任意的存储单元来存放线性表的结点；

2）在存储每个结点值的同时，必须存储指示其后继结点的地址。

链域（指针域）：存放结点的直接后继的地址。

 

单链表（Single Linked List）：每个结点只有一个链域的链表。

数据域：存储数据元素信息的域。

指针域：存储直接后继存储位置的域。

由于开始结点无前驱，故设头指针head指向开始结点。

终端结点无后继，故终端结点的指针域为空，即NULL。

在单链表中，取得第i个数据元素必须从头指针出发寻找，因此，单链表是非随机存取的存储结构。

　　在单链表的第一个结点之前附设一个结点，称为头结点。头结点的指针域存储指向第一个结点的指针。 

/* *位置约定：第m个，以0开始计数。 *位置为m，以1开始计数 */#include 
     
      #include 
      
       /* 链表节点 */struct node{    int data;    struct node *next;};/* 反转单链表，分别用3个指针，指向前一个，当前，下一个  * 修改链表头（指针），要用指针的指针  * 通过函数的方式修改指针，要用指针的指针 */static void reverse(struct node** head_ref){    struct node* prev = NULL;    struct node* current = *head_ref;    struct node* next;    while(current != NULL)    {        next = current->next;        current->next = prev;        prev = current;        current = next;    }    *head_ref = prev;}    //使用递归的方法static struct node* reverseRecall(struct node* head){    //最后一个节点会返回作为头部    if(head == NULL || head->next == NULL)        return head;    struct node* newHead = reverseRecall(head->next);    //head->next表示剩下的部分    head->next->next = head;    head->next = NULL;        //原来的头节点next应该为NULL    return newHead;}    // 添加数据，头部插入void push(struct node** head_ref, int new_data){    struct node* new_node = (struct node*) malloc(sizeof(struct node));    new_node->data = new_data;    new_node->next = (*head_ref);    (*head_ref) = new_node;}        //打印链表void printList(struct node* head){    struct node* temp = head;    while(temp != NULL)    {        printf("%d ", temp->data);        temp = temp->next;    }}int length(struct node* head){    int n = 0;    struct node* temp = head;    while(temp != NULL)    {        n++;        temp = temp->next;    }    return n;}void RemoveHead(struct node** head_ref){    if(*head_ref == NULL)    {        printf("there is no element in the list.\n");        return;    }    *head_ref = (*head_ref)->next;}/*不知道节点数N，只遍历一次就求出中间节点 *Q：当单链表长度为0时，报错 */void SearchMid(struct node* head, struct node** mid){    struct node *p1, *p2;    p1 = head;    p2 = head;    while((p2->next != NULL) && (p2->next->next != NULL))    {        p2 = p2->next->next;        p1 = p1->next;    }    *mid = p1;}/*Method1: 找出链表倒数第m个元素 *当m=0时，返回链表最后一个元素 *先求出链表的总长度len，然后顺序变量求出位置在len-m的元素 */node* SearchLastMElement1(struct node* head, int m){    int len = length(head);    if(m < 0 || m > len-1 || head == NULL)        return NULL;    struct node* temp = head;    for(int i = 1; i < len-m; i++)        temp = temp->next;    return temp;}/*Method2: 找出链表倒数第m个元素 *当m=0时，返回链表最后一个元素 *当前位置指针p，指向第m个元素的指针pm， *确保两个指针之间相差m个元素，然后以同样的速度移动它们 *当pm到达链表末尾时，p指针就是指向倒数第m个元素了 */node* SearchLastMElement2(struct node* head, int m){    struct node* p = head;    struct node* pm = head;    for(int i = 1; i <= m; i++)        //使指针pm指向第m个元素    {        if(pm->next != NULL)            pm = pm->next;        else            return NULL;    }    while(pm->next != NULL)            //同样的速度移动指针p和pm    {        p = p->next;        pm = pm->next;    }    return p;}int main(){    struct node* head = NULL;    push(&head, 20);    push(&head, 4);    push(&head, 15);    push(&head, 85);    push(&head, 60);    push(&head, 100);    push(&head, 80);    printList(head);    reverse(&head);    printf("\n==============================\nReversed Linked list \n");    printList(head);    printf("\n==============================\nreverseRecall Linked list \n");    head = reverseRecall(head);    printList(head);    printf("\n==============================\nlength of  Linked list: ");    int len = length(head);    printf("%d\n", len);    printf("==============================\nRemoveHead test: \n");    RemoveHead(&head);    printList(head);    printf("\n==============================\nSearchMid test: ");    struct node* mid;    SearchMid(head, &mid);    printf("%d\n", mid->data);    int m = 5;    struct node* elemM;    printf("==============================\nSearchLastMElement2 test: ");    elemM = SearchLastMElement2(head, m);    printf("the last %d element is %d\n", m, elemM->data);    printf("==============================\nSearchLastMElement2 test: ");    elemM = SearchLastMElement2(head, m);    printf("the last %d element is %d\n", m, elemM->data);    return 0;}
      
     

 输出：

80 100 60 85 15 4 20==============================Reversed Linked list20 4 15 85 60 100 80==============================reverseRecall Linked list80 100 60 85 15 4 20==============================length of  Linked list: 7==============================RemoveHead test:100 60 85 15 4 20==============================SearchMid test: 85==============================SearchLastMElement2 test: the last 5 element is 100==============================SearchLastMElement2 test: the last 5 element is 100

　　

参考连接：