有时间的话用 c 语言实现一些简单数据机构!

链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include<stdio.h>
#include<stdlib.h>
typedef struct _NodeList{
    int data;
    struct _NodeList * nlp;
}NodeList;

/*DEFINE METHOD*/
int getsize();
NodeList * get(int index); // 获取链表上的第index个节点，从 0 开始
void insert(NodeList * nlp,int index); // 将nlp 插入到 链表的 index出 从 0 开始
NodeList * new_node_list(int data); // 新建一个节点
void add(NodeList *nlp); // 将 nlp 添加到链表的末尾
void print_of_range(int range);  // 输出 range 条链表数据
NodeList * remove_o(int index); // 移除第index 个节点 从0 开始
void clear(); // 清空链表
NodeList * HEAD=NULL;
int NODE_SIZE=0;
int main(int argc, char const *argv[]){
    for(short i=0;i<10;i++){
        add(new_node_list(i+100));
    }
    insert(new_node_list(999),1);
    // printf("%d\n",HEAD->data);
    // printf("NODE_SIZE:%d\n",getsize());
    // printf("Get:%d\n",get(0)->data);
    print_of_range(6);
    remove_o(2);
    print_of_range(6);
    clear();
    return 0;
}
NodeList * new_node_list(int data){
    NodeList * nlp=(NodeList *)malloc(sizeof(NodeList));
    nlp->data=data;
    nlp->nlp=NULL;
    return nlp;
}
void insert(NodeList *nlp,int index){
   if(index>NODE_SIZE){
       printf("insert index:%d > NODE_SIZE:%d\n",index,NODE_SIZE);
       exit(0);
   }
   if(index==0){
       NodeList * temp=HEAD;
       nlp->nlp=temp;
       HEAD=nlp;
       NODE_SIZE++;
   }
   else if(index==NODE_SIZE) add(nlp);
   else{
       // get prep
       NodeList * prep=HEAD;
       NodeList * suffp=NULL;
       for(int i=0;i<index-1;i++){
           prep=prep->nlp; // prep is index-1;
       }
       suffp=prep->nlp; 
       prep->nlp=nlp;
       nlp->nlp=suffp;
       NODE_SIZE++;
   }
    
}
void add(NodeList *nlp){
    if(HEAD==NULL){
        HEAD=nlp;
        NODE_SIZE++;
        return;
        }
        NodeList * n=HEAD;
    for(int i=0;i<NODE_SIZE-1;i++){
        n=n->nlp; //n现在是最后一个 
    }
    NODE_SIZE++;
    n->nlp=nlp;
}
NodeList * get(int index){
   if(index<0||index>NODE_SIZE-1){
       printf("Out of range :index > %d\n",NODE_SIZE-1);
       exit(1);
   } 
   NodeList * getnlp=HEAD;
   for(int i=0;i<index;i++){
      getnlp=getnlp->nlp;
   }
   return getnlp;

}
int getsize(){
    return NODE_SIZE;
}
void print_of_range(int range){
    if(range>NODE_SIZE||range<0){
        printf("Out of range :range > %d\n",NODE_SIZE);
        exit(1);
    }
    NodeList * nlp=HEAD;
    for(int i=0;i<range;i++){
        printf("%d :value : %d\n",i,nlp->data);
        nlp=nlp->nlp;
    }
}
NodeList * remove_o(int index){
    if(index<0||index>NODE_SIZE-1){
        printf("Out of range :range > %d\n",NODE_SIZE);
        exit(1);
    }
    NodeList * removep=HEAD;
    if(index==0){
        HEAD=HEAD->nlp;
    }
    else if(index==NODE_SIZE-1){ // 最后一个
        NodeList * c=HEAD;
        for(int i=0;i<NODE_SIZE-2;i++){
            c=c->nlp;
        }
        removep=c->nlp;
        c->nlp=NULL;
    }else{
        NodeList * reprefix=HEAD;
        for(int i=0;i<index-1;i++){
           reprefix=reprefix->nlp; 
        }
        removep=reprefix->nlp;
        reprefix->nlp=removep->nlp;
    }
    NODE_SIZE--;
    return removep;
    
}
void clear(){
    NodeList * wait=NULL;
    NodeList * temp=HEAD;
    for(int i=0;i<NODE_SIZE;i++){
       wait=temp; 
       temp=temp->nlp;
       free(wait);
    }
    NODE_SIZE=0;
}

栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <stdio.h>
#include <stdlib.h>

