实验一 顺序表、单链表基本操作的实现
l 实验目的
1、顺序表
(1)掌握线性表的基本运算。
(2)掌握顺序存储的概念，学会对顺序存储数据结构进行操作。
(3)加深对顺序存储数据结构的理解，逐步培养解决实际问题的编程能力。
l 实验内容
1、顺序表
1、编写线性表基本操作函数：
(1)InitList(LIST *L,int ms)初始化线性表；
(2)InsertList(LIST *L,int item,int rc)向线性表的指定位置插入元素；
(3)DeleteList1(LIST *L,int item)删除指定元素值的线性表记录；
(4)DeleteList2(LIST *L,int rc)删除指定位置的线性表记录；
(5)FindList(LIST *L,int item)查找线性表的元素；
(6)OutputList(LIST *L)输出线性表元素；
2、调用上述函数实现下列操作：
(1)初始化线性表；
(2)调用插入函数建立一个线性表；
(3)在线性表中寻找指定的元素；
(4)在线性表中删除指定值的元素；
(5)在线性表中删除指定位置的元素；
(6)遍历并输出线性表；
l 实验结果
1、顺序表
(1)流程图
(2)程序运行主要结果截图
(3)程序源代码
#include#include#include
struct LinearList/*定义线性表结构*/{int *list; /*存线性表元素*/
int size; /*存线性表长度*/
int Maxsize; /*存list数组元素的个数*/};
typedefstructLinearList LIST;void InitList(LIST *L,int ms)/*初始化线性表*/{if((L->list=(int*)malloc(ms*sizeof(int)))==NULL)
{
printf("内存申请错误");
exit(1);
}
L->size=0;
L->Maxsize=ms;
}int InsertList(LIST *L,int item,int rc)/*item记录值；rc插入位置*/{inti;if(L->size==L->Maxsize)/*线性表已满*/
return -1;if(rc<0)
rc=0;if(rc>L->size)
rc=L->size;for(i=L->size-1;i>=rc;i--)/*将线性表元素后移*/L->list[i+=1]=L->list[i];
L->list[rc]=item;
L->size++;return 0;
}void OutputList(LIST *L)/*输出线性表元素*/{inti;for(i=0;isize;i++)
printf("%d",L->list[i]);
printf("\n");
}int FindList(LIST *L,int item)/*查找线性元素，返回值>=0为元素的位置，返回-1为没找到*/{inti;for(i=0;isize;i++)if(item==L->list[i])returni;return -1;
}int DeleteList1(LIST *L,int item)/*删除 指定元素值得线性表记录，返回值为>=0为删除成功*/{inti,n;for(i=0;isize;i++)if(item==L->list[i])break;if(isize)
{for(n=i;nsize-1;n++)
L->list[n]=L->list[n+1];
L->size--;returni;
}return -1;
}int DeleteList2(LIST *L,int rc)/*删除指定位置的线性表记录*/{inti,n;if(rc<0||rc>=L->size)return -1;for(n=rc;nsize-1;n++)
L->list[n]=L->list[n+1];
L->size--;return 0;
}intmain()
{
LIST LL;inti,r;
printf("list addr=%p\tsize=%d\tMaxsize=%d\n",,,);
InitList(&LL,10);
printf("list addr=%p\tsize=%d\tMaxsize=%d\n",,,);while(1)
{
printf("请输入元素值，输入0结束插入操作:");
fflush(stdin);/*清空标准输入缓冲区*/scanf("%d",&i);if(i==0)break;
printf("请输入插入位置：");
scanf("%d",&r);
InsertList(&LL,i,r-1);
printf("线性表为：");
OutputList(&LL);
}while(1)
{
printf("请输入查找元素值，输入0结束查找操作：");
fflush(stdin);/*清空标准输入缓冲区*/scanf("%d",&i);if(i==0)break;
r=FindList(&LL,i);if(r<0)
printf("没有找到\n");elseprintf("有符合条件的元素，位置为：%d\n",r+1);
}while(1)
{
printf("请输入删除元素值，输入0结束查找操作：");
fflush(stdin);/*清楚标准缓存区*/scanf("%d",&i);if(i==0)break;
r=DeleteList1(&LL,i);if(i<0)
printf("没有找到\n");else{
printf("有符合条件的元素，位置为：%d\n线性表为：",r+1);
OutputList(&LL);
}
}while(1)
{
printf("请输入删除元素位置，输入0结束查找操作：");
fflush(stdin);/*清楚标准输入缓冲区*/scanf("%d",&r);if(r==0)break;
i=DeleteList2(&LL,r-1);if(i<0)
printf("位置越界\n");else{
printf("线性表为：");
OutputList(&LL);
}
}
}
链表基本操作
l 实验目的
2、链表
(1)掌握链表的概念，学会对链表进行操作。
(2)加深对链式存储数据结构的理解，逐步培养解决实际问题的编程能力。
l 实验内容
1、编写链表基本操作函数：
(1)InitList(LIST *L,int ms)初始化链表；
(2)InsertList1(LIST *L,int item,int rc)向链表的指定位置插入元素；
(3)InsertList2(LIST *L,int item,int rc)向有序链表的指定位置插入元素；
(4)DeleteList(LIST *L,int item)删除指定元素值的链表记录；
(5)FindList(LIST *L,int item)查找链表中的元素；
(6)OutputList(LIST *L)输出链表中的元素；
2、调用上述函数实现下列操作：
(1)初始化链表；
(2)调用插入函数建立一个链表；
(3)在链表中寻找指定的元素；
(4)在链表中删除指定值的元素；
(5)遍历并输出链表；
l 实验结果
(1)、流程图：
(2)程序运行主要结果截图：
(3)程序源代码：
#include#includetypedefstructlist
{intdata;struct list *next;
}LIST;void initlist(LIST **p)
{*p=NULL;
}void insertlist1(LIST **p,int item,intrc)
{inti;
LIST*u,*q,*r;
u=(LIST*)malloc(sizeof(LIST));
u->data=item;for(i=1,r=*p;i)
{
q=r;
r=r->next;
}if(r==*p)*p=u;elseq->next=u;
u->next=r;
}void insertlist2(LIST **p,intitem)
{
LIST*u,*q,*r;
u=(LIST*)malloc(sizeof(LIST));
u->data=item;for(r=*p;r!=NULL&&r->datanext)if(r==*p)*p=u;elseq->next=u;
u->next=r;
}int deletelist(LIST **p,intitem)
{
LIST*q,*r;
q=*p;r=q;if(q==NULL)return 1;if(q->data==item)
{*p=q->next;free(r);return 0;
}for( ;q->data!=item&&q->next!=NULL;r=q,q=q->next)if(q->data==item)
{
r->next=q->next;free(q);return 0;
}return 1;
}int findlist(LIST *p,intitem)
{inti;for(i=1;p->data!=item&&p!=NULL;p=p->next,i++)return(p==NULL)?-1:i;
}void outputlist(LIST *p)
{while(p!=NULL)
{
printf("%4d",p->data);
p=p->next;
}
printf("\n");
}void freelist(LIST **p)
{
LIST*q,*r;for(q=*p;q!=NULL;)
{
r=q;
q=q->next;free(r);
}*p=NULL;
}intmain()
{
LIST*p;intop,i,rc;
initlist(&p);while(1)
{
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~6 进行操作：");
fflush(stdin);
scanf("%d",&op);switch(op)
{case 0:return -1;case 1:
printf("请输入新增结点的键值和位置：");
scanf("%d%d",&i,&rc);
insertlist1(&p,i,rc);break;case 2:
printf("请输入新增结点的键值：");
scanf("%d",&i);
insertlist2(&p,i);break;case 3:
printf("请输入要查找结点的键值：");
scanf("%d",&i);
rc=findlist(p,i);if(rc>0)
printf("位置位 %d\n",rc);elseprintf("没有找到\n");break;case 4:
printf("请输入要删除的结点的键值：");
scanf("%d",&i);
rc=deletelist(&p,i);if(rc==0)
printf("删除成功！\n",rc);elseprintf("没找到！\n");break;case 5:
printf("\n 链表内容为：\n");
outputlist(p);break;case 6:
freelist(&p);break;
}
}
}