数据结构-基础知识点（复习用）

没错这篇只是为了应对考试来着=。=

为了复习我也是绝了。

一、绪论部分

1.数据项是不可分割的最小单位，是构成数据元素的最小单位。
2.数据元素是数据的基本单位。
3.数据结构是指数据元素的集合以及他们之间的关系。
4.计算机所处理的数据一般具备某种内在联系，这是指：元素和元素之间存在某种关系。

5.在数据结构中，与所使用的计算机无关的是数据的逻辑结构，数据的逻辑结构可以分为线性和非线性结构两类。数据的逻辑结构是指数据元素之间逻辑关系的整体。数据结构在计算机内存中的表示是指数据的存储结构。

6.常用的线性结构有：线性表，栈，队列，双队列，数组，串。
常见的非线性结构有：二维数组，多维数组，广义表，树(二叉树等)，图。

7.顺序存储和链接存储是数据的两种最基本的存储结构。哈希表也是。

8.算法的计算量的大小称为计算的复杂性。

9.计算机算法的特性至少包括可执行性、确定性、有穷性、（输入输出）。

10.数据结构的抽象操作的定义与具体实现无关，数据的运算与采用何种存储结构有关。

11.算法分析的目的是分析算法的效率以求改进。

12.算法(algorithm)是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。此外，一个算法还具有下列5个重要特性：
1) 有穷性
一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成。
2) 确定性
算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。即对于相同的输入只能得出相同的输出。
3) 可行性
一个算法是可行的，即算法中描述的操作都是吋以逋过已经实现的基本运算执行有限次来实现的。
4) 输入
一个算法有零个或多个的输入，这些输入取自于某个特定的对象的集合。
5) 输出
一个算法有一个或多个的输出，这些输出是同输入有着某种特定关系的量。
通常设计一个“好”的算法应考虑达到以下目标：
正确性：算法应当能够正确地解决求解问题。
可读性：算法应当具有良好的可读性，以助于人们理解。
健壮性：当输入非法数据时，算法也能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。
效率与低存储量需求：效率是指算法执行的时间，存储量需求是指算法执行过程中所需要的最大存储空间，这两者都与问题的规模有关。

二、线性结构

1.线性表是具有n个数据元素的有限序列，可以为空。

2.线性表除了第一个元素和最后一个元素外，其余元素有且仅有一个前驱和一个后继元素。
3.顺序存储结构
优点：
（1）是一种随机存取结构，存取任何元素的时间都是常数，速度快。
（2）结构简单，逻辑上相邻的元素物理上也相邻。
（3）不使用指针，节省存储空间。存储密度大，相比链表少了指针域。
缺点：
（1）插入删除要移动大量元素，浪费时间。
（2）需要一个连续的存储空间。
（3）插入元素可能会溢出。
（4）自由区的存储空间不能被其他数据占用/共享。

4.静态链表中指针表示的是下一元素地址。

5.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用带头结点的双循环链表存储方式最节省运算时间。
某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用仅带有尾指针的单循环链表存储方式最节省运算时间。
6.link前驱，rlink后继
双向链表，p前插入q：p.link.rlink=q;q.rlink=p;q.link=p.link;p.link=q;
双向循环链表，p指针所指向结点前插入q所指向的新节点：
q.rlink=p;q.link=p.link;p.link.rlink=q;p.link=q;
7.单链表，指针为p的节点后插入指针为s的结点：
s->next=p->next;p->next=s;

8.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是:head->next == NULL
带表头结点的双循环链表L为空表的条件是L->next==L

9.循环链表H的尾结点P的特点是：P.next = H;

10.一个栈的输入序列123…n，若输出序列的第一个元素是n，输出第i(1<=i<=n)个元素是 n-i+1

11.若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈(i=1,2)栈顶，栈的底在v[1]，栈2的底在V[m]，则栈满的条件是(top[1]+1=top[2])。

12.栈在递归调用、子程序调用、表达式求值中应用。
13.线性表的静态链表存储结构与顺序存储结构相比优点是便于插入删除。
线性表的顺序存储结构和链式存储结构相比，优点是便于随机存取。

14.用单链表表示的链式队列的队头在链表的链头位置。

15.用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时队头队尾指针可能都要改。

16.要求线性表采用静态空间分配方式，且插入和删除操作时不需要移动元素，采用的存储结构是静态链表。

17.循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是(（rear-front+m）%m)。

