《线性表的操作与应用(算法与数据结构课程设计)》由会员分享,可在线阅读,更多相关《线性表的操作与应用(算法与数据结构课程设计)(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); ListTraverse(La); reverse(&La,a,5); ListTraverse(La); 程序3:报数游戏typedef struct LNodeElemType data;struct LNode *prior;struct LNode *ne