链表的创建与遍历

￡神魔★判官ぃ 2022-06-03 02:52 197阅读 0赞

**链表**，简而言之，就是基于链式储存结构下的线性表。链表包括单向链表、双向链表以及循环链表。

链表是一种很常用的数据结构，其定义如下：

/**
      * 单向链表的定义
      * 定义说明：包括数据域和指针域
      */
    typedef int ElemType;
    typedef struct node {
      ElemType data;
      struct node *next;
    }LNode,*LinkList;

链表的基本操作包括创建链表、在链表中插入结点、在链表中删除结点、遍历链表中的内容以及销毁链表等。创建链表的方法有两种，一种是**“头插入”法**，另一种是**“尾插入”法**。具体代码如下所示：

/**
      *方法描述：“头插入”法创建链表
      *输入参数：int n
      *返回类型：LinkList
      */
    LinkList createLinkListHead(int n) {
     LinkList head,p;
     int i;
     head = (LinkList)malloc(sizeof(LNode));
     head->next = null;
    
     for(i=0;i<n;i++) {
      p = (LinkList)malloc(sizeof(LNode));
      p->data = i+1;
      p->next = head->next;
      head->next = p;
     }
      return head;
    }
    
    /**
      *方法描述：“尾插入”法创建链表
      *输入参数：int n
      *返回类型：LinkList
      */
    LinkList createLinkListTail(int n) {
     LinkList p,r;
     LinkList list = null;
     int i;
     
     for(i=0;i<n;i++) {
      p = (LinkList)malloc(sizeof(LNode));
      p->data = i+1;
      p->next = null;
      if(!list) {
         list = p;
       } else {
         r->next = p;
        }
         r = p;
      }
      return list;
    }

关于这两种方法，简要说明：“头插入”法，首先构建一个带有头结点的空链表，然后创建结点并在链表的头部插入结点，直到创建好链表，利用这种方法创建链表所输入的内容和遍历该链表输出的内容呈现**逆序关系**，而“尾插入”法实现输入的内容与输出内容表现**对应关系**，这种方法就是在链表的尾部插入结点，直到创建好链表。

对于已经创建好的链表，如何遍历链表中的内容并将其输出，可以通过如下代码实现：

/**
     *方法描述：遍历链表内容并输出
     *输入参数：LinkList list
     *返回类型：void
     */
    void printLinkListContent(LinkList list) {
      printf("遍历链表并输出内容\n");
       
      while(list) {
       printf("%d  ",list->data);
       list = list->next
      }
       printf("\n");
    }

测试代码如下：

#include<stdio.h>
    #include<stdlib.h>
    
    /**
     *方法描述：主方法，实现链表的创建与遍历
     *输入参数：
     *返回类型：int
     */
    int main() {
      int NUM = 10;
      LinkList list = createLinkListTail(NUM);
      printLinkListContent(list);
      return 0;
    }

运行结果如下：

![1345300969_9138.jpg][]

总结：链表采用链式存储结构在内存空间实现线性表的逻辑关系，这种情况下，逻辑关系的有序性并不意味着物理结构的有序性。它包括数据域和指针域两部分，相对于顺序表来说，它方便进行插入、删除操作，但是，线性表的内容遍历与输出需要头指针开始。

参考资料：

【1】谭浩强 著.C程序设计(第三版).北京：清华大学出版社，2007

【2】杨峰 著.妙趣横生的算法(C语言实现).北京：清华大学出版社，2011

[1345300969_9138.jpg]: https://img-my.csdn.net/uploads/201208/18/1345300969_9138.jpg