插入排序
/*-----------------------------------------------------------------------------Copyright (c) 2010-2011 Zidane LiUsage of this program is free for non-commercial use.-----------------------------------------------------------------------------*//* 插入排序算法难度不大，基本思路是从第二个元素开始遍历整个表，如果当前元素小于前一个元素，插入到他的前一个元素之前，直到不小于为止。 第一次在Linux下写算法，由于只学习过C++，函数的按引用传递让我很是恼火。C语言只有按值传递，所以如果想实现按引用传递，可以使用指针（按地址传递）。而指针在传递的过程中也是按值传递，所以指针所指向的地址不会变。所以在使用指针传递之前要对指针malloc，这样才能达到预期的效果。*/#include <stdio.h>#include <stdlib.h>#define bool int#define TRUE 1#define FALSE 0#define INFEASIBLE -1#define OVERFLOW -2#define LIST_INIT_SIZE 100//初始化空间大小#define LISTINCREMENT 10//当空间不足时，为顺序表增加一个大小为LISTINCREMENT个数据元素的空间typedef int ElemType; //定义处理数据元素的类型为int//数据typedef struct{ElemType* elem;//存储空间基址int length; //当前长度int listsize; //当前分配的存储容量(以sizeof(ElemType)为单位)}Sqlist;void visit(ElemType x){printf("%d", x);}//初始化一个空的顺序表void InitList_Sq(Sqlist* L){//从基址L.elem开始分配LIST_INIT_SIZE * sizeof(ElemType)大小的空间L->elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));L->length = 0;L->listsize = LIST_INIT_SIZE;}//销毁一个顺序表void DestroyList_Sq(Sqlist* L){free(L->elem);free(L);}//将顺序表重置为空void ClearList_Sq(Sqlist* L){L->length = 0;L->listsize = LIST_INIT_SIZE;}//判断顺序表是否为空；如果为空，返回TRUE；如果不为空，返回FALSEbool ListEmpty_Sq(Sqlist L){return L.length == 0;}//返回顺序表长度int ListLength_Sq(Sqlist L){return L.length;}//获得顺序表第i个元素的值ElemType GetElem_Sq(Sqlist L, int i){return L.elem;}//在顺序表L中位置i(1 <= i <= ListLength(L) + 1)插入数据元素e，要求为非递增序列void ListInsert_Sq(Sqlist* L, int i, ElemType e){//当前存储空间已满，增加分配if (L->length >= L->listsize){ElemType* newbase = (ElemType*)realloc(L->elem, (L->listsize + LISTINCREMENT) * sizeof(ElemType));L->elem = newbase;L->listsize += LISTINCREMENT;}ElemType *p, *q;//给q赋位置i处数据元素的地址，q为顺序表末尾数据元素地址q = &L->elem;//为了方便，从最后一个数据元素开始移动for (p = &L->elem; p >= q; --p){*(p + 1) = *p;}*q = e;++L->length;}//在顺序表L中位置i(1 <= i <= ListLength(L) + 1)删除数据元素，并将删除的值存在e中void ListDelete_Sq(Sqlist* L, int i, ElemType e){ElemType *p, *q;//给q赋位置i处数据元素的地址，q为顺序表末尾数据元素地址p = &L->elem;e = *p;q = L->elem + L->length - 1;//为了方便，从删除位置i处开始移动for (++p; p <= q; ++p){*(p - 1) = *p;}--L->length;}//遍历整个顺序表void ListTraverse(Sqlist L){int i;for (i = 1; i <= ListLength_Sq(L); i++){visit(L.elem);}printf("\n");}//升序排列void InsertSort(Sqlist* L){ int j, i; for (j = 1; j < ListLength_Sq(*L); j++) { ElemType key = L->elem; //将key之前的ElemType集体向后移动一位 i = j - 1; while (i >= 0 && L->elem > key) { L->elem = L->elem; i--; } L->elem = key; }}int main(){ Sqlist* A = (Sqlist*)malloc(sizeof(Sqlist)); InitList_Sq(A); int i; ElemType temp; for (i = 1; i <= 6; i++) { scanf("%d", &temp); ListInsert_Sq(A, i, temp); } InsertSort(A); ListTraverse(*A); return 0;}
页:
[1]