数据结构实验指导手册.doc

实验一 线性表的顺序存储实验
一、实验目的
1、掌握用Visual C++6.0上机调试顺序表的基本方法
2、掌握顺序表的基本操作，插入、删除、查找、以及有序顺序表的合并等算法的实现
二、实验内容
1、顺序表基本操作的实现
[问题描述] 当我们要在顺序表的第i个位置上插入一个元素时，必须先将顺序表中第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。若是欲删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置。
[基本规定] 规定生成顺序表时，可以键盘上读取元素，用顺序存储结构实现存储。
[实现提醒] 要实现基本操作，可用实现的基本操作，也可设计简朴的算法实现。
[程序实现]
#include <stdio.h>
#include <conio.h>
typedef int DataType ;
# define maxnum 20
typedef struct
{int data[maxnum];
int length;
}SeqList;
/*插入函数*/
int insert(SeqList *L , int i , DataType x)
/* 将新结点x插入到顺序表L第i个位置 */
{ int j ;
if( i<0 || i>(*L).length +1)
{ printf(" \n i 值不合法 ! ");
return 0;
}
if((* L).length >=maxnum-1)
{ printf(" \n 表满不能插入!");
return 0;
}
for(j=(*L).length;j>=i;j--) (*L).data[j+1]=(*L).data[j];
(*L).data[i] = x;
(*L).length++;
return 1;
}
/*删除函数*/
int delete( SeqList *L ,int i)
/*从顺序L中删除第i个结点*/
{ int j ;
if( i<0|| i>(*L).length )
{ printf(" \n 删除位置错误 ! ") ;
return 0;
}
for(j=i+1;j<=(*L).length;j++)
(*L).data[j-1] =(*L).data[j];
(*L).length--;
return 1;
}

/*生成顺序表*/
void creatlist(SeqList * L)
{ int n , i , j ;
printf("请输入顺序表 L 的数据个数：\n") ;
scanf("%d" , &n) ;
for(i=0 ; i<n ; i++)
{ printf("data[%d] =" , i) ;
scanf("%d",&((*L).data[i]));
}
(*L).length=n-1;
printf("\n") ;
}/*creatlist */

/*输出顺序表 L*/
printout(SeqList * L)
{ int i ;
for (i=0 ; i<=(* L).length ; i++)
{ printf(" data[%d]=", i) ;
printf("%d", (*L).data[i]);
}/*printout */
printf("\n");
}

main()
{ SeqList *L ;
char cmd ;
int i , t , x;
clrscr() ;
creatlist(L);
do
{
printf("\ni , I ----- 插入\n") ;
printf("d , D ----- 删除\n") ;
printf("q , Q ----- 退出\n") ;
do
{cmd=getchar() ;
}while((cmd!='i')&&(cmd!='I')&&(cmd!='d')&&(cmd!='D')&&(cmd!='q')&&(cmd!='Q'));
switch(cmd)
{ case 'i':
case 'I':
printf("\nPlease input the DATA: ");
scanf("%d",&x) ;
printf("\nWhere? ");
scanf("%d",&i) ;
insert(L,i,x) ;
printout(L);
break ;
case 'd':
case 'D' :
printf("\nWhere to Delete? ");
scanf("%d",&i);
delete(L,i);
printout(L);
break ;
}
}while((cmd!='q')&&(cmd!='Q'));
}

2、有序顺序表的合并
[问题描述] 已知顺序表la和lb中的数据元素按非递减有序排列，将la和lb表中的数据元素，合并成为一个新的顺序表lc
[基本规定] lc中的数据元素仍按非递减有序排列，并且不破坏la和lb表
[程序实现]
# include <stdio.h>
# define maxnum 20
typedef int DataType ;
typedef struct
{ DataType data[maxnum] ;
int length ;
}SeqList ;

int MergeQL(SeqList la , SeqList lb , SeqList *lc)
{ int i , j , k ;
if (la.length+1 + lb.length+1>maxnum)
{ printf("\narray overflow!") ;
return 0;
}
i=j=k=0;
while(i<=la.length && j<=lb.length)
{ if (la.data[i]<=lb.data[j])
lc->data[k++]=la.data[i++] ;
else
lc->data[k++]=lb.data[j++];
}
/* 解决剩余部分 */
while (i<=la.length) lc->data[k++]=la.data[i++];
while (j<=lb.length) lc->data[k++]=lb.data[j++];
lc->length=k-1;
return 1;
}

