新手求教顺序表和链表 - 数据结构与算法

得分:7

//线性表的动态分配顺序存储结构。
#define LIST_INIT_SIZE 10 //线性表存储空间的初始分配量
#define LIST_INCREMENT 2 //线性表存储空间的分配增量
struct SqList
{
    ElemType *elem; //存储空间基址
    int length; //当前长度
    int listsize; //当前分配的存储容量(以sizeof(ElemType)为单位)
};

//顺序存储的线性表的基本操作(12个)
void InitList(SqList &L)
{    //操作结果：构造一个空的顺序线性表L
    L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
    if(!L.elem) //存储分配失败
        exit(OVERFLOW);
    L.length=0; //空表长度为0
    L.listsize=LIST_INIT_SIZE; //初始存储容量
}

void DestroyList(SqList &L)
{    //初始条件：顺序线性表L已存在。操作结果：销毁顺序线性表L
    free(L.elem); //释放L.elem所指的存储空间
    L.elem=NULL; //L.elem不再指向任何存储单元
    L.length=0;
    L.listsize=0;
}

void ClearList(SqList &L)
{    //初始条件：顺序线性表L已存在。操作结果：将L重置为空表
    L.length=0;
}

Status ListEmpty(SqList L)
{    //初始条件：顺序线性表L已存在。
    //操作结果：若L为空表，则返回TRUE；否则返回FALSE
    if(L.length==0)
        return TRUE;
    else
        return FALSE;
}

int ListLength(SqList L)
{    //初始条件：顺序线性表L已存在。操作结果：返回L中数据元素的个数
    return L.length;
}

Status GetElem(SqList L,int i,ElemType &e)
{    //初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
    //操作结果：用e返回L中第i个数据元素的值
    if(i<1||i>L.length) //i不在表L的范围之内
        return ERROR;
    e=*(L.elem+i-1); //将表L的第i个元素的值赋给e
    return OK;
}

int LocateElem(SqList L,ElemType e,Status(*compare)(ElemType,ElemType))
{    //初始条件：顺序线性表L已存在，compare()是数据元素判定函数(满足为1，否则为0)
    //操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。
    //若这样的数据元素不存在，则返回值为0。
    int i=1; //i的初值为第1个元素的位序
    ElemType *p=L.elem; //p的初值为第1个元素的存储位置
    while(i<=L.length&&!compare(*p++,e)) //i未超出表的范围且未找到满足关系的数据元素
        ++i; //继续向后找
    if(i<=L.length) //找到满足关系的数据元素
        return i; //返回其位序
    else //未找到满足关系的数据元素
        return 0;
}

Status PriorElem(SqList L,ElemType cur_e,ElemType &pre_e)
{    //初始条件：顺序线性表L已存在
    //操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱；
    //否则操作失败，pre_e无定义
    int i=2; //从第2个元素开始
    ElemType *p=L.elem+1; //p指向第2个元素
    while(i<=L.length&&*p!=cur_e) //i未超出表的范围且未找到值为cur_e的元素
    {
        p++; //p指向下一个元素
        i++; //计数加1
    }
    if(i>L.length) //到表结束处还未找到值为cur_e的元素
        return ERROR; //操作失败
    else //找到值为cur_e的元素，并由p指向其
    {
        pre_e=*--p; //p指向前一个元素(cur_e的前驱)，将所指元素的值赋给pre_e
        return OK; //操作成功
    }
}

Status NextElem(SqList L,ElemType cur_e,ElemType &next_e)
{    //初始条件：顺序线性表L已存在
    //操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，
    //否则操作失败，next_e无定义
    int i=1; //从第1个元素开始
    ElemType *p=L.elem; //p指向第1个元素
    while(i<L.length&&*p!=cur_e) //i未到表尾且未找到值为cur_e的元素
    {
        p++; //p指向下一个元素
        i++; //计数加1
    }
    if(i==L.length) //到表尾的前一个元素还未找到值为cur_e的元素
        return ERROR; //操作失败
    else //找到值为cur_e的元素，并由p指向其
    {
        next_e=*++p; //p指向下一个元素(cur_e的后继)，将所指元素的值赋给next _e
        return OK; //操作成功
    }
}