typedef struct
{
    int data;
} Data;
Data *pop();
void push(Data *data);
Data **init(unsigned int size);
Data *new_Data(int ata);
Data **STACK = NULL;
unsigned int SIZE = 0;
unsigned int REAL_SIZE = 0;
int main(int argc, char const *argv[])
{
    STACK = init(10);
    push(new_Data(100));
    push(new_Data(200));
    push(new_Data(300));
    push(new_Data(400));
    unsigned int I = REAL_SIZE;
    for (int i = 0; i < I-1; i++)
    {
        Data *dp = pop();
        printf("POP:%d", dp->data);
        putchar('\n');
    }
    push(new_Data(500));
    push(new_Data(700));
    Data *ep=pop();
    printf("end:%d\n",ep->data);
    free(ep);
    printf("%d",ep->data);
    return 0;
}
Data **init(unsigned int size)
{
    SIZE = size;
    return (Data **)calloc(size, sizeof(Data **));
}
void push(Data *data)
{
    if (REAL_SIZE >= SIZE)
    {
        printf("Stack overflow!\n");
        exit(1);
    }
    if (REAL_SIZE == 0)
    {
        *STACK = data;
    }
    else
    {
        ++STACK;
        *STACK = data;
    }
    ++REAL_SIZE;
}
Data *pop()
{
    if (REAL_SIZE == 0)
    {
        printf("Empty Stack!\n");
        exit(0);
    }

    Data *r = *STACK;
    if (REAL_SIZE == 1)
    {
        STACK = NULL;
        --REAL_SIZE;
        return r;
    }
    Data **pre = (STACK - 1);
    STACK = NULL;
    STACK = pre;
    --REAL_SIZE;
    return r;
}
Data *new_Data(int dat)
{
    Data *d = (Data *)malloc(sizeof(Data));
    d->data = dat;
    return d;
}

类似Java的ArrayList

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<stdio.h>
#include<stdlib.h>
typedef struct{
    int data;
}ArrayList;
int getsize();
ArrayList * newArrayList(int data);
void arraylist_add(ArrayList * alp); 
ArrayList * arraylist_remove(int index);
int clear(void);
ArrayList * getp(int index);
ArrayList get(int index);
int _arrlist_size_=0;
ArrayList * ARRAY_LIST=NULL;


int main(int argc, char const *argv[])
{
    ARRAY_LIST=newArrayList(10);//初始化
    printf("初始化:%d\n",ARRAY_LIST->data); 
    //添加
    arraylist_add(newArrayList(99));
    arraylist_remove(0);
    arraylist_add(newArrayList(111));
    printf("%d\n",(ARRAY_LIST+1)->data); 
    printf("GET:\n");
    printf("get:%d\n",get(0).data);
    printf("getp:%d\n",(getp(1)->data));
    return 0;
}


ArrayList * newArrayList(int data){
    ArrayList * alp=(ArrayList *)malloc(sizeof(ArrayList));
    alp->data=data;
    _arrlist_size_++;
    return alp;
}
int getsize(){
    return _arrlist_size_;
}
void arraylist_add(ArrayList * alp ){
   ArrayList * lp=(ArrayList *)malloc(sizeof(ArrayList)*_arrlist_size_); 
   for (int i=0;i<_arrlist_size_-1;i++){
     (lp+i)->data=(ARRAY_LIST+i)->data;
   }
//   free(ARRAY_LIST);
  (lp+_arrlist_size_-1)->data=alp->data;
  free(alp);
  free(ARRAY_LIST);
  ARRAY_LIST=lp;
} 
ArrayList *arraylist_remove(int index){
    ArrayList * r=ARRAY_LIST+index;
   ArrayList * alp=(ArrayList *)malloc(sizeof(ArrayList)*--_arrlist_size_);
   for (int i=0;i<index;i++){
      (alp+i)->data=(ARRAY_LIST+i)->data;
   }   
   for(int i=index;i<_arrlist_size_;i++){
       (alp+i)->data=(ARRAY_LIST+i+1)->data;
   }
   free(ARRAY_LIST);
   ARRAY_LIST=alp;
   return r;
} 
int clear(){
    free(ARRAY_LIST);   
    ARRAY_LIST=NULL;
    return 1;
}
ArrayList * getp(int index){
    return (ARRAY_LIST+index);
}
ArrayList get(int index){
    return *(ARRAY_LIST+index);
}

https://mizhou-njj.github.io/2020/01/24/data_struct/

评论