C言語、単一チェーンテーブル操作(添削・変更)(version 0.1)

 1 //  File Name     : list.h
 2 #include "stdafx.h"
 3 #include "stdio.h"
 4 #include <stdlib.h>
 5 #include "string.h"
 6  
 7 //creat list
 8 //creat node 
 9 //insert
10 //del
11 //find
12 //sort
13 typedef int data_t ;
14 typedef struct NODE{
15     data_t data;
16     NODE* next;
17 }NODE ,*NODEPTR;
18 
19 typedef struct LIST{
20     NODE* head;//init==0
21     NODE* tail;//init==0
22     int num ;  //min==0
23 }LIST;
24 
25 //create
26 extern NODE *create_node(data_t data);
27 extern LIST *creat_list();
28 extern bool is_null(LIST* list);
29 //find
30 extern NODE* find_node(LIST* list ,data_t data);
31 extern NODE* inline find_node_by_index(LIST* list , int index);//index : from 1 to list->num
32 
33 //del
34 extern int del_node_data(LIST* list,data_t data);
35 extern data_t del_node_head(LIST* list );
36 extern data_t del_node_index(LIST* list,int index);//index : from 1 to list->num
37 extern data_t del_node_tail(LIST* list );
38 
39 //insert
40 extern int insert_data_F(LIST* list, data_t data);
41 extern void insert_node_F(LIST* list, NODE* node);
42 extern int insert_data_T(LIST* list, data_t data);
43 extern void insert_node_T(LIST* list, NODE* node );
44 extern int insert_data_index(LIST* list , data_t data,int index);//index : from 1 to list->num
45 extern int insert_node_index(LIST* list , NODE* node,int index);//index : from 1 to list->num
46 
47 extern int insert_data_ordered(LIST* list , data_t data );//assume the list is ordered (low to high )48 
49 //sort
50 extern int sort(LIST* list);
51 extern int swap(LIST* list, int indexf,int indexn);//index : from 1 to list->num
52 extern int inline swap_node(NODE* before ,NODE* next);
53  

  1 /******************************************************************************
  2 
  3   Copyright (C), 2001-2011, DCN Co., Ltd.
  4 
  5  ******************************************************************************
  6   File Name     : list.c
  7   Version       : Initial Draft
  8   Author        : ocj
  9   Created       : 2014/8/8
 10   Last Modified :
 11   Description   : singlelist
 12   Function List :
 13               create_node
 14               creat_list
 15               del_node_data
 16               del_node_head
 17               del_node_index
 18               del_node_tail
 19               find_node
 20               find_node_by_index
 21               insert_data_F
 22               insert_data_index
 23               insert_data_ordered
 24               insert_data_T
 25               insert_node_F
 26               insert_node_index
 27               insert_node_T
 28               is_null
 29               sort
 30               swap
 31               swap_node
 32   History       :
 33   1.Date        : 2014/8/8
 34     Author      : ocj
 35     Modification: Created file
 36 
 37 ******************************************************************************/
 38 #include "list.h"
 39 //if success :ret!=0
 40 LIST *creat_list()
 41 {
 42     LIST* list = (LIST*)malloc(sizeof(LIST));
 43     list->head = 0;
 44     list->tail = 0;
 45     list->num = 0;
 46     return list;
 47 }
 48 //if success :ret!=0
 49 NODE *create_node(data_t data)
 50 {
 51     NODE* node = (NODE*)malloc(sizeof(NODE)); 
 52     node->dext = 0;
 53     node.data = data;
 54     return node;
 55 }
 56 
 57 //return 1: is null
 58 //return 0: not null
 59 bool is_null(LIST* list)
 60 {
 61     //return (list->num==0); //method 1 
 62     return (list->head->next == 0 )    ;//method 2
 63 }
 64 
 65 //ret==0:fail
 66 int insert_node_F(LIST* list, NODE* node)
 67 {
 68     if(list==0 || node ==0){
 69         return 0;
 70     }
 71     if(list->head==0){
 72         list->tail = node;
 73     }
 74     list->head = node ;
 75     node->next = list->head;
 76 //if list is null     ,node->next == list->head==0
 77 //if list is not null ,node->next == list->head!=0
 78     list->num++;  
 79 }
 80 
 81 //return 1 : ok
 82 //return 0 : fail
 83 int insert_data_F(LIST* list, data_t data)
 84 {
 85     NODE* node = create_node(data);
 86     if(node){
 87         return 0;
 88     }
 89     insert_node_F(list , node);
 90     return 1;
 91 }
 92 
 93 void insert_node_T(LIST* list, NODE* node )
 94 {
 95     if(list->head==0){
 96         node->next = 0;
 97         list->head = list->tail = node;
 98     }
 99     
100     list->tail = node ;
101     node->next = 0 ;
102     list->num++;
103 }
104 
105 //return 1 : ok
106 //return 0 : fail
107 int insert_data_T(LIST* list, data_t data)
108 {
109     NODE* node = create_node(data);
110     if(node){
111         return 0;
112     }
113     insert_node_T(list , node);
114     return 1;
115 }
116 
117 //ret=0: fail
118 int insert_node_index(LIST* list , NODE* node,int index)
119 {
120     if(index>listnum+1)    {
121         return 0;
122     }
123         
124     if(index==1){
125         insert_node_F(list ,node);
126     }else if(index ==list->num+1){
127         insert_node_T(list ,node);
128     }else{
129         NODE* before = list->head;
130         while(index>2){
131             index--;
132             before = before->next;        
133         }
134         node->next = before->next ;
135         before->next = node ;
136         list->num++;
137     }
138     return 1;
139 }
140 //ret=0: fail
141 int insert_data_index(LIST* list , data_t data,int index)
142 {
143     NODE* node = create_node(data)    ;
144     if(node==null){
145         return 0 ;
146     }
147     return insert_node_index(list , node,index );
148 }
149 
150 //assume the order is low to high
151 //ret==0: fail
152 int insert_data_ordered(LIST* list , data_t data )
153 {
154     NODE* node = create_node(data);
155     if(node==0){
156         return 0;
157     }
158     if(list->head == 0){
159         list->head = list->tail = node;
160         return 1;
161     }
162     
163     if(node->data < head->data){
164         insert_data_F(list ,node);
165     }else {
166         list->num++;
167         NODE *before = head;
168         NODE* nodet = head->next ;
169         while(node->data > nodet->data && nodet->next!=0){
170          //until( node->data < nodet->data  || tail )
171             nodet = nodet->next ;
172             before = before->next;    
173         }
174         if(nodet->next==0){
175             nodet->next = node ;
176         }else{
177             node->next = nodet ;
178             before->next = node ;
179         }
180     }
181     return 1;
182 }
183 
184 //not find: return 0
185 //success find and del :return 1 
186 int del_node_data(LIST* list,data_t data)  //find and del first_found
187 {
188     if(list->num ==0){
189         return 0;
190     }
191     
192     NODE* before = list->head ;    
193     NODE* nodet = list->head ;    
194     if(nodet->data == data){ //head->data == data
195         list->head = list->head->next ;
196         free(nodet);
197         list->num--;
198         return 1;
199     }
200     
201     nodet = nodet->next;
202     while(nodet->data!=data  && nodet->next!=0  ){
203         nodet = nodet->next;
204     }
205     if(nodet->data == data ){
206         before->next = nodet->next ;
207         free(nodet);
208         list->num--;
209     }else{//not found
210         return 0;
211     }
212     return 1;
213 }
214 
215 
216 data_t del_node_index(LIST* list,int index)
217 {
218     if(is_null(list) || index > list->num){
219         exit(-1);
220     }
221     NODE* before = list->head ;
222     NODE* del = list->head ;
223     data_t data ;
224     if(list->num == 1 )    { //head
225         list->num--;
226         list->head = list->tail = 0; 
227         data = del->data;
228         free(del);
229         return data;
230     }
231     
232     int first = 1 ;
233     for( ;index>1;index--){//offset --- index   
234         if(!first){
235             before = before->next ;
236         }
237         first = 0;
238         del = del->next;
239     }
240     
241     before->next = del->next ;
242     data = del->data;
243     if(del==list->tail){
244         list->tail = before ;    
245     }
246     free(del);
247     list->num--;
248     return data;
249 
250 } 
251 data_t del_node_head(LIST* list )
252 {
253     if(is_null(list)){
254         exit(-1) ;
255     }
256     data_t data ;
257     NODE* del = list->head ;
258     list->head = list->head->next ;
259     free(del);
260     list->num--;
261     return data;
262 }
263 data_t del_node_tail(LIST* list )
264 {
265     if(is_null(list)){
266         exit(-1) ;
267     }
268     NODE *before = list->head  ;
269     data_t data = list->tail->data;
270             
271     if(list->num ==1){
272         list->head = list->tail = 0;
273         list->num--;
274         free(before);
275         return data ;
276     }
277 
278     while(before->next!=0 && before->next->next != 0)    {
279         before = before->next ;
280     }
281     
282     list->tail = before;
283     list->num--;
284     free(before->next);
285     return data ;
286 }
287 
288 //return 0: fail to find 
289 //return node* : node first_found
290 NODE* find_node(LIST* list ,data_t data)
291 {
292     if(is_null(list)){
293         return 0 ;
294     }
295     
296     NODE* nodet = list->head;
297     do{
298         if(nodet->data == data)
299             return nodet;
300     }while(nodet->next!=0);
301 
302     return 0;
303 }
304 
305 //head_index == 1;
306 //return 0: fail to find 
307 //return node* : node first_found
308 NODE* inline find_node_by_index(LIST* list , int index)
309 {
310     if(list==0 || list->num ==0 || index > list->num){
311         return 0;
312     }
313     NODE* find = list->head;
314     while(--index){
315         find =find->next; 
316     }
317     return find ;
318 }
319 
320 int swap(LIST* list, int indexf,int indexn)
321 {
322     NODE* nodef = find_node( list , indexf ) ;
323     NODE* noden = find_node( list , indexn ) ;
324     data_t swp = nodef->data;
325     nodef->data = noden->data;
326     noden->data = swp->data;
327 }
328 
329 //ret==0 : fail
330 int inline swap_node(NODE* before ,NODE* next)
331 {
332     if(before == 0 ||next == 0){
333         return 0;
334     }
335     before->data ^=next->data ;
336     next->data      ^=before->data ;
337     before->data ^=next->data ;
338 }
339 
340 //asume from little to big
341 int sort(LIST* list)
342 {
343     int times;
344     int index;
345     NODE* before = list->head;
346     NODE* next =  0;    
347     if(list==0){
348         return 0;
349     }
350     if(list->num==0){
351         return 1 ;
352     }
353     for(times=0;times<list->num ;times++){
354         for(index=1;index<=size-times;index++){
355             before = find_node_by_index(list ,index);
356             next = before->next;
357             if(next->data<before->data){
358                 //before->data = before->data^ next->data ;            
359                 //nexty->data  = before->data^ next->data ;            
360                 //before->data = before->data^ next->data ;
361                 swap_node(before , next);
362             }
363     }
364     return 1;    
365 }