408数据结构笔记整理

第一章 绪论

1、数据结构的基本概念

1.1 数据

数据：是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。

1.2 数据元素、数据项

数据元素：是数据的基本单位，通常作为一个整体进行考虑和处理，一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位。

1.3 数据对象、数据结构、数据结构的三要素

数据对象：具有相同性质的数据元素的集合，是数据的一个子集。

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

数据结构的三要素：

①.逻辑结构：

a.集合结构

b.线性结构——一对一

除了第一个元素，所有元素都有唯一前驱；除了最后一个元素，所有元素都有唯一后继

c.树形结构——一对多

d.图状结构——多对多

②.数据的运算：针对某种逻辑结构，结合实际需求，定义基本运算

运算的定义是针对逻辑结构的，运算的实现是针对存储结构的。

③.物理结构(存储结构)：四种常见的存储结构：

顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中

链式存储：逻辑上相邻的元素在物理位置上可以不相邻，由指针指向地址

索引存储：在存储元素信息的同时，还建立附加的索引表。索引表中的每项称为索引项。

散列存储：又称哈希(Hash)存储，根据元素的关键字直接计算出该元素的存储地址。

存储结构会影响：存储空间分配的方便程度、对数据运算的速度。

1.4 数据类型、抽象数据类型

数据类型：是一个值的集合和定义在此集合上的一组操作的总称

①.原子类型，其值不可再分的数据类型

②.结构类型。其值可以分解为若干成分(分量)的数据类型。

抽象数据类型(Abstract Data Type, ADT)：是抽象数据组织及与之相关的操作。

2、算法

2.1 概念

算法(Algorithm)：是对特定问题求解步骤的一种描述，是指令的有限序列，其中的每条指令表示一个或多个操作。

算法的特性：

有穷性：算法必须在有穷时间内完成。(算法必须有穷，而程序可以无穷)

确定性：算法中每条指令必须有确切的含义，对于相同的输入，只能得出相同的输出。

可行性：算法中描述的操作的可以通过已经实现的基本运算执行有限次来实现。

输入：0个或多个

输出：一个或多个

好算法的特质：

正确性：正确的解决问题

可读性：能够帮助人们理解

健壮性：输入非法数据时，能适当的做出反应或进行处理。而不会产生莫名其妙的结果

高效性与地存储量需求

2.2算法的时间复杂度

事先预估算法时间开销T(n)与问题规模(n)的关系

加法规则：T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))

多项相加，只保留最高阶的项，且系数变为1

乘法规则：T(n)=T1(n)XT2(n)=O(f(n))XO(g(n))=O(f(n)Xg(n))

多项相乘，都保留

计算时间复杂度：

①.顺序执行的代码只会影响常数项，可忽略。

②.只需挑循环中的一个基本操作分析它的执行次数与n的关系即可。

③.如果有多层嵌套循环，只需关注最深层循环循环了几次。

2.3算法的空间复杂度

分别考虑普通程序与递归程序，计算方法按加法规则与乘法规则

第二章 线性表

1、定义

线性表是具有相同的数据类型的n(n>=0)个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。若用L命名线性表，则其一般表示为：L=(a1,a2,...,ai,ai+1,...,an)

2、基本操作

InitList(&L):初始化表。构造一个空的线性表L，分配内存空间。

DestroyList(&L):销毁操作。销毁线性表，并释放线性表L所占用的内存空间。

ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素e。

ListDelete(&L,i,&e):删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。

LocateElem(L,e):安值查找操作。在表L中查找具有给定关键字值的元素。

GetElem(L,i):按位查找操作。获取表L中第i个位置的元素的值。

Length(L):求表长，返回线性表L的长度，即L中数据元素的个数。

PrintList(L):输出操作，按前后顺序输出线性表L中的所有元素值。

Empty(L):判空操作。若L为空表，则返回true，否则返回false。

3、存储/物理结构

3.1 顺序表(顺序存储)

3.1.1 定义

①.静态分配

#define maxsize 10           //定义最大长度
typedef struct{
    elemtype data[maxsize];  //用静态的“数组”存放数据元素
    int length;              //顺序表的当前长度
}sqlist;                     //顺序表的类型定义（静态分配方式）

