线性数据结构

jer2021 · 2021-01-25 15:45:27 · 个人记录

线性数据结构

数据结构	优点	缺点
数组	插入快	查找慢，删除慢，大小固定只能存储单一元素
有序数组	比无序数组查询快	插入慢，删除慢，大小固定只能存储单一元素
栈	提供后进先出的存储方式	存储其他项慢
队列	提供先进先出的存储方式	存储其他项
链表	插入快，删除快	查找慢
二叉树	如果数是平衡的，则查找，插入，删除快	删除算法复杂
2-3-4树	查找，插入，删除快，树总是平衡的	算法复杂
哈希表	如果关键字已知则存储极快	删除慢，如果不知道关键字存储慢，对储存空间使用不充足
堆	插入，删除快，对最大数据储存快	对其他数据存取慢
图	对现实世界建模	有些算法慢而复杂
红黑树	查找，插入，删除快，树总是平衡的	算法复杂

二叉堆

链表

树状数组

指针

1. 指针变量（int *p) 与普通变量（int a)的关系

p ------ &a //&为取地址运算符
*p ------ a //*为间接运算符
*p=3 ------ a=3

2. 指针变量定义

int *p=NULL;

定义了一个指针p ,p指向一个内存空间，里面存放着一个内存地址。现在赋值为NULL(为0 ，表示特殊的空地址）。

3. 给指针变量p赋值

int a=3;
p=&a

即把a变量的内存地址给了p

*p的值为3 ，p为地址

4. 指针变量初始化

	方法	说明
1	int *p=NULL;	NULL为特殊的地址0 ，叫零指针
2	int *p=&a;	p初始化为变量a的地址
3	int*p=new(int)	申请一个空间给p ，*p内容不确定

5. 指向结构体变量的指针

一个结构体变量的指针就是该变量所占据的内存段的起始地址。可以设一个指针变量，用来指向一个结构体变量，此时，该指针变量的值是结构体变量的起始位置。

使用指针变量访问结构体成员示例

#include <cstdio>
#include <iostream>
using namespace std;
struct student{
    string name;
    int age;
    int fx;
}; 
student x={"xiaoming" ,13 ,100};
student *p;
int main()
{
    p=&x;
    cout << x.name << endl;
    cout << (*p).age << endl;
    cout << p->fx << endl;
}

输出

xiaoming
13
100

--------------------------------
Process exited after 0.05083 seconds with return value 0
请按任意键继续. . .

注：p->age 相当于 x.age。

链表

单链表

1. 单链表结构体定义

struct name{
    (类型）data
    struct name *next;
    //name为结构体名称 ，next指向下一个节点的指针
};

2. 基本操作

初始化

/*
| 头指针L | NULL | 
*/
L=new name;
L->next=NULL;

创建

取值，查找

P=L->next;j=1;
P=P->next;j=2;

插入

删除

相关代码

#include<iostream>
#include<string>
using namespace std;

typedef struct LNode {
    int data; //结点的数据域
    struct LNode *next; //结点的指针域
}LNode, *LinkList; //LinkList为指向结构体LNode的指针类型

void CreateList_R(LinkList &L)//尾插法创建单链表
{
    //输入n个元素的值，建立带表头结点的单链表L
    int n;
    LinkList s, r;
    L=new LNode;
    L->next=NULL; //先建立一个带头结点的空链表
    r=L; //尾指针r指向头结点
    cout <<"请输入元素个数n：" <<endl;
    cin>>n;
    cout <<"尾插法（正序）创建单链表..." <<endl;
    while(n--)
    {
        s=new LNode;//生成新结点
        cin>>s->data; //输入元素值赋给新结点的数据域
        s->next=NULL;
        r->next=s;//将新结点s插入尾结点r之后
        r=s;//r指向新的尾结点s
    }
}

LinkList findmiddle(LinkList L)
{
    LinkList p,q;
    p=L; //p为快指针，初始时指向L
    q=L; //q为慢指针，初始时指向L
    while(p!=NULL&&p->next!=NULL)
    {
        p=p->next->next;//p为快指针一次走两步；
        q=q->next; //q为慢指针一次走一步
    }
    return q;//返回中间结点指针
}

void Listprint_L(LinkList L) //单链表的输出
{
    LinkList p;
    p=L->next;
    while (p)
    {
        cout<<p->data<<"\t";
        p=p->next;
    }
    cout<<endl;
}

int main()
{
    LinkList L,mid;
    cout<<"创建单链表L:"<<endl;
    CreateList_R(L);
    cout<<"单链表数据为:"<<endl;
    Listprint_L(L);
    mid=findmiddle(L);
    cout<<"单链表中间结点数据为："<<mid->data<<endl;
    return 0;
}

双向链表

插入

P->pior->next=s;
S->pior=P->pior;
S->next=p;
P->next=S;

删除