本文实例讲述了C语言实现顺序表(线性表)的方法。分享给大家供大家参考，具体如下：

一：顺序表代码实现

? 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 174 #ifndef _SEQ_LIST_H #define _SEQ_LIST_H #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <string.h> #define ElemType float //以float类型测试算法通用性，而不是以惯用的int #define INIT_SIZE 10 //顺序表默认初始化大小 #define LIST_INCREMENT 5 //顺序表容量增量，容量不够使用malloc申请 #define list_full(list) ((list)->size >= (list)->capacity ? 1 : 0) //顺序表判满 #define list_empty(list) ((list)->size == 0 ? 1 : 0) //判空 typedef ElemType value_type; //元素类型 typedef value_type* value_ptr; //元素指针类型 typedef enum {false, true}bool; //为C语言增加bool量 typedef enum {POSITION, VALUE}DELETE_MODE; //删除元素模式选择，分别为按位置删除和按值删除 typedef struct sequelize_list{ ElemType *base; //顺序表基址 int size; //顺序表元素大小 int capacity; //顺序表容量 } seq_list, *list_ptr; void init_list(list_ptr lp) //初始化 { assert(lp != NULL); lp->base = (value_ptr)malloc(sizeof(value_type)*INIT_SIZE); //free assert(lp->base != NULL); memset(lp->base, 0, sizeof(value_type)*INIT_SIZE); lp->size = 0; lp->capacity = INIT_SIZE; } bool insert_elem(list_ptr lp, const int pos, const value_type elem) //插入元素 { assert(lp != NULL && pos >= 1 && pos <= lp->size+1); if(list_full(lp)){ //如果表满，追加申请空间 value_ptr new_base = (value_ptr)realloc(lp->base, sizeof(value_type)*(lp->capacity+LIST_INCREMENT));//此处注意realloc用法，用新地址接收是为了防止realloc失败，原地址有效内容被释放 assert(new_base != NULL); //并且realloc填写的申请空间大小必须是之前的大小+增量的大小，而不是只写增量，否则如果原地址内存不够，在新地址申请增量大小的空间，将之前的内容挪至新空间，内存溢出，将发生段错误 lp->base = new_base; //再赋回给原地址 lp->base[lp->capacity] = elem; lp->capacity += LIST_INCREMENT; ++lp->size; } else{ //未满，插入元素 for(int i=lp->size-1; i>=pos-1; --i){ //将元素后移，腾出位置 lp->base[i+1] = lp->base[i]; } lp->base[pos-1] = elem; //插入元素 ++lp->size; //} return true; } bool remove_elem_pos(list_ptr *lp, const int pos) //按位置删除 { assert(pos >= 1 && pos <= (*lp)->size); for(value_ptr ptmp=&(*lp)->base[pos-1]; ptmp<&(*lp)->base[(*lp)->size-1]; ++ptmp) *ptmp = *(ptmp+1); (*lp)->base[(*lp)->size-1] = 0; --(*lp)->size; return true; } bool remove_elem_val(list_ptr *lp, value_type elem) //按值删除 { for(int i=0; i<(*lp)->size; ++i) if((*lp)->base[i] == elem){ for(int j=i; j<(*lp)->size-1; ++j) //所有符合要求的值都被删除 (*lp)->base[j] = (*lp)->base[j+1]; (*lp)->base[(*lp)->size-1] = 0; --(*lp)->size; } return true; } bool remove_elem(list_ptr lp, const void* clue, DELETE_MODE mode) //外部接口，第三个参数选择按位置或按值删除模式 { assert(lp != NULL); if(list_empty(lp)){ //表空，不能删 fprintf(stdout, "already empty, can not remove.\n"); return false; } if(mode == POSITION){ //参数为POSITION，按位置删除 remove_elem_pos(&lp, *(int *)clue); } else{ //否则按值删除 remove_elem_val(&lp, *(value_ptr)clue); } return true; } void print_list(const seq_list sl) //打印函数 { if(sl.size == 0) fprintf(stdout, "nil list."); for(int i=0; i<sl.size; ++i) printf("%f ", sl.base[i]); printf("\n"); } int compare(const void *vp1, const void* vp2) //比较函数 { return *(value_ptr)vp1 - *(value_ptr)vp2; } int locate_elem(const seq_list sl, const value_type elem, int (*compare)(const void *, const void *)) //定位函数 { if(list_empty(&sl)){ fprintf(stdout, "list empty, con not locate.\n"); } else{ for(int i=0; i<sl.size; ++i) if((*compare)(&sl.base[i], &elem) == 0) //相等则找到，返回位置 return i+1; } return 0; } void sort_list(list_ptr lp, int (*compare)(const void *, const void *)) //排序函数 { assert(lp != NULL); qsort(lp->base, lp->size, sizeof(value_type), compare); //调用系统快速排序 } void merge_list(list_ptr lpa, list_ptr lpb, list_ptr combine, int (*compare)(const void *, const void *)) //合并两个顺序表 { assert(lpa != NULL && lpb != NULL && combine != NULL); combine->base = (value_ptr)malloc(sizeof(value_type) *(lpa->size+lpb->size)); //此处为新表申请空间，因此新表无需另外调用初始化函数，否则会发生内存泄漏 assert(combine->base != NULL); combine->capacity = combine->size = lpa->size+lpb->size; value_ptr it_pc = combine->base; value_ptr it_pa=lpa->base; value_ptr it_pb=lpb->base; while(it_pa<lpa->base+lpa->size && it_pb<lpb->base+lpb->size){ //由小到大插入新表 if(compare(it_pa, it_pb) <= 0) *it_pc++ = *it_pa++; else *it_pc++ = *it_pb++; } while(it_pa < lpa->base+lpa->size) //从上面while出循环只有两种情况，此处为pa为插完，pb已插完，pa剩余元素直接插入，天然有序 *it_pc++ = *it_pa++; while(it_pb < lpb->base+lpb->size) //同理，若pb剩有元素，直接插入，天然有序 *it_pc++ = *it_pb++; } #endif