②.动态分配

#include <stdlib.h>        //malloc、free函数的头文件
#define initsize 10        //顺序表的初始长度
typedef struct{        
    elemtype *data；       //指示动态分配数组的指针
    int maxsize；          //顺序表的最大容量
    int length；           //顺序表的最大长度
}sqlist；                  //顺序表的类型定义(动态分配方式)
 
 
void initlist(sqlist &L){
    //用malloc函数申请一片连续的存储空间
    L.data=(elemtype *)malloc(initsize*sizeof(elemtyp));
    L.length=0;
    L.maxsize=initsize;
}
 
//增加动态数组的长度
void increasesize(sqlist &L, int len){
    int *p=L.data;
    L.data=(elemtype *)malloc((L.maxsize+len)*sizeof(elemtype));
    for(int i=0;i<L.length;i++){
        L.data[i]=p[i];         //将数据复制到新区域
    }
    L.maxsize=l.maxsize+len;    //顺序表最大长度增加len
    free(p);                    //释放原来的内存空间
}
 
 
int main(){
    sqlist l;       //声明一个顺序表
    initlist(L);    //初始化顺序表
    //...往顺序表中随便插入几个元素...
    increasesize(L,5);
    return 0;
}

 顺序表的特点：

①.随机访问，即可以在O(1)时间内找到第i个元素。

②.存储密度高，每个节点只存储数据元素

③.拓展容量不方便(即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高)

④.插入、删除数据元素不方便

3.1.2 基本操作的实现

①.顺序表的插入与删除

插入操作的时间复杂度：

最坏：O(n);

平均：O(n);

删除操作的时间复杂度：

最坏：O(n);

平均：O(n);

#define maxsize 10     //定义最大长度
typedef struct{
int data[maxsize];     //用静态的“数组”存放数据元素
int length;            //顺序表的当前长度
}sqlist;               //顺序表的类型定义
 
 
//插入操作  listinsert(&L, i, e)
//c插入有问题时，无返回值
void listinsert(sqlist &L, int i, int e){
    for(int j=L.length;j>=i;j--)    //将第i个元素及之后的元素后移
        L.data[j]=L.data[j-1];
    L.data[i-1]=e;                  //在位置i处放入e
    L.length++;                     //长度加1
}
 
//插入有问题的时候有返回值
bool listinsert(sqlist &L, int i, int e){
    if(i<1||i>L.length+1)           //判断i的范围是否有效
        return false;
    if(L.length>=maxsize)           //当前存储空间已满，不能插入
        return false;
    for(int j=l.length;j>=i;j--)    //将第i个元素及之后的元素后移
        L.data[j]=L.data[j-1];
    L.data[i-1]=e;                  //在位置i处放入e
    L.length++;                     //长度加1
    return ture;
}
 
int main(){
sqlist L;           //声明一个顺序表
initlist(L);        //初始化顺序表
//...插入几个元素    
listinsert(L,3,3);  
return 0;
}
 
//删除操作 listdelete(&L,i,&e)
bool listinsert(sqlist &L,int i,int &e){
    if(i<1||i>L.length+1)           //判断i的范围是否有效
        return false;
    e=L.data[i-1];                  //将被删除的元素赋值给e
    for(int j=i;j<L.length;j++)     //将第i个位置后的元素前移
        L.data[j-1]=L.data[j];
    L.length--;                     //线性表长度减1
    return ture;
}
 
int main(){
    sqlist L;                                     //声明一个顺序表
    initlist(L);                                  //初始化顺序表
    //...插入几个元素
    int e= -1;                                    //用变量e把删除掉元素“带回来”
    if(listdelete(L,3,e))
        print("已删除第3个元素，删除元素值为=%d\n",e);
    else
        print("位序i不合法，删除失败\n");
    return 0；
}

②.顺序表的查找

按位查找：时间复杂度O(1)

按值查找：时间复杂度：最坏O(n), 平均O(n)

//GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值。
 
