数据结构实验二 线性表及其应用.docx

数据结构实验二 线性表及其应用.docx

《数据结构实验二 线性表及其应用.docx》由会员分享，可在线阅读，更多相关《数据结构实验二 线性表及其应用.docx（11页珍藏版）》请在冰点文库上搜索。

数据结构实验二线性表及其应用

第二章 线性表及其应用

【实验目的】

1.熟练掌握线性表的基本操作在顺序存储和链式存储上的实现；

2.以线性表的各种操作（建立、插入、删除、遍历等）的实现为重点；

3.掌握线性表的动态分配顺序存储结构的定义和基本操作的实现；

4.通过本章实验帮助学生加深对C语言的使用（特别是函数的参数调用、指针类型的应用和链表的建立等各种基本操作）。

第一节 知识准备

一、线性表的逻辑结构

线性表是由一组具有相同特性的数据元素组成的有限序列。

至于每个数据元素，它可以是一个数，一个符号，也可以是一页书，甚至更复杂的信息。

     例如：

26个英文字母构成一个线性表 （A，B，C，…，Y，Z）

           一串数字构成另一个线性表    （45，45，32，65，123）

每个数据元素可以由若干数据项组成，常把此数据元素称为记录。

能唯一标识一个记录的数据项的值称为关键字。

如：

一个学校的学生情况表如表2-1所示，表中每个学生的情况为一个记录，它由学号、姓名、性别、年龄、年级等五个数据项组成。

学号姓名性别年龄年级

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个圆形排列的洞，狐狸要吃兔子，兔子说：

“可以，但必须找到我，我就藏身于这十个洞中，你先到１号洞找，第二次隔１个洞（即3号洞）找，第三次隔２个洞（即6号洞）找，以后如此类推，次数不限。

”但狐狸从早到晚进进出出了1000次，仍没有找到兔子。

问兔子究竟藏在哪个洞里？

这实际上是一个反复查找线性表的过程，用以前学过的程序设计的知识也很容易实现，这里希望读者能体会数据结构的思想。

【数据描述】

定义一个顺序表，用具有10个元素顺序表来表示这10个洞。

每个元素分别表示围着山顶的一个洞，下标为洞的编号。

#define LIST_INIT_SIZE 10 //线性表存储空间的初始分配量

typedef struct {

   ElemType *elem; //存储空间基址

   int  length; //当前长度

   int listsize; //当前分配的存储容量（以sizeof（ElemType）为单位）

}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

status Rabbit（SqList &L）

  { //构造狐狸逮兔子函数

   int current=0; //定义一个当前洞口号的记数器，初始位置为第一个洞口

   for（i=0;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

}//第二次隔１个洞找，第三次隔２个洞找，以后如此类推,经过一千次

    printf（"兔子可能藏在如下的洞中：

"）

    for（i=0;i

         if（L.elem[i]==1）

printf（“ 第%d个洞\n ”,i+1）;//输出未进过的洞号

return OK;

}//end

【C源程序】

#include 

#include 

#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;  /*当前分配的存储容量（以sizeof（ElemType）为单位）*/

}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  */

status Rabbit（SqList *L）{

  /*构造狐狸逮兔子函数   */

   int i,current=0; /*定义一个当前洞口号的记数器，初始位置为第一个洞口*/

   for（i=0;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  */

}/*第二次隔１个洞找，第三次隔２个洞找，以后如此类推,经过一千次  */

    printf（"\n兔子可能藏在如下的洞中：

"） ;

    for（i=0;i

 if（（*L）.elem[i]==1）

    printf（"  \n此洞是第%d号洞 ",i+1）;/*输出未进过的洞号  */

return OK;

}

void main（）

{

SqList *L;

InitList_Sq（L）;

Rabbit（L）;

getch（）;

} 

【测试数据】

最后的输出结果为：

2  4  7  9

【说明】

本算法思路比较简单，采用了顺序表表示围着山顶的10个洞，首先对所有洞设置标志为1，然后通过1000次循环，对每次所进之洞修改标志为0，最后输出标志为1的洞。

【实验题】

1．同上面的狐狸逮兔子问题，如果山上有5个洞或20个洞，狐狸从早到晚进进出出了500次或10000次，仍没有找到兔子。

问兔子究竟可能藏在哪个洞里？

2．同上面的问题，将表示洞的线性表采用单链表实现，并比较其差异。

第三节 约瑟夫问题的实现

【问题描述】

设有n个人围坐在圆桌周围，现从某个位置m（1≤m≤n）上的人开始报数，报数到k的人就站出来。

