照着数据结构书敲的,内含快速插入排序算法
#include <stdio.h> #include <stdlib.h> #define MaxSize 50 typedef int ElemType; typedef struct { ElemType data[MaxSize]; int length; }SqList; /* * 创建一个线性表,使用了CreateList 后就不需要使用InitList来初始化 * 线性表了 * */ void CreateList(SqList * &L,ElemType a[],int n){ int i; L = (SqList * )malloc(sizeof(SqList)); for(i=0;i<n;i++) L->data[i]=a[i]; L->length = n; } /* * 初始化一个线性表,表中的数据是空的 * */ void InitList(SqList * &L){ L = (SqList * )malloc(sizeof(SqList)); L->length = 0; } /* * 销毁线性表,释放线性表中的内存 * */ void DestoryList(SqList * &L){ free(L); } /* * 判断线性表是否为空表,如果为空则返回真TRUE * */ bool ListEmpty(SqList * L){ return(L -> length); } /* * 返回当前线性表的长度Length * */ int ListLength(SqList * L){ return (L -> length); } /* * 输出线性表,顺序显示L中个节点的值域 * */ void DispList(SqList * L){ int i; for(i=0;i<L->length;i++) printf(" %d \n",L ->data[i] ); printf("\n"); } /* * 获取线性表中某个数据的元素值,用e返回 * */ bool GetElem(SqList * L,int i,ElemType &e){ if( i<1 || i>L->length ) return false; e = L ->data[i-1]; return true; } /* * 按值查找线性表中出现的位置(序号) * */ int LocateElem(SqList * L,ElemType e){ int i=0; while(i<L->length && L->data[i]!=e) i++; if(i>=L->length) return 0; else return i+1; } /* * 插入数据元素 * */ bool ListInsert(SqList * &L,int i,ElemType e){ int j; if(i<1 || i>L->length+1) return false; i--; for(j=L->length;j>i;j--) L -> data[j] = L->data[j-1]; L->data[i] = e; L->length++; return true; } /* * 删除数据元素 * */ bool ListDelete(SqList * &L,int i,ElemType &e){ int j; if( i<1 || i>L->length) return false; i--; e = L->data[i]; for(j=i;j<L->length-1;j++) L->data[j] = L->data[j+1]; L->length--; return true; } /* * 删除所有值等于x的元素 * 书本 P35解法1 */ void delnode1(SqList * &L,ElemType x){ int k = 0,i; for(i=0;i<L->length;i++) if(L -> data[i]!=x){ L->data[k] = L->data[i]; k++; } L ->length = k; } /* * 插入排序算法 * 书本 P36解法2 */ void move2(SqList * &L){ int i = 0,j; j = L->length-1; ElemType pivot = L->data[0]; while(i<j){ while(j>i && L->data[j]>pivot) j--; L->data[i] = L->data[j]; i++; while(i<j && L->data[i]<=pivot) i++; L->data[j]=L->data[i]; j--; } L->data[i] = pivot; printf("i = %d\n", i); } int main(){ int a[] = {3,8,2,7,1,5,3,4,6,0}; SqList *L; CreateList(L,a,10);//数组a的长度为10 DispList(L); move2(L); printf("排序后:\n"); DispList(L); }
发表评论