数据结构课后练习—第2章.ppt

第二章 线性表;学习要点;学习要点;一、判断对错题;二、单项选择题;二、单项选择题;二、单项选择题;三、填空题;四、简答题;四、简答题;四、简答题;四、简答题;4. 分析下述三个算法的具体功能。 ListNode *Demo1(LinkList L, ListNode *p) { //L是有头结点的单链表 ListNode *q=L-next; while(qq-next!=p) q=q-next; if(q) return q; else Error(*p not in L); };4. 分析下述三个算法的具体功能。 void Demo2(ListNode *p, ListNode *q) { //p，*q是链表中的两个结点 DataType temp; temp=p-data; p-data=q-data; q-data=temp; };4. 分析下述三个算法的具体功能。 LinkList test1( LinkList L ) { //L是无头结点的单链表 LinkList *q, *p; if ( LL-next ) {q=L; L=L-next; p=L; while ( p-next ) p=p-next; p-next=q; q-next=NULL; } return L; };5. 设有多项式 ⑴ 请画出 的单链表存储表示。 ⑵ 设 ，求得并画出的单链表存储表示。;五、程序设计题;Status ListDelete _L( LinkList L， ElemType x ) { //在带头结点的单链表L中，删除值为x的结点。 LNode *p,*q; p = L; while ( p-next p-next-data!=x ) { q=p; p = p-next; } //寻找值为x的结点，并令p指向其前驱（被删结点）； //指针q指向*p结点的前驱结点。 if ( !(p-next) ) return ERROR; //表中不存在值为x的结点。 p–next=q–next; //删除元素（结点）x的前驱结点。 free( p ) ; //释放结点的存储空间。 return OK; };线性表的结构定义： --------线性表的动态分配顺序存储结构--------- #define LIST_INIT_SIZE 100 //顺序表的初始分配量 #define LISTINCREMENT 10 //顺序表的分配增量 typedef struct{ ElemType *elem; //存储空间基址：即数组的起始地址 int length; //顺序表的当前长度：实际的元素个数 int listsize; //当前分配的存储容量（以sizeof（ElemType）为单位） }SqList;;2. 将一个顺序表中从第i个结点开始的k个结点删除。; if ( k=((q-p)+1) ) //第i个元素后的所有元素均被删除 { L.length = i-1; return OK; } else for( ; k=1; k=1; --k; ) { for ( ++p; p = q; ++p ) *( p-1 ) = *p; //到第i+1个元素平移 p++; --L.length; q = L.elem + L.length – 1; } return OK; //返回删除元素成功标志 } ;五、程序设计题;Status LinkListInsert( LinkList L, ElemType x ){ //在升序链表L（带头结点）中插入一个新元素结点x q=L; p=q-next; //找到插入位置 while( p!=NULLp-data=x ) { q=p; p=p-next; } s=( LinkList )malloc( sizeof(LNode) ); //生成新结点 s-data=x; s-next=p; //插入结点 q-next=s; }//LinkListInsert;结束