データ構造シングルチェーンテーブルC言語実装

17995 ワード

C言語学習チェーン？テーブルデータ構造 C言語実現

チェーン?テーブル
チェーン?テーブル
リニアテーブルを順次記憶する
割り付け方式
分散メモリ
集中メモリ
タイムパフォーマンス
O(n)を検索して削除O(1)を挿入します.
O(1)を検索して、O(n)を削除します.
スペース性能
スペースを割り当てる必要がなく、要素は無限に拡張できます.
割り当てスペース、要素の個数は有限です.
c言語コード実現(シングルチェーン表)

//
//  main.c
//           
//
//  Created by Kinble Wu on 2020/3/2.
//  Copyright © 2020 Kinble Wu. All rights reserved.
//
#include "include.h"

//          
typedef int ElemType;

//        
typedef struct Node{
    ElemType data;  //   
    struct Node* next;  //   
}Node;

//      
typedef struct Node* LinkList;

//      pos   
int GetElem(LinkList list,int pos){
    LinkList p;
    ElemType *e;
    p = list->next;
    int j = 1;

    //    ，  j==pos ，    
    while (p&&j<pos) {
        p = p->next;
        ++j;
    }
    //  ，        j  pos ，    
    if(!p||j>pos){
        return FALSE;
    }
    // p            e
    e = &p->data;
    //  e      
    return *e;
}

//     pos          
int InsertElem(LinkList list,int pos,ElemType data){
    /*****************************************************************
    *Function://InsertElem
    *Description://        
    *Calls://null
    *Called By://null
    *Input://list           ，pos       ，data       
    *Output://null
    *Return://TRUE  FALSE
    *Others:// 
    *****************************************************************/
    int j = 0;
    LinkList P,node_insert;
    
    P = list->next;
    j++;

    while (P&&j<pos){
        P = P->next;
    }
    //  ，        j  pos ，    
    if(!P||j>pos){
        return FALSE;
    }
    //         h  
    node_insert = (LinkList)malloc(sizeof(Node));
    node_insert->data = data;
    node_insert->next = P->next;
    P->next = node_insert;
    return TRUE;
    
}

//     pos     
int DeleteElem(LinkList list,int pos){
    int j = 0;
    LinkList P;
    
    P = list->next;
    j++;
    //    pos-1    
    while (P->next&&j<pos-1){
        P = P->next;
    }
    //  ，        j  pos ，    
    if(!P->next||j>pos-1){
        return FALSE;
    }
    //   pos-1 next  pos-1next next
    P->next = P->next->next;
    return TRUE;
    
}
//      n      (   )
void CreatList_head(LinkList *L,int num){
    LinkList P;
    int i = 0;
    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;
    while (i<num) {
        P = (LinkList)malloc(sizeof(Node));
        P->data = i;
        P->next = (*L)->next;
        (*L)->next = P;
        i++;
    }
}
//      n      （   ）
void CreatList_tail (LinkList *L,int num){
    LinkList P,Q;
    int i = 0;
    *L = (LinkList)malloc(sizeof(Node));
    P = *L;
    
    while (i<num) {
        Q = (LinkList)malloc(sizeof(Node));
        Q->data = i;
        P->next = Q;
        P = Q;
        free(Q);//    
        i++;
    }
    P->next = NULL;
}

//        
int Delet_WholeList(LinkList *L){
    LinkList P,Q;
    P = (*L)->next;
    while (P) {
        Q = P->next;
        free(P);
        P = Q;
    }
    (*L)->next = NULL;
    return TRUE;
}
int main(int argc, const char * argv[]) {
    // insert code here...
    
    
    
    printf("Hello, World!
");
    return 0;
}

セット、WeakSet、Map、WeakMap