應用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說話能有所贊助。