AllinToyou

这个屌丝很懒，什么也没留下！

热门标签

C++数据结构

作者：AllinToyou | 2024-04-15 01:12:45

踩

c++数据结构

（参考严蔚敏的数据结构）数据结构主要包含表、栈和队列、串、数组和广义表、树和二叉树以及图等结构。

一、线性表

由n个数据特性相同的元素构成的有限序列称为线性表

（一）顺序表

1、概念

用一组地址连续的存储单元依次存储线性表的数据元素，这种存储结构的线性表为顺序表；

2、基本术语

起始地址（基地址）：线性表第一个元素存储位置；

顺序存储结构：随机存取；

3、操作函数

初始化

InitList(Sqlist &L)；


Status InitList(Sqlist &L)
{
    //构造一个空的顺序表
    L.elem = new ElemType[MAXSIZE];
    if(!L.elem)exit(OVERFLOW)
    L.length=0;
    return OK;
}

取值

GetElem（Sqlist L,int i,ElemType &e）；


status GetElem（Sqlist L,int i,ElemType &e）
{
    if（i<1 || i>L.length）return ERROR;
    e=L.elem[i-1];
    return OK
}

查找

LocateElem(SqList L,ElemType e)


int LocateElem(SqList L,ElemType e)
{
    for(i = 0;i<L.lengeth;i++)
        if(L.elem[i]==e)return i=1;
    return 0;
}

插入

ListInsert(SqList &L,int i,ElemType e)


Statue ListInsert(SqList &L,int i,ElemType e)
{
//在顺序表L中第i个位置插入新元素e，i的合法值范围是1<=i<<L.length+1
    if((i<1)||(i>L.length+1))return ERROR;
    if(L.length == MAXSIZE)return ERROR;
 
    for(int j=L.length-1;j>=i-1;j--)
        L.elem[j+1] = L.elem[j];//将i之后的位置全部后移一位
    L.elem[i-1]=e;//将新元素插入到第i个位置
    ++L.length;//总表长加一
    return OK;
}

删除

ListDelete(SqList &L,int i)


Statue ListDelete(SqList &L,int i)
{
//在顺序表L中第i个位置删除元素e，i的合法值范围是1<=i<<L.length
    if((i<1)||(i>L.length))return ERROR;
 
    for(int j=i;j<L.length;j++)
        L.elem[j-1] = L.elem[j];//将i之后的位置全部前移一位
    L.elem[i-1]=e;//将新元素插入到第i个位置
    --L.length;//总表长减一
    return OK;
}

（二）链表

1、概念

一种链式存储的线性表，用一组地址任意的存储单元存放线性表的数据元素，称为存储单元为一个节点

2、基本术语

节点：链表是由一系列节点（Node）通过指针连接而成；

数据域：存储数据元素的域；

指针域：存储直接后继存储位置的域；

首元节点：链表中存储的第一个数据元素a1的节点；

头结点：在首元节点之前附设的一个节点；

头指针：指向链表中第一个节点的指针，如果有头结点，则指向头结点，如没有头结点，指向的是首元节点。

单链表：非随机存取的顺序存取结构；

循环链表：表中最后一个节点指针域指向头结点；

双向链表：两个指针域，一个指向直接后继，一个指向直接前驱。

3、操作函数

初始化

Status InitList(LinkList &L)；


Status InitList(LinkList &L)
{
    //构造一个空链表
    L=new LNose;    //生成新节点作为头结点，用头指针L指向头结点
    L->next = NULL;//头结点指针域置空
    return OK;
}

取值

Status GetElem(LinkList L,int i,ElemType &e)；


Status GetElem(LinkList L,int i,ElemType &e)
{
//在带头节点的单链表L中根序号i获取元素的值，用e返回L中第i个数据元素的值
    p = L->next;j=1;        //初始化，p指向首元节点，计数器j初值赋1
    while(p&&j<i)            //顺链表向后扫描，直到p为空或者p指向第i个元素
    {
        p = p->next;        //p指向下一个节点
        ++j;                //计数器j加一
}
    if(!p || j>i);           //i值不合理，i>n或者i<=0
    e = p->data;            //找到第i个节点，获取第i个节点的数据域
    return OK;
}

查找

LNode *LocateElem(LinkList L,ElemType e)


LNode *LocateElem(LinkList L,ElemType e)
{
//在带头节点的单链表L中寻找数值为e的元素
    p = L->next;        //初始化，p指向首元节点
    while(p&&p->data!=e)            //顺链表向后扫描，直到p为空或者p指向节点的数据域等于e
    {
        p = p->next;        //p指向下一个节点
    }
    return p;//查找成功返回e节点地址p，查找失败p为NULL
}

