#2线性关系

一、定义
线性表：线性表是具有相同的数据类型的n（n>=0）个数据元素的有限序列。
表长：线性表中元素的个数n称为表长。当n=0时，线性表为空表。
二、基本操作
初始化：InitList(&L)
插入：ListInsert(&L,i,e)
删除：ListDelete(&L,i,&e)
查找：GetElem(L,i)/LocateElem(L,e)
求表长：Length(L)
判空：Empty(L)
三、存储结构
（一）顺序表
1、顺序表的定义
顺序表是使用顺序存储方式实现的线性表。

//静态分配实现顺序表
typedef struct{
    ElemType data[MaxSize];
    int Length;
}SqList;
//动态分配实现顺序表
typedef struct{
    ElemType *data;
    int Length,MaxSize;
}SeqList;

2、顺序表的基本操作
初始化

//静态分配的初始化
bool InitList(SqList &L){
    L.Length=0;
    return true;
}
//动态分配的初始化
bool InitList(SeqList &L){
    L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);
    L.Length=0;
    L.MaxSize=InitSize;
    return true;
}
//动态分配下的扩容函数
bool IncreaseSize(SeqList &L,int Len){
    ElemType *p=L.data;
    L.data=(ElemType*)malloc(sizeof(ElemType)*(L.MaxSize+Len));
    for(int i=0;i<L.Length;i++)
    {
        L.data[i]=p[i];
    }
    L.MaxSize+=Len;
    free(p);
    return true;
}

插入

//按位序插入
bool ListInsert(SqList &L,int i,ElemType e){
    if(i<1||i>L.Length+1)
    {
        return false;
    }
    if(L.Length==L.MaxSize)
    {
        return false;
    }
    for(int j=L.Length;j>=i;j--)
    {
        L.data[j]=L.data[j-1];
    }
    L.[i-1]=e;
    L.Length++;
    return true;
}

删除

//按位序删除
bool ListDelete(SqList &L,int i,ElemType &e){
    if(i<1||i>L.Length)
    {
        return false;
    }
    e=L.data[i-1];
    for(int j=i;j<L.Length;j++)
    {
        L.data[j-1]=L.data[j];
    }
    L.length--;
    return true;
}

查找

//按位查找
ElemType GetElem(SqList L,int i){
    return L.data[i-1];
}
//按值查找
int LocateElem(SqList L,ElemType e){
    for(int i=0;i<L.Length;i++)
    {
        if(e==L.data[i])
        {
            return i+1;
        }
    }
    return 0;
}

求表长

int Length(SqList L){
    return L.Length;
}

判空

bool Empty(SqList L){
    if(L.Length==0)
    {
        return true;
    }
    else
    {
        return false;
    }
}

（二）链表
1、单链表
（1）单链表的定义
单链表是使用链式存储方式实现的线性表。每个结点之间通过一个单向的指针连接。

//单链表结点定义
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

（2）单链表的基本操作
初始化

//携带头结点
bool InitList(LinkList &L){
    L=(LNode*)malloc(sizeof(LNode));
    L->next=NULL;
    return true;
}
//不带头结点
bool InitList(LinkList &L){
    L=NULL;
    return true;
}

插入

//按位序插入
bool ListInsert(LinkList &L,int i,ElemType e){
    if(i<1)
    {
        return false;
    }
    LNode *p=L,*s;
    if(i=1)
    {
        s=(LNode*)malloc(sizeof(LNode));
        s->data=e;
        s->next=L;
        L=s;
        return true;
    }
    //若不带头结点，插入第一个结点特殊处理
    int j=0;
    while(p!=NULL&&j<i-1)
    {
        p=p->next;
        j++;
    }
    if(p==NULL)
    {
        return false;
    }
    s=(LNode*)malloc(sizeof(LNode));
    s->data=e;
    s->next=p->next;
    p->next=s;
    return true;
}
//指定结点后插
bool InsertNextNode(LNode *p,ElemType e){
    if(p==NULL)
    {
        return false;
    }
    LNode *s=(LNode*)malloc(sizeof(LNode));
    s->data=e;
    s->next=p->next;
    p->next=s;
    return true;
}
//指定结点前插
bool InsertPriorNode(LNode *p,ElemType e){
    if(p==NULL)
    {
        return false;
    }
    LNode *s=(LNode*)malloc(sizeof(LNode));
    s->data=p->data;
    p->data=e;
    s->next=p->next;
    p->next=s;
    return true;
}

