数据结构课程设计报告书Word下载.docx
《数据结构课程设计报告书Word下载.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计报告书Word下载.docx（32页珍藏版）》请在冰点文库上搜索。
i<
la.length;
i++）
{if（i%2==0）insert（lb,i/2,la.list[i]）;
//奇数位次元诩插入lb
elseinsert（lc,i/2,la.list[i]）;
//偶数位次元素插入lc
}
printf（"
\n您输入的线性表元素为:
\n\n"
print（la）;
线性表的奇数位次的元素为：
print（lb）;
线性表的偶数位次的元素为：
print（lc）;
v）
{printf（"
****本程序可以实现线性表奇偶位序的元素分别输出****\n\n\n"
inti,a;
请输入一个偶数作为线性表的长度：
scanf（"
%d"
&
a）;
while（a%2!
=0）
\n你刚才输入的是奇数，请重新输入一偶数：
v.length=a;
\n请输入线性表的元素（个数为你输入的偶数,超过个数的元素程序不计入）：
getchar（）;
v.length;
i++）
%c"
v.list[i]）;
//对la进行赋值
v）//构造一个空的线性表
{v.elem=（char*）malloc（max*sizeof（char））;
v.length=0;
v,intj,charc）
{v.list[j]=c;
//插入c
v.length++;
voidprint（sqlistv）
{inti;
v.list[i]）;
}//输出线性表元素
【调试和运行】
经过调试运行，程序均得到正确结果，例如输入9个元素adjfhres得到结果如下图：
【收获与体会】：
【2】已知线性表LA的数据元素（n个），现要求将LA的数据元素复制到另一个线性表LB中。
【程序设计思想】：
建立两个线性表la,lb。
对la进行输入赋值操作，然后对la线性表的每个元素依次对lb进行插入操作，从而得到线性表lb。
#definemax600//定义线性表最大长度
typedefstruct{
//输出线性表
*****************本程序可以实现线性表的复制******************\n"
sqlistla,lb;
//声明线性表
i++）//复制操作
{lb.list[i]=la.list[i];
lb.length++;
v）//输入元素，构造线性表
printf（"
\n请输入你想输入的线性表的长度：
\n"
v.length）;
\n请输入线性表的元素（超过长度的元素程序不计入）：
v）//建立空线性表
voidprint（sqlistv）//输出线性表元素
\n复制得到的线性表为：
【调试和运行】：
对程序进行调试和运行，输入9个元素tanwenzhi，得到结果如下图：
【3】：
设有一个线性表采用顺序存储结构，表中的数据元素值为正整数（n个）。
设在O（n）时间内，将线性表分成两为两部分，其中左半部分每个元素都小于原表的第一个元素，而右半部分则相反。
首先要建立一个线性表，对其进行赋值操作，然后进入主程序阶段，即voidpaixu（sqlistv）
{inti=0,j=v.length-1,x=v.list[0];
while（i<
j）
{
while（i<
j&
&
v.list[j]>
x）j=j-1;
if（i<
j）{v.list[i]=v.list[j];
i=i+1;
v.list[i]<
x）i=i+1;
j）{v.list[j]=v.list[i];
j=j-1;
v.list[i]=x;
把第一个元素作为比较基准，进行上式的循环，从而把小于第一个元素的排在左边，大于第一个元素的排在右边。
达到程序要求。
#definemax600
int*elem;
intlist[max];
voidpaixu（sqlist）;
**********本程序实现以第一个元素为标准左小右大分布***********\n"
sqlistl;
initial（l）;
inti=0,j=l.length-1,x=l.list[0];
l.list[j]>
j）{l.list[i]=l.list[j];
l.list[i]<
j）{l.list[j]=l.list[i];
l.list[i]=x;
print（l）;
v.elem=（int*）malloc（max*sizeof（int））;
\n请输入线性表的长度：
\n请输入%d个正整数：
v.length）;
voidprint（sqlistv）
\n重新分布以后的数列为:
inti;
i++）printf（"
%d"
对写好的程序进行编译通过无误，运行程序，输入八个整数：
35123414567367，运行得到的结果如下，达到了程序要求。
【4】：
设线性表LA＝（a1,a2,…,am），LB＝（b1,b2,…,bn）。
试编写一个算法，将LA、LB合并为线性表LC，使
要求LA、LB和LC均以单链表为存储结构，且LC表利用LA和LB中结点空间，这里m和n的值没有保存在头结点中，并分析算法时间复杂度。
首先建立三个线性表，对其中两个个进行赋值操作，得到原始的线性表，然后通过建立循环结构，再循环结构中判断出前两个线性表的元素的多少，根据判断的结果，分别对第三个空线性表进行插入操作，以达到程序的要求。
【程序核心语句】：
voidmerge1（LinkList&
A,LinkList&
B,LinkList&
C）//把链表A和B合并为C,A和B的元素间隔排列
p=A->
next;
q=B->
C=A;
while（p&
q）
{s=p->
p->
next=q;
//将B的元素插入
if（s）
{t=q->
q->
next=s;
//如A非空,将A的元素插入
}
p=s;
q=t;
【5】：
约瑟夫问题：
设编号为1，2，…，n的n（n>
0）个人按顺时针方向围坐一圈，每人持有一正整数密码。
开始时任选一个正整数作为报数上限值m，从第一个人开始顺时针方向自1起顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新从1报数。
如此下去，直到所有人全部出列为止。
令n最大值取30。
要求设计一个程序模拟此过程，求出出列编号序列（采用循环单链表结构）。
约瑟夫问题是一道经典的链表程序，有各种各样的算法细想，各种各样实现算法，这些都体现了程序的多样性。
对于这一经典问题，我采用循环链表结构，运用循环结构模拟游戏的过程，对于人数进行赋值，对于每个人的密码进行输入赋值，然后指定第一个密码，运用循环结构，通过主程序的作用，对出列号码进行存储，集中输出。
【程序设计代码】：
typedefstructnode////循环链表结构
intnum,code;
structnode*next;
}LinkList;
//建立单链表
*********本程序为约瑟夫问题的解决***********\n"
intm=0,n=0,i=0,j=0;
LinkList*head,*s,*r,*p;
//声明
\n请输入第一个m值:
scanf（"
m）;
\n请输入总人数:
n）;
\n输入%d个人依次的密码（!
数字只限于1到%d!
并以空格隔开）:
n,n）;
head=（LinkList*）malloc（sizeof（LinkList））;
//分配存储空间
head->
code）;
head->
num=1;
r=head;
for（i=1;
n;
i++）//依次出列
{
s=（LinkList*）malloc（sizeof（LinkList））;
//分配空间
s->
s->
num=i+1;
next=NULL;
r->
r=r->
}
r=head;
next=head;
\n出列顺序为:
//输出一次出列的序号
for（j=n;
j>
0;
j--）
if（m==1）
r->
num）;
p->
next=r->
m=r->
code;
else
for（i=1;
m-1;
p=r;
s=r->
s->
next=s->
r=s->
m=s->
free（s）;
//释放s
对程序进行编译无误，运行输入第一个密码为4，人数为23，每个人的密码依次为：
1、9、5、3、6、2、8、10、4、7、19、15、12、11、13、17、20、16、18、14、23、21、、22.运行得到结果如下图：
【实验二】栈和队列的基本操作
1．掌握栈和队列两种抽象数据类型的特点。
2．掌握顺序栈和链栈入栈、出栈的实现算法。
3．掌握栈满和栈空的描述方法。
4．掌握循环队列（顺序表示）和链队列入队、出队的实现算法。
5．掌握队满和队空的描述方法。
【实验内容】：
【1】：
试编写算法，在顺序存储结构下实现堆栈的下列运算：
（1）initstk（s）。
初始化操作，建立一个空栈s；
（2）emptystk（s）。
判定栈是否为空；
（3）pushstk（s）。
如果栈s不满，在栈顶插入x；
（4）popstk（s）。
如果栈s不空，删除栈顶元素，并返回该元素的值；
（5）getstk（s）。
如果栈s不空，返回栈顶元素。
这些都是栈的基本操作的训练，按照栈的定义和基本的操作来实现就可以了，考查的是基本操作的运用。
【程序核心算法】：
#definestack_init_size100;
#definestackincreament10;
selemtype*base;
selemtype*top;
intstacksize;
}sqstack;
（1）初始化操作，建立一个空栈s
voidinitstk（sqstack&
s）
{s.base=（selemtype*）malloc（stack_init_size*sizeof（selemtype））;
if（!
s.base）exit（overflow）;
s.top=s.base;
s.stacksize=stack_init_size;
returnok;
（2）判定栈是否为空
voidemptystk（sqstacks）
if（s.top==s.base）returnyes;
elsereturnno;
（3）如果栈不满，在栈顶插入x
voidpushstk（sqstack&
s,selemtypex）
{if（s.top-s.base<
s.stacksize）
*s.top++=e;
（4）如果栈不空，删除栈顶元素，并返回该元素值
voidpopstk（sqstack&
s,selemtype&
e）
if（s.top==s.base）returnerror;
e=*--s.top;
（5）如果栈不空，返回栈顶元素
voidgetstk（sqstacks,selemtype&
{if（s.top==s.base）returnerror;
e=*（s.top-1）;
训练的是栈的基本操作，进一步掌握了栈的基本操作，基础知识要牢固，便于灵活的运用。
【2】试编写算法，实现链队列的下列操作算法：
（1）initlq（q）。
初始化操作，建立一个空队列q；
（2）emptylq（q）。
判定队列q是否为空；
（3）enterlq（q）。
进队列；
（4）deletelq（q）。
出队列。
这里练习的是队列的基本操作，按照队列的定义与基本的操作去编写就好。
要注意判断队列的空满。
typedefstructqnode{
qelemtypedata;
structqnode*next;
}qnode,*queueptr;
queueptrfront;
queueptrrear;
}linkqueue;
初始化操作，建立一个空队列q
voidinitlq（linkqueue&
q）
{q.front=q.rear=（queueptr）malloc（sizeof（qnode））;
if（!
q.front）exit（overflow）;
q.front->
next=null;
判定队列q是否为空
voidemptylq（linkqueueq）
if（q.front==q.rear）returnyes;
elseretunno;
进队列
voidenterlq（linkqueue&
q,qelemtypee）
p=（queueptr）malloc（sizeof（qnode））;
p）exit（overflow）;
data=e;
q.rear->
next=p;
q.rear=p;
出队列
voiddeletelq（linkqueue&
if（q.front==q.rear）returnerror;
p=q.front->
next=p->
if（q.rear==p）q.rear=q.front;
free（p）;
【实验三】串的基本操作
1、掌握串的基本操作。
2、掌握串函数的基本使用方法。
3、加深对串的理解，逐步培养解决实际问题的编程能力。
假设以顺序存储结构存放字符串，试编写算法，实现下列基本操作（用C语言编写）：
（1）CreatString（&
S）。
输入并建立顺序存储的字符串S；
（2）SubString（&
T,S,pos,len）。
求S串从pos开始长度为len的子串放入T串；
（3）StrInsert（&
S,i,T）。
在串S的第i个字符前插入T；
（4）StrDelele（&
T,S,i,len）。
从串S中删除第i个字符起长度为len的子串送到T中。
char*ch;
intlength;
}hstring;
输入并建立顺序存储的字符串s
voidcreatstring（hstring&
{if（s.ch）free（s.ch）;
输入你要构造的串的元素个数：
i）;
（s.ch=（char*）malloc（i*sizeof（char））））exit（overflow）;
请依次输入元素：
intj;
for（j=0;
j<
i;
j++）
s.ch[j]）;
求s串从pos开始长度为len的子串放入t串
voidsubstring（hstring&
t,hstrings,intpos,intlen）
if（pos<
1）||pos>
s.length||len<
0||len>
s.length-pos+1）
returnerror;
if（t.ch）free（t.ch）;
len）{t.ch=null;
t.length=0）;
else{
t.ch=（char*）malloc（len*sizeof（char））;
for（i=0；
len-1;
{t.ch[i]=s.ch[pos+i-1];
t.length=len;
在串s的第i个字符前插入串t
voidstrinsert（hstring&
s,inti,hstringt）
if（i<
1||i>
s.length+1）returnerror;
if（t.length）{
（s.ch=（char*）realloc（s.ch,（s.length+t.length）*sizeof（char））））exit（overflow）;
for（j=s.length-1;
i-1;
--j）
{s.ch[j+t.length]=s.ch[j];
t.length-1;
{s.ch[i-1+j]=t.ch[j];
s.length+=t.length;
从串s中删除第i个字符起长度为len的子串送到t中
VoidStrDelete（hstring&
t,hstrings,inti,intlen）
{/*初始条件:
串S存在,1≤i≤strLength（s）-len+1*/
intj;
if（i<
升级会员 