Status ListInsert(SqList &L,int i,ElemType e)
{    //初始条件：顺序线性表L已存在，1≤i≤ListLength(L)+1
    //操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
    ElemType *newbase,*q,*p;
    if(i<1||i>L.length+1) //i值不合法
        return ERROR;
    if(L.length==L.listsize) //当前存储空间已满，增加分配，修改
    {
        newbase=(ElemType*)realloc(L.elem,(L.listsize+LIST_INCREMENT)*sizeof(ElemType));
        if(!newbase) //存储分配失败
            exit(OVERFLOW);
        L.elem=newbase; //新基址赋给L.elem
        L.listsize+=LIST_INCREMENT; //增加存储容量
    }
    q=L.elem+i-1; //q为插入位置
    for(p=L.elem+L.length-1;p>=q;--p) //插入位置及之后的元素右移(由表尾元素开始移)
        *(p+1)=*p;
    *q=e; //插入e
    ++L.length; //表长增1
    return OK;
}

Status ListDelete(SqList &L,int i,ElemType &e)
{    //初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
    //操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1
    ElemType *p,*q;
    if(i<1||i>L.length) //i值不合法
        return ERROR;
    p=L.elem+i-1; //p为被删除元素的位置
    e=*p; //被删除元素的值赋给e
    q=L.elem+L.length-1; //q为表尾元素的位置
    for(++p;p<=q;++p) //被删除元素之后的元素左移(由被删除元素的后继元素开始移)
        *(p-1)=*p;
    L.length--; //表长减1
    return OK;
}

void ListTraverse(SqList L,void(*visit)(ElemType&))
{    //初始条件：顺序线性表L已存在
    //操作结果：依次对L的每个数据元素调用函数visit()
    //visit()的形参加'&'，表明可通过调用visit()改变元素的值
    ElemType *p=L.elem; //p指向第1个元素
    int i;
    for(i=1;i<=L.length;i++) //从表L的第1个元素到最后1个元素
        visit(*p++); //对每个数据元素调用visit()
    printf("\n");
}

A real warrior never quits.

