C语言数据结构的线性表

照着数据结构书敲的，内含快速插入排序算法

#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); 



  



}