线性数据结构

# 线性数据结构 | 数据结构 | 优点 | 缺点 | | :----------: | :----------: | :----------: | | 数组 | 插入快 | 查找慢 ，删除慢 ，大小固定只能存储单一元素 | | 有序数组 | 比无序数组查询快 | 插入慢 ，删除慢 ，大小固定只能存储单一元素 | | 栈 | 提供后进先出的存储方式 | 存储其他项慢 | | 队列 | 提供先进先出的存储方式 | 存储其他项 | | 链表 | 插入快 ，删除快 | 查找慢 | | 二叉树 | 如果数是平衡的 ，则查找，插入，删除快 |删除算法复杂 | | 2-3-4树 | 查找，插入，删除快 ，树总是平衡的 | 算法复杂| | 哈希表 | 如果关键字已知则存储极快 | 删除慢 ，如果不知道关键字存储慢，对储存空间使用不充足 | | 堆 | 插入 ，删除快 ，对最大数据储存快 | 对其他数据存取慢 | | 图 |对现实世界建模 | 有些算法慢而复杂 | | 红黑树 | 查找，插入，删除快 ，树总是平衡的 | 算法复杂 | 二叉堆  链表  树状数组  - ## 指针 ### 1. 指针变量（int *p) 与普通变量（int a)的关系 ```cpp p ------ &a //&为取地址运算符 *p ------ a //*为间接运算符 *p=3 ------ a=3 ``` ### 2. 指针变量定义 ```cpp int *p=NULL; ``` 定义了一个指针p ,p指向一个内存空间 ，里面存放着一个内存地址。现在赋值为NULL(为0 ，表示特殊的空地址）。 ### 3. 给指针变量p赋值 ```cpp 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. 指向结构体变量的指针 **一个结构体变量的指针就是该变量所占据的内存段的起始地址。可以设一个指针变量，用来指向一个结构体变量，此时，该指针变量的值是结构体变量的起始位置。** **使用指针变量访问结构体成员示例** ```cpp #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. **单链表结构体定义** ```cpp struct name{ (类型）data struct name *next; //name为结构体名称 ，next指向下一个节点的指针 }; ``` #### 2. **基本操作** - **初始化** ``` /* | 头指针L | NULL | */ L=new name; L->next=NULL; ``` - 创建  - 取值，查找  ```cpp P=L->next;j=1; P=P->next;j=2; ``` - 插入  - 删除  **相关代码** ```cpp #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; } ``` ### 双向链表 - 插入  ```cpp P->pior->next=s; S->pior=P->pior; S->next=p; P->next=S; ``` - 删除