线性表、链表、栈和队列

线性表、链表、栈和队列是编程中常用的数据结构。

数据的逻辑结构

逻辑结构：是数据的组织形式，用来表示数据之间的逻辑关系，其结构由数据元素的集合和元素之间的关系组成。

三种基本逻辑结构

• 线性结构：数据元素之间为一对一前后连接的关系
• 树形结构：只有一个处在最高层次的数据元素无前结点，为根；其余元素均有且只有一个前结点，后结点无个数限制
• 图结构：每一元素均可有任意的前后结点，任意两结点可连接

数据的物理结构

数据元素及其关系在存储器中的存放形式称为物理结构，即存储结构。

物理结构分类

• 顺序存储：元素按某种顺序存储在连续的存储单元中，存储位置间关系反映元素间逻辑关系
• 链式存储：元素存储在不一定连续的存储单元，通过在元素中附加信息来表示与其想关的一个或多个其他元素的物理地址来建立元素间的逻辑关系
• 索引存储：将数据元素排成一个序列，每个元素对应一个索引，存储时建立附加的索引表，表中为元素的存储地址
• 散列存储：数据元素均匀存放在存储区中，在数据元素和其在存储器中的位置之间建立一个映射关系，根据该关系可得其存储地址

线性表

采用顺序存储结构的称为顺序表，采用链式存储结构的称为线性链表

顺序存储特点

• 优点：无需为元素间的逻辑关系增加额外存储空间；可随机存取
• 缺点：元素插入删除需进行大量元素移动，效率低；占用连续存储空间，且初始化时需确定大小

顺序表的定义

const int maxsize=200;      //最大长度
struct SeqList {
    ElemType data[maxsize]; //存储数组的地址
    int length;             //当前长度
};
SeqList List;
List.length=0;

顺序表插入元素

void Insert(SeqList *L,int i,ElemType x) {
    if(i<1||i>L->length-1||L->length==maxsize)
    cout<<"插入位置错误或表满"；
    else {
        for(int j=L->length+1;j>=i-1;j++)
            L->data[j+1]=l->data[j]; //元素依次后移
        L->data[i-1]=x;              //i位置存入新元素
        L->length++;                 //表长加一
    }
}

顺序表删除元素

void Delete(SqeList *L,int i) {
    if(i<1||i>L->length)
        cout<<"表中无第"<<i<<"个元素";
    else {
        for(int j=i;j<L->length;j++)
            L->data[j-1]=L->data[j]; //删除i位置元素，元素依次前移 
        L->length--;                 //表长减一
    }
}

顺序表查找元素

int Find(SeqList *L,ElemType x) {
    for(int i=0;i<L->length;i++) {
        if(L->data[i]==x)
        return i+1;        //返回元素位置
    }
    return 0;
}

链式存储特点

• 优点：无需预先设置存储空间，灵活分配；插入删除无需移动额外元素
• 缺点：需要额外空间存储元素关系，数据域、指针域；查询效率低

链表定义

struct LNode {
    ElemType data;         //数据域，ElemType为某种数据类型
    struct LNode *next;    //指针域
};
LNode* head;               //头指针
head=new LNode;            //头结点
head->next=NULL;           //头结点指针域为空

单链表长度

int Length() {
    LNode *p=head->next;
    int len=0;
    while(p!=NULL) {
        len++;
        p=p->next;
    }
    return len;
}

在链表i位置插入新结点

void Insert(LNode *head,int i,ElemType x) {
    if(i<1)
        cout<<"不存在第"<<i<<"个位置"；
    else {
        LNode *p=head;
        int k=0;                         //p指向头结点，最终指向第i-1个结点
        while(p!=NULL&&k<i-1) {           
            p=p->next;
            k++;
        }
        if(p==NULL)
            cout<<i<<"超出链表最大可插入位置"；
        else {
            LNode *s=new LNode;          //建立新结点s
            s->data=x;
            s->next=p->next;             //修改结点s指针
            p->next=s;                   //修改结点p指针
        }
    }
}

从单链表中删除第i个结点

void Delete(LNode *head,int i) {
    if(i<1)
        cout<<"不存在第"<<i<<"个位置"；
    else {
        LNode *p=head;                    //p指向头结点
        LNode *q;                         //q和p最终分别指向第i-1和第i个结点
        int k=0;   
        while(p!=NULL&&k<i-1) {
            q=p;
            p=p->next;
            k++;
        }
        if(p==NULL)
            cout<<i<<"超出链表长度";
        else {
            q->next=p->next;              //从链表中删除该结点
            delete p;                     //释放结点p
        }
}

查找链表中的结点

LNode* Find(LNode *head,ElemType x) {
    LNode *p=head->next;                 //p指向第一个元素所在结点
    while(p!=NULL&&p->data!=x)
        p=p->next;
    return p;
}

其他形式链表

• 循环链表：将单链表尾结点的指针由NULL改为指向头结点，首尾连接形成一个环形，为循环链表
• 双向链表：每个结点的指针域再增加一个指针，指向该结点的前一结点，形成两个不同方向的链
• 双向循环链表：将双链表的头结点的前趋指针指向尾结点，将尾结点的后继指针指向头结点

栈

• 只能在一端进行插入和删除操作的特殊线性表，允许进行插入删除操作的一端为栈顶，另一端为栈底
• 特点为先进后出(FILO,first in last out)或后进先出(LIFO,last in first out)
• 可应用于进制转换、括号/引号匹配检查、递归算法等

顺序栈定义

struct SqStack {
    ElemType *data;     //存储元素的变量
    int top;            //栈顶指针，存储元素下标
    int stacksize;      //栈空间大小
};
SqStack s;              //定义一个栈

元素入栈

void Push(SqStack *s,ElemType x) {
    if(s->top < s->stacksize-1) {
        s->top++;
        s->data[top]=x;
    } else 
        cout<<"栈满";
}

元素出栈

void Pop(SqStack *s,ElemType &e) {
    if(s->top > -1) {
        e=s->data[s->top];
        s->top--;
    } else 
        cout<<"栈空";
}

取栈顶元素

void Peek(SqStack *s,ElemType &e) {
    if(s->top > -1) {
        e=s->data[s->top];
    } else 
        cout<<"栈空";
}

队列

• 只能在表的一端进行插入操作，另一端进行删除操作的特殊线性表
• 允许删除元素的一端为队头(指针指空)，允许插入元素的一端为队尾(指针指队尾元素)，先进先出
• 主要应用于缓存，打印队列等

循环队列

• 将队列的头尾相连
• 当队尾和队头重叠时，约定为队空；当队尾加一后等于队头时，队满

链式队列

• 为队列的每一元素附加一个存储元素关系的指针域

队列定义

const int MAX=100
struct SqQueue {
    int data[MAX];     //存放元素的数组
    int front;         //队头指针
    int rear;          //队尾指针
};
SqQueue q;             //定义队列q
q.front=q.rear;        //指针初始化

入队操作

void EnQueue(SqQueue &q,ElemType x) {
    if((q.rear+1)%MAX==q.front)
        cout<<"队列已满";
    else {
        q.rear=(q.rear+1)%MAX;
        q.data[q.rear]=x;
    }
}

出队操作

void DeQueue(SqQueue &q) {
    if(q.rear==q.front)
        cout<<"队列为空";
    else 
        q.front=(q.front+1)%MAX;
    return q.data[q.front];
}

取队头元素

ElemType GetHead(SqQueue &q) {
    int i;
    if(q.rear==q.front)
        cout<<"队列为空";
    else 
        i=(q.front+1)%MAX;
    return q.data[i];
}