当前位置:Gxlcms > mysql > 数据结构表

数据结构表

时间:2021-07-01 10:21:17 帮助过:45人阅读

数据结构——表 1、定义: 线性表是一个线性结构,它是一个含有n≥0个结点的有限序列,对于其中的结点,有且仅有一个开始结点没有前驱但有一个后继结点,有且仅有一个终端结点没有后继但有一个前驱结点,其它的结点都有且仅有一个前驱和一个后继结点。 2、特

数据结构——表

1、定义:
线性表是一个线性结构,它是一个含有n≥0个结点的有限序列,对于其中的结点,有且仅有一个开始结点没有前驱但有一个后继结点,有且仅有一个终端结点没有后继但有一个前驱结点,其它的结点都有且仅有一个前驱和一个后继结点。
2、特征/性质
1)集合中必存在唯一的一个第一个元素
2)集合中必存在唯一的一个最后元素
3)除最后一个元素之外,均有唯一的后继
4)除第一个元素之外,均有唯一的前驱
3、线性表的基本操作
1)初始化线性表InitList(L)
2)销毁线性表DestoryList(L)
3)清空线性表ClearList(L)
4)求线性表的长度ListLength(L)
5)判断线性表是否为空IsEmpty(L)
6)获取线性表L中的某个数据元素内容GetElem(L,i,e)
7)检索值为e的数据元素LocateElem(L,e)
8)返回线性表L中e的直接前驱元素PriorElem(L,e)
9)返回线性表L中e的直接后继元素NextElem(L,e)
10)在线性表L中插入一个数据元素ListInsert(L,i,e)
11)删除线性表L中第i个数据元素ListDelete(L,i,e)
4、线性表的顺序表示:ArrayList
一般使用数组来描述 注意:数组中第i-1的单元存储着线性表中第i个数据元素的内容,换句话说,C语言中数组的下标从“0”开始,如果L是顺序表,则表中第i个数据元素是L.elem[i-1].
优点:在于随机访问元素 缺点:插入和删除的时候,需要移动大量的元素
补充:线性表复杂操作
1、求线性表的并集

思路:扩大线性表LA,将存在于线性表LB中不存在线性表LA中的数据元素插入到线性表LA中去,只需要从线性表LB中依次去取的每个数据元素,并依值在线性表LA中进行查访,如果不存在,则插入之

void union(List &La, List Lb)
{
    La_len = ListLength(La);
    Lb_len = ListLength(Lb);
    for(i = 1;i <= Lb_len; i++)
    {
        GetElem(Lb, i, e);//取Lb中第i个数据元素赋给e
        if(!LocateElem(La,e,equal))//La中不存在和e相同的数据元素,则插之
            ListInsert(La, ++La_len, e);
    }
}

算法复杂度:O(LALB)
2、线性表合并且按值非递减有序排列

void MergeList(List La, List Lb, List &Lc)
{
    //已知线性表La和Lb的数据元素按值非递减排序
    InitList(LC);
    i = j = 1;k = 0;
    La_len = ListLength(La);
    Lb_len = ListLength(Lb);
    while((i <= La_len) && (j <= Lb_len))
    {
        GetElem(La, i, ai);
        GetElem(Lb, j, bj);
        if(ai <= bj)
        {
            ListInsert(Lc, ++k, ai);
            ++i;
        }
        else
        {
            ListInsert(Lc,++k, bj);
            ++j;
        }
    }
    while(i <= La_len)
    {
        GetElem(La,i++,ai);
        ListInsert(Lc, ++k, ai);
    }
    while(j <= Lb_len)
    {
        GetElem(Lb,j++,bj);
        ListInsert(Lc,++k,bj);
    }
}

算法复杂度:O(LA+LB)

参考代码——典型操作代码实现

