2024年11月

在很多程序中,封装常用消息对话框有很多好处,尤其是在 GUI 应用程序中,本篇随笔结合.net 开发Winform界面的经验,对使用wxpython开发中 wx.MessageDialog 和 wx.lib.agw.genericmessagedialog.GenericMessageDialog 两种不同消息对话框的处理,对其进行简单封装,以适应程序开发的需要。

1、消息对话框的封装处理的优势

对常用消息对话框的封装处理,具有以下是一些主要的优点:

1.
代码复用

封装消息对话框可以避免重复代码。你可以定义一个统一的函数或类来处理所有消息对话框,从而在多个地方复用这段代码。

2.
一致性

通过封装,你可以确保所有消息对话框的外观和行为一致。这有助于提高用户体验,使用户在应用程序中获得统一的交互方式。

3.
简化调用

封装可以简化调用过程。你可以将常用的参数设置(如标题、图标、按钮类型等)预先定义好,从而在调用时减少参数输入。

4.
易于维护

当需要更改对话框的行为或样式时,只需在封装函数中进行修改,而不必在应用程序中的每个调用点进行更改。这使得维护变得更加简单和高效。

5.
增强可读性

通过使用封装的函数或类,代码变得更易读。其他开发者可以一眼看出对话框的作用,而不必深入了解其具体实现。

6.
集中管理

封装有助于集中管理对话框的逻辑,比如处理用户输入、响应用户选择等。这样可以更方便地进行逻辑更新或错误处理。

7.
扩展性

如果将来需要增加新的对话框或修改现有对话框的逻辑,封装使得扩展更加容易。你可以在封装的基础上进行扩展,而不影响现有的代码结构。

我在早期开发Winform的时候,对消息对话框进行了一些简单的封装,在随笔《
厚积薄发,丰富的公用类库积累,助你高效进行系统开发(2)----常用操作
》中有介绍。

封装的消息提示对话框包括个各种常用的对话框,如下所示:

2、对使用wxpython开发中常用消息对话框的封装

为了方便,我们先写一个页面来测试相关消息对话框的封装处理,如下界面所示。

wxpython开发中 wx.MessageDialog 和 wx.lib.agw.genericmessagedialog.GenericMessageDialog 都时跨平台支持的,GenericMessageDialog
是 wxPython 的一个扩展库,提供了一个通用的消息对话框类,用于在不同平台上显示消息框。这个类是跨平台的,支持以下主要平台:

  1. Windows
    :在 Windows 操作系统上,
    GenericMessageDialog
    会使用系统样式来渲染对话框。
  2. macOS
    :在 macOS 上,它会遵循 Cocoa 的界面风格。
  3. Linux
    :在各种 Linux 发行版上,它会适应 GTK 或 Qt(如果 wxPython 是基于这些库构建的)风格。

MessageDialog  和
GenericMessageDialog
旨在提供一致的用户体验,无论在哪个平台上运行。

MessageDialog和GenericMessageDialog 的差别

wx.MessageDialog

wx.lib.agw.genericmessagedialog.GenericMessageDialog
是 wxPython 中用于显示消息对话框的两种不同类,它们之间有一些主要的差别:

1) 类别及实现方式

  • wx.MessageDialog
    :


    • 是 wxPython 的内置类,使用系统原生的对话框实现。
    • 适应系统的外观和风格,因此在不同平台上看起来会有所不同。
    • 通常用于显示简单的消息、确认或警告对话框。
  • wx.lib.agw.genericmessagedialog.GenericMessageDialog
    :


    • 是 wxPython 的 AGW(Advanced Generic Widgets)库中的一部分,提供了一个更灵活的通用消息对话框实现。
    • 允许更多的自定义选项和更复杂的布局,适合需要更多控制和自定义的场景。
    • 可以在所有平台上保持一致的外观,因为它不依赖于系统原生对话框。

2)自定义能力

  • wx.MessageDialog
    :


    • 自定义选项有限,主要集中在按钮、图标和消息文本。
    • 不支持复杂的布局或多种控件的组合。
  • wx.lib.agw.genericmessagedialog.GenericMessageDialog
    :


    • 提供更多的自定义选项,如设置按钮图标、对话框的最小尺寸和布局。
    • 可以添加更多控件(如文本框、图片等),适合更复杂的用户交互需求。

3) 使用场景

  • wx.MessageDialog
    :


    • 适用于简单的确认消息、警告或信息提示场景。
    • 更适合于需要快速实现标准对话框的情况。
  • wx.lib.agw.genericmessagedialog.GenericMessageDialog
    :


    • 更适合于需要更高自定义和灵活性的应用程序。
    • 适用于复杂的对话框场景,比如需要显示额外信息或允许用户输入的情况。

如果你的需求简单,只需显示消息并获取用户确认,使用 wx.MessageDialog 是更简单的选择。
如果你需要更多的自定义功能或希望在多个平台上保持一致的外观,可以考虑使用 GenericMessageDialog。

消息对话框的常用代码如下所示。

    defShowMessageDialog(self):#创建消息对话框
        dlg =wx.MessageDialog(self,"This is a message dialog example.\nWould you like to proceed?","Confirmation", 
wx.YES_NO
| wx.CANCEL |wx.ICON_QUESTION)#显示对话框并处理用户选择 result =dlg.ShowModal()if result ==wx.ID_YES:
wx.MessageBox(
"You clicked Yes!", "Info")elif result ==wx.ID_NO:
wx.MessageBox(
"You clicked No!", "Info")elif result ==wx.ID_CANCEL:
wx.MessageBox(
"You clicked Cancel!", "Info")

dlg.Destroy()
#销毁对话框

以及

    defon_show_dialog(self, event):#创建 GenericMessageDialog
        dlg =GMD.GenericMessageDialog(self,"This is a message.","Message Title",
style
=wx.OK |wx.CANCEL)#设置图标(可选) dlg.SetYesNoCancelBitmaps(wx.ArtProvider.GetBitmap(wx.ART_INFORMATION, wx.ART_MESSAGE_BOX))#显示对话框 result =dlg.ShowModal()if result ==wx.ID_OK:print("OK button clicked")elif result ==wx.ID_CANCEL:print("Cancel button clicked")

dlg.Destroy()

如果每次这样调用,我们需要了解很多相关的参数信息,一般我们只需要传入一些简单的信息提示即可,因此需要对它们进行简单的封装。

我们定义一个类,提供最原始简单的显示消息的处理函数,然后再在基础上进行特殊的简化封装即可。

classMessageUtil:"""封装了常用的消息对话框,以方便使用常用对话框消息。
包括提示信息、警告信息、错误信息、确认信息、询问信息、输入信息、
选择信息、多选信息、文件选择信息、目录选择信息、字体选择信息、颜色选择信息、进度条信息等。
"""@staticmethoddefshow_message(parent, message, caption, style):"""显示消息对话框-使用GenericMessageDialog实现"""dlg=GMD.GenericMessageDialog(parent, message, caption, style)
dlg.SetIcon(images.appIcon.GetIcon())
#设置窗口图标 result=dlg.ShowModal()
dlg.Destroy()
returnresult

@staticmethod
defshow_message2(parent, message, caption, style):"""显示消息对话框-使用wx.MessageDialog 实现"""dlg=wx.MessageDialog(parent, message, caption, style)

result
=dlg.ShowModal()
dlg.Destroy()
return result