//静态分配
#define MaxSize 10 //定义最大长度
typedef struct{
ElemType data[MaxSize]; //用静态的“数组”存放数据元素
int length;             //顺序表的当前长度
}SqList;                //顺序表的类型定义（静态分配方式）
 
ElemType GetElem(SqList L, int i){
return L.data[i-1];
}
 
//动态分配
#define InitSize 10 //顺序表的初始长度
typedef struct{
ElemType *data;     //指示动态分配数组的指针
int MaxSize;        //顺序表的最大容量
int length;         //顺序表的当前长度
} SeqList;          //顺序表的类型定义（动态分配方式）
 
ElemType GetElem(SeqList L, int i){
return L.data[i-1];
}
 
 
//LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素。
 
#define InitSize 10 //顺序表的初始长度
typedef struct{
ElemType *data;     //指示动态分配数组的指针
int MaxSize;        //顺序表的最大容量
int length;         //顺序表的当前长度
} SeqList;          //顺序表的类型定义（动态分配方式）
 
//在顺序表L中查找第一个元素值等于e的元素，并返回其位序
int LocateElem(SeqList L,ElemType e){
for(int i=0;i<L.length;i++)
if(L.data[i]==e)
return i+1; //数组下标为i的元素值等于e，返回其位序i+1
return 0; //退出循环，说明查找失败
}

3.2 链表(链式存储)

3.2.1 单链表

每个节点除了存放数据元素外，还要存储指向下一个节点的指针

定义：

//定义一个单链表
typedef struct lnode{        //定义单链表节点类型
    elemtype data;           //每个节点存放一个数据元素
    struct lnode *next;      //指针指向下一节点
}lnode,*linklist;
 
//不带头节点
//初始化一个空的单链表
bool initlist(linklist &L){
    L=NULL;                  //空表，暂时还没有任何节点
    return true;
}
 
//带头结点
bool initlist(linklist &L){
    L=(lnode *) malloc(sizeof(lnode));
    if(L==NULL)
        return false
    L->next=NULL;
    return ture;
}
 
viod test(){
    linklist L;              //声明一个指向单链表的指针
    //初始化一个空表
    initlist(L);
    //...后续代码...
}
 
//判断单链表是否为空
bool empty(linklist L){
    if(L==NULL)
        return true;
    else
        return false;
}
或：
bool empty(linklist L){
return (L==NULL);
}

插入：

//按位序插入(带头结点)
bool listinsert(linklist &L,int i, elemtype e){
    if(i<1)
        return false;
    lnode *p;                   //指针p指向当前扫描到的结点
    int j=0;                    //当前p指向的是第几个结点
    p=L;                        //L指向头结点，头结点是第0个结点(不存数据)
    while(p!=NULL && j<i-1){    //循环找到第i-1个结点
        p=p->next;
        j++;
}
    if(p==NULL)                //i值不合法
        return false;
    lnode *s=(lnode *)malloc(sizeof(lnode));
    s->data=e;
    s->next=p->next;
    p->next=s;                //将结点s连到p之后
    return ture;              //插入成功
}
 
 
//不带头节点
bool listinsert(linklist $L,int i, elemtype e){
    if(i<1)
        return false;
    if(i==1){        //插入第一个节点的操作与其他节点的操作不同
        lnode *s = (lnode *)malloc(sizeof(lnode));
        s->data = e;
        s->next = L;
        L = s;        //头指针指向新节点
        return ture;
    }
    lnode *p;                   //指针p指向当前扫描到的结点
    int j=1;                    //当前p指向的是第几个结点
    p=L;                        //L指向头结点，头结点是第0个结点(不存数据)
    while(p!=NULL && j<i-1){    //循环找到第i-1个结点
        p=p->next;
        j++;
}
    if(p==NULL)                //i值不合法
        return false;
    lnode *s=(lnode *)malloc(sizeof(lnode));
    s->data=e;
    s->next=p->next;
    p->next=s;                //将结点s连到p之后
    return ture;              //插入成功
}
 
