1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173
| #include <stdio.h> #include <malloc.h>
//线性表
#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量 #define LISTINCREMENT 10 //线性表存储空间的分配增量(当存储空间不够时要用到)
typedef int ElemType; //数据元素的类型,假设是int型的
typedef struct{ ElemType *elem; //存储空间的基地址 int length; //当前线性表的长度 int listsize; //当前分配的存储容量 }LinearList;
int init_list(LinearList* list){ list->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType)); if (!list->elem){ return -1; //空间分配失败 } list->length = 0; //当前长度 list->listsize = LIST_INIT_SIZE; //当前分配量 return 0; }
void clear_list(LinearList* list){ list->length = 0; //当前长度 }
void destroy_list(LinearList* list){ free(list); }
int list_empty(LinearList* list){ return (list->length == 0); }
int list_length(LinearList* list){ return list->length; }
void print_list(LinearList* list){ int i; for (i=0; i < list->length; i++){ printf("%d ", list->elem[i]); } printf("\n"); }
int locate_elem(LinearList* list, ElemType* x){ int pos = -1; for (int i = 0; i < list->length; i++){ if (list->elem[i] == *x){ pos = i; } } return pos; }
int prior_elem(LinearList* list, ElemType* cur_elem, ElemType* pre_elem){ int pos = -1; pos = locate_elem(list, cur_elem); if(pos <= 0) return -1; *pre_elem = list->elem[pos-1]; return 0; }
int get_elem(LinearList* list, int index, ElemType* e){ if (index<0 || index >= list->length) return -1; *e = list->elem[index]; return 0; }
int next_elem(LinearList* list, ElemType* cur_elem, ElemType* next_elem){ int pos = -1; pos = locate_elem(list, cur_elem); if(pos == -1 || pos == (list->length - 1)) return -1; *next_elem = list->elem[pos+1]; return 0; }
int insert_elem(LinearList* list, int index, ElemType* e){ if (index<0 || index >= list->length) return -1; if (list->length >= list->listsize){ //判断存储空间是否够用 ElemType *newbase = (ElemType *)realloc(list->elem, (list->listsize + LISTINCREMENT)*sizeof(ElemType)); if (!newbase) return -1;//存储空间分配失败 list->elem = newbase;//新基址 list->listsize += LISTINCREMENT;//增加存储容量 } ElemType *q, *p; q = &(list->elem[index]); //q为插入位置 for (p = &(list->elem[list->length - 1]); p >= q; --p){ //从ai到an-1依次后移,注意后移操作要从后往前进行 *(p + 1) = *p; } *q = *e; ++list->length; return 0; }
int delete_elem(LinearList* list, int index, ElemType* e) { if (index<1 || index > list->length) return -1; ElemType *q, *p; p = &(list->elem[index]);//p为被删除元素的位置 *e = *p; //被删除的元素赋值给e q = list->elem + list->length - 1;//q指向表尾最后一个元素 for (++p; p <= q; ++p){ //从p的下一个元素开始依次前移 *(p - 1) = *p; } --list->length; return 0; }
int append_elem(LinearList* list,ElemType* e){ if (list->length >= list->listsize){ //判断存储空间是否够用 ElemType *newbase = (ElemType *)realloc(list->elem, (list->listsize + LISTINCREMENT)*sizeof(ElemType)); if (!newbase) return -1;//存储空间分配失败 list->elem = newbase;//新基址 list->listsize += LISTINCREMENT;//增加存储容量 } list->elem[list->length] = *e; ++list->length; return 0; }
int pop_elem(LinearList* list, ElemType* e){ if (list_empty(list)) return -1; *e = list->elem[list->length - 1]; --list->length; return 0; }
void union_list(LinearList* list_a, LinearList* list_b, LinearList* list_c){ //并集,C=A∪B int i,a_length,b_length; ElemType elem; a_length = list_length(list_a); b_length = list_length(list_b); for(i=0;i<a_length;i++){ get_elem(list_a, i, &elem); append_elem(list_c,&elem); } for(i=0;i<b_length;i++){ get_elem(list_b, i, &elem); if(locate_elem(list_a, &elem) == -1){ append_elem(list_c,&elem); } } }
void intersect_list(LinearList* list_a, LinearList* list_b, LinearList* list_c){ //交集,C=A∩B int i,a_length; ElemType elem; a_length = list_length(list_a); for(i=0;i<a_length;i++){ get_elem(list_a, i, &elem); if(locate_elem(list_b, &elem) != -1){ append_elem(list_c,&elem); } } }
void except_list(LinearList* list_a,LinearList* list_b, LinearList* list_c){ //差集,C=A-B(属于A而不属于B) int i,a_length; ElemType elem; a_length = list_length(list_a); for(i=0;i<a_length;i++){ get_elem(list_a, i, &elem); if(locate_elem(list_b, &elem) == -1){ append_elem(list_c,&elem); } } }
|