数据结构部分常考知识点

对于一元多项式相乘的算法，可以利用两个一元多项式相加的算法来实现，因为乘法运算可以分解为一系列的加法运算。栈与队列栈与队列也属于线性表，特殊性在于栈和队列的基本操作是线性表操作的子集。栈与队列是操作受限的线性表。栈与队列可称为限定性数据结构。栈与队列在面向对象的程序设计中是多型数据结构。栈(stack)定义：限定仅在表位进行插入或删除操作的线性表。表尾：称为栈顶（top）表头：称为栈底(bottom)不含任何元素的空表称为空栈。栈S=(a1,a2,…,an),a1为栈底元素，an为栈顶元素。栈的修改是按照后进先出（先进后出）原则进行的。栈称为后进先出的线性表（简称为LIFO）栈的基本操作：栈顶的插入或删除、栈的初始化、判空、取栈顶元素等抽象数据类型：数据对象，数据关系，数据操作InitStack(&S)：构造一个空栈SDestoryStack(&S):初始条件：栈S已经存在；操作结果：栈S被摧毁ClearStack(&S):初始条件：栈S存在；操作结果：栈S清为空栈StackEmpty(S):初始条件：栈S存在；操作结果：若栈S为空栈返回TRUE，否则返回FALSE。StackLength(S)：初始条件：栈S存在;操作结果：返回S中元素的个数，即栈的长度。GetTop(S,&e)：初始条件：栈S存在且非空；操作结果：用e返回S的栈顶元素。Push(&S,e)：初始条件：栈S存在；操作结果：插入元素e为新的栈顶元素。Pop(&S,e)：初始条件：栈S存在且非空；操作结果：删除栈顶元素且用e返回其值。StackTraverse(S,visit())：初始条件：栈S已存在且非空；操作结果：从栈底到栈顶依次对S的每一元素调用visit()函数。一旦visit()失败则操作失败。插入元素的操作：入栈删除栈顶元素的操作：出栈栈的存储表示方法：顺序存储结构和栈的链式表示。顺序栈：地址连续的存储单元依次存放从栈底到栈顶的数据元素，top指针指示栈顶元素在顺序栈中的位置。top=0：空栈一般初始化空栈时不应限定栈的最大容量。具体做法：先为栈分配一个基本容量，不够再逐段扩展。STACK_INIT_SIZE（存储空间初始化分配量）STACKINCREEMENT（存储空间分配增量）顺序栈的定义：typedefstruct{ SElemType*base; SElemType*top; Intstacksize;}SqStack;Stacksize:当前可使用的最大容量。base:栈底指针，base=NULL时栈结构不存在。top:栈顶指针，top=base表示栈空非空栈的栈顶指针始终指向栈顶元素的下一个位置上。栈的应用举例：（1）、数值的转换（2）、括号匹配的检验（3）、行编辑程序（4）、迷宫求解（5）、表达式求解（2）、括号匹配的检验：用“期待的急迫程度”这个概念来描述（3）、行编辑程序：设立一个输入缓冲区（4）、迷宫求解——穷举求解——后进先出（5）、表达式求值：iostream:输入输出流。程序编译时先对所有的预处理命令进行处理，将头文件中具体内容代替#include命令行。命名空间namespace。usingnamespacestd表示要用的明明空间std中的内容单行注释用//cin是C++系统定义的输入流对象。>>是“提取运算符”。类中包含两种成员：数据成员和成员函数。类:将一组数据和有权调用这些数据的函数封装在一起，组成一个数据类型。成员函数是对数据成员的操作。类具有封装性和信息隐藏。private（私有的）、public（公有的）public：既可以被本类中成员函数调用、也可以也可被类外的语句调用。private:私有的成员（函数或数据）只能被本类中成员函数调用。具有“类”类型的变量称为“对象”。对象占有实际存储空间，类型并不占用存储空间。“.”成员运算符。连接成员与对象。C++程序的编写和实现：用C++语言编写程序对源程序进行编译将目标文件进行连接运行程序数据类型：基本数据类型、非基本数据类型、指针类型。基本数据类型：整型、实型、字符型、布尔类型。非基本类型：枚举类型、结构体类型、共享体类型、类类型、数组类型、typedef定义的类型。整型：短整型、整型、长整型实型（浮点类型）：单精度、双精度、长双精度指针和结构体可以构成表、树、栈等复杂的数据类型。常量：数值型常量、字符型常量。浮点数的表示方法：十进制小数形式、指数形式：数符数字部分指数部分转义字符：‘\0’空字符、\ddd：1~3位八进制数所代表的字符、\xhh：1~2位十六进制所代表的字符。字符串常量：以双撇号扩起来的部分为字符串常量。‘\0’：空字符，并不属于字符串一部分，而是表示字符串结束。字符串常量比同样的字符多占一个字节的空间。函数的递归调用：在调用一个函数的过程中又出现直接或间接地调用该函数本身，称为函数的递归调用。包含递归调用的函数称为递归函数。局部变量和全局变量。局部变量（内部变量）：在一个函数内部定义的变量称为内部变量，只在函数内部可以被调用。形式参数也是局部变量（内部变量）在函数声明中出现的参数名，其作用范围只在本行的括号内。一个源文件可以包含一个或多个函数，函数内定义的变量为局部变量（内部变量），在函数之外定义的变量为全局变量或外部变量。全局变量的作用范围：从定义位置到本源文件结束。如果全局变量再被函数调用之后数。值发生改变，当再次被调用时，以最近一次改变的数值为准。全局变量的劣势：全局变量在程序的全部执行过程中都占用存储单元，而非仅在需要时才开辟。全局变量使得程序的通用性降低，因为在执行函数时要受到外部变量的影响。使用全局变量会降低程序的清晰性。不知道当前的全局变量到底改变没有。如果在同一源文件中全局变量与局部变量同名，则局部变量作用范围内全局变量被屏蔽，不起作用。作用域：文件作用域（全局的）、函数作用域（局部的）、块作用域（局部的）、函数原型作用域（局部的）。变量的存储类别：动态存储方式和静态存储方式。变量的两个属性：作用域（全局变量和局部变量）和存储期（动态存储和静态存储）。存储期：变量在内存中的存在期间（时间角度考虑）。静态存储方式：程序运行期间系统对变量分配固定的存储空间。动态存储方式：程序运行期间，系统对变量动态分配存储空间。内存：程序区、静态存储区、动态存储区。全局变量全部存在静态存储区。等程序结束释放全局变量。动态存储区存储的数据：1、函数形参2、函数中的自动变量（未加static）的局部变量3、函数调用时的现场保护和返回地址等。存储方式：静态存储和动态存储。具体包括：自动的（auto）、静态的（static）、寄存器的（register）和外部的（extern）自动变量：函数中局部变量，不使用关键字static加以说明，包括函数的形参和函数中自定义的变量。表示存储类型的auto可以省略。静态局部变量：希望函数中定义的局部变量在函数调用结束之后不消失而保留原值，占用存储单元不释放，下一次该函数调用时，在上一次保留的值的基础上继续运行。静态局部变量赋初值实在编译阶段，只赋值一次。如果定义静态局部变量时不赋值，编译系统自动赋值0（数值型变量）或空指针（字符型变量）。静态局部变量对于其它函数不能引用。用register声明起存期变量：寄存器变量：局部变量的值放在CPU中的寄存器中，需要用时直接从寄存器取出进行运算。extern声明外部变量（全局变量）：全局变量（外部变量）是在函数之外定义的变量，作用域是从变量的定义到本程序文件的结束。编译时将全局变量分配在静态存储区。extern声明全局变量，以扩展全局变量的作用域：如果在定义点之前的函数想引用定义的全局变量，则必须在引用之前用关键字extern对该变量做外部变量声明，表示该变量是一个将在下面定义的全局变量。这种声明叫提前引用声明。2.在多文件的程序中声明外部变量一个C++程序可以由一个或多个源程序文件组成。对于多源文件的形式，想在一个文件中引用另一个文件中已定义的外部变量正确的做法：在任一个文件中定义外部变量，在另一个源文件中对外部变量用extern的外部声明。extern扩展了外部变量的作用域，但是执行一个文件中函数时，可能会改变全局变量的值，从而会影响另一文件中的函数执行结果。用static声明的静态外部变量：希望某些外部变量只限于被本文件引用，而不能被其它文件引用。只用与本文件的外部变量（局部变量）称为静态外部变量。注意：不要误认为用static声明的外部变量才采用静态存储方式（存放在静态存储区），不加static的是动态存储（存放在动态存储区）。加extern或不加extern的外部变量都用静态存储方式，只是作用范围不同，都是编译时分配内存。变量属性小结：存储类别：auto、static、register、extern作用域：全局变量、局部变量存储器：静态存储、动态存储auto、static、register只能用于变量的定义。extern只能用于声明已定义的外部变量，而不能用于变量的定义。作用域：局部变量：自动变量（动态局部变量）、静态局部变量、寄存器变量、形式参数（可以定义为自动变量、寄存器变量）全局变量：静态外部变量（只限于本源文件）、外部变量（非静态外部变量，允许其它文件引用）存储器：动态存储、静态存储。静态存储：程序整个运行时间都存在、动态存储：在调用函数时分配单元。动态存储：自动变量、寄存器变量、形式参数静态存储：静态局部变量、静态外部变量、外部变量变量值存放位置：内存中静态存储区：静态局部变量、静态外部变量、外部变量动态存储区：自动变量和形式参数CPU中寄存器：寄存器变量预处理命令：宏定义文件包含条件编译预处理指令以#开头。宏定义：#define命令将一个指定的标识符（宏名）来代表一个字符串。#define标识符字符串还可以用#define命令来定义带参数的宏定义#define宏名（参数表）字符串文件包含处理include命令的两种形式：#include<文件名>或#include“文件名”条件编译：有时希望程序中某一部分只在满足一定条件下进行编译，也就是指定对程序中的一部分内容进行编译的条件，如果不满足这个条件就不便宜这部分内容。（1）#ifdef标识符 程序段1 #else 程序段2#endif（2）#ifndef标识符 程序段1 #else 程序段2#endif（3）#if表达式 程序段1#else 程序段2#endif数组的初始化用“{}”来实现除了单链表之外，还存在循环链表和双向链表。循环链表：单链表最后一个节点的指针指向头节点。将两个线性表合并为一个表时，设一个表为real1表示，另一个表为real2表示。合并的过程只需要5条语句。p=rear1->next;q=rear2->next;rear1->next=q->next;rear2->next=p;free(p)；voidLINSERT(LINKLIST*rear,DATATYPE2x){ LINKLIST*p; P=(LINKLIST*)malloc(sizeof(LINKLIST));p->data=x;p->next=NULL;if(rear->next==rear){ rear->next=p; p->next=rear; rear=p;}else{ p->next=rear->next->next; rear->next->next=p;}}双向链表：单链表满足查找后继元素，若要查找前驱元素，则须从头开始顺序向后查找。双向链表：可以方便的查找前驱节点。双向链表：3个域：1、数据域；2、指针域prior；3、指针域next。双向链表节点数据类项：typedefstructnode{ DATATYPE2data;structnode*prior,*next;}DLINKLIST;双向循环链表：将双向链表最后节点的next指针指向头节点，头节点的prior节点指向最后一个节点an。对于双向链表的基本操作：LENGTH、LOCATE、GET与单链表操作一致（设计一个方向的指针）。插入节点、删除节点有很大的不同。双向链表插入一个节点操作：在节点p之前插入一个节点的操作：voidDINSERT(DLINKLIST*p,DATATYPE2x){ DLINKLIST*s; s=(DLINKLIST*)malloc(sizeof(DLINKLIST)); s->data=x; p->prior->next=s;s->prior=p->prior;s->next=p;p->prior=s;}在双向链表中删除节点p的操作：voidDDELETE(DLINKLIST*p){ p->prior->next=p->next; p->next=p->prior;free(p);}顺序表与链表的关系：基于存储空间考虑：顺序表的存储空间是静态分配的。链表的存储空间是动态分配的。但是链表除了要存储数据之外还要存储指针，所以空间利用率不如顺序表。当线性表空间长度变化不大，存储空间可以事先估计时，可以采用顺序表。基于时间性能考虑： 顺序表是一种随机访问的线性表，可以快速实现数据的存取；链表是一种顺序访问的表，存取数据需要从头节点开始向后逐一扫描。 线性表频繁进行查找，很少进行插入或删除节点操作的采用顺序表。实例1：将一个无序的线性表删除重复节点（采用顺序表编写）。voiddeleseq(SEQUENLIST*q){ inti,j,k; for(i=0;i<q->len-1;i++) for(j=i+1;j<q->len;j++) if(q->data[i]==q->data[j]) { for(k=j+1;k<q->len;k++) q->data[k-1]=q->data[k]; q->len--; j--; }}实例2：在一个非递减有序的线性表中，插入一个值为x的元素，使插入后的线性表仍为非递减有序表，用带头节点的单链表编写算法。voidinsert_order(LINKLIST*head,DATATYPE2x){ LINKLIST*p,*h,*q;h=(LINKLIST*)malloc(sizeof(LINKLIST));h->data=x;h->next=NULL;p=head;q=head->next;while(q!=NULL&&q->data<x){ p=q;q=q->next;}h->next=q;p->next=h;}实例3：设L为带头节点的单链表，数据元素为递增有序，写一算法删除表中值相同的元素。voiddelelink(LINKLIST*L){ LINKLIST*p,*q; p=L->next; while(p&&p->next) { if(p->data==p->next->data) { q=p->next; p->next=q->next; free(q); } else p=p->next; }}实例4：在一个头指针所示的循环链表中，从表中任意一个节点p出发找到它的前驱节点。LINKLIST*prior(LINKLIST*p){ LINKLIST*q; q=p->next; while(q->next!=p) q=q->next; returnq;}TheNeXT在硬件基础上以软件实现功能。四位数码管点阵（8**）、红、绿可接液晶显示器16021864流水灯（8个发光二极管）键盘（4*4）和独立键盘电源按键（自锁式按键、触发式）晶振红外线接受管adcspIe2prom锁存器芯片（操作数码管和点阵）栈和队列：栈：只允许在表的一端进行删除或插入操作。队列：只允许在表的一端进行插入操作，在另一端进行删除操作。栈：先进后出或后进先出栈（stack）：只能在表的一端进行插入或删除操作的线性表，允许插入或删除操作的一端为栈顶（top）不允许插入或删除的另一端为栈底（bottom）。向栈顶插入元素的操作为入栈，删除栈底元素的操作为出栈。栈的基本操作：栈的初始化（Init_Stack(s)）;判断栈空的操作（Stack_Empty(s)）；入栈操作（Push_stack(s,x)）；出栈操作（Pop_stack(s)）;读栈顶元素（Gettop_Stack(s)）；栈置空操作（Clear_Stack(s)）；求栈的长度（StackLength(s)，返回栈s中的元素个数）。栈的顺序存储。顺序栈的数据类型：#definedatatypechar#defineMAXSIZE100typedefstruct{ datatypedata[MAXSIZE]; inttop;}SEQSTACK;定义一个指向顺序栈的指针：SEQSTACK*s;s->top=-1;//空栈s->top=MAXSIZE-1;//栈满。顺序栈的算法实现。初始化顺序栈：voidInit_Stack(SEQSTACK*s){ s->top=-1;}判断栈空操作intStack_Empty(SEQSTACK*s){ if(s->top==-1) return1; else return0;}入栈操作voidPush_Stack(SEQSTACK*s,datatypex){ if(s->top==MAXSIZE-1) printf(“stackfull\n”); else { s->top++; s->data[s->top]=x; }}读栈顶元素datatypeGettop_Stack(SEQSTACK*s){ datatypex; if(Stack_Empty(s)) { printf(“StackEmpty\n”);returnNULL;}else{ x=s->data[s->top]; returnx;}}出栈操作datatypePop_Stack(SEQSTACK*s){ datatypex;if(Stack_Empty(s)){ printf(“StackEmpty\n”); returnNULL;}else{ x=s->data[s->top]; s->top--; returnx;}}栈置空操作voidClear_stack(SEQSTACK*s){ s->top=-1;}求栈长度操作intStackLength(SEQSTACK*s){ returns->top+1;}栈的链式存储表示有名（链栈）：链栈的数据类型：typedefstructstacknode{ datatypedata; structstacknode*next;}LINKSTACK;用链栈定义栈顶指针：LINKSTACK*top;在链栈中栈顶总是第一元素，栈底总是最后一个元素。链栈栈顶指针top唯一确定一个链栈，当top=NULL时，链栈为空栈。链栈的好处：只要存在存储空间就不会有栈满情况。链栈基本操作：初始化空栈voidInit_Stack(LINKSTACK*top){ top=NULL;}判断栈空操作intStack_Empty(LINKSTACK*top){ if(top==NULL) return1; else return0;}（3）入栈操作voidPush_Stack(LINKSTACK*top,datatypex){ LINKSTACK*p; p=(LINKSTACK*)malloc(sizeof(LINKSTACK));p->data=x;p->next=top;top=p;}（4）读栈顶元素操作datatypeGettop_Stack(LINKSTACK*top){ datatypex; if(top==NULL) { printf(“stackempty\n”); returnNULL; } else { x=top->data; returnx; }}出栈操作datatypePop_Stack(LINKSTACK*top){ datatypex; LINKSTACK*p; if(top==NULL) { printf(“Stackempty\n”); returnNULL;}else{

