|
目录
【实验目的】
【实验预习】?
【实验内容】?
1. 编写程序实现顺序表的基本操作
2. 编写程序实现单链表的基本操作?
3. 循环链表的应用（约瑟夫回环问题）
【实验目的】
1. 掌握线性表的基本存储结构：顺序存储和链式存储。
2. 掌握顺序表与链表的各种基本操作算法。
3. 对线性表相应算法的时间复杂度进行分析。
4. 理解顺序表、链表数据结构的特点。
【实验预习】?
1. 顺序表的存储结构表示及基本操作。
2. 单链表的存储结构表示及基本操作。
【实验内容】?
1. 编写程序实现顺序表的基本操作
（1）实验测试数据
① 创建具有5个元素的顺序表：9，-12，7，36，100。
② 分别查找值为30和36的元素。
③ 在顺序表的第4个元素位置插入一个新元素，值为21；在第9个位置插入一个新元素，值为900。
④ 删除第1个元素。
⑤ 输出当前顺序表表长。
（2）实验说明及要求
① 顺序表采用动态分配存储表示。
#include<stdio.h>
#include<malloc.h>
#define ERROR 0
#define OK 1
#define INIT_SIZE 5 //初始分配的顺序表长度
#define INCREM 5 //溢出时，顺序表长度增量
typedef int ElemType; //定义表元素的类型
typedef struct Sqlist{
ElemType * slist; //存储空间的基地址
int length; //顺序表的当前长度
int listsize; //当前分配的存储空间
}Sqlist;
② 构造一个空的顺序表L。操作函数参考如下：?
int InitList_sq(Sqlist *L){
L->slist=(ElemType *)malloc(INIT_SIZE*sizeof(ElemType));
if (!L->slist) return ERROR; //初始化失败，返回0
L->length=0; //置空表长度为0
L->listsize=INIT_SIZE; //置初始空间容量
return OK; //初始化成功，返回1
}
③ 在顺序表L的第 i 个位置之前插入新元素 e?。
操作函数原型参考：int ListInsert_sq(Sqlist *L,int i,ElemType e);
int ListInsert_sq(Sqlist *L,int i,ElemType e){
if(L->length>=L->listsize){
L->slist=(ElemType *)realloc(L->slist,(L->listsize+INCREM)*sizeof(ElemType));
L->listsize+=INCREM;
}
if(i<1||i>L->length+1) return ERROR;
int j;
for(j=L->length-1;j>=i-1;j--){
L->slist[j+1]=L->slist[j];
}
L->slist[i-1]=e;
L->length++;
return OK;
}
④ 在顺序表L中删除第 i 个元素，并通过参数返回删除的元素值。
操作函数原型参考：int ListDelete_sq(Sqlist *L,int i,ElemType *e);
int ListDelete_sq(Sqlist *L,int i,ElemType *e){
if(i<1||i>L->length) return ERROR;
int j;
*e=L->slist[i-1];
for(j=i-1;j<L->length-1;j++){
L->slist[j]=L->slist[j+1];
}
L->length--;
return OK;
}
⑤ 在顺序表L中查找指定值为 e 的元素，返回其位置序号。
操作函数原型参考：int ListLocate_sq(Sqlist *L,ElemType e,int *pos);
int ListLocate_sq(Sqlist *L,ElemType e,int *pos){
int i;
*pos=-1;
for(i=0;i<L->length;i++){
if(L->slist[i]==e){
*pos=i+1;
break;
}
}
if(*pos==-1){
return ERROR;
}else{
return OK;
}
}
⑥ 依次输出顺序表L的所有元素。
操作函数原型参考：int PrintList_sq(Sqlist *L);
int PrintList_sq(Sqlist *L){
int i;
for(i=0;i<L->length;i++){
printf("%d ",L->slist[i]);
}
printf("\n");
return OK;
}
⑦ 求顺序表的表长。
操作函数原型参考：int ListLength_sq(Sqlist *L);
int ListLength_sq(Sqlist *L){
return L->length;
}
⑧ 创建一个包含n个元素的顺序表。
操作函数原型参考：int CreateList_sq(Sqlist *L,int n);
int CreateList_sq(Sqlist *L,int n){
int i;
if(L->length>=L->listsize){
L->slist=(ElemType *)realloc(L->slist,(L->listsize+INCREM)*sizeof(ElemType));
L->listsize+=INCREM;
}
for(i=0;i<n;i++){
scanf("%d,",&L->slist[i]);
L->length++;
}
return OK;
}
⑨ 主函数参考如下：
int main(){
Sqlist s1;
InitList_sq(&s1);
int n,select;
int m,k;
do{
printf("\n***************MENU***************\n");
printf("1.Create List\n");
printf("2.Get Element\n");
printf("3.Insert data\n");
printf("4.Delete data\n");
printf("5.Get ListLength\n");
printf("0.EXIT\n");
printf("\n***************MENU***************\n");
printf("\ninput choice:");
scanf("%d",&select);
getchar();
switch(select){
case 1:
printf("\n1-Create Sqlist:\n");
printf("please input n:");
scanf("%d",&n);
if(n==0) printf("ERROR");
CreateList_sq(&s1,n);
printf("\nPrint Sqlist:\n");
PrintList_sq(&s1);
break;
case 2:
printf("\n2-GetElem from Sqlist:\n");
printf("please input search data:");
scanf("%d",&k);
int pos;
if(!ListLocate(&s1,k,&pos))
printf("Not found");
else{
printf("found the element,position is %d\n",pos);
printf("\nPrint Sqlist:\n");
PrintList_sq(&s1);
}
break;
case 3:
printf("\n3-Insert from Sqlist:\n");
printf("\n input insert location and data:(location,data)\n");
scanf("%d,%d",&m,&k);
if(ListInsert_sq(&s1,m,k)){
printf("\nOK\n");
printf("\nPrint Sqlist:\n");
PrintList_sq(&s1);
}else{
printf("\nERROR!");
}
break;
case 4:
printf("\n4-Delete from Sqlist:\n");
printf("\nplease input delete location\n");
scanf("%d",&k);
int deldata;
if(ListDelete_sq(&s1,k,&deldata)){
printf("\nOK\n");
printf("\nDelete data is %d\n",deldata);
printf("\nPrintSqlist:\n");
PrintList_sq(&s1);
}else{
printf("\nERROR!\n");
}
break;
case 5:
printf("\n5-Get length of Sqlist:\n");
printf("\nLength is %d\n",ListLength_sq(&s1));
break;
case 0:
break;
}
}while(select);
return 0;
}
2. 编写程序实现单链表的基本操作?
（1）实验测试数据
① 初始化链表。
② 创建具有5个元素的链表：5，4，3，2，1。
③ 分别输出第3个元素值和第6个元素值。
④ 在链表的第1个元素位置插入一个新元素，值为8；在第7个元素位置插入一个新元素，值为700。
⑤ 删除第3个元素。
（2）实验说明及要求?
① 单链表存储结构。?
#include<stdio.h>
#include<malloc.h>
#define ERROR 0
#define OK 1
typedef int ElemType; //定义表元素的类型
typedef struct LNode{ //线性表的单链表存储
ElemType data;
struct LNode * next;
}LNode,*LinkList;
② 构造一个带头结点的单链表L。操作函数参考如下：?
LNode *InitList(LinkList L){
L=(LNode *)malloc(sizeof(LNode)); //申请一个头结点
if(!L) return ERROR; //申请失败
L->next=NULL; //头结点的指针域置空
return L;
}
③ 输入n个数据，创建具有n个结点的单链表L。
操作函数原型参考：LinkList CreateList(int n);?
LinkList CreateList(int n){
LinkList head=(LinkList)malloc(sizeof(LNode));
if(!head) return ERROR;
head->next=NULL;
LinkList p=head;
int i;
for(i=0;i<n;i++){
LinkList q=(LinkList)malloc(sizeof(LNode));
if(!q) return ERROR;
scanf("%d",&q->data);
p->next=q;
p=q;
}
p->next=NULL;
return head;
}
④ 输出带头结点单链表L的所有元素。
操作函数原型参考：void PrintList(LinkList L);?
void PrintList(LinkList L){
LinkList p=L->next;
while(p){
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}
⑤ 查找第 i 位置的元素，并由 e 返回其值。
操作函数原型参考：int GetElem(LinkList L,int i,ElemType *e);?
int GetElem(LinkList L,int i,ElemType *e){
int j=0;
LinkList p=L;
while(p&&j<i){
p=p->next;
j++;
}
if(!p||j>i){
return ERROR;
}
*e=p->data;
return OK;
}
⑥ 在第 i 个位置插入新元素e。
操作函数原型参考：int InsertElem(LinkList L,int i,ElemType e);?
int InsertElem(LinkList L,int i,ElemType e){
int j=0;
while(L&&j<i-1){
L=L->next;
j++;
}
if(!L||j>i-1){
return ERROR;
}
LinkList q=(LinkList)malloc(sizeof(LNode));
q->data=e;
q->next=L->next;
L->next=q;
return OK;
}
⑦ 删除第 i 位置的元素，并由 e 返回其值。
操作函数原型参考：int DeleteElem(LinkList L,int i,ElemType *e);?
int DeleteElem(LinkList L,int i,ElemType *e){
int j=0;
while(L&&j<i-1){
L=L->next;
j++;
}
if(i<1||j>i-1){
return ERROR;
}
if(!L||!L->next){
return ERROR;
}
*e=L->next->data;
L->next=L->next->next;
return OK;
}
主函数参考如下：?
int main(){
int i,n,select;
ElemType e;
LinkList L=NULL;
do{
printf("\n***************MENU***************\n");
printf("1.InitLinkList\n");
printf("2.GetElement\n");
printf("3.Insertdata\n");
printf("4.Deletedata\n");
printf("5.CreateLinkList\n");
printf("0.EXIT\n");
printf("\n***************MENU***************\n");
printf("\ninput choice:");
scanf("%d",&select);
getchar();
switch(select){
case 1:
printf("\n1-InitLinkList:\n");
L=InitList(L);
if(L!=NULL){
printf("\nInitLinkList OK!\n");
}else{
printf("\nInitLinkList ERROR!\n");
}
break;
case 2:
printf("\n2-GetElem from LinkList:\n");
printf("input pos=");
scanf("%d",&i);
if(L!=NULL&&GetElem(L,i,&e)){
printf("No%i is %d",i,e);
printf("\nPrintfList:\n");
PrintList(L);
}
else{
printf("Error&Not exists!");
}
break;
case 3:
printf("\n3-Insert e into LinkList:\n");
printf("input pos=");
scanf("%d",&i);
printf("input e=");
scanf("%d",&e);
if(L!=NULL&&InsertElem(L,i,e)){
printf("\nInsert OK!\n");
printf("\nPrintfList:\n");
PrintList(L);
}
else{
printf("\nInsert Error!\n");
}
break;
case 4:
printf("\n4-Delete from LinkList:\n");
printf("input pos=");
scanf("%d",&i);
if(L!=NULL&&DeleteElem(L,i,&e)){
printf("\nOK\n");
printf("\nDelete data is %d\n",e);
printf("\nPrintfList:\n");
PrintList(L);
}
else{
printf("\nDelete Error!\n");
}
break;
case 5:
printf("please input n:");
scanf("%d",&n);
if(n<0){
printf("ERROR!\n");
break;
}
printf("\nCreate LinkList\n");
L=CreateList(n);
printf("\nPrintfList:\n");
PrintList(L);
break;
case 0:
break;
}
}while(select);
return 0;
}
3. 循环链表的应用（约瑟夫回环问题）
? 用整数序列1，2，3，……n 表示顺序坐在圆桌周围的人，并采用循环链表作为存储结构。从任意位置 k 开始计数，计到 m 让此位置的人出局，重复上述过程，直至只剩下最后一个人。依次输出每个出局人的序号。如 n=8，m=4，k=1时，设每个人的编号依次为1，2，3，……，则得到的出局次序为 4，8，5，2，1，3，7，6。
#include<malloc.h>
#include<stdio.h>
#include<stdlib.h>
#define ERROR 0//操作返回值
#define OK 1
typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
LinkList CreateLoopListN(int n)
{
int i;
LinkList head,p,s;
p=head=(LinkList)malloc(sizeof(LNode));
//if(!p) return p;
scanf("%d",&(head->data));
for(i=2;i<=n;i++)
{
s=(LinkList)malloc(sizeof(LNode));
scanf("%d",&(s->data));
p->next=s;
p=s;
}
p->next=head;
return p;
}
void PrintLoopListRear(LinkList rear)
{
LinkList p;
if( rear==NULL) return;
p=rear->next;
printf("%d ",p->data);
p=p->next;
while(p!=rear->next)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}
void Josephus(LinkList rear,int n,int m)
{
LinkList p=rear,q;
int i,j;
for(i=0;i<n;i++){
for(j=1;j<m;j++){
p=p->next;
}
q=p->next;
printf("%d ",q->data);
p->next=q->next;
free(q);
}
}
int main()
{
LinkList rear;
int n,m;
scanf("%d %d",&n,&m);
rear=CreateLoopListN(n);
// PrintLoopListRear(rear);
Josephus(rear,n,m);
return 1;
}
|