《线性表的操作与应用(算法与数据结构课程设计)》由会员分享，可在线阅读，更多相关《线性表的操作与应用(算法与数据结构课程设计)（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
