C语言数据结构线性表的基本操作实验报告.doc

实验一 线性表的基本操作

一、实验目的与基本要求
1．掌握数据结构中的一些基本概念。数据、数据项、数据元素、数据类型和数据结构，以与它们之间的关系。
2． 了解数据的逻辑结构和数据的存储结构之间的区别与联系；数据的运算与数据的逻辑结构的关系。
3． 掌握顺序表和链表的基本操作：插入、删除、查找以与表的合并等运算。
4． 掌握运用C语言上机调试线性表的基本方法。
二、实验条件
1． 硬件：一台微机
2． 软件：操作系统和C语言系统
三、实验方法
确定存储结构后，上机调试实现线性表的基本运算。
四、实验容
1． 建立顺序表，基本操作包括：初始化，建立一个顺序存储的链表，输出顺序表，判断是否为空，取表中第i个元素，定位函数（返回第一个与x相等的元素位置），插入，删除。
2． 建立单链表，基本操作包括：初始化，建立一个链式存储的链表，输出顺序表，判断是否为空，取表中第i个元素，定位函数（返回第一个与x相等的元素位置），插入，删除。
3． 假设有两个按数据元素值非递减有序排列的线性表A和B，均以顺序表作为存储结构。编写算法将A表和B表归并成一个按元素值非递增有序（允许值一样）排列的线性表C。（可以利用将B中元素插入A中，或新建C表）
4． 假设有两个按数据元素值非递减有序排列的线性表A和B，均以单链表作为存储结构。编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许值一样）排列的线性表C。
五、附源程序与算法程序流程图
1.源程序
（1）源程序(实验要求1和3)
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef struct arr
{
int * elem;
int length;
int listsize;
}Sqlist;

void menu(); //菜单
void InitList(Sqlist *p); // 创建线性表
void ShowList(Sqlist *p); // 输出顺序线性表
void ListDelete(Sqlist *p,int i,int &e); // 在顺序线性表中删除第i个元素，并用e返回其值
void ListInsert(Sqlist *p); // 在顺序线性表中第i个元素前插入新元素e
void ListEmpty(Sqlist *p); // 判断L是否为空表
void GetList(Sqlist *p,int i,int &e); // 用e返回L中第i个数据元素的值
void ListInsert(Sqlist *p,int i,int e);
bool compare(int a,int b);
void LocateElem(Sqlist *L,int e); // 在顺序线性表L中查找第1个值与e满足compare()d元素的位序
void MergeList_L(Sqlist *La,Sqlist *Lb); // 归并

