数据结构试验报告 1
- 格式：wps
- 大小：56.00 KB
- 文档页数：9
数据结构实验报告
姓名：
学号：
专业班级：
线性表基本操作
一、实验目的：
1． 熟悉C/C++语言的上机环境，掌握C C++语言的基本结构。
2． 定义单链表的结点类型。
3． 熟悉对单链表的一些基本操作和具体的函数定义。
4． 通过单链表的定义掌握线性表的链式存储结构的特点。
5． 熟悉对单链表的一些其它操作 。
二、实验内容
实验单链表的建立、查找、插入、删除、排序和合并功能。
三、实验部骤：
（1）构写程序的大体框架；
（2）具体编写每个操作的程序；
（3）程序的检查；
（4）程序的调试；
四、调试问题：
该程序在DEV-C++中编写，其中，在编写删除函数时无法编译成
功；在合并函数测试时，后面的链表是从尾部连接的，这2个问题未
解决。
五、实验结果：
六、程序：
#include
#include
#define null 0
typedef struct node{/*构造结构体*/
int data;/*声明变量*/
struct node *next;
}slnode;
void travel(slnode *p)/*遍历函数*/
{
slnode *s;/*声明一个构造体指针变量*/
s=p->next;/*S指向头结点的下一个*/
while(s!=null)/*当S非空时*/
{
putchar(s->data);/*输出指针S所指结点的变量
*/
s=s->next;/*Ｓ指向下一个结点*/
}
putchar('\n');
}
slnode append(slnode *p,int x)/*结尾附加结点函数*/
{
slnode *s;
s=(slnode *)malloc(sizeof(slnode));/*为Ｓ开辟内存空间*/
s->next=p->next;/*ｓ和ｐ都指向头结点的下一个结点*/
s->data=x;/*将ｘ数据赋给Ｓ*/
p->next=s;/*Ｓ作为最后一个结点*/
}
void *initiate(slnode **h)/*建立单链表*/
{
*h=(slnode *)malloc(sizeof(slnode));/*开辟内存空间*/
(*h)->next=null;/*该单链表为空*/
}
slnode *search(slnode *p,int x)/*查找函数*/
{
slnode *s;
s=p->next;/*S指向单链表头结点的下一个结点*/
while(s!=null)/*当S非空时*/
{
if(s->data==x)/*如果要查找的数据等于S所
指向的结点中的数据*/
return(s);/*返回S*/
s=s->next;/*否则S指向其下一个结点*/
}
return(null);/*否则查找失败*/
}
int insert(slnode *p,int x,int y)/*插入函数，在已知结点x后插入新结点
y*/
{
slnode *m,*n;
n=(slnode*)malloc(sizeof(slnode));/*建立新结点n*/
n->data=y;/*该结点的数据为所要查找的Y*/
m=search(p,x);/*查找*/
if(m!=null)/*当找到所要插入的位置时*/
{
n->next=m->next;/*将新结点插入到已知结点后*/
m->next=n;
return(0);
}
else /*若未找到所要插入的位置*/
{
printf("%c not found!\n",x);/*插入失败*/
return(-1);
}
}
int delete(slnode *p,int x)/*删除函数*/
{
slnode *s,*q;
q=p;/*q指向头结点*/
s=p->next;/*s指向头结点的下一个结点*/
while(s!=null)/*s非空时*/
if(s->data!=x)/*若s所指向的结点的数据不是所要删除的数据，s
指向其下一个结点*/
{
q=s;
s=s->next;
}
else /*若查找到所要删除的结点*/
{q->next=s->next;/*删除该结点*/
free(s);/*释放s*/
return(0);
}
printf("%c:not found!\n",x);/*删除失败*/
return(-1);
}
slnode *sort(slnode *p)/*排序函数*/
{
slnode *s,*q;
q=p;
s=p->next;
while(s!=null)
{
if(s->data
关系，交换位置*/
{
p->next=s->next;
s->next=q;
}
return(q);/*返回排序后的链表*/
}
}
void unit(slnode *p,slnode *q)/*合并函数*/
{
slnode *s,*m;
s=p;
m=s;
while(s->next!=null)/*找到单链表p的最后一个结点，然后将链
表q的头结点接到p的最后面*/
s=s->next;
s->next=q;
travel(m);
}
main()
{
slnode *p,*q;
int i,ch1,x,y,z,j;
initiate(&p);/*建立单链表p*/
for(i=1;i<4;i++)/*为p添加多个结点*/
{
printf("ch%d=",i);
x=getchar();
getchar();
append(p,x);
}
printf("请输入要查找的数\n");
y=getchar();/*输入一个数*/
getchar();
search(p,y);/*查找*/
printf("请输入要插入的数及要插入的位置\n");
z=getchar();
getchar();
j=getchar();
getchar();
insert(p,ch1,z);/*插入*/
printf("排序后：\n");
travel(p);
delete(p,ch2);/*删除*/
travel(p);
sort(p);/*排序*/
initiate(&q);/*建立新链表*/
printf("输入新链表中的数据\n");
for(i=1;i<4;i++)
{
printf("lq%d=",i);
x=getchar();
getchar();
append(q,x);
}
unit(p,q);/*合并*/
getchar();
}
