武汉理工大学理学院电信科数据结构上机实验汇总武汉理工大学理学院电信科数据结构上机实验汇总
实验一 线性表的基本操作
1、顺序表操作源程序:
#include #define MAXLEN 100 typedef int datatype; typedef struct
{
datatype data[MAXLEN];
int length;
}Seqlist;
Seqlist L;
void Initlist(Seqlist *L)//顺序表初始化
{
L->length=0;
}
void Createlist(Seqlist *L,int ...
武汉理工大学理学院电信科数据结构上机实验汇总
实验一 线性
的基本操作
1、顺序表操作源程序:
#include
#define MAXLEN 100 typedef int datatype; typedef struct
{
datatype data[MAXLEN];
int length;
}Seqlist;
Seqlist L;
void Initlist(Seqlist *L)//顺序表初始化
{
L->length=0;
}
void Createlist(Seqlist *L,int n)//创建顺序表 {
int i;
printf("请输入d%个整数:\n",n);
for(i=0;idata[i]);
L->length=n;
}
int Getelem(Seqlist *L,int i,datatype *x)//按位查找元素 {
if(i<1||i>L->length)
return 0;
else
{
*x=L->data[i-1];
return 1;
}
}
int Locate(Seqlist *L,datatype x)//按值查找元素 {
int i=0;
while(ilength&&L->data[i]!=x)
i++;
if(i>=L->length)
return 0;
else
return i+1;
}
int Inselem(Seqlist *L,int i,datatype x)//元素插入 {
int j;
if(L->length>=MAXLEN)
{
printf("顺序表已满!!/n");
return -1;
}
if(i<1||i>L->length+1)
return 0;
if(i==L->length)
{
L->data[i-1]=x;
L->length++;
return 1;
}
else
{
for(j=L->length-1;j>=i-1;j--)
L->data[j+1]=L->data[j];
L->data[i-1]=x;
L->length++;
return 1;
}
}
int Delelem1(Seqlist *L,int i,datatype *x)//按位删除元素 {
int j;
if(L->length==0)
{
printf("该线性顺序表为空!!\n");
return 0;
}
if(i<1||i>L->length)
{
printf("不存在目标元素!!\n");
return 0;
}
else
{
*x=L->data[i-1];
for(j=i;jlength;j++)
L->data[j-1]=L->data[j];
L->length--;
return 1;
}
}
/*void Delelem2(Seqlist *L,datatype x)//按值删除元素
{
int k,j;
for(x==L->data[j];;j++)
{
for(k=j;klength;k++)
L->data[k]=L->data[k+1];
L->length--;
}
else
{
printf("顺序表中没有该元素执行删除!!/n");
}
}
} */
void displaylist(Seqlist *L) {
int i;
for(i=0;ilength;i++)
printf("%5d",L->data[i]);
printf("\n");
}
void manu()
{
printf("*****************命令菜单********************\n");
printf("1 创建顺序表\n");
printf("2 按位查找元素\n");
printf("3 按值查找元素\n");
printf("4 元素插入\n");
printf("5 按位删除元素\n");
/*printf("6 按值删除元素\n");*/
printf("*********************************************\n");
printf("请选择操作(注意:请先创建顺序表!):\n"); }
void main()
{
Seqlist L;
datatype x;
int n,i,loc,in2;
while(1)
{
manu();
scanf("%d",&in2);
switch(in2)
{
case 1:
Initlist(&L);
printf("请输入元素个数:\n");
scanf("%d",&n);
Createlist(&L,n);
printf("所建立的线性表为:\n");
displaylist(&L);
break;
case 2:
printf("请输入所查元素的位置:\n");
scanf("%d",&i);
if(Getelem(&L,i,&x))
printf("线性表中第%d个元素值为:%3d\n",i,x);
else
printf("输入位置有误!!");
break;
case 3:
printf("请输入所查元素的值:\n");
scanf("%d",&x);
loc=Locate(&L,x);
if(loc)
printf("该元素的位置为:%d\n",loc);
else
printf("线性表中无此元素!!\n");
break;
case 4:
printf("请输入需要插入元素的位置与值:\n");
scanf("%d%d",&i,&x);
if(Inselem(&L,i,x))
displaylist(&L);
else
printf("插入位置有误!\n");
break;
case 5:
printf("请输入所要删除元素的位置:\n");
scanf("%d",&i);
if(Delelem1(&L,i,&x))
displaylist(&L);
else
break;
/*case 6:
printf("请输入需要删除的元素值:\n");
scanf("%d",&x);
Delelem2(&L,x);
displaylist(&L);
break;*/
}
}
}
2、约瑟夫环问源程序:
#include"stdio.h"
#include"stdlib.h"
#define MAXNUM 30 /*需要处理的最多人数为30*/
typedef struct LinkList
{ int data;
struct LinkList *next;
}LinkList;
/*函数的声明*/
LinkList *CreatList();
void InitList(LinkList *,int ); int Getdata();
int GetPersonNumber();
int GetCountValue();
void GetOutputOrder(LinkList* , int, int, int* );
void printResult(int * ,int );
LinkList *CreatList()
{
LinkList *L;
L = (LinkList *)malloc(sizeof(LinkList));
if (L == NULL)
{ printf("分配内存失败~");
exit(1);
}
return L;
}
void InitList(LinkList *L, int personNumber)
{
LinkList *p, *q;
int i ;
p = L;
p->data = Getdata();
for (i = 2; i <= personNumber; i++)
{ q = (LinkList *)malloc(sizeof(LinkList));
if (q == NULL)
{ printf("分配内存空间失败~");
exit(1);
}
q->data =Getdata();
p->next = q;
p = q;
}
p->next = L;
}
int GetPersonNumber()
{
int personNumber;
printf("请输入人数:");
scanf("%d",&personNumber);
while (personNumber > MAXNUM || personNumber < 0)
{ printf("\n你输入的数字无效,请输入在0到%d的整数",MAXNUM);
scanf("%d",&personNumber);
}
printf("本次求约瑟夫环的出列顺序人数为%d人。\n",personNumber);
return personNumber; }
int Getdata()
{
int data;
printf("请输入数据的值:");
scanf("%d",&data);
return data;
}
int GetValue()
{
int m;
printf("请每次报数的值m:");
scanf("%d",&m);
return m;
}
void GetOutputOrder(LinkList *L, int personNumber, int m, int array[MAXNUM])
{
LinkList *p, *q;
int count = 1, i = 0;
p = L;
while (personNumber)
{
while (count != m)
{
q = p;
p = p->next;
count++;
}
array[i++] = p->data;
q->next = p->next;
free(p); p = q->next;
count = 1;
personNumber--;
}
}
void printResult(int array[],int personNumer)
{
int i;
printf("\n按每人的编号(1-%d)依次出列的顺序为:",personNumer);
for(i = 0; i < personNumer; i++)
printf("%-3d",array[i]);
printf("\n");
}
main()
{
LinkList *L;
int personNumber, m;
int array[MAXNUM];
printf("约瑟夫环问题。\n");
personNumber = GetPersonNumber();
m = GetValue();
L=CreatList();
InitList(L, personNumber);
GetOutputOrder(L, personNumber, m, array);
printResult(array, personNumber);
system("pause");
return 0;
}
实验二 栈与队列的基本操作
1、栈的基本操作源程序:
#include
#include
#include #define STACKSIZE 100 //存储空间初始分配量 #define STACKINCREMENT 10 //存储空间分配增量 //typedef int selemtype; typedef struct
{
int *base; //栈的基址即栈底指针
int *top; //栈顶指针
int stacksize; //当前分配的空间 }sqstack ;
int initstack(sqstack &s)//构造一个空栈S
{
s.base=(int *)malloc(STACKSIZE *sizeof(int));
if(!s.base)
{
printf("分配失败,结束程序!!");
return -1;
}
s.top=s.base; //空栈
s.stacksize=STACKSIZE;
return 0;
}
void gettop(sqstack s, int &e)//若栈不为空,则用e返回S的栈顶元素
{
if(s.top==s.base)
printf("栈空,无元素!!");
e=*(s.top-1);
printf("%3d\n",e);
}
int push(sqstack &s,int e)//进栈操作
{
if(s.top-s.base>=s.stacksize)
{
s.base=(int *)realloc(s.base,(s.stacksize+STACKSIZE)*sizeof(int));
if(!s.base)
{
printf("追加内存失败!!");
return 0;
}
s.top=s.base+s.stacksize;
s.stacksize+=STACKSIZE;
}
*s.top++=e;
return 1;
}
int pop(sqstack &s,int &e)//删除栈顶元素 {
if(s.base==s.top)
{
printf("空栈无元素!!\n");
return 0;
}
else
{
e=*--s.top;
return 1;
}
}
void display(sqstack s)//遍历栈
{
sqstack b;
int a;
b=s;
if(b.base==b.top)
printf("空栈无元素!!");
while(b.top!=b.base)
{
a=*--b.top;
printf("%3d\n",a);
}
}
void manue()
{
printf("*********************************************\n");
printf(" 1 创建栈\n");
printf(" 2 进栈操作\n");
printf(" 3 取栈顶元素\n");
printf(" 4 删除栈顶元素\n");
printf(" 5 遍历栈\n");
printf(" 0 退出操作\n");
printf("*********************************************\n");
printf("请输入工作项目(如果没有建立工作栈,请先创建~):\n");
}
void main()
{
int i,e;
sqstack s;
while(1)
{
manue();
scanf("%d",&i);
switch(i)
{
case 1:
if(!initstack(s))
printf("创建成功~~\n");
break;
case 2:
printf("请输入进栈元素:\n");
scanf("%d",&e);
push(s,e);
break;
case 3:
gettop(s,e);
break;
case 4:
if(pop(s,e))
printf("删除的头元素为:%3d\n",e);
break;
case 5:
display(s);
break;
case 0:
exit(0);
default:
printf("输入命令有误~~\n");
break;
}
}
}
2、队列的基本操作源程序:
(1)链队:
#include #include typedef struct qnode {
int data;
struct qnode *next; }qnode,*queueptr; typedef struct
{
queueptr front;
queueptr rear; }linkqueue;
int initqueue(linkqueue &Q)//初始化队列 {
Q.front=Q.rear=(queueptr)malloc(sizeof(qnode));
if(!Q.front)
return 0;
Q.front->next=NULL;
return 1;
}
int enqueue(linkqueue &Q,int e)
{
queueptr p;
p=(queueptr)malloc(sizeof(qnode));
if(!p)
return 0;
else
{
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return 1;
}
}
int dequeue(linkqueue &Q,int &e)
{
queueptr p;
if(Q.front==Q.rear)
return 0;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p)
Q.rear=Q.front;
free(p);
return e;
}
int queuelength(linkqueue &Q)
{
int length=0;
while(++Q.front!=Q.rear)
length++;
return length;
}
void showqueue(linkqueue &Q)
{
queueptr p;
p=Q.front->next;
if(p==NULL)
printf("队列为空,无元素!\n");
else
{
printf("队列元素为:\n");
while(p!=NULL)
{
printf("%5d\n",p->data);
p=p->next;
}
}
}
void manue()
{
printf("*************************************\n");
printf(" 1 创建列表\n");
printf(" 2 元素入队操作\n");
printf(" 3 元素删除操作\n");
printf(" 4 显示队内元素\n");
printf(" 0 退出操作\n");
printf("**************************************\n");
printf("请选择操作菜单(0-4):");
}
void main()
{
linkqueue Q;
int e,i,k=1;
while(k)
{
manue();
scanf("%d",&i);
switch(i)
{
case 0:
k=0;
break;
case 1:
if(initqueue(Q))
printf("成功创建队列!!\n");
break;
case 2:
printf("请输入入队元素值:\n");
scanf("%d",&e);
if(enqueue(Q,e))
printf("入队操作成功!\n");
showqueue(Q);
break;
case 3:
printf("被删除元素的值为:%3d\n",dequeue(Q,e));
break;
case 4:
showqueue(Q);
break;
default:
printf("输入命令有误~~\n");
break;
}
}
}
(2)循环队:
#include
#include #define MAXSIZE 100 typedef struct
{
int *base;
int front,rear; }squeue;
int initqueue(squeue &Q) {
Q.base=(int *)malloc(MAXSIZE * sizeof(int));
if(!Q.base)
return 0;
Q.front=Q.rear=0;
return 1;
}
int queuelength(squeue Q) {
return(Q.rear-Q.front+MAXSIZE)%MAXSIZE;
}
int enqueue(squeue &Q,int e) {
if((Q.rear+1)%MAXSIZE==Q.front)
return 0;
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MAXSIZE;
return 1;
}
int dequeue(squeue &Q,int &e) {
if(Q.front==Q.rear)
return 0;
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAXSIZE;
return e;
}
void showqueue(squeue &Q) {
squeue p;
p.front=Q.front;
if(p.front==Q.rear)
printf("队列为空,无元素!\n");
else
{
printf("当前队列元素为:\n");
while(p.front!=Q.rear)
{
printf("%5d\n",p.base[p.front]);
p.front=(p.front+1)%MAXSIZE;
}
}
}
void manue()
{
printf("*********************************************\n");
printf(" 1 创建循环队列\n");
printf(" 2 入队操作\n");
printf(" 3 出队操作\n");
printf(" 4 显示当前队列元素个数\n");
printf(" 5 输出队列元素\n");
printf(" 0 退出操作\n");
printf("*********************************************\n");
printf("请输入操作命令:\n");
}
void main()
{
int i,e,k=1;
squeue *Q;
while(k=1)
{
manue();
scanf("%d",&i);
switch(i)
{
case 1:
if(initqueue(*Q))
printf("创建成功~~\n");
break;
case 2:
printf("请输入入队元素:\n");
scanf("%d",&e);
if(enqueue(*Q,e))
showqueue(*Q);
break;
case 3:
printf("出队元素为:\n",dequeue(*Q,e));
showqueue(*Q);
break;
case 4:
printf("当前队列长度为:%d\n",queuelength(*Q));
break;
case 5:
showqueue(*Q);
break;
case 0:
k=0;
break;
default:
printf("命令输入有误~\n");
break;
}
}
}
实验三 二叉树的基本操作与哈夫曼编码 1、二叉树的基本操作源程序:
#include
#include
#define max 100
int count1,count2;
typedef struct bitnode {
char data;
struct bitnode *lchild,*rchild; }bitnode;
typedef bitnode *bittree;
void creatbittree(bittree &T) {
char ch;
if((ch=getchar())==' ')
T=NULL;
else
{
T=(bitnode *)malloc(sizeof(bitnode));
T->data=ch;
creatbittree(T->lchild);
creatbittree(T->rchild);
}
}
void xiantree(bittree &T) {
if(T==NULL)
;
else
{
printf("%3c\n",T->data);
xiantree(T->lchild);
xiantree(T->rchild);
}
}
void zhongtree(bittree &T) {
if(T==NULL)
;
else
{
zhongtree(T->lchild);
printf("%3c\n",T->data);
zhongtree(T->rchild);
}
}
void houtree(bittree &T)
{
if(T==NULL)
;
else
{
houtree(T->lchild);
houtree(T->rchild);
printf("%3c\n",T->data);
}
}
void yezinum(bittree &T) {
if(T)
{
if(T->lchild==NULL&&T->rchild==NULL)
count1++;
yezinum(T->lchild);
yezinum(T->rchild);
}
}
void jiediannum(bittree &T) {
if(T)
{
count2++;
jiediannum(T->lchild);
jiediannum(T->rchild);
}
}
void manue()
{
printf("*************************************\n");
printf(" 1 创建树\n");
printf(" 2 先序遍历\n");
printf(" 3 中序遍历\n");
printf(" 4 后序遍历\n");
printf(" 5 显示叶子节点数\n");
printf(" 6 显示总节点数\n");
printf(" 0 退出操作\n");
printf("**************************************\n");
printf("请选择操作菜单(0-4):"); }
void main()
{
int i;
bittree T;
while(1)
{
manue();
scanf("%d",&i);
switch(i)
{
case 1:
printf("请按先序遍历输入二叉树的各结点,空格表示空结点:\n");
getchar();
creatbittree(T);
printf("二叉树建立成功~~\n");
break;
case 2:
xiantree(T);
printf("输出完毕。\n");
break;
case 3:
zhongtree(T);
printf("输出完毕。\n");
break;
case 4:
houtree(T);
printf("输出完毕。\n");
break;
case 5:
yezinum(T);
printf("叶子结点数目为:%3d\n",count1);
break;
case 6:
jiediannum(T);
printf("结点数目为:%3d\n",count2);
break;
case 0:
printf("退出操作~~\n");
exit(0);
default:
printf("命令输入有误~~\n");
break;
}
}
}
*******************************************************************************
*******************************************************************************
2、哈夫曼编码源程序:
#include
#include
#include
#define maxnum 100
#define INF 32767
typedef struct
{
int weight;
int parent,lchild,rchild; } hfmnode,*huffmantree; typedef char * *huffmancode;
void select(huffmantree &HT, int end,int *s1,int *s2)//最小权值结点选择 {
int i, j;
int min=INF;
for(i=1;i<=end;i++)
{
if(HT[i].parent!=0) continue;
if(HT[i].weight*s2)
{
i=*s1;
*s1=*s2;
*s2=i;
}
}
void coding(huffmantree &HT,huffmancode &HC,int *w,int n)//构建哈夫曼树并编码
{
int m,i,c,start,f,s1,s2;
char *cd;
huffmantree p;
if(n<1)
return ;
m=2*n-1;
HT=(huffmantree)malloc((m+1)*sizeof(hfmnode));
for(p=HT,++p,i=1;i<=n;i++,++p)
{
p->weight=w[i];
p->lchild=0;
p->parent=0;
p->rchild=0;
}
for(;i<=m;++i,++p)
{
p->weight=0;
p->lchild=0;
p->parent=0;
p->rchild=0;
}
for(i=n+1;i<=m;++i)
{
select(HT,i-1,&s1,&s2);
HT[s1].parent=i; HT[s2].parent=i;
HT[i].lchild=s1; HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
HC=(huffmancode)malloc((n+1)*sizeof(char *));
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='\0';
for(i=1;i<=n;++i)
{
start=n-1;
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
if(HT[f].lchild==c)
cd[--start]='0';
else
cd[--start]='1';
HC[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(HC[i],&cd[start]);
}
free(cd);
}
void main()
{
huffmantree HT;
huffmancode HC;
int i,n;
int w[maxnum];
printf("请输入叶子结点的个数:\n");
scanf("%d",&n);
printf("请输入叶子结点权值:\n");
for(i=1;i<=n;i++)
scanf("%d",&w[i]);
coding(HT,HC,w,n);
for(i=1;i<=n;i++)
{
printf("\n权值%d对应的编码为:",w[i]);
puts(HC[i]);
}
}
实验四 内部排序基本操作
1,、各个排序源程序汇总:
#include #include
int x=1;//用于快排次数计数
void chushi(int quick[])//初始化操作数组 {
int i;
printf("输入八个整数:\n");
for(i=1;i<9;i++)
scanf("%d",&quick[i]);
}
void copy(int quick[],int b[])//将操作数组复制 {
int i;
for(i=1;i<9;i++)
b[i]=quick[i]; }
void xianshi(int q[])//显示当前排序结果 {
int i;
for(i=1;i<9;i++)
printf("%5d",q[i]);
printf("\n");
}
/**************************************************************/
//直插排序
void zhicha(int quick[]) {
time_t start,end,time;
start=clock();
int i,j,k=1;
int *q,b[9];
copy(quick,b);
q=b;
for(i=2;i<9;i++)
{
if(q[i]=high+1;j--)
q[j+1]=q[j];
q[high+1]=q[0];
printf("运用折半排序第%d次排序结果为:\n",k++);
xianshi(q);
}
end=clock();
time=end-start;
printf("时间共计%d",time); }
/***********************************************************/
//二路插入排序
void erlu(int quick[]) {
time_t start,end,time;
start=clock();
int b[8],c[8];
int i,j,first,final,mid,index;
for(i=1;i<9;i++)
{
b[i-1]=quick[i];
}
first=final=0;
c[0]=b[0];
for(i=1;i<8;i++)
{
if(c[final]<=b[i])
c[++final]=b[i];
else if(b[i]<=c[first])
{
first=(first+7)%8;
c[first]=b[i];
}
else
{
for(index=(final+7)%8;;index=(index+7)%8)
{
if(c[index]<=b[i])
{
mid=final++;
while(mid!=index)
{
c[(mid+1)%8]=c[mid];
mid=(mid+7)%8;
}
c[(index+1)%8]=b[i];
break;
}
}
}
}
printf("运用二路排序排序结果为:\n");
for(i=0;i<8;i++)
{
b[i]=c[first];
first=(first+1)%8;
printf("%5d",b[i]);
}
end=clock();
time=end-start;
printf("时间共计%d",time); }
/***************************************************************/
//希尔排序法
void shellsort(int b[],int dk)
{
int i,j,*q;
q=b;
for(i=dk+1;i<9;++i)
{
if(b[i]0&&(b[0]q[j+1])
{
q[0]=q[j];
q[j]=q[j+1];
q[j+1]=q[0];
temp=1;
}
}
if(!temp)
continue;
printf("运用冒泡排序第%d次排序结果为:\n",i);
xianshi(q);
}
end=clock();
time=end-start;
printf("时间共计%d",time); }
/*********************************************************************/
//快速排序
int partition(int b[],int low,int high)
{
int *q,temp;
b[0]=b[low];
temp=b[low];
while(low=temp)
high--;
b[low]=b[high];
while(low
本文档为【武汉理工大学理学院电信科数据结构上机实验汇总】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。