删除

//按位序删除
bool ListDelete(LinkList &L,int i,ElemType &e){
    if(i<1)
    {
        return false;
    }
    LNode *p=L,*s;
    int j=0;
    while(p!=NULL&&j<i-1)
    {
        p=p->next;
        j++;
    }
    if(p==NULL)
    {
        return false;
    }
    s=p->next;
    if(s==NULL)
    {
        return false;
    }
    e=s->data;
    p->next=s->next;
    free(s);
    return true;
}
//指定结点删除
bool DeleteNode(LNode *p,ElemType &e){
    if(p==NULL)
    {
        return false;
    }
    e=p->data;
    LNode *s=p->next;
    p->data=s->data;
    p->next=s->next;
    free(s);
    return true;
}

查找

//按位查找
LNode* GetElem(LinkList L,int i){
    if(i<0)
    {
        return NULL;
    }
    LNode *p=L;
    int j=0
    while(p!=NULL&&j<i)
    {
        p=p->next;
        j++;
    }
    return p;
}
//按值查找
LNode* LocateElem(LinkList L,ElemType e){
    LNode *p=L;
    while(p!=NULL&&p->data!=e)
    {
        p=p->next;
    }
    return p;
}

求表长

int Length(LinkList L){
    int j=0;
    LNode *p=L;
    while(p->next!=NULL)
    {
        p=p->next;
        j++;
    }
    return j;
    //若不带头结点，返回j-1
}

判空

bool Empty(LinkList L){
    if(L->next==NULL)
    //若不带头结点，判断条件为L==NULL
    {
        return true;
    }
    else
    {
        return false;
    }
}

2、双链表
（1）双链表的定义
双链表是使用链式存储实现的线性表。在单链表的基础上，添加了向前的指针。

typedef struct DNode{
    ElemType data;
    struct DNode *prior,*next;
}DLNode,*DLinkList;

（2）双链表的基本操作
初始化

//带头结点
bool InitList(DLinkList &L){
    L=(DNode*)malloc(sizeof(DNode));
    L->next=NULL;
    L->prior=NULL;
}

插入

//按位序插入
bool ListInsert(DLinkList &L,int i,ElemType e){
    if(i<1)
    {
        return false;
    }
    DNode *p=L,*s;
    int j=0;
    while(p!=NULL&&j<i-1)
    {
        p=p->next;
        i++;
    }
    if(p==NULL)
    {
        return false;
    }
    s=(DNode*)malloc(sizeof(DNode));
    s->data=e;
    s->next=p->next;
    p->next=s;
    s->prior=p;
    if(s->next!=NULL)
    {
        s->next->prior=s;
    }
    return true;
}
//指定结点后插
bool InsertNextNode(DLNode *p,ElemType e){
    if(p==NULL)
    {
        return false;
    }
    DNode *s=(DNode*)malloc(sizeof(DNode));
    s->data=e;
    s->next=p->next;
    p->next=s;
    s->prior=p;
    if(s->next!=NULL)
    {
        s->next->prior=s;
    }
    return true;
}
//指定结点前插
bool InsertPriorNode(DLnode *p,ElemType e){
    if(p==NULL)
    {
        return false;
    }
    p=p->prior;
    DNode *s=(DNode*)malloc(sizeof(DNode));
    s->data=e;
    s->next=p->next;
    p->next=s;
    s->prior=p;
    s->next->prior=s;
    return true;
}

删除

