10.1 可变数组
Example 01：
- array.h
#ifndef _ARRAY_H_
#define _ARRAY_H_
typedef struct {
int *array;
int size;
}Array;
#define BLOCK_SIZE 20
Array array_create(int init_size);
void array_free(Array *a);
int array_size(const Array *a);
int *array_at(Array *a,int index);
void array_inflate(Array *a,int more_size);
int array_get(const Array *a,int index);
void array_set(Array *a,int index,int value);
#endif- array.c
#include "array.h"
#include <stdio.h>
#include <stdlib.h>
//typedef struct {
//int *array;
//int size;
//}Array;
Array array_create(int init_size){
Array a;
a.size = init_size;
a.array = (int *)malloc(sizeof(int)*a.size);
return a;
}
void array_free(Array *a){
free(a->array);
a->array = NULL;
a->size = 0;
}
int array_size(const Array *a){
return a->size;
}
int *array_at(Array *a,int index){
if(index>=a->size){
//array_inflate(a,index-a->size+1);
array_inflate(a,(index/BLOCK_SIZE +1)*BLOCK_SIZE-a->size);
}
return &(a->array[index]);
}
//可变字符自动按块增长
void array_inflate(Array *a,int more_size){
int *p = (int *)malloc(sizeof(int)*(a->size + more_size));
int i;
for(i=0;i<a->size;i++){
p[i] = a->array[i];
}
free(a->array);
a->array = p;
a->size += more_size;
}
int array_get(const Array *a,int index){
return a->array[index];
}
void array_set(Array *a,int index,int value){
a->array[index] = value;
}
int main(){
Array a = 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));
int number;
int cnt = 0;
while(number != -1){
scanf("%d",&number);
if(number!=-1){
*array_at(&a,cnt++) = number;
}
}
array_free(&a);
return 0;
}可变数组的缺陷
- 要 copy，不能充分利用
10.2 链表存储数据
链表存储数据 add
- Example 01：
#include <stdio.h>
#include <stdlib.h>
typedef struct _node{
int value;
struct _node *next;
}Node;
int main(){
Node *head = NULL;
int number;
do{
scanf("%d",&number);
if(number != -1){
// add to linkList
Node *p = (Node*)malloc(sizeof(Node));
p->value = number;
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);
return 0;
}- Example 02：对 01 进行改进
#include <stdio.h>
#include <stdlib.h>
typedef struct _node{
int value;
struct _node *next;
}Node;
Node* add(Node *head, int number);
int main(){
Node *head = NULL;
int number;
do{
scanf("%d",&number);
if(number != -1){
head = add(head,number);
}
} while(number != -1);
return 0;
}
Node* add(Node *head, int number){
// add to linkList
Node *p = (Node*)malloc(sizeof(Node));
p->value = number;
p->next = NULL;
// find the last
Node *last = head;
if(last){
while(last->next){
last = last->next;
}
// attach
last->next = p;
}else{
head = p;
}
return head;
}- Example 02：对 01 进行改进
#include <stdio.h>
#include <stdlib.h>
typedef struct _node{
int value;
struct _node *next;
}Node;
Node* add(Node **pHead, int number);
int main(){
Node *head = NULL;
int number;
do{
scanf("%d",&number);
if(number != -1){
head = add(&head,number);
}
} while(number != -1);
return 0;
}
Node* add(Node **pHead, int number){
// add to linkList
Node *p = (Node*)malloc(sizeof(Node));
p->value = number;
p->next = NULL;
// find the last
Node *last = *pHead;
if(last){
while(last->next){
last = last->next;
}
// attach
last->next = p;
}else{
*pHead = p;
}
return *pHead;
}- Example 03：对 02 进行改进
#include <stdio.h>
#include <stdlib.h>
typedef struct _node{
int value;
struct _node *next;
}Node;
typedef struct _list{
Node *head;
}List;
void add(List *pList, int number);
int main(){
List list;
list.head = NULL;
int number;
do{
scanf("%d",&number);
if(number != -1){
add(&list,number);
}
} while(number != -1);
return 0;
}
void add(List *pList, int number){
// add to linkList
Node *p = (Node*)malloc(sizeof(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{
pList->head = p;
}
}- Example 04：对 03 进行改进
typedef struct _node{
int value;
struct _node *next;
}Node;
typedef struct _list{
Node *head;
Node *tail;
}List;
void add(List *pList, int number);
int main(){
List list;
list.head = list.tail = NULL;
int number;
do{
scanf("%d",&number);
if(number != -1){
add(&list,number);
}
} while(number != -1);
return 0;
}待完善：list.tail
10.3 链表输出数据
链表输出数据 print
- Example 01：
#include <stdio.h>
#include <stdlib.h>
typedef struct _node{
int value;
struct _node *next;
}Node;
typedef struct _list{
Node *head;
Node *tail;
}List;
void add(List *pList, int number);
int main(){
List list;
list.head = list.tail = NULL;
int number;
do{
scanf("%d",&number);
if(number != -1){
add(&list,number);
}
} while(number != -1);
Node *p;
//遍历输出
for(p=list.head;p;p=p->next){
printf("%d\t",p->value);
}
printf("\n");
return 0;
}
void add(List *pList, int number){
// add to linkList
Node *p = (Node*)malloc(sizeof(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{
pList->head = p;
}
}- Example 02：对 01 进行优化
#include <stdio.h>
#include <stdlib.h>
typedef struct _node{
int value;
struct _node *next;
}Node;
typedef struct _list{
Node *head;
//Node *tail;
}List;
void add(List *pList, int number);
void print(List *pList);
int main(){
List list;
list.head = NULL;
int number;
do{
scanf("%d",&number);
if(number != -1){
add(&list,number);
}
} while(number != -1);
print(&list);
return 0;
}
void add(List *pList, int number){
// add to linkList
Node *p = (Node*)malloc(sizeof(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{
pList->head = p;
}
}
void print(List *pList){
Node *p;
//遍历输出
for(p=pList->head;p;p=p->next){
printf("%d\t",p->value);
}
printf("\n");
}- Test Result
声明：本文由 公爵（博主）原创，依据 CC-BY-NC-SA 4.0 许可协议 授权，转载请注明出处。
本站由
