精华内容
下载资源
问答
  • 单链表

    千次阅读 多人点赞 2019-08-05 15:50:59
    带头结点和不带头结点的单链表 带头结点的单链表,头指针head指向头结点,头结点的值域不包含任何信息,从头结点之后的结点开始存储信息。 头指针head不等于NULL,head->next等于NULL时,链表为空。 ...

     

     一、基本概念

    带头结点和不带头结点的单链表

    带头结点的单链表,头指针head指向头结点,头结点的值域不包含任何信息,从头结点之后的结点开始存储信息。

    头指针head不等于NULL,head->next等于NULL时,链表为空。

     

    单链表结点定义

    typedef struct LNode{

        int data;   //data存放结点数据域

       struct LNode *next;    //指向后继结点的指针

    }LNode;  //定义单链表结点类型

    引入头结点的好处:(1)无论链表是否为空,头指针总指向头结点的非空指针,(2)开始结点的位置存放在头结点的指针域中,所以链表的第一个位置上的操作和其他位置一致,方便

    1. 建立单链表

    (1)头插法

    从一个空表开始,生成新结点,将读到的数据存放到新结点的数据域,然后将新结点插入到当前两边的表头,即头结点之后

    (头插法生成的链表中结点的次序和输入数据的顺序不一致)

    关键代码:

    LNode *s;int x;
    L=(LinkList)malloc(sizeof(LNode)); //创建头结点
    L->next=NULL;                  //初始链表为空
    /*....*/
    s=(LNode)malloc(sizeof(LNode));  //创建新结点
    s->data=x;
    s->next=L->next;
    L->next=s;                        //将新结点插入表中,L尾头指针
    

    (2)尾插法

    将新结点插入到当前链表的表尾,为此必须增加一个尾指针r,使其始终指向当前链表的尾结点。

    int x;
    L=(LinkList)malloc(sizeof(LNode));
    LNode *s,*r=L;  //r为表尾指针
    /***/
    while(x!=maxSize){
    s=(LNode *)malloc(sizeof(LNode));
    s->data=x;
    r->next=s;
    r=s;                  //r指向新的表尾结点
    }
    r->next=NULL;      //尾节点置空
    return L;

     2.按序号查找结点值(O(n))

    在单链表中从第一个结点出发,顺指针next域逐个往下搜索,直到找到第i个结点为止,否则返回最后一个结点指针域NULL;

    LNode *GetElem(LinkList L,int i){
        int j=1;          //计数,初始为1
        LNode *p=L->next;   //头结点指针赋给p
        if(i==0)
            return L;    //若i等于0,返回头结点
        if(i<1)
            return NULL; //若i无效,返回NULL
        while(p&&j<i){  //从第1个结点查找第i个结点
            p=p->next;
            j++;
    }
    return p;
    }

    3.按值查找(O(n))

    从单链表第一个结点开始,由前往后依次比较表中个结点数据域的值,若某个结点数据域的值等于给定值e,则返回该结点指针;若整个单链表无值相等的结点,则返回NULL;

    LNode *Locate(LinkList L,ElemType e){
            LNode *p=L->next;
            while(p!=NULL &&p->data!=e) //从第1个结点开始查找data域为e的结点
                p=p->next;    
    
            return p;    //找到后返回该结点指针,否则返回NULL
    }

    4.插入(O(n))

    要把x插入到第i个位置,先检查位置是否合法,然后找到待插入位置的前驱结点,即第i-1个结点,再往其后插入新结点

    步骤(1)调用序号查找算法GetElem  查找第i-1个结点。假设返回的第i-1个结点为*p

              (2)令新结点*s的指针域指向*p的后继结点,

               (3)再令结点*P的指针域指向新插入的结点*s

    p=GetElem(L,i-1);//查找插入为止的前驱结点
    s->next=p->next;   //图中1
    p->next=s;         //图中2

     

    5.删除(O(n))

    要删除第i个结点。先检查删除位置的合法性,然后查找表中第i-1个位置,即被删除结点的前驱结点,再将其删除

    假设结点*p为找到的被删除结点的前驱结点,为实现这一操作的逻辑关系的变化,仅需修改*p的指针域,即将*p的指针域next指向*q的下一结点

     

    p=GetElem(L,i-1);      //查找删除位置的前驱结点
    q=p->next;              //令q指向被删除结点
    p->next=q->next;            //将*q结点从链中断开
    free(q);                  //释放结点的存储空间

     拓展删除指定结点:

    先从表头结点开始顺序找到其前驱结点,然后执行删除

    p=p->netx;   //令q指向*p的后继结点

    p->data=p->next->data;    //和后继结点交换数据域

    p->next=q->next;       //将*q结点从链中断开

    free(q)

    6.求表长操作

    实质为计算数据结点(不含头结点)的个数,需要从第一个开始遍历全部结点。

    *p=first->link;
    int count=0;
    while(p!=NULL){
        p->link;count++;
    }
    return count;

     

    #include <stdio.h>
    #include <stdlib.h>
    //头插法
    #define SIZE 5
    
    #define ERROR 1
    #define OK     0
    
    /* 数据元素类型 */
    typedef int ListType;
    
    /* 单链表结点定义 */
    typedef struct LNode
    {
     ListType data;      // 数据域
     struct LNode *next; // 指针域,指向直接后继元素
    }LNode;
    
    /* 函数的声明 */
    LNode *HeadCreateList(void);// 使用头插法创建一个单链表
    LNode *TailCreateList(void);// 使用尾插法创建一个单链表
    void PrintfList(LNode *L);  // 打印输出链表
    
    
    
    int main(void)
    {
     LNode *L1 = NULL;
     LNode *L2 = NULL; 
     
     /* 使用头插法创建单链表 */
     L1 = HeadCreateList();
     printf("头插法创建的链表为:");
     PrintfList(L1);
     return 0;
    }
    
    
    LNode *HeadCreateList(void)//头插法 
    {
     int i;
     LNode *L;  // 头结点
     LNode *s;  // 新结点
     L->next = NULL;  // 此时链表为空
     // 创建链表
     for (i = 0; i < 5; i++)
     {
       // 创建新结点
       s = (LNode*)malloc(sizeof(LNode));
       s->data = i;
       // 使用头插法把新元素插入到链表中
       s->next = L->next;  // 新结点的next指针指向头结点
       L->next = s;    // 头结点的next指针指向新结点
     }
     
     return L;
    }
    
    
    
    void PrintfList(LNode *L)
    {
     LNode *temp = L;
     
     while(temp->next)
     {
       temp = temp->next;
       printf("%d ",temp->data);
     }
     printf("\n\n");
    }

     

    展开全文
  • 单链表插入 链表插入节点 单链表删除节点 链表删除节点 链表输出 链表输...

    单链表插入

    链表插入节点

    单链表删除节点

    链表删除节点

    链表输出

    链表输出

    链表释放内存空间

    链表释放内存空间

    展开全文
  • 单链表中我们在程序的最后加上一个释放内存的方法或者操作,这是一个很好的习惯。 但是在销毁过程当中,我遇到了一个问题,那就是释放的顺序应该是怎么样的,刚开始的时候我很思维习惯的用“数据输出”的方法,...

    在单链表中我们在程序的最后加上一个释放内存的方法或者操作,这是一个很好的习惯。

    但是在销毁过程当中,我遇到了一个问题,那就是释放的顺序应该是怎么样的,刚开始的时候我很思维习惯的用“数据输出”的方法,顺序的将内存释放了,但是出现了内存错误(泄露),百思不其解。

    后来发现,原来是释放的顺序搞反了,如果顺序释放的话,释放了第一个节点,其后的节点都丢失了,因为其后的节点都是通过头结点来寻找的。

    下面附上做实验时候的内存释放代码:如果有不对的地方,请大家纠正

    void Destroy(AddressBook &ab)
    {
    	Student * temp;
    	Student * del;
    	del = ab.first->next;
    	temp = ab.first ->next->next;
    	while(temp)
    	{
    		free(del);
    		del = temp;
    		temp = temp->next;
    	}
    	free(del);
    	free(ab.first);
    	ab.length = 0;
    }
    展开全文
  • 3.2.2 单链表类节点的释放

    千次阅读 2013-08-13 13:03:52
    本程序在于演示最基础单链表的Node(节点)内存分配与释放 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 ...
    本程序在于演示最基础单链表的Node(节点)内存分配与释放
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    /***********************************************************/
    // 程序名称:list.cpp
    // 程序目的:设计一个节点的配置与释放程序
    // 程序来源:数据结构(C语言版) P-58
    // 日期:2013-8-13 12:23:16
    /***********************************************************/


    #include <stdio.h>
    #include <stdlib.h>
    #define Max  10

    struct List      // 节点结构的声明
    {
         int  Number;
         char Name[Max];
         struct list* Next;
    };
    typedef  struct List Node;
    typedef Node* Link;

    int main( void)
    {
        Link New;            // 节点声明
         int DataNum;         // 数据编号
         char DataName[Max];  // 数据名称
         int i;

        New = (Link)malloc( sizeof(Node));       // 内存配置
         if ( NULL == New)
            printf( "内存动态分配失败!!\n");     // 内存配置失败
         else
        {
            printf( "请输入数据编号:");
            scanf( "%d", &DataNum);
            printf( "请输入数据名称:");
            scanf( "%s", DataName);

            New->Number = DataNum;
             for (i =  0; i <= Max; i++)
            {
                New->Name[i] = DataName[i];
            }
            New->Next =  NULL;

            printf( "\n####输出数据####\n");
            printf( "数据编号:%d\n", New->Number);
            printf( "数据名称:%s\n", New->Name);
        }

        free(New);   // 内存释放

         return  0;
    }
    输出结果:

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 23,749
精华内容 9,499
关键字:

单链表如何释放