《数据结构课堂笔记(di第一-三章)》由会员分享，可在线阅读，更多相关《数据结构课堂笔记(di第一-三章)（17页珍藏版）》请在金锄头文库上搜索。
1、一、数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。它是计算机程序加工的“原料”。二、数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。三、数据对象：是性质相同的数据元素的集合，是数据的一个子集。四、数据机构：是相互之间存在一种或多种特定关系的数据元素的集合。在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构。根据数据元素之间关系的不同特性，通常有下列4类基本结构：（1）集合-数据元素仅有同属一个关
2、系的关系（2）线性结构-结构中数据元素之间存在一个对一个的关系（3）树形结构-结构中的数据元素之间存在一个对多个的关系（4）图状结构或网状结构-结构中的数据元素之间存在多个对多个的关系五、元素在存贮结构（1）物理结构（存储结构）：它包括数据元素的表示和关系。（2）逻辑结构六、位bit：在计算机中表示信息的最小单位是二进制的一位七、元素element/节点node：位串八、数据域：当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串九、数据元素之间的关系在计算机中有两种不同的表示方法，顺序映像和非顺序映像，并由此得到两种不同的存储结构：顺序存储结构（借助元素在存储器中的相对位置来表示数据
3、元素之间的逻辑关系）和链式存储结构（借助指示元素存储地址的指针表示数据元素之间的逻辑关系）。类C语言语句：（1）预定义常量和类型：#define TRUE 1 FALSE 0#define OK 1 ERROR 0#define INFEASIBLE -1 OVERFLOW -2(2)数据元素类型ElemType(3)赋值语句：简单赋值 变量名=表达式；串联赋值 变量名1=变量名2=变量名k=表达式；成组赋值 （变量名1，变量名k）=（表达式1，表达式k）； 结构名=结构名； 结构名=（值1，值k）； 变量名=表达式； 变量名起始下标.终止下标= 变量名起始下标.终止下标；交换赋值：变量名变量
4、名；条件赋值：变量名=条件表达式？表达式T：表达式F；（4）选择语句有条件语句1 if（表达式）语句；条件语句2 if（表达式）语句；else语句；开关语句1 switch(表达式)case值1：语句序列1；break; case值n：语句序列n；break;default:语句序列n+1;开关语句2 switch(表达式)case条件1：语句序列1；break; case条件n：语句序列n；break;default:语句序列n+1;(6)循环语句有：for语句 for（赋初值表达式序列；条件；修改表达式序列）语句；while语句 while（条件）语句；do-while语句 do 语句序列
5、； while（条件）；（7）结束语句有函数结束语句 return表达式； return；case结束语句 break；异常结束语句 exit（异常代码）；（8）输入和输出语句有：输入语句 scanf（格式串，变量1，变量n）；输出语句 printf（格式串，表达式1，表达式n）；通常省略格式串。（9）注释单行注释/文字序列（10）基本函数有：求最大值 max（表达式1，表达式n）求最小值 min（表达式1，表达式n）求绝对值 abs（表达式）求不足整数值 floor（表达式）求进位整数值 ceil（表达式）判定文件结束 eof（文件变量）或eof判定行结束 eoln（文件变量）或eoln（1
6、1）逻辑运算约定与运算&：对于A&B，当A的值为0时，不再对B求值。或运算|：对于A|B，当A的值为非0时，不再对B求值。算法：是对特定问题求解步骤的一种描述，它是指令的有限序列。（1）有穷性（2）确定性（3）可行性（4）输入（5）输出算法设计要求：（1）正确性（2）可读性（3）健壮性（4）效率与低存储量需求线性表：是最常用且最简单的一种数据结构。一、线性表：除表中的第一个元素外，其余元素仅有一个前驱。除表中最后一个元素外，其余元素仅有一个后继。二、线性表的存贮结构1.解决存贮问题2.反映元素之间关系三、线性表的操作：1.插入一个元素2.删除一个元素3.查找一个元素4.排序怎么删除ai？覆盖算
7、不算删除？答：不算。删除正是为了得到。SeqlistDelete(A,n,i)if(in)Printf(“参数非法”);return 0;Elsefor(k=i+1;kn;k+)Ak-1=Ak;n=n-1;return n;栈（heap）五、堆栈（stack）：是一种特殊形式（表的插入和删除）的线性表限定在表的。运行作业1：线性表中元素为整型，以50为界，小于50在左，大于50在右。作业讲解：x=x and ij) j=j-1; if(Ajx) Ai=Aj; i=i+1;while(Aix and xj)i=x)Aj=Ai;jdate=a1;指针p指向对象date=a1，该对象是一个结构体，指
8、向结构体里a1那部分删除a1并把存储空间解放：free（p）； 动态存储结构地址=malloc（大小）；字节free（p）；区别：数组：编译时确定（静态）链表：编译时确定（动态）P=(ElemType*)=malloc(sizeof(ElemType); 改为NODE* 改为NODE因为是无类型指针，所以必须强制转换。Typedef 类型定义struct node NODE（定义为新的类型）二、链表的构造q=1;i-)pdatenext=NULL;把指针设为空指针，替换为qq=p;考虑链表的头指针当ai未插入时：算法：CreatLinkList(n) 构造链表，n为节点q=1;i-)pdate
9、next=q;q=p;return(p);注：此时p、q一样已被赋值给对方作业4：倒过来。从前节点到后节点。头指针head p=head;从头指针出发，依次输出节点。可用for循环或while循环（不确定循环次数时用）pdata);pnext;三、链表的插入算法：假定：在表中值为x的节点前面插入一个值为y的节点。分析：1.空链2.表中第1个节点的值为x3.表中有一个值为x的节点4.表中没有值为x的节点5.表中有多个值为x的节点。NODE*InsertLinkList(head,x,y)qdatanext=NULL;if(head=NULL)headdate=x)q-next=head;head
10、=q; elser=head;pnext;while(p-data=/x and p=NULL)pnext;if(p=NULL)q-nextnextnext=q;return(head); 假定：删除表中值为x的节点分析：1.空表； 2.第1个节点的值为x； 3.在表中有值为x的节点； 4.在表中没有值为x的节点NODE *=DeleteLinkList(head,x,t) （返回指针）a.值参 call by value b.变参call by addresssdata=x)s=head;headnext;elseq=head; （返回内容不同）pnext;while(p-data=x an
11、d p-next=NULL)q=p;pnext;if(p-data=x)snextnext;elseprintf(表中没有值为x的节点)；if(s=NULL)tdata;free(s);return(head); （返回值）四、链式存贮结构的栈五、链式存贮结构的队列六、循环链表L=(a1,a2,an) ai存在元素双向链表插入：值为x的节点前面加入值为y的节点删除值为x的节点：一个指针指向一个整体，指向同个整体的必须是相同的指针，不管是P还是m。八、十字链表NODE *PoliAdd (ah,bh)Pa=ah;Pb=bh;已知头指针分别为ah和bh的两条链。PC=(NODE*)malloc(sizeof(NODE);ST=PC;while(Pa=NULL and Pb=NULL)ctexp,Pb-exp);
