Day 16 顺序表(数组与结构体)

发布于:2021-10-25 03:19:41

1.线性表--顺序表(数组)


#include


#define MAX 10


?


typedef int Elementype; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//数组中元素类型 ,定义别名方便统一定义数据类型


?


void print(Elementype* array); ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //顺序列出元素


void insert_tail(Elementype* array,Elementype value); ? ? ? ? ? ? ? ? ? ? ? ??//在数组尾部 插入一个元素


void insert_index(Elementype* array,int index,Elementype value); ? ? ? //在指定位置插入指定数值


Elementype delete_index(Elementype* array,int index); ? ? ? ? ? ? ? ? ? ? ? ?//在指定位置删除数值


void delete_value(Elementype* array,Elementype value); ? ? ? ? ? ? ? ? ? ? ?//删除指定数值


?


int main()


{


??? Elementype array[MAX] = {0}; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //数组元素为0认为是空


??? print(array);


?


??? int i;


??? for(i = 0;i < 6;i++)


??? {


??????? insert_tail(array,i+1);


??? }


??? print(array);


???


??? insert_index(array,1,99);


??? print(array);


?


??? printf("delete_index :%d,value : %d
",1,delete_index(array,1));


??? print(array);


?


??? insert_index(array,4,5); ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//1 2 3 4 5 5 6


??? print(array);


??? delete_value(array,5);


??? print(array);


?


??? return 0;


}


?


void print(Elementype* array)


{


??? int i;


??? for(i = 0;i < MAX;i++)


??? {


??????? printf("%d ",array[i]);


??? }


??? printf("
");


}


?


void insert_tail(Elementype* array,Elementype value)


{


??? int len = 0;


??? while(array[len]) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//?while? ?( array[len++]?); ?/while(*(array+len++)); ?/while(*(array+len))?


??? { ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? // ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?{


? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?len++;


? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?} ?


??????? len++; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //


??? }


??? if(len >= MAX)


??? {


??????? printf("the array is full
");


??????? return;


??? }


??? array[len] = value;


}


?


void insert_index(Elementype* array,int index,Elementype value)


{


??? int len = 0;


??? int i;


??? while(*(array + len++));


??? if(len >= MAX)


??? {


??????? printf("the array is full
"); ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //判断元素是否溢出


??????? return;


??? }


?


??? if(index < 0 || index > len) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//大于等于0小于等于len插入值有效


??? {


??????? printf("index is error
");


??????? return;


??? }


?


??? for(i = len - 1;i >= index;i--) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //0到len-1中i位置上len-2覆盖len-1;len-1覆盖len,所以len递减


??? {


??????? array[i + 1] = array[i]; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//插入值腾出空间后面每个数后移,所以a[I]赋值a[i+1]


??? }


??? array[index] = value;


}


?


Elementype delete_index(Elementype* array,int index)


{


??? int len = 0;


??? while(array[len++]);


??? if(len <= 0) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//判断对象是否为空


??? {


??????? printf("the list is empty
");


??????? return;


??? }


?


??? if(index < 0 || index >= len) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??// 删除值0<=index<=len-1有效


??? {


??????? printf("index is error
");


??????? return;


??? }


?


??? Elementype value = array[index];


??? int i;


??? for(i = index;i < len - 1;i++) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //删除值后后面元素前移,数量变为len-2


??? {


??????? array[i] = array[i+1];


??? }


?


??? array[len-1] = 0;


??? return value;


}


?


void delete_value(Elementype* array,Elementype value)


{


??? int len = 0;


??? printf("the index of value %d = ",value);


??? while(array[len]) //1 2 3 4 5 6 7


??? {


??????? if(array[len] == value)


??????? {


??????????? printf("%d ",len);


??????????? delete_index(array,len);


??????? }


??????? else ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??//由于前移,判断前移的元素是否相同,不同则跳过,判断下个元素


??????? {


??????????? len++; ?


??????? }


??? }


??? printf("
");


}


?


类似的我们得出:2.线性表--顺序表(结构体)


?


#include


#include ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //定义malloc.realloc函数的头文件


?


#define TRUE 1


#define FALSE 0


?


int MAX = 10;


?


typedef int Elementype;


?


struct List ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//顺序表结构体


{


??? Elementype* head; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//顺序表的头指针


??? int length; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//顺序表的长度


};


?


int init(struct List* l); ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //若定义多个结构体方便大规模处理数据


void print(struct List l); ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?


int insert_tail(struct List* l,Elementype value); ? ? ? ? ? ? ? ? ? ? ? ? ?//尾插


int insert_index(struct List* l,int index,Elementype value); ? ? ? ?//指定位置插入指定数值


int delete_index(struct List* l,int index); ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //指定位置删除


int delete_value(struct List* l,Elementype value); ? ? ? ? ? ? ? ? ? ? ?//删除指定数值


int updata_index(struct List* l,int index,Elementype value); ? ? ? //更新指定位置指定数值


int query_value(struct List* l,Elementype value); ? ? ? ? ? ? ? ? ? ? ? ?//查询数值? ? ? ??


int empty(struct List* l); ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//清空结构体元素值


?


int main()


{


??? struct List list;


?


??? int ret;


??? ret = init(&list);


??? if(ret == FALSE)


??? {


??????? return 1;


??? }


?


??? int i;


??? for(i = 0;i < 20;i++)


??? {


??????? insert_tail(&list,i);


??? }


??? print(list);


?


??? insert_index(&list,2,99);


??? print(list);


?


??? delete_index(&list,2);


??? print(list);


?


??? insert_index(&list,2,2);


??? delete_value(&list,2);


??? print(list);


?


??? updata_index(&list,2,99);


??? print(list);


?


??? updata_index(&list,3,2);


??? updata_index(&list,8,2);


??? updata_index(&list,15,2);


??? print(list);


??? query_value(&list,2);


?


??? empty(&list);


?


??? return 0;


}


?


int init(struct List* l)


{


??? l->head = (Elementype*)malloc(MAX*sizeof(Elementype));


??? if(NULL == l->head)


??? {


??????? return FALSE;


??? }


??? l->length = 0;


??? return TRUE;


}


?


void print(struct List l)


{


??? int i;


??? for(i = 0;i < l.length;i++)


??? {


??????? printf("%d ",*(l.head + i));


??? }


??? printf("
");


}


?


int insert_tail(struct List* l,Elementype value)


{


??? if(l->length == MAX)


??? {


??????? l->head = (Elementype*)realloc(l->head,sizeof(Elementype)*(MAX + MAX / 2)); ? //必要的强制类型转换


??????? if(NULL == l->head)


??????? {


??????????? return FALSE;


??????? }


??????? MAX += MAX / 2;


??????? printf("realloc MAX = %d
",MAX);


??? }


??? *(l->head + l->length) = value;


??? l->length++;


??? return TRUE;


}


?


int insert_index(struct List* l,int index,Elementype value)


{


??? if(l->length == MAX)


??? {


??????? l->head = (Elementype*)realloc(l->head,sizeof(Elementype)*(MAX + MAX / 2));


??????? if(NULL ==l->head)


??????? {


??????????? return FALSE;


??????? }


??????? MAX += MAX / 2;


??????? printf("realloc MAX = %d
",MAX);


??? }


?


??? if(index < 0 || index > l->length) //0 <= index <= l->length


??? {


??????? printf("index is error
");


??????? return FALSE;


??? }


?


??? int i;


??? for(i = l->length - 1;i >= index;i--)


??? {


??????? *(l->head + i + 1) = *(l->head + i);


??? }


?


??? *(l->head + index) = value;


??? l->length++;


??? return TRUE;


}


?


int delete_index(struct List* l,int index)


{


??? if(index < 0 || index > l->length - 1) // 0 <= index <= l->length - 1


??? {


??????? printf("index is error
");


??????? return FALSE;


??? }


??? int i;


??? for(i = index;i < l->length -1;i++)


??? {


??????? *(l->head + i) = *(l->head + i + 1);


??? }


??? l->length--;


??? return TRUE;


}


?


int delete_value(struct List* l,Elementype value)


{


??? int i;


??? for(i = 0;i < l->length;i++)


??? {


??????? if(*(l->head + i) == value)


??????? {


??????????? delete_index(l,i);


??????????? i--;


??????? }


??? }


??? return TRUE;


}


?


int updata_index(struct List* l,int index,Elementype value)


{


??? if(index < 0 || index > l->length - 1)


??? {


??????? printf("index is error
");


??????? return FALSE;


??? }


??? *(l->head + index) = value;


??? return TRUE;


}


?


int query_value(struct List* l,Elementype value)


{


??? printf("query_value(%d) = ",value);


??? int i;


??? int flag = 0;


??? for(i = 0;i < l->length;i++)


??? {


??????? if(value == *(l->head + i))


??????? {


??????????? flag++;


??????????? printf("%d ",i);


??????? }


??? }


??? if(flag == 0)


??? {


??????? printf("Not Found
");


??????? return FALSE;


??? }


??? printf("
");


??? return TRUE;


}


?


int empty(struct List* l)


{


??? free(l->head);


??? l->head = NULL;


??? l->length = 0;


??? MAX = 10;


??? return TRUE;


}


?


?


?


?


?


?


?

相关推荐

最新更新

猜你喜欢