14.1-1*可变数组
the Interface
- Array array_create(int init_size);创建数组
- void array_free(Array*a);回收数组
- int array_size(const Array*a);告诉我们数组里面现在有几个单元可以使用
- intarray_at(Arraya,int index);访问数组某个单元
- 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可变数组的缺陷
- 申请使用内存，当我们需要更大的内存而之前的不需要了之后，之前的就会被废弃掉，在内存受限的情况下(比如单片机)就会导致内存明明还有，但是却已经申请不了更大的内存了(浪费内存空间)
- 效率极低
14.2-2链表
- 这是为百度进来补充的图，翁恺的课程是没有静态的图，用动态进行演示的
#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;
}