其中 show_message 和show_message2 是针对两者不同消息类的封装,我们可以根据实际需要替换来用即可。如对于常规的提示消息、告警、错误消息框,简单设置一下参数即可。

    #常用消息对话框的标题
    CAPTION_TIPS = "提示信息"CAPTION_WARNING= "警告信息"CAPTION_ERROR= "错误信息"CAPTION_CONFIRM= "确认信息"@staticmethoddef show_tips(parent, message, caption=CAPTION_TIPS):"""显示一般的提示信息"""
        returnMessageUtil.show_message(
parent, message, caption, wx.OK
|wx.ICON_INFORMATION
)
@staticmethod
def show_warning(parent, message, caption=CAPTION_WARNING):"""显示警告信息""" returnMessageUtil.show_message(
parent, message, caption, wx.OK
|wx.ICON_WARNING
)

@staticmethod
def show_error(parent, message, caption=CAPTION_ERROR):"""显示错误信息""" return MessageUtil.show_message(parent, message, caption, wx.OK | wx.ICON_ERROR)

而对于提供更多按钮的,也是设置参数即可,如下所述。

@staticmethoddef show_yes_no_tips(parent, message, caption=CAPTION_TIPS):"""显示询问用户信息,并显示提示标志"""
        returnMessageUtil.show_message(
parent, message, caption, wx.YES_NO
|wx.ICON_INFORMATION
)

@staticmethod
def show_yes_no_warning(parent, message, caption=CAPTION_WARNING):"""显示询问用户信息,并显示警告标志""" returnMessageUtil.show_message(
parent, message, caption, wx.YES_NO
|wx.ICON_WARNING
)

@staticmethod
def show_yes_no_error(parent, message, caption=CAPTION_ERROR):"""显示询问用户信息,并显示错误标志""" returnMessageUtil.show_message(
parent, message, caption, wx.YES_NO
|wx.ICON_ERROR
)

另外,wxpython还提供了TextEntryDialog、SingleChoiceDialog、MultiChoiceDialog等对话框,我们也可以简单封装一下使用。

@staticmethoddefshow_input_dialog(parent, message, caption, default_value):"""显示输入对话框"""dlg=wx.TextEntryDialog(parent, message, caption, default_value)
result
=dlg.ShowModal()if result ==wx.ID_OK:returndlg.GetValue()else:returnNone

@staticmethod
defshow_choice_dialog(parent, message, caption, choices):"""显示选择对话框"""dlg=wx.SingleChoiceDialog(parent, message, caption, choices)
result
=dlg.ShowModal()if result ==wx.ID_OK:returndlg.GetStringSelection()else:returnNone

@staticmethod
defshow_multi_choice_dialog(parent, message, caption, choices):"""显示多选对话框"""dlg=wx.MultiChoiceDialog(parent, message, caption, choices)
result
=dlg.ShowModal()if result ==wx.ID_OK:returndlg.GetSelections()else:return None

最后如下效果所示。

这样我们在程序里面统一调用就会有相同的效果,而且简化了很多不必要的参数。

MessageUtil.show_tips(None, "This is a test program.", "关于")

以上就是一些日常开发的函数处理和抽象处理,主要就是为了简化实际开发的时候的一些复杂度,并提供统一的界面效果。

最小系统

创建API项目

创建API项目并安装以下依赖

修改Program.cs为以下内容

using BookApp;

var builder = WebApplication.CreateBuilder(args);

await builder.AddApplicationAsync<BookAbpModule>();

builder.Host.UseAutofac();

var app = builder.Build();

await app.InitializeApplicationAsync();

await app.RunAsync();

创建BookAbpModule.cs

using Microsoft.OpenApi.Models;
using Volo.Abp;
using Volo.Abp.Application;
using Volo.Abp.AspNetCore.Mvc;
using Volo.Abp.Autofac;
using Volo.Abp.Domain;
using Volo.Abp.Modularity;
using Volo.Abp.Swashbuckle;

namespace BookApp
{
    [DependsOn(
        typeof(AbpAutofacModule),
        typeof(AbpAspNetCoreMvcModule),
        typeof(AbpSwashbuckleModule)
    )]
    public class BookAbpModule : AbpModule
    {
        override public void ConfigureServices(ServiceConfigurationContext context)
        {
            ConfigureSwaggerServices(context.Services);
        }


        override public void OnApplicationInitialization(ApplicationInitializationContext context)
        {
            var app = context.GetApplicationBuilder();
            var env = context.GetEnvironment();

            app.UseStaticFiles();
            app.UseRouting();

            app.UseSwagger();
            app.UseAbpSwaggerUI(options =>
            {
                options.SwaggerEndpoint("/swagger/v1/swagger.json", "BookApp API");
            });

            app.UseEndpoints(endpoints =>
            {
                endpoints.MapControllers();
            });
        }

        private void ConfigureSwaggerServices(IServiceCollection services)
        {
            services.AddAbpSwaggerGen(
                options =>
                {
                    options.SwaggerDoc("v1", new OpenApiInfo { Title = "BookApp API", Version = "v1" });
                    options.DocInclusionPredicate((docName, description) => true);
                    options.CustomSchemaIds(type => type.FullName);
                }
            );
        }
    }
}

模块化编程

新建AbpModuleA类库并引用Volo.Abp.Core

//加AbpModuleAModule.cs
using System.IO;

using System;
using Volo.Abp.Modularity;
using Volo.Abp;

namespace AbpModuleA
{
    public class AbpModuleAModule: AbpModule
    {
        public override void PreConfigureServices(ServiceConfigurationContext context)
        {
            Console.WriteLine("AbpModuleA.PreConfigureServices ");
        }

        override public void PostConfigureServices(ServiceConfigurationContext context)
        {
            Console.WriteLine("AbpModuleA.PostConfigureServices");
        }

        public override void ConfigureServices(ServiceConfigurationContext context)
        {
            Console.WriteLine("AbpModuleA.ConfigureServices");


        }

        public override void OnApplicationInitialization(ApplicationInitializationContext context)
        {
            Console.WriteLine("AbpModuleA.OnApplicationInitialization");

        }

        public override void OnPreApplicationInitialization(ApplicationInitializationContext context)
        {
            Console.WriteLine("AbpModuleA.OnPreApplicationInitialization");
        }
        override public void OnPostApplicationInitialization(ApplicationInitializationContext context)
        {   
            Console.WriteLine("AbpModuleA.OnPostApplicationInitialization");
        }
    }
}

新建AbpModuleB类库并引用Volo.Abp.Core

//加AbpModuleBModule.cs
using System.IO;

using System;
using Volo.Abp.Modularity;
using Volo.Abp;

namespace AbpModuleB
{
    public class AbpModuleBModule: AbpModule
    {
        public override void PreConfigureServices(ServiceConfigurationContext context)
        {
            Console.WriteLine("AbpModuleB.PreConfigureServices");
        }

        override public void PostConfigureServices(ServiceConfigurationContext context)
        {
            Console.WriteLine("AbpModuleB.PostConfigureServices");
        }

        public override void ConfigureServices(ServiceConfigurationContext context)
        {
            Console.WriteLine("AbpModuleB.ConfigureServices");


        }

        public override void OnApplicationInitialization(ApplicationInitializationContext context)
        {
            Console.WriteLine("AbpModuleB.OnApplicationInitialization");

        }

