第十四周：*链表

14.1-1*可变数组

the Interface

1. Array array_create(int init_size);创建数组
   
2. void array_free(Array*a);回收数组
   
3. int array_size(const Array*a);告诉我们数组里面现在有几个单元可以使用
   
4. intarray_at(Arraya,int index);访问数组某个单元
   
5. void array_inflate(Array*a,int more_size);让数组
   

#ifndef _ARRAY_H_

#define _ARRAY_H_

typedefstruct {

   int*array;

   intsize;

}Array;

Arrayarray_create(intinit_size);

voidarray_free(Array*a);

intarray_size(constArray*a);

4.int*array_at(Array*a,intindex);

5.voidarray_inflate(Array*a,intmore_size);

#endif

#include "array.h"

Arrayarray_create(intinit_size)

{

   Arraya;//首先是数组的创建，需要用到动态内存分配，结合所需要的size，来创建一个数组

   a.size=init_size;

   a.array= (int*)malloc(sizeof(int)*a.size);

   returna;

}

voidarray_free(Array*a)//再然后就是内存的释放、得到数组的大小

{

   free(a->array);

   a->array=NULL;

   a->size=0;

}

intarray_size(constArray*a);

int*array_at(Array*a,intindex);

voidarray_inflate(Array*a,intmore_size);

intmain(intargc,charconst*argv[])

{

   Arraya=array_create(100);

   

   return0;

}

14.1-2可变数组的数据访问

//从上述第16行内容延续，这里需要多加两个标准头文件

#include

#include

//3-6行的代码叫做封装,能够将里面的内容保护起来，这样别人就不知道你里面什么样子的了，保持神秘感哈哈

intarray_size(constArray*a)

{

    returna->size;

}

int*array_at(Array*a,intindex)//在然后是进行该数组的访问和修改

    //这里面需要注意的是array_at的返回需要是一个指针，如此便可以做到修改

{

    return&(a->array[index]);

}

int*array_get(constArray*a,intindex);

{

   returna->array[index];

}

voidarray_set(Array*a,intindex, intvalue)

{

   a->array[index] =value;

}

voidarray_inflate(Array*a,intmore_size);

intmain(intargc,charconst*argv[])

{

   Arraya=array_create(100);

   printf("%d\n",array_size(&a));

   //printf("%d\n",a.size);十七行跟十六行一个意思

   *array_at(&a,0) =10;//将一个值写到数组里面

   printf("%d\n",*array_at(&a,0));

   array_free(&a);

   

   return0;

}

14.1-3可变数组的自动增长

//从上述24行延续

voidarray_inflate(Array*a,intmore_size)

{

    int*p= (int*)malloc(sizeof(int)(a->size+more_size));

    inti;

    for( i=0; i<a->size; i++ ) {

        p[i] =a->size[i];

    }//可以换成标准库的函数mencpy，效率更高

    free(a->array);

    a->array=p;

    a->size+=more_size;

}//核心代码

intmain(intargc,charconst*argv[])

