线性表的链接存储

一、 实验目的

1. 掌握线性表的链接存储结构。

2. 能熟练地利用链接存储结构实现线性表的基本操作。 3. 能熟练地掌握链接存储结构中算法的实现。 二、 实验内容

1. 建立含有若干个元素的单链表，并将结果在屏幕上输出。

2. 对刚建立的单链表实现插入、删除、修改、查找，并将结果在屏幕上输出。

3. 解决约瑟夫问题：假设有n个人按1、2、3、…、n的顺序围成一圈，现在，从第

s个人开始按1、2、3、…、m的顺序报数，数到m的人出圈，接着从出圈的下一个人开始重复此过程，直到所有人出圈为止。试用链表解决这个问题。 三、 算法描述

1. 第1题、第2题的算法提示

定义单链表的结点结构，定义单链表的数据类型——单链表类，包括题目要求的插入、删除、查找等基本操作，为了便于查看操作结果，设计一个输出函数依次输出单链表的元素，以便后面反复使用。 此外，为操作方便，将插入、删除、修改、查找等操作都定义成单独的子函数形式。为查看这些操作的效果，可以在调用前后分别输出表的结果。 2. 第3题的算法提示

约瑟夫环问题的本身具有循环性质，考虑用循环链表。将循环链表的节点定义为结构体类型，建立约瑟夫环，建立一个循环链表并由头指针指示，其余具体算法与建立单链表类似。接着设计约瑟夫环算法实现出圈。 四、源程序及程序清单

第1、2题的源程序及其清单

#include using namespace std;

struct Node{ };

class Link{ public:

Link(); //无参构造函数，建立只有头结点的空链表

Link(int a[], int n); //有参构造函数，建立有n个结点的单链表 ~Link(); //析构函数

int Length(); //求单链表的长度 int data; //结点的数据域 Node *next; //结点的指针域

int Get(int i); //按位查找 int Locate( int x); //按值查找 void Insert(int i,int x); //插入操作 int Delete(int i); //删除操作 void Print(); //遍历操作

private:

Node *first; //单链表的头指针 };

Link::Link(){ }

Link::Link(int a[], int n){ }

Link::~Link(){

while(first!=NULL){

Node *p=first; first=first->next; first=new Node; first->next=NULL; for(int i=0;i

Node *s; s=new Node; s->data=a[i]; s->next=first->next; first->next=s; first=new Node; first->next=NULL;

}

}

delete p;

int Link::Length(){ }

int Link::Get(int i){ }

int Link::Locate(int x){

Node *p=first->next; int count=1;

while(p!=NULL&&count

if(p==NULL)

cout<<\参数非法\else

cout<<\该位置的元素值为：\return 0;

p=p->next; count++; Node *p=first->next; int count=0; while(p!=NULL){ }

cout<<\链表的长度为：\

p=p->next; count++;

return 0;

}

Node *p=first->next; int count=1; while(p!=NULL){ } return 0;

if(p->data==x)

cout<<\该元素的位置为：\p=p->next; count++;

void Link::Insert(int i,int x){ }

int Link::Delete(int i){

Node *p=first; int count=0;

while(p!=NULL&&count

if(p==NULL)

cout<<\位置非法\else{ }

Node *s; s=new Node; s->data=x; s->next=p->next; p->next=s; p=p->next; count++;