[TOC]

数据结构

image-20240415083710397

顺序表

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
58
59
60
61
62
63
64
#include <stdio.h>
#include <stdlib.h>
#define MaxSize 10 // 定义最大长度

typedef struct
{
   int data[MaxSize]; // 使用静态的数组存放数据元素
   int length;        // 顺序表的当前长度
} SqList;

// 在顺序表i位置插入e
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 true;
}

// 初始化顺序表
void InitList(SqList *&L)
{
   L = (SqList *)malloc(sizeof(SqList));
   L->length = 0; // 顺序表初始长度为0
}
// 添加元素
void AddList(SqList *L)
{
   int i = 0;
   while (i <= 5)
   {
      L->length++;
      L->data[i] = i;
      
      i++;
   }
}
// 打印元素
void printList(SqList *L)
{
   for (int i = 0; i < L->length; i++)
   {
      printf("%d", L->data[i]);
   }
}

int main()
{
   SqList *L;   // 声明一个顺序表
   InitList(L); // 初始化顺序表

   AddList(L);//添加元素

   ListInsert(L, 3, 3); // 在指定位置插入3

   printList(L);//打印元素
   return 0;
}

单链表

两种实现方式：

  1. 带头结点，写代码更方便。头结点不存储数据，头结点指向的下一个结点才存放实际数据。
  2. 不带头结点，麻烦。对第一个数据结点与后续数据结点的处理需要用不同的代码逻辑，对空表和非空表的处理需要用不同的代码逻辑。
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <stdio.h>
#include <stdlib.h>
#define ElemType int
// 结构体
typedef struct LNode
{
    int data;
    struct LNode *next;
} LNode;

// 初始化单链表
void InitList(LNode *&L)
{
    L = (LNode *)malloc(sizeof(LNode));
    L->next = NULL; // 创建头结点，并且将next指向null
}
// 输出单链表
void DispList(LNode *L)
{
    LNode *p = L->next;
    while (p != NULL)
    {
        printf("%d", p->data);
        p = p->next;
    }
    printf("\n");
}

// 判断单链表是否为空
bool ListEmpty(LNode *L)
{
    return (L->next == NULL);
}
// 求单链表的长度
int ListLength(LNode *L)
{
    int n = 0;
    LNode *p = L;
    while (p->next != NULL)
    {
        n++;
        p = p->next;
    }
    return n;
}
// 向单链表中添加元素
void AddList(LNode *&L)
{
    LNode *p,*s;
    p=L;
    
    for (int i = 0; i < 10; i++)
    {
       s = (LNode *)malloc(sizeof(LNode));
       s->data=i;
       p->next=s;
       p=p->next;
    }
    p->next=NULL;
    
}
// 主函数
int main()
{
    LNode *L;
    InitList(L);
    AddList(L);
    DispList(L);
    return 0;
}

image-20240416082322478

单链表尾插法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 向单链表中添加元素
void AddList(LNode *&L)
{
    LNode *p,*s;
    p=L;
    
    for (int i = 0; i < 10; i++)
    {
       s = (LNode *)malloc(sizeof(LNode));
       s->data=i;
       p->next=s;
       p=p->next;
    }
    p->next=NULL;
    
}

单链表头插法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void AddList(LNode *&L)
{
    LNode *p,*s;
    p=L;
    
    for (int i = 0; i < 10; i++)
    {
       s = (LNode *)malloc(sizeof(LNode));
       s->data=i;
       s->next=p->next;
       p->next=s;
    }
    
}

双链表

image-20240416083950226

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <stdio.h>
#include <stdlib.h>
#define ElemType int
// 结构体
typedef struct DNode
{                        // 定义双链表结点类型
    ElemType data;       // 数据域
    struct DNode *prior; // 前驱指针
    struct DNode *next;  // 后继指针
} DNode;

// 初始化双链表
void InitList(DNode *&L)
{
    L = (DNode *)malloc(sizeof(DNode));
    L->next = NULL;  // 将next指向null
    L->prior = NULL; // 将prior指向null
}

// 判断双链表是否为空
bool Empty(DNode *L)
{
    if (L->next == NULL)
        return true;
    else
        return false;
}

// 输出单链表
void DispList(DNode *L)
{
    DNode *p = L->next;
    while (p != NULL)
    {
        printf("%d", p->data);
        p = p->next;
    }
    printf("\n");
}