void main()
{
Sqlist La;
Sqlist Lb;
int n,m,x;
menu();
scanf("%d",&n);
while(n)
{
switch(n)
{
case 0: ; break;
case 1:
InitList(&La);break;
case 2:
ListEmpty(&La);break;
case 3:
printf("请输入插入的位序:\n");
scanf("%d",&m);
printf("请出入要插入的数:\n");
scanf("%d",&x);
ListInsert(&La,m,x);break;
case 4:
printf("请输入删除元素的位序:\n");
scanf("%d",&m);
ListDelete(&La,m,x);
printf("删除的元素为:%d\n",x);break;
case 5:
printf("请输入要找的与线性表中相等的数:\n");
scanf("%d",&m);
LocateElem(&La,m);break;
case 6:
printf("请输入查找的位序:\n");
scanf("%d",&m);
GetList(&La,m,x);
printf("La中第%d个元素的值为%d\n",m,x);break;
case 7:
ShowList(&La);break;
case 8:
InitList(&Lb);break;
case 9:
MergeList_L(&La,&Lb);
printf("归并成功!");break;
}
menu();
scanf("%d",&n);
}

}
/*菜单*/
void menu()
{
printf("********************\n\n");

printf(" 0.退出\n\n");

printf(" 1.创建线性表La\n\n");

printf(" 2.判断La是否为空表\n\n");

printf(" 3.插入元素(La)\n\n");

printf(" 4.删除元素(La)\n\n");

printf(" 5.定位元素(La)\n\n");

printf(" 6.取元素(La)\n\n");

printf(" 7.输出线性表\n\n");

printf(" 8.创建线性表Lb\n\n");

printf(" 9.归并为一个线性表La\n\n");

printf("********************\n\n");
}
/*创建顺序线性表L*/
void InitList(Sqlist *L)
{
int n;
int i=0;
L->elem=(int *)malloc(LIST_INIT_SIZE*sizeof(int));
if(NULL==L->elem)
printf("储存分配失败!\n");
else
{
L->length=0;
L->listsize=LIST_INIT_SIZE;
printf("输入顺序表a:\n");
scanf("%d",&n);
while(n)
{
L->elem[i]=n;
i++;
L->length++;
L->listsize=L->listsize-4;
scanf("%d",&n);
}
}
}
/*输出顺序线性表*/
void ShowList(Sqlist *p)
{
int i;
if(0==p->length)
printf("数组为空!\n");
else
for(i=0;i<p->length;i++)
printf("%d ",p->elem[i]);
printf("\n");
}
/*判断L是否为空表*/
void ListEmpty(Sqlist *p)
{
if(0==p->length)
printf("L是空表!\n");
else
printf("L不是空表!\n");
}
/*在顺序线性表中第i个元素前插入新元素e */
void ListInsert(Sqlist *p,int i,int e)
{
int *newbase;
int *q1;
int *q2;
while(i<1||i>p->length+1)
{
printf("您输入的i超出围!\n请重新输入要插入的位置\n:");
scanf("%d",&i);
}
if(p->length>=p->listsize)
{
newbase=(int *)realloc(p->elem,(p->listsize+LISTINCREMENT)*sizeof(int));
if(!newbase)
exit(0);
else
{
p->elem=newbase;
p->listsize+=LISTINCREMENT;
}
}
q1=&(p->elem[i-1]);
for(q2=&(p->elem[p->length-1]);q2>=q1;--q2)
*(q2+1)=*q2;
*q1=e;
++p->length;

}
/*/在顺序线性表中删除第i个元素，并用e返回其值*/
void ListDelete(Sqlist *p,int i,int &e)
{
int *q1,*q2;
while(i<1||i>p->length)
{
printf("您输入的i超出围!请重新输入:");
scanf("%d",&i);
}
q1=&(p->elem[i-1]);
e=*q1;
q2=p->elem+p->length-1;
for(++q1;q1<=q2;++q1)
*(q1-1)=*q1;
--p->length;
}
/*对比a与b相等*/
bool compare(int a,int b)
{
if(a==b)
return 1;
else
return 0;
}
/*在顺序线性表L中查找第1个值与e满足compare()d元素的位序*/
void LocateElem(Sqlist *L,int e)
{
int i=1;
int *p;
p=L->elem;
while(i<=L->length && !compare(*p++,e))
++i;
if(i<=L->length)
printf("第1个与e相等的元素的位序为%d\n",i);
else
printf("没有该元素!\n");
}
/*用e返回L中第i个数据元素的值*/
void GetList(Sqlist *p,int i,int &e)
{
Sqlist *p1;
p1=p;
e=p1->elem[i-1];
}
/* 已知顺序线性表La和Lb是元素按值非递减排列 */
/* 把La和Lb归并到La上,La的元素也是按值非递减 */
void MergeList_L(Sqlist *La,Sqlist *Lb)
{
int i=0,j=0,k,t;
int *newbase;
Sqlist *pa,*pb;
pa=La;
pb=Lb;
while(i<pa->length && j<pb->length)
{
if(pa->elem[i] >= pb->elem[j])
{
if(pa->listsize==0)
{
newbase=(int *)realloc(pa->elem,(pa->listsize+LISTINCREMENT)*sizeof(int));
if(!newbase)
exit(0);
}
for(k=pa->length-1; k>=i; k--)
pa->elem[k+1]=pa->elem[k];
pa->length++;
pa->elem[i]=pb->elem[j];
i++;
j++;
}
else
i++;
}
while(j<pb->length)
{
if( pa->listsize < pb->length-j )
{
newbase=(int *)realloc(pa->elem,(pa->listsize+LISTINCREMENT)*sizeof(int));
if(!newbase)
exit(0);
}
for(j;j<pb->length;j++,i++)
{
pa->elem[i]=pb->elem[j];
pa->length++;
}
}
for(i=0;i<pa->length/2;i++)
{
t=pa->elem[i];
pa->elem[i]=pa->elem[pa->length-i-1];
pa->elem[pa->length-i-1]=t;
}
}

