数据结构诸论与线性表总结

一、思维导图

二、重要概念

1.线性表

a.存储结构代码

顺序存储结构：

#define MaxSize 50
typedef int ElemType;
typedef struct{
    ElemType data[MaxSize];//结构体中含数组
    int length;
}SqList;

链式结构代码：

1)结点定义：

typedef struct LNode
{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

2)链表创建：

头插法：

void CreatListF(LinkList &L,int n)
{
    L=new LNode;
    L->next=NULL;
    for(int i=0;i<n;i++)
    {
        LinkList s=new LNode;
        cin>>s->data;
        s->next=L->next;
        L->next=s;
    }
}

尾插法：

void CreatListR(LinkList &L,int n)
{
    L->next=NULL;
    LinkList s=L;
    for(int i=0;i<n;i++)
    {
        LinkList p=new LinkList;
        p->next=NULL;
        cin>>p->data;
        s->next=p;
        s=s->next;
    }
}

b.易错的基本操作

1) 顺序存储的插入与删除：

插入：

在位置n+1插入，移动0次；在位置1插入，移动n次。

删除：

在位置n删除，移动0次；在位置1删除，移动n-1次。

2.栈

a.顺序栈

1)栈空条件：s->top=-1;

2)栈满条件：s->top=MaxSize-1;

3)进栈操作：

s->top++;
s->top=e;

注意：要先确定栈是否满了；

4)出栈操作：

e=s->top;
s->top--;

注意：要先确定栈是否为空；

b.链栈

1)栈空条件：s->next=NULL;

2)进栈：

因为只能在栈顶进行操作，所以用类似头插法的方法来进栈。且不用头指针，新建结点直接为头指针，且赋值于S。

StackNode *p=new StackNode;
p->data=e;
p->link=S;
S=p;

3)出栈：

先判断栈是否为空，然后赋值，销毁结点。

3.队列

a.顺序队列：

1)使用条件：所需要进行操作的元素个数不会超过MaxSize；

2)空队列条件：Q.front==Q.rear;

3)队列满条件：Q.rear-Q.front=m;

4)入队：Q.base[rear++]=x;

5)出队：x=Q.base[front++];

入队与出队相同：都是先赋值，再将变量++。

b.循环队列：

1)特点：逻辑上数组首尾相接，具体操作时少用一个元素空间:(%m)；

2)队空：Q.rear=Q.front;

3)队满：(Q.rear+1)%m=Q.front;

4)入队：Q.rear=(Q.rear+1)%m;

5)出队：Q.front=(Q.front+1)%m;

入队与出队都是先将变量++，再赋值。

6)队列中存在的元素：Q.rear-Q.front;（因为队头会变）。

c.链队列：

1)创建：

typedef struct QNode{
    int data;
    struct QNode *next;
}QNode,*QueuePtr;
typedef struct{
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;
Int InitQueue(LinkQueue &Q){
    Q.front=Q.rear=new QNode;//队头指针与队尾指针分别进行动态分配
    Q.front->next=NULL;
    return 1;
}

2)队空判断：Q.front==Q.rear;

不是Q.rear->next=NULL,因为有存在入队后出队的情况。

3)入队：

p=new LNode;
p->data=e;
p->next=NULL;  
Q.rear->next=p;
Q.rear=p;//队头不变，队尾进行连接链表的操作
if(Q.front->next==NULL)
{
    Q.front->next=p;
}  

4)出队：

先判断队列是否为空，然后取队头指针的next结点，取值，指向下一结点，销毁结点，并且判断是否原队列中只剩一个元素。

P=Q.front->next;
if(Q.rear==p)
Q.rear=Q.front;//所以front元素是取next值，而rear是取本身

4.串

a.串的模式匹配算法：

1)BF算法：主串与模式串都回溯；

2)KMP算法：主串不用回溯，在模式串中找尽量长的相同的顺序。

5.c++中的queue、stack、string使用

a.queue<元素类型>名称、stack<元素类型>名称:

栈、队列元素类型由自己定义，可以是int、char，或是自己定义的结构体;

b.出栈、出队的操作，只是将元素弹出，并不包括赋值；

c.string文件既包含对整体的操作（size()),还包含对串中的元素进行的操作。

三、疑难问题

1.递归函数的时间复杂度

a.列相应的分段函数；

b.根据具体函数，找到递归出口，确定函数调用次数；

c.确定每次调用所要进行的基本运算语句数；

d.根据列出的分段函数进行相加，得出时间复杂度。