        public override void OnPreApplicationInitialization(ApplicationInitializationContext context)
        {
            Console.WriteLine("AbpModuleB.OnPreApplicationInitialization");
        }
        override public void OnPostApplicationInitialization(ApplicationInitializationContext context)
        {   
            Console.WriteLine("AbpModuleB.OnPostApplicationInitialization");
        }
    }
}

修改Api项目的模块配置文件

//BookAbpModule.cs

using Microsoft.OpenApi.Models;
using Volo.Abp;
using Volo.Abp.Application;
using Volo.Abp.AspNetCore.Mvc;
using Volo.Abp.Autofac;
using Volo.Abp.Domain;
using Volo.Abp.Modularity;
using Volo.Abp.Swashbuckle;
using AbpModuleA;
using AbpModuleB;

namespace BookApp
{
    [DependsOn(
        typeof(AbpAutofacModule),
        typeof(AbpAspNetCoreMvcModule),
        typeof(AbpSwashbuckleModule),
        typeof(AbpModuleAModule),
        typeof(AbpModuleBModule)

    )]
    public class BookAbpModule : AbpModule
    {
        public override void PreConfigureServices(ServiceConfigurationContext context)
        {
            Console.WriteLine("BookAbpModule.PreConfigureServices ");
        }

        override public void PostConfigureServices(ServiceConfigurationContext context)
        {
            Console.WriteLine("BookAbpModule.PostConfigureServices");
        }

        override public void ConfigureServices(ServiceConfigurationContext context)
        {
            Console.WriteLine("BookAbpModule.ConfigureServices");

            ConfigureSwaggerServices(context.Services);
        }


        override public void OnApplicationInitialization(ApplicationInitializationContext context)
        {

            Console.WriteLine("BookAbpModule.OnApplicationInitialization");

            var app = context.GetApplicationBuilder();
            var env = context.GetEnvironment();

            if (env.IsDevelopment())
            {
                app.UseDeveloperExceptionPage();
            }

            app.UseStaticFiles();
            app.UseRouting();

            app.UseSwagger();
            app.UseAbpSwaggerUI(options =>
            {
                options.SwaggerEndpoint("/swagger/v1/swagger.json", "BookApp API");
            });
            app.UseConfiguredEndpoints();
        }

        public override void OnPreApplicationInitialization(ApplicationInitializationContext context)
        {
            Console.WriteLine("BookAbpModule.OnPreApplicationInitialization");
        }
        override public void OnPostApplicationInitialization(ApplicationInitializationContext context)
        {
            Console.WriteLine("BookAbpModule.OnPostApplicationInitialization");
        }

        private void ConfigureSwaggerServices(IServiceCollection services)
        {
            services.AddAbpSwaggerGen(
                options =>
                {
                    options.SwaggerDoc("v1", new OpenApiInfo { Title = "BookApp API", Version = "v1" });
                    options.DocInclusionPredicate((docName, description) => true);
                    options.CustomSchemaIds(type => type.FullName);
                }
            );
        }
    }
}


运行结果

我们会发现,系统加载所有继承AbpModule的文件,并按序运行里面的方法实现对模块的配置

访问数据库

新建Entities文件夹并创建Book.cs

using Volo.Abp.Domain.Entities;

namespace BookApp.Entities
{
    public class Book : Entity<Guid>
    {
        public string Name { get; set; }
    }
}

添加Data目录并添加BookAbpDbContext.cs

using BookApp.Entities;
using Microsoft.EntityFrameworkCore;
using System.Collections.Generic;
using System.Reflection.Emit;
using Volo.Abp.Data;
using Volo.Abp.EntityFrameworkCore;

namespace BookApp.Data
{
    [ConnectionStringName("Default")]
    public class BookAbpDbContext : AbpDbContext<BookAbpDbContext>
    {
        public BookAbpDbContext(DbContextOptions<BookAbpDbContext> options)
        : base(options)
        { }

        public DbSet<Book> Books { get; set; }

        protected override void OnModelCreating(ModelBuilder builder)
        {
            base.OnModelCreating(builder);

            builder.Entity<Book>(b =>
            {
                b.ToTable(nameof(Books));
            });
        }
    }
}

修改BookAbpModule.cs


using Microsoft.OpenApi.Models;
using Volo.Abp;
using Volo.Abp.Application;
using Volo.Abp.AspNetCore.Mvc;
using Volo.Abp.Autofac;
using Volo.Abp.Domain;
using Volo.Abp.Modularity;
using Volo.Abp.Swashbuckle;
using AbpModuleA;
using AbpModuleB;
using Volo.Abp.EntityFrameworkCore;
using BookApp.Data;
using Volo.Abp.EntityFrameworkCore.Sqlite;

namespace BookApp
{
    [DependsOn(
        typeof(AbpAutofacModule),
        typeof(AbpAspNetCoreMvcModule),
        typeof(AbpSwashbuckleModule),
        typeof(AbpDddApplicationModule),
        typeof(AbpDddDomainModule),
        typeof(AbpEntityFrameworkCoreSqliteModule),
        typeof(AbpModuleAModule),
        typeof(AbpModuleBModule)

    )]
    public class BookAbpModule : AbpModule
    {
        public override void PreConfigureServices(ServiceConfigurationContext context)
        {
            Console.WriteLine("BookAbpModule.PreConfigureServices ");
        }

        override public void PostConfigureServices(ServiceConfigurationContext context)
        {
            Console.WriteLine("BookAbpModule.PostConfigureServices");
        }

        override public void ConfigureServices(ServiceConfigurationContext context)
        {
            Console.WriteLine("BookAbpModule.ConfigureServices");

            ConfigureSwaggerServices(context.Services);

            // 使用sqlite作为数据库
            context.Services.AddAbpDbContext<BookAbpDbContext>(options =>
            {
                options.AddDefaultRepositories(includeAllEntities: true);
            });

            Configure<AbpDbContextOptions>(options =>
            {
                options.UseSqlite();
            });
        }


        override public void OnApplicationInitialization(ApplicationInitializationContext context)
        {

            Console.WriteLine("BookAbpModule.OnApplicationInitialization");

            var app = context.GetApplicationBuilder();
            var env = context.GetEnvironment();

            if (env.IsDevelopment())
            {
                app.UseDeveloperExceptionPage();
            }

            app.UseStaticFiles();
            app.UseRouting();

            app.UseSwagger();
            app.UseAbpSwaggerUI(options =>
            {
                options.SwaggerEndpoint("/swagger/v1/swagger.json", "BookApp API");
            });

            app.UseConfiguredEndpoints();
        }

        public override void OnPreApplicationInitialization(ApplicationInitializationContext context)
        {
            Console.WriteLine("BookAbpModule.OnPreApplicationInitialization");
        }
        override public void OnPostApplicationInitialization(ApplicationInitializationContext context)
        {
            Console.WriteLine("BookAbpModule.OnPostApplicationInitialization");
        }

        private void ConfigureSwaggerServices(IServiceCollection services)
        {
            services.AddAbpSwaggerGen(
                options =>
                {
                    options.SwaggerDoc("v1", new OpenApiInfo { Title = "BookApp API", Version = "v1" });
                    options.DocInclusionPredicate((docName, description) => true);
                    options.CustomSchemaIds(type => type.FullName);
                }
            );
        }
    }
}

修改appsettings.json