插入

Status ListInsert(LinkList &L,int i,ElemType e)

过程：

1.查找节点ai-1，并由指针p指向该节点；

2.生成一个新节点*s；

3.将新节点*s的数据域置为e；

4.将新节点*s的指针域指向节点ai；

5.将节点*p的指针域指向新节点*s。

实现：


Status ListInsert(LinkList &L,int i,ElemType e)
{
//在带头节点的单链表L中第i个位置插入值为e的新节点
    p = L;j=0;        //初始化
    while(p&&（j<i-1）)            //顺链表向后扫描，直到p为空或者p指向第i-1个节点
    {
        p = p->next;        //p指向下一个节点
        ++j;                //计数器j加一
}
    if(!p || j>i-1) return ERROR;           //i值不合理，i>n+1或者i<=0
    s=new LNode;            //生成一个新节点
    s->data = e;            //将节点*s的数据域置为e
    s->next = p->next;        //将节点*s的指针域指向节点ai
    p->next = s;            //将节点*p的指针域指向节点*s
    return OK;
}

删除

过程：

1.查找节点ai-1并由指针p指向该节点

2.临时保存待删除节点ai的地址在q，以备释放

3.将节点*p的指针域指向ai的直接后继节点

4.释放节点ai的空间


Status ListDelete(LinkList &L,int i)
{
//在带头节点的单链表L中,删除第i个元素
    p = L;j=0;        //初始化
    while((p->next)&&（j<i-1）)            //查找第i-1个节点，p指向该节点
    {
        p = p->next;        //p指向下一个节点
        ++j;                //计数器j加一
}
    if(!(p->next) || j>i-1) return ERROR;           //i>n或者i<1时，删除位置不合理
    q=p->next;                //临时保存被删除节点的地址以备释放
    p->next = q->next;        //改变删除节点前驱的指针域
    delete q;                //释放删除节点的空间
    return OK;
}

创建单链表

前插法创建：

1.创建只有头结点的空链表；

2.根据待创建链表包括的元素个数执行n次一下操作：生成一个新节点*p；输入元素值赋给新节点*p的数据域；将新节点*p插入到头结点之后。


void CreateList_H(LinkList &L,int n)
{//逆位序输入n个元素的值，建立带表头节点的单链表
    L=new LNode;
    L->next=NULL;        //先建立一个带头结点的空链表
    for(int i = 0;i<n;i++)
    {
        p = new LNode;        //生成新节点*p
        cin >> p->data;        //输入元素值赋给新节点*p指针域
        p->next = L->next;L->next = p;//将新节点*p插入到头结点之后
    }
}

后插法创建：

1.创建只有头结点的空链表；

2.尾指针r初始化，指向头结点。

2.根据待创建链表包括的元素个数执行n次一下操作：生成一个新节点*p；输入元素值赋给新节点*p的数据域；将新节点*p插入到尾结点*r之后；尾指针r指向新的尾节点*p。


void CreateList_R(LinkList &L,int n)
{//正位序输入n个元素的值，建立带表头节点的单链表L
    L=new LNode;
    L->next=NULL;        //先建立一个带头结点的空链表
    r = L;                //尾指针r指向头结点，保证每次都是尾节点
    for(int i = 0;i<n;i++)
    {
        p = new LNode;        //生成新节点*p
        cin >> p->data;        //输入元素值赋给新节点*p指针域
        p->next = NULL;r->next = p;//将新节点*p插入到头结点之后
        r=p;
    }
}

（三）顺序表和链表的比较

顺序表：

表类型	优点	缺点	适用场景
顺序表	存取速度高效，通过下标来直接存取	插入和删除比较慢，不可以实时增长长度	适用于需要大量访问元素的，而增加/删除元素较少的程序
链表	插入和删除速度快，保留原有的物理顺序	查找元素需要遍历，因此不支持随机查找	适用于需要频繁进行增加/删除元素，而查找元素较少的程序

二、栈和队列

（一）栈

1、概念

栈是一种后进先出（Last In, First Out, LIFO）的数据结构，类似于一叠盘子。

2、基本术语

栈顶（Top）: 最后一个加入的元素。
栈底（Bottom）: 最先加入的元素。

3、操作函数

push: 添加一个新元素到栈顶。
pop: 移除栈顶元素并返回它。
peek: 返回栈顶元素但不移除。
isEmpty: 检查栈是否为空。

代码示例（Python）:


class Stack:
    def __init__(self):
        self.items = []
 
    def push(self, item):
        self.items.append(item)
 
    def pop(self):
        if not self.is_empty():
            return self.items.pop()
 
    def peek(self):
        if not self.is_empty():
            return self.items[-1]
 
    def is_empty(self):
        return not self.items

