数据结构表

数据结构——表 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&#43;&#43;)
    {
        GetElem(Lb, i, e);//取Lb中第i个数据元素赋给e
        if(!LocateElem(La,e,equal))//La中不存在和e相同的数据元素，则插之
            ListInsert(La, &#43;&#43;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, &#43;&#43;k, ai);
            &#43;&#43;i;
        }
        else
        {
            ListInsert(Lc,&#43;&#43;k, bj);
            &#43;&#43;j;
        }
    }
    while(i <= La_len)
    {
        GetElem(La,i&#43;&#43;,ai);
        ListInsert(Lc, &#43;&#43;k, ai);
    }
    while(j <= Lb_len)
    {
        GetElem(Lb,j&#43;&#43;,bj);
        ListInsert(Lc,&#43;&#43;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中检索&#20540;为e的数据元素
 int LocateElem(SEQLIST L,Elemtype e)
 {
     for(i = 0;i < L.length;i&#43;&#43;)
     if(L.elem[i] == e)
        return i&#43;1;
    return 0;
 }
 //判定L中第一个与e满足关系compare()的数据元素的位序,如果没有，则返0
 LocateElem(L,e, int (*compare)(ElemType, ElemType))
 {
     i = 1;//i的初&#20540;为第一个元素的位序
     p = L.elem; //p的初&#20540;为第一个元素的存储位置
     while(i<= L.length && !(*compare)(*p&#43;&#43;,e))
        &#43;&#43;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 &#43; 1)
        return error;//检查i&#20540;是否合理
    q = &(L.elem[i-1]); //q为插入的位置
    for(p = L.elem[Length-1];p >= q;--p)
    {
       *(p&#43;1) = *p;
    }//出入位置及之后的元素右边移动
        *q = e;//插入e
        L.length&#43;&#43;;
    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; //被删除元素的&#20540;赋给e
    q = L.elem &#43; L.length - 1; //表尾元素的位置
    for(p = p&#43;1;p <= q;&#43;&#43;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&#43;&#43; = *pa&#43;&#43;;
        else
            *pc&#43;&#43; = *pb&#43;&#43;;
    }
    //插入La剩余元素
    while(pa <= pa_last)
        *pc&#43;&#43; = *pa&#43;&#43;;//插入La的剩余元素
    while(pb <= pb_last)
        *pc&#43;&#43; = *pb&#43;&#43;;//插入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 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 && j<i-1)
        {
            p = p->next;
            &#43;&#43;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;
        &#43;&#43;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、双向链表