数据结构基础知识汇总

数 据 结 构,主讲：,课程相关,计算机学科核心课程多编程(手写)，多调试(上机)学时：成绩核算：作业：上机前写完,上机时调试,多思考多问,本章要点,补充：C基础回顾,C程序概述 基本语法(数据类型 运算符 控制结构 函数) C指针与链表,#include #define typedef int ElemType;void main( ) /函数次序不定 子函数声明与变量定义 执行语句组 返回值类型 函数名1(参数表) /函数功能及返回值说明 变量定义与函数声明 执行语句组 .返回值类型 函数名n(参数表) 变量定义与函数声明 执行语句组 ,1、C程序概述,结构：由若干函数(main函数、库函数、自定义函数)组成，main函数是程序入口，出口？ 函数包括函数头和函数体两部分，函数头分返回值类型、函数名和参数列表;函数体包括声明部分和执行部分，声明部分包括变量定义和函数的声明，执行部分包括各类语句(输入输出语句、赋值语句、结构控制语句和函数调用语句);语句以分号结束补充：换行 缩进 对齐 注释 命名(含义+规范:变量/函数/符号常量,代码调试：断点调试 常见错误,int getMax( x, y) int r; if(xy)r=x; else r=y; return(r);void main scanf(“%d,%d”, a, b); /*读入两整数，用逗号分隔 c=getMax(a,b); printf(“max=%cn”,c) ,#include,;,int a,b,c;,*/,& &, ,( ),是否需要进行函数声明int max(int x,int y);,%d,1、变量未定义或函数使用前未声明，缺少头文件2、丢分号和4、工作区问题、 cpp与c,int int,2、 基本语法数据类型,2、 基本语法运算符,2、 基本语法控制结构,2、 基本语法函数，参数传递值传递,2、 基本语法函数，参数传递引用传递,3、 指针与链表,谭浩强-C程序设计(第3版)-第十章指针,基本概念指针的定义及用法指针在数组访问中的应用指针与动态存储分配利用指针创建和操作链表,内存区的每一个字节有一个编号，该编号称为内存单元的地址或指针。若在程序中定义一个变量，在运行时会为其分配若干内存单元，其中第一个存储单元的编号称为该变量的地址或指针,int i; short j,k;scanf(“%d %d”,short *p; short j,k; p=,地址 指针 变量的地址 指针变量,某些变量专门用以存放别的变量的地址,称这类变量为指针变量，该类变量的类型称为指针类型,i,01234567,i,j,k,i,012345678,j,p,k,00000000000000000000000000000011,00000000000000000000000000000001,p,定义格式：基类型 *指针变量名如：short j; short *p; p=,(1)通过指针对变量进行读写时如何知道需要读写的字节数？在定义指针变量时必须指定基类型，且变量的类型和指针的基类型要一致！(2)指针类型与整数类型不同.只能将变量的地址赋给一个指针变量,而不能将一个常数赋给一个指针变量(零除外,指针值为0意味着没指向任何变量)。指针变量的加1或减1实际移动sizeof(基类型)(3)在定义变量时使用*表示所定义变量是指针类型，在普通语句中使用*表示“取指针变量所指向存储单元的值”.如int i=5; int *p; p=,指针变量的定义与用法,i,234567,j,p,00000000000000000000000000000010,p,C语言中,一维数组的数组名是指向数组首元素的指针常量，该指针常量的基类型就是数组元素的类型，值是数组的起始地址。可通过数组名用下标法访问数组元素，如果用该指针常量给一个同类型的指针变量赋值，则可借助该指针变量用指针法访问数组元素,指针法访问数组,如： int a10; int *p; p=a ; /*也可用 int *p= 说明：指针加1或减1则指针指向的单元移动并非1，而是根据基类型所占字节数移动。指针法速度比下标法快,动态存储分配函数 #includevoid * malloc(unsigned size); /开辟成功返回空间首地址 /基类型暂定为void,用时进行强制类型转换，失败返回0void free(void *p);/销毁从p所指地址开始的一次性开/辟的存储空间,注意释放的含义及p的值不变基类型为int的指针类型“可以”当作基类型为int的动态数组名用,指针与动态存储分配,静态数组,#define N 10void main() int a10;/a为指针常量 for(int i=0;inext /新结点指针值不赋空会如何？,算法思路：开辟头结点，设一指针指向表尾节点，之后循环n次：每次开辟一个新结点，输入数据域值后拼接到表尾节点的后面，表尾节点后移。,链表的输出,void ListPrint_L(LinkList L) /输出带头结点的链表L各数据元素的值 LNode *curPtr; if(!L | !L-next) printf(“空表!”); curPtr=L-next; while(curPtr!=NULL) OutputElem(curPtr-data) ); curPtr=curPtr-next; /思考+curPtr? ,算法思路：设指针curPtr指向首元节点，只要curPtr取值不空(指向的结点存在):输出curPtr所指结点数据域的值，curPtr后移。,链表结点的删除,void ListDelete_L(LinkList L, int i, ElemType e) /功能及返回值说明,注意带头结点 /思路： ,作业2：仿照课堂例题实现成绩表相关操作,自定义类型LinkList:数据域为ElemType类型的单链表实现如下函数 ListCreate_L ListPrint_L ListDelete_L编写主函数对上述函数进行测试a完整的可运行的程序，注意编码规范和注释b 分析与作业1程序的异同,#include#include#include#define OK 1#define ERROR 0#define OVERFLOW -1 typedef struct Student char stuName20; char courseName20;float score;Score;typedef Score ElemType;typedef ElemType* SqList; /学生表类型,实为学生数组类型,动态typedef int Status;Status InputSco(Score ,typedef struct LNode ElemType data; /数据域 struct LNode * next; /指针域LNode,* LinkList;Status ListCreate_L (LinkList &L, int n)/创建含n个元素带头结点的单链表,成功返回OK,并用L带回首址/创建失败返回ERROR /思路:void ListPrint_L (SqList L, int n)/表含n个元素，输出表信息/思路:Status SqListDelete (SqList L, int n, int i,ElemType &s)/表含n个元素，删除第i个位置的的元素并带回/思路:备份原表中第i个元素, 第i+1至n个记录依次前移,Status ListCreate_Sq (SqList &L, int n)/创建含n个元素的顺序表,成功返回OK,并用L带回首址/创建失败返回ERROR /思路:开辟数组，循环n次：每次输入一个元素信息/注意边界情况的处理，n非法，内存溢出void ListPrint_L (SqList L, int n)/表含n个元素，输出表信息/