中国地质大学江城学院
数据结构课内实验报告
姓 名
班级学号
指导教师
20##年 月日
目 录
实验一 线性表............................................................................................................... 4
1 实验内容............................................................................................................... 4
2 算法思想描述........................................................................................................ 4
3 操作算法的实现..................................................................................................... 4
4 主测试程序............................................................................................................ 7
5 运行结果............................................................................................................... 8
实验二 堆栈和队列........................................................................................................ 8
1 实验内容............................................................................................................... 8
2 算法思想描述........................................................................................................ 8
3 操作算法的实现..................................................................................................... 8
4 主测试程序.......................................................................................................... 10
5 运行结果............................................................................................................. 10
实验三 串.................................................................................................................... 10
1 实验内容............................................................................................................. 10
2 算法思想描述...................................................................................................... 10
3 操作算法的实现................................................................................................... 11
4 主测试程序.......................................................................................................... 12
5 运行结果............................................................................................................. 12
实验四 数组................................................................................................................. 12
1 实验内容............................................................................................................. 12
2 算法思想描述...................................................................................................... 12
3 操作算法的实现................................................................................................... 13
4 主测试程序.......................................................................................................... 16
5 运行结果............................................................................................................. 17
实验一 线性表
1 实验内容
编写不带头结点单链表的初始化、插入、删除和输出操作算法。
2 算法思想描述
插入：在不设头结点的单链线性表L中第i个位置之前插入元素e，计数器初值为1，p指向第1个结点，i值不合法，生成新结点，以下将其插入L中，给s的data域赋值e，新结点指向原第1个结点，L指向新结点(改变L)，插在表的其余处，寻找第i-1个结点，p指向下一个结点大于表长+1，插入失败。新结点指向原第i个结点，原第i-1个结点指向新结点，插入成功。删除：在不设头结点的单链线性表L中，删除第i个元素，并由e返回其值，计数器初值为1，p指向第1个结点，表L空，删除失败，删除第1个结点，L由第2个结点开始(改变L)，将待删结点的值赋给e，删除并释放第1个结点，寻找第i个结点，并令p指向其前驱，计数器+1，P指向下一个位置，删除位置不合理，删除失败。q指向待删除结点，待删结点的前驱指向待删结点的后继，将待删结点的值赋给e，释放待删结点，删除成功。
3 操作算法的实现
#include<stdio.h>
#include<stdlib.h>
struct clist
{
int num;
struct clist *next;
};
typedef struct clist node;
typedef node *clink;
void Printlist(clink head)
{
clink ptr;
if(head==NULL)
{
printf("\n");
}
else
{
ptr=head;
do
{
ptr=ptr->next;
printf("[%d]",ptr->num);
}while(ptr!=head);
printf("\n");
}
}
clink Insertnode(clink head,clink ptr,int x)
{
clink newnode;
newnode=(clink)malloc(sizeof(node));
if(!newnode)
{
return NULL;
}
newnode->num=x;
newnode->next=NULL;
if(head==NULL)
{
head=newnode;
newnode->next=head;
}
else
{
if(ptr==NULL)
{
newnode->next=head->next;
head->next=newnode;
}
else
{
newnode->next=head->next->next;
head->next->next=newnode;
}
}
return head;
}
clink Findnode(clink head,int x)
{
clink ptr,ptr1;
ptr1=NULL;
if(head==NULL)
{
return NULL;
}
else
{
ptr=head;
do
{
if(ptr->num==x)
{
ptr1=ptr;
break;
}
ptr=ptr->next;
}while(ptr!=head);
return ptr1;
}
}
clink Deletnode(clink head,clink ptr)
{
clink ptr1;
ptr1=head;
if(head->next==head)
{
head=NULL;
}
else
{
while(ptr1->next!=ptr)
{
ptr1=ptr1->next;
}
ptr1->next=ptr1->next->next;
if(ptr==head)
{
head=ptr1;
}
}
return head;
}
void Freelist(clink head)
{clink ptr,ptr1;
ptr1=head;
do
{ptr=head->next;
head=head->next->next;
free(ptr);
}while(ptr!=ptr1);}
4 主测试程序
void main()
{ int arry[6]={9,7,3,4,5,6};
int i,num;
clink head,ptr;
head=NULL;
head=Insertnode(head,head,arry[0]);
if(!head)
{printf("内存分配错误\n");
exit(1);
}
printf("创建第一节点-->");
Printlist(head);
head=Insertnode(head,NULL,arry[1]);
printf("插入第一节点钱-->");
Printlist(head);
for(i=2;i<6;i++)
{head=Insertnode(head,head,arry[i]);
printf("插入节点之后");
Printlist(head);}
while(1){
printf("请输入查询值-->");
scanf("%d",&num);
if(num<0)
{
exit(1);
}
else
{
ptr=Findnode(head,num);
if(ptr==NULL)
{printf("找不到相应的编号\n");
continue;}
head=Deletnode(head,ptr);
printf("删除后的链表-->");
Printlist(head);
}}
Freelist(head);
}
5 运行结果
实验二 堆栈和队列
1 实验内容
假设以带头结点的单循环链表实现链式队列，并且要求只设尾指针，不设头指针，编写实现这种链式队列初始化、入队列和出队列操作的函数。
2 算法思想描述
创建空链表，设置尾指针，在进行队列初始化、入队列和出队列的算法操作。
3 操作算法的实现
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
typedef int DataType;
typedef struct qnode
{
DataType data;
struct qnode *next;
}LQNode;
typedef struct
{
LQNode *rear;
}LQueue;
void QueueInitiate(LQueue *Q)
{
Q->rear=(LQNode *)malloc(sizeof(LQNode));
Q->rear->next=Q->rear;
}
void QueueAppend(LQueue *Q,DataType x)
{
LQNode *p;
p=(LQNode *)malloc(sizeof(LQNode));
p->data=x;
Q->rear->next=p;
p->next=Q->rear->next;
Q->rear=p;
}
int QueueDelete(LQueue *Q,DataType *d)
{
LQNode *p,*front;
front=Q->rear->next;
if(front->next==front)
{
printf("队列为空！");
return 0;
}
else
{
p=front->next;
*d=p->data;
front->next=p->next;
free(p);
return 1;
}
}
void QueuePrint(LQueue *Q)
{
LQNode *p;
p=Q->rear->next;
if(p!=NULL)
printf("%d\n",p->data);
}
4 主测试程序
#include"string.h"
void main()
{
LQueue Q;
QueueInitiate(&Q);
QueueAppend(&Q,6);
QueuePrint(&Q);
QueueAppend(&Q,9);
QueuePrint(&Q);
}
5 运行结果
实验三 串
1 实验内容
编写函数实现串S和串T的比较操作，要求比较结果包含大于、小于和等于三种情况。
2 算法思想描述
先定义串s和串t的长度为n和m，设比较的起始位置都是0，当串s和串t的长度相等，在比较对应的任何字符是否相等，如果相等，则说明串s和串t相等。当串s的长度大于串t的长度，说明串s大于串t,反之，则小于。当串s和串t的长度相等，①若串s与串t的前n个字符相等，则s<t；②若串t与串s的前n个字符相等，则s>t.
3 操作算法的实现
#include<stdio.h>
#include<malloc.h>
#include<string.h>
typedef struct
{
char *str;
int maxLength;
int length;
}DString;
void Initiate (DString *S,int max,char *string)
{
int i;
S->str=(char *)malloc(sizeof(char) *max);
S->maxLength=max;
S->length=strlen(string);
for(i=0;i<S->length;i++)
S->str[i]=string[i];
}
int Compare (DString S,DString T)
{
int n=S.length,m=T.length;
int i=0,j=0,tag;
while(i<n&&j<m)
{
if(S.str[i]==T.str[i])
{i++;
j++;
}
else if(S.str[i]>T.str[j])
{
tag=1;
return tag;
}
else
{
tag=-1;
return tag;
}
}
if(n==m) tag=0;
else if(n>m) tag=1;
else if(n<m) tag=-1;
return tag;
}
4 主测试程序
void main()
{
DString String1,String2;
int max1=10,max2=10,c;
Initiate(&String1,max1,"zhongyuhua ");
Initiate(&String2,max2,"zhong ");
c=Compare(String1,String2);
printf("%d ",c);
printf("\n");
}
5 运行结果
实验四 数组
1 实验内容
设稀疏矩阵采用三元组顺序表存储结构，编写函数实现稀疏矩阵的转置运算B=AT。已知稀疏矩阵A中的非零元三元组的排列次序是先按行下标排列，在行下标下相同时按列下标排列，要求稀疏矩阵B中的非零元三元组的排列次序也是先按行下标排列，在行下标相同时按列下标排列。
2 算法思想描述
先创建三元组，输入数字使用AddSmatrix函数比较两个数字的大小，在矩阵相加，采用三元组表存储表示矩阵，然后矩阵复制，销毁稀疏矩阵的三元组顺序表，然后显示稀疏矩阵的三元组顺序表，
3 操作算法的实现
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#define OK 1
#define ERROR 0
#define MAXSIZE 12500
typedef int Status;
typedef int ElemType;
typedef struct
{
int i,j;
ElemType e;
}Triple;
typedef struct
{
Triple date[MAXSIZE+1];
int mu,nu,tu;
}TSMatrix;
Status CreatSMatrix( TSMatrix *M)
{
int row,col,date,k;
printf("请输入行数列数和非零元个数\n");
scanf("%d,%d,%d",&(*M).mu,&(*M).nu,&(*M).tu);
while( M->mu <= 0 || M->nu <= 0 || M->tu > ( M->mu * M->nu ) || M->tu > MAXSIZE)
{
printf("输入不正确，请重新输入\n");
fflush(stdin);
scanf("%d,%d,%d",&M->mu,&M->nu,&M->tu);
}
(*M).date[0].i = 0;
for( k = 1; k <= (*M).tu ; k++)
{
printf("Please input the row,col and date\n");
scanf("%d,%d,%d",&row,&col,&date);
M->date[k].i = row;
M->date[k].j = col;
M->date[k].e = date;
}
printf("输入非空元素组成的三元组完毕!\n");
return OK;
}
Status comp( int a, int b)
{
int i;
if( a < b)
i = 1;
if( a == b)
i = 0;
if( a > b)
i = -1;
return i;
}
Status AddSMatrix( TSMatrix &A, TSMatrix &B, TSMatrix *C)
{Triple *Ap,*Bp,*Ae,*Be,*Ch,*Ce;
if( A.mu != B.mu || A.nu != B.nu)
{ printf("\nA and B is not compared\n");
return ERROR; }
// if( (*C).date )
// free( (*C).date );
C->mu = A.mu;
C->nu = A.nu;
Ap = &A.date[1];
Bp = &B.date[1];
Ae = &A.date[A.tu];
Be = &B.date[B.tu];
Ch = Ce = C->date;
while( Ap <= Ae && Bp <= Be)
{Ce++;
switch( comp( Ap->i, Bp->i ) )
{case 1:
{*Ce = *Ap;
Ap++;}break;
case -1:
{*Ce = *Bp;
Bp++;}break;
case 0:
{ switch( comp(Ap->j,Bp->j) )
{ case 0:
{ *Ce = *Ap;
Ce->e += Bp->e;
if( !Ce->e )
Ce--;
Ap++;
Bp++;}break;
case 1:
{ *Ce = *Ap;
Ap++;}break;
case -1:
{ *Ce = *Bp;
Bp++;
}} }break; }}
if( Ap > Ae)
while( Bp <= Be )
{Ce++;
*Ce = *Bp;
Bp++;}
if( Bp > Be)
while( Ap <= Ae)
{ Ce++;
*Ce = *Ap;
Ap++;}
C->tu = Ce - Ch;
return OK;}
Status Transpose( TSMatrix M, TSMatrix &T)
{ int k;
T.mu = M.nu;
T.nu = M.mu;
T.tu = M.tu;
if( T.tu )
{ for( k = 1; k <= M.tu; k++)
{ T.date[k].i = M.date[k].j;
T.date[k].j = M.date[k].i;
T.date[k].e = M.date[k].e; }}
printf("\n矩阵转置完毕!");
return OK;}
Status CopySMatrix( TSMatrix M, TSMatrix &T)
{ int k;
if( M.tu )
{ for( k = 1; k <= M.tu; k++)
{T.date[k].i = M.date[k].i;
T.date[k].j = M.date[k].j;
T.date[k].e = M.date[k].e;} }
printf("复制完毕!");
return OK;}
Status DestroySMatrix( TSMatrix &M)
{ if( M.mu <= 0 || M.nu <= 0 || M.tu > M.mu * M.nu)
{ printf("\n不存在矩阵!\n");
return ERROR;}
for( int k = 1; k < M.tu + 1; k++)
{ M.date[k].i = 0;
M.date[k].j = 0;
M.date[k].e = 0;}
M.mu = 0;
M.nu = 0;
M.tu = 0;
printf("\n销毁完毕!\n");
return OK;}
Status PrintSMatrix( TSMatrix M)
{ int k;
if( M.mu <= 0 && M.nu <= 0)
{ printf("\n稀疏矩阵的三元组顺序表不存在\n");
return ERROR;}
else
{printf("稀疏矩阵的三元组顺序表是:\n");
for( k = 1; k <= M.tu; k++)
{ printf(" (%3d%3d%3d) ",M.date[k].i,M.date[k].j,M.date[k].e);}
printf("\n显示完毕!");
return OK;
}}
4 主测试程序
void main()
{TSMatrix M, T, A, B, C;
CreatSMatrix( &M );
PrintSMatrix( M );
Transpose( M, T );
printf("\n转置后的矩阵是:\n");
PrintSMatrix( T );
printf("\n矩阵的复制\n");
CopySMatrix( M, T );
printf("\n\n\n复制的矩阵为\n");
PrintSMatrix( T );
printf("\n\n\n");
printf("建立矩阵A");
CreatSMatrix( &A );
printf("\n建立矩阵B");
CreatSMatrix( &B );
printf("\nA+B\n");
AddSMatrix( A, B, &C );
printf("\n矩阵M和B相加为:\n");
PrintSMatrix( C );
DestroySMatrix( M );
DestroySMatrix( T );
DestroySMatrix( B );
DestroySMatrix( C );
// PrintSMatrix( M );
printf("\n\n\n\t\t\t程序完毕!\n\n\n");}
5 运行结果
