数据结构第二章线性表Word格式.docx
《数据结构第二章线性表Word格式.docx》由会员分享，可在线阅读，更多相关《数据结构第二章线性表Word格式.docx（16页珍藏版）》请在冰点文库上搜索。
c
顺序表的存储结构定义：
形式１：
＃defineMAXNUM100
DataTypeelement[MAXNUM];
Intn;
形式2：
structSeqList{DataTypeelement[MAXNUM];
intn;
}
比较这两种定义顺序表的方法，后者概念较为清晰，符合数据抽象的原则，今后我们的定义一般采用后者。
在实际应用中，为了使用方便，通常定义一个structSeqList类型的指针类型：
typedefstructSeqList*PSeqList;
pSeqListpalist;
/*指针变量*/
f函数的首部为：
voidf（PSeqListpl）
在主函数中调用函数f采用以下语句：
pl=&
L1;
f（pl）;
顺序表示中基本运算的实现
算法2.1创建空顺序表
PSeqListcreateNullList_seq（void）
{PSeqListpalist;
palist=（PSeqList）malloc（sizeof（structSeqList））;
if（palist!
=NULL）
palist->
n=0;
/*空表长度为0*/
else
printf（"
Outofspace!
!
\n"
）;
/*存储分配失败*/
return（palist）;
}
算法2.2顺序表的插入
intinsert_seq（PSeqListpalist,intp,DataTypex）
/*在palist所指顺序表中下标为p的元素之前插入元素x*/
{intq;
if（palist->
n==MAXNUM）/*溢出*/
{printf（"
Overflow!
return（FALSE）;
if（p<
0||p>
palist->
n）/*不存在下标为p的元素*/
Notexist!
\n"
for（q=palist->
n-1;
q>
=p;
q--）/*插入位置及之后的元素均后移一个位置*/
palist->
element[q+1]=palist->
element[q];
element[p]=x;
/*插入元素x*/
n=palist->
n+1;
/*元素个数加1*/
return（TRUE）;
算法2.3顺序表的删除
intdelete_seq（PSeqListpalist,intp）
/*在palist所指顺序表中删除下标为ｐ的元素*/
n–1）/*不存在下标为p的元素*/
\n"
return（FALSE）;
}
for（q=p;
q<
n-1;
q++）/*被删除元素之后的元素均前移一个位置*/
element[q]=palist->
element[q+1];
/*元素个数减1*/
}
算法分析:
✧在有n个元素的线性表里，在下标为i（第i+1个）的元素之前插入一个元素需要移动n-i个元素；
删除下标为i（第i+1个）的元素需要移动n-i-1个元素。
如果在下标为i的位置上插入和删除元素的概率分别是Pi和Pi’，则插入时的平均移动数是：
设在n+1个插入位置都是等概率的，则有，
✧删除的平均移动数是（
）：
✧所以顺序表的插入和删除操作的时间代价为O（n）。
✧类似地，在顺序表中进行定位（locate_seq）操作，则要依次与表中元素进行比较，当定位的概率平均分布在所有元素上时，一次定位平均需要和n/2个元素进行比较，其时间代价为O（n）。
算法2.4在顺序表中求某元素的下标
intlocate_seq（PSeqListpalist,DataTypex）
/*求x在palist所指顺序表中的下标*/
for（q=0;
n;
q++）
element[q]==x）
return（q）;
return（-1）;
算法2.5求palist所指顺序表中下标为ｐ的元素值
DataTyperetrieve_seq（PSeqListpalist,intp）
/*求palist所指顺序表中下标为p的元素值*/
{
if（p>
=0&
&
p<
n）/*存在下标为p的元素*/
return（palist->
element[p]）;
printf（"
Notexist.\n"
return（SPECIAL）;
/*返回一个顺序表中没有的特殊值*/
算法2.6判断线性表是否为空
intisNullList_seq（PSeqListpalist）
{
return（palist->
n==0）;
由上述操作可知：
顺序存储的优点:
不需要附加空间,随机存取任一个元素;
缺点:
很难估计所需空间的大小,且开始就要分配足够大的一片连续的内存空间.
2.3线性表的链接表示
链式存储结构
单链表：
每个元素除了需要存储自身的信息外，还要存储一个指示其后继的信息（即后继元素存储位置），这两部分信息组成了一个数据元素的存储结构，称为一个结点（注意：
每个结点所占用的存储单元应该是连续的）。
每个结点包括两个域：
数据域（info）—存放数据元素本身的信息；
指针域（link）—存放其后继结点的存储位置。
假设一线性表有n个元素，则这n个元素所对应的n个结点就通过指针链接成一个链表，
由于这种链表中每个结点只有一个指针域，故又称为单链表。
头指针指示单链表中第一个结点的存储位置。
如图2.5所示
图2.5链表示例
structLinkList/*单链表类型定义*/
{
PNodehead;
/*指向单链表中的第一个结点*/
};
/*单链表类型的指针类型*/
typedefstructLinkList*PLinkList;
PLinkListpllist;
/*pllist是指向单链表的一个指针变量*/
循环链表：
将单链表的形式稍作改变，让最后一个结点的指针指向头一个结点，这样就得到了循环链表。
使用循环链表的主要优点是：
从循环链表中任一结点出发，都能访问遍所有结点。
图2.11循环链表
双链表：
双链表中每个结点除了数据域以外有两个指针域：
一个指向其前驱结点，一个指向其后继结点。
每个结点的实际结构可以形象地描述如下：
structDoubleNode;
/*双链表结点*/
typedefstructDoubleNode*PDoubleNode;
/*结点指针类型*/
structDoubleNode/*双链表结点结构*/
{DataTypeinfo;
PDoubleNodellink,rlink;
};
为了灵活地处理，可对双链表进行封装，引入双链表结构：
structDoubleList/*双链表类型*/
{PDoubleNodehead;
/*指向第一个结点*/
PDoubleNoderear;
/*指向最后一个结点*/
双链表带来的最大好处是可以很容易地找到前驱和后继。
运算的实现：
单链表上的算法的实现：
算法2.7创建空链表
LinkListcreateNullList_link（void）
/*创建一个带头结点的空链表*/
{LinkListllist;
llist=（LinkList）malloc（sizeof（structNode））;
/*申请表头结点空间*/
if（llist!
=NULL）
llist->
link=NULL;
return（llist）;
算法2.8单链表的插入
intinsert_link（LinkListllist,inti,DataTypex）
/*在llist带头结点的单链表中下标为i的（第i+1个）结点前插入元素x*/
{PNodep,q;
intj;
p=llist;
j=0;
while（p!
=NULL&
j<
i）/*找下标为i-1的（第i个）结点*/
{p=p->
link;
j++;
if（j!
=i）/*i<
1或者大于表长*/
{printf（"
Thevalueofi=%disnotreasonble.\n"
i）;
return（0）;
q=（PNode）malloc（sizeof（structNode））;
/*申请新结点*/
if（q==NULL）
{printf（"
）;
return（0）;
else{/*插入链表中*/
q->
info=x;
link=p->
p->
link=q;
/*注意该句必须在上句后执行*/
return
（1）;
}
}
算法2.9单链表的删除
voiddelete_link（LinkListllist,DataTypex）
/*在llist带有头结点的单链表中删除第一个值为x的结点*/
{PNodep,q;
/*找值为x的结点的前驱结点的存储位置*/
while（p->
link!
=NULL&
p->
link->
info!
=x）
p=p->
if（p->
link==NULL）/*没找到值为x的结点*/
{printf（”Notexist!
\n”）;
else
{q=p->
/*找到值为x的结点*/
/*删除该结点*/
free（q）;
算法2.10在单链表中求某元素的存储位置
PNodelocate_link（LinkListllist,DataTypex）
/*在llist带有头结点的单链表中找第一个值为x的结点存储位置*/
{PNodep;
if（llist==NULL）return（NULL）;
p=llist->
while（p!
p=p->
return（p）;
算法2.11求单链表中下标为i的（第i+1个）元素的存储位置
PNodefind_link（LinkListllist,inti）
/*在带有头结点的单链表llist中求下标为i的（第i+1个）结点的存储位置;
当表中无下标为i的（第i+1个）元素时，返回值为NULL*/
{PNodep;
if（i<
0）/*检查i的值*/
Thevalueofi=%disnotreasonable.\n"
return（NULL）;
p=llist;
for（j=0;
j<
=i;
j++）
{p=p->
if（p==NULL）return（NULL）;
算法2.12判断单链表是否为空
intisNullList_link（LinkListllist）
/*判断llist带有头结点的单链表是否是空链表*/
{if（llist==NULL）
else
return（llist->
link==NULL）;
线性表的周游：
根据线性表的存储表示不同,其周游算法也不同:
顺序表示的周游
线性表的顺序表示的遍历
voidvisit_seq（Pseqlistpalist）
inti=0;
for（i=0;
i<
n;
i++）
visit（palist->
element[i]）;
线性表的单链表表示的遍历周游
voidvisit_link（LinkListllist）
Pnodep=llist;
for（p=llist;
p!
=NULL;
p=p->
link）
visit（p）;
单链表与顺序表的比较：
✧单链表的存储密度比顺序表低，它多占用了存储空间。
存储密度＝单链表数据项所占的空间/结点所占的空间
✧在单链表里进行插入、删除运算比在顺序表里容易得多。
✧对于顺序表，可随机访问任一个元素，而在单链表中，需要顺着链逐个进行查找，因此单链表适合于成批地、顺序地处理线性表中的元素时采用。
✧静态数据结构顺序表，在程序的运行期间数组的大小不再变化
✧动态数据结构链表，在程序的运行期间大小可自由变化
2.4应用举例――Josephus问题
问题提出
设有n个人围坐在一个圆桌周围，现从第s个人开始报数，数到第m的人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，…，如此反复直到所有的人全部出列为止。
Josephus问题是：
对于任意给定的n,s和m，求出按出列次序得到的n个人员的序列。
问题解答思路
数据结构
Josephus问题讨论的是一个圆链，所以自然想到使用线性表作为存储这个圆链的数据结构。
根据线性表种类的不同，就可以有2种不同的方法来表示圆链：
顺序表表示，循环单链表表示。
算法
在建立好线性表后，重复的对表中的元素实行检索和删除操作，将删除的元素依次输出就得到了Josephus问题的答案。
解答框架
1.对n,s,m进行赋值
2.插入元素构造Josephus表（对线性表初始化）
3.报数出列过程
源程序
顺序表
子程序
顺序表程序中对n,s,m进行赋值
voidinputnsm（int*n,int*s,int*m）
printf（"
\npleaseinputthevalues（<
100）ofn="
scanf（"
%d"
n）;
\npleaseinputthevaluesofs="
s）;
\npleaseinputthevaluesofm="
m）;
插入元素构造Josephus表（对线性表初始化）
顺序表的初始化
voidinitlist（PSeqListjos_alist,intn）
inti,k;
if（jos_alist==NULL）exit
（1）;
for（i=0;
i<
n;
i++）
k=insert_seq（jos_alist,i,i+1）;
if（k==FALSE）exit
（1）;
顺序表的报数出列过程
voidjosephus_seq（PSeqListpalist,ints,intm）
{ints1,i,w;
s1=s-1;
/*找出列的元素*/
for（i=palist->
i>
0;
i--）
s1=（s1+m-1）%i;
w=retrieve_seq（palist,s1）;
/*求下标为s1的元素的值*/
Outelement%d\n"
w）;
/*元素出列*/
delete_seq（palist,s1）;
/*删除出列的元素*/
顺序表的主程序
#defineMAXNUM100
#defineFALSE0
#defineTRUE1
typedefintDataType;
main（）
PSeqListjos_alist;
intn,s,m;
inputnsm（&
n,&
s,&
m）;
jos_alist=createNullList_seq（）;
/*创建空顺序表*/
initlist（jos_alist,n）;
josephus_seq（jos_alist,s,m）;
free（jos_alist）;
return0;
顺序存储结构Josephus算法时间复杂性：
循环单链表的子程序
对n,s,m进行赋值
报数出列过程
循环单链表的报数出列过程
voidjosephus_clink（PLinkListpclist,ints,intm）
{PNodep,pre;
inti;
p=*pclist;
/*找第s个元素*/
if（s==1）
{pre=p;
p=p->
while（p!
=*pclist）
{pre=p;
elsefor（i=1;
s;
=p->
link）/*当链表中结点个数大于1时*/
{for（i=1;
m;
i++）/*找第m个结点*/
{pre=p;
outelement:
%d\n"
p->
info）;
/*输出该结点*/
if（*pclist==p）/*该结点是第一个结点时，删除时需特殊处理一下*/
*pclist=p->
pre->
free（p）;
p=pre->
/*输出最后一个结点*/
*pclist=NULL;
free（p）;
简单示范程序：
#include"
stdio.h"
conio.h"
#defineN10
#defines1
#definem4
typedefstructStudent{intNo;
charName[15];
}StudentData;
typedefstructLNode{StudentDataStuData;
structLNode*link;
}LNode,*PList;
PListclist;
StudentDataStuData[N]={
{1,"
ChenNan"
},{2,"
ChenXiaobo"
},{3,"
ChenYing"
},
{4,"
ChengLiang"
},{5,"
ChentWenping"
},{6,"
DaiGuoxiong"
{7,"
GaoHuan"
},{8,"
GongFanghua"
},{9,"
GouJianting"
{10,"
GuanQiang"
}};
PListCreatLinkList（）
{inti;
PListp,q,cl=NULL;
N;
{p=（PList）malloc（sizeof（LNode））;
StuData.No=StuData[i].No;
strcpy（p->
StuData.Name,StuData[i].Name）;
if（cl==NULL）
{cl=p;
q=p;
else
{q->
link=p;
q->
link=cl;
returncl;
voidJosephus（intsta,intms,PListclst）
{PListp,q;
p=clst;
for（i=1;
s
升级会员 