Wondershare EdrawMind
Galeria de mapas mentais tabela linear de estrutura de dados
- 15
tabela linear de estrutura de dados
Estrutura de dados Capítulo 2 Mapa mental de tabela linear: 1. A definição e as operações básicas de uma tabela linear Uma tabela linear é uma sequência finita de n elementos de dados com o mesmo tipo de dados. , 2. Representação sequencial de listas lineares (listas sequenciais), 3. Representação encadeada de listas lineares, etc.
Editado em 2022-03-31 18:41:13
- Recomendado para você
- Descrição
Capítulo 2 Tabela Linear
1. Definição e operações básicas de tabelas lineares
Definição de tabela linear
Uma tabela linear é uma sequência finita de n elementos de dados do mesmo tipo de dados.
Conceito: elemento de cabeçalho, elemento de cauda, antecessor direto, sucessor direto.
Operações básicas de tabelas lineares
Estabelecer InitList(&L) é inicializar e destruir DestroyList(&L) Adicione ListInsert(&L,i,e) para inserir ExcluirListaExcluir(&L,i,e) CheckLocateElem(L,e),GetElem(L,e) Comprimento da tabela (L), saída PrintList (L), Vazio (julgamento vazio)
2. Representação sequencial de tabelas lineares (tabelas sequenciais)
Definição de tabela de sequência
Implementar tabelas lineares usando armazenamento sequencial; Armazenamento sequencial: Armazene elementos logicamente adjacentes em unidades de armazenamento que também sejam fisicamente adjacentes. O relacionamento é refletido pelo relacionamento de adjacência das unidades de armazenamento.
Implementação da tabela de sequência
alocação estática
//Alocação estática define a tabela de sequência. O espaço de armazenamento é estático e o tamanho é fixo desde o início. #define MaxSize 10 //Define o comprimento máximo estrutura typedef{ ElemType data[MaxSize]; //Use "array" estático para armazenar elementos de dados int length; //Comprimento atual da tabela de sequência }SqList; //Definição do tipo da lista de sequências (método de alocação estática) ElemType refere-se ao tipo de dados definido por você, como int, double //Tabela de sequência de inicialização #include<stdio.h> #define MaxSize10 estrutura typedef{ dados internos[MaxSize]; comprimento interno; }ListaSq; void ListaInit(SqList &L){ for(int i=0;i<TamanhoMax;i) L.data[i]=0; //Define todos os elementos de dados com valores iniciais padrão L.length=0; //Define o comprimento inicial da tabela de sequência como 0; } int principal(){ SqList L; //Declara uma lista de sequências InitList(L): //Lista de sequência de inicialização ... retornar 0; } //Tabela de sequência de implementação de alocação dinâmica, o tamanho pode ser alterado #include<stiod.h> #define InitSize 10 //Comprimento máximo padrão estrutura typedef{ int *data; //Ponteiro indicando array alocado dinamicamente int MaxSize; //Capacidade máxima da tabela de sequência int length; //Comprimento atual da tabela de sequência }SeqList; //Definição da lista de sequências int principal(){ SeqList L; //Declara uma lista de sequências ListaInit(L): //Insere vários elementos aleatoriamente na tabela de sequência da rede AumentarTamanho(L,5); retornar 0; } void ListaInit(SeqList &L){ //Use a função malloc para solicitar um espaço de armazenamento contínuo L.data(int *)malloc(InitSize*sizeof(int)); L.comprimento=0; L.MaxSize=InitSize; } //Aumenta o comprimento do array dinâmico void AumentaSize(SeqList &L,int len){ int *p=L.dados; L.data(int *)malloc((L.MaxSize len)*sizeof(int)): for(int i=0;i<L.comprimento;i ){ L.data[i]=p[i]; //Copia dados para nova área } L.MaxSize=L.MaxSize len //O comprimento máximo da tabela de sequência aumenta em len; free(p); //Libera o espaço de memória original }
alocação dinâmica
L.data=(ElemType *)malloc(sizeof ElemType *InitSize) A função malloc retorna um ponteiro, que precisa ser convertido em um ponteiro para o tipo de elemento de dados que você definiu.
Características das tabelas de sequência: ① Acesso aleatório ②Alta densidade de armazenamento ③É inconveniente expandir a capacidade ④ As operações de inserção e exclusão são inconvenientes e exigem a movimentação de um grande número de elementos
Inserção e exclusão de tabela de sequência
Inserção na tabela de sequência
ListInsert(&L,I,e), insere o elemento especificado e na i-ésima posição
//Inserção sequencial de elementos da tabela #define MaxSize 10 estrutura typedef{ Dados ElemType[MaxSize]; comprimento interno; }ListaSq; void ListInsert(SqList &L,int I,int e){ for(int j=L.length;j>I;j--){ //Mover o i-ésimo elemento e os elementos subsequentes para trás L.dados[j]=L.dados[j-1]; } L.data[i-1]=e; //Coloque e na i-ésima posição L.comprimento; //Comprimento 1 } int principal(){ ListaSq L; ListaInit(L): //Omitido aqui, você pode inserir uma série de elementos ListaInserir(L,3,3); retornar 0; } //Para evitar a inserção de elementos sem feedback, por exemplo, se a memória estiver cheia, a função Insert deve ser modificada para ter um valor de retorno. bool ListInsert(SqList &L,int I,int e){ if(i<1 || i>L.comprimento 1) retorna falso; if(L.comprimento>=MaxSize) retorna falso; for(int j=L.comprimento;j>i;j--) L.dados[j]=L.dados[j-1]; L.dados[i-1]=e; L.comprimento; retorna falso; }
Complexidade de tempo de inserção: melhor O(1), pior O(n), média O(n)
Exclusão da tabela de sequência
ListDelete(SqList &L,int i,int &e), exclui o elemento na posição i na tabela L e retorna o valor do elemento
//Exclui tabela de sequência bool ListDelete(SqList &L,int i,int &e){ if(i<1 || i>L.length 1) //Determina se o intervalo de i é válido retorna falso; e=L.dados[i-1]; for(int j=1;j<L.comprimento;j) L.dados[j-1]=L.dados[j]; L.comprimento--; retornar verdadeiro; } int principal(){ ListaSq L; ListaInit(L); int e=-1; if(ListaDelete(L,3,e)) printf("Excluir o terceiro elemento, o valor do elemento excluído é =%d/n",e); outro pprintf("A ordem de bits i é ilegal, falha na exclusão "); retornar 0; }
Complexidade de tempo de exclusão: O(1) na melhor das hipóteses, O(n) na pior das hipóteses, O(n) na média
Pesquisa de tabela de sequência
Pesquisa bit a bit
GetElem(L,i), obtém o valor do elemento na i-ésima posição na tabela L
//Pesquisa por bit //Alocação estática #define MaxSize estrutura typedef{ ElemType data[MaxSize]; //Use "array" estático para armazenar elementos de dados int length; //Comprimento atual da tabela de sequência }SqList; //Definição do tipo da lista de sequências (método de alocação estática) ElemType GetElem(SqList L,int i){ return L.data[i-1]; //Chama a função GetElem() para retornar o valor do i-ésimo elemento } //Alocação dinâmica #defineInitSize estrutura typedef{ ElemType *dados; int MaxSize; comprimento interno; }SeqList; ElemType GetElem(SeqList L,int i){ retornar L.dados[i-1]; }
Encontrar por valor
LocateElem(L,e), encontra o elemento com o valor da palavra-chave fornecido na tabela L
//Pesquisa por valor #defineInitSize 10 estrutura typedef{ ElemType *dados; int MaxSize; comprimento interno; }SeqList; //Encontre o elemento cujo valor do primeiro elemento é igual a e na lista de sequência L e retorne sua ordem de bits int LocateElem(SeqList L,ElemType e){ for(int i=0;i<L.comprimento,i) if(int i=0;o<L.comprimento;i) return i 1; //O valor do elemento marcado i no array é igual a e, e sua ordem de bits é retornada i 1 return 0; //Sai do loop, indicando que a busca falhou }
Complexidade de tempo: melhor O(1), pior O(n), média O(n)
Comparação de tipo de estrutura
3. Representação em cadeia de tabela linear
Lista única
Definição de lista vinculada individualmente
Além de armazenar elementos de dados, cada nó também armazena um ponteiro para o próximo nó.
Representação de código de lista vinculada única
estrutura LNode{ Dados ElemType; //Definir tipo de nó de lista vinculada único struct LNode *next;//Cada nó armazena um elemento de dados } struct LNode *p=(struct LNode *)malloc(sizeof(struct LNode)); //Cada vez que um novo nó é adicionado, solicite um espaço de nó na memória e use o ponteiro p para apontar para este nó. Você também pode usar typedef struct LNode LNode em vez de LNode *p=(LNode *)maloc(sizeof(LNode)); Nesse caso, você não precisa de struct LNode para adicionar nós.
//Livro didático, defina uma lista vinculada individualmente typedef struct LNode{} //Definir tipo de nó de lista vinculada único Dados ElemType; //campo de dados struct LNode *next; //Campo ponteiro LNode,*LinkList; //LNode é renomeado, *LinkList é o ponteiro para este nó Use LNode * para enfatizar que este é um nó Use LinkList para enfatizar que esta é uma lista vinculada individualmente
Duas implementações
Nó principal
//Lista vinculada individualmente com nó principal typedef estrutura LNode{ Dados ElemType; strut LNode *próximo; }LNode,*LinkLst; // Inicializa uma lista vinculada individualmente vazia bool ListaInit(LinkList &L){ L=NULL; //Esvaziar tabela, colocar dados sujos retornar verdadeiro; } teste vazio(){ LinkList L; //Declara um ponteiro para uma lista vinculada individualmente //Inicializa uma tabela vazia ListaInit(L); //....Código subsequente } //Determina se a lista vinculada individualmente está vazia bool Vazio(LinkList L){ retornar (L = NULO); }
Nenhum nó principal
//Lista vinculada individualmente sem nó principal typedef estrutura LNode{ Dados ElemType; estrutura LNode *próximo; }LNode,*LinkList; //Inicializa uma lista vinculada individualmente com nós de cabeçalho bool ListaInit(LinkList &L){ L=(LNode *)malloc(sizeof(LNode));//Alocar um nó principal se(L==NULO) retorna falso; L->próximo=NULO; retornar verdadeiro; } teste vazio(){ LinkList L; //Declara um ponteiro para uma lista vinculada individualmente //Inicializa uma tabela vazia ListaInit(L); //...Seguinte código } //Determina se a lista vinculada individualmente está vazia (com cabeçalho) bool Vazio(LinkList L){ if(L->próximo==NULO) retornar verdadeiro; outro retorna falso; }
Inserção e exclusão de lista vinculada individualmente
inserir
Inserir na ordem dos bits
//Inserir o elemento e (nó principal) na i-ésima posição na ordem de bits ListInsert(&L,int i,ElemType e){ se(eu<1) retorna falso; LNode *p; //Ponteiro p aponta para o nó atualmente varrido int j=0; //Para qual nó o p atual está apontando? p=L; //L aponta para o nó principal, que é o 0º nó (nenhum dado armazenado) while(p!=NULL&&j<i-1){ //Loop para encontrar o i-1º nó p=p->próximo; j; } if(p=NULL) //O valor de i é ilegal retorna falso; LNode *s =(LNode *)malloc(sizeof(LNode));//Solicitar um novo espaço de nó para armazenar novos elementos s->data=e; //O campo de dados do novo nó armazena o conteúdo do novo elemento s->next=p->next; //O próximo ponteiro do novo nó aponta para o próximo ponteiro apontado pelo nó i-1, que é chamado de i-ésimo elemento p->next=s; //O nó anterior próximo ao novo nó aponta para o novo nó retornar verdadeiro; } typedef estrutura LNode{ Dados ElemType; estrutura LNode *próximo; }LNode,*LinkList;
////Inserir o elemento e na i-ésima posição na ordem de bits (sem o nó principal) bool ListInsert(LinkList &L,int i,ElemType e){ se(eu<1) retorna falso; if(i==1){ //A operação de inserção no primeiro nó é diferente da operação de outros nós LNode *s=(LNode *)malloc(sizeof(LNode)); s->dados=e; s->próximo=L; L=s; //O ponteiro principal aponta para o novo nó retornar verdadeiro; } LNode *p; intj=1; p=L; enquanto(p!=NULO && j<i-1){ p=p->próximo; j; } se(p==NULO) retorna falso; s->dados=e; s->próximo=p->próximo; p->próximo=s; return true; //Inserção bem sucedida } typedef estrutura LNode{ Dados ElemType; estrutura LNode *próximo; }LNode,*LinkList;
Operação pós-inserção do nó especificado
//Operação pós-inserção, insere o elemento e após o nó p bool InsertNextNode(LNode *p,ElemType e){ se(p==NULO) LNode *s=(LNode *)malloc(sizeof(LNode)); if(s==NULL) //Alocação de memória insuficiente retorna falso; s->data=e; //Use o nó s para salvar o elemento de dados e s->próximo=p->próximo; p->next=s; //Conecta o nó s depois de p retornar verdadeiro; } typedef estrutura LNode{ Dados ElemType; estrutura LNode *próximo; }LNode,*LinkList;
Operação de inserção direta do nó especificado
InsertPriorNode(LinkList L,LNode *p,ElemType e), dado o nó principal, percorra toda a tabela para encontrar o nó anterior de p. Por conveniência, copie diretamente este nó e altere o conteúdo deste nó, o que torna o tempo. complicado. O grau é O (n)
//Operação de inserção direta, insere o nó s antes do nó p bool InsertPriorNode(LNode *p,LNode *s){ se(p==NULO || s==NULO) retorna falso; s->próximo=p->próximo; p->próximo=s; ElemType temp=p->dados; p->dados=s->dados; s->dados=temp; retornar verdadeiro; }
excluir
Excluir em ordem de bits
ListDelete(&L,i,&e): operação de exclusão. Exclua o elemento na posição i na tabela L e use e para retornar o valor do elemento excluído.
//A lista vinculada individualmente é excluída em ordem de bits bool ListDelete(LinkList &L,int I,ElemType &s){ se(eu<1) retorna falso; LNode *p; //Ponteiro p aponta para o nó atualmente varrido int j=0; //j indica para qual nó p aponta atualmente p=L; //L aponta para o nó principal, que é o 0º nó (nenhum dado armazenado) while(p!=NULL&&j<j-1){ //Loop para encontrar o i-1º nó p=p->próximo; j; } if(p==NULL) //i valor é ilegal retorna falso; if(p->next==NULL) //Não há outros nós após o i-1º nó retorna falso; LNode *q=p->next; //Deixe q apontar para o nó excluído e=q->data; //Use e para retornar o valor do elemento p->next=q->next; //"Desconectar" o nó *q da cadeia free(q); //Libera o espaço de armazenamento do nó return true; //Exclusão com sucesso } typedef estrutura LNode{ Dados ElemType; estrutura LNode *próximo; }LNode,*LinkList;
Exclusão do nó especificado
DeleteNode(LNode *p), exclui o ponteiro p
//Exclui o nó especificado p da lista vinculada individualmente bool DeleteNode (LNode *p){ se(p==NULO) retorna falso; LNode *q=p->next; //Deixe q apontar para o nó sucessor de *p p->data=p->next->data; //Troca campos de dados com nós subsequentes p->next=q->next; //"Desconectar" o nó *q da cadeia free(q); //Libera o espaço de armazenamento dos nós subsequentes retornar verdadeiro; }
Pesquisar em lista vinculada individualmente
Pesquisa bit a bit
//Pesquisa bit a bit de lista vinculada individualmente LNode *GetElem(LinkList L,int i){ se(eu<0) retornar NULO; LNode *p; intj=0; p=L; enquanto(p!=NULO&&j<1){ p=p->próximo; j; } retornar p; }
Encontrar por valor
LocateElem(LinkList L,ElemType e), encontra a localização do nó com campo de dados e
//Pesquise por valor em uma lista vinculada individualmente e encontre o nó cujo campo de dados retorna ==e LNode *LocateElem(LinkList L,ElemType e){ LNode *p = L->próximo; //Comece do primeiro nó para encontrar o nó com campo de dados e enquanto(p != NULL&&p->dados!=e) p=p->próximo; return p; //Retorna o ponteiro do nó após encontrá-lo, caso contrário retorna NULL }
Encontre o comprimento da mesa
//Encontra o comprimento da tabela comprimento interno(LinkList L){ int comprimento=0; LNode *p=L; while(p->próximo != NULO){ p=p->próximo; lento; } retornar lente; }
Criação de lista vinculada individualmente
etapa 1: inicializar uma lista vinculada individualmente etapa 2: Remova um elemento de dados por vez e insira-o no início/pé da tabela
método de inserção de cauda
Inicialize uma lista vinculada individualmente, defina o comprimento variável para registrar o comprimento da lista vinculada, defina o ponteiro final da lista e insira um elemento de dados por vez no final da lista.
//Método de inserção final para criar uma lista vinculada individualmente LinkList List_TailInsert(LinkList &L){ //Cria futuramente uma lista vinculada individualmente int x; //Definir ElemType como inteiro L=(LinkList)malloc(sizeof(LNode)); //Cria o nó principal LNode *s,*r=L; //r é o ponteiro final da tabela scanf(“%d”,&x); //Insira o valor do nó while(x!9999){ //Insira 9999 para indicar o fim s=(LNode *)malloc(sizeof(LNode)); s->dados=x; r->próximo=s; r=s; //r aponta para o novo ponteiro final da tabela scanf(“%d”,&x); } r->next=NULL; //Define o ponteiro do nó final como nulo retornar eu; }
Método de inserção de cabeça
//O método de inserção de cabeçalho cria uma lista vinculada individualmente LinkList List_HeadInsert(LinkList &L){ //Cria inversamente uma lista vinculada individualmente LNode*s; interno x; L=(LinkList)malloc(sizeof(LNode)); //Cria o nó principal L->next=NULL; //Lista vinculada inicialmente vazia scanf(“%d”,&x); //Insira o valor do nó while(x!=9999){ //Insira 9999 para indicar o fim s=(LNode*)malloc(sizeof(LNode)); //Cria um novo nó s->dados=x; s->próximo=L->próximo; L->next=s; //Insira o novo nó na tabela, L é o ponteiro principal scanf(“%d”,&x); } retornar eu; }
Lista duplamente vinculada
Inicialização de lista duplamente vinculada
Lista vinculada individualmente: uma lista vinculada individualmente não pode ser recuperada ao contrário, o que às vezes é inconveniente. Lista duplamente vinculada: pode avançar e recuar, diminuir a densidade de armazenamento
//Inicialização da lista duplamente vinculada (nó principal) bool InitDLinkList(DLinklist &L){ L=(DNode *)malloc(tamanhode(DNode)); se(L==NULO) flase de retorno; L->anterior=NULO; L->próximo=NULO; retornar verdadeiro; } void testDLinkList(){ // Inicializa a lista duplamente vinculada DLinklista L; InitDLinkList(L); //...Seguinte código } typedef estrutura DNode{ Dados ElemType; struct DNode *antes,*próximo; }DNode,*DLinklist; //Determina se a lista duplamente vinculada está vazia (nó principal) bool Vazio(DLinklist L){ if(L->próximo==NULO) retornar verdadeiro; outro retorna falso; }
Inserção em lista duplamente vinculada
//Inserção em lista duplamente vinculada bool InsertNextDNode(DNode *p,DNode *s){ s->next=p->next; //Inserir nó *s após o nó *p p->próximo->anterior=s; s->anterior=p; p->próximo=s; }
Exclusão de lista duplamente vinculada
//Exclui lista duplamente vinculada bool DeleteNextDNode(DNode *p){ if(p==NULL) retorna flase; DNode *q=p->next; //Encontre o nó sucessor q de p if(q==NULL) return false; //p não tem nó sucessor p->próximo=q->próximo; if(q->next!=NULL) //O nó q não é o último nó q->próximo->anterior=p; free(q); //Libera espaço do nó retornar verdadeiro; } void DestoryList(DLinklist &L){ //Loop para liberar cada nó de dados enquanto(L->próximo!=NULO) ExcluirNextDNode(L); free(L); //Libera o nó principal L=NULL; //ponteiro principal aponta para NULL }
Travessia de lista duplamente vinculada
//Traversal da lista duplamente vinculada while(p!=NULL){ //travessia para trás //Faça o processamento correspondente para o nó p p=p->próximo; } while(p!=NULL){ //travessia para frente p=p->prioe; } while(p->prioe!=NULL){ //Transversal para frente, pula o nó principal p=p->anterior; }
lista vinculada circular
Lista circular unida individualmente
Lista vinculada individualmente: começando em um nó, apenas os nós subsequentes podem ser encontrados, mas os nós anteriores são desconhecidos. Lista circular unida individualmente: começando em um nó, você pode encontrar qualquer outro nó.
//Define uma lista circular unida individualmente typedef struct LNode{ //Definir tipo de nó de lista vinculada único ElemType data; //Cada nó armazena um elemento de dados struct LNode *next; //dados apontam para o próximo nó }LNode,*LinkList; // Inicializa uma lista circular unida individualmente bool ListaInit(LinkList &L){ L=(LNode *)malloc(sizeof(LNode)); //Alocar um nó principal if(L==NULL) //Memória insuficiente, falha na alocação retorna falso; L->next = L; //O próximo nó principal aponta para o nó principal retornar verdadeiro; } //Determina se a lista circular unida individualmente está vazia bool Vazio(LinkList L){ if(L->próximo==L) retornar verdadeiro; outro flase de retorno; } //Determina se o nó p é o nó final da lista circular unida individualmente bool isTail(LinkList L,LNode *p){ se(p->próximo==L) retornar verdadeiro; outro retorna falso; }
Lista circular duplamente vinculada
//Inicializa lista circular dupla vinculada vazia bool InitDLinkList(DLinklist &L){ L=(DNode *)malloc(sizeof(DNode)); //Alocar um nó principal if(L==NULL) //Memória insuficiente, falha na alocação retorna falso; L->prior=L; //A prioridade do nó principal aponta para o nó principal L->next=L; //o próximo do nó principal aponta para o nó principal retornar verdadeiro; } void testDLinkList(){ //Inicializa lista duplamente vinculada circular DLinklista L; InitDLinkList(L); //...Seguinte código } //Determina se a lista duplamente vinculada circular está vazia bool Vazio(DLinklist){ if(L->próximo==L) retornar verdadeiro; outro retorna falso; } //Determina se o nó p é o nó final da lista circular duplamente vinculada bool isTail(DLinklist L,DNode *p){ se(p->próximo==L) retornar verdadeiro; outro retorna falso; } typedef estrutura DNode{ Dados ElemType; struct DNode *antes,*próximo; }DNode,*DLinklist;
lista vinculada estática
definição
Lista vinculada individualmente: cada nó é alocado aleatoriamente na memória. Lista vinculada estática: aloca um pedaço inteiro de espaço de memória contínua e cada nó é colocado centralmente.
representação de código
//Definir lista vinculada estática #define MaxSize 10 método typedef{} Dados ElemType; próximo; } void testSLinkList(){ estrutura Nó a[MaxSize]; //...Código subsequente } //Você também pode criar uma lista vinculada estática com o seguinte código #define MaxSize 10 //Comprimento máximo da lista vinculada estática typedef struct{ //Definição do tipo de estrutura de lista vinculada estática ElemType data; //Armazena elementos de dados int next; //subscrito da matriz do próximo elemento } SLinkList[MaxSize]; void testSLinkLst(){} SLinkLista; //...Seguinte código }
Implementação de operações básicas
Implementação de listas de sequência e listas vinculadas
estrutura lógica
São todas tabelas lineares e estruturas lineares.
Estrutura física/resultados de armazenamento
Vantagens das tabelas de sequência: suporte para acesso aleatório e alta densidade de armazenamento. Desvantagens: É inconveniente alocar grandes áreas de espaço contínuo e é inconveniente alterar a capacidade. Vantagens das listas vinculadas: Pequenos espaços discretos são fáceis de alocar e a capacidade é fácil de alterar. Desvantagens: Sem acesso aleatório, baixa densidade de armazenamento.
Operações de dados/operações básicas
Criação de tabela de sequência: Um grande espaço contíguo precisa ser pré-alocado. Se o espaço alocado for muito pequeno, será inconveniente expandir a capacidade posteriormente; se o espaço alocado for muito grande, os recursos de memória serão desperdiçados; Alocação estática: array estático, capacidade imutável Alocação dinâmica: array dinâmico (malloc, free), a capacidade pode ser alterada, mas requer a movimentação de um grande número de elementos, o que consome tempo. Destruição: Modifique o comprimento = 0, o espaço alocado estaticamente será recuperado automaticamente, o aplicativo malloc alocado dinamicamente precisa ser liberado manualmente Inserir/excluir elementos requer mover os elementos subsequentes para frente/para trás. A complexidade do tempo é O(n), e a sobrecarga de tempo vem principalmente de elementos móveis. Se o elemento móvel for grande, o custo do tempo de movimentação será alto. Pesquisa: Pesquisa bit a bit: O(1). Pesquisa por valor: O(n). Se os elementos da tabela estiverem ordenados, eles podem ser encontrados em tempo O(log2n).
Criação de lista vinculada: Você só precisa alocar um nó principal (você também pode omitir o nó principal e declarar apenas um ponteiro principal), que pode ser facilmente expandido posteriormente. Destruir: exclua cada nó por vez (grátis) Inserir/excluir elementos requer apenas a modificação do ponteiro. A complexidade do tempo é O(n) e a sobrecarga de tempo vem principalmente da localização do elemento de destino. O custo de tempo para encontrar elementos é menor. Pesquisa: Pesquisa bit a bit: O(n). Encontre por valor: O(n).
Use uma lista sequencial ou uma lista vinculada: O comprimento da lista é difícil de estimar e os elementos geralmente precisam ser adicionados, subtraídos/excluídos, portanto, use uma lista vinculada. O comprimento da tabela pode ser estimado e há muitas operações de consulta (pesquisa), portanto use uma tabela sequencial. Pergunta: Por favor, descreva a lista de sequências e a lista vinculada...Qual é melhor usar a lista de sequências ou a lista vinculada? As estruturas lógicas das listas de sequência e das listas vinculadas são resultados lineares e ambas pertencem a listas lineares. No entanto, as estruturas de armazenamento dos dois são diferentes. A tabela de sequência usa armazenamento sequencial... (recursos, vantagens e desvantagens); a lista vinculada usa armazenamento em cadeia... (vantagens e desvantagens). Devido ao uso de diferentes métodos de armazenamento, a eficiência de implementação das operações básicas também é diferente. Ao inicializar...ao inserir um elemento de dados...ao excluir um elemento de dados...ao procurar um elemento de dados...
Apêndice
Tabela de sequência
estrutura de armazenamento
Os elementos de dados que são logicamente adjacentes também são fisicamente adjacentes
Método para realizar
alocação estática
Implementado usando "matriz estática"
Uma vez determinado o tamanho, ele não pode ser alterado
alocação dinâmica
Implementado usando "matriz dinâmica"
L.data=(ElemType *)malloc (sizeof(El;emType)* tamanho)
Quando a tabela de sequência está cheia, malloc pode ser usado para expandir dinamicamente o rendimento máximo da tabela de sequência.
Preste atenção às funções malloc e free
É necessário copiar os elementos de dados para uma nova área de armazenamento e utilizar a função livre para liberar a área original.
Características
acesso aleatório
Pode encontrar o i-ésimo elemento em tempo O (1)
Alta densidade de armazenamento
Expandir a capacidade é inconveniente
Inserir e excluir elementos de dados é inconveniente
mesa linear
estrutura lógica
Cálculos/operações básicas
Armazenamento/Estrutura Física
Tabela de sequência (armazenamento sequencial)
Definição (como implementá-la no código)
Implementação de operações básicas
Lista vinculada (armazenamento vinculado)
Lista única
Definição (como implementá-la no código)
Implementação de operações básicas
Lista duplamente vinculada
lista vinculada circular
lista vinculada estática
Inserção e exclusão de tabela de sequência
inserir
ListaInserir(&L,i,e)
Insira o elemento e na i-ésima posição de L
Os elementos após a posição de inserção devem ser movidos para trás e o comprimento da tabela é aumentado em 1
complexidade de tempo
Melhor O(1), pior O(n), médio O(n)
excluir
ListaExcluir(&L,i,&e)
Exclua o i-ésimo elemento de L e retorne-o com e
Os elementos após a posição excluída devem ser movidos para frente e o comprimento da tabela é reduzido em 1
complexidade de tempo
Melhor O(1), pior O(n), médio O(n)
Pontos de código
Observe a diferença entre a ordem de bits i e o subscrito da matriz
O algoritmo deve ser robusto e determinar a legalidade de i
Preste atenção se o elemento movido começa no elemento frontal ou no elemento final.
Analise por que existe '&'
Pesquisa de tabela de sequência
Pesquisa bit a bit
GetElem(L,i)
Obtenha o valor do elemento na posição i na tabela L
Use o subscrito da matriz para obter o i-ésimo elemento L.data[i-1]
Análise de complexidade de tempo
A melhor/pior/média complexidade de tempo é O(1)
Encontrar por valor
LocateElem(L,e)
Encontre o elemento cujo valor do primeiro elemento é igual a e na lista de sequência L e retorne sua ordem de bits
Pesquisa começando no primeiro elemento e retrocedendo
Análise de complexidade de tempo
A melhor complexidade de tempo é O (1)
Pior complexidade de tempo O(n)
Complexidade média de tempo O(n)
Definição de lista vinculada individualmente
O que é uma lista vinculada individualmente
Usar "armazenamento em cadeia" (estrutura de armazenamento) realiza "estrutura linear" (estrutura lógica)
Um nó armazena um elemento de dados
O relacionamento de sequência entre cada nó é representado por um ponteiro
Defina uma lista vinculada individualmente usando código
typedef struct LNode{ //Definir tipo de nó de lista vinculada único Dados ElemType; //campo de dados struct LNode *next; //Campo ponteiro }LNode,*LinkList;
Duas implementações
Nó principal
Julgamento de tabela vazia: L==NULL
Código fácil de escrever
Nenhum nó principal
Julgamento de tabela vazia: L->next==NULL;
Escrever código é inconveniente
Outros pontos a serem observados
Como usar a palavra-chave typedef
LinkList é equivalente a LNode LinkList enfatiza uma lista vinculada; LNode enfatiza um nó;
Inserção e exclusão de lista vinculada única
inserir
Inserir na ordem dos bits
Nó principal
Nenhum nó principal
Operação pós-inserção do nó especificado
Operação de inserção direta do nó especificado
excluir
Excluir em ordem de bits
Exclusão do nó especificado
Pesquisar em lista vinculada individualmente
Pesquisa bit a bit
Observe a comparação com a "tabela de sequência"
Uma lista encadeada individualmente não possui a característica de “acesso aleatório” e só pode ser verificada sequencialmente.
Encontrar por valor
Encontre o comprimento da lista vinculada individualmente
Chave
A complexidade de tempo das três operações básicas é O(n)
Como escrever uma lógica de código que percorre cada nó
Preste atenção ao processamento das condições de contorno
Criação de lista vinculada individualmente
etapa 1: inicializar uma lista vinculada individualmente etapa 2: Pegue um elemento de dados por vez e insira-o no início/pé da tabela
método de inserção de cauda
Método de inserção de cabeça
Lista duplamente vinculada
inicialização
A prioridade e o próximo nó principal apontam para NULL.
Inserção (inserção traseira)
Preste atenção às modificações de ponteiro de nós recém-inseridos, nós predecessores e nós sucessores.
Caso limite: o nó recém-inserido está na última posição e requer tratamento especial
Excluir (pós-exclusão)
Preste atenção à modificação dos ponteiros do nó predecessor e do nó sucessor do nó excluído.
Caso limite: se o nó excluído for o último nó de dados, será necessário processamento especial
Atravessar
A partir de um determinado nó, a implementação de travessia para trás e travessia para frente (condição de terminação do loop)
As listas vinculadas não possuem características de acesso aleatório e as operações de busca só podem ser realizadas por meio de travessia sequencial.
lista vinculada circular
Lista circular unida individualmente
Mesa vazia
mesa não vazia
Lista circular duplamente vinculada
Mesa vazia
mesa não vazia
problema de código
Como julgar curto
Como determinar se o nó p é o nó inicial/pé da tabela
lista vinculada circular
O que é uma lista vinculada estática
Alocar centralmente um endereço contíguo inteiro para armazenar elementos de dados
Como definir uma lista vinculada estática
Descreva resumidamente a implementação das operações básicas