//后插操作：在p节点之后插入元素e
bool insertnextnode(lnode *p, emlemtype e){
    if(p==NULL)
        return false;
    lnode *s = (lnode *)malloc(sizeof(lnode));
    if(s==NULL)                //内存分配失败
        return false;
    s->data = e;                //用结点s保存数据元素e
    s->next = p->next;
    p->next = s;                //将结点s连接到p之后
    return ture;
}
 
//前插操作：在p结点之前插入元素e
bool insertpriornode(lnode *p, elemtype e){
    if(p==NULL)
        return false;
    lnode *s = (lnode *)malloc(sizeof(lnode));
    if(s==NULL)                //内存分配失败
        return false;
    s->next = p->next;
    s->data = p->data;        //将p中的元素复制到s中
    p->data = e;              //将新元素e代替p原来的元素
    p->next = s;              //将新节点s连接到p之后
    return ture;
}

时间复杂度：带头结点的按位序插入：平均O(n)，前插操作与后插操作：O(1)

删除

//按位序删除（带头结点）
bool listdelete(linklist &L,int i,elemtype &e){
    if(i<1)
        return false;
    lnode *p;                    //指针p指向当前扫描到的结点
    int j=0;                     //当前p指向的是第几个结点
    p = L;                       //L指向头结点，头结点是第0个结点（不存数据）
    while(p != NULL && j<i-1){   //循环找到第i-1个结点
        p=p->next;
        j=j++;
    }
    if(p==NULL)                  //i值不合法
        return false;
    if(p->next == NULL)          //第i-1个结点之后已无其他节点
        return false;
    lnode *q=p->next;            //令q指向被删除的结点
    e = q->data;                 //用e返回被删除元素的值
    p->next=q->next;             //将*q结点从链中“断开”
    free(q);                     //释放q结点的存储空间
    return ture;
}
//最坏、平均时间复杂度：O(n)
//最好时间复杂度：O(1)
 
 
//删除指定结点
bool deletenode(lnode *p){
    if(p==NULL)
        return false;
    lnode *q = p->next;            //令q指向*p的后继结点
    p->data = p->next->data;       //和后继结点交换数据域
    p->next = q->next;             //将*q结点从链中“断开”
    free(q);
    return ture;
}
//该程序的bug：如果指定删除最后一个结点，p->next =NULL,此时程序出错
//所以要删除最后一个结点只能从头查找

查找 

//按位查找，返回第i个元素（带头结点）
lnode * getelem(linklist L, int i)
    if(i<0)
        return false;
    lnode *p;                //指针p指向当前扫描到的结点
    int j=0;                 //当前p指向的是第几个结点
    p = L;                   //L指向头结点，头结点是第0个结点(不存数据)
    while(p!=NULL && j<i){   //循环找到第i个结点
        p=p->next;
        j++;
    }
    return p;
}
//平均时间复杂度:O(n)
//按值查找，找到数据域==e的结点
lnode * locateelem(linklist L,elemtype e){
    lnode *p = L->next;
    //从第一个结点开始查找数据域为e的结点
    while(p != NULL && p->data != e)
        p = p->next;
    return p;                        //找到后返回该结点指针，否则返回NULL
}
 
//时间复杂度：O(n)

求表长

//求表的长度
int length(linklist L){
    int len = 0;        //统计表长
    lnode *p = L;
    while(p->next != NULL){
        p = p->next;
        len++;
    }
    return len;
}

尾插法建立单链表 

头插法建立单链表 

3.2.2 双链表

//定义双链表
typedef sturct dnode{            //定义双链表结点类型
    elemtype data;               //数据域
    struct dnode *prior,*next;   //前驱与后继指针
}dnode, *dlinklist;
 
//初始化双链表
bool initdlinklist(dlinklist &L){
    L = (dnode *)malloc(sizeof(dnode));    //分配一个头结点
    if(L==NULL)                            //内存不足，分配失败
        return false;
    l->prior = NULL;
    L->next = NULL;
    return ture;
}
 
