数据结构(C语言)教材的伪代码(一)

失速的砖头

#include <stdio.h>
#include <stdlib.h>
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef int ElemType;
typedef struct _SqList{
ElemType* elem;//elem指向数组的首地址
        int length;//当前长度
        int listsize;//数组的大小
}SqList;

Status InitList_Sq(SqList& L){
        L.elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));
        if (!L.elem){
                printf("初始化失败.\n");
                return FALSE;
        }
        L.length = 0;

        L.listsize = LIST_INIT_SIZE;
        printf("初始化成功.\n");
        return OK;
}

Status DestroyList_Sq(SqList& L){
        //初始条件:线性表L存在
        //操作结果:销毁线性表L.
        if (!L.elem){
                printf("线性表不存在.\n");
                return FALSE;
        }
        free(L.elem);

        printf("线性表销毁成功.\n");
        return OK;
}

Status ClearList_Sq(SqList& L){
        //初始条件:线性表L存在
        //操作结果:将L重置为空表
        if (!L.elem){
                printf("线性表不存在.\n");
                return FALSE;
        }
        InitList_Sq(L);

        return OK;
}

Status ListEmpty_Sq(SqList L){
//初始条件:线性表L存在.
//操作结果:如果L是空表,返回TRUE,否则返回FALSE
        if (L.length == 0){
                printf("L是空表.\n");
                return TRUE;
        }
        else{
                printf("L不是空表.\n");
                return FALSE;
        }
}

Status ListLength_Sq(SqList L){
//初始条件:线性表L存在.
//操作结果:返回L中数据元素个数
        return L.length;
}

Status GetElem_Sq(SqList L, int i, ElemType& e){
        //初始条件:线性表已存在1 ≤ i ≤ ListLength(L).
        //操作结果:用e返回L中第i个数据元素的值
        e = L.elem[i-1];
        return OK;
}

Status compare (ElemType x, ElemType y){
        if (x == y){
                return TRUE;
        }
        else{
                return FALSE;
        }
}
Status LocateElem_Sq(SqList L, ElemType e, Status(*compare) (ElemType, ElemType)){
//线性表L存在,compare()是数据元素判定函数.返回L中第1个与e满足关系compare()的数据元素的位序.
//若这样的元素不存在,则返回0;
        int i = 1;//i的初值为第一个元素的位序
        ElemType* p = L.elem;//p的初值为第一个元素的存储位置(地址)
        while (i <= L.length && !(*compare)(*p++, e))
                ++i;
        if (i <= L.length)
                return i;
        else return FALSE;
}

int PriorElem_Sq(SqList L, ElemType cur_e, ElemType& pre_e){
//初始条件: 线性表L存在.
//操作结果: 若cur_e是L的数据元素,且不是第一个,则用pre_e返回他的前驱,否则操作失败,pre_e无定义NULL.
        int i = 1;
        i = LocateElem_Sq(L, cur_e, compare);
        if (i >1 && i <= L.length){ //符合条件
        pre_e = L.elem[i-2];//减1是当前值,再减1是前驱值
        }
        else{
                pre_e = 0;
                return FALSE;
        }
        return OK;
}


Status NextElem_Sq(SqList L, ElemType cur_e, ElemType& next_e){
//初始条件: 线性表L存在.
//操作结果: 若cur_e是L的数据元素,且不是最后一个,则用next_e返回他的后继,否则操作失败,next_e无定义NULL.
        int i = 1;
        i = LocateElem_Sq(L, cur_e, compare);
        if (i >=1 && i < L.length){ //符合条件
        next_e = L.elem;//i在数组中就是他的后继.
        }
        else{
                next_e = 0;
                return FALSE;
        }
        return OK;
}

Status ListInsert_Sq(SqList& L, int i, ElemType e){
//初始条件:线性表L存在,1 ≤ i ≤ ListLength(L)+1
//操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1
        if (i<1 || i>L.length + 1)
                return ERROR;
        if (L.length >= L.listsize){
                ElemType* newbase = (ElemType*)realloc(L.elem, (L.listsize + LISTINCREMENT)*sizeof(ElemType));

                if (!newbase)
                        exit(OVERFLOW);
                L.elem = newbase;
                L.listsize += LISTINCREMENT;
        }
        ElemType* q = &(L.elem[i - 1]);
        ElemType*p = NULL;
        for (p = &(L.elem[L.length - 1]); p >= q; --p)
                *(p + 1) = *p;

        *q = e;
        ++L.length;
        return OK;

}


