//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 }

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.

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; }

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; }

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]; }

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)

Além de armazenar elementos de dados, cada nó também armazena um ponteiro para o próximo nó.

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

Nó principal

Nenhum nó principal

inserir

excluir

Pesquisa bit a bit

Encontrar por valor

Encontre o comprimento da mesa

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

Método de inserção de cabeça

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 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; }

//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 }

//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 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; }

//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 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.

//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 }

São todas tabelas lineares e estruturas lineares.

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.

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...

Implementado usando "matriz estática"

Uma vez determinado o tamanho, ele não pode ser alterado

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.

É necessário copiar os elementos de dados para uma nova área de armazenamento e utilizar a função livre para liberar a área original.

Pode encontrar o i-ésimo elemento em tempo O (1)

Definição (como implementá-la no código)

Implementação de operações básicas

Lista única

Lista duplamente vinculada

lista vinculada circular

lista vinculada estática

Insira o elemento e na i-ésima posição de L

Melhor O(1), pior O(n), médio O(n)

Exclua o i-ésimo elemento de L e retorne-o com e

Melhor O(1), pior O(n), médio O(n)

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]

A melhor/pior/média complexidade de tempo é O(1)

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

A melhor complexidade de tempo é O (1)

Pior complexidade de tempo O(n)

Complexidade média de tempo O(n)

Julgamento de tabela vazia: L==NULL

Código fácil de escrever

Julgamento de tabela vazia: L->next==NULL;

Escrever código é inconveniente

Nó principal

Nenhum nó principal