//按位序删除
bool ListDelete(DLinkList &L,int i,ElemType &e){
    if(i<1)
    {
        return false;
    }
    DNode *p=L,*s;
    int j=0;
    while(p!=NULL&&j<i-1)
    {
        p=p->next;
        j++;
    }
    if(p==NULL)
    {
        return false;
    }
    s=p->next;
    if(s==NULL)
    {
        return false;
    }
    e=s->data;
    s->next=p->next;
    if(s->next!=NULL)
    {
        s->next->prior=p;
    }
    free(s);
    return true;
}
//指定结点删除
bool DeleteNode(DNode *p,ElemType &e){
    if(p==NULL)
    {
        return false;
    }
    e=p->data;
    DNode *s=p->prior;
    s->next=p->next;
    if(p->next!=NULL)
    {
        p->next->prior=s;
    }
    free(p);
    return true;
}

//查找

//按位查找
DNode* GetElem(DLinkList L,int i){
    if(i<1)
    {
        return NULL;
    }
    DNode *p=L;
    int j=0;
    while(p!=NULL&&j<i)
    {
        p=p->next;
        j++;
    }
    return p;
}
//按值查找
DNode* LocateElem(DLinkList L,ElemType e){
    DNode *p=L;
    while(p!=NULL&&e!=p->data)
    {
        p=p->next;
    }
    return p;
}

求表长

int Length(DLinkList L){
    DNode *p=L;
    int j=0;
    while(p->next!=NULL)
    {
        p=p->next;
        j++;
    }
    return j;
}

判空

bool Empty(DLinkList L){
    if(L->next==NULL&&L->prior==NULL)
    {
        return true;
    }
    else
    {
        return false;
    }
}

3、循环链表
（1）循环单链表
A、循环单链表的定义
循环单链表是使用链式存储实现的线性表，在单链表的基础上，使得最后一个结点的指针指向头结点。
B、循环单链表的基本操作
初始化

bool InitList(LinkList &L){
    L=(LNode*)malloc(sizeof(LNode));
    L->next=L;
    return true;
}

（2）循环双链表
A、循环双链表的定义
循环双链表是使用链式存储实现的线性表，在双链表的基础上，使得最后一个结点的向后指针指向头结点，头结点的向前指针指向最后一个结点。
B、循环双链表的基本操作
初始化

bool InitList(DLinkList &L){
    L=(DNode*)malloc(sizeof(DNode));
    L->next=L;
    L->prior=L;
    return true;
}

4、静态链表
静态链表的定义
静态链表是使用顺序存储的方式实现的逻辑上的链表。

typedef struct{
    ElemType data;
    int next;
}SLinkList[MaxSize];

四、应用线性表
（一）栈
1、栈的定义
栈是一种只允许在一端进行插入删除操作的线性表。
2、栈的基本操作
初始化：InitStack(&S)
入栈：Push(&S,e)
出栈：Pop(&S,&e)
读栈顶元素：GetTop(S,&e)
判空：Empty(S)
3、栈的存储结构
（1）顺序栈
A、顺序栈的定义
顺序栈是用顺序存储方式实现的栈。

typedef struct{
    ElemType data[MaxSize];
    int Top;
}SqStack;

B、顺序栈的基本操作
初始化

bool InitStack(SqStack &S){
    S.Top=-1;
    return true;
}

入栈

bool Posh(SqStack &S,ElemType e){
    if(S.Top==MaxSize-1)
    {
        return false;
    }
    S.data[++S.Top]=e;
    return true;
}

出栈

bool Pop(SqStack &S,ElemType &e){
    if(S.Top==-1)
    {
        return false;
    }
    e=S.data[S.Top--];
    return true;
}

读栈顶元素

bool GetTop(SqStack S,ElemType &e){
    if(S.Top==-1)
    {
        return false;
    }
    e=S.data[S.Top];
    return true;
}

判空

bool Empty(SqStack S){
    if(S.Top==-1)
    {
        return true;
    }
    else
    {
        return false;
    }
}

C、共享栈
共享栈使用一片空间存储两个顺序栈。

//定义
typedef struct{
    ElemType data[MaxSize];
    int Top1,Top2;
}ShStack;
//初始化
bool InitStack(ShStack &S){
    S.Top1=-1;
    S.Top2=MaxSize;
    return true;
}