p=top; top=top->next; x=p->data;free(p);returnx;}}栈的应用：设单链表中存放着n个字符，试编写一算法，判断该字符串是否为中心对称关系。intpan(LINKLIST*head){ inti;chara;LINKLIST*p=head;SEQSTACKq,*s;s=&q;s->top=-1;for(i=0;i<n/2;i++){ push(s,p->data); p=p->next；}if(n%2==1) p=p->next;while(p){ a=pop(s); if(a==p->data) p=p->next; else return0;}return1;}队列：每一新事件只能在队尾插入，每次先处理队头事件，即先输入和保存的事件，当队头事件处理完毕之后，从事件队列中删除，还可以查询事件队列中剩余的事件。队列（queue）：只能在表的一端进行插入在表的另一端进行删除操作的线性表。允许插入的一端为队列尾（tail），允许删除的另一端为队列头（front）。向队尾添加元素为“入队”；删除队列头元素称为“出队”。队头元素总是最先进入队列，也总是最先出队列。队尾元素总是最后进队列，也是最后出队列。队列满足“先进先出”（FIFO）。队列的基本操作：队列初始化：Init_Queue(q)构造一个空队列。判队空操作：Queue_Empty(q)，若q队列为空返回1，否则返回0。入队列操作：Add_Queue(q,x)在队列q的尾部插入一个元素x。读队列操作：Gethead_Queue(q)返回队列头元素；若队列为空返回0。出队列操作：Del_Queue(q)删除队列头元素，并返回该头元素，若队列为空队列，返回值为0。队列置空操作：Clear_Queue(q)将队列q置为空队列。求队列长度操作：QueueLength(q)返回队列q中元素个数。队列顺序存储表示：采用顺序存储结构存储的队列简称为顺序队列。一般采用以为数组来作为队列的顺序存储空间另外还设有两个指针：一个指向队头元素front，一个指向队尾元素rear。随着元素的入队或出队：font和rear会相应的发生变化。c语言描述顺序队列数据类型：#definedatatypechar#defineMAXSIZE100typedefstruct{ datatypedata[MAXSIZE]; intfront,rear;}SEQUEUE;采用顺序队列数据类型定义指针变量：SEQUEUE*q;初始化队列时：q->front=q->rear=-1；插入一个元素x：q->rear++;q->data[q->rear]=x尾指针总是指向队尾元素所在位置；头指针front总是指向队列中第一个元素的前面一个位置。出队操作：队头删除一个数据元素，有q->front++.当q->rear=MAXSIZE-1时，队列满。假溢出：假溢出出现的原因：“队尾入，队头出”，解决方案：采用循环队列，将队列存储空间的最后一个位置绕到第一个位置，即q->data[0]接在q->data[MAXSIZE-1]之后。循环队列插入一个新元素：q->rear=q->rear+1;if(q->rear==MAXSIZE) q->rear=0;或采用一种更简便的方式：q->rear=(q->rear+1)%MAXSIZE;相对应的循环队列删除一个元素：q->front=q->front+1;if(q->front==MAXSIZE) q->front=0;换成一种更简便的方式：q->front=(q->front+1)%MAXSIZE;循环队列初始化：q->front=q->rear=0;循环队列队满：(q->rear+1)%MAXSIZE=q->front;循环队列队空操作：q->front=q->rear;循环队列——初始化队列：voidInit_Queue(SEQUEUE*q){ q->front=0; q->rear=0;}循环队列——判队空操作：intQueue_Empty(SEQUEUE*q){ if(q->front==q->rear) return1; else return0;}循环队列——入队操作：voidAdd_Queue(SEQUEUE*q,datatypex){ if((q->rear+1)%MAXSIZE==q->front) printf(“Queuefull\n”); else{ q->rear=(q-rear+1)%MAXSIZE; q->data[q->rear]=x;}}循环队列——读队列操作：datatypeGethead(SEQUEUE*q){ datatypex; if(Queue_Empty(q)) { printf(“Queueempty\n”); returnNULL; } else{x=q->data[q->front+1]%MAXSIZE; returnx;}}循环队列——队列空操作voidClear_Queue(SEQUEUE*q){ q->front=0; q->rear=0;}循环队列——队列长度操作：intQueueLength(SEQUEUE*q){ intlen; len=(MAXSIZE+q->rear-q->front)%MAXSIZE; returnlen;}linux的特点免费的、开源的支持多线程、多用户安全性好对内存和文件管理优越linux：操作相对困难。linux最小只需要4MByte->嵌入式开发kentompson火星计划失败（30到300分时操作系统）开发了一个fileserversystem【文件系统】。Dennisrichres、kentomp