保研复习数据结构记（1）--概念，线性表_计算机保研数据结构专业课知识

作为自己复习的参照物，所以复习系列主要以提问和回答形式为主。

一.前言

数结构解决什么问题：对现实世界信息化；高效解决程序问题

二.复习C语言指针

• 什么是指针：是一个存放变量地址的变量，type* var=&anothervar，我们称var为指针，anothervar为被存放地址的变量，借用菜鸟教程上面的图片解答：

三.数据结构基本概念

• 什么是数据：数据是信息的载体，是客观世界中输入到计算机中能被计算机识别的字符集合，比如说0和1

• 数据元素和数据项与数据有什么关系：数据元素是数据的基本单位，数据元素可以由若干数据项组成，数据项不可分割。

• 数据结构是什么：是相互之间存在一种或多种关系的数据元素的集合。

• 什么是数据对象：具有相同性质的数据元素的集合，是数据的子集。

• 数据结构的三要素是什么：逻辑结构、数据的运算、物理结构

• 数据结构的逻辑结构都有什么：集合结构、线性结构、树形结构、网状结构

• 数据的物理结构都有什么结构：顺序存储、链式存储、索引存储、散列存储     

• 什么是顺序存储：逻辑上相邻的元素物理上也相邻

• 什么是链式存储：逻辑上相邻的元素，物理上不相邻，用指针反映逻辑关系

• 什么是索引存储：用索引表记录数据的关键字和地址的关系

• 什么是散列存储：根据元素的关键字计算存储地址

• 什么是抽象数据类型：是抽象数据组织及与之相关的操作，定义ADT就是在定义一种数据结构，确定了ADT的存储结构，才能实现这种数据结构

• 什么是算法：是对特定问题求解步骤的一种描述，程序=数据结构+算法

• 算法具备哪些特性：有穷性：算法必须在有穷步骤结束，死循环不是算法；确定性：算法对于相同的输入必须有相同的输出；可行性：算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。；输入：一个或多个输入；输出：一个或多个输出

• “好算法”的特质：正确性；可读性；健壮性（对错误的反应做出处理）；时间空间复杂度低

• 什么是算法的时间复杂度：事先预估问题规模n和算法运行时间T的关系T(n)

• 常见算法时间复杂度：

 四.线性表 

• 什么是线性表：具有相同数据类型的n个数据元素的有限序列，除首末元素外，每个元素只有一个前驱和后继。

1.顺序表

• 什么是顺序表：用顺序存储的方式实现线性表

• 如何求出顺序表中第i个元素的位置，假设第一个元素的存放位置是：LOC(L)              LOC(Li)=LOC(L)+i*数据元素的大小

• C++如何求数据元素的大小：sizeof函数，使用范例如下：

cout<<"sizeof(bool)="<<sizeof(bool)<<endl;				// 1	
cout<<"sizeof(char)="<<sizeof(char)<<endl;				// 1	
cout<<"sizeof(short)="<<sizeof(short int)<<endl;		// 2
cout<<"sizeof(int)="<<sizeof(int)<<endl;				// 4

•  顺序表的顺序存储定义，初始化示例：

#include<bits/stdc++.h>
#define MaxSize 10//定义最大长度
typedef struct
{
	int data[MaxSize];//用静态数组存放元素
	int length;//顺序表当前的长度	
}Sqlist;//顺序表的类型定义
void InitList(Sqlist &L)
{
	for(int i=0;i<MaxSize;++i)
	{
		L.data[i]=0;//将所有数据元素默认为初始值	
	}
	L.length=0;//顺序表初始长度为0	
}
int main()
{
	Sqlist L;//声明一个顺序表 
	InitList(L);//初始化顺序表 
	return 0;	
} 

•  顺序表的链式存储定义，初始化如下：