{
  "ConnectionStrings": {
    "Default": "Data Source=BookApp.db"
  },
  "Logging": {
    "LogLevel": {
      "Default": "Information",
      "Microsoft.AspNetCore": "Warning"
    }
  },
  "AllowedHosts": "*"
}

安装Nuget包"Microsoft.EntityFrameworkCore.Tools",并在在项目根目录下打开命令行工具,依次执行以下命令进行数据迁移和数据库更新:

dotnet ef migrations add InitialCreate
dotnet ef database update

新建Application目录

新建IBookAppService.cs

namespace BookApp.Application
{
    using BookApp.Entities;

    public interface IBookAppService
    {
        Task<string> CreateAsync(string name);
        Task<List<Book>> GetListAsync();
    }
}

新建BookAppService.cs

using BookApp.Entities;
using Volo.Abp.Application.Services;
using Volo.Abp.Domain.Repositories;

namespace BookApp.Application
{
    public class BookAppService : ApplicationService, IBookAppService
    {
        public IRepository<Book, Guid> Repository => LazyServiceProvider.LazyGetRequiredService<IRepository<Book, Guid>>();

        public async Task<string> CreateAsync(string name)
        {
            var book = await Repository.InsertAsync(new Book()
            {
                Name = name
            });

            return book.Name;
        }

        public async Task<List<Book>> GetListAsync()
        {
            var list = await Repository.GetListAsync();
            return list;
        }

    }
}

在Controllers目录新建BookController.cs

using BookApp.Application;
using Microsoft.AspNetCore.Mvc;
using Volo.Abp.AspNetCore.Mvc;
using BookApp.Entities;

namespace BookApp.Controllers
{
    [ApiController]
    [Route("[controller]")]
    public class BookController : AbpController
    {
        private readonly IBookAppService _service;

        public BookController(IBookAppService service)
        {
            _service = service;
        }

        [HttpGet]
        public Task<string> CreateAsync(string name)
        {
            return _service.CreateAsync(name);
        }

        [HttpGet("list")]
        public Task<List<Book>> GetListAsync()
        {
            return _service.GetListAsync();
        }
    }
}

整个文件结构与包引用情况如下

运行结果如下

我们可以通过这两个接口添加与显示Book信息。

参考文章

作者:吴晓阳(手机:13736969112微信同号)

python bytecode解析

前言

我们的电脑是怎么运行的呢?
计算机内部的 CPU 处理器是个硅片,上面雕刻着精心布置的电路,输入特定的电流,就能得到另一种模式的电流,而且模式可以预测,给这些模式起上名字并赋予含义,我们就可以说这种电流模式代表加法,电脑的工作原理就是如此,我们起的这些名字叫做 CPU 指令,有时也被成为机器码。

[引自:James Bennett]
我们的编程语言是怎么运行的呢?一些语言通过编译器,直接将源代码编译成机器码,这些语言就是编译语言,还有一些语言解除解释器,直接在运行时把源代码解释为机器码,这些就是解释型语言。不过还有第三种语言,介于源代码和机器码之间,一些语言编译得到的指令,但是这种指令不能被现有的CPU直接运行,而需要解释器去理解,并将这些指令翻译为真实的 CPU 接受的二进制码,这种中间指令就是我们今天要说的bytecode(字节码),有很多语言属于此类比如java,C#,还有python。

Java编译的字节码运行在java虚拟机上,C#编译的字节码运行在.Net 虚拟机上,而Python 编译的字节码运行在 Python 虚拟机上。

工作原理

CPython解释器在内部会将Python源代码编译成
字节码
,并缓存在
.pyc
​文件中,目的是当再次执行该文件时,直接读取
.pyc
​文件会更快,这样可以避免从源码重新编译到字节码,当然,Python再找到符合文件后,检查此文件的时间戳,如果发现字节码文件(文件在导入时就被编译完成)比源代码文件时间戳早(比如你修改过原文件),那么就会重新生成字节码,否则就会跳过此步骤。如果,Python在搜索时只找到了字节码而没有找到源代码文件,那么就会直接执行字节码文件(如果没有印象,请回想在模块导入时发生了什么)。然后,Python虚拟机执行字节码编译器发出的字节码。

面向栈

这个是在看
码农高天
(一个非常厉害的pytohn核心开发者)的视频里学到的概念,CPython使用一个基于栈的虚拟机,也就是说,它完全是面向栈,这种数据结构的。就是不断地push、pop。

CPython使用3种类型的栈:

  • 调用栈(call stack)。这是运行Python程序的主要结构,它为每个当前活动的函数调用,使用了一个东西
    帧(frame)
    ​,
    栈底是程序的入口点,每个函数调用推送一个新的帧到调用栈,当函数调用返回后,这个帧被销毁
  • 计算栈(evaluation stack,或称数据栈data stack)。在每个帧中,计算栈就是函数运行的地方,运行的代码大多数是由推入到这个栈中的东西组成的。在栈中操作它们,当函数被返回后,销毁它们。
  • 块栈(block stack)。在每个帧中,块栈被Python用于跟踪某些类型的控制结构,如循环、
    try/except
    ​块和
    with ... as ...
    ​块 ,这些控制结构全部被推入到块栈中,当退出这些控制结构式,块栈被销毁,这将帮助Python了解任意给定时刻哪个块是活动的,比如一个continue或者break语句,这些可能影响结果的块。

大多数Python字节码指令操作的是当前调用栈的计算栈,虽然还有些指令可以做其他的事情,比如跳转到指定指令,或者操作块栈。

字节码的阅读

其实还有
代码对象

字节码的工作
这两个概念没说,因为本文主要讲怎么阅读字节码,能够通过字节码手搓出py源码(是的,我是个CTFer),想了解更多的可以去本文末的推荐链接里看。

dis模块

因为python代码运行是到字节码再到机器码一气呵成的,我们想要看到中间指令,需要借助python的标准库dis模块,它可以将py代码翻译成字节码。如下:


image

案例

2024网鼎杯青龙组初赛的MISC02题目(1 解),是一个linux内存镜像取证,前面繁琐的步骤略过,最后一步获得一个 flag.txt 文件,里面是python字节码,明显需要我们手搓还原py代码,如下:

 31         226 PUSH_NULL
            228 LOAD_NAME                8 (key_encode)
            230 LOAD_NAME                7 (key)
            232 PRECALL                  1
            236 CALL                     1
            246 STORE_NAME               7 (key)

 32         248 PUSH_NULL
            250 LOAD_NAME               10 (len)
            252 LOAD_NAME                7 (key)
            254 PRECALL                  1
            258 CALL                     1
            268 LOAD_CONST               7 (16)
            270 COMPARE_OP               2 (==)
            276 POP_JUMP_FORWARD_IF_FALSE    43 (to 364)

 33         278 PUSH_NULL
            280 LOAD_NAME                9 (sm4_encode)
            282 LOAD_NAME                7 (key)
            284 LOAD_NAME                5 (flag)
            286 PRECALL                  2
            290 CALL                     2
            300 LOAD_METHOD             11 (hex)
            322 PRECALL                  0
            326 CALL                     0
            336 STORE_NAME              12 (encrypted_data)

 34         338 PUSH_NULL
            340 LOAD_NAME                6 (print)
            342 LOAD_NAME               12 (encrypted_data)
            344 PRECALL                  1
            348 CALL                     1
            358 POP_TOP
            360 LOAD_CONST               2 (None)
            362 RETURN_VALUE

 32     >>  364 LOAD_CONST               2 (None)
            366 RETURN_VALUE

