数据结构实验

1、学数据结构课程实验报告实验 名称：线性表基本操作的实现实验室（中心）：学生信息：专业班级：指导教师：实验完成时间： 2016教师评阅意见：签名：年 月 日实验成绩：实验一线性表基本操作的实现一、实验目的1. 熟悉C语言的上机环境，进一步掌握C语言的结构特点。2. 掌握线性表的顺序存储结构的定义及C语言实现。3. 掌握线性表的链式存储结构一一单链表的定义及C语言实现。4. 掌握线性表在顺序存储结构即顺序表中的各种基本操作。5. 掌握线性表在链式存储结构一一单链表中的各种基本操作。二、实验内容及要求1. 顺序线性表的建立、插入、删除及合并。2. 链式线性表的建立、插入、删除及连接。三、实验设备及软

2、件计算机、Microsoft Visual C+ 6. 0 软件四、设计方案（算法设计）采用的数据结构本程序顺序表的数据逻辑结构为线性结构，存储结构为顺疗;存储：链表的数据逻 辑结构依然为线性结构，存储结构为链式结构。设计的主要思路1建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度，顺序表的 长度和元素由用户输入；2. 利用前面建立的顺序表，对顺序表进行插入、删除及合并操作；3. 建立一个带头结点的单链表，结点的值域为整型数据，链表的元素山用户输入；4. 对前面建立的链表进行插入、删除及连个链表的连接操作；算法描述顺序表void Init(sqlist &);/初始化顺序

3、表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); 在单链

4、表中插入一个元素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 V顺序表#include <stdio.

5、h>#include <conio.h>#define Max 116enum BOOL False,True;typedef structchar elemMax; 线性表int last;Jsqlist;/last指示当前线性表的长度void Init(sqlist &);BOOL Inse(sqlist &,int,char); /在线性表中插入元素BOOL del(sqlist&,int,char &); /在线性表中删除元素 int Loc(sqlist,char);在线性表中定位元素void print(sqlist);void c

6、ombine( sqlist & , sqlist & , sqlist &);void main（）sqlist LI;sqlist L2;sqlist L3;int loc,S=l;char j,ch;BOOL temp;printf（”本程序用来实现顺序结构的线性表。n"）;printf（”可以实现查找、插入、删除、两个线性表的合并等操作。n“）;Init（Ll）;while（S）printf（"n 请选择:n”）；printf（*'l.显示所有元素n"）;printf（"2.插入一个元素n”）；printfC

7、9;3 .删除一个元素 n”）;printf（"4.查找一个元素 n”）；printfC'5.线性表的合并n“）;printf(H6.退出程序 nn");scanf(H %c”,&j);switch(j) case ,r：print(Ll); break;case 2:printf("请输入要插入的元素(一个字符)和插入位置:n"); printf("格式:字符，位置；例如:a,2n"); scanf(H%c,%d'&ch.&loc);temp=Inse(Ll ,loc,ch);if(temp=

8、False) printf("插入失败!n");else printf("插入成功!n");print(Ll);break;case 3:printf("请输入要删除元素的位置:”)；scanf(H%d,&loc);temp 二 del(L 1 ,loc,ch);if(temp=True) printf("删除了 一个元素:%cn",ch); else printf("该元素不存在!n");printfC1删除该元素后的线性表为:“)；print(Ll);break;case '4'

9、;: printf("请输入要查找的元素:");scanf(H %c'&ch);loc=Loc(Ll,ch);if(loc!=-l) printfC该元素所在位置:%dn",loc+l);else printf(H%c 不存在!n",ch);break;case 5:printf("请输入要进行合并的第二个线性表:");Init(L2);combine(Ll ,L2,L3)；printfC合并前的两个线性表如下:n”)；print(Ll);print(L2);printf(”输出合并后的线性表如下:n”);print(

10、L3);break;default:S=O;printf("Jg序结束，按任意键退出!n");)getch();)void Init(sqlist &v)初始化线性表int i;printf(“请输入初始线性表长度：n=”)；scanf( n%d H ,&v. last);printf("请输入从1到d的各元素(字符)，例如:abcdefgn",v.last); getchar();for(i=0;i<v.last;i+)scanf(H%c,&v.e!emi);BOOL Inse(sqlist &v,int loc,

11、char ch) 插入一个元素,成功返回 True,失败返回Falseint i;if(loc< l)ll(loc>v.last+1)printf("插入位置不合理!n");return False;else if(v.last>=Max)printf(”线性表已满!n“);return False;)else fbr(i=v.last-1 ;i>=loc-1 ;i)v.elemi+l=v.elemi;v.elemloc-l=ch;v.last+;return True;BOOLdel(sqlist &v,int loc,char &

12、ch) /删除一个元素，成功返回 True,并用 ch 返回 该元素值，失败返回Falseint j;if(loc<l IlloOv.last)return False;else ch=v.elemIoc-l;for(j=loc-l ;j Vv.las卜 1 ;j+)v.elemj=v.elemj+l;v.last;return True;int Loc(sqlist v,char ch)在线性表中查找ch的位置，成功返回其位置，失败返回-1int i=0;while(i<v.last&&v.elemfi !=ch) i+;if(v.elemi=ch)return

