《lab02 线性表的操作与应用》由会员分享，可在线阅读，更多相关《lab02 线性表的操作与应用（7页珍藏版）》请在金锄头文库上搜索。
1、黔南民族师范学院数学系 算法与数据结构实验班级： 姓名： 学号： - 1 -Lab02线性表的操作与应用【实验目的和要求】1掌握线性表的顺序表示和链表表示下的基本运算；2能设计恰当的线性表解决具体问题。【实验内容】1创建顺序表示的线性表 palist(线性表中的结点为整数)，然后，1) 写一个插入算法，在 palist 所指顺序表中，下标为 p 的元素之后插入一个值为 x 的元素，返回插入成功与否的标志。2) 写一个删除算法, 在 palist 所指顺序表中，删除第一个值为 x 的元素，删除成功，返回所删除元素的下标，否则返回-1。3) 写一个置逆算法, 求 palist 所指顺序表的逆线性表
2、，逆线性表仍占用原线性表的空间。4) 写一个排序算法，将 palist 所指顺序表的元素按从小到大的顺序排序。2创建一个带头结点的单链表 llist(每结点数据域仅有一个整数)，然后，1) 写一个插入算法，在 llist 中，p 所指结点前面插入值为 x 的新结点，返回插入成功与否的标志。2) 写一个删除算法, 在 llist 中，删除下标为 i 的(第 i+1 个)结点，并返回删除成功与否的标志。3) 编写一个算法，删除单链表中值相同的多余结点，即若链表中有多个结点具有相的数据域值，只保留其中的一个结点，其余结点均从链表中删去，使得最后得到的链表中的所有结点的数据域都不相同。3. 设计一种用
3、单链表存储多项式的结构(每个结点存储一项的系数和指数，类型都为 int)，并编写一个产生多项式链表的函数和实现两个多项式相加和相乘的函数。4将本章介绍的两种 Josephus 问题的求解过程在计算中实现，实现时要求输出的不是整数，而是实际的人名。【实验仪器与软件】1CPU 主频在 1GHz 以上，内存在 512Mb 以上的 PC；2VC6.0，Word 2003 及以上版本。实验讲评：实验成绩： 黔南民族师范学院数学系 算法与数据结构实验班级： 姓名： 学号： - 2 -评阅教师：2012 年 月 日黔南民族师范学院数学系 算法与数据结构实验班级： 姓名： 学号： - 3 -Lab02线性表的
4、操作与应用一、顺序表示的线性表的基本操作1（1）创建空顺序表PSeqList createNullList_seq(int m )PSeqList palist = (PSeqList)malloc(sizeof(struct SeqList);if (palist!=NULL)palist-element = (DataType*)malloc(sizeof(DataType)*m);if (palist-element)palist-MAXNUM=m;palist -n = 0; return palist ;else free palist;printf(“Out of space!n”
5、); /* 存储分配失败 */return NULL;（2）判断线性表是否为空int isNullList_seq( PSeqList palist ) /*判别palist所指顺序表是否为空表。*/return ( palist-n = 0 );（3）在顺序表中求某元素的下标intlocate_seq(PSeqListpalist,DataTypex)int q;for ( q=0; qn ; q+) if ( palist-elementq = x) return q ;return -1;（4）顺序表的插入int intsertPre_seq(PSeqList palist,int p,
6、Datatype x)/*在palist所指顺序表中下标为p的元素之前插入元素x*/int q;if(palist-n=palist-MAXNUM)printf(overflow!n);黔南民族师范学院数学系 算法与数据结构实验班级： 姓名： 学号： - 4 -return 0;if(ppalist-n) /*不存在下标为 p 的元素*/printf(Not exist!n);return 0;for(q=palist-n-1;q=p;q-) /*插入位置及之后的元素均后移一个位置*/palist-elementq+1=palist-elementq;palist-elementp=x;pal
7、ist-n=palist-n+1;return 1;（5）顺序表的删除int deleteP_seq( PSeqList palist, int p ) /* 在 palist 所指顺序表中删除下标为的元素*/int q;if ( ppalist-n 1 ) /* 不存在下标为 p 的元素*/printf(“Not exist!n “);return 0 ;for(q=p; qn-1; q+) /* 被删除元素之后的元素均前移一个位置*/palist-elementq = palist-elementq+1;palist-n = palist-n -1;/* 元素个数减 1 */return
8、1 ;二、单链表的基本操作1 (1)创建空单链表LinkList createNullList_link(void)LinkList llist;llist=(LinkList)malloc(sizeof(struct Node );if (llist!=NULL) llist-link=NULL;else printf(“Out of space!n”); /*创建失败*/return llist;黔南民族师范学院数学系 算法与数据结构实验班级： 姓名： 学号： - 5 -(2)判断单链表是否为空int isNullList_link(LinkList llist)return (llist
9、-link=NULL);(3)在单链表中求某元素存储位置在带头结点的单链表 llist 中找第一个值为 x 的结点存储位置PNode locate_link(LinkList llist, DataType x)PNode p;if(llist=NULL) return NULL; /*找不到时返回空指针*/p=llist-link;while (p!=NULLreturn p;(4)单链表的插入在带头结点的单链表 llist 中下标为 p 的结点后插入值为 x 的新结点intinsertPost_link(LinkListllist, PNodep, DataTypex) PNodeq=(P
10、Node)malloc(sizeof(StructNode); /*申请新结点*/ if (q=NULL) printf(Out of Space!n) ;return 0;else q-info =x;q-link=p-link; p-link=q;return 1;(5)单链表的删除intdeleteV_link(LinkListllist, DataTypex) PNodep, q; p = llist;if(p=NULL) return 0 ;while( p-link != NULL & p-link-info != x )p = p-link; 黔南民族师范学院数学系 算法与数据结
11、构实验班级： 姓名： 学号： - 6 -if( p-link = NULL ) printf(”Not exist!n ”); return 0 ;else q = p-link; p-link = q-link; free( q ); return 1 ; 三、线性表的应用1用单链表表示整系数多项式，并实现两个多的相加和相乘运算。2. Josephus 问题求解Josephus 问题：设有 n 个人围坐在一个圆桌周围，现从第个人开始报数，数到第 m 的人出列，然后从出列的下一个人重新开始报数，数到第 m 的人又出列如此反复，直到所有的人全部出列为止，问：对于任意给定的 n,s 和 m，按出列
12、次序得到的 n 个人的序列。求解 Jostephus 问题的一般步骤如下：（1）首先利用线性表的一些运算，如，创建空线性表、插入元素等，构造Josephus 表。（2）从 Jposephus 表中第 s 个节点开始寻找、输出删除表中的第 m 个节点，然后再从该节点后的下一个节点开始寻找、输出和删除表中的第 m 个节点，重复此过程，直到 Josephus 表中的所有元素都被删除。以下采用循环链表模拟将初始序列看成一个整体的序列 1,2，3，n，为了处理方便，吧他们存储在一个循环单链表中。这种循环单链表结构中 josephus 问题的解主要由一下两个函数组成：（1）建立一个由头指针指示的 jose
13、phus 循环但链表，改算法主要由init_clink 实现。(2)从 jos_clist 所指的循环但链表中第 s 个节点开始寻找，反复输出和删除循环但链表中的第 m 个节点，该算法主要由 josephus_clist 实现，此算法的具体步骤如下：（1，建立由头指针 jos_clist 所指的循环单链表中第 s 个节点，放在指针变量 p 中，（2，从 p 所指节点开始计数，寻找第 m 个节点，并输出该节点的元素值；（3，删除改节点，并将该节点的下一个节点放在指针变量 p 中，转去执行（2， ，直到所有节点被删除为止。下面给出完整的 c 程序：#define FALSE 0#define TRUE 1typedef int DataType;struct Node;黔南民族师范学院数学系 算法与数据结构实验班级： 姓名： 学号： - 7 -typedef struc
