c - 如何比较链表中的条目？

Question

我正在做一个管理建筑物中房间数量的 C 项目，我可以在其中选择预订或预预订房间。为此，我会要求用户输入一些数据(姓名、他想预订房间的时间和他想预订的房间)。

我已经可以做到了。但是，我还需要能够在已经预订的情况下为用户提供预预订房间的选项，因此如果预订被取消，那么第一个同时预预订的用户将被分配到房间.

“预保留”是什么意思:将用户置于遵循 FIFO(先进先出)理念的等候名单中

你能推荐一种方法吗？

这是我的头文件:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <conio.h>
#include <stdlib.h>
#include <ctype.h>
#include <time.h>

#define ARQ "Dados.txt" /*ARQUIVO COM OS DADOS*/

#define OP_INSERIR     '1'
#define OP_ALTERAR     '2'
#define OP_APAGAR      '3'
#define OP_LISTAR      '4'
#define OP_PESQUISAR   '5'
#define OP_PRERESERVAR '6'

#define OP_SAIR       '0'

#define OP_PESQ_HORAS '1'
#define OP_PESQ_NOME  '2'

char *MainMenu[]={
    "\n\tM E N U    P R I N C I P A L\n",
    "1. Fazer Reserva",
    "2. Alterar Reserva",
    "3. Apagar Reserva",
    "4. Listar Reservas",
    "5. Pesquisar",
    "0. Sair",
    NULL
};

char *PesqMenu[]={
    "1. Pesquisar por Intervalo de Tempo",
    "2. Pesquisar por Nome",
    "0. Voltar",
    NULL
};

FILE *fp;

typedef struct{
    char Nome[100];
    int Sala;
    int Hora_inicio;
    int Minuto_inicio;
    int Hora_fim;
    int Minuto_fim;
    char Status; /* '*' Indica que o registo está apagado */
} PESSOA;

程序的其余部分(我无法将其拆分为 .c 文件，我的编译器是否循环进入以下问题:“看来该项目尚未构建。您要构建它吗？ "如果你也能在这件事上帮助我，我将不胜感激):

#include "header.h"

void Mensagem(char *msg);

/*Lê os dados de um registo introduzidos pelo utilizador*/

void Ler_Pessoa(PESSOA *p){

    printf("Introduza o seu Nome (Primeiro e Ultimo) : "); gets(p->Nome);
    printf("Introduza o numero da sala que quer reservar:  "); scanf("%d", &p->Sala);
    printf("Introduza a partir de que horas quer reservar a sala (HH:MM): "); scanf("%2d:%2d",&p->Hora_inicio , &p->Minuto_inicio);
    printf("Introduza ate que horas quer reservar a sala (HH:MM): "); scanf("%2d:%2d", &p->Hora_fim , &p->Minuto_fim);
    p -> Status = ' ';
    fflush(stdin);
    system("cls");
}

void Mostrar_Pessoa(PESSOA p){
    printf("Nome          : %s\n",p.Nome);
    printf("Sala Reservada: %d\n",p.Sala);
    printf("Hora Inicial  : %2d:%2d",p.Hora_inicio , p.Minuto_inicio);
    printf("\tHora Final    : %2d:%2d\n",p.Hora_fim , p.Minuto_fim);
}

/*Adicionar uma Pessoa ao Arquivo */

void Adicionar_Pessoa(PESSOA p){
    fseek(fp , 0L , SEEK_END);
    if (fwrite(&p, sizeof(p), 1, fp)!=1)
        Mensagem("Adicionar Pessoa: Falhou a escrita  do Registo");
}

/* Coloca uma mensagem na tela */

void Mensagem(char *msg){
    printf(msg);
    getchar();
}
/*
 * Verifica se o Arquivo já existe. Se não existir, ele é criado.
 * Se já existir, abre-o em Modo de Leitura e Escrita (r+b)
 */

 void Inic(){
     fp = fopen(ARQ, "r+b"); /* Tenta Abrir*/
     if (fp==NULL){
         fp=fopen(ARQ, "w+b"); /*Cria o Arquivo*/
         if (fp==NULL){
             fprintf(stderr, "ERRO FATAL: Impossivel Criar Arquivo de Dados \n");
             exit(1);
         }
     }
 }

/*
 * Faz um Menu Simples com as opções do vector de Strings.
 * Seleciona a Opção, usando o primeiro caracter de cada string.
 * Devolve o primeiro caracter da opção
 */

 char Menu(char *Opcoes[]){
     int i;
     char ch;
     while(1){
         printf("\n");
         for (i=0 ; Opcoes[i] != NULL ; i++){
             printf("\n\t\t%s\n\n", Opcoes[i]);
         }
         printf("\n\n\t\tOpcao : ");
         ch = getchar(); fflush(stdin);
         system("cls");
         for (i=0 ; Opcoes[i]!=NULL ; i++){
             if (Opcoes[i][0]==ch)
                return ch;
         }
     }
 }

void Inserir_Pessoa(){
    PESSOA x;
    Ler_Pessoa(&x);
    Adicionar_Pessoa(x);
}

void Alterar_Pessoa(){
    PESSOA x;
    long int n_reg;
    char resp;
    printf("Qual o No. do Registo: ");
    scanf("%ld",&n_reg);
    fflush(stdin);
    if (fseek(fp, (n_reg-1)*sizeof(PESSOA),SEEK_SET)!=0){
        Mensagem("Registo Inexistente!!!");
        return;
    }
    if (fread(&x, sizeof(PESSOA),1,fp)!=1){
        Mensagem("Problemas na Leitura do Registo!!!");
        return;
    }
    if (x.Status == '*'){
        Mensagem("Um Registo Apagado nao pode ser alterado!!!\n\n");
        return;
    }
    printf("\n\nDados Actuais\n\n");
    Mostrar_Pessoa(x);
    printf("\n\nDeseja alterar a sua reserva? (s/n): "); resp = getchar();
    if(toupper (resp)!= 'S')
        return;
    fflush(stdin);
    printf("\n\nNovos Dados\n\n");
    Ler_Pessoa(&x);

    // Recuar um Registo no Arquivo//
    fseek(fp, -(long) sizeof(PESSOA), SEEK_CUR);
    // Reescrever o Registo;
    fwrite(&x, sizeof(PESSOA), 1, fp);
    fflush(fp); /*Despejar os dados no Disco*/
}

void Apagar_Pessoa(){
    PESSOA x;
    long int n_reg;
    char resp;

    printf("Qual o No. do Registo: ");
    scanf("%ld",&n_reg); fflush(stdin);
    if (fseek(fp,(n_reg-1)*sizeof(PESSOA),SEEK_SET)!=0){
        Mensagem ("Registo Inexistente!!!");
        return;
    }
    if (fread (&x, sizeof(PESSOA), 1 ,fp)!=1){
        Mensagem("Problemas na Leitura do Registo!!!");
        return;
    }
    if (x.Status=='*'){
        Mensagem("O Registo ja esta Apagado!!!\n\n");
        return;
    }
    printf("\n\nDados Actuais\n\n");
    Mostrar_Pessoa(x);
    printf("\n\nApagar o Registo (s/n)?: "); resp=getchar();
    fflush(stdin);
    if(toupper (resp)!= 'S')
        return;
    x.Status='*';

    fseek (fp, -(long) sizeof(PESSOA) , SEEK_CUR);
    fwrite(&x, sizeof(PESSOA), 1, fp);
    fflush(fp); /*Despejar os dados para o Disco*/
    system("cls");
}

void Listar_Pessoa(){
    long int N_Linhas = 0;
    PESSOA reg;
    rewind(fp);
    while(1){
        if (fread(&reg, sizeof(reg), 1 ,fp )!= 1) break; /*Sair do Ciclo*/
        if (reg.Status == '*') continue ; /*Passa ao próximo*/
        Mostrar_Pessoa(reg);
        N_Linhas++;
        if (N_Linhas %20==0)
            Mensagem("PRESSIONE <ENTER> para continuar . . .");
    }
    Mensagem("\n\nPRESSIONE <ENTER> para continuar . . ."); /*No fim da Listagem*/
}

void Pesquisar_HORAS(int ini, int fim){
    PESSOA reg;
    rewind (fp);

    while (fread(&reg, sizeof(PESSOA), 1, fp)){
        if (reg.Status != '*' && reg.Hora_inicio>=ini && reg.Hora_inicio <=fim)
            Mostrar_Pessoa(reg);
    }
    Mensagem("\n\nPRESSIONE <ENTER> para continuar . . . "); /* No fim da Listagem */
}

void Pesquisar_Nome(char *s){
    PESSOA reg;
    rewind(fp);

    while (fread(&reg , sizeof(PESSOA) , 1 , fp)){
        if (reg.Status!= '*' && strstr(reg.Nome,s))
            Mostrar_Pessoa(reg);
    }
    Mensagem ("\n\nPRESSIONE <ENTER> para continuar . . ."); /*No fim da Listagem*/
}

void main(){
    system("MODE con cols=100 lines=40");
    char Opcao;
    Inic();
    printf("Mini Projecto de Praticas de Programacao Procedimental\n");
    printf("Trabalho por:\n\nJoao Pedro Baptista de Oliveira, n%c 2010129867\nTomas Morgado de Carvalho Conceicao, n%c 2012138578\n\n",248,248);
    printf("----------------------------------------------------------------------------------------------------\n");
    time_t t;
    time(&t);
    printf("Data: %s\n", ctime(&t));
    printf("----------------------------------------------------------------------------------------------------\n");

    while ((Opcao =Menu(MainMenu))!=OP_SAIR){
        switch(Opcao){
            case OP_INSERIR: Inserir_Pessoa(); break;
            case OP_ALTERAR: Alterar_Pessoa(); break;
            case OP_APAGAR : Apagar_Pessoa(); break;
            case OP_LISTAR : Listar_Pessoa(); break;
            case OP_PESQUISAR:
            while ((Opcao=Menu(PesqMenu))!= OP_SAIR){
                switch (Opcao){
                    case OP_PESQ_HORAS:{
                        int n1,n2;
                        printf("Intervalo de horas: ");
                        scanf("%d",&n1);
                        printf("Ate: ");
                        scanf("%d",&n2);
                        fflush(stdin);
                        Pesquisar_HORAS(n1,n2); break;
                        }
                    case OP_PESQ_NOME:{
                        char string[BUFSIZ +1];
                        printf("Introduza o nome que quer pesquisar: ");
                        gets(string); fflush(stdin);
                        Pesquisar_Nome(string);
                    }
                }
            }
        }
    }
    printf("\n\t\tDepartamento de Engenharia Informatica - Universidade de Coimbra\n\n");
}

Answer 1

我不知道你是如何存储这些信息的(可能是由于未发布语言或存储代码)，但你的问题的标题建议链接列表。

这个问题的一个相当有效的(内存和性能方面)解决方案是有一个哈希表(带桶)，其中哈希表的键是房间的唯一标识符(数字/ID)，值存储在哈希表中每个槽中的是请求房间的人的结构(可能是您的 PESSOA 结构)。

然后你有3个主要场景:
- 如果哈希表条目 i 为空(没有值/桶)，房间是免费的。
- 哈希表条目 i 的第一个值/桶是当前在房间里的人。
- 哈希表条目 i 的剩余值/桶是等待房间的人。

这是高效的，因为您不需要存储完整的房间列表来分配人员，而且查找特定房间的时间是恒定的。

当一个新人想要“预先预订”时，您只需获取他们的信息，通过房间 ID 跳转到哈希表条目，并附加到值(value)/遗愿 list 。当一个人放弃房间时，根据房间 ID 跳转到哈希表条目并删除第一个值/桶，实质上是将下一个人提升到第一个值/桶。

如果您需要根据人名查找房间，您可以维护第二个哈希表，其中键是人名，值/桶是相同的信息结构，它也应该包含房间 ID。这个哈希表中的键不需要是唯一的，只要它也支持名称冲突的桶。