乐码库:一个极速、放心、纯净的下载站! 更新: 资源发布
  • 您的位置:首页 > 技术文档 > C/C++ > 利用C语言实现顺序表的实例操作
  • 收藏本页
      利用C语言实现顺序表的实例操作
      发布时间:2016-12-21 08:02:03 关键词: 顺序表c语言实现,c语言建立顺序表,c语言顺序表的实现
      内容简介:顺序表是线性表中的一种重要的数据结构,也是最基础的数据结构,所以他不仅是学习中的重点,也是应用开发非常常用的一种数据结构。这篇文章介绍如何利用C语言实现顺序表。

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

    一:顺序表代码实现

    #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 /*seq_list*/

    二:测试代码

    为保证通用性,不用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语言能有所帮助。

      相关内容
      最新更新
      热门排行榜