王道408数据结构 |
您所在的位置：网站首页 › initlist怎么声明 › 王道408数据结构 |
王道408数据结构
|
第一章：绪论数据结构在学什么？ 如何用程序代码把现实世界的问题信息化 如何用计算机来高效的处理这些信息从而创造价值 数据元素——描述一个个体 数据元素、数据项： 数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。 一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位。  什么是数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集。  什么是数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 线性数据结构：朴实无华排行榜 网状数据结构：枯燥无味朋友圈  数据结构三要素：逻辑结构，数据的运算，物理结构（存储结构） 逻辑结构：数据元素之间的逻辑关系是什么？ 集合：各个元素同属一个集合，别无其它关系。 线性结构：数据元素之间是一对一的关系。除了第一个元素，所有元素都有唯一前驱；除了最后一个元素，所有元素都有唯一后继。 树形结构：数据元素是一对多的关系。 图结构：数据元素之间是多对多的关系。 数据的运算：针对于某种逻辑结构，结合实际需求，定义基本运算  物理结构（存储结构）：如何在计算机内部表示数据元素的逻辑结构？ 顺序存储：把逻辑上相邻的元素存储在物理元素上也相邻的存储单位中，元素之间的关系由存储单位的邻接关系来体现。 链式存储：逻辑上相邻的元素在物理位置上可以不相邻，借助指示元素存储地址的指针来元素之间的逻辑关系。 索引存储：在存储元素信息的同时，还建立附加的索引表。索引表的每一项称为索引项，索引项的一般形式是（关键字，地址）。 散列存储：根据元素的关键字直接计算出该元素的存储地址，又称为哈希存储。 注：后三种可以统称为离散存储。  数据类型，抽象数据类型：数据类型是一个值的集合和定义在此集合上的一组操作的总称。 1）原子类型：其值不可分的数据类型 2）结构类型：其值可以再分解为若干成分（分量）的数据类型。 抽象数据类型是抽象数据组织及与之相关的操作。  什么是算法：程序=数据结构+算法 算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个操作。  算法的特性：有穷性：一个算法必须总在执行有穷步之后结束，且每一步都可以在有穷时间内完成。（算法必须是有穷的，而程序可以是无穷的。） 确定性：算法中每条指令必须有确切的含义，对于相同的输入只能得到相同的输出。 可行性：算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。 输入：一个算法有零个到多个输入，这些输入取自于某个特定的对象的集合。 输出：一个算法有一个或多个输出，这些输出是与输入有着某些特定关系的量。  “好”算法的特质1）正确性：算法应能够正确地解决求解问题。 2）可读性：算法应具有良好的可读性，以帮助人们理解。 3）健壮性：输入非法数据时，算法能够适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。 4）高效率与低存储量需求：花的时间少，时间复杂度低；不费内存，空间复杂度低。  算法时间复杂度算法时间复杂度：事前预估算法时间开销T(n)与问题规模n的关系（T表示“time”） 算法1 逐步递增性爱你 void loveYou(int n) { // n 为问题规模 int i = 1；//1 while(inext; if(q == NULL) return false; p->next = q->next; if(q->next!=NULL) q->next->prior=p; free(q); return true; } //双链表的销毁 void DestoryList(DLinklist &L){ while(L->next != NULL) DeleteNextDNode(L); free(L); // 释放头结点 L = NULL; // 头结点指向NULL } 循环链表循环单链表vs单链表： 单链表：从一个结点出发只能找到后续的各个结点 循环单链表：从一个结点出发可以找到其它任何一个结点 很多时候对于链表的操作都是在头部或尾部，时间复杂度为O(n)，而对于循环链表 循环双链表vs双链表： 双链表：表头结点的prior指向NULL。表尾结点的next指向NULL 循环双链表：表头结点的prior指向表尾结点，表尾结点的next指向头结点 #include #include typedef int ElemType; typedef struct LNode{ ElemType data; struct LNode *next; }LNode, *LinkList; //初始化一个循环单链表 bool InitList(LinkList &L){ L = (LNode *)malloc(sizeof(LNode)); if(L==NULL) return false; L->next = L; return true; } //判断循环链表是否为空 bool Empty(LinkList L){ if(L->next == L) return true; else return false; } bool isTail(LinkList L,LNode *p){ if(p->next==L) return true; else return false; } void testLinkList(){ //初始化一个循环链表 LinkList L; InitList(L); } int main(){ testLinkList(); } 循环双链表的插入： //在p结点之后插入s结点 bool InsertNextDNode(DNode *p,DNode *s){ s->next = p->next; p->next->prior = s; s->prior = p; p->next = s; } 静态链表：单链表：各个结点在内存中星罗棋布，散落天涯。 静态链表：分配一整片连续的内存空间，各个结点集中安置。  定义一个静态链表： 方法一（简单版） #define MaxSize 10; //静态链表的最大长度 struct Node{ //静态链表结构类型的定义 ElemType data; //存储数据元素 int next; //下一个元素的数组下标 }; void testSLinkList(){ struct Node a[MaxSize];//数组a作为静态链表 }方法二（课本版） #define MaxSize 10; typedef struct { ElemType data; int next; }SLinkList[MaxSize]; void testSLinkList(){ SLinkList a; } 测试代码： #include #include #define MaxSize 10 typedef int ElemType; struct Node{ ElemType data; int next; }; typedef struct{ ElemType data; int next; }SLinkList[MaxSize]; void testSLinkList(){ struct Node x; printf("sizeX=%lu\n",sizeof(x)); struct Node a[MaxSize]; printf("sizeA=%lu\n",sizeof(a)); SLinkList b; printf("sizeB=%lu\n",sizeof(b)); } int main(){ testSLinkList(); }运行结果如图：  静态链表的基本操作：  知识点与重要考点回顾  顺序表vs链表逻辑结构上：都属于线性表，都是线性结构存储结构上：顺序表：支持随机存取，存储密度高。但是大片连续空间分配不方便，改变容量不方便。链表：离散的小空间分配方便，改变容量方便。到那时不可随机存取，存储密度低。基本操作：创，销，增删改查。基本操作： 创： 顺序表需要预分配大片连续空间。若分配空间过小，则之后不方便拓展容量（静态分配不可拓展，动态分配用malloc和free，容量可以改变但是需要移动大量的元素，时间代价高）；若分配空间过大，则浪费内存资源。 链表只需分配一个头结点（也可以不要头结点，只声明一个头指针），之后方便拓展。 销： 顺序表需要先修改Length=0，当使用静态数组时，系统会自动回收空间。动态数组时，需要手动free。 typedef struct{ ElemType *data; int MaxSize; int length; }SeqList; L.data = (ElemType *)malloc(sizeof(ElemType)*InitSize); free(L.data);链表则需要依次删除各个结点（free） 增删： 顺序表插入/删除元素需要将后续元素都后移/前移。时间复杂度O(n),时间开销主要来自移动元素。 链表插入和删除元素只需修改指针即可。时间复杂度O(n),时间开销主要来自查找目标元素。 显然，虽然两者的时间复杂度在一个数量级，但是考虑到若数据元素很大，则移动的时间代价相比查找的时间代价要更高。 查： 按位查找：顺序表：O(1),链表：O(n) 按值查找：若表内元素有序，顺序表可在O(log2n)时间内找到，而链表仍然是O(n) 如何选择？ 如图：  知识回顾与重要考点：  第三章：栈和队列栈的定义线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。若用L命名线性表，则其一般表示为：L(a1,a2,…,ai+1,an) 栈(stack)是只允许在一段进行插入或删除操作的线性表。  重要术语：栈定，栈底，空栈 栈的基本操作 n个不同元素进栈，出栈元素不同排列的个数为1/(n+1)C(n,2n)。上述公式称之为卡特兰树(Catalan)数，可采用数学归纳法证明(不要求掌握)。   #include
#include
typedef int ElemType;
//定义
#define MaxSize 10 //定义栈中元素的最大个数
typedef struct{
ElemType data[MaxSize]; //静态数组存放栈中元素
int top; //栈顶指针
}SqStack;
//初始化操作
void InitStack(SqStack &S){
S.top=-1; //初始化栈顶指针
}
//判断栈空
boolc StackEmpty(SqStack S){
if(S.top==-1) //栈空
return true;
else //不空
return false;
}
//新元素入栈
bool Push(SqStack &S,ElemType x){
if(S.top==MaxSize-1)//栈满，报错
return false;
S.top = S.top + 1; //指针先加1
S.data[S.top] = x; //新元素入栈
//上边两句等价于S.data[++S.top]=x
return true;
}
//出栈操作
bool Pop(SqStack &S,ElemType &x){
if(S.top==-1) //栈空，报错
return false;
x=S.data[S.top]; //栈顶元素先出栈
S.top = S.top -1; //指针再减1
return true;
}
//读栈顶元素
bool GetTop(SqStack S,ElemType &x){
if(S.top==-1)
return false;
x=S.data[S.top];
return true;
}
//注，初始化时，top是0和-1的实现代码不一样！！！
void testStack(){
SqStack S; //声明一个顺序栈(分配空间)
InitStack(S);
//...
}
int main(){
testStack;
}
顺序栈的缺点：top==MaxSize,栈的大小不可变 共享栈的概念： 【数据结构】共享栈 - 主教主 - 博客园#include #include typedef int ElemType; typedef struct LNode{ ElemType data; struct LNode *next; }LNode, *LinkList; //初始化一个单链表 bool InitList(LinkList &L){ L = (LNode *)malloc(sizeof(LNode)); if(L == NULL){ return false; } L->next = NULL; return true; } void test(){ LinkList L; //初始化一个空表 InitList(L); } int main(){ test(); } 栈的链式存储结构栈是一种，特殊的，受限制的线性表。而链栈作为栈的一种一种，对应线性表里的单链表。 链栈是运算受限的单链表，只能在链表头部进行操作。（用链式存储，存储的栈） 代码： #include #include typedef int ElemType; typedef struct Linknode{ ElemType data; struct Linknode *next; }*LiStack; 队列的基本概念栈是只允许在一端进行插入或删除操作的线性表 队列是只允许在一端进行插入，在另一端删除的线性表 特点：先进入队列的元素先出队。 队列的顺序实现：  #include
#include
//队列的顺序实现
#define MaxSize 10 //定义队列中元素的最大个数
typedef int ElemType; //用静态数组存放队列元素
typedef struct{ //队头指针和队尾指针
ElemType data[MaxSize];
int front,rear;
}SqQueue;
//初始化操作
void InitQueue(SqQueue &Q){
//初始化时 队头，队尾指针指向0
Q.rear=Q.front=0;
}
//判断队列是否为空
bool QueueEmpty(SqQueue Q){
if(Q.rear==Q.front)
return true; /队空条件
else
return false;
}
//循环队列，入队操作
bool EnQueue(SqQueue &Q,ElemType x){
if((Q.rear+1)%MaxSize==Q.front)
return false; //队满则报错
Q.data[Q.rear]=x; //将x插入队尾
Q.rear=(Q.rear+1)%MaxSize; //队尾指针后移
return true;
}
//循环队列，出队操作（删除一个队头元素，并用x返回）
bool DeQueue(SqQueue &Q,ElemType &x){
if(Q.rear==Q.front)//判断队空
return false;
x=Q.data[Q.front];
Q.front=(Q.front+1)%MaxSize
return true;
}
void testQueue(){
SqQueue Q;
InitQueue(Q);
// ...后续操作...
}
 循环队列  判断队列已满/已空 方案一：队空条件：Q.rear=Q.front队满条件：(Q.rear+1)%MaxSize==Q.front方案二：在队列结构体中设置一个size。插入成功：size++删除成功：size—队空条件：size=0队满条件：size=MaxSize方案三：在队列结构体中设置一个tag每次删除操作成功时，都令tag=0每次插入操作成功时，都令tag=1队空条件：front=rear&&tag=0队满条件：front=rear&&tag=1 队列的链式实现#include
typedef int ElemType;
typedef struct LinkNode{ //链式队列结点
ElemType data;
struct LinkNode *next;
}LinkNode;
typedef struct{ //链队队列
LinkNode *front,*rear; //队列的队头和队尾指针
}LinkQueue;
//初始化队列（带头结点）
void InitQueue(LinkNode &Q){
//初始化时 front，rear都指向头结点
Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));
Q.front->next=NULL;
}
//判断队列是否为空
bool IsEmpty(LinkQueue Q){
if(Q.front==Q.rear)
return true;
else
return false;
}
//新元素入队（带头结点）
void EnQueue(LinkQueue &Q,ElemType x){
LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));
s->data=x;
s->next=NULL;
Q.rear->next=s; //新结点插入到rear之后
Q.rear=s; //修改表尾指针
}
//新元素入队(不带头结点)
void EnQueue_2(LinkQueue &Q,ElemType x){
LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));
s->data=x;
s->next=NULL;
if(Q.front == NULL){ //不带头结点的空队列中插入第一个元素
Q.front = s; //修改队头队尾指针
Q.rear = s;
}
else{
Q.rear->next=s;
Q.rear=s;
}
}
//队头元素出队(不带头结点)
bool DeQueue(LinkQueue &Q,ElemType &x){
if(Q.front==Q.rear)
return false; //空队
LinkNode *p=Q.front->next;
x=p->data; //用变量x返回队头元素
Q.front->next=p->next; //修改头结点的next指针
if(Q.rear==p) //此次是最后一个结点出队
Q.rear=Q.front; //修改rear 指针
free(p); //释放结点空间
return true;
}
void testLinkQueue(){
LinkQueue Q; //声明一个队列
InitQueue(Q); //初始化队列
//。。。后续操作。。。
}
顺序存储：预分配的空间耗尽时队满 链式存储：一般不会队满，除非内存不足  双端队列栈：只允许从一端插入和删除的线性表 队列：只允许从一端插入，另一端删除的线性表 双端队列：只允许从两端插入，两端删除的线性表 输入受限的双端队列：只允许从一端插入，两端删除的线性表输出受限的双端队列：只允许从两端插入，一端删除的线性表考点：判断输出序列合法性 若数据元素输入序列为1，2，3，4，则哪些输出序列是合法的，哪些是非法的？栈中合法的序列，双端队列中也一定合法。  栈的应用--括号匹配问题括号匹配问题(如下代码，所有的括号都是成双成对出现的)： void test(){ int a[10][10]; int x = 10*(20*(1+1)-(3-2)); printf("加油！奥里给！") } 匹配代码实现#include
#include
//初始化栈
#define MaxSize 999
typedef int ElemType; //用静态数组存放队列元素
typedef struct{
ElemType data[MaxSize]; //静态数组存放栈中元素
int top; //栈顶指针
}SqStack;
//初始化栈
void InitStack(SqStack &S){}
//判断栈是否为空
bool StackEmpty(SqStack S){}
//新元素入栈
bool Push(SqStack &S,char x){}
//栈顶元素出栈，用x返回
bool Pop(SqStack &S,char &x){}
bool bracketCheck(char str[],int length){
SqStack S;
InitStack(S); //初始化一个栈
for (int i=0;i=0)其中，S是串名，单引号括起来的字符序列是串的值；ai可以是字母，数字或其他字符；串中字符的个数n称为串的长度。n=0时的串称为空串。 子串：串中任意个连续的字符组成的子序列 主串：包含子串的串 字符在主串中的位置：字符在串中的序号 子串在主串中的位置：子串的第一个字符在主串中的位置 注：空串vs空格串 M='',N=' '（M是空串，N是空格串，每个空格占1B空间） 串VS线性表  串的基本操作  字符集编码： 任何数据存到计算机中一定是二进制数。需要确立一个字符和二进制数的对应规则，这就是”编码“ ”字符集“： 英文字符----ASCII字符集 中英文----Unicode字符集（基于同一个字符集，可以有多种编码方案，如：UTF-8，UTF-16） 拓展：乱码问题 在你的文件中，原本采用某一套编码规则y=f(x),如：'码'0001010100010101010010 打开文件时，你的软件以为你采用的是另一套编码规则y=g(x),如0001010100010101010010'薆'  串的存储结构串的顺序存储 #include #define MAXLEN 255 //预定义最大串长为255 //静态数组实现 typedef struct { char ch[MAXLEN]; //每个分量存储一个字符 int length; //串的实际长度 }SString; //动态数组实现 typedef struct { char *ch; int length; }HString; int main(){ HString S; S.ch = (char*)malloc(MAXLEN*sizeof(char)); S.length = 0; } 串的链式存储 typedef struct StringNode{ char ch; //每个结点存1个字符 struct StringNode *next; }StringNode,*String; //上边的存储密度低 typedef struct StringNode{ char ch[4]; struct StringNode *next; }StringNode,*String; 更多的基本操作 bool SubString(SString &Sub,SString S,int pos,int len){ //子串范围越界 if (pos+len-1>S.length) return false; for(int i=pos;iT，则返回值>0；若S=T，则返回值=0，若S |
【本文地址】