第二章线性表
2.1描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。
并说明头指针和头结点的作用。
答：头指针是一个指针变量，里面存放的是链表中首结点的地址，并以此来标识一个链表。如链表H，链表L等，表示链表中第一个结点的地址存放在H、L中。头结点是附加在第一个元素结点之前的一个结点，头指针指向头结点。当该链表表示一个非空的线性表时，头结点的指针域指向第一个元素结点，为空表时，该指针域为空。
开始结点指第一个元素结点。
头指针的作用是用来惟一标识一个单链表。
头结点的作用有两个：一是使得对空表和非空表的处理得以统一。二是使得在链表的第一个位置上的操作和在其他位置上的操作一致，无需特殊处理。
2.2填空题
1、在顺序表中插入或删除一个元素，需要平均移动（表中一半）元素，具体移动的元素个数与（表长和该元素在表中的位置）有关。
2、顺序表中逻辑上相邻的元素的物理位置（必定）相邻。单链表中逻辑上相邻的元素的物理位置（不一定）相邻。
3、在单链表中，除了首元结点外，任一结点的存储位置由（其直接前驱结点的链域的值）指示。
4、在单链表中设置头结点的作用是（插入和删除元素不必进行特殊处理）。
2.3何时选用顺序表、何时选用链表作为线性表的存储结构为宜?
答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑：
1.基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。
2.基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在
表的首尾两端，则采用尾指针表示的单循环链表为宜。
2.10 Status DeleteK(SqList &a,int i,int k)//删除线性表a中第i个元素起的k个元素
{
if(i<1||k<0||i+k-1>a.length) return INFEASIBLE;
for(count=1;i+count-1<=a.length-k;count++) //注意循环结束的条件
a.elem[i+count-1]=a.elem[i+count+k-1];
a.length-=k;
return OK;
}//DeleteK
2.11设顺序表中的数据元素递增有序，试写一算法，将X插入到顺序表的适当位置上，以保持该表的有序性。
答：因已知顺序表L是递增有序表，所以只要从顺序表终端结点（设为i位置元素）开始向前寻找到第一个小于或等于x的元素位置i后插入该位置即可。
在寻找过程中，由于大于x的元素都应放在x之后，所以可边寻找，边后移元素，当找到第一个小于或等于x的元素位置i时，该位置也空出来了。
算法如下：
//顺序表存储结构如题2.7
void InsertIncreaseList( Seqlist *L , Datatype x )
{
int i;
if ( L->length>=ListSize)
Error(“overflow");
for ( i=L -> length ; i>0 && L->data[ i-1 ] > x ; i--)
L->data[ i ]=L->data[ i-1 ] ; // 比较并移动元素
L->data[ i ] =x;
L -> length++;
}
2.12 int ListComp(SqList A,SqList B)//比较字符表A和B,并用返回值表示结果,值为正,表示A>B;值为负,表示A { for(i=1;A.elem[i]||B.elem[i];i++) if(A.elem[i]!=B.elem[i]) return A.elem[i]-B.elem[i]; return 0; }//ListComp 2.13试写一算法在带头结点的单链表上实现线性表操作LOCATE（L，X）。Listnode *LocateNode(Linklist head,DataType key) { ListNode *p=head->next; While(p&&p->data!=key) p=p->next; return p; } 2.14试写一算法在带头结点的单链表结构上实现线性表操作规程LENGTH（L）。 #include"stdio.h" #define Maxsize 20 typedef int elemtype; typedef struct node{ elemtype data; struct node *next; }lnode; typedef lnode * linklist; int length_list(linklist head) {lnode *p=head; int j=0; if(!p){ printf("error");exit(0);} while(p->next) {p=p->next;j++;} return j; } 2.15已知L1和L2分别指向两个单链表的头结点，且已知其长度分别为m和n。试写一算法将这两个链表连接在一起，请分析你的算法的时间复杂度。 解： 分析： 由于要进行的是两单链表的连接，所以应找到放在前面的那张表的表尾结点，再将后表的开始结点链接到前表的终端结点后即可。该算法的主要时间消耗是用在寻找第一张表的终端尾结点上。这两张单链表的连接顺序无要求，并且已知两表的表长，则为了提高算法效率，可选表长小的单链表在前的方式连接。 具体算法如下： LinkList Link( LinkList L1 , LinkList L2，int m,int n ) {//将两个单链表连接在一起 ListNode *p , *q, *s ; //s指向短表的头结点,q指向长表的开始结点，回收长表头结点空间 if (m<=n) {s=L1;q=L2->next;free(L2);} else {s=L2;q=L1->next;free(L1);} p=s; while ( p->next ) p=p->next; //查找短表终端结点 p->next = q; //将长表的开始结点链接在短表终端结点后 return s; } 本算法的主要操作时间花费在查找短表的终端结点上，所以本算的法时间复 杂度为： O(min(m,n)) 2.16见书后答案. 2.17 Status Insert(LinkList &L,int i,int b)//在无头结点链表L的第i个元素之前插入元素b { p=L;q=(LinkList*)malloc(sizeof(LNode)); q.data=b; if(i==1) { q.next=p;L=q; //插入在链表头部 } else { while(--i>1) p=p->next; q->next=p->next;p->next=q; //插入在第i个元素的位置 } }//Insert 2.18 Status Delete(LinkList &L,int i)//在无头结点链表L中删除第i个元素 { if(i==1) L=L->next; //删除第一个元素 else { p=L; while(--i>1) p=p->next; p->next=p->next->next; //删除第i个元素 } }//Delete 2.19 Status Delete_Between(Linklist &L,int mink,int maxk)//删除元素递增排列的链表L中值大于mink且小于maxk的所有元素 { p=L; while(p->next->data<=mink) p=p->next; //p是最后一个不大于mink的元素 if(p->next) //如果还有比mink更大的元素 { q=p->next; while(q->data p->next=q; } }//Delete_Between 2.20 Status Delete_Equal(Linklist &L)//删除元素递增排列的链表L中所有值相同的元素 { p=L->next;q=p->next; //p,q指向相邻两元素 while(p->next) { if(p->data!=q->data) { p=p->next;q=p->next; //当相邻两元素不相等时,p,q都向后推一步 } else { while(q->data==p->data) { free(q); q=q->next; } p->next=q;p=q;q=p->next; //当相邻元素相等时删除多余元素 }//else }//while }//Delete_Equal 2.21试分别用顺序表作为存储结构，实现将线性表(a0,a1,...an-1)就地逆置的操作，所谓"就地"指辅助空间应为O(1)。 答： 要将该表逆置，可以将表中的开始结点与终端结点互换，第二个结点与倒数第二个结点互换，如此反复，就可将整个表逆置了。算法如下： // 顺序表结构定义同上题 void ReverseList( Seqlist *L) { DataType temp ; //设置临时空间用于存放data int i; for (i=0;i<=L->length/2;i++)//L->length/2为整除运算 { temp = L->data[i]; //交换数据 L -> data[ i ] = L -> data[ L -> length-1-i]; L -> data[ L -> length - 1 - i ] = temp; } } 2.22试写一算法，对单链表实现就地逆置。 答：链表： 分析： 可以用交换数据的方式来达到逆置的目的。但是由于是单链表，数据的存取不是随机的，因此算法效率太低。可以利用指针改指来达到表逆置的目的。具体情况入下： (1)当链表为空表或只有一个结点时，该链表的逆置链表与原表相同。 (2)当链表含2个以上结点时，可将该链表处理成只含第一结点的带头结点链表和一个无头结点的包含该链表剩余结点的链表。然后，将该无头结点链表中的所有结点顺着链表指针，由前往后将每个结点依次从无头结点链表中摘下，作为第一个结点插入到带头结点链表中。这样就可以得到逆置的链表。算法是这样的： 结点结构定义如下： typedef char DataType; //假设结点的数据域类型的字符 typedef struct node{ //结点类型定义 DataType data; //结点的数据域 struct node *next;//结点的指针域 }ListNode; typedef ListNode *LinkList; ListNode *p; LinkList head; LinkList ReverseList( LinkList head ) {// 将head 所指的单链表(带头结点)逆置 ListNode *p ,*q ;//设置两个临时指针变量 if( head->next && head->next->next) { //当链表不是空表或单结点时 p=head->next; q=p->next; p -> next=NULL; //将开始结点变成终端结点 while (q) { //每次循环将后一个结点变成开始结点 p=q; q=q->next ; p->next = head-> next ; head->next = p; } return head; } return head; //如是空表或单结点表，直接返回head } 2.23 void merge1(LinkList &A,LinkList &B,LinkList &C)//把链表A和B合并为C,A和B的元素间隔排列,且使用原存储空间 { p=A->next;q=B->next;C=A; while(p&&q) { s=p->next;p->next=q; //将B的元素插入 if(s) { t=q->next;q->next=s; //如A非空,将A的元素插入 } p=s;q=t; }//while }//merge1 2.24假设有两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法将A和B表归并成一个按元素值递减有序（即非递增有序，允许表中含有相同的元素）排列的线性有C，并要求利用原表（即A表和B表）的结点空间构造C表。 解： void reverse_merge(LinkList &A,LinkList &B,LinkList &C)//把元素递增排列的链表A和B合并为C,且C中元素递减排列,使用原空间 { pa=A->next;pb=B->next;pre=NULL; //pa和pb分别指向A,B的当前元素 while(pa||pb) { if(pa->data { pc=pa;q=pa->next;pa->next=pre;pa=q; //将A的元素插入新表} else { pc=pb;q=pb->next;pb->next=pre;pb=q; //将B的元素插入新表} pre=pc; } C=A;A->next=pc; //构造新表头 }//reverse_merge 分析:本算法的思想是,按从小到大的顺序依次把A和B的元素插入新表的头部pc处,最后处理A或B的剩余元素. 2.25 void SqList_Intersect(SqList A,SqList B,SqList &C)//求元素递增排列的线性表A和B的元素的交集并存入C中 { i=1;j=1;k=0; while(A.elem[i]&&B.elem[j]) { if(A.elem[i] if(A.elem[i]>B.elem[j]) j++; if(A.elem[i]==B.elem[j]) { C.elem[++k]=A.elem[i]; //当发现了一个在A,B中都存在的元素, i++;j++; //就添加到C中 } }//while }//SqList_Intersect 2.26 void LinkList_Intersect(LinkList A,LinkList B,LinkList &C)//在链表结构上重做上题 { p=A->next;q=B->next; pc=(LNode*)malloc(sizeof(LNode)); while(p&&q) { if(p->data else if(p->data>q->data) q=q->next; else { s=(LNode*)malloc(sizeof(LNode)); s->data=p->data; pc->next=s;pc=s; p=p->next;q=q->next; } }//while C=pc; }//LinkList_Intersect 2.27 void SqList_Intersect_True(SqList &A,SqList B)//求元素递增排列的线性表A和B 的元素的交集并存回A中 { i=1;j=1;k=0; while(A.elem[i]&&B.elem[j]) { if(A.elem[i] else if(A.elem[i]>B.elem[j]) j++; else if(A.elem[i]!=A.elem[k]) { A.elem[++k]=A.elem[i]; //当发现了一个在A,B中都存在的元素 i++;j++; //且C中没有,就添加到C中 } }//while while(A.elem[k]) A.elem[k++]=0; }//SqList_Intersect_True 2.28 void LinkList_Intersect_True(LinkList &A,LinkList B)//在链表结构上重做上题{ p=A->next;q=B->next;pc=A; while(p&&q) { if(p->data else if(p->data>q->data) q=q->next; else if(p->data!=pc->data) { pc=pc->next; pc->data=p->data; p=p->next;q=q->next; } }//while }//LinkList_Intersect_True 2.29 void SqList_Intersect_Delete(SqList &A,SqList B,SqList C) { i=0;j=0;k=0;m=0; //i指示A中元素原来的位置,m为移动后的位置 while(i { if(B.elem[j] else if(B.elem[j]>C.elem[k]) k++; else { same=B.elem[j]; //找到了相同元素same while(B.elem[j]==same) j++; while(C.elem[k]==same) k++; //j,k后移到新的元素 while(i A.elem[m++]=A.elem[i++]; //需保留的元素移动到新位置 while(i } }//while while(i A.elem[m++]=A.elem[i++]; //A的剩余元素重新存储。 A.length=m; }// SqList_Intersect_Delete 分析:先从B和C中找出共有元素,记为same,再在A中从当前位置开始, 凡小于same的 元素均保留(存到新的位置),等于same的就跳过,到大于same时就再找下一个same. 2.30 void LinkList_Intersect_Delete(LinkList &A,LinkList B,LinkList C)//在链表结构上重做上题 { p=B->next;q=C->next;r=A-next; while(p&&q&&r) { if(p->data else if(p->data>q->data) q=q->next; else { u=p->data; //确定待删除元素u while(r->next->data if(r->next->data==u) { s=r->next; while(s->data==u) { t=s;s=s->next;free(t); //确定第一个大于u的元素指针s }//while r->next=s; //删除r和s之间的元素 }//if while(p->data=u) p=p->next; while(q->data=u) q=q->next; }//else }//while }//LinkList_Intersect_Delete 2.31假设在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的直接前趋结点。 解： 已知指向这个结点的指针是*s，那么要删除这个结点的直接前趋结点，就只要找到一个结点，它的指针域是指向*s的直接前趋，然后用后删结点法，将结点*s的直接前趋结点删除即可。 算法如下： void DeleteNode( ListNode *s) {//删除单循环链表中指定结点的直接前趋结点 ListNode *p, *q; p=s; while( p->next->next!=s) p=p->next; //删除结点 q=p->next; p->next=q->next; free(p); //释放空间 } 注意： 若单循环链表的长度等于1，则只要把表删空即可。 2.32已知有一个单向循环链表，其每个结点中含三个域：prior、data和next，其中data为数据域，next为指向后继结点的指针域，prior也为指针域，但它的值为空，试编写算法将此单向循环链表改为双向循环链表，即使prior成为指向前驱结点的指针域。 Status DuLNode_Pre(DuLinkList &L)//完成双向循环链表结点的pre域 { for(p=L;!p->next->pre;p=p->next) p->next->pre=p; return OK; }//DuLNode_Pre 2.33已知由单链表表示的线性表中，含有三类字符的数据元素(如：字母字符、数字字符和其它字符)，试编写算法构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。 解： 要解决这样的问题，只要新建三个头结点，然后在原来的单链表中依次查询， 找到一类字符结点时，就摘下此结点链接到相应头结点指明的新链表中就是了。 算法如下： //设已建立三个带头结点的空循环链表A,B,C且A、B、C分别是尾指针. void DivideList( LinkList L, LinkList A, LinkList B, LinkList C) { ListNode *p=L->next, *q; while ( p ) { if ( p->data>='a' &&p->data<='z'|| p->data>='A' &&p->data<='Z') { q=p->next; p=p->next;//指向下一结点 q->next=A->next;//将字母结点链到A表中 A->next=q;A=q; } else if( p->data>='0' && p->data<='9') { // 分出数字结点 q=p->next; p=p->next;//指向下一结点 q->next=B->next;//将数字结点链到B表中 B->next=q;B=q; } else { //分出其他字符结点 q=p->next; p=p->next;//指向下一结点 q->next=C->next;//将其他结点链到C表中 C->next=q;C=q; } } } 2.34 void Print_XorLinkedList(XorLinkedList L)//从左向右输出异或链表的元素值{ p=L.left;pre=NULL; while(p) { printf("%d",p->data); q=XorP(p->LRPtr,pre); pre=p;p=q; //任何一个结点的LRPtr域值与其左结点指针进行异或运算即得到其右结点指针 } }//Print_XorLinkedList 2.35 Status Insert_XorLinkedList(XorLinkedList &L,int x,int i)//在异或链表L的第i个元素前插入元素x { p=L.left;pre=NULL; r=(XorNode*)malloc(sizeof(XorNode)); r->data=x; if(i==1) //当插入点在最左边的情况 { p->LRPtr=XorP(p.LRPtr,r); r->LRPtr=p; L.left=r; return OK; } j=1;q=p->LRPtr; //当插入点在中间的情况 while(++j { q=XorP(p->LRPtr,pre); pre=p;p=q; }//while //在p,q两结点之间插入 if(!q) return INFEASIBLE; //i不可以超过表长 p->LRPtr=XorP(XorP(p->LRPtr,q),r); q->LRPtr=XorP(XorP(q->LRPtr,p),r); r->LRPtr=XorP(p,q); //修改指针 return OK; }//Insert_XorLinkedList 2.36 Status Delete_XorLinkedList(XorlinkedList &L,int i)//删除异或链表L的第i个元素{ p=L.left;pre=NULL; if(i==1) //删除最左结点的情况 { q=p->LRPtr; q->LRPtr=XorP(q->LRPtr,p); L.left=q;free(p); return OK; } j=1;q=p->LRPtr; while(++j { q=XorP(p->LRPtr,pre); pre=p;p=q; }//while //找到待删结点q if(!q) return INFEASIBLE; //i不可以超过表长 if(L.right==q) //q为最右结点的情况 { p->LRPtr=XorP(p->LRPtr,q); L.right=p;free(q); return OK; } r=XorP(q->LRPtr,p); //q为中间结点的情况,此时p,r分别为其左右结点 p->LRPtr=XorP(XorP(p->LRPtr,q),r); r->LRPtr=XorP(XorP(r->LRPtr,q),p); //修改指针 free(q); return OK; }//Delete_XorLinkedList 2.37 void OEReform(DuLinkedList &L)//按1,3,5,...4,2的顺序重排双向循环链表L中的所有结点 { p=L.next; while(p->next!=L&&p->next->next!=L) { p->next=p->next->next; p=p->next; } //此时p指向最后一个奇数结点 if(p->next==L) p->next=L->pre->pre; else p->next=l->pre; p=p->next; //此时p指向最后一个偶数结点 while(p->pre->pre!=L) { p->next=p->pre->pre; p=p->next; } p->next=L; //按题目要求调整了next链的结构,此时pre链仍为原状 for(p=L;p->next!=L;p=p->next) p->next->pre=p; L->pre=p; //调整pre链的结构,同2.32方法 }//OEReform 分析:next链和pre链的调整只能分开进行.如同时进行调整的话,必须使用堆栈保存偶数结点的指针,否则将会破坏链表结构,造成结点丢失. 2.38 DuLNode * Locate_DuList(DuLinkedList &L,int x)//带freq域的双向循环链表上的查找 { p=L.next; while(p.data!=x&&p!=L) p=p->next; if(p==L) return NULL; //没找到 p->freq++;q=p->pre; while(q->freq<=p->freq) q=q->pre; //查找插入位置 if(q!=p->pre) { p->pre->next=p->next;p->next->pre=p->pre; q->next->pre=p;p->next=q->next; q->next=p;p->pre=q; //调整位置 } return p; }//Locate_DuList 2.39 float GetValue_SqPoly(SqPoly P,int x0)//求升幂顺序存储的稀疏多项式的值 { PolyTerm *q; 实验一线性表的基本操作 一、实验目的与基本要求 1．掌握数据结构中的一些基本概念。数据、数据项、数据元素、数据类型和数据结构，以及它们之间的关系。 2．了解数据的逻辑结构和数据的存储结构之间的区别与联系；数据的运算与数据的逻辑结构的关系。 3．掌握顺序表和链表的基本操作：插入、删除、查找以及表的合并等运算。4．掌握运用C语言上机调试线性表的基本方法。 二、实验条件 1．硬件：一台微机 2．软件：操作系统和C语言系统 三、实验方法 确定存储结构后，上机调试实现线性表的基本运算。 四、实验内容 1．建立顺序表，基本操作包括：初始化，建立一个顺序存储的链表，输出顺序表，判断是否为空，取表中第i个元素，定位函数（返回第一个与x相等的元素位置），插入，删除。 2．建立单链表，基本操作包括：初始化，建立一个链式存储的链表，输出顺序表，判断是否为空，取表中第i个元素，定位函数（返回第一个与x相等的元素位置），插入，删除。 3．假设有两个按数据元素值非递减有序排列的线性表A和B，均以顺序表作为存储结构。编写算法将A表和B表归并成一个按元素值非递增有序（允许值相同）排列的线性表C。（可以利用将B中元素插入A中，或新建C表）4．假设有两个按数据元素值非递减有序排列的线性表A和B，均以单链表作为存储结构。编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许值相同）排列的线性表C。 五、附源程序及算法程序流程图 1.源程序 （1）源程序(实验要求1和3) #include 数据结构练习题1 指导老师：常璐璐 姓名：邢莉彬 学校：滨州学院 院系：信息工程学院软件技术 填空题 1. 对于一个n个结点的单链表，在表头插入元素的时间复杂度为_____O(1)_____，在表尾插入元素的时间复杂度为_____O(n)_____。 2. 删除非空线性链表中由q所指的链结点（其直接前驱结点由r指出）的动作时执行语句___r->link=q->link_______和______free(q)____。 结点结构为 typedef struct Node{ int value; node * link; }node; 3. 非空线性链表中，若要在由p所指的链结点后面插入新结点q，则应执行语句____ q->link=p->link;______和_____ p->link=q;_____。 结点结构为 typedef struct Node{ int value; node* link; }node; 4. 线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_____(n-1)/2_____。 5. 在一个长度为n的顺序表中第i个元素（1≤i≤n）之前插入一个元素时，需向后移动_____ n-i+1_____ 个元素。 6.在具有n个链结点的链表中查找一个链结点的时间复杂度为O(_______n___)。 7. 线性表中的插入、删除操作，在顺序存储方式下平均移动近一半的元素，时间复杂度为_____O（n）_____；而在链式存储方式下，插入和删除操作的时间复杂度都是____O(1)______ 。 8. 若某线性表采用顺序存储结构，每个元素占4个存储单元，首地址为100，则第10个元素的存储地址为____136______。 选择题 1. 对于一个带头结点的单链表，头指针为head，判定该表为空的条件是________B__。 A. head==NULL B. head->next==NULL C. head->next==head D. head!=NULL 2. 将长度为m的线性链表链接在长度为n的线性链表之后的过程的时间复杂度若采用大O形式表示，则应该是______B____。 A．O(m) B．O(n) C．O(m+n) D．O(m-n) 3.在包含1000个数据元素的线性表中，实现如下4个操作所需要的执行时间最长的是______A____ 。 《数据结构》第二章习题参考答案 一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打“×”） 1、顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。( × ) 2、链表中的头结点仅起到标识的作用。( × ) 3、所谓静态链表就是一直不发生变化的链表。( × ) 4、线性表的特点是每个元素都有一个前驱和一个后继。( × ) 5、在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。（×） 6、线性表就是顺序存储的表。（×） 7、课本P84 2.4题 （1）√（2）×（3）×（4）×（5）√（6）×（7）×（8）√ （9）×（10）×（11）√（12）√ 二、单项选择题 1、下面关于线性表的叙述中，错误的是哪一个？（ B ） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 2、链表不具有的特点是（ B ） A．插入、删除不需要移动元素B．可随机访问任一元素 C．不必事先估计存储空间D．所需空间与线性长度成正比 3、(1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。 (2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。 (3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。 以上错误的是（ B ） A．（1），（2）B．（1）C．（1），（2），(3) D.（2） 4、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（B）A．p->link =s; s-> link =p-> link; B．s-> link =p-> link; p-> link =s; C．p-> link =s; p-> link =s-> link; D．p-> link =s-> link; p-> link =s; 5、若某线性表最常用的操作是取任一指定序号的元素及其前驱，则利用（C）存储方式最节省时间。 A．单链表B．双链表C．顺序表D．带头结点的双循环链表6、对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ C ）。A．O(n)，O(n) B. O(n)，O(1) C. O(1)，O(n) D. O(1)，O(1) 7、在一个以 h 为头的单循环链中，p 指针指向链尾的条件是（ A ） A. p->next=h B. p->next=NULL C. p->next->next=h D. p->data=-1 三、填空题 第二章线性表练习题 一、选择题 1.线性表是具有n个的有限序列。 A、表元素 B、字符 C、数据元素 D、数据项 E、信息项 2.线性表的静态链表存储结构与顺序存储结构相比优点是。 A、所有的操作算法实现简单 B、便于随机存储 C、便于插入和删除 D、便于利用零散的存储器空间 3.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度为。 A、O(log2n) B、O(1) C、O(n) D、O(n2) 4.（1）静态链表既有顺序存储的特点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关； （2）静态链表中能容纳元素个数的最大数在定义时就确定了，以后不能增加；（3）静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。 以上错误的是。 A、（1）、（2） B、（1） C、（1）、（2）、（3） D、（2） 6.在双向链表存储结构中，删除p所指的结点时须修改指针。 A、p－＞next－＞prior=p－＞prior; p－＞prior－＞next=p－＞next; B、p－＞next=p－＞next－＞next;p－＞next－＞prior=p; C、p－＞prior－＞next=p;p－＞prior=p－＞prior－＞prior; D、p－＞prior=p－＞next－＞next;p－＞next=p－＞prior－＞prior; 7.在双向循环链表中，在P指针所指的结点后插入q所指向的新结点，其修改指针的操作是。 A、p－＞next=q; q－＞prior=p;p－＞next－＞prior=q;q－＞next=q; B、p－＞next=q;p－＞next－＞prior=q;q－＞prior=p;q－＞next=p－＞next; C、q－＞prior=p; q－＞next=p－＞next; p－＞next－＞prior=q; p－＞next=q; D、q－＞next=p－＞next;q－＞prior=p;p－＞next=q;p－＞next=q; 8.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是。 A、 n b、2n－1 c、2n d、n－1 9.在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动个元素。 A、n－i B、n－i+1 C、n－i－1 D、i 10.线性表L=(a1，a2,……an)，下列说法正确的是。 A、每个元素有有一个直接前驱和一个直接后继 B、线性表中至少有一个元素 C、表中诸元素的排列必须是由小到大或由大到小。 D、除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。 11.对单链表表示法，以下说法错误的是。 A、数据域用于存储线性表的一个数据元素 B、指针域(或链域)用于存放一指向本结点所含数据元素的直接后继所在结点的指针 C、所有数据通过指针的链接而组织成单链表 D、NULL称为空指针，它不指向任何结点只起标志作用 实验1 线性表的基本操作 一、需求分析 目的： 掌握线性表运算与存储概念，并对线性表进行基本操作。 1.初始化线性表； 2.向链表中特定位置插入数据； 3.删除链表中特定的数据； 4.查找链表中的容； 5.销毁单链表释放空间； 二、概要设计 ●基础题 主要函数： 初始化线性表InitList（List* L，int ms） 向顺序表指定位置插入元素InsertList（List* L，int item，int rc）删除指定元素值的顺序表记录DeleteList1(List* L,int item) 删除指定位置的顺序表记录 DeleteList2（List* L,int rc） 查找顺序表中的元素 FindList（List L，int item） 输出顺序表元素OutputList（List L） 实验步骤： 1，初始化顺序表 2，调用插入函数 3，在顺序表中查找指定的元素 4，在顺序表中删除指定的元素 5，在顺序表中删除指定位置的元素 6，遍历并输出顺序表 ●提高题 要求以较高的效率实现删除线性表中元素值在x到y（x和y自定义）之间的所有元素 方法： 按顺序取出元素并与x、y比较，若小于x且大于y，则存进新表中。 编程实现将两个有序的线性表进行合并，要求同样的数据元素只出现一次。 方法： 分别按顺序取出L1，L2的元素并进行比较，若相等则将L1元素放进L中，否则将L 1，L2元素按顺序放进L。 本程序主要包含7个函数 主函数main() 初始化线性表InitList（List* L，int ms） 向顺序表指定位置插入元素InsertList（List* L，int item，int rc）删除指定元素值的顺序表记录DeleteList1(List* L,int item) 删除指定位置的顺序表记录 DeleteList2（List* L,int rc） 查找顺序表中的元素 FindList（List L，int item） 输出顺序表元素OutputList（List L） 提高题的程序 void Combine(List* L1,List* L2,List* L) void DeleteList3(List* L,int x,int y) 二、详细设计 初始化线性表InitList（List* L，int ms） void InitList(List* L,int ms) { L->list=(int*)malloc(LIST_INIT_SIZE*sizeof(int)); L->size=0; L->MAXSIZE=LIST_INIT_SIZE; 第2章线性表 一选择题 1．下述哪一条是顺序存储结构的优点？（） A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示 2．下面关于线性表的叙述中，错误的是哪一个？（） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 3．线性表是具有n个（）的有限序列（n>0）。 A．表元素 B．字符 C．数据元素 D．数据项 E．信息项 4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。 A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表 5. 链表不具有的特点是（） A．插入、删除不需要移动元素 B．可随机访问任一元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比 6. 下面的叙述不正确的是（） A．线性表在链式存储时，查找第i个元素的时间同i的值成正比 B. 线性表在链式存储时，查找第i个元素的时间同i的值无关 C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比 D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关 7. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1<=i<=n+1)。 A. O(0) B. O(1) C. O(n) D. O(n2) 8. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（）。 A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 9．线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（）A．O（i） B．O（1） C．O（n） D．O（i-1） 10．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（）。 A．p->next=s;s->next=p->next; B． s->next=p->next;p->next=s; C．p->next=s;p->next=s->next; D． p->next=s->next;p->next=s; 11．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL 二、判断 1. 链表中的头结点仅起到标识的作用。( ) 2. 顺序存储结构的主要缺点是不利于插入或删除操作。( ) 3．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。( ) 4．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。( ) 5. 对任何数据结构链式存储结构一定优于顺序存储结构。( ) 6．集合与线性表的区别在于是否按关键字排序。( ) 7. 线性表的特点是每个元素都有一个前驱和一个后继。( ) 第二章习题 1.描述以下三个概念的区别：头指针，头结点，首元素结点。 2.填空： （1）在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。 （2）在顺序表中，逻辑上相邻的元素，其物理位置相邻。在单链表中，逻辑上相邻的元素，其物理位置相邻。 （3）在带头结点的非空单链表中，头结点的存储位置由指示，首元素结点的存储位置由指示，除首元素结点外，其它任一元素结点的存储位置由指示。3．已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。 a. 在P结点后插入S结点的语句序列是：。 b. 在P结点前插入S结点的语句序列是：。 c. 在表首插入S结点的语句序列是：。 d. 在表尾插入S结点的语句序列是：。 供选择的语句有： （1）P->next=S; （2）P->next= P->next->next; （3）P->next= S->next; （4）S->next= P->next; （5）S->next= L; （6）S->next= NULL; （7）Q= P; （8）while(P->next!=Q) P=P->next; （9）while(P->next!=NULL) P=P->next; （10）P= Q; （11）P= L; （12）L= S; （13）L= P; 4.设线性表存于a(1:arrsize)的前elenum个分量中且递增有序。试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 5.写一算法，从顺序表中删除自第i个元素开始的k个元素。 6.已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。 7.试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1, a2..., an）逆置为（an, an-1,..., a1）。 （1）以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。 （2）以单链表作存储结构。 8.假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表（即A 表和B表的）结点空间存放表C。 第二章线性表 2.1 填空题 (1)一半插入或删除的位置 (2)静态动态 (3)一定不一定 (4)头指针头结点的next 前一个元素的next 2.2 选择题 (1)A (2) DA GKHDA EL IAF IFA(IDA) (3)D (4)D (5) D 2.3 头指针：在带头结点的链表中，头指针存储头结点的地址；在不带头结点的链表中，头指针存放第一个元素结点的地址； 头结点：为了操作方便，在第一个元素结点前申请一个结点，其指针域存放第一个元素结点的地址，数据域可以什么都不放； 首元素结点：第一个元素的结点。 2.4已知顺序表L递增有序，写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 void InserList(SeqList *L,ElemType x) { int i=L->last; if(L->last>=MAXSIZE-1) return FALSE; //顺序表已满 while(i>=0 && L->elem[i]>x) { L->elem[i+1]=L->elem[i]; i--; } L->elem[i+1]=x; L->last++; } 2.5 删除顺序表中从i开始的k个元素 int DelList(SeqList *L,int i,int k) { int j,l; if(i<=0||i>L->last) {printf("The Initial Position is Error!"); return 0;} if(k<=0) return 1; /*No Need to Delete*/ if(i+k-2>=L->last) L->last=L->last-k; /*modify the length*/ 北京邮电大学电信工程学院 数据结构实验报告 实验名称：实验1——线性表 学生姓名： 班级： 班内序号： 学号： 日期： 1．实验要求 1、实验目的：熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法 学习指针、模板类、异常处理的使用 掌握线性表的操作的实现方法 学习使用线性表解决实际问题的能力 2、实验内容： 题目1： 线性表的基本功能： 1、构造：使用头插法、尾插法两种方法 2、插入：要求建立的链表按照关键字从小到大有序 3、删除 4、查找 5、获取链表长度 6、销毁 7、其他：可自行定义 编写测试main()函数测试线性表的正确性。 2. 程序分析 2.1 存储结构 带头结点的单链表 2.2 关键算法分析 1.头插法 a、伪代码实现：在堆中建立新结点 将x写入到新结点的数据域 修改新结点的指针域 修改头结点的指针域,将新结点加入链表中b、代码实现： Linklist::Linklist(int a[],int n)//头插法 {front=new Node; front->next=NULL; for(int i=n-1;i>=0;i--) {Node*s=new Node; s->data=a[i]; s->next=front->next; front->next=s; } } 2、尾插法 a、伪代码实现：a.在堆中建立新结点 b.将a[i]写入到新结点的数据域 c.将新结点加入到链表中 d.修改修改尾指针 b、代码实现: Linklist::Linklist(int a[],int n,int m)//尾插法 {front=new Node; Node*r=front; for(int i=0;i 第二章习题 1. 描述以下三个概念的区别：头指针，头结点，首元素结点。 2. 填空： （1）在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。 （2）在顺序表中，逻辑上相邻的元素，其物理位置相邻。在单链表中，逻辑上相邻的元素，其物理位置相邻。 （3）在带头结点的非空单链表中，头结点的存储位置由指示，首元素结点的存储位置由指示，除首元素结点外，其它任一元素结点的存储位置由指示。3．已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。 a. 在P结点后插入S结点的语句序列是：。 b. 在P结点前插入S结点的语句序列是：。 c. 在表首插入S结点的语句序列是：。 d. 在表尾插入S结点的语句序列是：。 供选择的语句有： （1）P->next=S; （2）P->next= P->next->next; （3）P->next= S->next; （4）S->next= P->next; （5）S->next= L; （6）S->next= NULL; （7）Q= P; （8）while(P->next!=Q) P=P->next; （9）while(P->next!=NULL) P=P->next; （10）P= Q; （11）P= L; （12）L= S; （13）L= P; 4. 设线性表存于a(1:arrsize)的前elenum个分量中且递增有序。试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 5. 写一算法，从顺序表中删除自第i个元素开始的k个元素。 6. 已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。 7. 试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1, a2..., an）逆置为（an, an-1,..., a1）。 （1）以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。 （2）以单链表作存储结构。 8. 假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表（即A 表和B表的）结点空间存放表C。 《数据结构》实验报告 专业： 学号： 姓名： 实验二线性表 【实验目的】 1.熟悉VC环境，学习如何使用C语言实现线性表的两种存储结构。 2.通过编程、上机调试，进一步理解线性表的基本概念，东运用C语言实现线性表基本操作。 3.熟练掌握线性表的综合应用问题。 【实验内容】 1、一个线性表有n个元素（n-MAXSIZE.MAXSIZE指线性表的最大长度），且递增有。现有一元素x要插入到线性表的适当位置上，并保持线性表原有的顺序不变。设计程序实现。要求：采用顺序存储表示实现；采用链式存储表示方法实现：比较两种方法的优劣。 2.从单链表中删除指定的元素x，若x在单链表中不存在，给出提示信息。 要求： ①指定的值x由键盘输入； ②程序能处理空链表的情况。 3.设有头结点的单链表，编程对表中的任意值只保留一个结点，删除其余值相同的结点。 要求： ①该算法用函数（非主函数)实现； ②在主函数中调用创建链表的函数创建一个单链表，并调用该函数，验证算法的正确性。LinkedList Exchange（LinkedList HEAD,p) //HEAD是单链表头结点的指针，p是链表中的一个结点。本算法将p所指结点与其后 继结点交换。 （q=head->next；//q是工作指针，指向链表中当前待处理结点。 pre=head；//pre是前驱结点指针，指向q的前驱。 while（q'=null &&q1=p)(pre=q；q=q->next；]/未到p结点，后移指针。 if（p->next==null)printf(“p无后继结点\n”）；/p是链表中最后一个结点，无后继。 else/处理p和后继结点交换 （q=p->next；//暂存p的后继。 pre->next=q://p前驱结点的后继指向p的后继。 p->next=q->next；//p的后继指向原p后继的后继。 q->next=p：//原p后继的后继指针指向p。} }//算法结束。 4.已知非空单链表第一个结点由head指出，请写一算法，交换p所指结点与其下一个结点在链表中的位置。 要求： 线性表 一、选择题 1.线性表是（ A ） A．一个有限序列，可以为空B．一个有限序列，不可以为空 C．一个无限序列，可以为空D．一个无限序列，不可以为空 2.一维数组与线性表的特征是（ C ）。 A．前者长度固定，后者长度可变B．两者长度均固定 C．后者长度固定，前者长度可变D．两者长度均可变 3.用单链表方式存储的线性表，存储每个结点需要两个域，一个数据域，另一个是( B ). A．当前结点所在地址域B．指针域 C．空指针域D．空闲域 4.用链表表示线性表的优点是（ B ）。 A．便于随机存取 B．便于进行插入和删除操作 C．占用的存储空间较顺序表少 D．元素的物理顺序与逻辑顺序相同 5.在具有 n 个结点的单链表中，实现__A _的操作，其算法的时间复杂度都是O（n）。 A．遍历链表和求链表的第i个结点 B．在地址为P的结点之后插入一个结点 C．删除开始结点 D．删除地址为P的结点的后继结点 6.下面关于线性表的叙述中，错误的是（ B ）。 A．线性表采用顺序存储必须占用一片连续的存储单元 B．线性表采用顺序存储便于进行插入和删除操作 C．线性表采用链式存储不必占用一片连续的存储单元 D．线性表采用链式存储便于进行插入和删除操作 7.已知单链表的每个结点包括一个指针域next，它指向该结点的后继结点。现要将指针 q 指向的新结点插入到指针 p 指 向的结点之后，下面的操作序列中正确的是（ C ）。 A . q = p->next; p->next = q->next ; B . p->next = q->next; q = p->next ; C . q->next = p->next; p->next = q ; D . p->next = q; q->next = p->next ; 第一章 1．在数据结构中，从逻辑上可以把数据结构分为（C ） A．动态结构和静态结构 B. 紧凑结构和非紧凑结构 C．线性结构和非线性结构 D. 内部结构和外部结构 ● 2.在数据结构中,与所使用的计算机无关的是( A ) A. 逻辑结构 B. 存储结构 C. 逻辑和存储结构 D. 物理结构 3.下面程序的时间复杂度为____O（mn）_______。 for (int i=1; i<=m; i++) for (int j=1; j<=n; j++ ) S+=i 第二章线性表 ●链表不具备的特点是（A） A 可以随机访问任一结点（顺序） B 插入删除不需要移动元素 C 不必事先估计空间 D 所需空间与其长度成正比 2. 不带头结点的单链表head为空的判定条件为（A ），带头结点的单链表head为空的判定条件为（B ） A head==null B head->next==null C head->next==head D head!=null ●3.在线性表的下列存储结构中，读取元素花费时间最少的是（D） A 单链表 B 双链表 C 循环链表 D 顺序表 ● 4.对于只在表的首、尾两端进行手稿操作的线性表，宜采用的存储结构为(C) A 顺序表 B 用头指针表示的单循环链表 C 用尾指针表示的单循环链表 D 单链表 ● 5.在一个具有n 个结点的有序单链表中插入一个新的结点，并保持链表元素仍然有序， 则操作的时间复杂度为( D ) A O(1) B O(log2n) C O(n2) D O(n) ● 6.在一个长度为n (n>1)的单链表上，设有头和尾两个指针，执行(B)操作与链表的长 度有关 A 删除单链表中第一个元素 B 删除单链表中最后一个元素 C 在第一个元素之前插入一个新元素 D 在最后一个元素之后插入一个新元素 ●7.与单链表相比，双向链表的优点之一是(D) A 插入删除操作更简单 B 可以进行随机访问 C 可以省略表头指针或表尾指针 D 顺序访问相邻结点更容易 ●8.若list是某带头结点的循环链表的头结点指针，则该链表最后那个链结点的指针域 (头结点的地址)中存放的是( B ) A list的地址 B list的内容 C list指的链结点的值 D 链表第一个链结点的地址 ●9.若list1和list2分别为一个单链表与一个双向链表的第一个结点的指针，则( B ) A list2比list1占用更多的存储单元 B list1与list2占用相同的存储单元 C list1和list2应该是相同类型的指针变量 D 双向链表比单链表占用更多的存储单元 10.链表中的每个链结点占用的存储空间不必连续，这句话正确吗？ (不正确) 11. 某线性表采用顺序存储结构，元素长度为4，首地址为100，则下标为12的（第13个）元素的存储地址为148。V 100+4*12=148 11.在顺序表的（最后一个结点之后）插入一个新的数据元素不必移动任何元素。 12.若对线性表进行的操作主要不是插入删除，则该线性表宜采用（顺序）存储结构，若频繁地对线性表进行插入和删除操作，则该线性表宜采用( 链 )存储结构。 第二章线性表习题 判断题 1.线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。（） 选择题 1.一个线性表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是( ) （A）110 （B）108 （C）100 （D）120 3. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。 （A）64 （B）63 （C）63.5 （D）7 4.线性表采用链式存储结构时，其地址（）。 (A) 必须是连续的 (B) 部分地址必须是连续的 (C) 一定是不连续的 (D) 连续与否均可以 5. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（） （A）s->next=p;p->next=s; （B） s->next=p->next;p->next=s; （C）s->next=p->next;p=s; （D）p->next=s;s->next=p; 6.在一个单链表中，若删除p所指结点的后续结点，则执行（） （A）p->next=p->next->next; （B）p=p->next; p->next=p->next->next; （C）p->next=p->next; （D）p =p->next->next; 7.下列有关线性表的叙述中，正确的是（） （A）线性表中的元素之间隔是线性关系 （B）线性表中至少有一个元素 （C）线性表中任何一个元素有且仅有一个直接前趋 （D）线性表中任何一个元素有且仅有一个直接后继 8.线性表是具有n个（）的有限序列（n≠0) （A）表元素（B）字符（C）数据元素（D）数据项 填空题 1.已知P为单链表中的非首尾结点，在P结点后插入S结点的语句为：( ) 。 2.顺序表中逻辑上相邻的元素物理位置(一定 )相邻，单链表中逻辑上相邻的元素物理位置( )相邻。 实验一线性表及其应用 一、实验目的 1.熟悉C语言的上机环境，进一步掌握C语言的结构特点。 2.掌握线性表的顺序存储结构的定义及C语言实现。 3.掌握线性表的链式存储结构——单链表的定义及C语言实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容 1.顺序线性表的建立、插入及删除。 2.链式线性表的建立、插入及删除。 三、实验步骤 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插入元素68。 3.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。 四、实现提示 1.由于C语言的数组类型也有随机存取的特点，一维数组的机内表示就是顺序结构。因此，可用C语言的一维数组实现线性表的顺序存储。 在此，我们利用C语言的结构体类型定义顺序表： #define MAXSIZE 1024 typedef int elemtype; /* 线性表中存放整型元素*/ typedef struct { elemtype vec[MAXSIZE]; int len; /* 顺序表的长度*/ }sequenlist; 将此结构定义放在一个头文件sqlist.h里，可避免在后面的参考程序中代码重复书写，另外在该头文件里给出顺序表的建立及常量的定义。 2. 注意如何取到第i个元素，在插入过程中注意溢出情况以及数组的下标与位序（顺序表中元素的次序）的区别。 3.单链表的结点结构除数据域外，还含有一个指针域。用C语言描述结点结构如下： typedef int elemtype; typedef struct node 一、判断题 1. 线性表的逻辑顺序与存储顺序总是一致的。(FALSE) 2. 顺序存储的线性表可以按序号随机存取。(TRUE) 3.顺序表的插入和删除一个数据元素，每次操作平均只有近一半的元素需要移动。TRUE) 4.线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。(TRUE) 5，在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。(FALSE ) 6.在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。(TRUE) 7.线性表的链式存储结构优于顺序存储结构。(FALSE ) 8. 在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。(TRUE) 9.线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。(TRUE) 10.在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。(FALSE ) 二．选择题 11．线性表是()。 (A)一个有限序列，可以为空； (B)一个有限序列，不能为空； (C)一个无限序列，可以为空； (D)一个无序序列，不能为空。答：A 12．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（）个元素。 (A)n/2(B)(n+1)/2(C)(n–1)/2(D)n答：A 13．线性表采用链式存储时，其地址()。 (A)必须是连续的；(B)部分地址必须是连续的；(C)一定是不连续的；(D)连续与否均可以。答：D 14．用链表表示线性表的优点是（）。 (A)便于随机存取 (B)花费的存储空间较顺序存储少 (C)便于插入和删除 (D)数据元素的物理顺序与逻辑顺序相同答：C 15.单链表中，增加一个头结点的目的是为了（）。 2.6．数据的存储结构主要有哪两种？它们之间的本质区别是什么？ 答：主要有：顺序存储结构和链式存储结构两种。 区别: 顺序存储结构是借助元素在存储器的相对位置来表示数据间的逻辑关系，而链式存储结构是借助指针来表示数据间的逻辑关系。 2.7 设数据结构的集合为D={d1,d2,d3,d4,d5},试指出下列各关系R所对应的数据结构B=(D,R)中哪些是线性结构，哪些是非线性结构。 （1）R={(d1,d2),(d2,d4),(d4,d2),(d2,d5),(d4,d1)}; ( 2 ) R={(d5,d4),(d4,d3),(d3,d1),(d1,d2)}; ( 3 ) R={(di,di+1)|i=4,3,2,1}; ( 4 ) R={(di,dj)|i 2.〉链表：扩展性强，易于删除，添加；内存中地址非连续；长度可以实时变化；适用于需要进行大量增添或删除元素操作而对访问元素无要求的程序。 （2）缺点 顺序表：插入，删除操作不方便；扩展性弱；不易删除，添加。 链表：不易于查询，索引慢。 （3）顺序表和链表的优缺点是互相补充的关系。 2.17 试比较单向链表与双向链表的优缺点。 答：（1）优点 单向链表：耗存储空间小； 双向链表：可以从任何一点开始进行访问; （2）缺点： 单向链表：访问时必须从头开始，耗时。 双向链表：耗存储空间大。 （3）两者为互补关系 2.22 CQ[0:10]为一循环队列，初态front=rear=1,画出下列操作后队的头，尾指示器状态： （1）d,e,h,g,入队； （2）d,e出队； （3）I,j,k,l,m入队； （4）b出队； 第二章测试试题 班级：学号：姓名：成绩： 一、选择题（每小题5分） 1.线性表是( A )。 A一个有限序列，可以为空；B一个有限序列，不能为空； C一个无限序列，可以为空；D一个无序序列，不能为空。 2.用链表表示线性表的优点是（C）。 A便于随机存取 B花费的存储空间较顺序存储少 C便于插入和删除 D数据元素的物理顺序与逻辑顺序相同 3.某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( D )存储方式最节省运算时间。 A单链表 B双链表 C单循环链表 D带头结点的双循环链表 4.带头结点的单链表head为空的判定条件是（B ）。 A.head==NULL; B.head->next==NULL; C.head->next==head; D.head!=NULL; 5.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行（C ）。 A.s->next=p->next;p->next=s; B.p->next=s->next;s->next=p; C.q->next=s;s->next=p; D.p->next=s; s->next=q; 二、填空题（每小题5分） 1．给定有n个结点的向量，建立一个单链表的时间复杂度_______。建立一个有序单链表的时间复杂度_______。 2．从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较_____个结点。 3．在一个长度为n的线性表（采用顺序存储结构）中删除第i个元素(1≤i≤n)时，需向前移动____个元素。 4．当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用_____存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用_______存储结构为宜。5．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的个元素。 三、算法设计题（每小题25分） 1．设有一个用向量表示的线性表L，要求写出一个将该表逆置的过程，允许在原表的存储空间外再增加一个附加的工作单元。 2．已知两个整数集合A和B，它们的元素分别依元素值递增有序存放在两个单链表HA 和HB中，编写一个函数求出这两个集合的并集C，并要求集合C的链表的结点仍依元素值递增有序存放。（注意：并集不是归并） 《数据结构》习题集 第一章序论 思考题： 1.1简述下列术语：数据、数据元素、数据对象、数据结构、存储结构、数据类型、抽象数据类型 作业题： 1.2设有数据结构（D，R），其中 D={d1, d2, d3, d4 } R={r1, r2} r1={ (5) x=n; y=0; //n是不小于1的常数 while(x>=(y+1)*(y+1)){ △y++; } (6) x=91; y=100; while ( y>0 ) { △if(x>100) { x-=10; y--; } else x++ ; } (7) for( i=0; iC语言数据结构线性表的基本操作实验报告
数据结构线性表习题1
《数据结构》第二章习题参考答案 殷人昆版
第2章线性表习题解析(答)
数据结构_实验1_线性表的基本操作
数据结构练习题-线性表
(完整版)数据结构课后习题及解析第二章
DS第二章-课后习题答案
数据结构实验一题目一线性表实验报告
数据结构课后习题及解析第二章
数据结构线性表实验报告
数据结构-线性表-习题
【免费下载】数据结构习题及答案
第二章 线性表习题
《数据结构》实验一 线性表及其应用
数据结构_线性表练习题
第二章数据结构习题作业
第二章线性表测试题
数据结构习题
相关主题
文本预览