C -数据结构

数据结构数据结构数据结构：是一门研究非数值计算的程序设计问题中计算机操作对象以及它们之间的关系和操作等等的学科。基本概念数据：是对客
观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素：是数据的基本单位，在计算机程序
中通常作为一个整体进行考虑和处理。数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。主要内容1.1线性表以及
其应用1.2栈、队列1.3排序、查找1.1线性表以及其应用（1）线性表分为静态线性表和动态线性表静态线性表
特征：表中节点的存储是连续的，占用一块连续存储区，一般节点的数量是固定的；存储表示如下图数据结构如下图线性表顺序存
储结构特定：借助元素在存储器中的相对位置（即，物理位置相邻）来表示数据元素之间的逻辑关系。缺点：插入、删除时，需移动大
量数据。一次性分配内存空间。表的容量难以扩充。1.1线性表以及其应用（2）动态线性表特征：表中节点的存储
是不连续的，一般节点的数量是不固定的；存储表示如下图数据结构如下图链式存储结构链式存储结构是计算机中的另一种最基本
和最主要的数据存储结构。和顺序存储结构不同，初始时链式存储结构为空链，每当有新的数据元素需要存储时用户向系统动态申请所需的存
储空间插入链中。链式存储结构每个结点有两个域，其中存储数据元素信息的域称为整数域；存储直接后继存储位置的域称为指针域。
structNode{intdata;structNodeNex
t;};typedefstructNodeNode_t;链式存储结构存储线性结构数据元素集合的方法是用结
点（Node）构造链。线性结构数据元素的特点是：除第一个和最后一个元素外，每个元素只有一个惟一的前驱和一个惟一的后继。链式结构
中每个结点除数据域外还有一个或一个以上的指针域，数据域用来存放数据元素，指针域用来构造数据元素之间的关系。只有一个指针域的结点结构
如图所示。根据指针域的不同和结点构造链的方法不同，链式存储结构存储线性结构数据元素的方法主要有单链、单循环链和双向循环
链等三种。这三种结构中每一种又有带头结点结构和不带头结点结构两种。头结点是指头指针所指的不存放数据元素的结点。其中，带头结
点的链式结构在表的存储中更为常用，不带头结点的链式结构在堆栈和队列的存储中更为常用。我们把图中头结点的数据域部分涂上阴影，以
明显表示该结点为头结点。图2和图3中的指针域为指向下一个结点的指针。图4中结点右部的指针域为指向下一个结点的指针，结点左部的
指针域为指向上一个结点的指针。在以后的图示中，头指针将用head表示。图中的符号“∧”表示空指针，空指针在算法描述中用N
ULL表示。空指针是一个特殊标识，用来标识链的结束。NULL在C中宏定义为0，因此空指针在C中也就是0地址。为与顺序表中
数据元素从a0开始相一致，讨论链表时数据元素也从a0开始。链式存储结构也可以方便地存储非线性结构的数据
元素。链式存储结构存储非线性结构数据元素的最典型的例子是链式结构的二叉树。添加插入删除循环链表(circularl
inkedlist)循环链表是表中最后一个结点的指针指向头结点，使链表构成环状特点：从表中任一结点出发均可找到表中其他结点
，提高查找效率操作与单链表基本一致,循环条件不同单链表p或p->next=NULL循环链表p或p->next=H
双向链表双向链表(Doublelinkedlist): 在单链表的每个结点里再增加一个指向其直接前趋的指针域pr
ior。这样就形成的链表中有两个方向不同的链，故称为双向链表。双向链表（doublelinkedlist）结点定义栈
和队列栈和队列是两种特殊的线性表，是操作受限的线性表栈（stack）一、栈的定义和特点定义：限定仅在表尾进行插入或删除操作
的线性表，表尾—栈顶，表头—栈底，不含元素的空表称空栈特点：先进后出（FILO）或后进先出（LIFO）栈的表示和实现栈有两种
存储表示方法:顺序栈链栈顺序栈实现：链栈队列队列的定义及特点定义：队列是限定只能在表的一端进行插入，在表的另一
端进行删除的线性表队尾(rear)——允许插入的一端队头(front)——允许删除的一端队列特点：先进先出(FIFO)队列
的顺序存储结构实现：用一维数组实现sq[M]存在问题设数组长度为M，则：当front=0,rear=M时，再有元素入队发生
溢出——真溢出当front?0,rear=M时，再有元素入队发生溢出——假溢出解决方案队首固定，每次出队剩余元素向下移动——
浪费时间循环队列基本思想：把队列设想成环形，让sq[0]接在sq[M-1]之后，若rear+1==M,则令rear=0;循环
队列上的插入操作（进队列）StatusEnQueue(SqQueue&Q,QElemTypee){if(
(Q.rear+1)%MXASIZE==Q.front)returnERROR;//队列满Q.
base[Q.rear]=e;//新元素存放到队尾
Q.rear=(Q.rear+1)%MAXQSIZE;//修改队为指示器returnOK;
}3）循环队列的删除把队头元素删除StatusDeQueue(SqQueue&Q,QElemTypee){
if(Q.front==Q.rear)returnERROR;//队列空
e=Q.base[Q.front];//删除当
前队头元素Q.front=(Q.front+1)%MAXQSIZE;//修改队头指示器
returnOK;}
链队列结点定义1.1线性表
以及其应用（3）线性表的应用－－索引表引出为便于对数据（线性数据和非线性数据）进行检索和更新；定义对数据进行索引的线性
表；分类索引可以分为单级索引和多级索引单级索引的图示（如下图）1.1线性表以及其应用（4）多级索引(以2级
为例)的图示1.1线性表以及其应用（5）使用索引表的好处可以将一些非线性的问题转换为了线性问题加以解决提高
数据检索的效率便于数据的更新1.2栈、队列栈栈的数据结构有什么特点栈有什么样的应用队列队列的数据结构有什么特点
队列有什么样的用途查找查找——也叫检索，是根据给定的某个值，在表中确定一个关键字等于给定值的记录或数据元素关键字——是数据
元素中某个数据项的值，它可以标识一个数据元素查找方法评价查找速度占用存储空间多少算法本身复杂程度平均查找长度ASL(Av
erageSearchLength)：为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值叫查找算法的~顺序查找
查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较算法描述折半查找查找过程：每次将待查记录所在区间缩小一半适用条
件：采用顺序存储结构的有序表算法实现设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值
初始时，令low=1,high=n,mid=?(low+high)/2?让k与mid指向的记录比较若k==r[mid].ke
y，查找成功若kr[mid].key，则low=mid+1重复上述操作，
直至low>high时，查找失败算法描述分块查找查找过程：将表分成几块，块内无序，块间有序；先确定待查记录所在块，再在块内查
找适用条件：分块有序表算法实现用数组存放待查记录,每个数据元素至少含有关键字域建立索引表，每个索引表结点含有最大关键字域和
指向本块第一个结点的指针算法描述哈希查找基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，
一次存取就能得到所查元素的查找方法定义哈希函数——在记录的关键字与记录的存储地址之间建立的一种对应关系叫~哈希函数是一种映象
，是从关键字空间到存储地址空间的一种映象哈希函数可写成：addr(ai)=H(ki)ai是表中的一个元素addr(ai)是a
i的存储地址ki是ai的关键字哈希表——应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫~
哈希查找——又叫散列查找，利用哈希函数进行查找的过程叫~从例子可见：哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任
何关键字的哈希函数值都落在表长允许的范围之内即可冲突：key1?key2，但H(key1)=H(key2)的现象叫~同义词：具
有相同函数值的两个关键字，叫该哈希函数的~哈希函数通常是一种压缩映象，所以冲突不可避免，只能尽量减少；同时，冲突发生后，应该有处
理冲突的方法哈希函数的构造方法直接定址法构造：取关键字或关键字的某个线性函数作哈希地址，即H(key)=key或
H(key)=a·key+b特点直接定址法所得地址集合与关键字集合大小相等，不会发生冲突实际中能用这种哈希函数的情况很少
数字分析法构造：对关键字进行分析，取关键字的若干位或其组合作哈希地址适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道
的情况平方取中法构造：取关键字平方后中间几位作哈希地址适于不知道全部关键字情况折叠法构造：将关键字分割成位数相同的几部分
，然后取这几部分的叠加和（舍去进位）做哈希地址种类移位叠加：将分割后的几部分低位对齐相加间界叠加：从一端沿分割界来回折送，然
后对齐相加适于关键字位数很多，且每一位上数字分布大致均匀情况除留余数法构造：取关键字被某个不大于哈希表表长m的数p除后所得余
数作哈希地址，即H(key)=keyMODp，p?m特点简单、常用，可与上述几种方法结合使用p的选取很重要；p选的
不好，容易产生同义词随机数法构造：取关键字的随机函数值作哈希地址，即H(key)=random(key)适于关键字长度不等的
情况选取哈希函数，考虑以下因素：计算哈希函数所需时间关键字长度哈希表长度（哈希地址范围）关键字分布情况记录的查找频率
处理冲突的方法开放定址法方法：当冲突发生时，形成一个探查序列；沿此序列逐个地址探查，直到找到一个空位置（开放的地址），将发生冲
突的记录放到该地址中，即Hi=(H(key)+di)MODm，i=1,2,……k(k?m-1)其中：H(key)——哈希函数
m——哈希表表长di——增量序列分类线性探测再散列：di=1,2,3,……m-1二
次探测再散列：di=12,-12,22,-22,32,……±k2(k?m/2)伪随机探测再散列：di=伪随机数序列再哈希法方
法：构造若干个哈希函数，当发生冲突时，计算下一个哈希地址，即：Hi=Rhi(key)i=1,2,……k其中：Rhi——
不同的哈希函数特点：计算时间增加链地址法方法：将所有关键字为同义词的记录存储在一个单链表中，并用一维数组存放头指针哈希查找
过程及分析哈希查找过程哈希查找分析哈希查找过程仍是一个给定值与关键字进行比较的过程评价哈希查找效率仍要用ASL哈希查找过
程与给定值进行比较的关键字的个数取决于：哈希函数处理冲突的方法哈希表的填满因子?=表中填入的记录数/哈希表长度哈希查找算法
实现 用线性探测再散列法处理冲突实现查找过程：同前删除：只能作标记，不能真正删除插入：遇到空位置或有删除标记的位置就可以
插入算法描述：用外链表处理冲突算法排序排序定义——将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列叫~
排序分类按待排序记录所在位置内部排序：待排序记录存放在内存外部排序：排序过程中需对外存进行访问的排序按排序依据原则插入
排序：直接插入排序、折半插入排序、希尔排序交换排序：冒泡排序、快速排序选择排序：简单选择排序、堆排序归并排序：2-路归并排序
基数排序插入排序直接插入排序排序过程：整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从
第2个记录开始，逐个进行插入，直至整个序列有序折半插入排序排序过程：用折半查找方法确定插入位置的排序叫~算法描述希尔排序
(缩小增量法)排序过程：先取一个正整数d1组和排序操作；直至di=1，即所有记录放进一个组中排序为止1.3排序、查找(1)排序常用的排序方法－－冒泡排序程序:
voidBubbleSort(inta[],n) { inti,j; intx;
for(i=1;i{//找到一组中最大的 if(a[j]>a[j+1]){//进行交换
x=a[j];a[j]=a[
j+1];a[j+1]=x; }
}; }}1.3排序、查找(2)常用的排序方法－－选择排序程序
: voidSelectSort(inta[],intn) { inti,j,k;in
tx for(i=1;ik=i-1; for(j=i;jif(a[j]}x=a[i-1];a[i-1]=a[k]
;a[k]=x; }}1.3排序、查找(3)查找常用的
查找方法－－折半查找折半查找的前提－－线性表是有序的程序 intBinarySearch(inta[],intN,
intx){ intlow=0,high=N-1;//定义并初始化区间下界和上界变量
intmid;//定义保存中点元素下标的变量 whil
e(low<=high){ mid=(low+high)/2; if(x==
a[mid])returnmid; elsei
f(xelselow=mid+1;//在右半侧 }
return-1;}算法描述交换排序冒泡排序排序过程将第一个记录的关键字与第二个记录的关键字进行比
较，若为逆序r[1].key>r[2].key，则交换；然后比较第二个记录与第三个记录；依次类推，直至第n-1个记录和第n个记录比
较为止——第一趟冒泡排序，结果关键字最大的记录被安置在最后一个记录上对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被
安置在第n-1个记录位置重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止算法描述快速排序基本思想：通过一
趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整
个序列有序排序过程：对r[s……t]中记录进行一趟快速排序，附设两个指针i和j，设枢轴记录rp=r[s]，x=rp.key初始
时令i=s,j=t首先从j所指位置向前搜索第一个关键字小于x的记录，并和rp交换再从i所指位置起向后搜索，找到第一个关键字大于
x的记录，和rp交换重复上述两步，直至i==j为止再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止选择排序
简单选择排序排序过程首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换再通过n-2次比较，
从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换重复上述操作，共进行n-1趟排序后，排序结束堆排序堆的定义：
n个元素的序列(k1,k2,……kn)，当且仅当满足下列关系时，称之为堆堆排序：将无序序列建成一个堆，得到关键字最小（或最大）的
记录；输出堆顶的最小（大）值后，使剩余的n-1个元素重又建成一个堆，则可得到n个元素的次小值；重复执行，得到一个有序序列，这个过程
叫~堆排序需解决的两个问题：如何由一个无序序列建成一个堆？如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？第二个
问题解决方法——筛选方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者
进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”问题Q1.为了描述并解决先进先出
特征的问题，我们一般会采用考虑以下哪种数据结构A,队列?????B,栈?????C,树?????D,二叉树Q
2.为了描述并解决先进后出特征的问题，我们一般会采用考虑以下哪种数据结构（??）。 ??A,队列?????B,栈???
??C,树?????D,二叉树Q3.对线性表进行二分法查找，其前提条件是A,线性表以顺序方式存储，并且按关键码值排好序
B,线性表以顺序方式存储，并且按关键码值的检索频率排好序C,线性表以链接方式存储，并且按关键码值排好序D,线性表以链接
方式存储，并且按关键码值的检索频率排好序例已知一组关键字(19,14,23,1,68,20,84,27,55,11,10
,79)哈希函数为：H(key)=keyMOD13,用链地址法处理冲突012
345678910111214^127796855198420231011^
^^^^^^^^^^^给定k值计算H(k)此地址为空关键字==k查找失败查找成功按处理冲突方
法计算HiYNYN例已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)
哈希函数为：H(key)=keyMOD13,哈希表长为m=16，设每个记录的查找概率相等
(1)用线性探测再散列处理冲突，即Hi=(H(key)+di)MODmH(55)=3冲突，H1=(3+1)MOD1
6=4冲突，H2=(3+2)MOD16=5H(79)=1冲突，H1=(1+1)MOD
16=2冲突，H2=(1+2)MOD16=3冲突，H3
=(1+3)MOD16=4冲突，H4=(1+4)MOD16=5
冲突，H5=(1+5)MOD16=6冲突，H6=(1+6)MOD16=7
冲突，H7=(1+7)MOD16=8冲突，H8=(1+8)MOD1
6=90123456789101112
131415ASL=(16+2+33+4+9)/12=2.514168275519208479
231110H(19)=6H(14)=1H(23)=10H(1)=1冲突，H1=(1+1)MOD16=2
H(68)=3H(20)=7H(84)=6冲突，H1=(6+1)MOD16=7冲突
，H2=(6+2)MOD16=8H(27)=1冲突，H1=(1+1)MOD16=2冲突
，H2=(1+2)MOD16=3冲突，H3=(1+3)MOD16=4H(11)=11H(1
0)=10冲突，H1=(10+1)MOD16=11冲突，H2=(10+2)MOD16=1
2(2)用链地址法处理冲突012345678910111214^127796
855198420231011^^^^^^^^^^^^ASL=(16+24+3+4)/
12=1.75关键字(19,14,23,1,68,20,84,27,55,11,10,79)Ch7_4.cCh7_5.c算
法描述例49386597761327i=238(3849)65
97761327i=365(384965)97761327i
=497(38496597)761327i=576(3849
657697)1327i=613(133849657697)
27i=1()i=7(133849657697)2
727jjjjjj977665493827(132738
49657697)排序结果：例i=1(30)137085
3942620i=213(1330)708539
42620i=76(61330394270
85)20…...i=820(6133039427
085)20sjmi=820(613303942
7085)20sjmi=820(613303942
7085)20sjmi=820(6133039
427085)20sji=820(613203039
427085)算法评价时间复杂度：T(n)=O(n2)空间复杂度：S(n)=O(1)Ch8_2.
c取d3=1三趟分组：132748554493865977
6三趟排序：4132738484955657697例初始
：4938659776132748554一趟排序：1327
485544938659776二趟排序：13448
38274955659776取d1=5一趟分组：493865
9776132748554取d2=3二趟分组：13274855
44938659776Ch8_3.c例49386597
76132748554#defineT3intd[]={5,3,1};j
i49133827一趟排序：1327485544938659
776jiji274jiji55ji38jijiji二趟排序：134
4838274955659776jiji6548ji97
55ji764希尔排序特点子序列的构成不是简单的“逐段分割”，而是将相隔某个增量的记录组成一个子序列希尔排序可提高
排序速度，因为分组后n值减小，n2更小，而T(n)=O(n2),所以T(n)从总体上看是减小了关键字较小的记录跳跃式前移，在进
行最后一趟增量为1的插入排序时，序列已基本有序增量序列取法无除1以外的公因子最后一个增量值必须为1例4938
659776132730初始关键字38496576
13273097第一趟38496513273076第二趟
384913273065第三趟3813273049第四趟
13273038第五趟132730第六趟38497697139727
97309713767676273013652765306513134949304927
3827383038算法评价时间复杂度最好情况（正序）比较次数：n-1移动次数：0最坏情况（逆序）比较次数
：移动次数：空间复杂度：S(n)=O(1)T(n)=O(n2)Ch8_4.c例初始关键字：49
38659776132750ijxji完
成一趟排序：(273813)49(769765
50)分别进行快速排序：(13)27(38)49(5065)
76(97)快速排序结束：1327384950
6576974927ijijij4965ji1349ij4997
ij例初始：[49386597761327]kj
jjjjjkki=11349一趟：13[38659776
4927]i=2kkjjjjj2738二趟：1327[65
97764938]三趟：132738[97
764965]四趟：13273849[769
765]五趟：1327384965[9776
]六趟：132738496576[97]排序结束：
13273849657697或(i=1,2,…...?n/
2?)ki?k2iki?k2i+1ki?k2iki?k2i+1例（96，83，27，38，11，9）例（13
，38，27，50，76，65，49，97）962791138831327384965765097可
将堆序列看成完全二叉树，则堆顶元素（完全二叉树的根）必为序列中n个元素的最小值或最大值例132738496576
50979727384965765013输出：132749389765765013输出：1
39749382765765013输出：13273849502765769713输出：13
276549502738769713输出：132738496550273876971
3输出：1327387665502738499713输出：1327384950657
62738499713输出：132738499765762738495013输出：13
273849506597762738495013输出：13273849509765
762738495013输出：13273849506576659727384950
13输出：1327384950659765762738495013输出：132738
495065769765762738495013输出：132738495065
7697第二部分问题与习题栈的应用举例由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中常用的工具。
数制转换十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理:
N=(ndivd)d+nmodd(其中:div为整除运算,mod为求余运算)例如
(159)10=(237)8，其运算过程如下:nndiv8nmod8
159197192
3202 实际情况:
(159)10=(237)81598198280237余7余3余2toptop7
top73top732a1a2a3…………………….an入队出队frontrear队
列Q=(a1,a2,……,an)front=0rear=0123450队空123450front
J1,J1,J3入队J1J2J3rearrear123450J4,J5,J6入队J4J5J6fro
nt设两个指针front,rear,约定：rear指示队尾元素后一位置；front指示队头元素位置初值front=rear
=0空队列条件：front==rear入队列：sq[rear++]=x;出队列：x=sq[++front];rearre
arfrontrear123450J1,J2,J3出队J1J2J3frontfrontfront0
M-11frontrear…...…...实现：利用“模”运算入队：rear=(rear+1)%M;s
q[rear]=x;出队：front=(front+1)%M;x=sq[front];队满、队空判定条件
0101C
0172
7272 C6
363
6354
5454A
BABD
DE
FEG图3-13循环队列上的插入Q.rearQ.rearQ.rearQ.front
Q.frontQ.front满队列空队列GABC
CDG
DFE
FE图3-14循环队列的删除过程Q.rearQ.rearQ.rearQ.fron
t（1）满（2）删除A、B后的队列（3）删除最后一个元素空队列Q.frontQ.fronttypedefs
tructQnode{QElemTypedata;structQnodenext;}Qnod
e,QueuePtr;头结点^…...front队头队尾rear设队首、队尾指针front
和rear,front指向头结点，rear指向队尾typedefstruct{QueuePtrfront;
QueuePtrrear;}LinkQueue;frontrearx入队^xfrontreary入队
x^yfrontrearx出队x^yfrontrear空队^frontreary出队^数据1数
据2数据3数据4……数据n数据n-1数据1的地址数据1的Key值数据2的地址数据2的Key值…………数据n
-1的地址数据n-1的Key值数据n的地址数据n的Key值原始数据：索引表：数据1数据2数据3数据4……数据
n-2数据n-1数据1的地址数据1的Key值数据4的地址数据4的Key值数据组1的地址数据组1的key值数据n-3
的地址数据n-3的Key值数据n的地址数据n的Key值原始数据：一级索引表：数据n-3数据n…………二级索引
表：…………数据组2的地址数据组2的key值Ch7_1.ci例0123
4567891011
513192137566475
808892找6464监视哨iiii比较次数=5比较次数：查找第n个元素：1
查找第n-1个元素：2……….查找第1个元素：n查找第i个元素：n+1-i查找失败：
n+1顺序查找方法的ASLlowhighmid例12345
678910115131
92137566475808892找211
2345678
910115131921375664
75808892lowhighmid1234
5678910115
131921375664758088
92lowhighmidCh7_2.c例12345
6789101151319
2137566475808892lowhighm
id找701234567
89101151319213756
6475808892lowhighmid123
4567891011
51319213756647580
8892lowhighmid123456
78910115131921
37566475808892lowhighmid
12345678
910115131921375664
75808892lowhigh1185210741936判定树：
12345678
910115131921375664
75808892Ch7_3.c123456
7891011121314151617182212138
9203342443824486058745786532248
861713索引表查38ASL最大最小两者之间表结构有序表、无序表有序表
分块有序表存储结构顺序存储结构线性链表顺序存储结构顺序存储结构线性链表查找方法比较顺序查找折半查找分块查找关
键字集合存储地址集合hash例30个地区的各民族人口统计表编号地区别总人口汉族
回族…...1北京2上海…...…...以编号作关键字，构造哈希函数：H(
key)=keyH(1)=1H(2)=2以地区别作关键字，取地区名称第一个拼音字母的序号作哈希函数：H(Beijing)
=2H(Shanghai)=19
H(Shenyang)=19例有80个记录，关键字为8位十进制数，哈希地址为2位十进制数813465
3281372242813874228130
13678132281781338967813
6853781419355…..…..????????分析：?只
取8?只取1?只取3、4?只取2、7、5
????数字分布近乎随机所以：取????任意两位或两位与另两位的叠加作哈希地址
例关键字为：0442205864，哈希地址位数为4586442200410088H(key
)=0088移位叠加58640224046092H(key)=6092间界叠加例表长
为11的哈希表中已填有关键字为17，60，29的记录，H(key)=keyMOD11,现有第4个记录，其关
键字为38，按三种处理冲突的方法，将它填入表中0123456
78910601729(1)H(38)=38MOD11=5冲突
H1=(5+1)MOD11=6冲突H2=(5+2)MOD11=7冲突H3
=(5+3)MOD11=8不冲突38(2)H(38)=38MOD11=5冲突
H1=(5+12)MOD11=6冲突H2=(5-12)MOD11=4不冲突38(3)
H(38)=38MOD11=5冲突设伪随机数序列为9，则：H1=(5+9)MOD
11=3不冲突38ITEducation&TrainingDate:ITEducation&
TrainingDate:第一部分数据结构基础知识数据的逻辑结构数据的存储结构数据的运算：检索、排序、插入、
删除、修改等线性结构非线性结构顺序存储链式存储线性表栈队树形结构图形结构数据结构的三个方面：数据1后继:2数据2后继:3数据3后继:4…………数据n-1后继:n数据nendtypedefstruct{Data_tdata;//数据域intnext;//后继域}Node_t,PNode_t;//提供的操作有：初始化、插入、删除等。图顺序存储结构内存结构示意图typedefstruct{Data_tdata;//数据域Node_tnext;//后继域}Node_t,PNode_t;//提供的操作有：初始化、插入、删除等。数据1后继数据2后继数据3后继…………数据n-1后继数据nend图只有一个指针域的结点结构指针域数据域nextdata或图2带头结点的单链结构(a)空链；(b)非空链图3带头结点的单循环链结构(a)空链；(b)非空链图4带头结点的双循环链结构(a)空链；(b)非空链图单链表在第一个位置删除结点过程p=a.next;a.next=a.next.next;dispose(p);图单链表在第一个位置插入结点过程（a）插入前；（b）插入后new(s);s.data=x;s.next=a.next;a.next=s;heada0a1…an￡-1xs(a)heada0a1…an￡-1x(b)hh空表TypedetstructDuLNode{ ElemTypedata; structDuLNodeprior; structDuLNodenext;}DuLNode,DuLinkList;priorelementnextL空双向循环链表：非空双向循环链表：LABbcapp->prior->next=p=p->next->proir;ana1a2……...栈底栈顶...出栈进栈栈s=(a1,a2,……,an)top=0123450栈空栈顶指针top,指向实际栈顶后的空位置，初值为0top123450进栈Atop出栈栈满BCDEF栈的初始空间为Mtop=0,栈空，此时出栈，则下溢（underflow)top=M,栈满，此时入栈，则上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空栈顶^…...topdatalink栈底入栈算法出栈算法^…...栈底toptopxptop^…...栈底topqITEducation&TrainingDate: