（数据结构&C语言）对链表的认识-创新互联

• • （数据结构&C语言）链表
  • • 初始化链表
    • 单链表结点的插入
    • 单链表结点的删除
    • 获取指定位置上的元素
    • 查找指定元素的位置
    • 获取链表长度
    • 相关问题

链表不同于顺序表，顺序表底层采用数组作为存储容器，需要分配一块连续且完整的内存空间进行使用，而链表则不需要，它通过一个指针来连接各个分散的结点，形成了一个链状的结构，每个结点存放一个元素，以及一个指向下一个结点的指针，通过这样一个一个相连，最后形成了链表。它不需要申请连续的空间，只需要按照顺序连接即可，虽然物理上可能不相邻，但是在逻辑上依然是每个元素相邻存放的，这样的结构叫做链表（单链表）。

链表分为带头结点的链表和不带头结点的链表，带头结点的链表就是会有一个头结点指向后续的整个链表，但是头结点不存放数据，而不带头结点的链表就像上面那样，第一个节点就是存放数据的结点，一般设计链表都会采用带头结点的结构，因为操作更加方便。

接下来以带头结点的链表为例：

struct NodeList {int element;  //保存当前元素
  struct NodeList * next;  //指向下一个结点的指针
};
typedef struct NodeList * Node;

void initList(Node head) {head->next = NULL;  头结点默认下一个为NULL
}

先修改新插入结点的后继结点指向，指向原本在这个位置上的结点，接着将前驱结点的后继结点指向修改为新插入的结点：

寻找带插入位置的前驱结点：

_Bool insertList(Node head, int element, int index){//index表示位序
    if(index< 1) return 0;   //如果在非法位置插入，返回0表示插入操作执行失败
    while (--index) {//通过--index的方式不断向后寻找前驱结点，index为0时程序跳出循环
        head = head->next;   //正常情况下继续向后找
      	if(head == NULL) return 0;  //当已经没有后续结点时，说明index超出可插入的范围
    }
    return 1;
}

再根据上述思路，实现新结点的插入：

_Bool insertList(Node head, int element, int index){if(index< 1) return 0;
    while (--index) {head = head->next;
      	if(head == NULL) return 0;
    }
    Node node = malloc(sizeof (Node));
    if(node == NULL) return 0;   //创建一个新的结点，如果内存空间申请失败返回0
    node->element = element;   //将元素保存到新结点中
    node->next = head->next;   //先让新插入的节点指向原本位置上的这个结点
    head->next = node;   //接着将前驱结点指向新的这个结点
    return 1;
}

直接将待删除节点的前驱结点指向修改为待删除节点的下一个：

这样，待删除结点其实已经不在链表中了，所以只需要释放掉待删除结点占用的内存空间：

_Bool deleteNode(Node head,int index) {//head表示头结点
  _Bool deleteList(Node head, int index){if(index< 0) return 0;
    while (index--) {//找到前驱结点
        head = head->next;
        if(head == NULL) return 0;
    }
    if(head->next == NULL) return 0;  //如果前驱结点下一个是NULL，说明index也已超出代删除范围（删除与插入范围不一样）
    Node tmp = head->next;   //保存待删除结点
    head->next = head->next->next;   //让前驱结点指向下一个的下一个结点
    free(tmp);   //使用free函数释放掉待删除结点的内存
    return 1;
}

int getList(Node head,int index) {if(index< 1) return 0;
  do {head = head->next;  //使用do while语句跳过头结点
    if（head == NULL) return 0;
  } while(--index);  //为的是找到指定位置的结点
  return head->element;
}

int findList(Node head, int element){head = head->next;    //先走到第一个结点
    int i = 1;  //从位序1开始
    while (head) {if(head->element == element) return i;   
        head = head->next; 
        i++;
    }  //遍历完都没找到，则返回-1
    return -1;
}

int sizeNode(Node head) {int i = 0;  //从空的头结点开始
  while(head->next) {head = head->next;
    i++;
  }
  return i;
}

完整代码如下：

#include#includestruct NodeList {int element;
    struct NodeList * next;
};
typedef struct NodeList * Node;

void initNode(Node head) {head->next = NULL;
}

_Bool insertNode(Node head,int element,int index) {if(index< 1) return 0;
    while(--index) {head = head->next;
        if(head == NULL) return 0;
    }
    
    Node node = malloc(sizeof(Node));
    node->element = element;
    node->next = head->next;
    head->next = node;
    return 1;
}

_Bool deleteNode(Node head,int index) {if(index< 1) return 0;
    while(--index) {head = head->next;
        if(head == NULL) return 0;
    }
    if(head->next == NULL) return 0;
    
    Node baocun = head->next;
    head->next = head->next->next;
    free(baocun);
    return 1;
}

int  getNode(Node head,int index) {if(index< 1) return 0;
    do {   head = head->next;
           if(head == NULL) return 0;
       } while(--index);
       return head->element;
}

int findNode(Node head,int element) {head = head->next;
    int i = 1;
    while(head) {if(head->element == element) return i;
        head = head->next;
        i++;
    }
    return -1;
}

int sizeNode(Node head) {int i = 0;
    while(head->next) {head = head->next;
        i++;
    }
    return i;
}

void printNode(Node head) {//打印链表
    while(head->next) {head = head->next;
        printf("%d ",head->element);
    }
    printf("\n");
}

int main() {struct NodeList biao;
    initNode(&biao);
    for (int i = 0; i< 5; ++i) {insertNode(&biao, i * 50, i + 1);
    }
    deleteNode(&biao,3);
    printNode(&biao);
    printf("%d\n",getNode(&biao, 3));
    printf("%d\n",sizeNode(&biao));
    printf("%d\n",findNode(&biao,150));
}

运行后，成功得到结果：

值得注意的是：

• 插入：因为要寻找对应位置的前驱结点，所以平均时间复杂度为 O ( n ) O(n) O(n)，但是不需要做任何的移动操作，效率肯定是比顺序表要高的。
• 删除：同上，所以平均时间复杂度为 O ( n ) O(n) O(n)
• 获取元素：由于必须要挨个向后寻找，才能找到对应的结点，所以时间复杂度为 O ( n ) O(n) O(n)，不支持随机访问，只能顺序访问，比顺序表慢。

在随机访问元素时，链表需要通过遍历，而顺序表则利用数组的特性直接访问得到。

插入或删除某个元素时，顺序表需要通过遍历，而链表只需修改结点指向。

进行不同的操作时，从执行效率来看，各有各的有优势。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