（2）链栈
A、链栈
链栈是使用链式存储实现的栈。

typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode,*LStack;

B、链栈的基本操作
初始化

bool InitStack(LStack &S){
    S=(LinkNode*)malloc(sizeof(LinkNode));
    S->next=NULL;
    return true;
}

入栈

bool Push(LStack &S,ElemType e){
    LinkNode *p=(LinkNode*)malloc(sizeof(LinkNode));
    p->data=e;
    p->next=s->next;
    s->next=p;
    return true;
}

出栈

bool Pop(LStack &S,ElemType &e){
    if(s->next==NULL)
    {
        return false;
    }
    LinkNode *p=s->next;
    e=p->data;
    s->next=p->next;
    free(p);
    return true;
}

读栈顶元素

LinkNode* GetTop(LStack S){
    return S->next;
}

判空

bool Empty(LStack S){
    if(S->next==NULL)
    {
        return true;
    }
    else
    {
        return false;
    }
}

4、栈的应用
（1）括号匹配

bool BracketCheck(char str[],int length){
    SqStack S;
    InitStack S;
    for(int i=0,i<length;i++)
    {
        if(str[i]=='('||str[i]=='['||str[i]='{')
        {
            Push(S,str[i]);
        }
        else
        {
            if(Empty(S))
            {
                return false;
            }
            char Top;
            Pop(S,Top);
            if(str[i]==')'&&Top!='(')
            {
                return false;
            }
            if(str[i]==']'&&Top!='[')
            {
                return false;
            }
            if(str[i]=='}'&&Top!='{')
            {
                return false;
            }
        }
    }
    return Empty(S);
}

（2）表达式求值
A、后缀表达式
（A-1）中缀转后缀
自左向右扫描，直至末尾：
①若扫描到操作数，直接加入后缀表达式。
②若扫描到界限符，
a.“（”直接入栈。
b.“）”依次弹出栈顶元素，直至弹出“（”。
③若扫描到运算符，依次弹出栈中优先级不低于当前运算符的所有运算符，直到碰到“（”或栈空，最后将当前运算符加入表达式。
（A-2）后缀计算
自左向右扫描，直至末尾：
①若扫描到操作数，入栈。
②若扫描到运算符，弹出两个栈顶元素，计算并重新入栈。
B、前缀表达式
（B-1）中缀转前缀
自右向左扫描，规则一致。
（B-2）前缀计算
自右向左扫描，规则一致。
C、中缀表达式
中缀计算
自左向右扫描，直至末尾：
①若扫描到操作数，压入操作数栈。
②若扫描到运算符或界限符，依次弹出运算符栈中优先级不低于当前运算符的所有运算符，直到碰到“（”或栈空，每弹出一个运算符，弹出两个操作数进行运算并压入操作数栈。
最后将当前运算符加入运算符栈。
（3）递归
（二）队列
1、队列的定义
队列是一种只允许在一端输入，在另一端删除的线性表。
2、队列的基本操作
初始化：InitQueue(&Q)
入队：EnQueue(&Q,e)
出队：DeQueue(&Q,&e)
读队头元素：GetHead(Q,&e)
判空：Empty(Q)
3、队列的存储结构
（1）顺序队列
A、顺序队列的定义
顺序队列是使用顺序存储方式实现的队列。

typedef struct{
    ElemType data[MaxSize];
    int front,rear;
}SqQueue;

B、顺序队列的基本操作
初始化

bool InitQueue(SqQueue &Q){
    Q.front=Q.rear=0;
    return true;
}

入队

bool EnQueue(SqQueue &Q,ElemType e){
    if((Q.rear+1)%MaxSize==Q.front)
    {
        return false;
    }
    Q.data[Q.rear]=e;
    Q.rear=(Q.rear+1)%MaxSize;
    return true;
}

出队

bool DeQueue(SqQueue &Q,ElemType &e){
    if(Q.front==Q.rear)
    {
        return false;
    }
    e=Q.data[Q.front];
    Q.front=(Q.front+1)%MaxSize;
    return true;
}

