C语言数据结构的线性表

字数

586 字

阅读时间

4 分钟

更新日期

9/14/2016

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

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