《数据结构》实验报告一 系别:嵌入式系统工程系
班级:嵌入式 11003 班
学号:11160400314
姓名:xxx
日期:2012 年 4 月 9 日
指导教师 XX
一、上机实验的问题和要求:
顺序表的查找、插入与删除。设计算法,实现线性结构上的顺序表的产生以及元素的查找、插入与删除。具体实现要求:
1. 从键盘输入 10 个整数,产生顺序表,并输入结点值。
2. 从键盘输入 1 个整数,在顺序表中查找该结点的位置。若找到,输出结点的位置;若找不到,则显示“找不到”。
3. 从键盘输入 2 个整数,一个表示欲插入的位置 i,另一个表示欲插入的数值 x,将 x 插入在对应位置上,输出顺序表所有结点值,观察输出结果。
4. 从键盘输入 1 个整数,表示欲删除结点的位置,输出顺序表所有结点值,观察输出结果。
二、程序设计的基本思想,原理和算法描述:
(包括程序的结构,数据结构,输入/输出设计,符号名说明等)
创建一个顺序表,实现对顺序表的插入,查找,删除等功能。
三、源程序及注释:
#include <stdio.h> /*顺序表的定义:*/ #define ListSize 100
/*表空间大小可根据实际需要而定,这里假设为100*/ typedef int DataType;
/*DataType可以是任何相应的数据类型如int, float或char*/ typedef struct { DataType data[ListSize]; /*向量data用于存放表结点*/
int length;
/*当前的表长度*/ }SeqList;
/*子函数的声明*/
void CreateList(SeqList * L,int n);
/*创建顺序表函数*/ int LocateList(SeqList L,DataType x);
/*查找顺序表*/ void InsertList(SeqList * L,DataType x,int i); /*在顺序表中插入结点x*/ void DeleteList(SeqList * L,int i);/*在顺序表中删除第i个结点*/ void PrintList(SeqList L,int n); /*打印顺序表中前n个结点*/
void main() {
SeqList L;
int n=10,x,i;
/*欲建立的顺序表长度*/
L.length=0;
/*调用创建线性表函数*/ printf(“create function:\n”);
CreateList(&L,n);
/*建立顺序表*/
PrintList(L,n);
/*打印顺序表*/
/*调用查找函数*/
printf(“search function:\n”);
printf("input the data you want to search:");
scanf("%d",&x);
i=LocateList(L,x);
/*顺序表查找*/
if (i==0)
printf("sorry,don"t find %d!\n\n",x);
else
printf("i have find the %d,it locate in %d!\n\n",x,i);
/*调用插入函数*/ printf(“Insert function:\n”);
printf("输入要插入的位置:(input the position:)");
scanf("%d",&i);
printf("输入要插入的元素:(input the data:)");
scanf("%d",&x);
InsertList(&L,x,i);
/*顺序表插入 */
PrintList(L,n);
/*打印顺序表 */
/*调用删除函数*/ printf(“delete function:\n”);
printf("输入要删除的位置:(input the position:)");
scanf("%d",&i);
DeleteList(&L,i);
/*顺序表删除 */
PrintList(L,n);
/*打印顺序表 */
}
/*顺序表的建立:*/ void CreateList(SeqList *L,int n) { int i;
for (i=0;i<n;i++)
{printf("\ninput the %d data:",i+1);
scanf("%d",&(*L).data[i]);
}
(*L).length=n; }
/*顺序表的查找:*/ int LocateList(SeqList L,DataType x) {
int i=0;
while (i<___=L.length-1______________ && ____L.data[i]_=!e______________)
++i;
if (i<L.length) return i+1;
else return 0; }
/*顺序表的插入:*/ void InsertList(SeqList *L,DataType x,int i) {/*将新结点x插入L所指的顺序表的第i个结点的位置上 */
int j;
if (i<1 || i>__L.length____________________)
{
printf("插入位置非法");
exit(0);
}
if ((*L).length>=___MaxSize_______________)
{
printf("表空间溢出,退出运行");
exit(0);
}
for (j=(*L).length-1;j>=i-1;j--)
____L.data[k+1]=L.data[k]_______________________________ ; /*顺序表元素从后向前依次后移*/
____L.data[i-1]=e_______________________________;
/*将x插入第i个结点位置*/
_____L.length++___________________________;
/*表长自增1*/ }
/*顺序表的删除:*/ void DeleteList(SeqList *L,int i)
{/*从L所指的顺序表中删除第i个结点 */
int j;
if (i<1 || i>___L.length____________________________)
{
printf("删除位置非法");
exit(0);
}
for (j=i;j<=(*L).length-1;j++)
____L.data[k-1]=L.data[k]________________________________; /*顺序表自第i个结点开始,依次前移*/
______L.length--__________________________;
/*表长自减1*/ }
/*顺序表的打印:*/ void PrintList(SeqList L,int n) { int i;
printf(“the sequal list data is:”);
for (i=0;i<n;i++)
printf("%d
",L.data[i]);
printf("\n\n"); }
调试后的代码:
#include<stdio.h>
#define MaxSize 100
typedef int Datatype;
typedef struct
{ {
Datatype data[MaxSize];
int length;
}seqlist;
void GreatList(seqlist*L,int n);
int GetList(seqlist L, Datatype x);
int IntList(seqlist *L,Datatype x,int i);
int DelList(seqlist L,int i,Datatype *x);
void PrintList(seqlist L,int n);
void main()
{ {
seqlist L;
int n=10,x,i;
L.length=0;
printf("great function:\ \ n");
GreatList(&L,n);
PrintList(L,n);
printf("get function:\ \ n");
printf("please inp ut your want to search\ \ n");
scanf("%d",&x);
i=GetList(L,x);
if(i==0)
{ {
printf("\ \ nsorry,don"t find %d\ \ n",x);
} }
else
{ {
printf("\ \ nhave find the %d,it located in %d\ \ n",x,i);
} }
printf("\ \ nIns function:\ \ n");
printf("\ \ nplease
input the position: \ \ n");
scanf("%d",&i);
printf("\ \ nplease input the data:\ \ n");
scanf("%d",&x);
IntList(&L,i,x);
PrintList(L,n);
printf("\ \ ndel function:\ \ n");
printf("\ \ nplease input you want to delete position:\ \ n");
scanf("%d",&i);
pr intf("\ \ nplease input you want delete number:
");
scanf("%d",&x);
DelList(L,i,&x);
PrintList(L,n);
//getch();
} }
void GreatList(seqlist *L,int n)
{ {
int i;
for(i=0;i<n;i++)
{ {
printf("\ \ nplease input the %d data \ \ n",i+1);
scanf("%d",&(*L).data[i]);
} }
(*L).length=n;
} }
int GetList(seqlist L,Datatype x)
{ {
int i;
i=0;
while((i<=L.length- - 1)&&(L.data[i]!=x))
i++;
if(i<L.length)
return(i+1);
else
return(- - 1);
} }
int IntList(seqlist *L,Datatype x,int i)
{ {
int k;
if((i<1)||(i>L- - >length))
{ {
printf("\ \ nThe position is wrong\ \ n");
return(0);
}
if(L- - >length>=MaxSize)
{ {
printf("\ \ nempty\ \ n");
return(0);
} }
for(k=L- - >length- - 1;k>=i- - 1;i++)
{ {
L L- - >data[k+1]=L- - >data[k];
L L- - >data[i- - 1]=x;
L L- - >length++;
} }
return(1);
} }
int DelList(seqlist L,int i,Datatype *x)
{ {
int k;
if((i<1)||(i>L.length))
{ {
printf("\ \ nThe position is wrong\ \ n"); ;
return(0);
} }
*x=L.data[i- - 1];
for(k=i;i<=L.length;k++)
{ {
L.data[k- - 1]=L.data[k];
L.length --; ;
}
return(1);
} }
void PrintList(seqlist L,int n)
{ {
int i;
printf("\ \ nThe sequal List Data is:
\ \ n");
for(i=0;i<n;i++)
printf("%d ",L.data[i]);
printf("\ \ n");
} }
四、运行输出结果:
五、调试和运行程序过程中产生的问题及采取的措施:
开始只是一些小的问题,如丢了分号、括号,单词写错了,前后不一致等等。
最主要的问题就是函数检查没错误,但是运行中出现错误。第一个就是插入的函数能打印出来,但是出入不进去数;第二就是删除不了数。
(如下图)
六、:
对算法的程序的讨论、分析,改进设想,其它经验教训:
本次实验主要考查的的是顺序表的应用及编写,而其他的很多功能都是原来练习过的,相对来说比较容易。但是完成本次实验收获还是很多的,不仅仅实在新知识上的加深,进一步了解顺序表。
七、对实验方式、组织、设备、题目的意见和建议:
希望老师以后可以给我们多些自己动手实践的机会,可以在课堂上多让我们动手去上机操作,老师带领我们完成主要部分,或给一
些提示指导。