13、i;else return(-l);)void print(sqlist v) 显示'"l前线性表所有元素int i;for(i=0;i<v.last;i+)printf("%c ",v.elemi);printf("n");)void combine( sqlist &sl , sqlist &s2 , sqlist &s3 )顺序表的连接int i=0;int j=0 ;int k=0 ;while( i < si.last && j < s2.1ast)if(sl .ele

14、mi<=s2.elemj)s3.elemk=s 1 .elemi;i+；elses3.elemk=s2.elemj; j+;k+;)if(i=sl.last)while(j<s2.1ast)s3.elemk=s2.elemj;k+;j+;if(j=s2.1ast)while(i<sl.last)s3.elemk=s 1 .elemfi;k+;1)s3.1 ast=k;2、链表的操作#include <coni#include <stdio.h>#include <stdlib.h>#define LEN sizeof(LNode)enum BOO

15、LFalse,True;typedef struct nodechar data;struct node *next;LNode,*LinkList;void CreaL(LinkList &,int); 生成一个单链表BOOL LInsert(LinkList &,int,char); 在单链表中插入一个元素BOOL LDele(LinkList&jnt,char &); 在单链表中删除一个元素BOOL LFind_key(LinkList,char,int &); /按关键字查找一个元素BOOL LFind_order(LinkList,char &

16、amp;,int); 按序号查找一个元素 void LPrint(LinkList);显示单链表所有元素void LUnion（LinkList &,LinkList &,LinkList &,int）; 两个链表的连接void main（）LinkList L;LinkList T;LinkList H;BOOL temp;int num,num 1 ,loc,flag= 1;char j,ch;printfC本程序实现链式结构的线性表的操作。n“）；printf（"可以进行插入，删除，定位，查找等操作。n”）;printfC*请输入初始时链表长度:”）；s

17、canf（n%d,&num）;CreaL（Ljium）;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（H %c”,&j）;switch（j）case T:LPrint(L);

