线性数据结构

数据结构	优点	缺点
数组	插入快	查找慢 ，删除慢 ，大小固定只能存储单一元素
有序数组	比无序数组查询快	插入慢 ，删除慢 ，大小固定只能存储单一元素
栈	提供后进先出的存储方式	存储其他项慢
队列	提供先进先出的存储方式	存储其他项
链表	插入快 ，删除快	查找慢
二叉树	如果数是平衡的 ，则查找，插入，删除快	删除算法复杂
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;

• 删除