// 判断单链表是否为空
bool ListEmpty(DNode *L)
{
    return (L->next == NULL);
}
// 向单链表中添加元素（尾插法）
void AddList1(DNode *&L)
{
    DNode *p, *s;
    p = L;

    for (int i = 0; i < 10; i++)
    {
        s = (DNode *)malloc(sizeof(DNode));
        s->data = i;

        s->prior = p;
        p->next = s;
        p = p->next;
    }
    p->next = NULL;
}
// 向单链表中添加元素（头插法）
void AddList(DNode *&L)
{
    DNode *p, *s;
    p = L;

    for (int i = 0; i < 10; i++)
    {
        s = (DNode *)malloc(sizeof(DNode));
        s->data = i;

        s->prior=p;
        s->next=p->next;
        p->next=s;
    }
}
// 主函数
int main()
{
    DNode *L;
    InitList(L);
    AddList(L);
    DispList(L);
    return 0;
}

栈

栈的基本操作

  1. InitStack(&S)：初始化栈。构造一个空栈 S，分配内存空间。
  2. DestroyStack(&S)：销毁栈。销毁并释放栈 S 所占用的内存空间。
  3. Push(&S, x)：进栈。若栈 S 未满，则将 x 加入使其成为新的栈顶元素。
  4. Pop(&S, &x)：出栈。若栈 S 非空，则弹出（删除）栈顶元素，并用 x 返回。
  5. GetTop(S, &x)：读取栈顶元素。若栈 S 非空，则用 x 返回栈顶元素。
  6. 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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <stdio.h>
#include <stdlib.h>
#define ElemType int
#define MaxSize 10
// 结构体
typedef struct
{
    ElemType data[10]; // 静态数组存放栈中元素
    int top;           // 栈顶元素
} SqStack;

// 初始化栈
void InitList(SqStack *&L)
{
    L = (SqStack *)malloc(sizeof(SqStack));
    L->top = -1;
}

// 判断栈是否为空
bool StackEmpty(SqStack *S)
{
    if (S->top == -1)
        return true;
    else
        return false;
}
// 新元素进栈
void push(SqStack *S)
{ // 判断栈是否已满
    if (S->top == MaxSize - 1)
    {
        printf("栈满");
    }
    else
    {
        
        for (int i = 0; i < MaxSize-1; i++)
        {
            S->top++;
            S->data[S->top] = i;
        }
        
        
    }
}
// 出栈
bool Pop(SqStack *S,int x)
{ // 判断栈是否为空
    if (S->top == -1)
    {
        printf("栈空");
    }else{
        printf("出栈了：");
        for (int i = 0; i < x; i++)
        {
            printf("%d ",S->data[S->top]);
            S->top--;
        }
        
    }
}
//打印栈内元素

// 主函数
int main()
{
    SqStack *s;
    InitList(s);
    push(s);
    //出栈2次
    Pop(s,2);
    return 0;
}

队列

image-20240416104244262

队列的基本操作

  1. InitQueue(&Q)：初始化队列。构造一个空队列 Q。
  2. DestroyQueue(&Q)：销毁队列。销毁并释放队列 Q 所占用的内存空间。
  3. EnQueue(&Q, x)：入队。若队列 Q 未满，将 x 加入，使之成为新的队尾。
  4. DeQueue(&Q, &x)：出队。若队列 Q 非空，删除队头元素，并用 x 返回。
  5. GetHead(Q,&x)：读队头元素。若队列 Q 非空，则将队头元素赋值给 x。
  6. QueueEmpty(Q)：判空。若队列 Q 为空，则返回 true。
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
58
59
#include <stdio.h>
#include <stdlib.h>
#define ElemType int
#define MaxSize 10
// 结构体
typedef struct
{
    ElemType data[MaxSize]; // 用静态数组存放队列元素
    int front, rear;        // 队头指针和队尾指针
} SqQueue;
// 初始化
void InitQueue(SqQueue *&q)
{
    q = (SqQueue *)malloc(sizeof(SqQueue));
    q->front = q->rear = -1;
}
// 入栈
void EnQueue(SqQueue *q)
{
    if (q->rear == MaxSize - 1)
    {
        printf("栈满");
    }
    else
    {
        for (int i = 0; i < MaxSize - 1; i++)
        {
            q->rear++;
            q->data[q->rear] = i;
        }
    }
}
// 出队
void DeQueue(SqQueue *q, int x)
{
    if (q->front == q->rear)
    {
        printf("队空");
    }
    else
    {
        for (int i = 0; i < x; i++)
        {
            q->front++;
            printf("%d",q->data[i]);
        }
    }
}
// 主函数
int main()
{
    SqQueue *q;
    InitQueue(q);
    EnQueue(q);
    // 出队2次
    DeQueue(q, 2);
    return 0;
}

串

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。