资源描述
习 题2.1选择题1、线性表的顺序存储结构是一种（ A ）的存储结构，线性表的链式存储结构是一种（ B ）的存储结构。A、随机存取 B、顺序存取 C、索引存取 D、散列存取2、对于一个线性，既要求能够进行较快的插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应该选择（ B ）。A、顺序存储方式 B、链式存储方式C、散列存储方式 D、索引存储方式3、已知，L是一个不带头结点的单链表，p指向其中的一个结点，选择合适的语句实现在p结点的后面插入s结点的操作（ B ）。A、p-next=s ; s-next=p-next ; B、s-next=p-next ; p-next=s ;C、p-next=s ; s-next=p ; D、s-next=p ; p-next=s ;4、单链表中各结点之间的地址（ C D ）。A、必须连续 B、部分地址必须连续C、不一定连续 D、连续与否都可以5、在一个长度为n的顺序表中向第i个元素（0inext= =L）。2.3读下面的程序段，画出执行过程的示意图及所完成的功能。1、 # define N 6void main ( ) ListSq L ; int A N ;int i , elem ;InitList(L); /初始化函数for ( int j=0; jN; j+)scanf(%d,&A j ) ; for ( int m=0; mdata=x;s=malloc(sizeof(Lnode);s-data=y; L-next=s; s-next=NULL;return L;功能：创建一个两个结点的不带头结点的单链表，两个结点的值分别为X和Y，L为单链表的头指针。2.4 算法题1、 编写在两种存储方式下，删除线性表中多余的值相同元素的算法。解：顺序存储方式下：void del(ListSq &L) int i=0; while (iL.len-1) int j=i+1; while (jL.len)if (L.ei= =L.ej) for (int k=j+1;knext; while (p-next!=NULL) Lnode *q=p-next; Lnode *r=p;while (q!=NULL)if (q-data= =p-data) r-next=q-next; free(q); q=r-next; else r=q; q=q-next; p=p-next;2、已知，顺序表的元素类型为整型，编写将该顺序表分成两个顺序表的算法，一个存放所的奇数元素，另一个存放所的偶数元素。解：void fenSq(ListSq L, ListSq &La, ListSq &Lb ) int j=0,k=0; for (int i=0;inext; int n=0; while(p!=L) n+; p=p-next; return n;4、编写删除有序单链表中元素值大于min并且小于max的全部元素的算法。如果给定的表是无序的，如何改写上面的算法。解：void del4(Lnode *L,Elemtype min , Elemtype max ) Lnode *q,*s,*p ; p=L-next; q=L; while (p!=NULL&p-datenext; if (p!=NULL)/表示存在大于min的结点，最后一个小于等于min的结点为q结点 while (p!=NULL&p-datenext; if (p!=NULL)/ 表示存在大于等于max的结点，既p结点 while (q-next!=p) /删除q的后继结点到p的前驱结点为止的所有结点 s=q-next; q-next=s-next; free(s); else s=q-next; q-next=NULL;/q以后的结点全部要删除 while (s!=NULL) p=s-next; free(s); s=p; 5、用顺序表来求集合的并集、交集和差集，也可以用链表来实现以上操作。（作为上机实践题目）# include typedef int Elemtype ; # define maxlen 100 # define N 30struct ListSqElemtype e maxlen ; int len ; ;/顺序表的创建算法void Create_Sq( ListSq &L , Elemtype A , int n ) int i ;for ( i=0 ; in ; i+ )L.ei =Ai; L.len=n ; /顺序表的输出算法void PrintList( ListSq L ) printf(当前集合为:n);for ( int i=0; iL.len; i+)printf(%dt , L.e i ) ; printf ( n ) ;void bingji(ListSq L1,ListSq L2,ListSq &L3)for(int k=0;kL1.len;k+)L3.ek=L1.ek;L3.len=L1.len;for (int i=0;iL2.len;i+)int j=0;while(j=L1.len)L3.eL3.len=L2.ei; L3.len+;void jiaoji(ListSq L1,ListSq L2,ListSq &L3)int k=0;for(int i=0;iL1.len;i+)int j=0;while(jL2.len)&(L1.ei!=L2.ej) j+;if(jL2.len) L3.ek+=L1.ei;L3.len=k;void chaji(ListSq L1,ListSq L2,ListSq &L3)int k=0;for(int i=0;iL1.len;i+)int j=0;while(j=L2.len) L3.ek+=L1.ei;for(int m=0;mL2.len;m+)int n=0;while(n=L1.len) L3.ek+=L2.em;L3.len=k;/主函数void main ( ) ListSq L1,L2,L3 ; L3.len=0;int A N ;int m,n,c;printf(请输入线性表L1的元素个数:n);scanf(%d,&m);printf(请输入线性表L1的元素:n);for ( int j=0; jm; j+)scanf(%d,&A j ) ; Create_Sq( L1 , A , m );PrintList( L1 ) ;printf(请输入线性表L2的元素个数:n);scanf(%d,&n);printf(请输入线性表L2的元素:n);for ( int w=0; wn; w+)scanf(%d,&A w ) ; Create_Sq( L2 , A , n );PrintList( L2 ) ;while(1)printf(请按提示进行输入：n);printf(实现两个集合的并集，请输入1：n); printf(实现两个集合的交集，请输入2：n);printf(实现两个集合的差集，请输入3：n);printf(退出，请输入4：n);scanf(%d,&c);switch(c)case 1: bingji(L1,L2,L3); PrintList( L3 ) ;break;case 2: jiaoji(L1,L2,L3); PrintList( L3 ) ;break;case 3: chaji(L1,L2,L3); PrintList( L3 );break; case 4:return;default: printf(输入有误！n);6、用循环单链表来实现约瑟夫问题。（作为上机实践题目）#include #include typedef struct Lnode int data ; Lnode *next ; *Link; void CreateList( Link &L , int n )/建立一个n个结点的循环单链表 int i ; Lnode *p,*s; s= ( Lnode * ) malloc ( sizeof ( Lnode ) ;s-data = 1 ;L=p=s;for ( i=2 ; idata = i ; p-next = s ; p=s ; p-next=L;void DeleteList( Link &L , Lnode * p, Lnode *q)/从循环单链表中删除结点pq-next=p-next ; / 修改结点的指针域free (p) ; / 释放p结点所占存储空间void josephus(Link &L,int s , int m ) Lnode *p,*q;p=L;for (int i=1;inext;q=p-next;while(q-next!=p) q=q-next;while(p-next!=p) for (int j=1;jnext; printf(%d,p-data);DeleteList( L , p , q);p=q-next;printf(%d ,p-data);printf(n);void main() Link L=NULL;int m,n,s;printf(请输入围圈人数、报数的开始位置和报数的上限n);scanf(%d,%d,%d,&n,&s,&m);if (m1000)|(n1000) printf(输入值m或n不合法！n);elseif (sn) printf(输入值s和n不合法！n);else CreateList( L,n );printf(n);josephus( L, s , m );7、某百货公司对仓库中的库存电视进行管理时，按其价格从低到高的次序构成一个循环单链表来保存信息，每个结点包含价格、数量和指针三个域。现新到m台价格为h的电视机，编写修改原信息链表的算法。（作为上机实践题目） # include # include struct Elemtypefloat jiage;int shuliang;struct LnodeElemtype data; struct Lnode * next ; ; /单链表的后插入创建算法void Rcreate( Lnode *L , Elemtype A , int n ) int i ; Lnode *p,*s;p=L;for ( i=0 ; idata = Ai; s-next=p-next; p-next=s ; p=s ; /单链表的输出算法void printList( Lnode *L ) Lnode *p ;if(L-next=L)printf(单链表为空！n);elsep=L-next;printf(当前仓库中库存的电视相关信息为:n);printf(价格tt数量n);while ( p-next!=L) printf (%ft , p-data.jiage) ;printf (%dn , p-data.shuliang) ;p=p-next;printf (%ft , p-data.jiage) ;printf (%dn , p-data.shuliang) ;void Insert( Lnode *L , Elemtype elem)Lnode *s;s=( Lnode * ) malloc (sizeof (Lnode) ; s-data=elem; if(L-next=L)s-next=L-next;L-next=s;elseLnode *p=L,*q =L-next; while (q!=L)&q-data.jiagedata.jiage) p=q;q=q-next ; s-next=q; p-next=s; /主函数void main( ) Lnode *L; int n;Elemtype A 50 ,elem;printf(请输入仓库中库存的电视的台数：n);scanf(%d,&n);printf(按价格从低到高输入电视信息：n);for ( int j=0; jnext=L; Rcreate( L , A , n ) ; printList( L ) ; printf(请输入新到的电视相关信息！n);printf(请输入价格:);scanf(%f,&elem.jiage);printf(请输入数量:);scanf(%d,&elem.shuliang);printf(n);Insert(L,elem);printList( L ) ;
展开阅读全文