线性表之单链表(代码片段)

关键词：

在学完线性表之后，总结一下顺序表的优缺点

优点

• 无须为元素之间的逻辑结构增添额外的储存空间，自成一体。
• 随机存取，十分方便。

缺点

• 空间利用率不高，容易造成“碎片”。
• 插入删除操作需要移动大量的元素。
• 当线性表的长度变化较大时，难以确定储存空间的容量。

而单链表可以很好的弥补顺序表的这些缺点。

一、实现方式

typedef int Elemtype;
typedef struct Node

    Elemtype e;//数据域 
    struct Node *next;//指针域
 Node , *LinkList;

二、操作集

初始化

void createList( LinkList *L )

    *L = ( LinkList ) malloc ( sizeof(Node) );
    (*L)->next = NULL;
    (*L)->e = 0;

创建头结点，头结点储存表长。

创建整张表

void createListHead( LinkList *L , int n )

    LinkList p;
    int i;
    srand( time(0) );
    //创建头结点
    *L = ( LinkList ) malloc ( sizeof(Node) );
    (*L)->next = NULL;
    
    for( i = 0 ; i < n ; i++ )
    
        p = ( LinkList ) malloc ( sizeof(Node) );
        p->e = rand() % 100 + 1;
        p->next = (*L)->next;
        (*L)->next = p;
     

使用头插法创建一张n个1-100数的随机数表。

void createListTail( LinkList *L , int n )

    LinkList p,r;//p新节点指针，r尾指针 
    int i;//节点数目 
    srand(time(0));
    
    //创建头结点 
    *L = ( LinkList ) malloc ( sizeof(Node) );
    r = *L;//尾指针先指向头节点 
    
    for( i = 0 ; i < n ; i++ )
    
        p = ( LinkList ) malloc ( sizeof(Node) );
        p->e = rand() % 100 + 1;
        r->next = p;
        r = p;//指向尾部 
    
    r->next = NULL;//最后指向空 
 

使用头插法创建一张n个1-100数的随机数表。

读取

int getList( LinkList L , int i, Elemtype *e ) 

    //计数器 
    int j = 1;
    //指向第一个节点 
    LinkList p = L->next;
    
    while( p != NULL && j < i )
    
        p = p->next;
        j++;
    
    
    /*第i个元素不存在*/
    if( !p || j > i )
    
        return 0;
    
    
    *e = p->e;
    return 1;  

插入操作

int insertList( LinkList *L , int i , Elemtype e )

    int j = 1;
    LinkList p = *L;
    
    while( p && j < i )
    
        p = p->next;
        j++;
    
    
    //该位置不存在，超过表长或者为负数 
    if( !p || j > i )
    
        return 0;
    
    
    LinkList s = ( LinkList ) malloc ( sizeof(Node) );
    s->e = e;
    s->next = p->next;
    p->next = s;
    (*L)->e+=1;
    return 1;

步骤见下图，注意顺序，一步错步步错。

删除操作

int deleteList( LinkList *L , int i , Elemtype *e )

    int j = 0;
    LinkList q,p;
    
    p = *L;//头指针赋值
    j = 1;
    
    //找到被要删除元素的上一个元素 
    while( p->next && j < i )
    
        p = p->next;
        j++;
    
    
    /*第i个元素不存在*/ 
    if( !(p->next) || j > i )
    
        return 0;
    
    
    q = p->next;
    p->next = p->next->next;
    *e = q->e;
    free(q);
    
    return 1;

删除节点的过程，看图更容易理解

遍历操作

