顺序表的实现以及功能；

xiaoxiao2021-04-14 44

1 #include"utili.h" 2 3 typedef struct SeqList 4 { 5 ElemType *base; 6 size_t capacity; 7 size_t size; 8 }SeqList; 9 10 void InitList(SeqList *lt);//初始化； 11 void show_list(SeqList *lt);//显示顺序表； 12 bool IsFaull(SeqList *lt);//判满； 13 bool IsEmpty(SeqList *lt);//判空； 14 bool push_back(SeqList *lt,ElemType x);//尾插； 15 bool push_pop(SeqList *lt,ElemType x);//头插； 16 bool push_front(SeqList *lt);//尾删； 17 bool pop_front(SeqList *lt);//头删； 18 bool insert_pos(SeqList *lt,ElemType x,int pos);//按位置插入; 19 bool insert_val(SeqList *lt,ElemType x);//按值插入; 20 bool erase_pos(SeqList *lt,int pos);//按位置删除; 21 bool erase_val(SeqList *lt,ElemType x);//按值删除; 22 int find(SeqList *lt,ElemType key);//查找数据; 23 size_t length(SeqList *lt);//求长度; 24 void clear(SeqList *lt);//清除表; 25 void sort(SeqList *lt);//排序; 26 void reverse(SeqList *lt);//逆置; 27 28 void InitList(SeqList *lt)//初始化 29 { 30 lt->base = (ElemType*)malloc(sizeof(ElemType)*DEFAULT_SIZE); 31 assert(lt->base != NULL); 32 lt->capacity = DEFAULT_SIZE; 33 lt->size = 0; 34 } 35 void show_list(SeqList *lt) 36 { 37 for(int i=0; i<lt->size; ++i) 38 { 39 cout<<lt->base[i]<<" "; 40 } 41 cout<<endl; 42 } 43 bool IsFaull(SeqList *lt) 44 { 45 if(lt->size >= lt->capacity) 46 return TRUE; 47 return FALSE; 48 } 49 bool IsEmpty(SeqList *lt) 50 { 51 if(lt->size == 0) 52 return TRUE; 53 return FALSE; 54 } 55 56 bool push_back(SeqList *lt,ElemType x) 57 { 58 if(IsFaull(lt)) 59 { 60 cout<<"顺序表已满，插入失败！"<<endl; 61 return FALSE; 62 } 63 lt->base[lt->size] = x; 64 lt->size++; 65 return TRUE; 66 } 67 68 bool push_pop(SeqList *lt,ElemType x) 69 { 70 if(IsFaull(lt)) 71 { 72 cout<<"顺序表已满，插入失败!"<<endl; 73 return FALSE;

74 }

75 for(int i=lt->size; i>=0; --i) 76 { 77 lt->base[i] =lt->base[i-1]; 78 } 79 lt->base[0] = x; 80 lt->size++; 81 return TRUE; 82 } 83 84 bool pop_front(SeqList *lt) 85 { 86 if(IsEmpty(lt)) 87 { 88 cout<<"表为空，删除失败!"<<endl; 89 return FALSE; 90 } 91 for(int i=0; i<lt->size-1; ++i) 92 { 93 lt->base[i] = lt->base[i+1]; 94 } 95 lt->size--; 96 return TRUE; 97 } 98 99 bool push_front(SeqList *lt) 100 { 101 if(IsEmpty(lt)) 102 { 103 cout<<"表为空，删除失败!"<<endl; 104 return FALSE; 105 } 106 lt->size--; 107 return TRUE; 108 } 109 110 bool insert_pos(SeqList *lt,ElemType x,int pos) 111 { 112 if(pos<0 || pos>lt->size) 113 { 114 cout<<"位置不合法!"<<endl; 115 return FALSE; 116 } 117 if(IsFaull(lt)) 118 { 119 cout<<"表已满，不能插入:"<<endl; 120 return FALSE; 121 } 122 for(int i=lt->size; i>pos; --i) 123 { 124 lt->base[i] = lt->base[i-1]; 125 } 126 lt->base[pos] = x; 127 lt->size++; 128 return TRUE; 129 } 130 131 bool insert_val(SeqList *lt,ElemType x) 132 { 133 if(IsFaull(lt)) 134 { 135 cout<<"顺序表已满，插入失败!"<<endl; 136 return FALSE; 137 } 138 int i; 139 for( i=0; i<lt->size-1; ++i) 140 { 141 if(x<lt->base[i]) 142 break; 143 } 144 for(int j=lt->size;j>i;--j) 145 { 146 lt->base[j] = lt->base[j-1]; 147 } 148 lt->base[i] = x; 149 lt->size++; 150 } 151 152 bool erase_pos(SeqList *lt,int pos) 153 { 154 if(IsEmpty(lt)) 155 { 156 cout<<"顺序表为空，不能删除"<<endl; 157 return FALSE; 158 } 159 if(pos<0 || pos>=lt->size) 160 { 161 cout<<"位置非法，不能删除!"<<endl; 162 return FALSE; 163 } 164 for(int i=pos;i<lt->size;i++) 165 { 166 lt->base[i] = lt->base[i+1]; 167 } 168 lt->size--; 169 } 170 171 bool erase_val(SeqList *lt,ElemType x) 172 { 173 if(IsEmpty(lt)) 174 { 175 cout<<"顺序表为空，不能删除!"<<endl; 176 return FALSE; 177 } 178 int pos = find(lt,x); 179 if(pos == -1) 180 { 181 cout<<"要删除的值不存在，不能删除!"<<endl; 182 return FALSE; 183 } 184 erase_pos(lt,pos); 185 186 } 187 188 int find(SeqList *lt,ElemType key) 189 { 190 if(IsEmpty(lt)) 191 { 192 cout<<"顺序表为空，查找失败!"<<endl; 193 194 } 195 for(int i=0;i<lt->size;++i) 196 { 197 if(lt->base[i] == key) 198 return i; 199 } 200 return -1; 201 } 202 size_t length(SeqList *lt) 203 { 204 return lt->size; 205 } 206 207 void clear(SeqList *lt) 208 { 209 lt->size = 0; 210 } 211 void sort(SeqList *lt) 212 { 213 if(IsFaull(lt) || lt->size == 1) 214 return; 215 ElemType temp; 216 for(int i=0; i<lt->size-1; ++i) 217 { 218 for(int j=0; j<lt->size-i; ++j) 219 { 220 if(lt->base[j] >lt-> base[j+1]) 221 { 222 temp = lt->base[j]; 223 lt->base[j] = lt->base[j+1]; 224 lt->base[j+1] = temp; 225 } 226 } 227 } 228 } 229 void reverse(SeqList *lt) 230 { 231 if(IsFaull || lt->size == 1) 232 return ; 233 int low = 0; 234 int high = lt->size-1; 235 ElemType temp; 236 while(low < high) 237 { 238 temp = lt->base[low]; 239 lt->base[low] = lt->base[high]; 240 lt->base[high] = temp; 241 low++; 242 high--; 243 } 244 } /

主函数

1 #include"utili.h" 2 #include"seqlist.h" 3 int main() 4 { 5 ElemType item; 6 int pos,len; 7 8 SeqList mylist; 9 InitList(&mylist); 10 int select = 1; 11 while(select) 12 { 13 cout<<"********************************"<<endl; 14 cout<<"*[1] push_back [2]pop_back*"<<endl; 15 cout<<"*[3] show_list [0] quit *"<<endl; 16 cout<<"*[4] push_front [5] pop_front*"<<endl; 17 cout<<"*[6] insert_pos [7] insert_val"<<endl; 18 cout<<"*[8] erase_pos [9] erase_val*"<<endl; 19 cout<<"*[10] find [11] sort *"<<endl; 20 cout<<"*[12] length [13] clear *"<<endl; 21 cout<<"*[14] reverse *"<<endl; 22 cout<<"********************************"<<endl; 23 cout<<"请选择：>"; 24 cin>>select; 25 switch(select) 26 { 27 case 1: 28 29 cout<<"输入要插入的数据，以-1结束:"; 30 while(cin>>item,item != -1) 31 { 32 push_back(&mylist,item); 33 } 34 break; 35 36 case 2: 37 cout<<"请输入要插入的数据，以-1结尾:"; 38 while(cin>>item,item != -1) 39 { 40 push_pop(&mylist,item); 41 } 42 break; 43 44 case 3: 45 show_list(&mylist); 46 break; 47 48 case 4: 49 break; 50 case 5: 51 pop_front(&mylist); 52 break; 53 54 case 6: 55 cout<<"输入插入的数据:>"; 56 cin>>item; 57 cout<<"输入要插入的位置:"; 58 cin>>pos; 59 insert_pos(&mylist,item,pos); 60 break; 61 case 7: 62 cout<<"输入要插入的数据:>"; 63 cin>>item; 64 insert_val(&mylist,item); 65 break; 66 case 8: 67 cout<<"请输入要删除的位置:>"; 68 cin>>pos; 69 erase_pos(&mylist,pos); 70 break; 71 72 case 9: 73 cout<<"输入要删除的数据:"; 74 cin>>item; 75 erase_val(&mylist,item); 76 break; 77 78 case 10: 79 cout<<"输入要查找的数据:>"; 80 cin>>item; 81 pos = find(&mylist,item); 82 cout<<"pos = "<<pos<<endl; 83 break; 84 case 11: 85 sort(&mylist); 86 break; 87 case 12: 88 len = length(&mylist); 89 cout<<"len = "<<len<<endl; 90 break; 91 case 13: 92 clear(&mylist); 93 break; 94 case 14: 95 reverse(&mylist); 96 break; 97 case 0: 98 break; 99 default: 100 break; 101 } 102 } 103 return 0; 104 }

转载请注明原文地址: https://ju.6miu.com/read-670243.html

技术

最新回复(0)