读队头元素

bool GetHead(SqQueue Q,ElemType &e){
    if(Q.front==Q.rear)
    {
        return false;
    }
    e=Q.data[Q.front];
    return true;
}

判空

bool Empty(SqQueue Q){
    if(Q.front==Q.rear)
    {
        return true;
    }
    else
    {
        return false;
    }
}

（2）链式队列
A、链式队列的定义
链式队列是使用链式存储方式实现的队列。

//结点定义
typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode;
//队头队尾指针定义
typedef struct{
    LinkNode *front,*rear;
}LinkQueue;

B、链式队列的基本操作
初始化

bool InitQueue(LinkQueue &Q){
    Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));
    Q.rear->next=NULL;
    return true;
}

入队

bool EnQueue(LinkQueue &Q,ElemType e){
    LinkNode *p=(LinkNode*)malloc(sizeof(LinkNode));
    p->data=e;
    p->next=NULL;
    Q.rear->next=p;
    Q.rear=p;
    return true;
}

出队

bool DeQueue(LinkQueue &Q,ElemType &e){
    if(Q.front==Q.rear)
    {
        return false;
    }
    LinkNode *p=Q.front->next;
    e=p->data;
    Q.front->next=p->next;
    if(p->next==NULL)
    {
        Q.rear==Q.front;
    }
    free(p);
    return true;
}

读队头元素

LinkNode* GetHead(LinkQueue Q){
    return Q.front->next;
}

判空

bool Empty(LinkQueue Q){
    if(Q.front==Q.rear)
    {
        return true;
    }
    else
    {
        return false;
    }
}

4、双端队列
允许或部分允许从两端进行插入和删除操作的队列。具体有：
双端队列：允许从两端进行插入和删除
输入受限的双端队列：允许一端插入，两端删除
输出受限的双端队列：允许两端插入，一端删除
（三）串
1、串的定义
串：即字符串，是由0个或多个字符组成的有限序列。
串长：串中字符的个数n称为串的长度，n=0时为空串。
子串：串中任意个连续字符组成的子序列。
2、串的基本操作
求子串：SubString(&Sub,S,pos,len)
比较：StrCompare(S,T)
定位：Index(S,T)
3、串的存储结构
（1）顺序串
顺序串的定义
顺序串是使用顺序存储实现的串。

typedef struct{
    char ch[MaxLen];
    int length;
}SString;

（2）链串
链串的定义
链串是使用链式存储实现的串。

typedef struct StringNode{
    char ch;
    struct StringNode *next;
}StringNode,*String;

（3）基本操作
求子串

bool SubString(SString &Sub,SString S,int pos,int len){
    if(pos+len-1>S.length)
    {
        return false;
    }
    for(int i=pos;i<pos+len;i++)
    {
        Sub.ch[i]=S.ch[i];
    }
    Sub.length=len;
    return true;
}

比较

int StrCompare(SString S,SString T){
    for(int i=0;i<=S.length&&i<=T.length;i++)
    {
        if(S.ch[i]!=T.ch[i])
        {
            return S.ch[i]-T.ch[i];
        }
    }
    return S.length-T.length;
}

定位

int Index(SString S,SString T){
    int i=1,n=S.length,m=T.length;
    SString sub;
    while(i<=n-m+1)
    {
        SubString(sub,S,i,m);
        if(StrCompare(sub,T)!=0)
        {
            i++;
        }
        else
        {
            return i;
        }
    }
    return 0;
}

4、字符串的模式匹配
（1）朴素算法模式匹配
朴素算法模式匹配是从主串S的第i位开始，依次与模式串T进行逐位对比，一般来说i的初始值为1.
若对比失败，则回退i的值，并使得i=i+1，再次开始对比，直到对比成功或全部对比失败。
（2）KMP算法
KMP算法是预先计算出模式串对应的next数组，通过next数组调整模式串对比指针j的位置，而主串指针i不回退。

学习之旅

#1：绪论

#3树形关系

旅者

学习之旅