void printList( LinkList L )

    LinkList p = L->next;
    while( p )
    
        printf("%d ",p->e);
        p = p->next;
    
    printf("
打印完成");

清空操作

int ClearList( LinkList *L )

    LinkList p,q;
    p = (*L)->next;//指向第一个节点
    
    while( p!=NULL )
    
        q = p->next;
        free(p);
        p = q;
     
    (*L)->next = NULL;
    return 1;

主函数

int main()

    Node *L;
    Elemtype a;
    
    createListHead(&L,10);
    printList(L);
    
    return 0;

纸上得来终觉浅，绝知此事要躬行

——陆游

线性表之单链表(代码片段)

在学完线性表之后，总结一下顺序表的优缺点优点无须为元素之间的逻辑结构增添额外的储存空间，自成一体。随机存取，十分方便。缺点空间利用率不高，容易造成“碎片”。插入删除操作需要移动大量的元素。当线性... 查看详情

算法习题---线性表之单链表逆序打印(代码片段)

一：题目逆序打印单链表中的数据，假设指针指向单链表的开始结点二：思路1.可以使用递归方法，来进行数据打印2.可以借助数组空间，获取长度，逆序打印数组3.若是可以，对链表数据使用头插法，逆序排列，然后正序打印即... 查看详情

数据结构学习总结线性表之单链表(代码片段)

   一，回忆链表 　链表，别名链式存储结构或单链表，用于存储逻辑关系为"一对一"的数据。与顺序表不同，链表不限制数据的物理存储状态，换句话说，使用链表存储的数据元素，其物理存储位置是随机的。&nbs... 查看详情

数据结构线性表之实现单循环链表(代码片段)

数据结构线性表之实现单循环链表数据结构线性表之实现单循环链表相关文章单循环链表单循环链表定义数据结构线性表之实现单循环链表相关文章数据结构线性表之概念(一)数据结构线性表之抽象基类(二)数据结构线性表之实... 查看详情

算法习题---线性表之单链表的查找(代码片段)

一：问题已知一个带头结点的单链表，结点结构为（data，link）假设该链表只给出了头指针list，在不改变链表的前提下，设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数），若查找成功，算法输出该... 查看详情

数据结构与算法-线性表之循环链表(代码片段)

前言：前面几篇介绍了线性表的顺序和链式存储结构，其中链式存储结构为单向链表（即一个方向的有限长度、不循环的链表），对于单链表，由于每个节点只存储了向后的指针，到了尾部标识就停止了向后链的操作。也就是说... 查看详情

线性表之链表(代码片段)

单链表也是一种链式存取的线性表，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，以next指针指向下一个节点而链接起来，相比于顺序表，链表有着快速增加，删除节点的优势，其节点... 查看详情

数据结构之单链表(代码片段)

...构3.定义单链表结构代码实现4.单链表的增删改查4.1单链表之尾插4.1.1单链表之开辟空间4.1.2单链表之打印值4.2单链表之头插4.3单链表之尾删4.4单链表之头删4.5单链表之查链表长度4.6单链表之判断链表是否为空4.7单链表之查找某一... 查看详情

线性表之单链表实现

for(循环）还是while(循环）循环之后，i和条件值相等。#include<stdio.h>#include<malloc.h>#include<stdlib.h>typedefstructnode{ intdata; structnode*next;}NODE,*PNODE;PNODEcreateList(PNODE);voidtravelList(PNO 查看详情

03线性表之链表(代码片段)

肚子饿了就要吃  ~  嗝 ———路飞 1.本章重点链表表示和实现（单链表+双链表）链表的常见OJ题顺序表和链表的区别和联系2.为什么需要链表引子：顺序表的问题及思考(1)动态顺序表特点：插入数据，... 查看详情

单链表之crud操作(代码片段)

package链表.单链表crud;publicclassSingleLinkedListDemopublicstaticvoidmain(String[]args)SingleLinkedListsll=newSingleLinkedList();HeroNodeheroNode1=newHeroNode(1,"虚空掠夺者");HeroNodeheroNode 查看详情

数据结构学习笔记二线性表之链表篇（双向链表）(代码片段)

链表根据带头不带头、单向或双向、循环非循环三个方面可组成成八种类型。这八种类型中仅有两种是我们常用的。第一种是单向不带头非循环链表，也就是单链表。单链表因为结构简单，但是实际操作比较复杂，所... 查看详情

线性链表之顺序表

/* @content线性链表之顺序表 @date2017-3-211:06 @authorJohnnyZen *//*线性表  顺序表  链式表[带头指针/不带头指针]   单链表  循环单链表 双向链表循环双链表   ADT& 查看详情

数据结构与算法-线性表之静态链表(代码片段)

前言：前面介绍的线性表的顺序存储结构和链式存储结构中，都有对对象地引用或指向，也就是编程语言中有引用或者指针，那么在没有引用或指针的语言中，该怎么实现这个的数据结构呢？一、简介　　定义：用数组代替指针... 查看详情

线性表之顺序表(代码片段)

线性表的结构体定义：#defineMaxSize100typedefstructintdata[MaxSize];intlength;Sqlist;　　顺序表在内存中以数组形式保存，是一组连续的内存空间。顺序表基本算法：构造一个空的线性表：//初始化线性表STATUSInitList(Sqlist&L)//置表长为0L.len... 查看详情

数据结构之双链表(代码片段)

...项目的建造双链表结点的定义双链表的各种方法实现双链表之新建结点双链表之初始化双链表之判空双链表之求具体元素数量双链表之打印链表内容双链表之尾插双链表之尾删双链表之头插双链表之头删双链表之查找值双链表之... 查看详情

单链表之头插法的理解！(代码片段)

如图:头结点是*L。。。头结点一般储存单链表的长度的信息。首节点是（*L）->next。。。是储存元素的值和下一个元素的位置的信息。现在我想插入一个新的节点p。。。第一：新节点的指针域指向首节点。第二：修改头结点的... 查看详情

数据结构之顺序表(代码片段)

...找元素操作顺序表之任意位置插入顺序表之任意位置擦除线性表之查看有多少元素线性表之修改任意位置线性表之销毁空间综合SeqList.h文件内容SeqList.c文件内容前言讲完算法效率,就正式开始我们的数据结构 查看详情