（二）队列

1、概念

队列是一种先进先出（First In, First Out, FIFO）的数据结构，类似于排队。

2、基本术语

队首（Front）: 队列的第一个元素。
队尾（Rear/Back）: 队列的最后一个元素。

3、操作函数

enqueue: 在队尾添加一个新元素。
dequeue: 移除队首元素并返回它。
front: 获取队首元素但不移除。
isEmpty: 检查队列是否为空。

代码示例（Python）:


class Queue:
    def __init__(self):
        self.items = []
 
    def enqueue(self, item):
        self.items.insert(, item)
 
    def dequeue(self):
        if not self.is_empty():
            return self.items.pop()
 
    def front(self):
        if not self.is_empty():
            return self.items[-1]
 
    def is_empty(self):
        return not self.items

三、串、数组和广义表

（一）串

1、概念

由字符组成的有序序列，用于表示文本数据。

2、基本术语

串长、子串、空串。

3、操作函数

concat(str1, str2)：串连接。
substring(str, start, length)：返回子串。
indexOf(sub)：返回子串在主串中的位置。

（二）数组

1、概念

由固定大小的相同类型元素组成的有序集合，元素可以通过索引访问。

2、基本术语

元素、索引、维度。

3、操作函数

access(i)：访问索引为i的元素。
update(i, value)：更新索引为i的元素值。
length()：返回数组长度。

（三）广义表

1、概念

数据结构的一种，可以包含它是一个广义表，类似于LISP语言的列表（list）结构。

2、基本术语

表头、表尾。

3、操作函数

head(list)：返回表头。
tail(list)：返回表尾。
isEmpty(list)：检查表是否为空。

四、树和二叉树

（一）树

1、概念

一种分层的非线性数据结构，由节点组成，每个节点有零个或多个子节点。

2、基本术语

根节点（root）、子节点（child）、父节点（parent）、叶节点（leaf）、深度（depth）等

3、操作函数

addChild(node, child)：给节点添加子节点。
removeChild(node, child)：移除节点的子节点。
traverse()：遍历树。

（二）二叉树

1、概念

每个节点最多有两个子节点的树，称为左子节点和右子节点

2、基本术语

左子树、右子树。

3、操作函数

同树的操作函数，但二叉树特有的遍历方式包括前序遍历、中序遍历和后序遍历。

五、图

（一）图

1、概念

由节点（也称顶点或顶点）以及连接这些节点的边组成的集合。

2、基本术语

顶点（Vertex）
边（Edge）
权（Weight）（某些图中的边带有权重）
邻接（Adjacency）
路径（Path）

3、操作函数

添加顶点
添加边
找到顶点间的路径
遍历（深度优先搜索，广度优先搜索等）

代码示例（Python）:


class Graph:
    def __init__(self):
        self.vertices = {}
    
    def add_vertex(self, key):
        if key not in self.vertices:
            self.vertices[key] = []
    
    def add_edge(self, u, v):
        if u in self.vertices and v in self.vertices:
            self.vertices[u].append(v)
            self.vertices[v].append(u)  # 若为无向图，双向添加
    
    def find_path(self, start_vertex, end_vertex, path=[]):
        path = path + [start_vertex]
        if start_vertex == end_vertex:
            return path
        if start_vertex not in self.vertices:
            return None
        for vertex in self.vertices[start_vertex]:
            if vertex not in path:
                extended_path = self.find_path(vertex, end_vertex, path)
                if extended_path: 
                    return extended_path
        return None

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/AllinToyou/article/detail/425051

C++数据结构

一、线性表

（一） 顺序表

1、概念

2、基本术语

3、操作函数

初始化

取值

查找

插入

删除

（二）链表

1、概念

2、基本术语

3、操作函数

初始化

取值

查找

插入

删除

创建单链表

前插法创建：

后插法创建：

（三）顺序表和链表的比较

顺序表：

二、栈和队列

（一）栈

1、概念

2、基本术语

3、操作函数

（二）队列

1、概念

2、基本术语

3、操作函数

三、串、数组和广义表

（一）串

1、概念

2、基本术语

3、操作函数

（二）数组

1、概念

2、基本术语

3、操作函数

（三）广义表

1、概念

2、基本术语

3、操作函数

四、树和二叉树

（一）树

1、概念

2、基本术语

3、操作函数

（二）二叉树

1、概念

2、基本术语

3、操作函数

五、图

（一）图

1、概念

2、基本术语

3、操作函数

代码示例（Python）:

（一）顺序表