#include<bits/stdc++.h>
#define InitSize 10//默认的最大长度 
typedef struct
{
	int* data;//指示动态分配数组的指针 
	int MaxSize;//顺序表的最大容量 
	int length;//顺序表的当前长度 
}Seqlist;
void InitList(Seqlist &L)//分配存储空间
{
	int* p=new int[InitSize];//用new申请一片连续的内存空间,但是这是新一片
	L.data=p;
	L.length=0;
	L.MaxSize=InitSize;
}
void IncreaseSize(Seqlist &L,int len)
{
	int* p=L.data;
	L.data=(int*)new int[L.MaxSize+len];//增大存储空间
	for(int i=0;i<L.length;++i)
	{
		L.data[i]=p[i];//将数据复制到新区域 
	}
	L.MaxSize=L.MaxSize+len;
	delete []p;
}
int main()
{
	Seqlist L;//声明一个顺序表
	InitList(L);//初始化顺序表
	IncreaseSize(L,5);
	return 0; 
}

• 顺序表有什么特点：随机访问O(1)访问；存储密度高；拓展容量不方便；插入删除不方便

• 顺序表的插入操作代码实现如下，平均时间复杂度为O(n)

bool InsertList(Sqlist &L,int i,int e)
{
	if(i<1||i>L.length+1)//当i<1也就是i=0时，是不正确的；同理当i=L.length+2时是顺序表不连续的，注意代码的健壮性
		return false;
	if(L.length>MaxSize)
		return false;
	for(int j=L.length;j>=i;--j)//j必须从L.length开始反向赋值 
		L.data[j]=L.data[j-1];//后移元素 
	L.data[i-1]=e;//赋值新元素，第i个位置实际上是线性表的i-1下标
	L.length++;
	return true; 
}

注意！！代码第七行j一定要大于等于i，而不是j大于i，只有j大于等于i的时候，j最后一次循环的值才是i，又因为i其实不是实际意义上的下标，而是比下标多+1。

• 顺序表的删除操作，是正向赋值，后面的赋值给前面的，时间复杂度O(n)

• bool DeleteList(Sqlist& L,int i,int& e)//将删除的值赋给e之后返回 
  {
  	if(i<1||i>L.length)//判断线性表范围是否有效 
  		return false;
  	e=L.data[i-1];//i和下标不一样，i比下标+1 
  	for(int j=i;j<L.length;++j)//和插入不同，这次是正向 
  	{
  		L.data[j-1]=L.data[j];//后面的覆盖前面的 
  	}
  	L.length--;//长度-1 
  	return true;
  }
  

• 顺序表的查找操作

        按位查找O(1)

GetElem(Sqlist L,int i)
{
	return L.data[i-1];
}

2.链表

• 什么是链表：用链式存储方式实现的线性表
• 用代码定义一个单链表，实现获取第i个元素的函数

typedef struct//定义单链表节点类型 
{
	int data;//定义数据域 
	struct LNode* next;//定义指针域 
}LNode,*LinkList;
//LNode强调是某个节点的指针 
//LinkList强调的是整个链表
LNode* GetElem(LinkList L,int i)
{
	int j=1;
	if(i==0)//返回第一个元素 
		return L;
	if(i<j)//如果是负数的话要返回空 
		return NULL;
	LNode* p=L->next;
	while(p!=NULL&&j<i)
	{
		p=p->next;
		++j;
	}
	return p;
}

• 带头节点的链表初始化和判断是否为空如下，带头节点的链表比不带头节点的链表使用方便。

bool InitList(LinkList& L)
{
	L=(LNode*)new LNode;
	if(L==NULL)//内存不足，分配失败 
		return false;
	L->next=NULL;//头结点之后暂时没有节点 
	return true;
}
bool IsEmpty(LinkList L)
{
	if(L->next==NULL)
		return true;//确实为空
	else
		return false;
//	return (L==NULL); //如果不带头节点，这样返回
}

•  单链表按位序插入代码如下（带头节点）

//对于列表L在第i个位置插入e，带头节点 
bool Insert(LinkList L,int i,int e)
{
	if(i<1)
		return false;
	LNode* p;//定义一个查询指针 
	int j=0;
	p=L;
	while(p!=NULL&&j<i-1)//逐渐移动到位序为i的前一个i-1 
	{
		p=p->next;
		++j;
	}
	if(p==NULL)//发现第i-1个是空 
		return false;
	LNode* s=(LNode*)new LNode;//创建节点 
	s->data=e;//插入
	s->next=p->next;
	p->next=s;
	return true;
}