void testdlinklist(){
    //初始化双链表
    dlinklist L;
    initdlinklist(L);
    //后续代码...
 
//判断双链表是否为空(带头结点)
bool empty(dlinklist L){
    if(L->next == NULL)
        return true;
    else
        return false;
}
 
 
//双链表的插入
//在p结点之后插入s结点
bool insertnextdnode(dnode *p, dnode *s){
    if(p==NULL || s==NULL)                //非法参数
        return false;
    s->next=p->next;
    if(p->next !=NULL)                    //如果p结点有后继结点
        p->next->prior=s;
    s->prior=p;
    p->next=s;
    return ture;
}
 
 
//双链表的删除
//删除p结点的后继结点
bool deletenextdnode(dnode *p){
    if(p==NULL)    return false;
    dnode *q = p->next;                    //找到p的后继结点q
    if(q==NULL)    return false;           //p没有后继
    p->next=q->next;
    if(q->next !=NULL)                    //q结点不是最后一个结点
        q->next->prior=p;
    free(q);
    return ture;
}

3.2.3 循环链表

循环单链表：最后一个结点的指针指向第一个结点

循环双链表：表头结点的prior指向表尾结点；表尾结点的next指向头结点

3.2.4 静态链表

//定义静态链表
#define maxsize 10            //静态链表的最大长度
typedef struct node{          //静态链表结构类型的定义
    elemtype data;            //存储数据元
    int next;                 //下一个元素的数组下标素
}slinklist[maxsize],slist;
 

第三章 栈和队列

1.栈的定义

栈：是只允许在一端进行插入或删除操作的线性表

栈顶：允许插入和删除的一方

栈低：不允许插入与删除的一方

栈的特点：先进后出

2.栈的基本操作

//顺序栈的定义
#define maxsize 10                //定义栈中元素的最大个数
typedef struct{
    elemtype data[maxsize];       //静态数组存放栈中元素
    int top;                      //栈顶指针
}sqstack;
 
//初始化栈
void initstack(sqstack &s){
    s.top=-1;                     //初始化栈顶指针
}
 
//判断栈空
bool stackempty(sqstack s){
    if(s.top==-1)                //栈空
        return ture;
    else
        return false;
}
 
//新元素进栈
bool push(sqstack &s, elemtype x){
    if(s.top==maxsize-1)          //栈满，报错
        return false;
    s.top=s.top+1;
    s.data[s.top]=x;
    return ture;
}
 
//出栈操作
bool pop(sqstack &s,elemtype &x){
    if(s.top==-1)                //栈空，报错
        return false;
    x=s.data[s.top--];           //栈顶元素出栈，指针减一
    return ture;
}
 
//读栈顶元素
bool gettop(sqstack s,elemtype &x){
    if(s.top==-1)                  //栈空，报错
        return false;
    x=s.data[s.top];                //x记录栈顶元素
    return ture;
}

//定义共享栈
#define maxsize 10                //定义栈中元素的最大个数
typedef struct{
    elemtype data[maxsize];       //静态数组存放栈中元素
    int top0;                     //0号栈栈顶指针
    int top1;                     //1号栈栈顶指针
}shstack
 
//初始化栈
void initstack(shstack &s){
    s.top0=-1;                    //初始化栈顶指针
    s.top1=maxsize;
}

//链栈的定义
typedef struct linknode{
    elemtype data;                //数据域
    struct linknode *next;        //指针域
} *listack;                       //栈类型定义

//队列的顺序实现
#define maxsize 10                 //定义队列中元素的最大个数
typedef struct{
    elemtype data[maxsize];        //用静态数组存放元素
    int front,rear;                //对头指针和队尾指针
}sqqueue;
 
//初始化队列
void initqueue(sqqueue &Q){
    //初始时 对头、队尾指针指向0
    Q.rear=Q.front=0;
}
 
//判断队列是否为空
bool queueempty(sqqueue Q){
    if(Q.front==Q.rear)            //队空条件
        return ture;
    eles
        return false;
}
 
//入队
bool enqueue(sqqueue &Q,elemtype x){
    if(Q.rear-Q.front==maxsize)          //队列已满
        return false;
    Q.data[Q.rear++]=x;              //将x插入队尾，再将队尾指针后移
    return ture;
}
 
//出队操作