线性表的操作与应用(算法与数据结构课程设计).doc

《线性表的操作与应用(算法与数据结构课程设计).doc》由会员分享，可在线阅读，更多相关《线性表的操作与应用(算法与数据结构课程设计).doc（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、线性表的操作与应用一、问题描述线性表是一种常见的数据结构，它在实际中有着广泛的应用。本文要求实现线性表的就地逆置操作，并选择合适的存储结构，以同学录为例完成线性表的建立、查找、插入、删除、修改等操作来实现有关线的操作与应用。二、基本要求1、采用顺序和链式存储结构，分别实现线性表的就地逆置操作；2、采用双向链表，实现报数游戏：即n个人报数，先向n端报数，报到m出列。当报数到达表尾时，再向表尾向1端报数。如此反复，求出列顺序。3、选择合适的存储结构，以同学录为例完成线性表的建立、查找、插入、删除、修改等操作。三、测试数据1、就地逆置的数据为：1 3 5 7 92、报数游戏的数据为：10个人1到3报

2、数3、同学录得数据为：1)建立的数据: 学号 姓名 性别 101 lining nan228 zhougao nan335 fangqian nv 2) 查找的数据: 学号：228 3）插入的数据: 434 meixu nan 4）删除的数据: 学号：228 5) 修改的数据: 335 fangqian nan四、算法思想 1、就地逆置的算法思想：1)链式结构：从头到尾扫描单链表L，将头节点的next域置为NULL，将原链表的每个元素节点依次插入头节点。2)顺序结构：利用原有的存储空间，设置一个变量t，再利用循环表的两个方向向表中间进行表头表尾的交换。2、报数游戏的算法思想：在实现双向链表的基

3、本操作：建立，插入，删除后，用for循环从1到m报数，在循环中：1）用标志ch判断是向前或向后报数。2）当到达表头或表尾时，改变指针方向和报数方向。3）每当报数到3或只剩两个结点时，删除所报数在的结点，并将m置为-1。3、同学录的算法思想：选择链式结构作为个人信息的存储结构，用链表的基本操作：建立、插入、删除等算法，完成同学录的建立、查询、显示信息等功能，再用switch语句来判断想要实现的功能。五、模块划分 1、就地逆置 链式结构：1)void InitList(LinkList *L)，初始化链表。2)void DestroyList(LinkList *L)，销毁链表。3)void Cl

4、earList(LinkList *L)，清空链表。4)int ListEmpty(LinkList L)，判断链表是否为空。若为空，则返回1；反之，则返回0。5)void ListTraverse(LinkList L)，遍历链表并输出。6)void CreateList(LinkList *L, ElemType a, int n)，后接法建立顺序链表。 7)void reverse(SqList *L,ElemType a,int n), 逆置顺序表。8)main()，主函数。顺序结构：1)void InitList(SqList *L)，初始化链表。2)void DestroyList

5、(SqList *L)，销毁链表。3)void ClearList(SqList *L)，清空链表。4)int ListLength(SqList L)，求链表的长度。5)void ListTraverse(SqList L)，遍历链表并输出。6)void InputElem(SqList *L, ElemType a, int n)，由预置数组输入顺序表元素。7)void reverse(SqList *L,ElemType a,int n), 逆置顺序表。8）main()，主函数。2、报数游戏：1)void InitList(LinkList *L), 初始化链表。 2)void List

6、Traverse(LinkList L)，遍历链表。3)void CreateList(LinkList *L, ElemType a, int n)，建立双向链表 4) 4)void ysf(LinkList *L, int m)，约瑟夫函数。 5）void main() 主函数：用以个while循环和switch选择结构进行进行循环交互性操作。 3、同学录：1）void add(Stud *head) 来实现同学录的建立。 2)void search(Stud *head,int id)查询学生信息。3)void del(Stud *head,int id)删除学号为id的学生的信息。 4

7、)void rewrite(Stud *head,int id) 修改学号为id的学生的信息。 5)void print(Stud *head)显示建立好的同学录。 6）void main() 主函数：用以个while循环和switch选择结构进行进行循环交互性操作。六、数据结构/(ADT)1、链表的存储结构 ：typedef struct LNode ElemType data; struct LNode *next; LNode,*LinkList;2、顺序表的存储结构 */typedef struct ElemType *elem;int length; SqList;3、学生信息： t

