C语言：静态链表和动态链表

2021-03-10 08:29

阅读：637

标签：序号 mamicode 约瑟夫环问题静态取值需要动态分配固定循环

静态链表

1. 用结构体数组的方式声明，所占的存储空间是固定的，例如：

struct StructName{

　　int a;

　　long b;

　　char c[size];

　　struct StructName *next; //静态链表区别于数组的地方，包含了一个指向同类型结构体的指针

}List[LEN]; //一条长度固定的链表

2. 链表访问其中一个结点的数据不能像结构体数组那样用点运算符取值，需要用"->"来访问其中的数据

例如：

struct Node a,*p=&a; //同时定义了一个结构体a和一个结构体指针p；

a.next = &a;

p -> next = p; //两者区别

3. 代码练习，用静态链表解决约瑟夫环问题

技术图片

#include 
#include 

int main()
{
    struct List{
        int no;
        struct List *next;
    }list[13];    //建立静态链表
    int i,n=1;
    struct List *p = list;    //遍历指针
    for(i=0;inext == p)
            break;
        if(n+1 == 3)  //下一个结点是3
        {
            n = 1;
            p->next = (p->next)->next;   //将下一个结点删除
        }
        else
            n++;
        p = p->next;
    }
    printf("最后留下来的人最初的序号为 %d\n",p->no);

    return 0;
}

动态链表

1. 动态分配存储空间，会用到malloc和free函数，值得注意的一点是调用malloc()之后返回的指针不是结构体类型的指针，需要强制类型转换

动态建立链表的过程中需要三个结构体指针标定位置：

头指针head指向链表第一个结点，p1指向当前结点，p2指向下一个结点

如图所示

技术图片

2. 动态链表的插入和删除就是在修改对应结点的指针指向，程序结束要遍历所有结点用free函数释放分配的存储空间

3. 在C++和Java中几乎不使用结构体来构造链表，你可以使用Vector和ArrayList动态数组满足你的要求，这些数据结构隐去了实现细节，你只需要知道怎么用就好

除了按照分配存储空间的方式将链表分为静态和动态链表，链表还可以按照指向的复杂性分为单向、双向和循环链表等等

1.单向链表

一个结点只包含一个指向的链表，只具备顺推功能，不具备回溯能力

2.双向链表

一个结点包含prev和next两个指向的指针，既可以顺推也可以回溯

3.循环链表

技术图片

循环链表也有单项和双向之分，图中描述的是单向循环链表

最后，链表是一类复杂的数据结构，光理解它是远远不够的，运用并掌握它才是难点。

C语言：静态链表和动态链表

标签：序号 mamicode 约瑟夫环问题静态取值需要动态分配固定循环

原文地址：https://www.cnblogs.com/lemon-567/p/14155091.html

上一篇：有人说C++20变得越来越陌生，从颜值派到理性派，浅谈对C++的看法！

下一篇：C++ 时间 & 日期

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：C语言：静态链表和动态链表
文章链接：http://soscw.com/index.php/essay/62679.html

亲，登录后才可以留言！

C语言：静态链表和动态链表

静态链表

动态链表

除了按照分配存储空间的方式将链表分为静态和动态链表，链表还可以按照指向的复杂性分为单向、双向和循环链表等等

评论

热门文章

推荐文章

最新文章

置顶文章