首页 考试资料幻灯片工程技术公务员考试小学教学中学教学大学教学外语资料
数据结构实验书


学号 姓名 性别 年龄 年级 96001 张平 女 21 大二 96002 王极 男 20 大一 96003 膨磊 男 23 大三 96004 严正英 女 19 大一 96005 李强 男 20 大二

综上所述,线性表有如下特性: 1. 除第一个和最后一个元素以外,每个元素有且仅有一个直接前趋和一个直接后继;第一个结点只有直 接后继,最后一个结点只有直接前趋。

2. 线性表中的每个数据元素,其数据类型是一致的。 3. 数据元素之间的相对位置是线性的,结构中的数据元素之间存在一个对一个的关系。

二、线性表的顺序表示和实现 计算机的内存是由有限多个存储单元组成的,每个存储单元都有对应的整数地址,各存储单元的地址是连 续编号的。对于一个线性表,如果用一组连续的存储单元依次存放它的各个数据元素,这就是线性表的顺 序分配。也就是说,在线性表的顺序分配结构中,逻辑结构上相邻的数据元素,其物理位置也是相邻的。 若一个数据元素只占用一个存储单元,则这种分配方式如图 2-1 所示。从图可知,线性表的第 i 个数据元 素的存储地址 LOC(ai)=LOC(a1)+(i-1) 如果一个数据元素占据 k 个存储单元,则有 LOC(ai)=LOC(a1)+(i-1)×k

其中,LOC(a1)是线性表的第一个数据元素的存储地址。

三、 线性表的链式表示和实现 1.单链表 线性链表即线性表的链式存储结构是用一组任意的存储单元(它们可以是连续的,也可以是不连续的)来 存储线性表的各个数据元素。为了表示每个元素与其直接后继元素之间的逻辑关系,对每个元素来说,除 了需要存储元素本身的信息之外,还需要存储一个指示其直接后继的信息(即直接后继的存储位置),这 两部分信息组成了一个数据元素的存储结构,称之为一个结点(node),当然每一个结点占用的存储单元 应该是连续的。这样,每个结点包括两个域,存储数据元素本身信息的域称之为数据域(data),存储直 接后继结点存储位置的域称之为指针域(next),该域内信息为一指针,它指出线性表某一数据元素逻辑 上直接后继元素的存储位置。 由于线性表的最后一个数据元素没有后继, 故相应结点的指针域内容为空 NULL (也可以用符号∧表示)。如图 2-2 所示为一个不带头结点的单链表。

在实际应用中,有时也使用带头结点的单链表,如图 2-3 所示,虽然浪费了一个结点,但是却换来了其它 操作的便利,例如在插入删除操作中,不用判断是否对第一个结点进行。我们称这个结点为“哨兵”,其 作用往往是不用判断出界;在以后的学习中,还会经常遇上“哨兵”。

2.循环链表

循环链表是线性表的一种特殊的链式存储结构,它的特点是线性链表的最后一个结点(即表尾结点)的指 针域存放链表中第一个结点的地址,则整个链表形成了一个环。如图 2-4 所示。

3.双向循环链表 双向循环链表是对循环链表的改进,当我们需要经常查找某一节点的前驱时,可以增加一个指向前驱的指 针域,构成双向循环链表。如图 2-5 所示。

第二节 狐狸逮兔子实验

【问题描述】 围绕着山顶有 10 个圆形排列的洞,狐狸要吃兔子,兔子说:“可以,但必须找到我,我就藏身于这十个洞 中,你先到1号洞找,第二次隔1个洞(即 3 号洞)找,第三次隔2个洞(即 6 号洞)找,以后如此类推, 次数不限。”但狐狸从早到晚进进出出了 1000 次,仍没有找到兔子。问兔子究竟藏在哪个洞里? 这实际上是一个反复查找线性表的过程,用以前学过的程序设计的知识也很容易实现,这里希望读者能体 会数据结构的思想。 【数据描述】 定义一个顺序表,用具有 10 个元素顺序表来表示这 10 个洞。每个元素分别表示围着山顶的一个洞,下标 为洞的编号。 #define LIST_INIT_SIZE typedef struct { ElemType int *elem; //存储空间基址 //当前长度 //当前分配的存储容量(以 sizeof(ElemType)为单位) 10 //线性表存储空间的初始分配量

length;

int listsize; }SqList; 【算法描述】 status

InitList_Sq(SqList

&L) {

//构造一个线性表 L L.elem=(ElemType )malloc(LIST_INIT_SIZE*sizeof(ElemType));

If(!L.elem) return OVERFLOW; //存储分配失败 L.length=0; //空表长度为 0

L.listsize=LIST_INIT_SIZE; return } OK;

//初始存储容量

//InitList_Sq Rabbit(SqList &L)

status {

//构造狐狸逮兔子函数 int current=0; //定义一个当前洞口号的记数器,初始位置为第一个洞口

for(i=0;i<LIST_INIT_SIZE;i++) L.elem[i]=1; //给每个洞作标记为 1,表示狐狸未进之洞 L.elem[LIST_INIT_SIZE-1]=L.elem[0]=0;//首先进入第一个洞,标记进过的洞为 0。 for(i=2;i<=1000;i++) { current=(current+i)%LIST_INIT_SIZE;//实现顺序表的循环引用 L.elem[i]=0; // 标记进过的洞为 0

}//第二次隔1个洞找,第三次隔2个洞找,以后如此类推,经过一千次 printf("兔子可能藏在如下的洞中:") for(i=0;i<LIST_INIT_SIZE;i++) if(L.elem[i]==1) printf(“ return }//end OK; 第%d 个洞n ”,i+1);//输出未进过的洞号

【C 源程序】 #include <stdio.h> #include <stdlib.h> #define OK 1

#define OVERFLOW -2 typedef int status; typedef int ElemType; #define LIST_INIT_SIZE 10 /*线性表存储空间的初始分配量 typedef struct { ElemType *elem; /* 存储空间基址 */ */

int length; int listsize; }SqList;

/* 当前长度 */ /*当前分配的存储容量(以 sizeof(ElemType)为单位)*/

status InitList_Sq(SqList *L){ /*构造一个线性表 L */

(*L).elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!((*L).elem)) return OVERFLOW; /* 存储分配失败 */ (*L).length=0; /*空表长度为 0 */ /*初始存储容量 */

(*L).listsize=LIST_INIT_SIZE; return OK; } /*InitList_Sq */ status Rabbit(SqList *L){ /*构造狐狸逮兔子函数 int i,current=0; */

/*定义一个当前洞口号的记数器,初始位置为第一个洞口*/

for(i=0;i<LIST_INIT_SIZE;i++) (*L).elem[i]=1; /*给每个洞作标记为 1,表示狐狸未进之洞 (*L).elem[LIST_INIT_SIZE-1]=0; (*L).elem[0]=0; /*第一次进入第一个洞,标记进过的洞为 0 */ */

for(i=2;i<=1000;i++){ current=(current+i)%LIST_INIT_SIZE;/*实现顺序表的循环引用 (*L).elem[current]=0; /* 标记进过的洞为 0 */ */ */

123456789101112131415161718192021222324252627282930

 


 

  【Top

最新搜索

 


 

热点推荐