//数组定义
 typedef struct 
 {
    Elemtype elem[LIST_MAX_LENGTH]; //指向存放线性表中数据元素
    int length; //线性表的当前长度
    int listsize;
 }SEQLIST;
 //初始化线性表
 int InitList(SEQLISI *L)
 {
     L.elem = (Elemtype *)malloc(LIST_MAX_LENGTH*sizeof(Elemtype));//分配空间
     if(L.elem == NULL)
        exit(OVERFLOW);//存储分配失败
     L.length = 0;//空表长度为0
     L.listsize = LIST_MAX_LENGTH;//初始存储容量
     return OK;
 }
 //销毁线性表
 void DestoryList(SEQLIST *L)
 {
     if(L.elem)
        free(L.elem);//释放线性表占据的所有存储空间
 }
 //清空线性表
 void ClearList(SEQLIST *L)
 {
     L.length = 0;
 }
 //求线性表的长度
 int GetLength(SEQLIST L)
 {
     return(L.Length);
 }
 //判断线性表是否为空
 int IsEmpty(SEQLIST L)
 {
     if(L.length == 0)
        return true;
    return false;
 }
 //获取线性表L中某个数据元素的内容
 int GetElem(SEQLIST L,int i,Elemtype *e)
 {
     if(i < 1 || i > L.Length)
        return error;
    *e = L.elem[i-1];//数组中第i-1个单元存储着线性表中第i个数据元素内容
    return ok;
 }
 //在线性表L中检索值为e的数据元素
 int LocateElem(SEQLIST L,Elemtype e)
 {
     for(i = 0;i < L.length;i++)
     if(L.elem[i] == e)
        return i+1;
    return 0;
 }
 //判定L中第一个与e满足关系compare()的数据元素的位序,如果没有,则返0
 LocateElem(L,e, int (*compare)(ElemType, ElemType))
 {
     i = 1;//i的初值为第一个元素的位序
     p = L.elem; //p的初值为第一个元素的存储位置
     while(i<= L.length && !(*compare)(*p++,e))
        ++i;
    if(i <= L.length)return i;
    else return 0;
 }

 //在线性表中第i个数据元素之前插入数据元素e
 int ListInsert(SEQLIST *L,int i,Elemtype e)
 {
     if(L.length >= L.listsize)
        exit(OVERFLOW);
    if(i < 1||i>L.length + 1)
        return error;//检查i值是否合理
    q = &(L.elem[i-1]); //q为插入的位置
    for(p = L.elem[Length-1];p >= q;--p)
    {
       *(p+1) = *p;
    }//出入位置及之后的元素右边移动
        *q = e;//插入e
        L.length++;
    return ok;
 }
 //把线性表中第i个数据元素删除
 int ListDelete(SEQLIST *L, int i, Elemtype *e)
 {
     if(IsEmpty(L))
        return error;
    if(i < 1 ||i>L.length)
        return error;
    p = &(L.elem[i-1]);//p为被删除元素的位置
    e = *p; //被删除元素的值赋给e
    q = L.elem + L.length - 1; //表尾元素的位置
    for(p = p+1;p <= q;++p)
        *(p-1) = *p;//被删除元素之后的元素左移
    --L.length;
    return OK;
 }

总结:顺序存储结构表示的线性表,在做插入或删除操作的时,平均需要移动大约一半的数据元素;对于长度变化较大的线性表,要一次性地分配足够的存储空间,但这些空间常常又得不到充分的利用;线性表的容量难以扩充
补充:顺序表的合并

void MergeList_Sq(SqList La, SqList Lb, SqList &Lc)
{
    pa = La.elem;pb = Lb.elem;
    Lc.Listsize = Lc.length = La.length + Lb.length;
    pc = Lc.elem = (ElemType*)malloc(Lc.listsize * sizeof(ElemType));
    if(!Lc.elem)exit(OVERFLOW);
    pa_last = La.elem + La.length - 1;
    pb_last = Lb.elem + Lb.length - 1;
    while(pa <= pa_last && pb <= pb_last)
    {
        if(*pa < *pb) *pc++ = *pa++;
        else
            *pc++ = *pb++;
    }
    //插入La剩余元素
    while(pa <= pa_last)
        *pc++ = *pa++;//插入La的剩余元素
    while(pb <= pb_last)
        *pc++ = *pb++;//插入Lb的剩余元素
}

算法复杂度为O(La.length + Lb.length)
5、线性表的链表表示LinkedList
一般采用链表来描述

\


优点:对于新增和删除操作add和remove方便,不需要移动元素 缺点:不方便随机访问元素,因为LinkedList要移动指针
常用术语:

1)表示每个数据元素的两个部分信息组合在一起叫做结点;
2)其中表示数据元素内容的部分叫做数据域data
3)表示直接后继元素存储地址的部分叫做指针或指针域next
4)head是头指针,它指向单链表中第一个结点,这是单链表操作的入口点,最后一个结点没有直接后续结点,所以放入NULL
5)为了简化对链表的操作,常在链表的第一个结点之前附加入一个结点,并称为头结点
特征:<喎?http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vc3Ryb25nPjxicj4KMaOpz9/Q1LHt1tC1xMr9vt3UqsvY1Nq05rSitaXUqtbQtcS05rfFy7PQ8tPrwt+8rcuz0PKyu9K7tqjSu9bCo7vTw9K71+nIztLitcS05rSitaXUqrTmtKLP39DUse21xMr9vt3UqsvYo6jV4tfptOa0orWl1Kq/ydLUysfBrND4tcSjrNKyv8nS1MrHsrvBrND4tcSjqTxicj4KMqOp1Nq21M/f0NSx7bLZ1/fKsaOs1rvE3M2ouf3Nt9a41eu9+MjrwbSx7aOssqLNqLn9w7+49r3hteO1xNa41evT8s/yuvPJqMPoxuTT4L3hteOjrNXi0fm+zbvh1OyzydGw1dK12tK7uPa94bXjus3RsNXS1+6689K7uPa94bXjy/m7qLfRtcTKsbzksru1yKOsvt/T0NXi1tbM2LXjtcS05siht73KvbG7s8bOqsuz0PK05siht73KvaGjPGJyPgo8c3Ryb25nPrLOv7y0+sLroaqhqrXk0M2y2df3yrXP1jwvc3Ryb25nPjwvcD4KPHByZSBjbGFzcz0="brush:sql;">//实现线性表的链式存储结构的类型的定义 typedef struct linklist//结点类型 { Elemtype elem; struct linklist *next; }LINKLIST; typedef struct//链表类型 { LINKLIST *head; }LINK_LIST; //初始化链表 int InitList(LINK_LIST *L) { L->head = (*LINKLIST)malloc(sizeof(LINKLIST));//为头结点分配存储单元 if(L->head) { L->head->next = NULL; return OK; } return error; } //摧毁链表 void DestoryList(LINK_LIST *L) { LINKLIST *p; while(L->head)//依次删除链表中的所有结点 { p = L->head; L->head = L->head->next; free(p); } } //清空链表 void ClearList(LINK_LIST *L) { LINKLIST *p; while(L->head->next) { p = L->head->next; //p指向链表中头结点后面的第一个结点 L->head->next = p->next;//删除p结点 free(p);//释放p结点占据的存储空间 } } //求链表的长度 int ListLength(LINK_LIST L) { LINK_LIST *p; int len; for(p = L->head,len = 0;p->next == NULL; p=p->next,len++) return len; } //判断链表是否为空 int IsEmpty(LINK_LIST L) { if(L->head->next == NULL) return true; return false; } //通过e返回链表L中第i个元素的内容 int GetElem(LINK_LIST L, int i, Elemtype *e) { p = L->next; j = 1;//初始化,p指向第一个结点,j为计数器 while(p && j < i)//顺时针向后查找,直到p指向第i个元素或p为空 { p = p->next; ++j; } if(!p || j > i) return ERROR; e = p->elem;//取第i个元素 return OK; }//算法复杂度为O(n) //在链表L中检索值为e的数据元素 LINKLIST *LocateELem(LINK_LIST L,Elemtype e) { LINKLIST *p; for(p = L->head->next; p&&p->elem != e; p=p->next); return(p); } //返回链表L中结点e的直接前驱结点 LINKLIST *PriorElem(LINK_LIST L,LINKLIST* e) { LINKLIST *P; if(L->head->next == e) return NULL;//检测为第一个结点 for(p=L->head;p->next&&p->next != e;p = p->next); if(p->next == e) return p; return NULL; } //返回结点为e的直接后继结点 LINKLIST *NextElem(LINK_LIST L,LINKLIST* e) { LINKLIST *p; for(p=L->head->next;p&&p!=e;p=p->next); if(p) p=p->next; return p; }

补充:高级操作
1)插入结点

\

//在带头结点的单链线性表L中第i个位置之前插入元素e
    int ListInsert(LinkList *L,int i, ElemType)
    {
        p = L;j = 0;
        while(p && jnext;
            ++j
        }//需找第i-1个结点
        if(!p || j>i-1)
            return error;//i<1或者大于表长加1
        s = (LinkList)malloc(sizeof(LNode));
        s->data = e;
        s->next = p->next;
        p->next = s;
        return ok;
    }

复杂度为O(n)
2)删除结点

\

//在带头结点的单链线性表L中删除第i个元素,并由e返回其值
int LisyDelete(LinkList *L, int i,ElemType &e)
{
    p = L;j = 0;
    while(p->next && j < i-1)
    {
        p = p->next;
        ++j;//寻找第i个结点,并令p指向其前驱
    }
    if(!(p->next) || j>i-1)
        return error;
    q = p->next;
    p->next = q->next;
    e = q->elem;
    free(q);
    return ok;
}

复杂度为O(n)
3)合并有序链表

void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc)
{
    pa = La->next;
    pb = Lb->next;
    Lc = pc = La;//用La的头结点作为Lc的头结点
    while(pa && pb)//由于链表的长度是隐藏的,修改循环条件
    {
        if(pa->elem <= pb->elem)
        {
            pc->next = pa; //pc所指结点链接到pc所指结点之后
            pc = pa;
            pa = pa->next;
        }
        else
        {
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
    }
    pc->next = pa ? pa : pb;
    free(fb);
}

6、循环链表

\


循环链表的操作和线性链表基本一致,差别在于算法中循环条件不是p或p->next是否为空了,而是它们是否等于头指针。
7、双向链表

人气教程排行