main()
{ SeqList la={{3,4,7,12,15},4} ;
SeqList lb={{2,5,7,15,18,19},5} ;
SeqList lc ;
int i ;
if (MergeQL(la,lb,&lc))
{ printf("\n") ;
for(i=0;i<=lc.length ; i++)
printf("%4d",lc.data[i]);
}
}

实验二 单链表实验
一、实验目的
1、掌握用Visual C++6.0上机调试单链表的基本方法
2、掌握单链表的插入、删除、查找、求表长以及有序单链表的合并算法的实现
二、实现内容
1、单链表基本操作的实现
[问题描述]要在带头结点的单链表h中第i个数据元素之前插入一个数据元素x ，一方面需要在单链表中寻找到第i-1个结点并用指针p指示，然后申请一个由指针s 指示的结点空间，并置x为其数据域值，最后修改第i-1个结点，并使x结点的指针指向第i个结点，要在带头结点的单链表h中删除第i个结点，一方面要计数寻找到第i个结点并使指针p指向其前驱第i-1个结点，然后删除第i个结点并释放被删除结点空间。
[基本规定]用链式存储结构实现存储
[实现提醒]链式存储结构不是随机存储结构，即不能直接取到单链表中某个结点，而要从单链表的头结点开始一个一个地计数寻找。
[程序实现]
# include <stdio.h >
# include <malloc.h >
typedef char DataType ;

typedef struct node{
DataType data; /*结点的数据域*/
struct node *next; /*结点的指针域*/
}ListNode;

void Init_List(ListNode **L)
{
(*L)=(ListNode *)malloc(sizeof(ListNode));/*产生头结点*/
(*L)->next=NULL;
}

int List_Length(ListNode *L )
{
int n=0;ListNode *p=L->next;
while(p!=NULL)
{
n++;
p=p->next;
}
return n;
}

ListNode* GetNode(ListNode *L,int i)
{
int j;
ListNode *p;
p=L;j=0; /*从头结点开始扫描*/
while(p->next&&j!=i) /*顺指针向后扫描,直到p->next为NULL或i=j为止*/
{
p=p->next;
j++;
}
if(i==j)
return p; /*找到了第i个结点*/
else
return NULL; /*当i<0或i>0时,找不到第i个结点*/
}

void InsertList(ListNode *L,DataType x,int i)
{
ListNode *p,*s;
p=GetNode(L,i-1); /*寻找第i-1个结点*/
if (p==NULL) /*i<1或i>n+1时插入位置i有错*/
{ printf("position error");
return ;
}
s=(ListNode *)malloc(sizeof(ListNode));
s->data=x;s->next=p->next;p->next=s;
}

void DeleteList(ListNode *L ,int i)
{
ListNode *p,*r;
p=GetNode(L,i-1); /*找到第i-1个结点*/
if (p==NULL||p->next==NULL) /*i<1或i>n时,删除位置错*/
{ printf("position error");
return ;
}
r=p->next; /*使r指向被删除的结点a*/
p->next=r->next; /*将ai从链上删除*/
free(r);
}

/*使用头插法建立带头结点链表算法*/
ListNode * CreatListF(void)
{
char ch;
ListNode *head=(ListNode *)malloc(sizeof(ListNode)); /*生成头结点*/
ListNode *s; /*工作指针*/
head->next=NULL;
ch=getchar(); /*读入第1个字符*/
while(ch!='\n')
{
s=(ListNode *)malloc(sizeof(ListNode)); /*生成新结点*/
s->data=ch; /*将读入的数据放入新结点的数据域中*/
s->next=head->next;
head->next=s;
ch=getchar(); /*读入下一字符*/
}
return head;
}

/*使用尾插法建立带头结点链表算法*/
ListNode * CreatListR1(void)
{
char ch;
ListNode *head=(ListNode *)malloc(sizeof(ListNode)); /*生成头结点*/
ListNode *s,*r; /*工作指针*/
r=head; /*尾指针初值也指向头结点*/
while((ch=getchar())!='\n')
{
s=(ListNode *)malloc(sizeof(ListNode));
s->data=ch;
r->next=s;
r=s;
}
r->next=NULL; /*终端结点的指针域置空,或空表的头结点指针域置空*/
return head;
}

