第一章 绪论

1.0数据结构在学什么

image-20241108174722732

数据结构在学什么？

1.1数据结构的基本概念

image-20241108174919164

image-20241108175451336

image-20241108175525061

1.2算法和算法评价

image-20241108175701029

image-20241108180051207

image-20241108180158724

image-20241108180432547

第二章 线性表

2.1线性表的定义和基本操作

image-20241108180646358

image-20241108180813550

2.2线性表的顺序表示

image-20241108181153520

image-20241108181556403

image-20241108181804317

2.3顺序表的链式表示

单链表

image-20241108181937655

image-20241108182046854

image-20241108182232557

image-20241108182311322

image-20241108182544821

image-20241108182823312

image-20241108183145884

image-20241108183440275

image-20241108183621669

image-20241108183932454

双链表

image-20241108184320710

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
//定义双链表
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;
}

循环链表

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

循环双链表：表头节点的前驱指向表尾结点；表尾结点的后继指向头结点

静态链表

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

第三章 栈和队列

3.1栈的定义

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

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

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

栈的特点：先进后出

3.2栈的基本操作

InitStack(&S) ： 初始化 栈。构造一个空栈 S ， 分配内存空间 。

DestroyStack(&S) ： 销毁 栈。销毁并 释放 栈 S 所占用的 内存空间 。

Push(&S,x) ： 进栈 ，若栈 S 未满，则将 x 加入使之成为新栈顶。

Pop(&S,&x) ： 出栈 ，若栈 S 非空，则弹出栈顶元素，并用 x 返回。

GetTop(S, &x) ： 读栈顶元素 。若栈 S 非空，则用 x 返回栈顶元素

其他常用操作：

StackEmpty(S) ：判断一个栈 S 是否为空。若 S 为空，则返回 true ，否则返回 false 。

顺序栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//顺序栈的定义
#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;
}

共享栈

1
2
3
4
5
6
7
8
9
10
11
12
13
//定义共享栈
#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;
}

链栈

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