数据结构c语言版 顺序表部分代码

严蔚敏教授的书，里面用了好多所谓的伪代码，个人不喜欢。好不容易把它们都翻译过来，弄得c不像c，c++不像c++的！就全当时复习数据结构了！

使用的是dc++编译器！tc2.0应该不行，因为用到了很多c++的东西~！

我觉得需要注意的就是那个指向函数的指针最函数参数的问题：

定义和声明的时候用的格式是（函数类型 *）函数名（形参表）

调用的时候什么都不用，直接用函数名

用指针指向的函数的参数应该放在调用它的函数的参数里，

这么说总觉得说不清，自己体会一下就好了！

定义顺序表的代码：

cpp 代码

/*
  数据结构（严教版）
  第二章 线性表
  顺序表部分代码
  作者：thebigforest
  时间：2007年1月4日 21点
*/
//很多书上都有注释，我就不多写了
//按照书上定义的顺序写的，好像有点混乱
#define LIST_INIT_SIZE 10
#define LISTINCREMENT 2

typedef struct{
    int *elem;
    int lenght;
    int listsize;
}SqList;

void InitList(SqList &L){
    L.elem=(int *)malloc(LIST_INIT_SIZE*sizeof(int));
    if(!L.elem)
        exit(1);
    L.lenght=0;
    L.listsize=LIST_INIT_SIZE;
}//算法2.3
void DestroyuList(SqList &L){
    free(L.elem);
    L.elem=NULL;
    L.lenght=0;
    L.listsize=0;
}
void ClearList(SqList &L){
    L.lenght=0;
}
int ListEmpty(SqList L){
    if(L.lenght==0)
        return 1;
    else
        return 0;
}
int ListLength(SqList L){
    return(L.lenght);
}
int GetElem(SqList L,int i,int &e){
    if(i<1||i>L.lenght)
        return 0;
    else
        e=*(L.elem+i-1);
        return 1;
}
int LocateElem(SqList L,int e,int (*compare)(int,int)){
    int i=1;
    int *p;
    p=L.elem;
    while(i<=L.lenght&&!compare(*p++,e))
    i++;
    if(i<=L.lenght)
        return i;
    else
        return 0;
}//算法2.6
int PriorElem(SqList L,int cur_e,int &pre_e){
    int i=2;
    int *p=L.elem+1;
    while(*p!=cur_e&&i<=L.lenght){
        i++;
        p++;
        }
    if(i<=L.lenght){
         pre_e=*--p;
         return 1;
      }
    else
        return 0;
}
int NextElem(SqList L,int cur_e,int &next_e){
    int i=1;
    int *p=L.elem;
    while(i
        p++;
        i++;
    }
    if(i
        next_e=*++p;
        return 1;
     }
    else
        return 0;
}
int ListInsert(SqList &L,int i,int e){
    int *newbase,*p,*q;
    if(i<1||i>L.lenght+1)
        return 3;
    if(L.lenght>=L.listsize){//检测空间是否够
        if(!(newbase=(int *)realloc(L.elem,(LISTINCREMENT+L.listsize)*sizeof(int))))
            return 0;
        L.elem=newbase;
        L.listsize+=LISTINCREMENT;
    }
        p=L.elem+i-1;
        for(q=L.elem+L.lenght-1;q>=p;q--)
            *(q+1)=*q;
        *p=e;
        L.lenght++;
        return 1;
 }//算法2.4