/*复制链表A中的内容到表B中*/
void copy(ListNode *a, ListNode *b)
{
ListNode *pa=a->next; ListNode *u;
ListNode *rb=b;
while(pa!=NULL)
{
u=( ListNode *)malloc(sizeof(ListNode));
u->data=pa->data;
rb->next=u;
rb=u;
pa=pa->next;
}
rb->next=NULL;
}

/*输出带头结点的单链表*/
void DisplaySL(ListNode *la, char *comment)
{ ListNode *p ;
p=la->next ;
if(p) printf("\n%s\n" , comment) ;
while(p)
{ printf("%4c",p->data);
p=p->next;
}
printf("\n") ;
}

/*主函数*/
main( )
{ ListNode *la ,*lb,*lc, *p ;
int n,x,i;
printf("\n用头插法建立链表la，请输入节点内容:");
la=CreatListF();
DisplaySL(la,"新生成链la节点内容:");
printf("\n链表la的长度: %2d",List_Length(la));
printf("\n请输入要插入的元素: ");
scanf("%c",&x) ;
printf("\n请输入要插入的位置：");
scanf("%d",&i) ;
InsertList(la,x,i);
DisplaySL(la,"插入后链la节点内容");
printf("\n请输入要删除元素的位置：");
scanf("%d",&i);
DeleteList(la,i);
DisplaySL(la, "删除后链la节点内容");
printf("\n用尾插法建立链表lb，请输入节点内容:");
fflush(stdin);
lb=CreatListR1();
DisplaySL(lb,"新生成链lb节点内容:");
Init_List(&lc);
copy(la,lc);
DisplaySL(lc,"复制生成的链lc节点内容:");
}

2、有序单链表的合并
[问题描述] 已知单链表la和lb中的数据元素按非递减有序排列，将la和lb中的数据元素,合并为一个新的单链表lc,lc中的数据元素仍按非递减有序排列。
[基本规定] 不破坏la表和lb表的结构。
[程序实现]
# include <stdio.h>
#include<alloc.h>
#define NULL 0
typedef int DataType;
typedef struct SLNode
{ DataType data;
struct SLNode * next;
}slnodetype;
int MergeSL(slnodetype *la,slnodetype *lb,slnodetype **lc);
int CreateSL(slnodetype *la,int n);
void DisplaySL(slnodetype *la , char * comment);
main( )
{ slnodetype *la, *lb, *lc ,*p;
int n,m;
la=(slnodetype *)malloc(sizeof(slnodetype));
la->next=NULL;
lb=(slnodetype *)malloc(sizeof(slnodetype));
lb->next=NULL;
lc=(slnodetype *)malloc(sizeof(slnodetype));
lc->next=NULL;
printf("\n 输入链la节点数:");
scanf("%d",&n);
printf("\n 输入链la 节点内容:");
CreateSL(la,n);
DisplaySL(la,"链la 节点内容:");
printf("\n 输入链lb节点数:");
scanf("%d",&m);
printf("\n 输入链lb节点内容:");
CreateSL(lb,m);
DisplaySL(lb,"链lb 节点内容:");
if(MergeSL(la,lb,&lc)) DisplaySL(lc,"合成后的链lc:");
getchar();
}

