/****************************************************************************************************
*使用编译器：C-FREE
*实现数据结构中的顺序表
*编写人：徐文才（才哥）
*****************************************************************************************************/
/**顺序表结构和工具函数实现*/
#include<stdio.h>
#include<ctype.h>/**定义初始容量*/
#define MEMORY_CAPACITY 100
/**设置递增空间*/
#define MEMORY_INCREASE 10/**内存是否申请成功*/#define MEMORY_ALLOCAT_SUCCESS 1#define MEMORY_ALLOCAT_FAILURE 0/**顺序表是否为空#define LIST_IS_EMPTY 1;#define LIST_NO_EMPTY 0;/**定义TRUE和FALUSE*/#define TRUE 1;#define FALSE 0;#define NOT_EXIT -1;
/**定义顺序表的结构*/
struct LinearList{
int *elem; // 申请空间指针，类似于指针数组 int length;//表示所含有元素的个数 int size; //申请的元素内存的容量}; /**定义类型，注意c语言中不存在引用&*/ typedef struct LinearList linearList;
/************************************************************************
*初始化说明:malloc申请内存，并初始化长度（length==0）
*指针的容量为MEMORY_CAPACITY,返回成功
************************************************************************/
/**顺序链表初始化*/int InitList(linearList *linear){ //分配内存 linear->elem = (int*)malloc(MEMORY_CAPACITY * sizeof(int)); if(!linear->elem) return MEMORY_ALLOCAT_FAILURE; linear->length = 0; linear->size = MEMORY_CAPACITY;//设置初始容量 return MEMORY_ALLOCAT_SUCCESS;}
/*************************************************************************
*判断链表是否为空
*根据线性表的定义，若长度length == 0则说明线性表为空
**************************************************************************/
int IsEmpty(linearList *linear){ if(linear->length != 0){ return FALSE; } return TRUE;}
/**************************************************************************
*数据查找：使用二分法，时间复杂度，和空间复杂度比较小*如果存在返回位置(index）
*************************************************************************/int LocateElem(linearList *linear,int low,int high,int number){ int mid = (high + low)/2; int location = 0; if(linear->elem[mid] > number){ return LocateElem(linear,mid + 1,high,number); }else if(linear->elem[mid] < number){ return LocateElem(linear,low,mid - 1,number); }else if(linear->elem[mid] = number){ location = mid; return location; } return NOT_EXIT;}
/**********************************************************************
*判断直接前驱和直接后继：仅仅需要判断是不是首数据
*判断等于末尾数据
**********************************************************************/
int IsNextElem(linearList *linear,int index){
if(index==linear->length)
return FALSE;
return TRUE;
}
int IsPriorElem(linearList *linear,int index){
if(index-1==0)
return FALSE;
return TRUE;
}
/********************************************************************
*查看数据链表中的元素个数
* 只需要返回线性顺序结构中的length
*********************************************************************/
int NumOfElem(linearList *linear){
return linear->length; } /********************************************************************* *获取索引为i位置的值 * 通过索引值获取，下标获取元素 *********************************************************************/int getElem(linearList *linear,int index){ if(index < 1 || index > linear->length) { return FALSE; } return linear->elem[index - 1];}/*****************************************************************************
*插入数据*参数:顺序表，索要插入的位置，索要插入的数据
*步骤分析:1.判断位置是否合法 2.判断数据是否超出容量
*若超出则修改内存 3.数据向后移动（n-i+1）次，*(p+1) = *p
*4.进行数据的赋值,以及长度的++。
*渐进时间复杂度:O(n)
****************************************************************************/ int ListInsert(linearList *linear,int index,int number){ if(index < 1 || index > (linear->size)+1){ return FALSE; } linearList *newbase; if(index > linear->size){ newbase = (int*)realloc((MEMORY_CAPACITY + MEMORY_INCREASE)*sizeof(int)); linear->elem = newbase; free(newbase); newbase = NULL; } linearList *p = NULL; newbase = &linear->elem[index - 1]; for(p = &linear->elem[linear->length-1];p < newbase;p++){ *(p+1) = *p; } linear->elem[index - 1] = number; linear->length++; linear->size = MEMORY_CAPACITY + MEMORY_INCREASE; return TRUE; }
/*****************************************************************************
*删除数据*参数:顺序表，索要插入的位置，索要插入的数据
*步骤分析:1.判断位置是否合法
* 2.数据向后移动（n-i）次，*(p-1)=*p
* 3.长度的--。
*渐进时间复杂度:O(n)
****************************************************************************/ int ListDelete(linearList *linear,int index){ if(index < 1 || index > linear->length){ return FALSE; } int *startBase = &linear->elem[index - 1]; int *p = NULL; for(p = startBase + 1;p<&(linear->elem[linear->length]);p++){ *(p - 1) = *p; } linear->length --; return TRUE; }
/***********************************************************
*遍历list,并输出元素,
***********************************************************/
void ListTraverse(linearList *linear){
int i = 0; for(i = 0;i<linear->length;i++){ printf("%d ",linear->elem[i]); }}/**************************************************************
*数据链表的合并
* 返回一个线性列表 (利用归并的方法)
**************************************************************/
linearList * MergeList(linearList *list1,linearList *list2){
int list3_len = list1->length + list2->length; linearList *list3; list3->elem = (int *)malloc(list3_len * sizeof(int)); if(!list3->elem){ exit(-1); } int i,k,j = 0; while(i < list1->length && j < list2->length){ if(list1->elem[i] <= list2->elem[j]){ list3->elem[k++] = list1->elem[i++]; } else { list3->elem[k++] = list1->elem[j++]; } } while(i < list1->length){ list3->elem[k++] = list1->elem[i++]; } while(j < list2->length){ list3->elem[k++] = list1->elem[j++]; } return list3;}
/******************************************************************
*顺序表的销毁：直接进行释放
*******************************************************************/
void DestroyList(linearList *linear){ free(linear); linear = NULL; printf("LIST DELETE SUCCESS!\n");}
int main(){
}