首页
课程
路径
文章
PHP培训
精品课
下载

技术文章  >  数据库 > mysql教程

数据结构表

原创
2016-06-07 15:59:46 1105浏览

数据结构——表 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 


算法复杂度：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 


算法复杂度：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  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.listsize)
        exit(OVERFLOW);
    if(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 L.length)
        return error;
    p = &(L.elem[i-1]);//p为被删除元素的位置
    e = *p; //被删除元素的值赋给e
    q = L.elem + L.length - 1; //表尾元素的位置
    for(p = p+1;p 


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


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 


算法复杂度为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 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;//idata = 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 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 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、双向链表
数据结构 数据结构 定义 线性 一个 结构 它是 含有 0个PHP课程HTML视频教程CSS视频JS视频教程Vue视频教程
声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn核实处理。
上一条：DBCP与C3P0数据库连接池 下一条：索引组织表和普通表

相关文章

查看更多
  • 热门课程
打开APP，随时随地在线学习！