《大话数据结构》读书笔记之线性表基本操作（数组实现）
/*Name: 线性表抽象数据类型（使用数组实现）
Copyright:
Author: 巧若拙
Date: 08-09-14 14:38
Description:
*/
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<math.h>
#define MAXSIZE 10
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int ElemType;
typedef int Status; //函数类型，其值是函数结果状态代码，如OK等
typedef struct{
ElemType data[MAXSIZE];//数组存储线性表元素
int length;//线性表元素个数，即线性表长度
} SqList;
Status InitList(SqList *L);//建立一个空的线性表L
Status ListEmpty(SqList L);//若线性表为空，返回TRUE，否则返回FALSE
Status ClearList(SqList *L);//将线性表清空
int ListLength(SqList L);//返回线性表L的元素个数
Status DisplayList(SqList L);//输出线性表L的所有元素
Status GetElem(SqList L, int i, ElemType *e);//将线性表L中第i个位置元素值赋给e
Status LocateElem(SqList L, ElemType e);//在线性表L中查找是否存在与给定值e相等的元素
Status ListInsert(SqList *L, int i, ElemType e);//在线性表L中的第i个位置插入新元素e
Status ListDelete(SqList *L, int i, ElemType *e);//删除线性表L中的第i个位置，并将该元素值赋给e
Status ListSort(SqList *L);//给线性表L排序
int main(void)
{
SqList a;
ElemType *p, e = 0;
int i;
InitList(&a);//建立一个空的线性表
for (i=0; i<MAXSIZE; i++)
{
ListInsert(&a, i+1, i+100);
}
DisplayList(a);
for (i=1; i<ListLength(a); i+=2)
{
ListDelete(&a, i, &e);//删除线性表L中的第i个位置，并将该元素值赋给e
}
printf("e = %d\n", e);
DisplayList(a);
i = 5;
e = 50;
if (LocateElem(a, e))//在线性表L中查找是否存在与给定值e相等的元素
{
printf("存在%d\n", e);
}
else
{
printf("不存在%d\n", e);
ListInsert(&a, i, e);
}
DisplayList(a);
ListSort(&a);//给线性表L排序
DisplayList(a);
return 0;
}
/*
函数功能：建立一个空的线性表L
初始条件：无
操作结果：初始化线性表L。操作成功返回OK，否则返回ERROR
*/
Status InitList(SqList *L)
{
L->length = 0;
return OK;
}
/*
函数功能：判断线性表是否为空
初始条件：顺序线性表L已经存在
操作结果：若线性表为空，返回TRUE，否则返回FALSE
*/
Status ListEmpty(SqList L)
{
return (L.length == 0) ? TRUE : FALSE;
}
/*
函数功能：将线性表清空
初始条件：顺序线性表L已经存在
操作结果：将线性表清空。操作成功返回OK，否则返回ERROR
*/
Status ClearList(SqList *L)
{
if (L == NULL)
{
return ERROR;
}
L->length = 0;
return OK;
}
/*
函数功能：返回线性表L的元素个数
初始条件：顺序线性表L已经存在
操作结果：返回线性表L的元素个数
*/
int ListLength(SqList L)
{
return L.length;
}
/*
函数功能：输出线性表L的所有元素
初始条件：顺序线性表L已经存在
操作结果：输出线性表L的所有元素。操作成功返回OK，否则返回ERROR
*/
Status DisplayList(SqList L)
{
int i;
if (L.length == 0)
{
printf("none!\n");
return ERROR;
}
for (i=0; i<ListLength(L); i++)
{
printf("data[%d] = %d, ", i, L.data[i]);
}
printf("\n");
return OK;
}
/*
函数功能：将线性表L中第i个位置元素值赋给e
初始条件：顺序线性表L已经存在，1 <= i <= ListLength(L)；
操作结果：将线性表L中第i个位置元素值赋给e。操作成功返回OK，否则返回ERROR
*/
Status GetElem(SqList L, int i, ElemType *e)
{
if (L.length == 0 || i < 1 || i > L.length)
{
return ERROR;
}
*e = L.data[i-1];
return OK;
}
/*
函数功能：在线性表L中查找是否存在与给定值e相等的元素
初始条件：顺序线性表L已经存在
操作结果：在线性表L中查找是否存在与给定值e相等的元素。找到返回TRUE，否则返回FALSE
*/
Status LocateElem(SqList L, ElemType e)
{
int i;
for (i=0; i<L.length; i++)
{
if (L.data[i] == e)
{
return TRUE;
}
}
return FALSE;
}
/*
函数功能：在线性表L中的第i个位置插入新元素e
初始条件：顺序线性表L已经存在，1 <= i <= ListLength(L)；
操作结果：在线性表L中的第i个位置插入新元素e，L的长度加1。操作成功返回OK，否则返回ERROR
*/
Status ListInsert(SqList *L, int i, ElemType e)
{
int k;
if (L->length == MAXSIZE || i < 1 || i > L->length+1)
{
return ERROR;
}
for (k=L->length; k>=i; k--)
{
L->data[k] = L->data[k-1];
}
L->data[k] = e;
L->length++;
return OK;
}
/*
函数功能：删除线性表L中的第i个位置，并将该元素值赋给e
初始条件：顺序线性表L已经存在，1 <= i <= ListLength(L)；
操作结果：删除线性表L中的第i个位置，并将该元素值赋给e，L的长度减1。
操作成功返回OK，否则返回ERROR
*/
Status ListDelete(SqList *L, int i, ElemType *e)
{
int k;
if (L->length == 0 || i < 1 || i > L->length)
{
return ERROR;
}
*e = L->data[i-1];
for (k=i; k<L->length; k++)
{
L->data[k-1] = L->data[k];
}
L->length--;
return OK;
}
/*
函数功能：给线性表L排序
初始条件：顺序线性表L已经存在
操作结果：使线性表L元素按非递减排列。操作成功返回OK，否则返回ERROR
*/
Status ListSort(SqList *L) //基本插入排序
{
int i, j;
ElemType temp;
if (L->length == 0)
{
return ERROR;
}
for (i=1; i<L->length; i++)
{
temp = L->data[i];
for (j=i;(j>0) && (L->data[j-1]>temp); j--)
{
L->data[j] = L->data[j-1];
}
L->data[j] = temp;
}
return OK;
}
