结构之美:单链表的初始化、创建与遍历

写一个简单的单链表
服务器君一共花费了355.002 ms进行了7次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

前面已经对单链表做了一些解释。链表在进行循环遍历时效率不高,但是插入和删除时优势明显。

单链表实际上是由节点(Node)组成的,一个链表拥有不定数量的节点。而向外暴露的只有一个头节点(Head),我们对链表的所有操作,都是直接或者间接地通过其头节点来进行的。节点(Node)是由一个需要储存的对象及对下一个节点的引用组成的。也就是说,节点拥有两个成员:储存的对象、对下一个节点的引用。其实应该用数据和地址代替前面的对象和引用的。

单链表的结构示意图(包括空的单链表):

那么大家可能清楚了,为什么说有了头节点就可以操作所有节点。因为有连续不断的引用嘛!那么在链表里的属性大概就只有两个了:头节点和节点数量。当然,根据需要,我们通常需要更多的属性。

下面用C语言简单写一个单链表,并完成初始化,创建链表与链表遍历。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef int ElemType;   /* ElemType类型根据实际情况而定,这里假设为int */
/* 定义单链表结点类型 */
typedef struct Node{
    ElemType element;
    struct Node *next;
}Node;

/* 1.初始化线性表,即置单链表的表头指针为空 */
void initList(Node **pNode)
{
    *pNode = NULL;
    printf("initList函数执行,初始化成功\n");
}

/* 2.创建线性表,此函数输入负数终止读取数据*/
Node *creatList(Node *pHead)
{
    Node *p1;
    Node *p2;

    p1=p2=(Node *)malloc(sizeof(Node)); //申请新节点
    if(p1 == NULL || p2 ==NULL)
    {
        printf("内存分配失败\n");
        exit(0);
    }
    memset(p1,0,sizeof(Node));

    scanf("%d",&p1->element);   //输入新节点
    p1->next = NULL;            //新节点的指针置为空
    while(p1->element > 0)      //输入的值大于0则继续,直到输入的值为负
    {
        if(pHead == NULL)       //空表,接入表头
        {
            pHead = p1;
        }
        else
        {
            p2->next = p1;      //非空表,接入表尾
        }
        p2 = p1;
        p1=(Node *)malloc(sizeof(Node));    //再重申请一个节点
        if(p1 == NULL || p2 ==NULL)
        {
        printf("内存分配失败\n");
        exit(0);
        }
        memset(p1,0,sizeof(Node));
        scanf("%d",&p1->element);
        p1->next = NULL;
    }
    printf("creatList函数执行,链表创建成功\n");
    return pHead;           //返回链表的头指针
}

/* 3.打印链表,链表的遍历*/
void printList(Node *pHead)
{
    if(NULL == pHead)   //链表为空
    {
        printf("PrintList函数执行,链表为空\n");
    }
    else
    {
        while(NULL != pHead)
        {
            printf("%d ",pHead->element);
            pHead = pHead->next;
        }
        printf("\n");
    }
}

int main()
{
    Node *pList = NULL;
    int length = 0;

    ElemType posElem;
    initList(&pList);   //链表初始化
    printList(pList);   //遍历链表,打印链表

    printf("请为链表输入节点值,输入负数退出 \n");
    pList=creatList(pList); //创建链表
    printList(pList);
}

链表是由不定数量的节点连接(通过相互之间的引用)起来的,由于这种关系,在链表里我们只定义了头节点和节点数量。节点是由存储的对象及对下一个“节点”的引用封装而成。

延伸阅读

此文章所在专题列表如下:

  1. 结构之美:定义一个线性表
  2. 结构之美:线性表的查找、插入与删除操作
  3. 结构之美:线性表的链式存储结构——链表
  4. 结构之美:单链表的初始化、创建与遍历
  5. 结构之美:单链表的头结点与头指针
  6. 结构之美:使用头插法创建单链表
  7. 结构之美:使用尾插法创建单链表
  8. 结构之美:单链表的销毁删除
  9. 结构之美:查找单链表指定位置结点的数据
  10. 结构之美:在单链表指定位置插入数据
  11. 结构之美:删除单链表指定位置的数据
  12. 结构之美:单链表逆序
  13. 结构之美:判断单链表中是否有环
  14. 结构之美:获取单链表倒数第N个结点值
  15. 单循环链表的初始化、创建、删除、查找与遍历
  16. 结构之美:双向循环链表的结构与定义

本文地址:http://www.nowamagic.net/librarys/veda/detail/1803,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/1803

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《编译原理(第2版)》 Alfred V. Aho (作者), Monica S.Lam (作者), 赵建华 (译者), 郑滔 (译者), 戴新宇 (译者)

《编译原理(第2版)》全面、深入地探讨了编译器设计方面的重要主题,包括词法分析、语法分析、语法制导定义和语法制导翻译、运行时刻环境、目标代码生成、代码优化技术、并行性检测以及过程间分析技术,并在相关章节中给出大量的实例。与上一版相比,《编译原理(第2版)》进行了全面的修订,涵盖了编译器开发方面的最新进展。每章中都提供了大量的系统及参考文献。《编译原理(第2版)》是编译原理课程方面的经典教材,内容丰富,适合作为高等院校计算机及相关专业本科生及研究生的编译原理课程的教材,也是广大技术人员的极佳参考读物。

更多计算机宝库...