实验一--线性表的实验.doc

实验一 线性表的实验

实验课程名： C语言程序设计
专业班级： 学号： 姓名
实验时间： 实验地点： 指导教师：

一、实验目的及要求
1、掌握用Visual C++6.0调试顺序表的基本方法。
2、掌握顺序表的基本操作，插入、删除、查找、以及有序顺序表的合并等算法的实现。
3、掌握用Visual C++6.0上机调试单链表的基本方法。
4、掌握单链表的插入、删除、查找、求表长以及有序单链表的合并算法的实现。
5、进一步掌握循环单链表的插入、删除、查找算法的实现。
二、实验内容
１、任务一：用顺序表实现通讯录管理
（2） 构建如表1所示的顺序表并输出检验，实现表1。
（3） 增加插入记录的功能并输出检验，实现表2。
（4） 增加按学号查找的功能并运行验证。
（5） 增加删除记录的功能并运行验证。
表1
学号
姓名
性别
手机号码
QQ号
2013001
张珊
女
13800001919
34578
表2
2013002
李思
女
13910121978
8796532
2013003
陈琪
女
13789450012
3789123
2013004
王强
男
13634567856
6543783
2013005
赵括
男
13534408976
5679
2013006
刘刚
男
13386543211
98315
注意：用结构化程序设计的方法实现即（其中的）把单一功能设计成一个独立的函数。如构建顺序表设计成一个函数，同样插入、查找、删除、输出也设计成独立的函数。解答：
（1）源代码：#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MaxSize 10
typedef struct{
char xuehao[14];//学号
char name[20]; //姓名
int sex; //性别
char tel[14]; //联系电话
char qq[12]; //QQ号
}ElemType;
typedef struct{
ElemType *list;
int length;
int size;
}SeqList;
void InitSeqList( SeqList *L)
{
char flag;
int i,n;
ElemType *p;
L->list=( ElemType * )malloc(MaxSize*sizeof( ElemType ));
L->length=0 ;
L->size=MaxSize ;
printf("是否输入初始数据？（Y/N）");
scanf("%c",&flag);
if(flag=='N'||flag=='n') return;
printf("请输入初始化数据的个数:");
scanf("%d",&n);
if(n>L->size) {printf("数据太多，不足以存储！");return;}
p=L->list;
L->length=n;
for(i=0;i<n;i++)
{
printf("请输入第%d个数据(学号 姓名 性别（0或1） 联系电话 QQ号)：\n",i+1);
scanf("%s%s%d%s%s",p->xuehao,p->name , &p->sex , p->tel ,p->qq );
p++;
}
return;
}

void PrintSeqList(SeqList *L)
{
int i;
printf("学号 姓名 性别 联系电话 QQ号\n");
for( i=0 ; i<L->length ; i++ )
{

printf("%s\t%s\t",L->list[i].xuehao,L->list[i].name );
if(L->list[i].sex)
printf("男");
else printf("女");
printf("\t%s\t%6s\n", L->list[i].tel ,L->list[i].qq );

}
}
/*int main()
{
SeqList L;
InitSeqList( &L );
PrintSeqList( &L );
return 0;
}*/ int InsertSeqList(SeqList *L,int i,ElemType *e)
{
ElemType *q,*p;
if(L->length+1>L->size ) {printf("表满，失败！");return 0;}
if(i<1||i>L->length+1) {printf("插入位置错误，失败！");return 0;}
q=&(L->list[i-1]);
for(p=&(L->list[L->length-1]);p>=q;p--)
*(p+1)=*p ;
*(p+1)=*e;
L->length++;

return 1;

}
/*int main()
{
ElemType e;
SeqList L;

InitSeqList(&L);
PrintSeqList(&L);
printf("请输入要插入的数据(学号 姓名 性别（0或1） 联系电话 QQ号)：\n");
scanf("%s%s%d%s%s",e.xuehao,e.name , &e.sex , e.tel ,e.qq );
printf("学号 姓名 性别 联系电话 QQ号\n");
printf("%s\t%s\t",e.xuehao,e.name );
if(e.sex)
printf("男");
else printf("女");
printf("\t%s\t%6s\n", e.tel ,e.qq );
InsertSeqList(&L,2,&e);
PrintSeqList(&L);
return 0;
}*/
int LocateList(SeqList *L,char *x)
{
int i=0;

while(i<L->length &&strcmp(L->list[i].xuehao ,x ))

++i;

if(i<L->length )

{

printf("\n学号 姓名 性别 联系电话 QQ号\n");

printf("%s\t%s\t",L->list[i].xuehao,L->list[i].name);

if(L->list[i].sex) printf(" 男 "); else printf(" 女 ");

printf("%s\t%6s\n",L->list[i].tel,L->list[i].qq);

return i+1;

}

return 0;
}
/*int main()
{

SeqList L;
InitSeqList(&L);
PrintSeqList(&L);
printf("输出查询结果：\n");
LocateList(&L,"02");
return 0;
}*/
int DeleteList(SeqList *L,int i)
{
int j;
ElemType *q,*p;
if(L->length ==0) {printf("表空，删除失败！\n");return 0;}

if(i<1||i>L->length) {printf("删除位置错，失败！\n");return 0;}
p=&(L->list[i-1]);
for(q=&(L->list[L->length-1]);q<=p;p--)
*(p-1)=*p;
L->length --;

return 1;
}
int main()
{
int i;
SeqList L;
InitSeqList(&L);
PrintSeqList(&L);
printf("请输入删除位数:");
scanf("%d",&i);
DeleteList(&L,i);
PrintSeqList(&L);
return 0;
}
（2）运行结果：

