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

学学 数据结构数据结构课程课程 实验报告实验报告 实实 验验 名名 称：称： 线性表基本操作的实现 实验室实验室( (中心中心) )： 学学 生生 信信 息：息： 专专 业业 班班 级：级： 指指 导导 教教 师师 ： 实验完成时间：实验完成时间： 2016 教师评阅意见： 签名： 年 月 日 实验成绩： 章: 线性表提升实验 2 实验一实验一 线性表基本操作的实现线性表基本操作的实现 一、实验目的一、实验目的 1.熟悉 C 语言的上机环境，进一步掌握 C 语言的结构特点。 2.掌握线性表的顺序存储结构的定义及 C 语言实现。 3.掌握线性表的链式存储结构单链表的定义及 C 语言实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构单链表中的各种基本操作。 二、实验内容及要求二、实验内容及要求 1.顺序线性表的建立、插入、删除及合并。 2.链式线性表的建立、插入、删除及连接。 三、实验设备及软件三、实验设备及软件 计算机、Microsoft Visual C+ 6.0 软件 四、设计方案（算法设计）四、设计方案（算法设计） 采用的数据结构 本程序顺序表的数据逻辑结构为线性结构，存储结构为顺序存储；链表的 数据逻辑结构依然为线性结构，存储结构为链式结构。 设计的主要思路 1.建立含 n 个数据元素的顺序表并输出该表中各元素的值及顺序表的长度，顺序 表的长度和元素由用户输入； 2.利用前面建立的顺序表，对顺序表进行插入、删除及合并操作； 3.建立一个带头结点的单链表，结点的值域为整型数据，链表的元素由用户输入； 章: 线性表提升实验 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 章: 线性表提升实验 4 #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); 章: 线性表提升实验 5 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); 章: 线性表提升实验 6 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(); 章: 线性表提升实验 7 void Init(sqlist printf(“请输入初始线性表长度：n=“); scanf(“%d“, printf(“请输入从 1 到%d 的各元素(字符)，例如:abcdefgn“,v.last); getchar(); for(i=0;iv.last+1) printf(“插入位置不合理!n“); return False; else if(v.last=Max) printf(“线性表已满!n“); return False; else for(i=v.last-1;i=loc-1;i-) 章: 线性表提升实验 8 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;j #include #include #define LEN sizeof(LNode) enum BOOLFalse,True; typedef struct node char data; struct node *next; LNode,*LinkList; 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 /两个链表的连接 void main() LinkList L; LinkList T; 章: 线性表提升实验 1 2 LinkList H; BOOL temp; int num,num1,loc,flag=1; char j,ch; printf(“本程序实现链式结构的线性表的操作。n“); printf(“可以进行插入，删除，定位，查找等操作。n“); printf(“请输入初始时链表长度:“); scanf(“%d“, 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“, switch(j) case 1:LPrint(L); break; case 2:printf(“请输入元素(一个字符)和要插入的位置:n“); printf(“格式:字符，位置；例如:a,3n“); scanf(“ %c,%d“, 章: 线性表提升实验 1 3 temp=LInsert(L,loc,ch); if(temp=False) printf(“插入失败!n“); else printf(“插入成功!n“); LPrint(L); break; case 3:printf(“请输入要删除的元素所在位置:“); scanf(“%d“, temp=LDele(L,loc,ch); if(temp=False) printf(“删除失败!n“); else printf(“成功删除了一个元素:%cn“,ch); LPrint(L); break; case 4:if(L-next=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“); 章: 线性表提升实验 1 4 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“); 章: 线性表提升实验 1 5 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; 章: 线性表提升实验 1 6 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 章: 线性表提升实验 1 7 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; 章: 线性表提升实验 1 8 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 9 六、测试结果及说明六、测试结果及说明 顺序表和链表基本操作的实现程序编译结果没错误和提醒，运行测试结果正 确，没有出现错误； 1、顺序表 2、链表 章: 线性表提升实验 2 0 七、实验体会七、实验体会 1.由于 C 语言的数组类型也有随机存取的特点，一维数组的机内表示就是顺序结 构。因此，可用 C 语言的一维数组实现线性表的顺序存储。 2.注意如何取到第 i 个元素，在插入过程中注意溢出情况以及数组的下标与位序 （顺序表中元素的次序）的区别。 3.单链表的结点结构除数据域外，还含有一个指针域。 章: 线性表提升实验 2 1 线性表提升实验线性表提升实验 （一）（一） 、实现顺序表元素的就地逆置、实现顺序表元素的就地逆置 一、设计方案一、设计方案 采用的数据结构 本程序采用的数据逻辑结构为线性结构，存储结构为顺序结构，算法的总 体功能是实现顺序表中元素的逆置。 设计的主要思路 由用户确定初始顺序表的长度并输入初始顺序表的元素，然后通过交换元 素的方法将初始表中的元素进行逆置处理、输出元素。 算法描述 status Initlist_Sq(Sqlist *L) /对顺序表 A 进行初始化 void input(Sqlist *A) /对一个线性表输入数据，是先输入长度，然后再输入数 据 void print(Sqlist *A) /对一个线性表进行输出 void invert(Sqlist *A) /实现一个顺序表的逆置 二、主要代码二、主要代码 #include 章: 线性表提升实验 2 2 #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“); 章: 线性表提升实验 2 3 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; 章: 线性表提升实验 2 4 void main() Sqlist A; /定义一个线性表 A Initlist_Sq( /对 A 进行初始化 input( /输入数据 printf(“输入的数据为:n“); print( printf(“逆序处理后为:n“); invert( /对线性表 A 逆置 print( /输出逆置以后的 A 三、测试结果及说明三、测试结果及说明 由用户输入初始顺序表的长度以及元素，然后通过程序实现初始顺序表的 逆置并输出结果，程序的测试结果完全正确，没有出现任何的错误。 章: 线性表提升实验 2 5 （二）（二） 、实现单循环链表的逆置、实现单循环链表的逆置 一、设计方案一、设计方案 采用的数据结构 本程序采用的数据逻辑结构为线性结构，存储结构为链式存储结构，算法 的总体功能是实现单循环链表中元素的逆置。 设计的主要思路 由用户确定初始链表的长度并输入初始链表的元素，然后通过过交换指针 的方法将初始表中的元素进行逆置处理、输出元素。 算法描述 void creatlinklist(linklist struct lnode *next; lnode ,*linklist; /建立一个空表，初始化，并对其进行输入值 void creatlinklist(linklist 章: 线性表提升实验 2 6 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; 章: 线性表提升实验 2 7 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) 章: 线性表提升实验 2 8 printf(“%d “,p-data); p=p-next; printf(“n“); return 0; 三、测试结果及说明三、测试结果及说明 由用户确定输入的元素个数为 6 个，依次输入 16、25、34、43、52、61， 逆置处理后输出的结果为 61、52、43、32、21、16，程序运行的结果正确，没 有出现错误。 （三）（三） 、解决约瑟夫环的出列问题、解决约瑟夫环的出列问题 一、设计方案一、设计方案 采用的数据结构 本程序采用的数据逻辑结构为线性结构，存储结构为链式存储结构，算法 的总体功能是实现约瑟夫环的出列问题。 设计的主要思路 章: 线性表提升实验 2 9 设编号为 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 *); /得到一个结点 static NodeType *GetNode(const int, const int); /测试链表是否为空, 空为 True，非空为 False 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 *); /得到一个结点 章: 线性表提升实验 3 0 static NodeType *GetNode(const int, const int); /测试链表是否为空, 空为 True，非空为 False 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“); 章: 线性表提升实验 3 1 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(