{

   Arraya=array_create(100);

   printf("%d\n",array_size(&a));

   //printf("%d\n",a.size);十七行跟十六行一个意思

   *array_at(&a,0) =10;//将一个值写到数组里面

   printf("%d\n",*array_at(&a,0));

   intnumber;

   intcnt=0;

   while(number!=-1 ){

       scanf("%d",&number);

       if( number!=-1 ){

       *array_at(&a,cnt++) =number;

       //scanf("%d",array_at(&a,cnt++));

   }//无限的读入整数，让自己不断的自己增长

   array_free(&a);

   

   return0;

}

//第九行的内容改动

int*array_at(Array*a,intindex)//在然后是进行该数组的访问和修改

    //这里面需要注意的是array_at的返回需要是一个指针，如此便可以做到修改

{

   if( index>=a->size ){

       array_inflate(a,(index/BLOCK_SIZE+1)-a->size+1);//这里有点乱，后续要来修正

   }

    return&(a->array[index]);

}

14.2-1可变数组的缺陷

1. 申请使用内存，当我们需要更大的内存而之前的不需要了之后，之前的就会被废弃掉，在内存受限的情况下(比如单片机)就会导致内存明明还有，但是却已经申请不了更大的内存了(浪费内存空间)
   
2. 效率极低
   

14.2-2链表

1. 这是为百度进来补充的图，翁恺的课程是没有静态的图，用动态进行演示的
   

#include"node.h"

#include

#include

//typedef struct _node{

//    int value;

//    struct _node *next;

//}Node;

intmain(intargc,charconstargv[])

{

   Node*head=NULL;

   intnumber;

   do{

       scanf("%d",&number);

       if( number!=-1 ) {

           //add to linked-list

           Node*p= (Node*)malloc(size(Node));

           p->next=NULL;

           //find the last

           Node*last=head;

           if( last ){

               while (last->next){

                   last=last->next;

                   }

               //attach

               last->next=p;

               }else{

                   head=p;

           }

       }

   }while( number!=-1 );

   

   return0;

}

14.2-3链表的函数

#include"node.h"

#include

#include

//typedef struct _node{

//    int value;

//    struct _node *next;

//}Node;

voidadd(Node*head,intnumber);

typedefstruct_list{

   Node*head;

   Node*tail;

}List;

intmain(intargc,charconstargv[])

{

   Node*head=NULL;

   Listlist;

   intnumber;

   list.head=list.tail=NULL;

   do{

       scanf("%d",&number);

       if( number!=-1 ){

           add(&list,number);

       }

   }while( number!=-1);

   

   return0;

}

voidadd(List*pList,intnumber)

{

      //add to linked-list

   Node*p= (Node*)malloc(size(Node));

   p->value=number;

   p->next=NULL;

   //find the last

   Node*last=pList->head;

      if( last ){

         while (last->next){

             last=last->next;

           }

         //attach

          last->next=p;

         }else{

           head=p;

   }

   returnhead;

}

14.2-4链表的搜索

//从上述16行延续

voidprint(List*pList)//函数原型置顶，另外说明我没有把这个置顶到其他代码块里面

voidadd(List*pList,intnumber)    

 

intmain(intargc,charconstargv[])

{

   Node*head=NULL;

   Listlist;

   intnumber;

   list.head=list.tail=NULL;

   do{

       scanf("%d",&number);

       if( number!=-1 ){

           add(&list,number);

       }

   }while( number!=-1);

   

   printf(&list);

   scanf("%d",&number);

   Node*p;

   intisFound=0;

   for( p=list.head; p; p=p->next){

       if( p->value==number ){

           printf("找到了\n");

           isFound=1;

           break;

       }

   }

   if ( !isFound ){

       printf("没找到\n");

   }

   //Node*p;

   //for( p=list.head; p; p = p->next){

   //    printf("%d\t",p->value);

   //}//遍历，把链表每个节点的值打出来

   //printf("\n");  这些内容转移到下面了，并且有了一部分的改动

   

   return0;

}

voidadd(List*pList,intnumber)

{

      //add to linked-list

   Node*p= (Node*)malloc(size(Node));

   p->value=number;

   p->next=NULL;

   //find the last

   Node*last=pList->head;

      if( last ){

         while (last->next){

             last=last->next;

           }

         //attach

          last->next=p;

      }else{

           head=p;

      }

}

voidprint(List*pList){

   Node*p;

   for( p=list->head; p; p=p->next){

       printf("%d\t",p->value);

   }//遍历，把链表每个节点的值打出来

   printf("\n");

}

14.2-5链表的删除

//从上述第5行开始

intmain(intargc,charconstargv[])

{

   Node*head=NULL;

   Listlist;

   intnumber;

   list.head=list.tail=NULL;

   do{

       scanf("%d",&number);

       if( number!=-1 ){

           add(&list,number);

       }

   }while( number!=-1);

   

   printf(&list);

   scanf("%d",&number);

   Node*p;

   intisFound=0;

   for( p=NULL; p=list.head; q=p,p=p->next){

       if( p->value==number ){

           //需要考虑到边界效应，q没有进行限制需要进行限制

           if(q){

               q->next=p->next;

           } else {

               list.head=p->next;

           }

           //q->next = p->next;

           free(p);

           break;

       }

   }

   //Node*p;

   //for( p=list.head; p; p = p->next){

   //    printf("%d\t",p->value);

   //}//遍历，把链表每个节点的值打出来

   //printf("\n");  这些内容转移到下面了，并且有了一部分的改动

   

   return0;

}

14.2-6链表的清除

如何整个链表都清除掉

   //从上述19行开始

   for( p=NULL; p=list.head; q=p,p=p->next){

       if( p->value==number ){

           //需要考虑到边界效应，q没有进行限制需要进行限制

           if(q){

               q->next=p->next;

           } else {

               list.head=p->next;

           }

           //q->next = p->next;

           free(p);

           break;

       }

   }

   for( p=head; p; p=q ){

       q=p->next;

       free(p);

   }//链表这样就删除掉了    

   return0;

}