int ListDelete(SqList &L,int i,int &e){
    if(i<1||i>L.lenght)
        return 0;
    int *p,*q;
    p=L.elem+i-1;//书上是&(L.elem[i-1])
    e=*p;
    q=L.elem+L.lenght-1;
    for(;p//一个一个往前挪
        *p=*(p+1);
    }
    L.lenght--;
    return 1;
}//算法2.5 书上的*(p-1)=*p 我觉得像我这么写少一步似乎效率稍高一点！
void ListTraverse(SqList L,void(*visit)(int)){
    int i=1;
    int *p=L.elem;
    while(i<=L.lenght){
        i++;
        visit(*p++);
        }
}
int equal(int x,int y)
{
    if(x==y)
        return 1;
    else
            return 0;
}//给算法2.1作辅助
void unit(SqList &La,SqList Lb){
    int i,b,La_len;
    La_len=La.lenght;
    for(i=1;i<=Lb.lenght;i++){
        GetElem(Lb,i,b);
        if(!(LocateElem(La,b,equal)))
            ListInsert(La,++La_len,b);
    }
}//算法2.1
void unit_sq(SqList &La,SqList Lb){
    int *pa,*pb,i,j;
    for(i=1;i<=Lb.lenght;i++){
        pb=Lb.elem+i-1;
        for(j=1;j<=La.lenght;j++){
            pa=La.elem+j-1;
            if(*pa==*pb)break;
        }
        if(j>=La.lenght)
            *(pa++)=*pb;
    }
}//本来想用指针直接赋值，改良一下算法2.1,但是看来不行
void MergeList(SqList La,SqList Lb,SqList &Lc){
    InitList(Lc);
    int i=1,j=1,ai,bi,k=0;
    while(i<=La.lenght&&j<=Lb.lenght){
        GetElem(La,i,ai);
        GetElem(Lb,j,bi);
        if(ai>=bi)
            ListInsert(Lc,++k,ai);
        else
            ListInsert(Lc,++k,bi);
    }
    while(i<=La.lenght){
        GetElem(La,i,ai);
        ListInsert(Lc,++k,ai);
    }
    while(j<=Lb.lenght){
        GetElem(Lb,j,bi);
        ListInsert(Lc,++k,bi);
    }
}//算法2.2
void MergeList_sq(SqList La,SqList Lb,SqList &Lc){
    InitList(Lc);
    Lc.lenght=Lb.lenght+La.lenght;
    Lc.listsize=La.listsize+Lb.listsize;
    Lc.elem=(int *)malloc(Lc.listsize*sizeof(int));
    int *pa,*pb,*pa_end,*pb_end,*pc;
    pa=La.elem;
    pb=Lb.elem;
    pa_end=La.elem+La.lenght-1;
    pb_end=Lb.elem+Lb.lenght-1;
    pc=Lc.elem;
    while(pa<=pa_end&&pb<=pb_end){
        if(*pa>=*pb)
            *pc++=*pb++;
        else
            *pc++=*pb++;
    }
    while(pa<=pa_end){
        *pc++=*pa++;
    }
    while(pb<=pb_end){
        *pc++=*pb++;
    }
}//算法2.7

验证部分的代码：main.cpp

cpp 代码

#include<maloc.h></maloc.h>
    #include<stdio.h></stdio.h>
    #include<stdlib.h></stdlib.h><stdlib.h></stdlib.h>

#include"2.1 Linear_list.h"

void print1(int x){//打印函数
    printf(".....print1.....\n");
    printf("%d  \n",x);
    printf("......End.......\n");
}
int compare(int x,int y){//比较函数，第一个比第二个大就OK
    printf("...compare...\n");
    if(x>y)
        return 1;
    else
        return 0;
}
int main(void){
    SqList L;
    int i,c;
    printf("现在开始操作每一个函数\n");
    printf("创建一个顺序表：使用InitList\n");
    InitList(L);
    printf("创建成功! \n");
    printf("使用ListInsert 依次插入数值11 22 33 44 77\n");
    ListInsert(L,1,11);
    ListInsert(L,2,22);
    ListInsert(L,3,33);
    ListInsert(L,4,44);
    ListInsert(L,5,77);
    printf("插入成功，用ListTraverse + print1显示\n");
    ListTraverse(L,print1);
    printf("使用ListDelete函数删除第3个元素\n");
    ListDelete(L,3,c);
    printf("删除了 %d\n",c);
    printf("删除成功，用ListTraverse + print1显示\n");
    ListTraverse(L,print1);
    printf("接下来我们获取第3个元素的数值，使用GetElem\n");
    GetElem(L,3,c);
    printf("第三个数值是 %d\n",c);
    printf("用PriorElem获得它的前驱\n");
    PriorElem(L,c,c);
    printf("前驱是：%d\n",c);
    printf("用NextElem获取那个前驱的后继\n");
    NextElem(L,c,c);
    printf("前驱是 %d\n",c);
    printf("使用LocateElem+commpare找出第一个比55大的序号\n");
    c=LocateElem(L,55,compare);
    printf("是第 %d 个！\n",c);
    printf("最后清空L，用ClearList\n");
    ClearList(L);
    printf("使用ListEmpty检验是否位空\n");
    if(ListEmpty(L))
        printf("为空\n");
    else
        printf("不为空\n");
    printf("销毁表,使用DestroyuList\n");
    DestroyuList(L);
    printf("彻底OK");
    getchar();
    return 1;
}