2. 插入功能

3. 查询功能

4. 删除功能

（3） 运行结果分析：
本次作业利用C语言实现顺序表初始化、插入、删除、查找、的基本操作。

任务二：用链表实现通讯录管理
1、 构建通讯录的链表并输出检验，实现表1。
2、增加插入记录的功能并输出检验，实现表2。
3、增加按学号查找的功能并运行验证。
4、增加删除记录的功能并运行验证。

解答：
（1）源代码：#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct{
char xuehao[14];//学号
char name[20]; //姓名
int sex; //性别
char tel[14]; //联系电话
char qq[12]; //QQ号
}DataType;
typedef struct LNode{
DataType data;
struct LNode *next;
}LNode,*LinkList;
LinkList CreatList()//头插法建立链表
{
LinkList head;
head = (LinkList)malloc(sizeof(LNode));
LinkList p , s ;
s = head ;
char flag='y';
head->next =NULL;
while((flag=='Y')||(flag=='y'))
{
p=(LinkList)malloc(sizeof(LNode));
if(!p) exit(-1);
printf("请输入数据(学号 姓名 性别（0或1） 联系电话 QQ号)：\n");
scanf("%s%s%d%s%s",p->data.xuehao,p->data.name,&p->data.sex,p->data.tel,p->data.qq);
p->next = s->next ;
s->next = p ;
s = p ;
getchar();
printf("继续输入吗？（y/n）:");
scanf("%c",&flag);
printf("\n");
}
return head;
}

void PrintList(LinkList head)
{
LNode *p;
p=head->next;
printf("学号 姓名 性别 联系电话 QQ号\n");
printf("------------------------------------------------------------\n");
while(p!=NULL)
{
printf("%-14s%-14s",p->data.xuehao,p->data.name);
if(p->data.sex) printf("男 "); else printf("女 ");
printf("%-14s%-10s\n",p->data .tel,p->data.qq);
printf("----------------------------------------------------------\n");
p=p->next ;
}
}

/*int main()
{
LinkList head;
head=CreatList();
PrintList(head);
return 0;
}*/
void InsertLinkList(LinkList head)
//考虑实际情形，在教材的基础作了一个变化，将插入位置和插入的数据信息改为输入，不作为形参传入信息。
{
LinkList p,s;
int i;
int j;
p=head->next;
j=1;
printf("请输入要插入结点位置:");
scanf("%d",&i);
while(p&&j<i-1)
{
p=p->next ;
j++;
}
if(!p||j<i-1) {printf("错误！\n");return;}

s=(LinkList)malloc(sizeof(LNode));
printf("请输入要插入的数据：\n");
printf("学号 姓名 性别（0或1） 联系电话 QQ号\n");
scanf("%s%s%d%s%s",s->data.xuehao,s->data.name,&s->data.sex,s->data.tel,s->data.qq);
s->next =p->next ;
p->next =s;
return;
}
void GetElemList(LinkList head,DataType *e)//读取位置改为在函数内输入
{
LinkList p;
int i,j=1;
printf("请输入要读取第几个元素：");
scanf("%d",&i);
p=head->next;
while(p&&j<i)
{
p=p->next ;j++;
}
if(!p||j>i) {printf("没有找到！\n");return;}

printf("学号 姓名 性别（0或1） 联系电话 QQ号\n");
printf("%-14s%-14s",p->data.xuehao,p->data.name);
if(p->data.sex) printf(" 男 "); else printf(" 女 ");
printf("%-14s%-10s\n",p->data .tel,p->data.qq);
e=&(p->data);
}
int DeleteElemLinkList(LinkList head,DataType *e)
{
LinkList p,q;
int i;
int j;

p=head;
j=1;

printf("请输入要删除结点位置:");
scanf("%d",&i);
while(p&&(j<i))
{
p=p->next ;
j++;
}
if(!p||j<i) {printf("错误！\n");return 0;}
q=p->next ;e=&q->data ;p->next =q->next ;
free(q);
return 1;
}

int main()
{
LinkList head;
DataType e;
int choice;

do
{
printf(" 通讯录管理系统\n");
printf("======================================\n");
printf(" 0:退出\n");
printf(" 1:建立通讯录\n");
printf(" 2:插入\n");
printf(" 3:删除\n");
printf(" 4:查询\n");
printf(" 5:输出\n");
printf("======================================\n");
printf("请选择0-5\n");
scanf("%d",&choice);
while(choice<0||choice>5)
{
printf("输入错误，请重新输入:");
scanf("%d",&choice);
}
switch(choice)
{
case 0:exit(1);
case 1:head=CreatList();break;
case 2:InsertLinkList(head);break;
case 3:DeleteElemLinkList(head,&e);break;
case 4:GetElemList(head,&e);break;
case 5:PrintList(head);break;
}

}while(choice);
return 0;
}
（2） 运行结果：

（3） 运行结果分析：
利用链表构建通讯录，然后通过各个节点之间的联系完成构建、插入、删除、查询的功能。

三、实验小结
本次实验我知道了用C语言顺序表的基本方法。掌握了顺序表的基本操作，插入、删除、查找、以及有序顺序表的合并等算法的实现。了解用Visual C++6.0上机调试单链表的基本方法。了解了单链表的插入、删除、查找、求表长以及有序单链表的合并算法的实现。

16