Status ListDelete_Sq(SqList& L, int i, ElemType& e){
//初始条件:线性表L存在且非空,1 ≤ i ≤ ListLength(L)
//操作结果:删除L的第i个数据元素,并用e返回其值,L的长度减1
        if ((i<1) || (i > L.length))
                return ERROR;
        
        ElemType* p = NULL;
        p = &(L.elem[i - 1]);
        e = *p;
        ElemType* q = NULL;
        q = L.elem + L.length - 1;
        
        for (++p; p <= q; ++p)
                *(p - 1) = *p;
        --L.length;
        return OK;
}

ElemType& visit(ElemType& e){
//输出线性表L一个数据元素.
        return e;
}

Status ListTraverse_Sq(SqList L, ElemType& (*visit)(ElemType& e)){
//初始条件:线性表L存在
//操作结果:依次对L的每个数据元素调用函数visit().一旦visit()失败,则操作失败.
//就是遍历函数
        int i = 1;
        ElemType p;
        while (i<=L.length){
                p = visit(*(L.elem++));
                printf("%d ", p);
                i++;
        }
        printf("\n");
        return OK;
}

int main(void)
{
        SqList p;
        p.elem = NULL;
        p.length = -1;
        p.listsize = -1;
        
        InitList_Sq(p);
        DestroyList_Sq(p);
        ClearList_Sq(p);
        ListEmpty_Sq(p);
        ListLength_Sq(p);
        //插入线性表,
        int e;
        printf("在\"=\"后键入Ctrl+z表示输入结束.\n");
        while (1){
                printf("请输入第%d个元素的值=", ListLength_Sq(p)+1);
                if (scanf("%d", &e) == EOF)
                        break;
                ListInsert_Sq(p, ListLength_Sq(p) + 1, e);

        }
        ListTraverse_Sq(p, (*visit));
        printf("--------------\n");
        // 显示长度
        ListLength_Sq(p);
        printf("数据元素的个数=%d\n",ListLength_Sq(p));
        // 返回元素      
        int i = 1;//初始化i=1
        printf("要返回第几个元素的值(1 ≤ i ≤ %d) ", ListLength_Sq(p));
        scanf("%d",&i);
        GetElem_Sq(p, i, e);
        printf("e=%d\n", e);
        printf("--------------\n");
        //判定函数
        printf("请输入要查找的数=", e);
        scanf("%d", &e);
        printf("在线性表(顺序表)的第%d位\n", LocateElem_Sq(p, e, (*compare)));
        printf("--------------\n");
        //返回前驱的值
        printf("请输入要查找的数=", e);
        int pre_e1 = 0;
        scanf("%d", &e);
        PriorElem_Sq(p, e, pre_e1);
        printf("%d的前驱是=%d\n",e,pre_e1);
        printf("--------------\n");
        //返回后继的值
        printf("请输入要查找的数=", e);
        int next_e1 = 0;
        scanf("%d", &e);
        NextElem_Sq(p, e, next_e1);
        printf("%d的后继是=%d\n",e,next_e1);
        printf("--------------\n");
        // 插入函数
        printf("请输入要插入的位置(1≤i≤%d)=",ListLength_Sq(p)+1);
        scanf("%d",&i);
        printf("请输入要插入的值=");
        scanf("%d",&e);  
        ListInsert_Sq(p, i, e);
        ListTraverse_Sq(p, (*visit));
        printf("--------------\n");
        //删除函数
        printf("请输入要删除的位置(1≤i≤%d)=",ListLength_Sq(p));
        scanf("%d",&i);
        ElemType del_e;  
        ListDelete_Sq(p, i, del_e);
        ListTraverse_Sq(p, (*visit));
        printf("--------------\n");
        //再掉一次遍历函数.
        ListTraverse_Sq(p, (*visit));
        return OK;
}