Disassembly of <code object key_encode at 0x14e048a00, file "make.py", line 10>:
 10           0 RESUME                   0

 11           2 LOAD_GLOBAL              1 (NULL + list)
             14 LOAD_FAST                0 (key)
             16 PRECALL                  1
             20 CALL                     1
             30 STORE_FAST               1 (magic_key)

 12          32 LOAD_GLOBAL              3 (NULL + range)
             44 LOAD_CONST               1 (1)
             46 LOAD_GLOBAL              5 (NULL + len)
             58 LOAD_FAST                1 (magic_key)
             60 PRECALL                  1
             64 CALL                     1
             74 PRECALL                  2
             78 CALL                     2
             88 GET_ITER
        >>   90 FOR_ITER               105 (to 302)
             92 STORE_FAST               2 (i)

 13          94 LOAD_GLOBAL              7 (NULL + str)
            106 LOAD_GLOBAL              9 (NULL + hex)
            118 LOAD_GLOBAL             11 (NULL + int)
            130 LOAD_CONST               2 ('0x')
            132 LOAD_FAST                1 (magic_key)
            134 LOAD_FAST                2 (i)
            136 BINARY_SUBSCR
            146 BINARY_OP                0 (+)
            150 LOAD_CONST               3 (16)
            152 PRECALL                  2
            156 CALL                     2
            166 LOAD_GLOBAL             11 (NULL + int)
            178 LOAD_CONST               2 ('0x')
            180 LOAD_FAST                1 (magic_key)
            182 LOAD_FAST                2 (i)
            184 LOAD_CONST               1 (1)
            186 BINARY_OP               10 (-)
            190 BINARY_SUBSCR
            200 BINARY_OP                0 (+)
            204 LOAD_CONST               3 (16)
            206 PRECALL                  2
            210 CALL                     2
            220 BINARY_OP               12 (^)
            224 PRECALL                  1
            228 CALL                     1
            238 PRECALL                  1
            242 CALL                     1
            252 LOAD_METHOD              6 (replace)
            274 LOAD_CONST               2 ('0x')
            276 LOAD_CONST               4 ('')
            278 PRECALL                  2
            282 CALL                     2
            292 LOAD_FAST                1 (magic_key)
            294 LOAD_FAST                2 (i)
            296 STORE_SUBSCR
            300 JUMP_BACKWARD          106 (to 90)

 15     >>  302 LOAD_GLOBAL              3 (NULL + range)
            314 LOAD_CONST               5 (0)
            316 LOAD_GLOBAL              5 (NULL + len)
            328 LOAD_FAST                0 (key)
            330 PRECALL                  1
            334 CALL                     1
            344 LOAD_CONST               6 (2)
            346 PRECALL                  3
            350 CALL                     3
            360 GET_ITER
        >>  362 FOR_ITER               105 (to 574)
            364 STORE_FAST               2 (i)

 16         366 LOAD_GLOBAL              7 (NULL + str)
            378 LOAD_GLOBAL              9 (NULL + hex)
            390 LOAD_GLOBAL             11 (NULL + int)
            402 LOAD_CONST               2 ('0x')
            404 LOAD_FAST                1 (magic_key)
            406 LOAD_FAST                2 (i)
            408 BINARY_SUBSCR
            418 BINARY_OP                0 (+)
            422 LOAD_CONST               3 (16)
            424 PRECALL                  2
            428 CALL                     2
            438 LOAD_GLOBAL             11 (NULL + int)
            450 LOAD_CONST               2 ('0x')
            452 LOAD_FAST                1 (magic_key)
            454 LOAD_FAST                2 (i)
            456 LOAD_CONST               1 (1)
            458 BINARY_OP                0 (+)
            462 BINARY_SUBSCR
            472 BINARY_OP                0 (+)
            476 LOAD_CONST               3 (16)
            478 PRECALL                  2
            482 CALL                     2
            492 BINARY_OP               12 (^)
            496 PRECALL                  1
            500 CALL                     1
            510 PRECALL                  1
            514 CALL                     1
            524 LOAD_METHOD              6 (replace)
            546 LOAD_CONST               2 ('0x')
            548 LOAD_CONST               4 ('')
            550 PRECALL                  2
            554 CALL                     2
            564 LOAD_FAST                1 (magic_key)
            566 LOAD_FAST                2 (i)
            568 STORE_SUBSCR
            572 JUMP_BACKWARD          106 (to 362)

 18     >>  574 LOAD_CONST               4 ('')
            576 LOAD_METHOD              7 (join)
            598 LOAD_FAST                1 (magic_key)
            600 PRECALL                  1
            604 CALL                     1
            614 STORE_FAST               1 (magic_key)

 19         616 LOAD_GLOBAL             17 (NULL + print)
            628 LOAD_FAST                1 (magic_key)
            630 PRECALL                  1
            634 CALL                     1
            644 POP_TOP

 20         646 LOAD_GLOBAL              7 (NULL + str)
            658 LOAD_GLOBAL              9 (NULL + hex)
            670 LOAD_GLOBAL             11 (NULL + int)
            682 LOAD_CONST               2 ('0x')
            684 LOAD_FAST                1 (magic_key)
            686 BINARY_OP                0 (+)
            690 LOAD_CONST               3 (16)
            692 PRECALL                  2
            696 CALL                     2
            706 LOAD_GLOBAL             11 (NULL + int)
            718 LOAD_CONST               2 ('0x')
            720 LOAD_FAST                0 (key)
            722 BINARY_OP                0 (+)
            726 LOAD_CONST               3 (16)
            728 PRECALL                  2
            732 CALL                     2
            742 BINARY_OP               12 (^)
            746 PRECALL                  1
            750 CALL                     1
            760 PRECALL                  1
            764 CALL                     1
            774 LOAD_METHOD              6 (replace)
            796 LOAD_CONST               2 ('0x')
            798 LOAD_CONST               4 ('')
            800 PRECALL                  2
            804 CALL                     2
            814 STORE_FAST               3 (wdb_key)

 21         816 LOAD_GLOBAL             17 (NULL + print)
            828 LOAD_FAST                3 (wdb_key)
            830 PRECALL                  1
            834 CALL                     1
            844 POP_TOP

 22         846 LOAD_FAST                3 (wdb_key)
            848 RETURN_VALUE

magic_key:7a107ecf29325423
encrypted_data:f2c85bd042247896b43345e589e3ad025fba1770e4ac0d274c1f7c2a670830379195aa5547d78bcee7ae649bc3b914da

我们从
key_encode
​函数源码第11行(字节码第一列是源码行号)开始看:

Disassembly of <code object key_encode at 0x14e048a00, file "make.py", line 10>:
 10           0 RESUME                   0

 11           2 LOAD_GLOBAL              1 (NULL + list)
             14 LOAD_FAST                0 (key)
             16 PRECALL                  1
             20 CALL                     1
             30 STORE_FAST               1 (magic_key)

第十行是定义
key_encode
​函数,
LOAD_GLOBAL
​ 加载内置list函数,
LOAD_FAST
​ 加载key参数,
PRECALL
​准备调用list函数,参数数量为一,
CALL
​ 执行函数调用,


STORE_FAST
​ 将结果存储在局部变量magic_key中。所以源码就是:

