新手求教顺序表和链表

#2

世界模型2011-08-08 20:41

学完了就要自己动手去实现

#3

loveshuang2011-08-08 23:43

还是自己多动手的好哦，动手多了才会熟练，有错误可以来大家一起谈论的，你要是真想找东西参考的话百度上面多得是了。

#4

QQ3469571352011-08-10 12:37

//线性表的动态分配顺序存储结构。
#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");
}

#5

QQ3469571352011-08-10 12:41

程序代码：

//线性表的单链表存储结构。
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");
}

#6

QQ3469571352011-08-10 12:43

可能用到的头文件及宏定义

程序代码：

#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等

要多思考

新手求教 顺序表和链表