学《数据结构》课程实验报告实验名称：线性表基本操作的实现实验室(中心)：学生信息：专业班级：指导教师：实验完成时间： 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 <stdio.h>#include <conio.h>#define Max 116enum 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",&st);printf("请输入从1到%d的各元素(字符)，例如:abcdefg\n",st);getchar();for(i=0;i<st;i++)scanf("%c",&v.elem[i]);}BOOL Inse(sqlist &v,int loc,char ch) //插入一个元素，成功返回True，失败返回False{int i;if((loc<1)||(loc>st+1)){printf("插入位置不合理!\n");return False;}else if(st>=Max){printf("线性表已满!\n");return False;}else {for(i=st-1;i>=loc-1;i--)v.elem[i+1]=v.elem[i];v.elem[loc-1]=ch;st++;return True;}}BOOL del(sqlist &v,int loc,char &ch) //删除一个元素，成功返回True，并用ch返回该元素值，失败返回False{int j;if(loc<1||loc>st)return False;else {ch=v.elem[loc-1];for(j=loc-1;j<st-1;j++)v.elem[j]=v.elem[j+1];st--;return True;}}int Loc(sqlist v,char ch)//在线性表中查找ch的位置，成功返回其位置，失败返回-1{int i=0;while(i<st&&v.elem[i]!=ch) i++;if(v.elem[i]==ch)return i;else return(-1);}void print(sqlist v) //显示当前线性表所有元素{int i;for(i=0;i<st;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 < st && j < 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==st){while(j<st){s3.elem[k]=s2.elem[j];k++;j++;}}if(j==st){while(i<st){s3.elem[k]=s1.elem[i];k++;}}st=k;}2、链表的操作#include <conio.h>#include <stdio.h>#include <stdlib.h>#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("本程序实现链式结构的线性表的操作。