利用C语言实现顺序表的实例操作

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

一：顺序表代码实现

#ifndef _SEQ_LIST_H
#define _SEQ_LIST_H

#include 
#include 
#include 
#include 

#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; ibase, 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_pabase+lpa->size && it_pbbase+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 

二：测试代码

为保证通用性，不用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= 1)
 fprintf(stdout, "found %f at the position %dn", 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

三：测试结果



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