18.循环队列存储在数组A[0..m]中，则入队时的操作为rear=(rear+1)mod(m+1)。

19.最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是rear=front,队满的条件是(rear+1)%max == front

20.如果最常用的操作时取第i个元素及前驱元素，则采用顺序表存储方式最节省时间。

21.与单链表相比，双链表的优点之一是访问前后相邻节点更方便

22.在两个各有n个元素的递增有序顺序表归并成一个有序顺序表，其最少的比较次数为n，最多2n-1。
23.表达式求值运算符栈中运算符优先级：栈底最低。

24.在速度匹配等需要进行顺序缓冲的应用中，可以考虑使用队列。左右括号匹配：栈

25.在单链表中，增加一个头节点的目的是为了方便运算的实现。

26.将长度为m的单链表链接在长度为n的单链表之后的算法时间复杂度为 o(m）。

27.如果对含有n(n＞1)个元素的线性表的运算只有4种：删除第一个元素，删除最后一个元素，在第一个元素前面插入新元素，在最后―个元素的后面插入新元素，则最好使用( 只有开始数据节点指针没有尾节点指针的循环双链表)。

28.静态链表与动态链表在元素的插入、删除方面类似，不需要做元素的移动。

29.判定一个顺序栈st为（元素个数最多为MaxSize）空的条件为st.top==-1
判断栈满：st.top=MaxSize-1.

30.链栈与顺序栈相比有一个明显的优点: 通常不会出现栈满的情况

31.最适合用做链队列的不带表头节点的链表是:只带尾节点指针的循环单链表
最不合适用做链队的不带头节点的链表是: 只带队首节点指针的非循环单链表
不带有头节点，最不合适用作链栈的链表是: 只有表头指针没有表尾指针的循环单链表

32.空栈也有栈顶指针。

N、考试内容

一、讨论题

1.顺序表和链表按下标读取修改插入删除的平均时间复杂度是多少？当插入和删除较为频繁时应该是用那种线性结构？

答：线性顺序表和线性链表的插入和删除的平均时间复杂度都是O(n)
频繁地对一个线性表进行插入和删除操作，则该线性表宜采用链式存储结构。因为链式存储结构在插入和删除数据元素时不需要移动数据元素，只需要修改结点的指针域就可以改变数据元素之间的逻辑关系。

2．什么是队列、队头、队尾？

答：
队列：在一端进入，另一端出的线性表，先进先出。
对头：删除的一端。
队尾：插入的一端。

3.学过的那些结构和二叉树的链式结构比较像呢？

答：
1.广义表的扩展链
2.树的长子兄弟法

4.对称阵和稀疏矩阵在压缩存储时是否会丢失随机存储功能（无法O(1)时间按下标访问）？

答：对称阵不会。(还可以用下标访问)
稀疏矩阵会。（常见的稀疏矩阵包括三元组和十字链表，都需要遍历，所以丢失了。）

5.在堆排序、快速排序和归并排序中谁最省内存？谁是稳定的？谁的平均排序速度最快？

答：
最省内存：堆排序
稳定：归并排序
平均排序速度最快：快速排序

6.用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否有关？

答：用邻接矩阵表示图时，矩阵元素的个数是顶点个数的平方，所以与点的个数有关。
但与边的条数无关。非零元素的个数与边的条数有关。

二、实验题
1.排序题。（nlogn排序算法任意一个：归并排序）

void Merge(SqList L,int start,int mid,int end){
    start--;mid--;end--;
    ElemType* Lc = L.data + start;
    //准备La
    int La_length = mid - start + 1;
    ElemType* La = (ElemType*) malloc(La_length * sizeof(ElemType));
    int c;
    for(c = 0;c<La_length;c++){
        La[i] = Lc[i];
    }
    //准备Lb
    int Lb_length = end - mid;
    ElemType* Lb = Lc + La_length;
    //归并
    int i = 0,j = 0,k = 0;
    while(i<La_length && j <Lb_length){
        if(La[i] <= Lb[j])
            Lc[k++] = La[i++];
        else
            Lc[k++] = Lb[j++];
    }
    while(i<La_length)
        Lc[k++] = La[i++];
    while(j<Lb_length)
        Lc[k++] = Lb[j++];
    free(La);
}

（1）二叉树（前中后序遍历）

void Traverse_PreOrder(BinTree T){
 if(T!=NULL){
     printf("%c",T->data);         //先访问根节点
     Traverse_PreOrder(T->lchild); //遍历左子树
     Traverse_PreOrder(T->rchild); //遍历右子树
 }
}
void Traverse_InOrder(BinTree T){
 if(T!=NULL){
     Traverse_InOrder(T->lchild);//先中序遍历左子树
     printf("%c",T->data); //再访问根节点
     Traverse_InOrder(T->rchild); //遍历右子树
 }
}
void Traverse_PostOrder(BinTree T){
 if(T!=NULL){
     Traverse_PostOrder(T->lchild); //先后序遍历左子树
     Traverse_PostOrder(T->rchild); //后序遍历右子树
     printf("%c",T->data);  //访问根节点
 }
}

（2）二叉搜索树的搜索、插入
插入：

bool BST_Insert(BinTree *T,TElemType e){
    BinTree *pos = BST_search2(T,e);
    if(*pos==NULL){
        *pos=(BinTree) calloc(1,sizeof(BinNode));
        (*pos)->data = e;
        return true;
    }else
        return false;
}

搜索：

BinTree* BST_Search2(BinTree *T,TElemType e){
    if((T)==NULL || e==(T)->data)
        return T; //查找结束
    if(e<(*T)->data) //在左子树中继续查找
        return BST_Search2(&(*T)-> lchild,e);
    else
        return BST_Search2(&(*T)->rchild,e); //在右子树中继续查找
}

3.
（1）顺序表的插入删除

//插入
bool Insert(SqList *L,int i,ElemType e){
    if(i>=1&&i<=L->length+1&&(IsFull(*L)?Expand(L):true)){
            int k;
        for(k = L->length;k>=i;k--){
            L->data[k] = L->data[k-1];}
        L->data[i-1] = e;
        L->length ++; //表长加1
        return true;
    }else return false;
}
//删除
bool Delete(SqList *L,int i,ElemType *e){
    if(i<1 || i> L->length) return false; //i值不合法
    *e = L->data[i-1];
    for(;i<L->length;i++){
        L->data[i-1] = L->data[i];
    }
    L->length--; //表长减1
    return true;
}

（2）链表的出入

bool Insert(LinkList L,int i,ElemType e){
    LNode* p;//找到前驱p
    if((p=GetPtr(L,i-1))!=NULL){
        LNode* q = (LNode*) malloc(sizeof(LNode)); //生成新的结点
        q->data = e; //将e插入L中
        q->next = p->next;//q的后继指向p的后继
        p->next = q;//p的后继指向q
        return true;
    }
    return false;
}
bool Delete(LinkList L,int i,ElemType e){
    LNode* p; //找到前驱p
    if((p=GetPtr(L,i-1))!=NULL&&p->next!=NULL){ //p的后继不能为0
        LNode* q = p->next; //删除并释放结点
        p->next = q->next; //让p的后继指向q的后继
        *e = q->data; //把q的内容给e
        free(q); //释放q
        return true;
    }
    return false;
}

（3）栈的出栈入栈

bool Push(SqStack *S,ElemType e){
    if(S->top - S->base >= S->size){ //判断栈满
        Expend(S);
    }
    *((S->top)++) = e;//从栈顶进入 top加1
    return true;
}
bool Pop(SqStack *S,ElemType *e){
    if(S->top == S->base) //判断栈空
        return false;
    *e = *(--S->top); //从栈顶出 top减1
    return true;
}

（4）队列的出队入队

bool EnQueue(LinkQueue *Q,ElemType e){
    QueuePtr p = (QueuePtr) malloc(sizeof(QNode)); /创建结点/
    if(p!=NULL)
        return false;
    p->data = e; 
    p->next = NULL;
    Q->rear->next = p; /* 让新节点挂在队尾  */
    Q->rear = p; /* 队尾指向P节点  */
    return true;
}
bool DeQueue(LinkQueue &Q,ElemType *e){
    QueuePtr p;
    if(Q->front == Q->rear) /*队列为空*/
        return false;
    p = Q->front->next; 
    e = p->data; /*保存p的值*/
    Q->front->next = p->next; /*把头结点的next指向删除元素的下一个结点地址*/
    if(Q->rear == p)/*如果删除的是队尾*/
        Q->rear = Q->front;/*删除该结点后链队列为空，rear和front同时指向头结点*/
    free(p);
    return true;
}