avatar

数据结构

01 链表

1、结点(node):数据元素的存储映像。由数据域和指针域两部分组成。

  • 数据域:存储元素数值数据
  • 指针域:存储直接后继结点的存储位置

2、链表:n个结点由指针链组成的一个链表

  • 头指针:是指向链表中第一个结点的指针

  • 首元结点:是链表中存储第一个数据元素$ a_1 $的结点

  • 头结点:是在链表的首元结点之前附设的一个结点

1.1 单链表

结点只有一个指针域的链表,称为单链表或线性链表

单链表有两种形式,一种是带头结点的单链表,一种是不带头结点的单链表


1、不带头结点
头指针(head)直接存放第一个元素的地址

2、带头结点
头指针(head)指向头结点,头结点的指针域再来存放首元结点的位置

带头结点的作用:

  • 便于首元结点的处理:首元结点的地址保存在头结点的指针域中,所以在链表的第一个位置上的操作和其他位置一致,无须进行特殊处理;
  • 便于空表和飞控表的统一处理:无论链表是否为空,头指针dou’shi指向头结点的非空指针,因此空表和非空表的也就统一了。

带头结点的单链表

单链表的存储结构

1
2
3
4
typedef struct Lnode{
ElemType data; // 数据域
struct Lnode *next; // 结构域
}Lnode, *LinkList // LinkList为指向结构体Lnode的指针类型

定义链表和定义结点指针p

1
2
3
4
5
//定义链表
LinkList L;
//定义结点指针p
LinkList p;//不常用
Lnode *p;//常用

1.1.1 单链表的初始化

1
2
3
4
5
6
7
8
Sratus lintList_L(LinkList &L){
//C++
L = new LNode;
//C
L = (LinkList)malloc(sizeof(Lnode))

L->next = NULL;
}

1.1.2 单链表的基本操作

1、判断链表是否为空

1
2
3
4
bool isListNull(LinkList L){
if(L->next == NULL)return true;
else return false;
}

2、单链表的销毁
1
2
3
4
5
6
7
8
9
Status DestroyList(LinkList &L){
Lnode *p; // 或LinkList p;
while(L){
p = L;
L = L->next;
delete p;
//C: free p;
}
}

3、清空单链表
1
2
3
4
5
6
7
8
9
10
Status ClearList(LinkList &L){
Lnode *p, *q;
p = L->next;
while(p){
q = p->next;
free p;
p = q;
}
L->next = NULL;
}

4、求链表的表长

从首元结点开始,依次计数所有结点

1
2
3
4
5
6
7
8
9
int ListLength(LinkList L){
LinkList p;
p = L->next;
i = 0;
while(p){
i++;
p = p->next;
}
}

1.1.3 单链表的重要操作

  • 取值:取单链表中第i个元素的内容
  • 查找:
    • 按值查找:根据指定的数据获取数据所在的位置(地址)
    • 按值查找:根据指定的数据获取数据所在的位置序号
  • 插入:在第i个结点前插入新节点
  • 删除:删除第i个结点
  • 单链表的建立
    • 头插法
    • 尾插法

取值

1
2
3
4
5
6
7
8
9
10
11
12
Status GetElem_L(LinkList L, int i, ElemType &e){
p = L->next;
int j = 1;
while(p && j < i){ // 向后扫描,直到p指向第i个元素或p为空
p = p->next;
j++;
}
if(!p || j > i){
return ERROR;
}
return p->data;
}

查找

1、返回地址

1
2
3
4
5
6
7
Lnode *LocateElem_L(LinkList L, Elemtype e){
p = L->next;
while(p->data != e && p){
p = p->next;
}
return p;
}

2、返回位置序号

1
2
3
4
5
6
7
8
9
10
11
12
int LocateELem_L(LinkList L, Elemtype e){
p = L->next;
int j = 1;
while(p->data != e && p){
p = p->next;
j++;
}
if(p)
return j;
else
return 0;
}

插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Status ListInset_L(LinkList &L, int i, ElemType e){
Lnode *p = L->next;
j = 1;
while(p && j < i - 1){
p = p->next;
j++;
}
if(!p || j > i-1)return ERROR;
if(p){
Lnode *s = (LinkList)malloc(sizeof(Lnode));
s->data = e;
s->next = p->next;
p->next = s;
}
}

删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Status ListDelete_L(LinkList &L, int i, ElemType &e){
Lnode *p = L->next;
int i, j = 1;
Lnode *q = (LinkList)malloc(sizeof(Lnode));
while(p->next && i < i-1){
p = p->next;
j++;
}
if(!(p->next) || j > i-1)return ERROR;
q = p->next;
e = q->data;
p->next = (p->next)->next; // 或p->next = q->next;
free q;
}

单链表的建立