（2）源程序(实验要求2和4)
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
typedef struct LNode
{
int data;
struct LNode *next;
}LNode, *LinkList;

void menu();
LinkList InitList();
void ShowList(LinkList L);
void ListDelete(LinkList L,int i,int &e);
void ListEmpty(LinkList L);
void GetList(LinkList L,int i,int &e);
void ListInsert(LinkList L,int i,int e);
bool compare(int a,int b);
void LocateElem(LinkList L,int e);
LinkList MergeList_L(LinkList La,LinkList Lb);

int total=0;
void main()
{
LinkList La;
LinkList Lb;
La=(LinkList)malloc(sizeof(struct LNode));
La->next=NULL;
Lb=(LinkList)malloc(sizeof(struct LNode));
Lb->next=NULL;
int n;
int m;
int x;
menu();
scanf("%d",&n);
while(n)
{
switch(n)
{
case 0: ; break;
case 1:
La->next=InitList();break;
case 2:
ListEmpty(La);break;
case 3:
printf("请输入要插入到第几个节点前:\n");
scanf("%d",&m);
printf("请输入插入的数据:\n");
scanf("%d",&x);
ListInsert(La,m,x);break;
case 4:
printf("请输入删除元素的位序:\n");
scanf("%d",&m);
ListDelete(La,m,x);
printf("删除的元素为:%d\n",x);break;
case 5:
printf("请输入要找的与线性表中相等的数:\n");
scanf("%d",&m);
LocateElem(La,m);break;
case 6:
printf("请输入查找的位序:\n");
scanf("%d",&m);
GetList(La,m,x);
printf("La中第%d个元素的值为%d\n",m,x);break;
case 7:
ShowList(La);break;
case 8:
Lb->next=InitList();break;
case 9:
La=MergeList_L(La,Lb);
printf("归并成功\n");break;
}
menu();
scanf("%d",&n);
}

}
void menu()
{
printf("********************\n\n");

printf(" 0.退出\n\n");

printf(" 1.创建线性表La\n\n");

printf(" 2.判断是否为空表\n\n");

printf(" 3.插入元素\n\n");

printf(" 4.删除元素\n\n");

printf(" 5.定位元素\n\n");

printf(" 6.取元素\n\n");

printf(" 7.输出线性表\n\n");

printf(" 8.创建线性表Lb\n\n");

printf(" 9.归并两线性表\n\n");

printf("********************\n\n");
}

// 创建链式线性表L
LinkList InitList()
{
int count=0;
LinkList pHead=NULL;
LinkList pEnd,pNew;
pEnd=pNew=(LinkList)malloc(sizeof(struct LNode));
printf("请输入数据:\n");
scanf("%d",&pNew->data);
while(pNew->data)
{
count++;
if(count==1)
{
pNew->next=pHead;
pEnd=pNew;
pHead=pNew;
}
else
{
pNew->next=NULL;
pEnd->next=pNew;
pEnd=pNew;
}
pNew=(LinkList)malloc(sizeof(struct LNode));
printf("请输入数据:\n");
scanf("%d",&pNew->data);
}
free(pNew);
total=total+count;
return pHead;
}
// 判断L是否为空表
void ListEmpty(LinkList L)
{
if(NULL==L->next)
printf("此表为空表!\n");
else
printf("此表不为空表!\n");
}
// 在链式线性表中第i个元素前插入新元素e
void ListInsert(LinkList L,int i,int e)
{
LinkList p;
LinkList s;
p=L;
int j=0;
while(p&&j<i-1)
{
p=p->next;
++j;
}
if(!p||j>i-1)
printf("不存在您要找的节点!\n");
else
{
s=(LinkList)malloc(sizeof(int));
s->data=e;
s->next=p->next;
p->next=s;
printf("插入节点成功!\n");
}
}
// 输出链式线性表
void ShowList(LinkList L)
{
LinkList p;
p=L->next;
if(p==NULL)
printf("此表为空表!\n");
else
while(p)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}
// 在链式线性表中删除第i个元素，并用e返回其值
void ListDelete(LinkList L,int i,int &e)
{
LinkList p;
LinkList q;
p=L;
int j=0;
while(p->next && j<i-1)
{
p=p->next;
++j;
}
if(!(p->next)||j>i-1)
printf("没有找到要删除的位置!");
else
{
q=p->next;
p->next=q->next;
e=q->data;
free(q);
}
}
// 用e返回L中第i个数据元素的值
void GetList(LinkList L,int i,int &e)
{
LinkList p;
p=L->next;
int j=0;
while(p->next && j<i-1)
{
p=p->next;
++j;
}
if(!(p)||j>i-1)
printf("没有找到要查找的位置!");
else
e=p->data;
}
// 对比a与b相等
bool compare(int a,int b)
{
if(a==b)
return 1;
else
return 0;
}
// 在链式线性表L中查找第1个值与e满足compare()d元素的位序
void LocateElem(LinkList L,int e)
{
int i=0;
LinkList p;
p=L;
while(p->next && !compare(p->data,e))
{
p=p->next;
i++;
}
if(NULL==p->next)
{
if(0==compare(p->data,e))
printf("没有该元素!\n");
else
printf("第1个与e相等的元素的位序为%d\n",i);
}
else
if(compare(p->data,e))
printf("没有该元素!\n");
}