下一个人，即原来的第k+1个位置上的人，又从1开始报数，再报数到k的人站出来。

依此重复下去，直到全部的人都站出来为止。

试设计一个程序求出出列序列。

    这是一个使用循环链表的经典问题。

因为要不断地出列，采用链表的存储形式能更好地模拟出列的情况。

【数据描述】

我们可以建立一个不带头结点的循环链表，其中的n个人用n个结点来表示。

Typedef int Elemtype;

Typedef struct Cnode

  {  Elemtype data;

     struct Cnode *next;

   }CNode;

【算法描述】见图2.5的流程图。

Status Create_clist（Clist &clist,int n）

{ clist=null;

  for（i=n;i>=1;i--）

     { if（!

（p=（CNode *）malloc（sizeof（CNode））））

               return overflow; //存储分配失败

       p->data=i;

       p->next=clist;

       clist=p;

       if（i==n） 

 q=p;//用q指向链表的最后一个结点

}

q->next=clist;//把链表的最后一个结点的链域指向链表的第一个结点，构成循环链表

ok;

}//end

status Joseph（int m,int n,int k）

{  if（m>n） return ERROR;//起始位置错

   if（!

Create_clist（clist,n））

     return ERROR;//循环链表创建失败

   p=clist;

   for（i=1;i

      p=p->next;//p指向m位置的结点

   while（p）

      { for（i=1;i

           p=p->next;//找出第k个结点

       q=p->next;

       printf（“%d”,q->data）;//输出应出列的结点

       if（p->next==p）  

          p=null;//删除最后一个结点

         else { p->next=q->next;//删除第K个结点

                p=p->next;//使P指向第k+1个元素位置

                free（q）; }

       }  //while

      clist=null;

 } //end    

【C源程序】

#include 

#include 

#define NULL 0

#define OK 1

#define ERROR 0

#define OVERFLOW -2

typedef int Status;

typedef int Elemtype;/*定义数据元素类型  */

typedef struct Cnode

  {  Elemtype data;

     struct Cnode *next;

   }CNode;

CNode *joseph;/*定义一个全局变量  */

Status Create_clist（CNode *clist,int n）

{  CNode *p,*q;

int i;

clist=NULL;

   for（i=n;i>=1;i--）

     { p=（CNode *）malloc（sizeof（CNode））;

       if（p==NULL）

               return OVERFLOW; /*存储分配失败  */

       p->data=i;

       p->next=clist;

       clist=p;

       if（i==n）

 q=p;/*用q指向链表的最后一个结点  */

}

q->next=clist; /*把链表的最后一个结点的链域指向链表的第一个结点，构成循环链表  */

joseph=clist;  /*把创建好的循环链表头指针赋给全局变量  */

return OK;

}           /*end  */

Status Joseph（CNode *clist,int m,int n,int k）

{  int i;

CNode *p,*q;

if（m>n） return ERROR;/*起始位置错  */

     if（!

Create_clist（clist,n））

     return ERROR;/*循环链表创建失败  */

   p=joseph;/*p指向创建好的循环链表  */

   for（i=1;i

      p=p->next;/*p指向m位置的结点  */

   while（p）

      { for（i=1;i

           p=p->next;/* 找出第k个结点  */

       q=p->next;

       printf（"%d ",q->data）;/*输出应出列的结点  */

       if（p->next==p）

  p=NULL;/*删除最后一个结点  */

         else { p->next=q->next;

                p=p->next;

free（q）; }

       }  /*while  */

      clist=NULL;

 } /* end */

void main（ ）

{ int m,n,k,i;

  CNode *clist;

  clist=NULL;/*初始化clist  */

printf（"\n请输入围坐在圆桌周围的人数n：

"）;

scanf（"%d",&n）;

printf（"\n请输入第一次开始报数人的位置m：

"）;

scanf（"%d",&m）;

printf（"\n你希望报数到第几个数的人出列?

"）;

scanf（"%d",&k）;

Create_clist（clist,n）;/*创建一个有n个结点的循环链表clist  */

printf（"\n出列的顺序如下：

\n"）;

Joseph（clist,m,n,k）;

getch（）;

}/*main  */

【测试数据】

1、请输入围坐在圆桌周围的人数n：

7

   请输入第一次开始报数人的位置m：

3

   你希望报数到第几个数的人出列?

 2

   出列的顺序如下：

4 6 1 3 7 5 2

2、请输入围坐在圆桌周围的人数n：

13

   请输入第一次开始报数人的位置m：