18、break;case 2:printf("请输入元素(一个字符)和要插入的位置:n"); printf("格式:字符，位置；例如:a,3n");scanf(H %c,%d”,&ch,&loc);temp=LInsert(LJoc,ch);if(temp=False) printf("插入失败!n");else printf("插入成功!n");LPrint(L);break;case 3:printf(”请输入要删除的元素所在位置:”)；scanf(”d”,&loc);temp=LDele(

19、L,loc,ch);if(temp=False) printf("删除失败!n”);else printf("成功删除了一个元素:cn",ch);LPrint(L);break;case ,4,:if(L->next=NULL)printfC链表为空!W);prints请输入要查找的元素(一个字符):J;scanf(H %c'&ch);temp 二 LFind_key(L,choc);if(temp=False) printf("没有找到该元素!n");else printf(n该元素在链表的第d个位置。nMoc);bre

20、ak;case ,5,:if(L->next=NULL)printfC链表为空!nj;elseprintf("请输入要查找的位置:”)； scanf(H%d*&loc); temp=LFind_order(L,chJoc); if(temp=False) printf("该位置不存在!n"); else printf(”个元素是：%cn",loc,ch);break;case ,6,:if(L->next=NULL)printfC 链表为空!n“);printfC1请输入第二个链表的长度:J;scanf(H%d,',&

21、num 1);CreaL(T.numl);if(T->next=NULL)printf(”第二个链表为空!n“);LUnion(LXH,num+num 1);printf("输出连接后链表中的所有元素:“);printfCXn");LPrint(H);break;default:flag=O;printf(HJS序结束,按任意键退出!n");getch();)void CreaL(LinkList &v,int n)生成一个带头结点的有n个元素的单链表int i;LinkList p;v=(LinkList)malloc(LEN);v->nex

22、t=NULL;printf('谓输入d 个字符：例如：abcdefgn",n);getchar();for(i=n;i>0;i)p=(LinkList)malloc(LEN);scanf(n%c,&p->data);p->next=v->next;v->next=p;)BOOL LInsert(LinkList &v,int i,char e)在单链表的第i各位置插入元素e,成功返 回True,失败返回FalseLinkList p,s;int j=0;p=v；while(p&&j<i-l) (p=p->

23、;next;+j;(if(!pllj>M) return False;s=(LinkList)malloc(LEN);s->data=e;s->next=p >ncxt;p->next=s;return True;BOOL LDele(LinkList &v,int i,char &e)在单链表中删除第i个元素，成功删除返 回True,并用e返回该元素值，失败返回FalseLinkList p,q;int j=0;p=v；while(p->next&&j vi 1)p=p->next;+j;)if(!(p->nex

24、t)llj>i-l) 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返回该元素位置，失败返回Falsei=l；LinkList p;p=v->next;whi le(p->data!=e)&&(p->next !=NULL)(p=p->next; i+;if(p->data!=e)r

25、eturn False; else return True;BOOL LFind_order(LinkList v,char &e,int i)在单链表中查找第i个元素，成功返回 True,并用e返回该元素值，失败返回FalseLinkList p;int j=0;p=v；while(p->next&&jvi)p=p->next;+4j;( if(j!=i) return False; else e=p->data;return True;void LPrint(LinkList v) 显示链表所有元素LinkList q;q=v->next;p

26、rintf("链表所有元素:”)；while(q!=NULL)printf(M%c ,q->data);q=q->next;printf(MnH);void LUnion(LinkList &u,LinkList &v,LinkList &w,int n)int i;LinkList p;w=(LinkList)malloc(LEN); /生成头结点wonext二NULL;for(i=n;i>0;i)p=(LinkList)malloc(LEN); / 生成新结点if(u!=NULL)p->data=u->data ;u=u-&g

27、t;next;elsep->data=v->data ;v=v->next;p->next=w->next;w->next=p;)六、测试结果及说明顺序表和链表基本操作的实现程序编译结果没错误和提醒，运行测试结果正确,没有出现错误；1、顺序表申程片用弄知刃页序结构的线性裘。內以实现査找、插入、删除、两个线性表的合笄等燥佑. 側输入初始线性表长度：n=5荷希入从1到5的容元養宇符），Wfl：abcdefgrft794诗進择：1稣所有元矛2 插入Y元孝3 删除T元姜 2 黃找T、元紊 5 线性表的合并 4退出程用请输入要进行合并色第二个线性表:请输入初集线性表长

28、虧H=3 貨输入从1到3的各元耒（字符），Wabcdefg咅并前的两个线性表如下：5 9 7 2 49 8 4期岀合并后的线性表如下：5 9 7 2 4 9 8 4宵选拓1. 且示所有西第2矯人T、元丢? 删除一T元疾4.香藏一元圭捜狗拼音输人法全：2、链表 i环DQvktopXOTfWjraSXt统取坯爹gbug»tt炸.。2- X衣程序实现槌出洁£的线仕土二I壬仁可以送行插入.册除罡亿萱拽尊换作c 清谕入初始时链表长氐si誅）入处字符：例如：abcdcf79512诂表所有元素:2 15 9?i舌选拓1显云所有元爭2. ffiA1、元宏3.8H除Y元辛4.按关链字鱼找元素3拎序号查找元寿&徴表的迭捉了 退出程用:青输入第二个馆表的长鹿：4i論入4个字符：例如abcdefg7395输出连接后论表中的所有