数据结构实验-线性表基本操作

. 可编辑范本 学学 数据结构数据结构课程课程 实验报告实验报告 实实 验验 名名 称：称： 线性表基本操作的实现 实验室实验室( (中心中心) )： 学学 生生 信信 息：息： 专专 业业 班班 级：级： 指指 导导 教教 师师 ： 实验完成时间：实验完成时间： 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 /在线性表中插入元素 BOOL del(sqlist /在线性表中删除元素 int Loc(sqlist,char); /在线性表中定位元素 void print(sqlist); /输出顺序表 void combine( sqlist /两个线性表的合并 2、链表 void CreaL(LinkList /生成一个单链表 BOOL LInsert(LinkList /在单链表中插入一个元素 BOOL LDele(LinkList /在单链表中删除一个元素 BOOL LFind_key(LinkList,char,int /按关键字查找一个元素 . 可编辑范本 BOOL LFind_order(LinkList,char /按序号查找一个元素 void LPrint(LinkList); /显示单链表所有元素 void LUnion(LinkList /两个链表的连接 五、程序代码五、程序代码 1、顺序表 #include #include #define Max 116 enum BOOLFalse,True; typedef struct char elemMax; /线性表 int last; /last 指示当前线性表的长度 sqlist; void Init(sqlist BOOL Inse(sqlist /在线性表中插入元素 BOOL del(sqlist /在线性表中删除元素 int Loc(sqlist,char); /在线性表中定位元素 void print(sqlist); void combine( 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.退出程序nn); scanf( %c, switch(j) case 1:print(L1); break; case 2:printf(请输入要插入的元素(一个字符)和插入位置:n); printf(格式：字符，位置；例如:a,2n); scanf(%c,%d, temp=Inse(L1,loc,ch); if(temp=False) printf(插入失败!n); . 可编辑范本 else printf(插入成功!n); print(L1); break; case 3:printf(请输入要删除元素的位置:); scanf(%d, temp=del(L1,loc,ch); if(temp=True) printf(删除了一个元素:%cn,ch); else printf(该元素不存在!n); printf(删除该元素后的线性表为:); print(L1); break; case 4:printf(请输入要查找的元素:); scanf( %c, loc=Loc(L1,ch); if(loc!=-1) printf(该元素所在位置:%dn,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 printf(请输入初始线性表长度：n=); scanf(%d, printf(请输入从 1 到%d 的各元素(字符)，例如:abcdefgn,v.last); getchar(); for(i=0;i=Max) printf(线性表已满!n); return False; 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 if(locv.last) return False; else ch=v.elemloc-1; for(j=loc-1;jv.last-1;j+) v.elemj=v.elemj+1; v.last-; . 可编辑范本 return True; int Loc(sqlist v,char ch)/在线性表中查找 ch 的位置，成功返回其位置，失败 返回-1 int i=0; while(iv.last 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); printf(n); void combine( sqlist int j=0 ; int k=0 ; . 可编辑范本 while( i s1.last i+; else s3.elemk=s2.elemj; j+; k+; if(i=s1.last) while(js2.last) s3.elemk=s2.elemj; k+; j+; if(j=s2.last) while(inext=NULL) printf(链表为空!n); else printf(请输入要查找的元素(一个字符):); . 可编辑范本 scanf( %c, 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, temp=LFind_order(L,ch,loc); if(temp=False) printf(该位置不存在!n); else printf(第%d 个元素是：%cn,loc,ch); break; case 6:if(L-next=NULL) printf(链表为空!n); else printf(请输入第二个链表的长度:); scanf(%d, 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 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-next=v-next; v-next=p; . 可编辑范本 BOOL LInsert(LinkList int j=0; p=v; while(p+j; if(!p|ji-1) return False; s=(LinkList)malloc(LEN); s-data=e; s-next=p-next; p-next=s; return True; BOOL LDele(LinkList int j=0; p=v; while(p-next+j; if(!(p-next)|ji-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 LinkList p; p=v-next; while(p-data!=e) i+; if(p-data!=e) return False; else return True; BOOL LFind_order(LinkList v,char int j=0; p=v; while(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 LinkList p; w=(LinkList)malloc(LEN); /生成头结点 w-next=NULL; for(i=n;i0;-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.单链表的结点结构除数据域外，还含有一个指针域。 . 可编辑范本 线性表提升实验线性表提升实验 （一）（一） 、实现顺序表元素的就地逆置、实现顺序表元素的就地逆置 一、设计方案一、设计方案 采用的数据结构 本程序采用的数据逻辑结构为线性结构，存储结构为顺序结构，算法的总 体功能是实现顺序表中元素的逆置。 设计的主要思路 由用户确定初始顺序表的长度并输入初始顺序表的元素，然后通过交换元 素的方法将初始表中的元素进行逆置处理、输出元素。 算法描述 status Initlist_Sq(Sqlist *L) /对顺序表 A 进行初始化 v o . 可编辑范本 i d i n p u t ( S q l i s t * A) / / 对 一 . 可编辑范本 个 线 性 表 输 入 数 据， 是 先 输 入 长 度， 然 后 再 输 入 数 据 void print(Sqlist *A) /对一个线性表进行输出 . 可编辑范本 void invert(Sqlist *A) /实现一个顺序表的逆置 二、主要代码二、主要代码 #include #include #include #define SIZE 100 #define ListInc 10 #define OK 1 typedef struct int *elem; int length; int listsize; Sqlist; typedef int status; status Initlist_Sq(Sqlist *L) L-elem =(int *)malloc(SIZE*sizeof(status); if(!L-elem) printf(voerflow); else L-length=0; L-listsize=SIZE; return OK; /对一个线性表输入数据，是先输入长度，然后再输入数据 void input(Sqlist *A) . 可编辑范本 int i=0; printf(本程序用于实现顺序表的逆置。n); printf(n 请输入长度:n); scanf(%d, printf(请输入数:n); for(i=0;ilength;i+) scanf(%d, /对一个线性表进行输出 void print(Sqlist *A) int i; for(i=0;ilength;i+) printf(%dt,A-elemi); printf(nn); void invert(Sqlist *A) int n=A-length; int m=(A-length)/2,i; int temp; for(i=0;ielemi; A-elemi=A-elemn-i-1; A-elemn-i-1=temp; void main() Sqlist A; /定义一个线性表 A Initlist_Sq( /对 A 进行初始化 input( /输入数据 printf(输入的数据为:n); print( printf(逆序处理后为:n); invert( /对线性表 A 逆置 print( /输出逆置以后的 A 三、测试结果及说明三、测试结果及说明 由用户输入初始顺序表的长度以及元素，然后通过程序实现初始顺序表的 逆置并输出结果，程序的测试结果完全正确，没有出现任何的错误。 . 可编辑范本 （二）（二） 、实现单循环链表的逆置、实现单循环链表的逆置 一、设计方案一、设计方案 采用的数据结构 本程序采用的数据逻辑结构为线性结构，存储结构为链式存储结构，算法 的总体功能是实现单循环链表中元素的逆置。 设计的主要思路 由用户确定初始链表的长度并输入初始链表的元素，然后通过过交换指针 的方法将初始表中的元素进行逆置处理、输出元素。 算法描述 v o i d . 可编辑范本 c r e a t l i n k l i s t ( l i n k l i s t . 可编辑范本 struct lnode *next; lnode ,*linklist; /建立一个空表，初始化，并对其进行输入值 void creatlinklist(linklist if(!l) exit(OVERFLOW); l-next=l; /循环链表 linklist p,q; int i; . 可编辑范本 q=l; printf(请输入 %d 个元素:n,n); for(i=0;idata); p-next=q-next; q-next=p; q=p; /逆置函数 void invert(linklist p=l-next; q=p-next; r=q-next; while(p!=l) q-next=p; p=q; q=r; r=r-next; . 可编辑范本 int main() printf(本程序用于实现单循环链表的逆置处理：nn); linklist l,p; int length,i; printf(请输入元素的个数:n); scanf(%d, creatlinklist(l,length); p=l-next; printf(输入的链表为:n); while(p!=l) printf(%d ,p-data); p=p-next; printf(n); printf(逆置后的链表为n); invert(l); p=l-next; i=0; while(p!=l) printf(%d ,p-data); p=p-next; printf(n); . 可编辑范本 return 0; 三、测试结果及说明三、测试结果及说明 由用户确定输入的元素个数为 6 个，依次输入 16、25、34、43、52、61，逆 置处理后输出的结果为 61、52、43、32、21、16，程序运行的结果正确，没有出 现错误。 （三）（三） 、解决约瑟夫环的出列问题、解决约瑟夫环的出列问题 一、设计方案一、设计方案 采用的数据结构 本程序采用的数据逻辑结构为线性结构，存储结构为链式存储结构，算法 的总体功能是实现约瑟夫环的出列问题。 设计的主要思路 设编号为 1，2，3，n 的 n(n0)个人按顺时针方向围坐一圈，每个人 持有一个正整数密码。开始时任选一个正整数做为报数上限 m，从第一个人开 始顺时针方向自 1 起顺序报数，报到 m 是停止报数，报 m 的人出列，将他的密 码作为新的 m 值，从他的下一个人开始重新从 1 报数。如此下去，直到所有人 全部出列为止。令 n 最大值取 30。要求设计一个程序模拟此过程，求出出列编 . 可编辑范本 号序列。 算法描述 static void CreaL(NodeType *, const int); /运行约瑟夫环问题 static void PrintL(const NodeType *); /得到一个结点 s t a t i c N o d e T y p e * G . 可编辑范本 e t N o d e ( c o n s t i n t, c o n s t . 可编辑范本 i n t); / / / 测 试 链 表 是 否 为 空, 空 为 T r u e ， . 可编辑范本 非 空 为 F a l s e static unsigned EmptyL(const NodeType *); static void StatGame(NodeType *ppHead, int iCipher); 二、主要代码二、主要代码 #include #include #define Max 30 #define True 1 #define False 0 typedef struct NodeType int Num; int PassWord; struct NodeType *next; NodeType; static void CreaL(NodeType *, const int); /运行约瑟夫环问题 . 可编辑范本 static void PrintL(const NodeType *); /得到一个结点 s t a t i c N o d e T y p e * G e t N o d e ( c o n s t i n t, c o n . 可编辑范本 s t i n t); / / / 测 试 链 表 是 否 为 空, 空 为 T r u e ， 非 空 为 F a l s e static unsigned EmptyL(const NodeType *); static void StatGame(NodeType *ppHead, int iCipher); int main(void) . 可编辑范本 printf(本程序用于实现约瑟夫环操作nn); int n, m; NodeType *pHead=NULL; while(1) printf(输入总的人数 n(Max) printf(数字太大，请重新输入!n); continue; else break; CreaL( printf(n 打印出原始每个结点的序列号和密码n); PrintL(pHead); printf(n 最终每个结点退出的序列号和密码n); StatGame( return 0; static void CreaL(NodeType *ppHead, const int n) int i,iCipher; . 可编辑范本 NodeType *pNew, *pCur; for(i=1;inext=*ppHead; else pNew-next=pCur-next; pCur-next=pNew; pCur=pNew; printf(已完成结点初始化!n); static void StatGame(NodeType *ppHead, i