LinkList MergeList_L(LinkList La,LinkList Lb)
{
int i,j,k;
LinkList pa_1,pb_1,pa_2,pb_2,pc,pd;
pa_1=La->next;
pc=pa_2=La;
pb_1=pb_2=Lb->next;
if(pa_1->data > pb_1->data)
{
pc=pa_2=Lb;
pa_1=Lb->next;
pb_1=pb_2=La->next;
}
while(pa_1 && pb_1)
{
if(pa_1->data >= pb_1->data)
{
pa_2->next=pb_1;
pb_2=pb_1->next;
pb_1->next=pa_1;
pb_1=pb_2;
pa_2=pa_2->next;
}
else
{
pa_1=pa_1->next;
pa_2=pa_2->next;
}
}
if(pb_1)
pa_2->next=pb_1;
pd=(LinkList)malloc(sizeof(struct LNode));
pd->next=NULL;
pa_2=pd;
k=total;
for(i=0;i<total;i++)
{
pa_1=pc->next;
for(j=1;j<k;j++)
pa_1=pa_1->next;
pb_1=(LinkList)malloc(sizeof(struct LNode));
pa_2->next=pb_1;
pa_2=pa_2->next;
pa_2->data=pa_1->data;
k--;
}
pa_2->next=NULL;
return pd;
}

2.流程图(实验要求1和3)

图1 主函数流程图

图2创建线性表La流程图

图3判断La是否为空表流程图

图4 插入元素(La)流程图

图5删除元素(La)流程图

图6定位元素(La)流程图

图7取元素(La)流程图

图8输出线性表流程图

图9输出线性表流程图
流程图(实验要求2和4)
图10主函数流程图

图11创建线性表La流程图

图12判断是否为空表流程图

图13插入元素流程图

图14删除元素流程图
图15定位元素流程图图 图16取元素流程图

图17创建Lb流程图

图18归并两表流程图
六、运行结果
1. (实验要求1和3)
点击运行，首先出现的是菜单界面，选择菜单选项进行操作，如图所示。

按“1”回车后，即可以创建顺序表La，输入“0”结束添加，如图所示。

输入2，判断La是否为空表，如图所示。

输入3，在指定的位序插入元素，如图所示。

输入4，在指定的位序删除元素，如图所示。

输入5，查找表中与之相等数的位序，如图所示。

输入6，查找相应位序对应的元素，如图所示。

输入7，输出顺序表中的容，如图所示。

输入8，创建顺序表Lb，如图所示。

输入9，归并两表为递减顺序，如图所示。

2. (实验要求2和4)

七、算法效率分析
八、实验小结
通过这个实验，感受到了指针的重要性，同时也感受到了指针并不是如你所愿的那样去指，稍不留神，就出错了。
再有函数定义时*与&与调用结构体成员的方法，课后应该再仔细斟酌斟酌，多多交流，多多练习把。

51 / 51