5

   你希望报数到第几个数的人出列?

 6

   出列的顺序如下：

10 3 9 4 12 7 5 2 6 11 8 1 13

3、请输入围坐在圆桌周围的人数n：

21

   请输入第一次开始报数人的位置m：

3

   你希望报数到第几个数的人出列?

 9

   出列的顺序如下：

11 20 8 18 7 19 10 2 15 9 4 1 21 3 6 14 12 13 5 16 17

【说明】

本算法采用一个不带表头的循环链表来处理约瑟夫问题，在此算法中，每次找出需出列结点，要经过k次循环移动定位指针，全部结点出列，需经过n个k次循环，因此，本算法的时间复杂度为O（k*n）。

实际问题的处理中，有许多与约瑟夫问题类似，都可以采用此方法完成。

【实验题】

1.处理约瑟夫问题也可用数组完成，请读者自己编写使用数组实现约瑟夫问题的算法和程序。

2.猴王问题。

某森林中有n只猴子在商量猴王选举问题，所有的猴子都想当猴王，因此大家商量了一个选举办法如下：

所有的猴子围成一圈，先从第一个猴子开始报数，报数到13的猴子就出列。

紧接着的下一个猴子，又从1开始进行新的一轮报数，报数到12的猴子再出列；依此重复下去，每一轮报数都比上一轮的报数少1，直到报数减为1之后，又从13开始报数。

直到原列中只剩下一个猴子为止，这个猴子就是猴王。

试设计一个程序求出猴王。

第四节 思考题

1.假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将表A和表B归并成一个按元素非递减有序（允许值相同）排列的线性表C，并要求利用原表（即表A和表B）的结点空间存放表C。

               （上海交通大学一九九九年硕士生入学考试试题）

【简要分析】除了指向线性表C头结点的指针外，还需设置三个指针Pa，Pb，Pc；首先Pa，Pb分别指向线性表A和B的表头，Pc指向A和B的表头值较小的结点，线性表C头节点的指针等于Pc；然后，比较Pa与Pb的值的大小，让Pc的后继指向较小值的指针，接着Pc向后移动，较小值的指针也向后移动，以此类推，直到Pa，Pb中某一个为空，这时，让Pc的后继指向Pa，Pb中非空的指针就完成了C表的建立。

2.给定一个整数数组b[0..N-1], b中连续相等元素构成的子序列称为平台.试设计算法,求出b中最长平台的长度.

（中科院计算机技术研究所1999年硕士入学考试数据结构与程序设计试题）

【简要分析】设置一个平台长度变量Length和一个计数器Sum。

初始化Length为1，Sum为1，再设置两下标指针i、j，首先，i指向第一个数组元素，j指向其次的第二个元素，比较i、j指向元素值的大小，若相等，则Sum++，i++，j++，再次比较i、j指向元素值的大小；若不相等，则比较Length与Sum的大小，如果Sum值大于Length，则把Sum的值赋给Length，Sum的值重置为1，同时i，j也向前各移动一位；重复上面的过程，直到i指向最后一个元素为止，此时的Length就是最长平台的长度。

3.参加知识竞赛的n个学校（编号为1…n），每个学校派至多m名学生参赛，每个学生的编号有二位学校代码和五位座位编号构成。

统计每个学校的参赛学生的平均分，并依次确定学校的名次；查找竞赛的最高分和最低分，并计算它们的方差；给出前三名学生的具体信息。

【简要分析】本题解决办法较多。

我们可以采用单链表来对所有学生的信息进行存储，至多需要n*m个结点，每个结点至少包含如下几个域：

2位学校代码、5位座位编号、学生姓名、竞赛成绩等。

也可以采用顺序表来对所有学生的信息进行存储，构造一个结构体数组，至多需要n*m个数组元素，每个数组元素的数据项值与单链表中的结点域值类似。

然后再另外构造一个存储学校信息的顺序表或单链表，每个结点至少包含如下几个域：

二位学校代码、学校名称、学校取得的平均分、学校名次等。

在构造好所有的存储结构之后，就可以编制相应的计算平均分、排序、查找、输出等算法了。

Chapter Two     Linear_List and its applications

Objectives

1.To understand basic operations of Linear_List in implementation of Sequence_List and Link_List.

2.To focus on basic operations of Linear_List, such as, creation, insertion, deletion and traversal.

3.To understand definition and basic operation of dynamic allocation list.

4.To help students better understand applications of C program language through experiments. Especially, focus on function call, application of pointer type and creation of Link_List, etc.