//线性表的单链表存储结构。 struct LNode { ElemType data; LNode *next; }; typedef LNode *LinkList; //另一种定义LinkList的方法 //带有头结点的单链表的基本操作(12个)， void InitList(LinkList &L) { //操作结果：构造一个空的线性表L L=(LinkList)malloc(sizeof(LNode)); //产生头结点，并使L指向此头结点 if(!L) //存储分配失败 exit(OVERFLOW); L->next=NULL; //头结点的指针域为空 } void DestroyList(LinkList &L) { //初始条件：线性表L已存在。操作结果：销毁线性表L LinkList q; while(L) //L指向结点(非空) { q=L->next; //q指向首元结点 free(L); //释放头结点 L=q; //L指向原首元结点，现头结点 } } void ClearList(LinkList L) //不改变L { //初始条件：线性表L已存在。操作结果：将L重置为空表 LinkList p=L->next; //p指向第1个结点 L->next=NULL; //头结点指针域为空 DestroyList(p); //销毁p所指的单链表 } Status ListEmpty(LinkList L) { //初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE if(L->next) //非空 return FALSE; else return TRUE; } int ListLength(LinkList L) { //初始条件：线性表L已存在。操作结果：返回L中数据元素的个数 int i=0; //计数器初值为0 LinkList p=L->next; //p指向第1个结点 while(p) //未到表尾 { i++; //计数器+1 p=p->next; //p指向下一个结点 } return i; } Status GetElem(LinkList L,int i,ElemType &e) { //L为带头结点的单链表的头指针。当第i个元素存在时，其值赋给e并返回OK；否则返回ERROR int j=1; //计数器初值为1 LinkList p=L->next; //p指向第1个结点 while(p&&j<i) //顺指针向后查找，直到p指向第i个结点或p为空(第i个结点不存在) { j++; //计数器+1 p=p->next; //p指向下一个结点 } if(!p||j>i) //第i个结点不存在 return ERROR; e=p->data; //取第i个元素的值赋给e return OK; } int LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType)) { //初始条件：线性表L已存在，compare()是数据元素判定函数(满足为1，否则为0) //操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。 //若这样的数据元素不存在，则返回值为0 int i=0; //计数器初值为0 LinkList p=L->next; //p指向第1个结点 while(p) //未到表尾 { i++; //计数器+1 if(compare(p->data,e)) //找到这样的数据元素 return i; //返回其位序 p=p->next; //p指向下一个结点 } return 0; //满足关系的数据元素不存在 } Status PriorElem(LinkList L,ElemType cur_e,ElemType &pre_e) { //初始条件：线性表L已存在 //操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，返回OK， //否则操作失败，pre_e无定义，返回ERROR LinkList q,p=L->next; //p指向第1个结点 while(p->next) //p所指结点有后继 { q=p->next; //q指向p的后继 if(q->data==cur_e) //p的后继为cur_e { pre_e=p->data; //将p所指元素的值赋给pre_e return OK; //成功返回OK } p=q; //p的后继不为cur_e，p向后移 } return ERROR; //操作失败，返回ERROR } Status NextElem(LinkList L,ElemType cur_e,ElemType &next_e) { //初始条件：线性表L已存在 //操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，返回OK， //否则操作失败，next_e无定义，返回ERROR LinkList p=L->next; //p指向第1个结点 while(p->next) //p所指结点有后继 { if(p->data==cur_e) //p所指结点的值为cur_e { next_e=p->next->data; //将p所指结点的后继结点的值赋给next_e return OK; //成功返回OK } p=p->next; //p指向下一个结点 } return ERROR; //操作失败，返回ERROR } Status ListInsert(LinkList L,int i,ElemType e) { //在带头结点的单链线性表L中第i个位置之前插入元素e int j=0; //计数器初值为0 LinkList s,p=L; //p指向头结点 while(p&&j<i-1) //寻找第i-1个结点 { j++; //计数器+1 p=p->next; //p指向下一个结点 } if(!p||j>i-1) //i小于1或者大于表长 return ERROR; //插入失败 s=(LinkList)malloc(sizeof(LNode)); //生成新结点，以下将其插入L中 s->data=e; //将e赋给新结点 s->next=p->next; //新结点指向原第i个结点 p->next=s; //原第i-1个结点指向新结点 return OK; //插入成功 } Status ListDelete(LinkList L,int i,ElemType &e) { //在带头结点的单链线性表L中，删除第i个元素，并由e返回其值 int j=0; //计数器初值为0 LinkList q,p=L; // p指向头结点 while(p->next&&j<i-1) //寻找第i个结点，并令p指向其前驱 { j++; //计数器+1 p=p->next; //p指向下一个结点 } if(!p->next||j>i-1) //删除位置不合理 return ERROR; //删除失败 q=p->next; //q指向待删除结点 p->next=q->next; //待删结点的前驱指向待删结点的后继 e=q->data; //将待删结点的值赋给e free(q); //释放待删结点 return OK; //删除成功 } void ListTraverse(LinkList L,void(*visit)(ElemType)) //visit的形参类型为ElemType { //初始条件：线性表L已存在。操作结果：依次对L的每个数据元素调用函数visit() LinkList p=L->next; // p指向第1个结点 while(p) //p所指结点存在 { visit(p->data); //对p所指结点调用函数visit() p=p->next; //p指向下一个结点 } printf("\n"); }

#include<string.h> //字符串函数头文件 #include<ctype.h> //字符函数头文件 #include<malloc.h> //malloc()等 #include<limits.h> // INT_MAX等 #include<stdio.h> //标准输入输出头文件，包括EOF(=^Z或F6)，NULL等 #include<stdlib.h> //atoi()，exit() #include<io.h> //eof() #include<math.h> //数学函数头文件，包括floor()，ceil()，abs()等 #include<sys/timeb.h> //ftime() #include<stdarg.h> //提供宏va_start，va_arg和va_end，用于存取变长参数表 //函数结果状态代码。 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 //#define INFEASIBLE -1 没使用 //#define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3，故去掉此行 typedef int Status; //Status是函数的类型，其值是函数结果状态代码，如OK等