magic_key = list(key)

然后我们看源码第12行:

12          32 LOAD_GLOBAL              3 (NULL + range)
             44 LOAD_CONST               1 (1)
             46 LOAD_GLOBAL              5 (NULL + len)
             58 LOAD_FAST                1 (magic_key)
             60 PRECALL                  1
             64 CALL                     1
             74 PRECALL                  2
             78 CALL                     2
             88 GET_ITER
        >>   90 FOR_ITER               105 (to 302)
             92 STORE_FAST               2 (i)

前四行
LOAD_GLOBAL
​、
LOAD_CONST
​、
LOAD_FAST
​分别将range、1、len、magic_key压入栈中,即加载,第一组
PRECALL
​和
CALL
​是调用len计算magic_key的长度,第二组
PRECALL
​和
CALL
​是调用range,
GET_ITER、FOR_ITER
​开始循环,直到地址302结束,
STORE_FAST
​将栈顶弹出存入变量 i 中。所以源码为:

magic_key = list(key)
for i in range(1,len(magic_key)):

然后我们看源码第13行:

 13          94 LOAD_GLOBAL              7 (NULL + str)
            106 LOAD_GLOBAL              9 (NULL + hex)
            118 LOAD_GLOBAL             11 (NULL + int)
            130 LOAD_CONST               2 ('0x')
            132 LOAD_FAST                1 (magic_key)
            134 LOAD_FAST                2 (i)
            136 BINARY_SUBSCR
            146 BINARY_OP                0 (+)
            150 LOAD_CONST               3 (16)
            152 PRECALL                  2
            156 CALL                     2
            166 LOAD_GLOBAL             11 (NULL + int)
            178 LOAD_CONST               2 ('0x')
            180 LOAD_FAST                1 (magic_key)
            182 LOAD_FAST                2 (i)
            184 LOAD_CONST               1 (1)
            186 BINARY_OP               10 (-)
            190 BINARY_SUBSCR
            200 BINARY_OP                0 (+)
            204 LOAD_CONST               3 (16)
            206 PRECALL                  2
            210 CALL                     2
            220 BINARY_OP               12 (^)
            224 PRECALL                  1
            228 CALL                     1
            238 PRECALL                  1
            242 CALL                     1
            252 LOAD_METHOD              6 (replace)
            274 LOAD_CONST               2 ('0x')
            276 LOAD_CONST               4 ('')
            278 PRECALL                  2
            282 CALL                     2
            292 LOAD_FAST                1 (magic_key)
            294 LOAD_FAST                2 (i)
            296 STORE_SUBSCR
            300 JUMP_BACKWARD          106 (to 90)


LOAD_GLOBAL
​、
LOAD_CONST
​、
LOAD_FAST
​ 分别将全局常量str、hex、int压栈,常量'0x'压栈,变量magic_key和 i 压栈,
BINARY_SUBSCR
​索引动作,即magic_key[i],
BINARY_OP
​执行+操作,
LOAD_CONST
​将常量16压栈,
PRECALL
​和
CALL
​执行函数调用,在这里我们先暂停一下,强调一下:
因为是不断的面向栈操作,我们还原源码时一定要和进栈的顺序对应上
,所以我们此时可以还原
int('0x'+magic_key[i],16)
​,继续往后看,将int、'0x'、magic_key、i、1压栈,
BINARY_OP
​执行 - 操作,
BINARY_SUBSCR
​索引,即magic_key[i-1],
LOAD_CONST
​将16压栈,
PRECALL
​和
CALL
​执行函数调用,此时可以还原
int('0x'+magic_key[i-1],16)
​,然后
BINARY_OP
​执行 ^ 操作,两组
PRECALL
​和
CALL
​执行函数调用,此时还原到
str(hex(int('0x'+magic_key[i],16) ^ int('0x'+magic_key[i-1],16)))
​,
LOAD_METHOD
​将方法replace压栈,后面将'0x'和''压栈,然后调用函数,即replace('0x',''),然后将magic_key、i压栈,进行索引存储,所以源码为:

magic_key = list(key)
for i in range(1,len(magic_key)):
	magic_key[i] = str(hex(int('0x'+magic_key[i],16) ^ int('0x'+magic_key[i-1],16))).replace('0x','')

后面的同理,不再赘叙,第15行、16行 :

magic_key = list(key)
for i in range(1,len(magic_key)):
	magic_key[i] = str(hex(int('0x'+magic_key[i],16) ^ int('0x'+magic_key[i-1],16))).replace('0x','')

for i in range(0,len(key),2):
	magic_key[i] = str(hex(int('0x'+magic_key[i],16) ^ int('0x'+magic_key[i+1],16))).replace('0x','')

第18行:

magic_key = list(key)
for i in range(1,len(magic_key)):
	magic_key[i] = str(hex(int('0x'+magic_key[i],16) ^ int('0x'+magic_key[i-1],16))).replace('0x','')

for i in range(0,len(key),2):
	magic_key[i] = str(hex(int('0x'+magic_key[i],16) ^ int('0x'+magic_key[i+1],16))).replace('0x','')

magic_key = ''.join(magic_key)

第19行:

magic_key = list(key)
for i in range(1,len(magic_key)):
	magic_key[i] = str(hex(int('0x'+magic_key[i],16) ^ int('0x'+magic_key[i-1],16))).replace('0x','')

for i in range(0,len(key),2):
	magic_key[i] = str(hex(int('0x'+magic_key[i],16) ^ int('0x'+magic_key[i+1],16))).replace('0x','')

magic_key = ''.join(magic_key)
print(magic_key)

第20行:

magic_key = list(key)
for i in range(1,len(magic_key)):
	magic_key[i] = str(hex(int('0x'+magic_key[i],16) ^ int('0x'+magic_key[i-1],16))).replace('0x','')

for i in range(0,len(key),2):
	magic_key[i] = str(hex(int('0x'+magic_key[i],16) ^ int('0x'+magic_key[i+1],16))).replace('0x','')

magic_key = ''.join(magic_key)
print(magic_key)
wdb_key = str(hex(int('0x'+magic_key) ^ int('0x'+key,16))).replace('0x','')

第21行、22行,此时
key_encode
​函数结束:

def key_encode(key):
	magic_key = list(key)
	for i in range(1,len(magic_key)):
		magic_key[i] = str(hex(int('0x'+magic_key[i],16) ^ int('0x'+magic_key[i-1],16))).replace('0x','')

	for i in range(0,len(key),2):
		magic_key[i] = str(hex(int('0x'+magic_key[i],16) ^ int('0x'+magic_key[i+1],16))).replace('0x','')

	magic_key = ''.join(magic_key)
	print(magic_key)
	wdb_key = str(hex(int('0x'+magic_key) ^ int('0x'+key,16))).replace('0x','')
	print(wdb_key)
	return wdb_key

然后我们看31行:

key = key_encode(key)

第32行:

key = key_encode(key)
if len(key) == 16:

第33行:

key = key_encode(key)
if len(key) == 16:
	encrypted_data = hex(sm4_encode(key,flag))

第34行:

def key_encode(key):
	magic_key = list(key)
	for i in range(1,len(magic_key)):
		magic_key[i] = str(hex(int('0x'+magic_key[i],16) ^ int('0x'+magic_key[i-1],16))).replace('0x','')

	for i in range(0,len(key),2):
		magic_key[i] = str(hex(int('0x'+magic_key[i],16) ^ int('0x'+magic_key[i+1],16))).replace('0x','')

	magic_key = ''.join(magic_key)
	print(magic_key)
	wdb_key = str(hex(int('0x'+magic_key) ^ int('0x'+key,16))).replace('0x','')
	print(wdb_key)
	return wdb_key

key = key_encode(key)
if len(key) == 16:
	encrypted_data = hex(sm4_encode(key,flag))
	print(encrypted_data)

至此我们的源码就搓出来了,题目还给了如下信息:

magic_key:7a107ecf29325423
encrypted_data:f2c85bd042247896b43345e589e3ad025fba1770e4ac0d274c1f7c2a670830379195aa5547d78bcee7ae649bc3b914da

分析可知,我们已知
magic_key
​和
encrypted_data
​,
encrypted_data
​是由
flag
​经过sm4加密得到的,密钥为
key
​,所以我们需要知道
key
​,就可以sm4解密得到
flag
​,所以我们需要对 key_encode 函数的逻辑进行逆向得到
key
​,最后exp如下:

def key_encode(key):
	magic_key = list(key)
	for i in range(1,len(magic_key)):
		magic_key[i] = str(hex(int('0x'+magic_key[i],16) ^ int('0x'+magic_key[i-1],16))).replace('0x','')

	for i in range(0,len(key),2):
		magic_key[i] = str(hex(int('0x'+magic_key[i],16) ^ int('0x'+magic_key[i+1],16))).replace('0x','')

	magic_key = ''.join(magic_key)
	# print(magic_key)
	wdb_key = str(hex(int('0x'+magic_key,16) ^ int('0x'+key,16))).replace('0x','')
	# print(wdb_key)
	return wdb_key

magic_key = list("7a107ecf29325423")

for i in range(0,16,2):
	magic_key[i] = str(hex(int('0x'+magic_key[i],16) ^ int('0x'+magic_key[i+1],16))).replace('0x','')

for i in range(len(magic_key)-1,0,-1):
	magic_key[i] = str(hex(int('0x'+magic_key[i],16) ^ int('0x'+magic_key[i-1],16))).replace('0x','')

key = "".join(magic_key)
print(key_encode(key))

# 输出:ada1e9136bb16171

然后去赛博厨子解密即可拿到flag:wdflag{815ad4647b0b181b994eb4b731efa8a0}


image

参考链接:

PyCon 2018:James Bennett--理解 Python 字节码 掘金翻译计划

码农高天:字节码和虚拟机?python代码竟然是这么执行的!

王战山的学习笔记:Python中的字节码

python官方文档:dis — Disassembler for Python bytecode

今天我们开始学习目前学习到的最难最复杂的数据结构图。

简单回顾一下之前学习的数据结构,数组、单链表、队列等线性表中数据元素是一对一关系,而树结构中数据元素是一对多关系,而图结构中数据元素则是多对多关系,任何两个数据元素之间都有可能有关系,由此可见图结构的复杂程度。

希望通过这篇文章可以让大家很轻松的了解和学习图结构并快速入门,把一些晦涩难懂概念通过合理的组织归类使其简单明了,再配合一些图例说明,希望可以使大家茅塞顿开。

01
、基础概念

1、定义


是一个二元组G=(V(G),E(G))。其中V(G)是非空集,称为
点集
,对于V中的每个元素,我们称其为
顶点
或节点,简称

;E(G)为V(G)各节点之间边的集合,称为
边集

常用G=(V,E)表示图。

2、组成部分

上面的定义可能较为抽象,我们也可以从另一个角度来理解图,即图的内部结构,图由哪些要素组成的——



。简单来说图就是由若干个点以及连接两点的边构成的图形,而上面的定义也只是在说所有的点和所有的边组成图,这样是不是就很容易理解了。

其中点可以代表某种事物,而边可表示两个事物之间的关系,这样我们就可以把一些实际问题转为图,然后使用软件解决问题。

3、分类

我们可以根据边是否有方向,是否带权,简单的将图分类为无向图、有向图、带权图,当然还有其他类型的图,现阶段我们就不过多介绍了,容易把自己搞晕。

(1)无向图

无向图顾名思义就是
边没有方向
,即两个点之间没有方向,没有顺序之分,这样的边叫作
无向边
,也简称

。其中点也叫作
端点

(2)有向图

有向图则指
边有方向
,也就代表边所连接的两点有顺序之分,其中一个为
起点
,则另一个则为
终点
,而这样的边就叫作
有向边


。起点和终点也叫
端点

其中同一个点既可以是起点,也可以是终点。

对于任何图,与一个点关联的所有边数称为该点的

。而对于有向图来说,以一个点为起点的边数称为该的点
出度
,以一个点为终点的边数称为该点的
入度

如上图点A的出度为3,入度1。

(3)带权图

带权图指每个边都带有一个权重,代表边连接的两点关系的强弱、远近。同时权只是代表边的权重,并不代表边的方向,因此无论无边图还是有边图都可以是带权图。

02
、存储方式

了解了图的基本知识以后,带来了一个新的问题,这么复杂的结构我们要怎么存储下来呢?

下面我们就来介绍几种常用的存储方式邻接矩阵、邻接表、逆邻接表、十字链表。

1、邻接矩阵

邻接矩阵就是用一个二维数组来存储任意两点之间的关系,其中行列索引表示点,而行列索引所在的位置的值表示两点关系,其中两点关系可以用以下数值表示:

(1)
0
:表示两点之间没有边;

(2)
1
:表示两点之间有边;

(3)
权值
:表示两点之间边的权值;

如果图存在n个点,则可以用n x n的二维数组来表示图,下面我们来看看常见图的表示方式。

(1)无向图

对于无向图,如果点A与点B有边,则[A,B]与[B,A]都为1,否则都为0,因此无向图的邻接矩阵是对称的,如下图:

(2)有向图

对于有向图,则可以通过把行索引当作边的起点,把列当作边的终点,来表示方向,比如[A,B]为1,而[B,A]为0,如下图:

对于有向图,我们可以发现关于点的度有以下特性:

点的
出度
就是第i行元素之和;

点的
入度
就是第i列元素之和;

点的

就是第i行元素之和 + 第i列元素之和;

(3)带权图

对于带权图,本质上和无向图与有向图相同,只是存储的值有所差别,如果两点之间有边则直接存权值,如果两点之间无边则存一个特殊值(如0、无穷),如果可以保证权值中不存在0,可以用0,否则要选一个其他特殊值,如下图:

总结

优点

(1)
简单直观
:实现简单,易于理解,尤其适合小型图。

(2)
快速查找
:便于判断两点之间是否有边,以及各点的度。

缺点

(1)
空间浪费
:空间复杂度高为O(n^2),对于稀疏图,许多元素为零,造成空间浪费。

(2)
不易扩展
:不便于插入和删除点,需要更新整个矩阵,时间复杂度高为O(n)。

2、邻接表

对于邻接矩阵空间浪费以及不易扩展的问题,发展出了另一种链式存储方式——「邻接表」。

邻接表的存储思想和前面章节介绍的散列的链式存储很像。首先我们用一个数组存储所有的点,而每个点元素又作为单链表头,其后继节点则存储与头节点相邻的点元素。

(1)无向图

如下图,图中所有点都存储在数组中,而与其相邻的点存储在其后面的链表中。

点A相邻的点为点B和点C;

点C相邻的点为点A、点D和点E;

点D相邻的点为点C;

(2)有向图

与无向图不同的是有向图链表中存储的不是所有相邻的点,而是存储有方向的点,即以数组中的点为起的终点元素。

点A为起点的终点为点B和点C;

点B为起点的终点为点E;

点D为起点的终点不存在;

通过上图可以发现,邻接表对于有向图可以很直观的表示出某个点的出度,但是对于入度获取就很麻烦。

(3)带权图

带权图与无向图和有向图相比,只需要在元素中多加一个权重属性即可。

总结

优点

(1)
节省空间
:时间复杂度相对较低为O(m+n),m为点数量,n为边数量,对于稀疏图存储效率更高;

(2)
操作灵活
:插入和删除点操作方便,时间复杂度为O(1);

(3)
出度易取
:对于有向图获取某个点的出度非常方便,只需要找到这个点所在的数组元素位置,然后获取其链表中的元素个数即可;

缺点

(1)
不便查找
:判断两点之间是否有边的时间复杂度为O(V), 其中V 是该点的相邻点数量;

(2)
入度难算
:对于有向图点的入度的计算难度较大,时间复杂度为 O(E),其中E是图中的边的数量;

3、逆邻接表

逆邻接表从名字上就可以看出来和邻接表是逆的关系,这个逆就体现在入度和出度上。我们知道邻接表计算出度容易,计算入度难,而逆邻接表恰恰相反是计算入度容易,计算出度难。

如下图数组中存储点元素,而链表中存储的是以数组中的点为终点的起点元素。

点A为终点的起点不存在;

点B为终点的起点为点A;

点D为终点的起点为点A和点E;

总结

与邻接表差异在于在存储的方向正好相反,所以入度和出度计算难度正好相反,而其他则完全一样。

4、十字链表

邻接表出度计算容易,逆邻接表入度计算容易,那么有没有一种结构同时计算出度入度都容易呢?答案就是十字链表。

十字链表是邻接表和逆邻接表的结合体,每个点的边通过双向链表存储,同时记录了边的出度和入度。

下面我们详细讲解一下十字链表是怎么得到的。

(1)合并逆邻接表与邻接表

如下图我们之间把逆邻接表和邻接表拼接到一起,得到一个伪十字链表。

之所以称这个结合体为伪十字链表,是因为它虽然同时存储了边的两个方向,解决了出度入度计算问题,但是也引发了新的问题——存储效率低。

从上图不难看出链表中存在严重的重复存储的问题。要解决这个问题,我们先梳理一下我们得到的伪十字链表结构。

(2)链表由存点改存边

首先数组存储所有点,左侧链表存储起点元素集合,右侧链表存储终点元素集合;然后我们想为什么需要两条链表呢?因为一条链表就代表一个方向;

那第一步我们是否可以先解决方向的问题呢?而目前的结构节点只有一个点的信息,显然没有方向性,因此我们需要把链表节点改造成包含两个点的结构即起点和终点,这也意味着链表由原来存储点元素变为存储边元素。

原来点A出度链表存储点B和点C,现在改为存储[A->B]边和[A->C]边。

原来点B入度链表存储点A,现在改为存储[A->B]边。

如下图:

(3)删除重复元素

到这里就有条件解决重复的元素的问题了,比如上面链表中有两个[A->B]边,如果我们想把点B入度链表中[A->B]边删除,那么我们必须要有一个途径使得点B的入度链表可以和点A的出度链表中[A->B]边链接上。

首先数组元素结构应该至少包含:数据域|入边头节点指针|出边头节点指针;

然后链表节点元素结构应该至少包含:边起点下标|边终点下标|下一个入边节点指针域|下一个出边节点指针域;

下面我们进行去除重复元素,首先表里下出度链表结构,移除现有入度链表,其中入度链表中的元素指向到出度链表中,最后结果如下图:

如上图红色实线箭头表示出度链表,而彩色虚线箭头表示入度链表。

点A为终点的边不存在,点A为起点的边为 [A->B]边和[A->C]边;

点B为终点的边为[A->B]边(即红色1号虚线),点B为起点的边为 [B->E]边;

点C为终点的边为[A->C]边(即绿色2号虚线)和[E->C]边(即绿色3号虚线),点C为起点的边为[C->D]边;

总结

优点

(1)高效存储,适合复杂的有向图,支持快速遍历;

(2)快速计算出度入度;

缺点

(1)实现复杂,维护难度高;


:测试方法代码以及示例源码都已经上传至代码库,有兴趣的可以看看。
https://gitee.com/hugogoos/Planner

Welcome to
子木聊出海
! 从「程序员泥瓦匠」写技术博客,现在改到「子木聊出海」写一写以下相关的,欢迎阅读和交流 ~

一、关于我

我是子木,10 年的 SaaS、营销、电商和 AI 等领域经验,一路从技术开发到产品与增长负责人。在过去的职业生涯中,我的工作经历跨越了从编写代码、产品研发、到驱动增长的不同领域,尤其专注于工具类产品的设计、推广和用户增长策略

二、我的职业旅程:从技术,到产品,再到增长驱动产品

我的职业生涯起步于代码开发,那时我主要负责后端架构,追求高效和稳定的技术方案。在有赞工作的那几年,我不仅参与了搜索中台的核心开发,还在增长和市场拓展方面积累了丰富的经验。在担任高级工程师和增长工程师期间,我致力于通过数据和技术手段推动产品增长,例如构建关键词挖掘系统、优化 SEO 策略。我逐渐意识到,增长黑客和 Marketing Research 等可以成为市场营销和用户增长的强大支撑

之后,我走上了产品和增长的道路,先后负责过多个创新产品。两家 SaaS 公司作为业务线负责人,我主导了产品架构、市场定位和用户体验等环节。在这些项目中,我特别注重通过用户需求调研和数据分析来驱动产品迭代

三、现阶段的工作:专注出海与创新

目前,我的工作重心是出海 SaaS,特别是在 AI 视频生成和编辑工具领域。我和组内小伙伴在通过精准的 Google SEO 策略、社交媒体推广、红人营销和 Target Growth 策略,实现了用户和市场一定的增长。目前还在路上,需要我进一步对产品价值的理解,然后逐步扩展到用户需求的深层次挖掘和增长策略的制定

四、我相信的理念 & 个人愿景

我的工作理念可以概括为三点:
技术创新驱动产品价值

用户需求定义产品方向
、和
数据分析指导增长决策
。我注重细节并追求结果导向,每一个项目都力求将用户需求与产品设计完美结合,从而创造出能够解决真实问题的产品。

我对技术保持热情,同时希望通过更加市场导向的思维将这些技术应用到实际中去。这种双重背景赋予了我从细节出发、从数据入手制定增长策略的优势,也让在出海 SaaS 这条路上很 Enjoy

未来十年,继续出海软件方向深耕,尤其现阶段结合 AI 技术方向,希望留一些“小作品”在全球市场上。如果你对 AI、产品增长、出海市场感兴趣,或是有相关合作机会,欢迎交流和联系我!

from :
https://bysocket.com/hello-world/

出处:子木聊出海
博客:bysocket.com
我是子木,爱分享 Learning by Writing. 专注于出海 SaaS,探索 SEO、红人营销、Ads、EDM 等增长策略