三、链表,栈,队列,二叉树
(一)链表
(1)链表:由设计为大小合适的小的容器组成,这些容器可以根据需要链接在一起。
由头指针管理的结点
数组的缺陷
动态数组的缺陷
数组是在编译时分配内存的,所以数组的大小是不可改变的,可是链表是动态的,所以
可以在需要的时候增加和减小链表的长度。
(要加长要减短很容易。 链表来源于生活,如火车、 钻石用底座镶嵌连接起来--节点)
节点中放数据和指向下一个节点的指针:
-------- ----------- ----------- -----------
| head |-->|数据|指针|-->|数据|指针|-->|数据|NULL|
-------- ----------- ----------- -----------
头指针 头节点 内部节点 尾节点
struct Node{
T data; //数据
Node* next; //指向下一个节点,而不是数据
};
若改造成类:
class Node{
public: //加public 或者 设置友元 来提供访问权
T data;
Node* next;
};
链表家庭组成:
头节点: 其工作是管理链表的头。 第一个节点
尾节点: 最后一个 next==NULL 初始时,头节点的Next指针指向尾节点(既是头,也是尾)。
内部节点:存放数据类型。
头指针:指向头一个节点的指针,只有4byte
(2)链表的特点
a.非常重要的数据结构 (应用非常广泛)
b.灵活 数组必须连续存放,而链表不要求连续,只要零碎空间;
c.比数组节省空间 因为数组可能会浪费原来申请的空间,而链表要多少申请多少;
数组必须连续存放,而链表不要求连续,只要零碎空间;
d.访问比较慢 后续数据必需从头遍历数据才可访问到;
e.操作比较复杂 通过封装一些函数来解决。
(3)链表的操作
通常把头指针封装成一个链表类 Node* head;
插入
a.插入第一个节点:
1).准备节点
申请空间 Node* p = new Node;
设置data p->data = ...;
设置next=NULL p->next = NULL;
2).head指向新节点 head = p;
b.插入第二个节点:(前插法---新节点总是成为头节点)
1).准备节点
2).让新节点的next成员指向旧节点 p->next = head;
3).让head指向新节点 head = p;
插入第一个节点也可用以上三个步骤(一般复杂步骤兼容简单步骤)
头插法优点:只需要与head打交道,效率最高;
缺点:顺序与插入颠倒了 (应用于栈 再好不过)
c.插入第二个节点:(后插法)
1).准备节点
2).找到尾节点的next成员
写一个函数来找 返回类型Node*& (注意:返回的是Node*的引用,才可以修改它)
3).让它指向新节点
d.在任意位置插入新节点: (涵盖了前插、后插的通用算法):
1).准备新节点
2).找到链表中要插入位置的指针pn
3).让新节点的next成员指向要指入的位置 p->next = pn;
4).让找到的指针指向新节点 pn = p;
对于第2步举个例子,发现规律:
-------- ------------ ----------- ------------ ------------
| head |-->|数据0|指针|-->|数据1|指针|-->|数据2|指针|-->|数据3|NULL|
-------- ------------ ----------- ------------ ------------
0 pt = head;
1 pt->next;
2 pt=pt->next; pt->next
3 pt=pt->next; pt->next
两次
...
n号 pt=pt->next; pt->next //得出结论
n-1次
提醒:链表中只有两种的指针:head 和 next
pt = pt->next 使pt指向pt的下一个节点(前提要有下一个,否则段错误)
建议:一定要多画图!多画图自己就会有思路
---------------------------------------------------------
查找功能分析步骤:
1.定义一个指向第一个节点的指针
2.反复:2.1如果指针为空,找不到数据;
2.2如果非空,看节点中的数据是否是要找的数据
2.2.1 是,找到了
2.2.2 不是,让指针指向下一个节点
函数代码如下:
int find( T d )
{
Node* pt = head;
int pos = 0; //记录找到节点编号
while( pt!=NULL )
{
if( pt->data==d )
return pos; //找到返回节点编号
pt = pt->next;
++pos;
}
return -1; //找不到返回无效值
}
---------------------------------------------------------
更新功能的步骤分析:
1.查找数据,取得在链表中的位置
2.根据位置取得指向节点的指针
3.通过指针修改节点中的数据
函数代码如下:
bool update( T d1, T d2 )
{
int pos = find(d1);
if( pos==-1 )
return false;
Node* pt = getp(pos);
pt->data = d2;
return true;
}
---------------------------------------------------------
删除功能的步骤分析:
1.找到要删的数据所在的位置 pos
2.取得指向要删节点位置的指针 pn
3.把指针保存一份 pt=pn;
4.让pn指向下一个节点 pn = pn->next;
5.释放空间 delete pt;
函数代码如下:
bool erase( T d )
{
int pos = find(d);
if( pos==-1 )
return false;
Node*& pn = getp(pos);
Node* pt = pn;
pn = pn->next;
delete pt;
--len;
return true;
}
---------------------------------------------------------
取链表头:
T getHead()
{
if( empty())
return T();
return head->data;
}
取链表尾:
T getTail()
{
if( empty())
return T();
return getp(len-1)->data;
}
---------------------------------------------------------
(4)双向链表 (了解)
多维护了一个指针,可以前后遍历
struct Node{
int v;
Node *prev;
Node *next;
};
以空间换取时间
(二)栈
(1)LIFO(只要实现这一特征就是栈)
(2)常用方法:push(),pop(),isempty(),count(),clear(),reset()等
( 3 ) 栈的实现: 用数组实现,用链表实现
(三)队列
(1)FIFO;
(2)常用方法:insert(),pop()等;
(四)二叉树
(1)每个节点最多只有两个分支的树,它有一个根指针,要指向这棵树的根节点(最顶端的节点). 左子树上的值小于其父节点的值,右子树上的值都大于其父节点上的值。 --- 排序二叉树
(2)周游(遍历) :
先序 --- 中左右
中序 --- 左中右
后序 --- 左右中
(3)二叉查找树的常见操作:增,删,查,改,遍历;
主要的思想是迭代;
(4)非常方便查找
四、常用算法
(一)算法
有穷性 --- 在保证执行有限步骤之后确定能够结束
确切性 --- 每条语句具体干什么
输入输出 --- 所有的算法都有输出,打印屏幕,写文件,写DB
(二)常用的重要的方法(必须掌握下列排序的思想)
排序
(1)冒泡排序:用得是多轮排序,只比较相邻的数据对。只要发生过交换就要继续,如果没有发生交换排序完成。
规律:每一轮下来都会把最大的一个排好序。
适用于:只有少数是乱序的时候
void sort(){
bool bSwap;//不可以在do里面定义,不然在while()中就不能使用了
do{
bSwap=false;//是否交换过?
for(int i=0;i<n-1;i++){
if(a[i]>a[i+1]){
int t=a[i];
a[i]=a[i+1];
a[i+1]=t;
bSwap=true;//交换过
}
}
n--;//优化,因为每一次最大的都会排好序,所以可以少比一个数。
}while(bSwap); //只要发生过交换就再来一次
}
时间7秒10240个数据
int main(){
const int N=1024;
int a[n];
for(int i=0;i<N;i++)
a[i] = N-i;//保存的是1
long t1=time(NULL);
sort(a,N);
long t2=time(NULL);
cout<<"time:"<< t2-t1 <<endl;
for(int i=0;i<10;i++)
cout<<a[i]<<' ';
cout<<endl;
}
(2)选择排序:每次都找最大(最小)的元素放在应该放的位置
1反复i=0 i--n-1
1.1在未排序的数据中找到最小的元素。
1.1.1反复(j=i-n-1),以前做过递归选择排序
1.2把最小元素,跟下标为i的元素交换。
写void sort(int *a,n);对数组中N个元素排序。用选择排序法。
void sort(int *a , int n){
for(int i=0;i<n-1;i++){
int pos=i;
for(int j=i;j<i-n-1;j++){
if(a[j]<a[pos]){
pos=j;
}
}
int p=a[pos];
a[pos]=a[i];
a[i]=p;
}
}
#include<ctime>
int main(){
const num=10240;
int a[num];
for(int i=0;i<num;i++){
a[i]=num-i;
}
long t1=time(NULL);
sort(a,num);
long t2=time(NULL);
for(int i=0;i<8;i++){
cout<<a[i]<<' ';
cout<<endl;
cout<<"time:"<<t2-t1<<endl;
}
return 0;
}
时间2秒10240个数据
(3)插入排序:将头两个元素排序.把接下来的数据依次将每一个元素排到正确的位置.直到所有的元素都排完.前面一个数据不比要插入的数据大了,就是要插入的位置.凡是比它大的数据都要向后移动.
void sort(int *a,int n){
for(int i=1;i<n;i++){
int cur=a[i];
int j;
for(j=i;j>0&&a[j-1]>a[j];j--){
a[j]=a[j-1];//大量的数据移动,所以速度慢点.
}
a[j]=cur;
}
}
时间3秒10240个数据
(4)快速排序:效率最高的排序算法.
找一个分界值,把数据分成两组,对每一组在分成两组,知道只有最后一组数据只有一个数据为止.把大于分界值得放在一边,把不小于分界值得放在另一边.对这两小组在继续.
数组 {503,87,512,61,908,170,897,275,653,462}
1) [462 87 275 61 170] 503 [897 908 653 512]
2) [170 87 275 61] 462 503 [897 908 653 512]
3) [61 87] 170 [275] 462 503 [897 908 653 512]
4) 61 [87] 170 [275] 462 503 [897 908 653 512]
5) 61 87 170 [275] 462 503 [897 908 653 512]
6) 61 87 170 275 462 503 [897 908 653 512]
7) 61 87 170 275 462 503 [512 653] 897 [908]
8) 61 87 170 275 462 503 512 [653] 897 [908]
9) 61 87 170 275 462 503 512 653 897 [908]
10) 61 87 170 275 462 503 512 653 897 908
void swap(int& x,int & y){
int t=x;
x=y;
y=t;
}
void sort(int *a,int n){
if(n<=1){return ;}
int pivot=a[n>>1];//a[0],a[n-1],a[n/2]找谁居中作为分界值.这里简单处理选a[n/2];
swap(a,a[n>>1]);
int *p=new int[n];
int* lp=p;
int* rp=p+(n-1);
int pivot=*a;
int *pt=a;//为了效率
for(int i=1;i<n-1;i++){
if(pivot>*pt){
*lp++=*pt;
}else{
*rp--=*pt;
}
}
*lp=pivot;
pt=a;
lp=p;
for(int i=0;i<n;i++){
*pt++=*lp++;
}
delete[] p;
int left=rp-p;
sort(a,left);
sort(a+left+1,n-left-1);
}
分享到:
相关推荐
数据结构基数排序数据结构基数排序数据结构基数排序数据结构基数排序数据结构基数排序数据结构基数排序
数据结构之基数排序数据结构之基数排序数据结构之基数排序数据结构之基数排序数据结构之基数排序
c语言版本的数据结构的快速排序算法,适用于新手学习
这本书是用java讲数据结构和排序算法的,全书只有44页,但是讲的内容很不错,推荐学习或者复习数据结构的童鞋下在看看!
数据结构冒泡排序算法 数据结构冒泡排序算法
数据结构拓扑排序
数据结构各种排序算法实现及比较 数据结构各种排序算法实现及比较 数据结构各种排序算法实现及比较
数据结构 综合排序 冒泡排序 直接插入排序 快速排序 希尔排序,完整的代码,有每种排序时间的比较
数据结构排序数据结构排序数据结构排序数据结构排序
数据结构排序一章的希尔结构排序,显示结果的
数据结构试验 排序问题的实现 内部排序等 C语言 源代码
数据结构--快速排序C++源代码,自己编写调试,代码简单易懂,不长
数据结构 希尔排序 演示 一看就懂 非常直观
海大秦平老师数据结构课程第八章搜索和第九章排序的算法题,一共有三道题 T1:【折半查找算法】 利用折半查找算法在一个有序表 R 中插入一个关键字 为 k 的元素想,并保持表的有序性。 T2:【二叉排序树算法】 对于...
C++数据结构-排序 源代码
数据结构实验排序程序数据结构;源程序;直接排序;快速排序
数据结构的数据结构课程设计源代码,实现冒泡排序的源代码
1、链表排序 [问题描述] 建立一个...设计要求:利用随机函数产生10个样本,每个样本有20000随机整数,利用直接插入排序、希尔排序,冒泡排序、快速排序、选择排序、堆排序,归并排序,基数排序八种排序方法进行排序
数据结构课程中的各种排序示例完整程序,用C语言实现 各种示例包括:希尔排序、选择排序、插入排序、冒泡排序、快速排序等
数据结构排序算法中的快速排序,是非常重要的一个算法,从时间上来看,是在随机情况下排大量数据的最优选择