数据结构课堂笔记di第一三章.docx
- 文档编号:12159034
- 上传时间:2023-06-04
- 格式:DOCX
- 页数:24
- 大小:115.52KB
数据结构课堂笔记di第一三章.docx
《数据结构课堂笔记di第一三章.docx》由会员分享,可在线阅读,更多相关《数据结构课堂笔记di第一三章.docx(24页珍藏版)》请在冰点文库上搜索。
数据结构课堂笔记di第一三章
一、数据:
是对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
它是计算机程序加工的“原料”。
二、数据元素:
是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。
一个数据元素可由若干个数据项组成。
数据项是数据的不可分割的最小单位。
三、数据对象:
是性质相同的数据元素的集合,是数据的一个子集。
四、数据机构:
是相互之间存在一种或多种特定关系的数据元素的集合。
在任何问题中,数据元素都不是孤立存在的,而是在它们之间存在着某种关系,这种数据元素相互之间的关系称为结构。
根据数据元素之间关系的不同特性,通常有下列4类基本结构:
(1)集合------------数据元素仅有同属一个关系的关系
(2)线性结构----------结构中数据元素之间存在一个对一个的关系(3)树形结构------------结构中的数据元素之间存在一个对多个的关系(4)图状结构或网状结构-----------结构中的数据元素之间存在多个对多个的关系
五、元素在存贮结构
(1)物理结构(存储结构):
它包括数据元素的表示和关系。
(2)逻辑结构
六、位bit:
在计算机中表示信息的最小单位是二进制的一位
七、元素element/节点node:
位串
八、数据域:
当数据元素由若干数据项组成时,位串中对应于各个数据项的子位串
九、数据元素之间的关系在计算机中有两种不同的表示方法,顺序映像和非顺序映像,并由此得到两种不同的存储结构:
顺序存储结构(借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系)和链式存储结构(借助指示元素存储地址的指针表示数据元素之间的逻辑关系)。
类C语言语句:
(1)预定义常量和类型:
#defineTRUE1FALSE0
#defineOK1ERROR0
#defineINFEASIBLE-1OVERFLOW-2
(2)数据元素类型ElemType
(3)赋值语句:
简单赋值变量名=表达式;
串联赋值变量名1=变量名2=…=变量名k=表达式;
成组赋值(变量名1,…,变量名k)=(表达式1,…,表达式k);
结构名=结构名;
结构名=(值1,…,值k);
变量名[]=表达式;
变量名[起始下标..终止下标]=变量名[起始下标..终止下标];
交换赋值:
变量名<->变量名;
条件赋值:
变量名=条件表达式?
表达式T:
表达式F;
(4)选择语句有
条件语句1if(表达式)语句;
条件语句2if(表达式)语句;
else语句;
开关语句1switch(表达式){
case值1:
语句序列1;break;
…
case值n:
语句序列n;break;
default:
语句序列n+1;
}
开关语句2switch(表达式){
case条件1:
语句序列1;break;
…
case条件n:
语句序列n;break;
default:
语句序列n+1;
}
(6)循环语句有:
for语句for(赋初值表达式序列;条件;修改表达式序列)语句;
while语句while(条件)语句;
do-while语句do{
语句序列;
}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
(11)逻辑运算约定
与运算&&:
对于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?
覆盖算不算删除?
答:
不算。
删除正是为了得到。
SeqlistDelete(A[],n,i)
{
if(i<1ORi>n)
{
Printf(“参数非法”);
}return0;
}
Else
{
for(k=i+1;k A[k-1]<=A[k]; n<=n-1; returnn; } 栈(heap) 五、堆栈(stack): 是一种特殊形式(表的插入和删除)的线性表 限定在表的。 。 。 运行 作业1: 线性表中元素为整型,以50为界,小于50在左,大于50在右。 作业讲解: x<=A[i]; while(A[j]>=xandi { j<=j-1; if(A[j] { A[i]<=A[j]; i<=i+1; } while(A[i] i<=i+1; if(A[i]>=x) { A[j]<=A[i]; j<=j-1; } 第三章: 链式存贮结构的线性表 一、为什么要引入链表? 顺序表的优点: 结构紧凑,存储空间利用率高,操作简单。 缺点: 它需要一块连续的存贮空间。 多任务多生产 则找不出谁是前驱谁是后继 插入a1: *p=a1;改为: p->date=a1;指针p指向对象date=a1,该对象是一个结构体,指向结构体里a1那部分 删除a1并把存储空间解放: free(p); 动态存储结构 地址=malloc(大小);字节 free(p); 区别: 数组: 编译时确定(静态) 链表: 编译时确定(动态)<原本不存在> P=(ElemType*)=malloc(sizeof(ElemType)); 改为NODE*改为NODE 因为是无类型指针,所以必须强制转换。 Typedef类型定义structnodeNODE(定义为新的类型) 二、链表的构造 q<=NULL; for(j=n;i>=1;i--) { p<=(NODE*)malloc(sizeof(NODE)); p->date<=an;将an替换为ai注: i此处为n-1 p->next<=NULL;把指针设为空指针,替换为q q<=p; } 考虑链表的头指针 当ai未插入时: 算法: CreatLinkList(n)构造链表,n为节点 { q<=NULL; for(i=n;i>=1;i--) { p<=(NODE*)malloc(sizeof(NODE)); scanf(ai); p->date<=ai; p->next<=q; q<=p; } return(p); } 注: 此时p、q一样∵已被赋值给对方 作业4: 倒过来。 从前节点到后节点。 头指针headp<=head; 从头指针出发,依次输出节点。 可用for循环或while循环(不确定循环次数时用) p<=head; while(p=\NULL) { printf(p->data); p<=p->next; } 三、链表的插入算法: 假定: 在表中值为x的节点前面插入一个值为y的节点。 分析: 1.空链 2.表中第1个节点的值为x 3.表中有一个值为x的节点 4.表中没有值为x的节点 5.表中有多个值为x的节点。 NODE*InsertLinkList(head,x,y) { q<=(NODE*)malloc(sizeof(NODE)); q->data<=y; q->next<=NULL; if(head=NULL) head<=q; elseif(head->date=x) { q->next<=head; head<=q; } else { r<=head; p<=head->next; while(p->data=/xandp=\NULL) p<=p->next; if(p=\NULL) { q->next<=p; r->next<=q; } else r->next<=q; } return(head); } 假定: 删除表中值为x的节点 分析: 1.空表; 2.第1个节点的值为x; 3.在表中有值为x的节点; 4.在表中没有值为x的节点 NODE*=DeleteLinkList(head,x,t)(返回指针)a.值参callbyvalue {b.变参callbyaddress s<=NULL; if(head=NULL) printf("这是一个空表") elseif(head->data=x) { s<=head; head<=head->next; } else q<=head;(返回内容不同) p<=head->next; while(p->data=\xandp->next=\NULL) { q<=p; p<=p->next; } if(p->data=x) { s<=p; q->next<=p->next; } else printf("表中没有值为x的节点"); } if(s=\NULL) { t<=s->data; 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<=\NULLandPb<=\NULL) { ct<=Compare(Pa->exp,Pb->exp);假定有compare比较 switch(ct) { case">": attach(PC,Pa->coof,Pa->exp); Pa<=Pa->next; break; case"=": m<=Pa->coof+Pb->coof attach(PC,m,Pa->exp); Pb<=Pa->next; break; case"<": attach(PC,Pb->coof,pb->exp); Pb<=Pb->next; break; } } while循环可能出现一条链结束了一条链还未结束∴还剩下一节结点,但可能同时结束 while(Pa=\NULL) { attach(PC,Pa->coof,Pa->exp); Pa<=Pa->next; } while(Pb=\NULL) { attach(PC,Pb->coof,Pb->exp); Pb<=Pb->next; } 该部分算法将剩余部分未加的链挂上去但PC走动,ST仍指向空结点 PC<=ST->next; free(ST); } 如图: a.比较指数的大小 b.比较完后考虑是否相加,还是挂在一条链上 从前往后产生链。 产生一个结点往上挂。 例题: 一元多项式相加, 前提: 不破坏原本两条链,相加求第三条链 分析: 数据结构 必须考虑抵消指数的情况m=\0. 用项对应结点 Compare(a,b) { if(a>b) { if(a>b) return('>'); elseif(a=b) return('='); else return('<'); } } } voidattach(PC,coof,exp) { 栈: 是限定仅在表尾进行插入或删除操作的线性表 表尾(栈顶)表头(栈底) 压栈算法: intPushStack(s[],top,x) { if(top>=SMAX) { printf("overlow"); return0; } else { S[top]<=x; top=top++; } } 出栈算法: ElemTypePopstack(s[],top,bottom) { if(top<=bottom) { printf("overlow"); } return0; } else { top<=top-1; y<=S[top]; returny; } 作业2: 为了节省空间,两个栈共享一段内存,写出这两个栈的压栈及出栈算法。 队列: 1.什么是队列? 也是一种特殊的线性表(插入在表的一端,删除在表的另一端) 区别于线性表: 插入、删除在同一端。 2.队列的操作: 1.插入。 如何判断其满? intQueueInsert(Q[],front,rear,x) { if(rear>=QMAX) { printf("Overlow"); return0; } else { rear=rear+1; Q[rear]<=x; return1; } } 2.删除: ElemTypeQueueDelete(Q[],front,rear) { if(rear<=front) { printf("Overlow"); return0; } else { front=front+1; } } 以上为错误算法,rear rear=front指针重叠“假满”∵删除/插入一次无事,N次则无用了。 插入满了只能删除,rear、front均在尾,插入为满,删除为空∴成为了无用队列。 rear=100 rear+1=\101 =1 mol->%求余 (100+1)%=1->即令100+1=1 正确的队列插入与删除算法如下: intQueueInsert(Q[],front,rear,x) { if((rear+1)modQMAX=front) { printf("Overlow"); return0; } else { modQMAX Q[rear]<=x; return1; } } ElemTypeQueueDelete(Q[],front,rear) { if(rear<=front) { printf("Overlow"); return0; } else { modQMAX } 3.队列的应用keyboardbuffer32byte 如何解决“假满”? ---------还有空的地方却不能再插入。 答: 接为环状(上弯下弯不同) 元素本身是字符型。 1Byte=指针4Byte 总结: 优点: 1.不要求连续的、大块的内存,充分地利用内存空间 2.动态的存储结构 不足: 1.空间复杂度增加 2.操作(算法)复杂些 作业4: 给定一个链表,将其倒过来。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课堂 笔记 di 第一