《《数据结构》实验一 线性表及其应用.doc》由会员分享，可在线阅读，更多相关《《数据结构》实验一 线性表及其应用.doc（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、实验一 线性表及其应用一、实验目的1.熟悉C语言的上机环境，进一步掌握C语言的结构特点。2.掌握线性表的顺序存储结构的定义及C语言实现。3.掌握线性表的链式存储结构单链表的定义及C语言实现。4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。5.掌握线性表在链式存储结构单链表中的各种基本操作。二、实验内容 1.顺序线性表的建立、插入及删除。 2.链式线性表的建立、插入及删除。三、实验步骤1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。2.利用前面的实验先建立一个顺序表L=21，23，14，5，56，17，31，然后在第i个位置插入元素68。3.建立一个带头结点的单链表，结
2、点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。四、实现提示1.由于C语言的数组类型也有随机存取的特点，一维数组的机内表示就是顺序结构。因此，可用C语言的一维数组实现线性表的顺序存储。在此，我们利用C语言的结构体类型定义顺序表：#define MAXSIZE 1024typedef int elemtype; /* 线性表中存放整型元素 */typedef struct elemtype vecMAXSIZE; int len; /* 顺序表的长度 */sequenlist;将此结构定义放在一个头文件sqlist.h里，可避免在后面的参考程序中代码重复书写，另外在该头文件里
3、给出顺序表的建立及常量的定义。2. 注意如何取到第i个元素，在插入过程中注意溢出情况以及数组的下标与位序（顺序表中元素的次序）的区别。3.单链表的结点结构除数据域外，还含有一个指针域。用C语言描述结点结构如下： typedef int elemtype;typedef struct node elemtype data; /数据域 struct node *next; /指针域 linklist; 注意结点的建立方法及构造新结点时指针的变化。构造一个结点需用到C语言的标准函数malloc()，如给指针变量p分配一个结点的地址：p=(linklist *)malloc(sizeof(linkli
4、st);该语句的功能是申请分配一个类型为linklist的结点的地址空间，并将首地址存入指针变量p 中。当结点不需要时可以用标准函数free(p)释放结点存储空间，这时p为空值（NULL）。五、思考与提高1. 如果按由表尾至表头的次序输入数据元素，应如何建立顺序表。2. 在main函数里如果去掉L=&a语句，会出现什么结果？六、完整参考程序 1.顺序线性表的建立、插入及删除。#include #include #define MAX 30 /定义线性表的最大长度enum BOOLFalse,True; /定义BOOL型typedef struct char elemMAX; /线性表 int
5、last; /last指示当前线性表的长度sqlist;void initial(sqlist &); /初始化线性表BOOL insert(sqlist &,int,char); /在线性表中插入元素BOOL del(sqlist&,int,char &); /在线性表中删除元素int locate(sqlist,char); /在线性表中定位元素void print(sqlist); /显示线性表中所有元素void main()sqlist S; /S为一线性表 int loc,flag=1; char j,ch; BOOL temp;printf(本程序用来实现顺序结构的线性表。n);
6、printf(可以实现查找、插入、删除等操作。n); initial(S); /初始化线性表 while(flag) printf(请选择:n); printf(1.显示所有元素n); printf(2.插入一个元素n); printf(3.删除一个元素n); printf(4.查找一个元素n); printf(5.退出程序 n); scanf( %c,&j); switch(j)case 1:print(S); break; /显示所有元素 case 2:printf(请输入要插入的元素(一个字符)和插入位置:n); printf(格式：字符，位置；例如:a,2n); scanf( %c,%
7、d,&ch,&loc); /输入要插入的元素和插入的位置 temp=insert(S,loc,ch); /插入 if(temp=False) printf(插入失败!n); /插入失败 else printf(插入成功!n); print(S); /插入成功 break; case 3:printf(请输入要删除元素的位置:); scanf(%d,&loc); /输入要删除的元素的位置 temp=del(S,loc,ch); /删除 if(temp=True) printf(删除了一个元素:%cn,ch); /删除成功 else printf(该元素不存在!n); /删除失败 print(S)
8、; break; case 4:printf(请输入要查找的元素:); scanf( %c,&ch); /输入要查找的元素 loc=locate(S,ch); /定位 if(loc!=-1) printf(该元素所在位置:%dn,loc+1); /显示该元素位置 else printf(%c 不存在!n,ch);/当前元素不存在 break; default:flag=0;printf(程序结束，按任意键退出!n); getch();void initial(sqlist &v)/初始化线性表 int i; printf(请输入初始线性表长度：n=); /输入线性表初始化时的长度 scanf(
9、%d,&v.last); printf(请输入从1到%d的各元素(字符)，例如:abcdefgn,v.last); getchar(); for(i=0;iv.last;i+) scanf(%c,&v.elemi); /输入线性表的各元素BOOL insert(sqlist &v,int loc,char ch) /插入一个元素，成功返回True，失败返回False int i; if(locv.last+1) printf(插入位置不合理!n); /位置不合理 return False; else if(v.last=MAX) /线性表已满 printf(线性表已满!n); return F
10、alse; else for(i=v.last-1;i=loc-1;i-) v.elemi+1=v.elemi;/其后元素依次后移 v.elemloc-1=ch; /插入元素 v.last+; /线性表长度加一 return True; BOOL del(sqlist &v,int loc,char &ch) /删除一个元素，成功返回True，并用ch返回该元素值，失败返回False int j; if(locv.last) /删除位置不合理 return False; else ch=v.elemloc-1; /ch取得该元素值 for(j=loc-1;jv.last-1;j+) v.ele
11、mj=v.elemj+1; /其后元素依次前移 v.last-; /线性表长度减一 return True; int locate(sqlist v,char ch)/在线性表中查找ch的位置，成功返回其位置，失败返回-1 int i=0; while(iv.last&v.elemi!=ch) i+; /当前位置后移，直到找到为止 if(v.elemi=ch) /找到当前元素 return i; else return(-1);void print(sqlist v) /显示当前线性表所有元素int i; for(i=0;iv.last;i+) printf(%c ,v.elemi); pri
12、ntf(n); 2.链式线性表的建立、插入及删除。#include #include #include #define LEN sizeof(LNode) /定义LEN为一个节点的长度enum BOOLFalse,True; /定义BOOL型typedef struct nodechar data; /数据域 struct node *next;/指向下一个节点的指针LNode,*LinkList;void CreatList(LinkList &,int); /生成一个单链表BOOL ListInsert(LinkList &,int,char); /在单链表中插入一个元素BOOL List
13、Delete(LinkList &,int,char &); /在单链表中删除一个元素BOOL ListFind_keyword(LinkList,char,int &); /按关键字查找一个元素BOOL ListFind_order(LinkList,char &,int); /按序号查找一个元素void ListPrint(LinkList); /显示单链表所有元素void main()LinkList L; BOOL temp; int num,loc,flag=1; char j,ch; printf(本程序实现链式结构的线性表的操作。n); printf(可以进行插入，删除，定位，查
14、找等操作。n); printf(请输入初始时链表长度:); /输入生成单链表时的元素个数 scanf(%d,&num); CreatList(L,num); /生成单链表 ListPrint(L); while(flag) printf(请选择:n); printf(1.显示所有元素n); /显示链表元素 printf(2.插入一个元素n); /插入链表元素 printf(3.删除一个元素n); /删除链表元素 printf(4.按关键字查找元素n); /按关键字查找 printf(5.按序号查找元素n); /按序号查找 printf(6.退出程序 n); /退出 scanf( %c,&j);
15、 switch(j)case 1:ListPrint(L); break; case 2:printf(请输入元素(一个字符)和要插入的位置:n); printf(格式:字符，位置；例如:a,3n); scanf( %c,%d,&ch,&loc); /输入要插入的元素和要插入的位置 temp=ListInsert(L,loc,ch); /插入 if(temp=False) printf(插入失败!n); /插入失败 else printf(插入成功!n); /成功插入 ListPrint(L); break; case 3:printf(请输入要删除的元素所在位置:); scanf(%d,&l
16、oc); /输入要删除的节点的位置 temp=ListDelete(L,loc,ch); /删除 if(temp=False) printf(删除失败!n); /删除失败 else printf(成功删除了一个元素:%cn,ch); /删除成功，显示该元素 ListPrint(L); break; case 4:if(L-next=NULL) /链表为空 printf(链表为空!n); elseprintf(请输入要查找的元素(一个字符):); scanf( %c,&ch); /输入要查找的元素 temp=ListFind_keyword(L,ch,loc); /按关键字查找 if(temp=
17、False) printf(没有找到该元素!n); /查找失败 else printf(该元素在链表的第%d个位置。n,loc); /成功查找，显示该元素位置 break; case 5:if(L-next=NULL) /链表为空 printf(链表为空!n); elseprintf(请输入要查找的位置:); scanf(%d,&loc); /输入要查找的元素的位置 temp=ListFind_order(L,ch,loc); /按序号查找 if(temp=False) printf(该位置不存在!n); /查找失败 else printf(第%d个元素是：%cn,loc,ch); /成功查找
18、，显示该元素 break; default:flag=0;printf(程序结束，按任意键退出!n); getch();void CreatList(LinkList &v,int n)/生成一个带头结点的有n个元素的单链表 int i; LinkList p; v=(LinkList)malloc(LEN); /生成头结点 v-next=NULL; printf(请输入%d个字符：例如：abcdefgn,n); getchar(); for(i=n;i0;-i) p=(LinkList)malloc(LEN); /生成新结点 scanf(%c,&p-data); p-next=v-next;
19、 v-next=p; BOOL ListInsert(LinkList &v,int i,char e)/在单链表的第i各位置插入元素e，成功返回True，失败返回False LinkList p,s; int j=0; p=v; while(p&jnext;+j; /查找第i-1个元素的位置 if(!p|ji-1) return False; /没有找到 s=(LinkList)malloc(LEN); /生成一个新结点 s-data=e; s-next=p-next; /将新结点插入到单链表中 p-next=s; return True;BOOL ListDelete(LinkList &
20、v,int i,char &e)/在单链表中删除第i个元素，成功删除返回True，并用e返回该元素值，失败返回False LinkList p,q; int j=0; p=v; while(p-next&jnext;+j; if(!(p-next)|ji-1) return False; /查找失败 q=p-next;p-next=q-next; /删除该元素 e=q-data; /e取得该元素值 free(q); /释放该元素空间 return True;BOOL ListFind_keyword(LinkList v,char e,int &i)/在单链表中查找关键字为e的元素，成功返回T
21、rue,并用i返回该元素位置， /失败返回False i=1; LinkList p; p=v-next; while(p-data!=e)&(p-next!=NULL)/p指针指向下一个，直到 p=p-next; i+; /找到或到链表尾为止 if(p-data!=e) /该元素在链表中不存在 return False; else return True;BOOL ListFind_order(LinkList v,char &e,int i)/在单链表中查找第i个元素，成功返回True，并用e返回该元素值， /失败返回False LinkList p; int j=0; p=v; whil
22、e(p-next&jnext;+j; if(j!=i) return False; /查找失败 else e=p-data; /查找成功，用e取得该元素值 return True; void ListPrint(LinkList v) /显示链表所有元素 LinkList q; q=v-next; printf(链表所有元素:); while(q!=NULL) printf(%c ,q-data);q=q-next; printf(n);10及 )应)( ; -) % ! ):有表( 元有链 素该 功找 = 失找/ !; ; - 元个第直动/ 0 值素回用 返，第中单 & , 存存链该/ =
23、(为表或/ ; ; 直，下指 ! ( - 返置位该用, 功成元字查表 & 空素释 (素该 / ; 该/; 失找 ; | (;+; =位素个找/ & - 0= , 返失元返并 回删，素第表在 , 中链到点/ ; 结个/ ( 找没 |(位位个 找/+ - ) &( 结成/) ) ( - ()( ) ： 入 结成/; ) 表表素 结头一 ( ) )!意，束( 0 元该找查 ) , 是元第 失查 !存该 = 查号/; ( _ 位素找要/ ) , ):位要请( )空链 为为 = ( 位元显查成 ; 位 的素( 失查 元有( ) = ( 查键/ ( _ = 元找入/ )& ):字(元要输( ) 空表( 为
24、链 : )( 元示功删 :了除 失除/!失( 删删 ;, = 位的的入/ ; &%( )置元除输 ) 插成/) 入( 失失/)!失( ) = ( 插/ = 位入和的要输 ;), ) 如；，式( ):位和字(入 )( : ( )& ( 退/ 序.( 查号/)找号 查键/ 查关 ( 元链除 一. 元表入 )素元插( 元表/ ) 所. )择 链成生 ) ,%(个素时成生 长链入 )找，进以 ) 作的的式链序 , , ( 元所链/ 元个号按 ) _ 元一查关/) 元一删单在) & 元一中链在; 链个生/;)& 指的一指/ 据据 ; 义/; , 长的一为定 . 除及插的性链) ) % +; 元有线当/
25、( ) 元元找 为找直置前 + ) . 合不/ 理合位 )+ |) ( 回， 回功元插 , 元的线/ .,% =() ) . 如符字的%入输 ) , 长时化性输/=度表线请( 性线 & ) )意任序 ; : 存不元/ ,在存 位素示/) %位元( - ( 定/ ) ( 元元查/ , )元找请 )( 失除/;存不该 成删 , :一删 ( 删/ , 位素的入/ ; ):置除入请 成入 )( ;功插 失插/)败( = 插/ ;) ( 位入素入入/ ),& %( ) ,如置符：( )置插)个素插输请 元有显/ )& ) 序出 )素一 )元除 )元一 ( )素示 ( )择请 性化/ ) ) 。除、实(
26、)的序现用本 = 性一/ ( 元所性显/ ( 元定表/ ) 元删表在 元插性/ , 性化初/;) 长长前指 性线 义 长大性定/ 除除插的线.程参果么出句 果数 在表顺立应据输的至由果提考） 值时空点释) 标可需当中量指地并空的点 为类分是的该) * 址的结配变给) 数的 需结构变指结造方立结 针指/ 据数 下如结言用。个还域数点结别别序的表（与的及况注程入元第何注义的及建序给头在，重中考的免， 件个定构 * 的序 *型存性 / 表顺定构结用我储存表现数一言，此结就内组一特取随型数 提现表链相法尾按输将求型域点表单头个 素插个第后， ， 表个立验的度长表及元该并序元数含步验除及插建线. 除及、建性.内验实作本各表单结存链线作本各中顺储顺表现实及的单存的性现言及定储存的点构的握步境上语悉目验