•   单链表按位序删除代码如下（带头节点）

bool ListDelete(LinkList& L,int i,int& e)
{
	if(i<1)
		return false;
	LNode* p;
	int j=0;
	p=L;
	while(p!=NULL&&j<i-1)
	{
		p=p->next;
		++j;	
	}	
	if(p==NULL)//i值不合法 
		return false;
	if(p->next==NULL)//第i个值之后没有其他节点 
		return false;
	LNode* q=p->next;
	e=q->data;
	p->next=p->next->next;
	delete q;//删除中介节点 
	return true;
} 

 4.双链表

•  双链表的定义

typedef struct DNode{
	int data;
	struct DNode *prior,*next;
}DNode,*DLinkList;

• 双链表的初始化和判断是否为空

//初始化双链表 
bool InitDLinkList(DLinkList& L)
{
	L=(DNode*)new DNode;
	if(L==NULL)//分配失败
		return false;
	DNode->next=NULL;
	DNode->prior=NULL;
	return true; 
}
//判断双链表是否为空（带头节点） 
bool Empty(DLinkList L)
{
	if(L->next==NULL)//
		return true;
	else
		return false;
} 

• 双链表的插入

//双链表的插入:在p节点之后插入s节点
bool InsertNextDNode(DNode* p,DNode* s)
{
	if(p==NULL||s==NULL)//非法参数 
		return false;
	s->next=p->next;//注意接下来移动指针的顺序 
	if(p->next!=NULL)//如果p节点后有后继节点
	 	p->next->prior=s;
	s->prior=p;
	p->next-s;
	return true;
}

• 双链表的删除

//删除p的后继节点 
bool DeteteNextNode(DNode* p)
{
	if(p==NULL)
		return false;
	DNode* q=p->next;//找到p的后继节点q 
	if(q==NULL) return false;//如果p没有后继节点 
	p->next=q->next;
	if(q->next!=NULL)//q节点不是最后一个节点 
		q->next->prior=p;
	delete q;
	return true;
}

 5.循环链表

• 循环单链表 

//定义单链表并且初始化
typedef struct LNode//定义单链表节点类型 
{
	int data;//每个节点存放一个数据元素
	struct LNode* next;//指针指向下一个节点 
}LNode,*LinkList;
//初始化一个循环单链表
bool InitList(LinkList& L)
{
	L=(LNode*)new LNode;//分配一个头节点 
	if(L==NULL)//内存不足分配失败 
		return false;
	L->next=L;//头节点next指向头节点 
	return true;
}
//判断循环单链表是否为空
bool Empty(LinkList L)
{
	if(L->next==L)
	return true;
	else 
	return false;
} 

• 循环双链表

//定义双链表并且初始化
typedef struct DNode//定义双链表节点类型 
{
	int data;//每个节点存放一个数据元素
	struct DNode* next,*prior;//指针指向下一个节点 
}DNode,*DLinkList;
//初始化一个循环双链表
bool InitList(DLinkList& L)
{
	L=(LNode*)new LNode;//分配一个头节点 
	if(L==NULL)//内存不足分配失败 
		return false;
	L->next=L;//头节点next指向头节点 
    L->prior=L;
	return true;
}
//判断循环双链表是否为空
bool Empty(DLinkList L)
{
	if(L->next==L)
	return true;
	else 
	return false;
}

5.顺序表和链表的比较

• 有什么相同点：都属于线性表
• 存储结构的优缺点：顺序表支持随机存取、不需要存储指针，存储密度高；但是大片连续空间分配不方便，改变容量不方便。链表改变容量方便，但是不可随机存取。
• 在创建线性表方面有什么不同：顺序表需要预分配大片连续空间，若之后空间过小，则不方便拓展容量；若分配空间过大，则浪费资源。而链表只需要分配一个头节点，灵活性好。