8、ypedef struct Student int id; char name20; char sex20; struct Student *next;Stud;七、源程序#include malloc.h#include stdio.h#include string.h#include stdlib.h#include stdio.h#include stdlib.hTypedef int ElemType;程序1：链式存储结构，实现线性表的就地逆置typedef struct LNodeElemType data;struct LNode *next; LNode,*LinkList;vo

9、id InitList(LinkList *L) *L=(LinkList)malloc(sizeof(LNode); (*L)-next=NULL; void DestroyList(LinkList *L) LinkList p; while(*L!=NULL) p=*L; *L=(*L)-next; free(p); void ClearList(LinkList *L) LinkList p; p=(*L)-next; while(p!=NULL) (*L)-next=p-next; free(p); p=(*L)-next; int ListEmpty(LinkList L) if

10、(L-next=NULL) return 1; else return 0; void ListTraverse(LinkList L) LinkList p; printf(nList:t); p=L-next; while (p!=NULL) printf(%dt,p-data); p=p-next; void CreateList(LinkList *L, ElemType a, int n) LinkList p,new; int i; p=*L; for(i=0; idata=ai; p-next=new; p=p-next; p-next=NULL; void reverse(Li

11、nkList *L) LinkList p,q,r;p=(*L)-next; q=NULL; while (p!=NULL) r=p-next; p-next=q; q=p; p=r; (*L)-next=q;main() LinkList La; ElemType a=1,3,5,7,9; InitList(&La); CreateList(&La,a,5); ListTraverse(La); reverse(&La); ListTraverse(La); DestroyList(&La);程序2：顺序存储结构，实现线性表的就地逆置typedef struct ElemType *elem

12、;int length; SqList;void InitList(SqList *L) L-elem=(ElemType*)malloc(N*sizeof(ElemType); L-length=0; void DestroyList(SqList *L) free(L-elem); void ClearList(SqList *L) L-length=0; int ListLength(SqList L) return L.length; void ListTraverse(SqList L) int i; printf(nList:t); for(i=0; iL.length; i+)

13、printf(%dt,L.elemi); void InputElem(SqList *L, ElemType a, int n) int i; for(i=0; ielemi=ai; L-length=n; void reverse(SqList *L,ElemType a,int n) int i,t; for(i=0;ielemi=ai; for(i=0;ielemi; L-elemi=L-elemn-1-i; L-elemn-1-i=t;main() SqList La; ElemType a=1,3,5,7,9; InitList(&La); InputElem(&La,a,5);

14、ListTraverse(La); reverse(&La,a,5); ListTraverse(La); 程序3：报数游戏typedef struct LNodeElemType data;struct LNode *prior;struct LNode *next; LNode,*LinkList;void InitList(LinkList *L) *L=(LinkList)malloc(sizeof(LNode); (*L)-next=NULL; void ListTraverse(LinkList L) LinkList p; printf(nList:t); p=L-next; w

15、hile (p!=L) printf(%3d,p-data); p=p-next; printf(n);void CreateList(LinkList *L, ElemType a, int n) LinkList p,new; int i; p=*L; for(i=0; idata=ai;new-prior=p; new-next=*L; p-next=new;(*L)-prior=new;p=p-next; void ysf(LinkList *L, int m)LinkList p,q; int count;int ch; printf(输出约瑟夫序列：); ch=0; p=(*L);

16、 for(count=0;countnext;if(ch) p=p-prior;if(p=*L) if (!ch)p=p-prior;count-;ch=!ch;else if (ch)p=p-next;count-;ch=!ch;if(count=2 | p-next-next =p)if (!ch) q=p-prior;if (ch) q=p-next;printf(%3d,p-data);count=-1;p-prior-next=p-next;p-next-prior=p-prior;free(p);p=q;if(*L)-prior=*L & (*L)-next=*L) printf(

17、nn);return; main() LinkList La; ElemType a=1,2,3,4,5,6,7,8,9,10; InitList(&La); CreateList(&La,a,10); ListTraverse(La); ysf(&La,3);程序4：同学录typedef struct Student char id20; char name20; char sex20; struct Student *next;Stud;void add(Stud *head) Stud *p=(Stud*)malloc(sizeof(Stud); printf(请输入学号:);scanf

18、(%s,&p-id); printf(请输入姓名:);scanf(%s,&p-name); printf(请输入性别:);scanf(%s,&p-sex); p-next=head-next; head-next=p;void search(Stud *head,char *id)Stud *p=head-next; while(p!=NULL) if(strcmp(p-id,id)=0) printf(学号:%s,&p-id); printf(姓名:%s,&p-name);printf(性别:%s,&p-sex);break; else p=p-next;void del(Stud *hea

19、d,char *id)Stud *p=head; while(p-next!=NULL)if(strcmp(p-next-id,id)=0) Stud *q=p-next; p-next=q-next; free(q);break; else p=p-next;void rewrite(Stud *head,char *id)Stud *p=head; while(p-next!=NULL)if(strcmp(p-next-id,id)=0) Stud *q=p-next; p-next=q-next; free(q);break; else p=p-next;p=(Stud*)malloc(

20、sizeof(Stud); printf(请重新输入学号:);scanf(%s,&p-id); printf(请重新输入姓名:);scanf(%s,&p-name); printf(请重新输入性别:);scanf(%s,&p-sex); p-next=head-next;head-next=p;void print(Stud *head)Stud *p=head-next; printf(学号 姓名 性别 n);while(p!=NULL) printf(%-8s,&p-id); printf(%-15s,&p-name); printf(%-8sn,&p-sex); p=p-next;voi

21、d main()Stud *head=(Stud*)malloc(sizeof(Stud); head-next=NULL; while(1)int ch; printf(n1 增加学生 2 查询学生信息 3 删除学生 4 修改学生信息 5 显示信息n); scanf(%d,&ch); switch(ch)case 0:return; case 1:add(head);break; case 2:char id20; printf(输入查询学生的学号:); scanf(%s,&id); search(head,&id);break; case 3: char id20; printf(输入删除

22、学生的学号); scanf(%s,&id); del(head,&id);break; case 4: char id20; printf(输入修改学生的学号); scanf(%s,&id); rewrite(head,&id);break; case 5:print(head);break; default:printf(输入错误n); 八、测试情况程序的测试结果如下：程序1:程序2：程序3：程序4：1)输入3个数据后，显示结果如下: 2)查找的数据: 学号：228, 显示结果如下： 3)插入的数据: 434 meixu nan，显示结果如下： 4)删除的数据: 学号：228，显示结果如下：

23、5)修改的数据: 335 fangqian nan，显示结果如下： 九、参考文献 1、严蔚敏，数据结构 C语言，清华大学出版社。 2、谭浩强，c语言程序设计，清华大学出版社。小结顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。将表中元素一个接一个的存入一组连续的存储单元中，这种存储结构是顺序结构。顺序表的存储特点是：只要确定了起始位置，表中任一元素的地址都可以得到。单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始。循环链表和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。循

24、环链表的运算与单链表的运算基本一致。所不同的有以下几点：1、在建立一个循环链表时，必须使其最后一个结点的指针指向表头结点，而不是象单链表那样置为NULL。此种情况还使用于在最后一个结点后插入一个新的结点。2、在判断是否到表尾时，是判断该结点链域的值是否是表头结点，当链域值等于表头指针时，说明已到表尾。而非象单链表那样判断链域值是否为NULL。双向链表：双向链表中有两条方向不同的链，即每个结点中除next域存放后继结点地址外，还增加一个指向其直接前趋的指针域prior。它的特点是：（1）双链表由头指针head惟一确定的；（2）带头结点的双链表的某些运算变得方便；（3）将头结点和尾结点链接起来，为

25、双向循环链表。本次课程设计可看成三部分：第一部分是对线性表的逆置操作；第二部分是运用双向链表有前后两个指针的特点实现往复报数问题；第三部分是运用单链表来实现同学录得建立、修改、删除等操作。在整个实验中的第二部分有关双向链表的操作，让我头疼不已。由于它有两个指针域，使得一些基本操作：建立、插入、删除变得复杂多了。回头思考这中间所遇到的问题，最根本的原因是对链表的理解和认识还不够深刻，编程能力不足。通过本次课程设计，我受益很多。锻炼了我的逻辑思维，和调试程序的能力。而且还让我知道决定程序成功与否的往往不是程序的整体思路和整体算法，而是细小的书写错误，我在此次课程设计中深有体会。例如char name20，我写成了char name;导致我的程序运行的结果出错。此外，我体验了分工合作，集体编程和个人编程有很大不同，相互间独立而又紧密联系在一起，