1、头插法

1
2
3
4
5
6
7
8
9
10
void CreatList_H(LinkList &L, int n){
L = (LinkList)malloc(sizeof(Lnode));
L->next = NULL;
for(i = 0; i < n; i++){
Node *p = (LinkList)malloc(sizeof(Lnode));
scanf("%d", &(p->data));
p->next = L->next;
L->next = p;
}
}

2、尾插法

1
2
3
4
5
6
7
8
9
10
11
12
13
void CreateList_R(LinkList &L, int n){
L = (LinkList)malloc(sizeof(Lnode));
L->next = NULL;
Lnode *r = L;
int i;
for(i = 0; i < n; i++){
Lnode *p = (LinkList)malloc(sizeof(Lnode));
scanf("%d", &(p->data));
p->next = NULL;
r->next = p;
r = p;
}
}

单链表翻转

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
#include <stdio.h>
#include <stdlib.h>

typedef struct Lnode {
int data;
struct Lnode* next;
}Lnode, * LinkList;

void CreatList_R(LinkList L, int n) {
L->next = NULL;
Lnode* r = L;
int i;
for (i = 0; i < n; i++) {
Lnode* p = (LinkList)malloc(sizeof(Lnode));
scanf("%d", &(p->data));
p->next = NULL;
r->next = p;
r = p;
}
}

void PrintList(LinkList L) {
Lnode* p = L->next;
while (p) {
printf("%d ", p->data);
p = p->next;
}
return;
}

void ReverseList(Lnode* L) {
if (L == NULL || L->next == NULL || L->next->next == NULL)return;
Lnode* pre = L->next->next;
L->next->next = NULL;
Lnode* temp;
while (pre) {
temp = pre->next;
pre->next = L->next;
L->next = pre;
pre = temp;
}
return;
}

int main()
{
int n = 0;
scanf("%d", &n);
LinkList La = (LinkList)malloc(sizeof(Lnode));
CreatList_R(La, n);
ReverseList(La);
PrintList(La);
return 0;
}

双链表

结点有两个指针域的链表,称为双链表

循环链表

首尾相接的链表称为循环链表

02 栈和队列

  • 栈:后进先出,先进后出
  • 队列:后进后出,先进先出

1.1 栈的定义和特点

栈(stack)是一个特殊性线性表,是限定仅在一端进行插入和删除的操作

  • 栈是仅在表尾进行插入和删除操作的线性表
  • 表尾称为栈顶Top,表头称为栈底Base

插入元素到栈顶的操作,称为入栈
从栈顶删除最后一个元素的操作,称为出栈

1.2 栈的表示与实现

顺序栈的表示

1
2
3
4
5
typdef struct{
SElemType *base; // 栈底指针
SElemType *top // 栈顶指针
int stacksize; // 栈可用最大容量
}SqStack;

1.2.1 顺序栈的初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
define MAXSIZE 100;
typdef struct{
SElemType *base; // 栈底指针
SElemType *top // 栈顶指针
int stacksize; // 栈可用最大容量
}SqStack;

Status InitStack(SqStack &S){
S.base = (SElemType*)malloc(MAXSIZE*sizeof(SElemType));
if(!S.base)exit(OVERFLOW);
S.top = S.base;
S.stacksize = MAXSIZE;
return;
}

1.2.2 顺序栈的基本操作

1.2.2.1 顺序栈判断栈是否为空

1
2
3
4
Status StackEmpty(SqStack S){
if(S.top == S.base)return true;
else return false;
}

1.2.2.2 顺序栈的长度

1
2
3
int StackLength(SqStack S){
return S.top-S.base;
}

1.2.2.3 清空顺序栈

1
2
3
Status ClearStack(Sqtack& S){
if(S.base)S.top == S.base;
}

1.2.2.4 销毁顺序栈

1
2
3
4
5
6
7
8
Status DestroyStack(SqStack& S){
if(S.base){
free S.base;
S.stacksize = 0;
S.base = S.top = NULL;
}
return;
}

1.2.3 顺序栈的重要操作

1.2.3.1 顺序栈的入栈

1
2
3
4
5
6
7
Status Push(SqStack& S, SElemType e){
if(S.top-S.base==S.stacksize){
return;
}
*S.top = e;
S.top++;
}

1.2.3.2 顺序栈的出栈

1
2
3
4
5
Status Pop(SqStack& S, SElemType& e){
if(S.top==S.base)return;
S.top--; // --S.top
e = *S.top; // e = *--S.top;
}

1.2 队列的定义和特点

队列(queue)是一种先进先出的线性表,再一端(表尾)插入,再另一端(表头)删除

文章作者: 安河桥北以北
文章链接: http://chenai007.github.io/2020/10/12/C++/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Ash's blog

评论