数据结构 | 1-5章

落日映苍穹つ 2021-11-05 15:06 190阅读 0赞

## 一、绪论 ##

#### (一) 数据结构以及相关概念的定义 ####

*  数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
 *  数据元素：是数据的基本单位，在计算机程序中通常作为一个整体处理，比如树。
 *  数据对象：性质相同的数据元素的集合，是数据的一个子集，如整数数据对象。
 *  数据结构：相互之间存在一种或多种特定关系的数据元素的集合：集合、线性结构、树形结构、图状结构或网状结构。
 *  物理结构/存储结构：顺序存储结构、链式存储结构
 *  逻辑结构

#### (二) 抽象数据类型 ####

*  赋值语句、选择语句、循环语句、结束语句、输入和输出语句、注释、基本函数、逻辑运算约定

#### (三) 算法的时间复杂度和空间复杂度 ####

*  略

## 二、线性表 ##

#### (一) 线性表的定义和基本操作 ####

*  定义：n个数据元素的优先序列。

#### (二) 线性表的实现 ####

###### 1. 顺序存储结构 ######

#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量
    #define LISTINCREMENT 10//线性表存储空间的分配增量
    typedef struct{ 
    	Elem *elem; //存储空间基地址
    	int length;//当前长度
    	int listsize; //当前分配的存储容量，以sizeof（ElemType）为单位
    }SqList;

###### 2. 链式存储结构，循环链表，双向链表 ######

//单链表/循环链表

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

//双向链表

typedef struct DuLNode{ 
    	ElemType data;
    	struct DuLNode *prior;
    	struct DuLNode *next;
    }DuLNode, *DuLinkList;

###### 3. 线性表的应用 ######

*  缺练习题，关于线性表的增删查改的练习题

## 三、栈、队列 ##

#### (一) 栈和队列的基本概念 ####

*  栈：限定仅在表尾进行插入或删除操作的线性表。
 *  队列： 先进先出的线性表，只允许在表的一端进行插入，而在另一端删除元素。

#### (二) 栈和队列的顺序存储结构 ####

//栈的顺序存储表示

#define STACK_INIT_SIZE 100;//存储空间初始分配量
    #define STACKINCREMENT ;//存储空间分配量
    typedef struct {
    	SElemType *base;
    	SElemType *top; 
    	int stcksize; //当前已分配的存储空间，以元素为单位
    }SqStack;

//循环队列的顺序存储结构

#define MAXQSIZE 100; //最大队列长度
    typedef struct {
    	QElemType *base; //初始化动态分配存储空间
    	int front; //头指针，若队列不空，指向队列头元素
    	int rear'//尾指针，若队列不空，指向队列尾元素的下一个位置
    }SqQueue；

#### (三) 栈和队列的链式存储结构 ####

//队列的链式存储

typedef struct QNode{
    	QElemType data;
    	struct QNode *next;
    }QNode,*QueuePtr;
    typedef struct {
    		QueuePtr front;
    		QueuePtr rear;
    }LinkQueue;

#### (四) 栈和队列的应用 ####

*  数制转换  
    对于输入任意的一个非负十进制整数，打印输出与其等值的八进制数。

void conversion(){
    	InitStack(s);
    	scanf("%d",N);
    	while(N)
    	{
    		Push(S,N%8);
    		N=N/8;
    	}
    	while(! StackEmpty(s))
    	{
    		Pop(s,e);
    		printf("%d",e);
    	}
    }

*  括号匹配的检验
 *  行编辑程序

void LineEdit（）
    {
    	InitStack(S);
    	ch=getchar();//从终端接受第一个字符
    	while(ch!=EOF)
    	{
    		while(ch!=EOF &&ch!='\n')
    		{
    			switch(ch)
    			{
    				case '#':Pop(S,c); break; //仅当栈非空时退栈
    				case '@':CkearStack(S); break;//重置S为空栈
    				default：Push（S，ch）;break;//有效字符进栈，未考虑栈满情形
    			}
    			ch=getchar(); //从终端接收下一个字符
    		}
    		//将才栈底到栈顶的栈内字符传送至调用过程的数据区
    		ClearStack（S）；
    		if(ch!=EOF) ch=getchar();
    	}
    	DestroyStack(S);
    }

*  迷宫求解
 *  表达式求值
 *  斐波那契
 *  汉诺塔

## 四、串 ##

#### (一) 串的各种存储表示和操作 ####

*  串：由0或多个字符组成的有限序列，用单引号引起来，如`a='BHKI'`
 *  串的定长顺序存储表示

#define MAXSTRLEN 255 //用户可在255以内定义最大串长
    typedef unsigned char SString[MAXSTRLEN+1]；//0号单元存放串的长度

*  串连接时，未超出最大串长的则结果正确，超出部分会直接被截断
 *  堆分配存储表示

typedef struct {
    	char *ch;//若是非空串，则按串长分配存储区，否则为NULL
    	int length;//串长度
    }HString；

*  串的块链存储表示

#define CHUNKSIZE 80;//用户可定义的块大小
    typedef struct Chunk{
    	char ch[CHUNKSIZE];
    	struct Chunk *next;
    }Chunk;
    typedef struct {
    	Chunk *head, *tail;//串的头和尾指针
    	int curlen;//串的当前长度
    }LString；

#### (二) KMP算法 ####

这个推送讲得很详细：https://mp.weixin.qq.com/s/2JyZoy9pESrcd5hsGWLWgw  
这篇待看：https://blog.csdn.net/dark\_cy/article/details/88698736

*  字符串查找算法：常用于在一个文本串S内查一个模式串P的出现位置。
 *  KMP算法需要知道手写代码，还未弄懂

## 五、数组和广义表 ##

#### (一) 数组的基本概念、表示和实现 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTQ1OTI2_size_16_color_FFFFFF_t_70]

#### (二) 矩阵的压缩存储 ####

*  假若值相同的元素或零元素在矩阵中的分布有一定规律，则我们称次矩阵为特殊矩阵，反之，称为稀疏矩阵。

###### 1. 特殊矩阵 ######

###### 2. 稀疏矩阵 ######

#### (三) 广义表的定义和存储结构 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTQ1OTI2_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTQ1OTI2_size_16_color_FFFFFF_t_70]: /images/20211105/97db706f3e4a4aaa840b400e323c9267.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTQ1OTI2_size_16_color_FFFFFF_t_70 1]: /images/20211105/79e72f63d1784c7eb39db9814188c399.png