数据结构前三章(*回忆)

  1. 数据结构的基本概念
  2. 算法的基本概念
  3. 算法的时间复杂度
  4. 算法的空间复杂度
  5. 线性表(逻辑结构)的定义和基本操作
  6. 顺序表(存储结构:顺序存储)的定义和基本操作
  7. 单链表(存储结构:链式存储)的定义和基本操作
  8. 双链表的定义和基本操作
  9. 循环链表的定义和基本操作
  10. 静态链表的定义和基本操作
  11. 链表和顺序表的比较
  12. 栈的定义(逻辑结构:线性表)和基本操作
  13. 顺序栈(存储结构:顺序存储)的定义和基本操作
  14. 链栈(存储结构:链式存储)的定义和基本操作
  15. 队列的定义(逻辑结构:线性表)和基本操作
  16. 队列的顺序实现
  17. 队列的链式实现
  18. 双端队列(栈是只在一端进出的队列)
  19. 栈的应用
    - 括号匹配
    - 中缀表达式转后缀表达式
    - 中缀表达式求值、后缀表达式求值

数据结构的基本概念

程序 = 算法 + 数据结构
数据结构 = 数据的逻辑结构、数据的物理结构(存储结构)、数据的运算

算法的基本概念

算法是数据运算的顺序和执行方式

算法的时间复杂度与空间复杂度

时间复杂度:算法的运行次数与数据规模n的关系
空间复杂度:算法所占用的内存单元与数据规模n的关系
用O表示法

线性表

定义:相同类型元素 的有限序列
操作:

//初始化
InitList(List &L);
//销毁列表
DestroyList(List &L);
//插入
ListInsert(List &L,ElemType x);
//删除i位元素
ListDelete(List &L,int i,ElemType &x);
//返回x地址
LocateElem(List L,ElemType x);
//返回i位元素x
GetElem(List L,ELemType &x);
//判空
IsEmpty(List L);
//判满
IsFull(List L);
//返回线性表长
ListLong(List L);

线性表的顺序存储

顺序表
顺序表的特点:
优点:随机读取,存储密度大
缺点:扩容不方便,插入、删除数据不方便
逻辑结构:线性表
存储结构:顺序存储
代码定义

静态分配

#define MaxSize 10
typedef struct{
	ElemType data[MaxSize];
	int length;
}SqList;

void InitList(SqList &L){
	for(int i = 0; i < MaxSize;i++)L.data[i] = 0;
	L.length = 0;
}

bool IsEmpty(SqList &L){
	if(L.length == 0)return true;
	return false;
}

bool InsertList(SqList &L,int i,ElemType e){
	if(i < 0|| i > length||L.length == MaxSize)return false;
	if(i == length)L.data[i] = e;
	else{
		for(int j = length - 1;j >= i - 1;j--){
			L.data[j+1] == L.data[j];
		}
		L.data[i - 1] = e;
	}
	L.length ++;
	return true;
}

动态分配

#define InitSize 10
typedef struct{
	ElemType *data;
	int maxSize;
	int length;
}SqList;

bool InitList(SqList &L){
	L.data = (int *)malloc(InitSIze*sizeof(int));
	if(L.data == NULL)return false;
	L.length = 0;
	L.maxSize = InitSize;
	return true;
}

bool IncreaseSize(SqList &L,int len){
	int *p = L.data;
	L.data = (int *)malloc((L.MaxSize + len)*sizeof(int));
	if(L.data == NULL)return false;
	for(int i = 0;i < L.length;i++)L.data[i] == p[i];
	L.maxSize += len;
	return true;
}

线性表的链式存储

单链表
定义:每个节点存储数据及指向下一个节点指针的线性表
链表的特点:
优点:扩容方便,不要求大片连续的空间
缺点:不可随机存取,存储密度小,要耗费一定空间存储指针

实现:

无头节点

typedef struct LNode{
	ElemType data;
	struct LNode *next;
}LNode, *LinkList;

void InitList(LinkList &L){
	L = NULL;
}

bool IsEmpty(LinkList L){
	if(L == NULL)return true;
	return false;
}

有头节点

typedef struct LNode{
	ElemType data;
	struct LNode *next;
}LNode*LinkList;

bool InitList(LinkList &L){
	L = (LNode *)malloc(sizeof(LNode));
	L -> next = NULL;
}

bool IsEmpty(LinkList L){
	if( L -> next == NULL)return true;
	return false;
}

bool ListInsert(LinkList L,int i,ElemType x){
	if(i < 1)return false;
	for(int j = 0;j < i - 1 && L != NULL; j++){
		L = L -> next;
	}
	if(L == NULL)return false;
	LNode *s = (LNode *)malloc(sizeof(LNode));
	if(s == NULL)return flase;
	s -> data = x;
	s - > next = L -> next;
	L -> next = s;
	return true;
}

bool InsertNextNode(LNode *p,ElemType e){
	if(p == NULL)return false;
	LNode *s == (LNode *)malloc(sizeof(LNode));
	if(s == NULL)return false;
	s -> data = e;
	s -> next = p -> next;
	p -> next = p;
	return true;
}

bool ListInsert(LinkList L,int i,ElemType x){
	if(i < 1)return false;
	for(int j = 0;j < i - 1 && L != NULL; j++){
		L = L -> next;
	}
	return InsertNextNode(L,x);
}

bool InsertPriorNode(LNode *p,ElemType e){
	if(p == NULL)return false;
	LNode *s = (LNode *)malloc(sizeof(LNode));
	s -> next = p -> next;
	s ->value = p -> value;
	p -> next = s;
	p -> value = e;
	return true;
}
上一篇:【数据结构】单链表的操作例2-3&4(TQ-P27)


下一篇:数据结构(C++)--学习单链表时发现的一些小坑