二：测试代码

? 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 为保证通用性，不用int，用float测试。 #include "seq_list.h" #define ARRAY_SIZE 10 int main() { value_type array[] = {39.1, 32.1, 10.1, 11.1, 22.1, 5.1, 36.1, 28.1, 46.1, 32.1}; seq_list list; //顺序表1 init_list(&list); for(int i=0; i<ARRAY_SIZE; ++i) insert_elem(&list, 1, array[i]); printf("list:\n"); print_list(list); #if 1 int clue = 1; //按顺序删除，删除第一个元素 //value_type clue = 32.1; //按值删除，删除值为32.1的元素，需修改下面参数为VALUE printf("after remove:\n"); remove_elem(&list, &clue, POSITION); print_list(list); #endif #if 1 int found = locate_elem(list, 22.1, compare); //定位22.1元素所在位置 if(found >= 1) fprintf(stdout, "found %f at the position %d\n", list.base[found-1], found); else fprintf(stdout, "not found.\n"); #endif sort_list(&list, compare); printf("list after sort:\n"); print_list(list); value_type array2[] = {98.1, 65.1, 4.1, 86.1, 34.1, 21.1, 86.1, 74.1, 93.1, 46.1}; seq_list list2; init_list(&list2); for(int i=0; i<ARRAY_SIZE; ++i) insert_elem(&list2, 1, array2[i]); printf("list2:\n"); print_list(list2); printf("list2 after sort:\n"); sort_list(&list2, compare); print_list(list2); seq_list new_list; //无需调用init函数初始化，因为新表在merge_list中会初始化。如果强行调用，那么会出现内存泄漏。 merge_list(&list, &list2, &new_list, compare); printf("new merge_list:\n"); print_list(new_list); free(list.base); free(list2.base); free(new_list.base); //三个释放，防止内存泄漏 return 0; }

三：测试结果

四：总结

以上就是本文的全部内容，希望对大家学习使用C语言能有所帮助。