当前位置：首页 -> 基础 -> c++编程基础

数据结构--线性表顺序存储(一)

2014-11-24 02:27:47 · 作者: · 浏览: 2
标签: 数据结构 线性 顺序 存储
之前对 数据结构 的学习，多注重思想，小于实践。发现实现过程中，其实存在着不少问题。打算在这一阶段的学习过程中，总结些实现过程的知识，方便日后再学习。
知识点： 指针传递 和 函数指针
指针传递：当数据量较大时（如 类或者结构体），函数在传递参数时 通常传递 指针
函数定义时，可以直接操作 形参，也可以定义变量 接受形参之后在 操作
Status ListTraverse(SqList *L)
{
SqList *list_point = L; //内部定义 一变量，接受 形参后再操作
....
}
int MergeList_sq(SqList *DesList, SqList *list_a, SqList *list_b)
{
DesList->length = list_a->length + list_b->length; //直接操作形参值，
....
}
函数指针
声明/定义： int LocateElem(SqList *L, ElemType e, Status (*cmp)(ElemType, ElemType));
调用: LocateElem(&La, 3, compare); //compare只要与 Status cmp(int, int ) 格式相同即可
可以
typedef Status (*FunType)(ElemType, ElemType); // 用 FunType 代表指向 符合 Status xxx(int, int ) 格式函数的函数指针
声明/定义： int LocateElem(SqList *L, ElemType e, FunType);
调用: LocateElem(&La, 3, compare); //compare只要与 Status cmp(int, int ) 格式相同即可 
//顺序存储链表的实现  
#include   
#include   
   
#define ElemType int  
#define LIST_INCREMENT 10  
#define LIST_INIT_SIZE 20  
#define Status int  
#define Position int  
#define OK 1  
#define TRUE 1  
#define FALSE 0  
#define ERROR 0  
   
typedef struct{  
ElemType *base; //链表首地址  
int length;  
int listsize;  
}SqList;  
   
typedef Status (*FunType)(ElemType, ElemType);  
Status compare(ElemType, ElemType); //  小于等于1时返回 1   否则为 0  
Status GetElem(SqList *L, Position i, ElemType *e);//取 位置i的元素  
Status InitList_sq(SqList *L);  
Status InsertList_sq(SqList *L, int i, ElemType e);//在第i位置 即base[i-1] 前插入e  
Status ListTraverse(SqList *L); //遍历列表  
//int LocateElem(SqList *L, ElemType e, FunType cmp);//使L种元素与e满足  函数指令的位置，可以更改指向的函数  
int LocateElem(SqList *L, ElemType e, Status (*cmp)(ElemType, ElemType));  
   
int MergeList_sq(SqList *DesList, SqList *list_a, SqList *list_b);  
   
int main()  
{  
    SqList list_sqA;  
    SqList list_sqB;  
    SqList list_sqC;  
    int i;  
    InitList_sq(&list_sqA);  
    for (i = 1; i <= 9; i++)  
    {  
        InsertList_sq(&list_sqA, i, i);  
        //printf("insert success\n");  
    }  
    ListTraverse(&list_sqA);  
    //i = LocateElem(&list_sqA, 4, compare);//第一个小于4的下标  （位置-1）  
    //printf("%d", i);  
   
    InitList_sq(&list_sqB);  
    for (i = 1; i <= 20; i++)  
    {  
        InsertList_sq(&list_sqB, i, i*2);     
    }  
    ListTraverse(&list_sqB);  
   
    InitList_sq(&list_sqC);  
    MergeList_sq(&list_sqC, &list_sqA, &list_sqB);  
   
    ListTraverse(&list_sqC);  
    return 0;  
}  
   
   
Status InitList_sq(SqList *L)  
{  
    SqList *List = L;  
    if(NULL == (List->






base = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType))))  
        return FALSE;  
   
    List->listsize = LIST_INIT_SIZE;  
    List->length = 0;  
   
    return OK;  
}  
//int LocateElem(SqList *L, ElemType e, FunType cmp);  
int LocateElem(SqList *L, ElemType e, Status (*cmp)(ElemType, ElemType))//第一个小于e的数的位置  
{  
    int i = 0;  
    SqList *List = L;  
    for (i = 0; i < List->length; i++)  
    {  
        if (cmp(e, List->base[i]))  
        {  
            return i;  
        }  
    }  
    return 0;  
}  
   
Status compare(ElemType a, ElemType b)  
{  
    if ( a <= b)  
        return 1;  
    else  
        return 0;  
}  
   
Status InsertList_sq(SqList *L, int i, ElemType e)//第i位置 之前   1<= i <= length+1  
{  
    SqList *List = L;  
    int k = 0;  
    if ((i < 1)||(i > List->length+1))//边界检测  
    {  
        return ERROR;  
    }  
    if (List->length == List->listsize) //空间检测   
    {  
        List->base = (ElemType*)realloc(List->base, (List->length + LIST_INCREMENT)*sizeof(ElemType));  
    }  
   
    for(k = List->length; k >= i; k--) //k初始话为 第length+1位置的数组下标 length,直到第i位置对应下标i-1  
        List->base[k] = List->base[k-1];  
    List->base[i-1] = e;//k = i -1 ;用i-1不用k，可包括 i在length+1位置插入  
   
    List->length++;//更改长度  
   
    return OK;  
}  
   
Status ListTraverse(SqList *L)  
{  
    SqList *list_point = L;  
    int i;  
    for (i = 1; i <= list_point->length; i++)  
    {  
        printf("%d ",list_point->base[i-1]);  
    }  
    printf("\n");  
   
    return OK;  
}  
   
Status GetElem(SqList *L, Position a, ElemType *e)  
{  
    int i = 0;  
    if ((a < 1)||(a > L->length))  
    {  
        return ERROR;  
    }  
    *e = L->base[a-1];  
   
    return OK;  
}  
   
int MergeList_sq(SqList *DesList, SqList *list_a, SqList *list_b)  
{  
    ElemType *Pa_end = list_a->base + list_a->length - 1;  
    ElemType *Pb_end = list_b->base + list_b->length - 1;  
    ElemType *Pa = list_a->base;  
    ElemType *Pb = list_b->base;  
    ElemType *P_l