int MergeSL(slnodetype * la , slnodetype *lb,slnodetype * *lc)
{ slnodetype * pa, * pb, * pc;
lc=(slnodetype *)malloc(sizeof(slnodetype));
pa=la->next;
pb=lb->next;
pc= *lc;
while(pa&&pb)
{
pc->next=(slnodetype*)malloc(sizeof(slnodetype));
pc=pc->next;
if(pa->data<=pb->data)
{ pc->data=pa->data;
pa=pa->next;
}
else{ pc->data=pb->data;
pb=pb->next;
}
}
while (pa) /*插入la链的剩余段 */
{
pc->next=(slnodetype*)malloc(sizeof(slnodetype));
pc=pc->next;
pc->data=pa->data;
pa=pa->next;
}
/*插入lb链的剩余段*/
while(pb)
{
pc->next=(slnodetype*)malloc(sizeof(slnodetype));
pc=pc->next;
pc->data=pb->data;
pb=pb->next;
}

/*生成单链表*/
int CreateSL(slnodetype *la ,int n)
{ int i ;
slnodetype *p , *q ;
q=la ;
for (i=1 ; i<=n ; i++)
{ p=(slnodetype *)malloc(sizeof(slnodetype));
scanf("%d" , &p->data) ;
q->next=p;
q=p;
}
q->next=NULL ;
return 1 ;
}

/*输出单链表*/
void DisplaySL(slnodetype *la, char *comment)
{ slnodetype *p ;
p=la->next ;
if(p) printf("\n%s\n" , comment) ;
while(p)
{ printf("\n%3d" , p->data);
p=p->next ;
}
printf("\n") ;
}

实验三 循环链表实验
一、实验目的
1、掌握用Visual C++6.0上机调试循环链表的基本方法
2、进一步掌握循环单链表的插入、删除、查找算法的实现
二、实现内容
1. 约瑟夫环问题
[问题描述]设有N个人围坐一圈，现从某个人开始报数，数到M的人出列，接着从出列的下一个人开始重新报数，数到M的人以出列，如此下去，直到所有人都出列为此。试设计拟定他们的出列顺序序列的程序。
[基本规定] 选择单向循环链表作为存储结构模拟整个过程，并依次输出列的各人的编号。
[实现提醒] 程序运营之后，一方面规定用户指定初始报数的下限值，可以n<=30,此题循环链表可不设头节点，并且必须注意空表和非空表的界线。
如 n=8, m=4 时，若从第一个人， 设每个人的编号依次为 1，2，3，…开始报数，则得到的出列顺序为4，8，5，2，1，3，7，6，
如下图所示，内层数字表达人的编号 ，每个编号外层的数字代表人出列的序号。
[程序实现]
#include <stdio.h>
#include <malloc.h>
typedef struct node
{ int num;
struct node *next;
}linklist;
linklist *creat(head,n) /*使n个人围成一圈，并给每个人标记号数*/
linklist *head;
int n ;
{linklist *s,*p;
int i;
s=(linklist * )malloc(sizeof(linklist));
head=s;
s->num=1;
p=s;
for(i=2;i<=n; i++)
{ s=(linklist *) malloc(sizeof(linklist));
s->num=i;
p->next=s;
p=s;
}
p->next=head;
return(head);
}/* creat */

linklist * select(linklist *head, int m)
{ linklist *p, *q;
int i, t;
p=head; t=1;
q=p; /* q为p的前趋指针*/
p=p->next;
do
{
t=t+1 ; /*报一次数*/
if(t%m==0)
{ printf("%4d", p->num);
q->next=p->next;
free(p);
p=q->next;
}
else { q=p;
p=p->next;
}
}while(q!=p);
head=p;
printf("%4d",p->num);
return (head);
}/* select */

main( )
{ int n,m;
linklist *head;
printf("\ninput the total number:n=");
scanf("%d", &n);
printf("\ninput the number to call:m=");
scanf("%d", &m);
head=creat(head,n);
head=select(head,m);
printf("\nthe last one is :%d", head->num);
}/* main */

思考题：编程实现两个循环单链表的合并。

实验四 栈、队列的实现及应用
一、实验目的
1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用。
2、掌握栈和队列的特点，即先进后出与先进先出的原则。
3、掌握栈和队列的基本操作实现方法。
二、实验内容
1、实现栈的顺序存储
# define MAXSIZE 100
typedef int ElemType;
typedef struct
{ ElemType data[MAXSIZE];
int top;
}SeqStack;

void InitStack(SeqStack *s)
{s->top=0;
return 1;
}

int StackEmpty(SeqStack *s)
{ if(s->top==0) return 1;
else return 0;
}

int StackFull(SeqStack *s)
{ if(s->top==MAXSIZE-1) return 1;
else return 0;
}

void Push(SeqStack *s,int x)
{ if (StackFull(s)){ printf("the stack is overflow!\n");
return 0;
}
else { s->data[s->top]=x;
s->top++;
}
}

void Display(SeqStack *s)
{if(s->top==0)
printf("the stack is empty!\n");
else{ while(s->top!=0)
{ printf("%d->",s->data[s->top]);
s->top=s->top-1;
}
}
}

ElemType Pop(SeqStack *s)
{ if(StackEmpty(s)) return 0;
else return s->data[--s->top];
}

ElemType StackTop(SeqStack *s)
{ int i;
if(StackEmpty(s)) return 0;
else { i=s->top-1;
return s->data[i];} /*返回栈顶元素的值，但不改变栈顶指针*/
}

main(SeqStack *p)
{int n,i,k,h,x1,x2,select;
printf("create a empty stack!\n");
InitStack(p);
printf("input a stack length:\n");
scanf("%d",&n);
for(i=0;i<n;i++)
{ printf("input a stack value:\n");
scanf("%d",&k);
Push(p,k);
}
printf("select 1:Display()\n");
printf("select 2:Push()\n");
printf("select 3:Pop()\n");
printf("select 4:StackTop()\n");
printf("input a your select(1-4):\n");
scanf("%d",&select);
switch(select)
{case 1:{ display(p);
break;}
case 2:{ printf("input a push a value:\n");
scanf("%d",&h);
Push(p,h);
display(p);
break;}
case 3:{ x1=Pop(p);
printf("x1->%d\n",x1);
display(p);
break;
}
case 4:{ x2=StackTop(p);
printf("x2->%d",x2);
break;
}
}
}

2、运用栈实现数制转换
# define MAXSIZE 100
typedef int ElemType； /*将顺序栈的元素定义为整型*/
typedef struct
{ ElemType data[MAXSIZE];
int top;
}SeqStack;

void InitStack(SeqStack *s)
{s->top=0;
return 1;
}

int StackEmpty(SeqStack *s)
{ if(s->top==0) return 1;
else return 0;
}

int StackFull(SeqStack *s)
{ if(s->top==m-1) return 1;
else return 0;
}

void Push(SeqStack *s,int x)
{ if (StackFull(s)){ printf("the stack is overflow!\n");
return 0;
}
else { s->data[s->top]=x;
s->top++;
}
}

ElemType Pop(SeqStack *s)
{ ElemType y;
if(StackEmpty(s)){ printf("the stack is empty!\n");
return 0;
}
else { y=s->data[s->top];
s->top=s->top-1;
return y;
}
}

ElemType StackTop(SeqStack *s)
{ if(StackEmpty(s)) return 0;
else return s->data[s->top];
}
void Dec_to_Ocx (int N) /* n是非负的十进制整数，输出等值的八进制数*/
{
SeqStack *S； /*定义一个顺序栈*/
ElemType x；
Init_SeqStack(S)； /*初始化栈*/
if(N<0)
{
printf("\nError,The number must be over 0。")；
return；
}
if(!N) Push(S,0)；
while(N) /*自右向左产生八进制的各位数字，并将其进栈*/
{ Push(S，N%8)； /*余数入栈 */
N=N/8； /*商作为被除数*/
}
printf("Number %d converted to OCT:",N);
while(StackEmpty(S)) /*栈非空时退栈输出*/
{ x=Pop(S)；
printf(“%d”,x)；
}
printf("\n");
}
main( )
{ int n;
printf("Input a number to convert to OCT:\n");
scanf("%d",&n);
Dec_to_Ocx (n);
}

3、实现循环队列的顺序存储
#define maxsize 100
typedef struct
{int data[maxsize];
int front;
int rear;
}seqqueue;

int sqinit(seqqueue *p)
{
p->front=0;p->rear=0;
return 1;}

int enqueue(seqqueue *q, int e)
{if((q->rear+1)%maxsize==q->front)
return 0;
else
q->data[q->rear]=e;
q->rear=(q->rear+1)%maxsize;
return 1;
}

int dequeue(seqqueue *q)
{int e;
if (q->front==q->rear)
return 0;
e=q->data[q->front];
q->front=(q->front+1)%maxsize;
return e;
}

int empty(seqqueue *q)
{int v;
if (q->front==q->rear)
v=1;
else v=0;
return v; }

int gethead(seqqueue *q)
{int e;
if (q->front==q->rear) e=-1;
else e=q->data[q->front];
return e;
}

void display(seqqueue *q)
{int s;
s=q->front;
printf("the sequeue is display:\n");
if (q->front==q->rear)
printf("the sequeue is empty!