数据结构实验-线性表基本操作
学
《数据结构》课程
实验报告
实验名称：线性表基本操作的实现实验室(中心)：
学生信息：
专业班级：
指导教师：
实验完成时间： 2016
实验一线性表基本操作的实现
一、实验目的
1.熟悉C语言的上机环境，进一步掌握C语言的结构特点。
2.掌握线性表的顺序存储结构的定义及C语言实现。
3.掌握线性表的链式存储结构——单链表的定义及C语言实现。
4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。
5.掌握线性表在链式存储结构——单链表中的各种基本操作。
二、实验内容及要求
1.顺序线性表的建立、插入、删除及合并。
2.链式线性表的建立、插入、删除及连接。
三、实验设备及软件
计算机、Microsoft Visual C++ 6.0软件
四、设计方案（算法设计）
㈠采用的数据结构
本程序顺序表的数据逻辑结构为线性结构，存储结构为顺序存储；链表的数据逻辑结构依然为线性结构，存储结构为链式结构。
㈡设计的主要思路
1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度，顺序表的长度和元素由用户输入；
2.利用前面建立的顺序表，对顺序表进行插入、删除及合并操作；
3.建立一个带头结点的单链表，结点的值域为整型数据，链表的元素由用户输入；
4.对前面建立的链表进行插入、删除及连个链表的连接操作；
㈢算法描述
1、顺序表
void Init(sqlist &);//初始化顺序表
BOOL Inse(sqlist &,int,char); //在线性表中插入元素
BOOL del(sqlist&,int,char &); //在线性表中删除元素
int Loc(sqlist,char); //在线性表中定位元素
void print(sqlist); //输出顺序表
void combine( sqlist & , sqlist & , sqlist &);//两个线性表的合并
2、链表
void CreaL(LinkList &,int); //生成一个单链表
BOOL LInsert(LinkList &,int,char); //在单链表中插入一个元素
BOOL LDele(LinkList &,int,char &); //在单链表中删除一个元素
BOOL LFind_key(LinkList,char,int &); //按关键字查找一个元素
BOOL LFind_order(LinkList,char &,int); //按序号查找一个元素
void LPrint(LinkList); //显示单链表所有元素
void LUnion(LinkList &,LinkList &,LinkList &,int); //两个链表的连接
五、程序代码
1、顺序表
#include
#include
#define Max 116
enum BOOL{False,True};
typedef struct
{
char elem[Max]; //线性表
int last; //last指示当前线性表的长度
}sqlist;
void Init(sqlist &);
BOOL Inse(sqlist &,int,char); //在线性表中插入元素
BOOL del(sqlist&,int,char &); //在线性表中删除元素
int Loc(sqlist,char); //在线性表中定位元素
void print(sqlist);
void combine( sqlist & , sqlist & , sqlist &);
void main()
{
sqlist L1;
sqlist L2;
sqlist L3;
int loc,S=1;
char j,ch;
BOOL temp;
printf("本程序用来实现顺序结构的线性表。\n");
printf("可以实现查找、插入、删除、两个线性表的合并等操作。\n"); Init(L1);
while(S)
{
printf("\n请选择:\n");
printf("1.显示所有元素\n");
printf("2.插入一个元素\n");
printf("3.删除一个元素\n");
printf("4.查找一个元素\n");
printf("5.线性表的合并\n");
printf("6.退出程序\n\n");
scanf(" %c",&j);
switch(j)
{
case '1':print(L1); break;
case '2':{printf("请输入要插入的元素(一个字符)和插入位置:\n");
printf("格式：字符，位置；例如:a,2\n");
scanf("%c,%d",&ch,&loc);
temp=Inse(L1,loc,ch);
if(temp==False) printf("插入失败!\n");
else {printf("插入成功!\n");
print(L1);
}
break;
}
case '3':{printf("请输入要删除元素的位置:");
scanf("%d",&loc);
temp=del(L1,loc,ch);
if(temp==True) printf("删除了一个元素:%c\n",ch);
else printf("该元素不存在!\n");
printf("删除该元素后的线性表为:");
print(L1);
break;
}
case '4':{printf("请输入要查找的元素:");
scanf(" %c",&ch);
loc=Loc(L1,ch);
if(loc!=-1) printf("该元素所在位置:%d\n",loc+1);
else printf("%c 不存在!\n",ch);
break;
}
case '5':{printf("请输入要进行合并的第二个线性表:");
Init(L2);
combine(L1,L2,L3);
printf("合并前的两个线性表如下:\n");
print(L1);
print(L2);
printf("输出合并后的线性表如下:\n");
print(L3);
break;
}
default:S=0;printf("程序结束，按任意键退出!\n");
}
}
getch();
}
void Init(sqlist &v)//初始化线性表
{
int i;
printf("请输入初始线性表长度：n=");
scanf("%d",&https://www.wendangku.net/doc/3e16405407.html,st);
printf("请输入从1到%d的各元素(字符)，例如:abcdefg\n",https://www.wendangku.net/doc/3e16405407.html,st);
getchar();
for(i=0;i scanf("%c",&v.elem[i]); } BOOL Inse(sqlist &v,int loc,char ch) //插入一个元素，成功返回True，失败返回False { int i; if((loc<1)||(loc>https://www.wendangku.net/doc/3e16405407.html,st+1)) { printf("插入位置不合理!\n"); return False; } else if(https://www.wendangku.net/doc/3e16405407.html,st>=Max) {printf("线性表已满!\n"); return False; } else { for(i=https://www.wendangku.net/doc/3e16405407.html,st-1;i>=loc-1;i--) v.elem[i+1]=v.elem[i]; v.elem[loc-1]=ch; https://www.wendangku.net/doc/3e16405407.html,st++; return True; } } BOOL del(sqlist &v,int loc,char &ch) //删除一个元素，成功返回True，并用ch返回该元素值，失败返回False { int j; if(loc<1||loc>https://www.wendangku.net/doc/3e16405407.html,st) return False; else { ch=v.elem[loc-1]; for(j=loc-1;j v.elem[j]=v.elem[j+1]; https://www.wendangku.net/doc/3e16405407.html,st--; return True; } } int Loc(sqlist v,char ch)//在线性表中查找ch的位置，成功返回其位置，失败返回-1 { int i=0; while(i if(v.elem[i]==ch) return i; else return(-1); } void print(sqlist v) //显示当前线性表所有元素 { int i; for(i=0;i printf("%c ",v.elem[i]); printf("\n"); } void combine( sqlist &s1 , sqlist &s2 , sqlist &s3 )//顺序表的连接{ int i=0 ; int j=0 ; int k=0 ; while( i < https://www.wendangku.net/doc/3e16405407.html,st && j < https://www.wendangku.net/doc/3e16405407.html,st) { if(s1.elem[i]<=s2.elem[j]) { s3.elem[k]=s1.elem[i]; i++; } else { s3.elem[k]=s2.elem[j]; j++; } k++; } if(i==https://www.wendangku.net/doc/3e16405407.html,st) { while(j { s3.elem[k]=s2.elem[j]; k++; j++; } } if(j==https://www.wendangku.net/doc/3e16405407.html,st) { while(i { s3.elem[k]=s1.elem[i]; k++; } } https://www.wendangku.net/doc/3e16405407.html,st=k; } 2、链表的操作 #include #include #include #define LEN sizeof(LNode) enum BOOL{False,True}; typedef struct node { char data; struct node *next; }LNode,*LinkList; void CreaL(LinkList &,int); //生成一个单链表 BOOL LInsert(LinkList &,int,char); //在单链表中插入一个元素 BOOL LDele(LinkList &,int,char &); //在单链表中删除一个元素 BOOL LFind_key(LinkList,char,int &); //按关键字查找一个元素 BOOL LFind_order(LinkList,char &,int); //按序号查找一个元素 void LPrint(LinkList); //显示单链表所有元素 void LUnion(LinkList &,LinkList &,LinkList &,int); //两个链表的连接 void main() { LinkList L; LinkList T; LinkList H; BOOL temp; int num,num1,loc,flag=1; char j,ch; printf("本程序实现链式结构的线性表的操作。\n"); printf("可以进行插入，删除，定位，查找等操作。\n"); printf("请输入初始时链表长度:"); scanf("%d",&num); CreaL(L,num); LPrint(L); while(flag) { printf("请选择:\n"); printf("1.显示所有元素\n"); printf("2.插入一个元素\n"); printf("3.删除一个元素\n"); printf("4.按关键字查找元素\n"); printf("5.按序号查找元素\n"); printf("6.链表的连接\n"); printf("7.退出程序\n"); scanf(" %c",&j); switch(j) { case '1':LPrint(L); break; case '2':{printf("请输入元素(一个字符)和要插入的位置:\n"); printf("格式:字符，位置；例如:a,3\n"); scanf(" %c,%d",&ch,&loc); temp=LInsert(L,loc,ch); if(temp==False) printf("插入失败!\n"); else printf("插入成功!\n"); LPrint(L); break; } case '3':printf("请输入要删除的元素所在位置:"); scanf("%d",&loc); temp=LDele(L,loc,ch); if(temp==False) printf("删除失败!\n"); else printf("成功删除了一个元素:%c\n",ch); LPrint(L); break; case '4':if(L->next==NULL) printf("链表为空!\n"); else { printf("请输入要查找的元素(一个字符):"); scanf(" %c",&ch); temp=LFind_key(L,ch,loc); if(temp==False) printf("没有找到该元素!\n"); else printf("该元素在链表的第%d个位置。\n",loc); } break; case '5':if(L->next==NULL) printf("链表为空!\n"); else { printf("请输入要查找的位置:"); scanf("%d",&loc); temp=LFind_order(L,ch,loc); if(temp==False) printf("该位置不存在!\n"); else printf("第%d个元素是：%c\n",loc,ch); } break; case '6':if(L->next==NULL) printf("链表为空!\n"); else { printf("请输入第二个链表的长度:"); scanf("%d",&num1); CreaL(T,num1); } if(T->next==NULL) printf("第二个链表为空!\n"); LUnion(L,T,H,num+num1); printf("输出连接后链表中的所有元素:"); printf("\n"); LPrint(H); break; default:flag=0;printf("程序结束，按任意键退出!\n"); } } getch(); } void CreaL(LinkList &v,int n)//生成一个带头结点的有n个元素的单链表 { int i; LinkList p; v=(LinkList)malloc(LEN); v->next=NULL; printf("请输入%d个字符：例如：abcdefg\n",n); getchar(); for(i=n;i>0;--i) {p=(LinkList)malloc(LEN); scanf("%c",&p->data); p->next=v->next; v->next=p; } } BOOL LInsert(LinkList &v,int i,char e)//在单链表的第i各位置插入元素e，成功返回True，失败返回False { LinkList p,s; int j=0; p=v; while(p&&j if(!p||j>i-1) return False; s=(LinkList)malloc(LEN); s->data=e; s->next=p->next; p->next=s; return True; } BOOL LDele(LinkList &v,int i,char &e)//在单链表中删除第i个元素，成功删除返回True，并用e返回该元素值，失败返回False { LinkList p,q; int j=0; p=v; while(p->next&&j {p=p->next;++j;} if(!(p->next)||j>i-1) return False; q=p->next;p->next=q->next; e=q->data; free(q); return True; } BOOL LFind_key(LinkList v,char e,int &i)//在单链表中查找关键字为e的元素，成功返回True,并用i返回该元素位置，失败返回False { i=1; LinkList p; p=v->next; while((p->data!=e)&&(p->next!=NULL)) {p=p->next; i++;} if(p->data!=e) return False; else return True; } BOOL LFind_order(LinkList v,char &e,int i)//在单链表中查找第i个元素，成功返回True，并用e返回该元素值，失败返回False { LinkList p; int j=0; p=v; while(p->next&&j {p=p->next;++j;} if(j!=i) return False; else { e=p->data; return True; } } void LPrint(LinkList v) //显示链表所有元素 { LinkList q; q=v->next; printf("链表所有元素:"); while(q!=NULL) {printf("%c ",q->data);q=q->next;} printf("\n"); } void LUnion(LinkList &u,LinkList &v,LinkList &w,int n) { int i; LinkList p; w=(LinkList)malloc(LEN); //生成头结点 w->next=NULL; for(i=n;i>0;--i) {p=(LinkList)malloc(LEN); //生成新结点 if(u!=NULL) { p->data=u->data ; u=u->next; } else { p->data=v->data ; v=v->next; } p->next=w->next; w->next=p; } } 六、测试结果及说明 顺序表和链表基本操作的实现程序编译结果没错误和提醒，运行测试结果正确，没有出现错误； 1、顺序表 2、链表 七、实验体会 1.由于C语言的数组类型也有随机存取的特点，一维数组的机内表示就是顺序结构。因此，可用C语言的一维数组实现线性表的顺序存储。 2.注意如何取到第i个元素，在插入过程中注意溢出情况以及数组的下标与位序（顺序表中元素的次序）的区别。 3.单链表的结点结构除数据域外，还含有一个指针域。