发布时间 : 星期二 文章华南理工大学数据结构课程习题集部分答案更新完毕开始阅读ec556181777f5acfa1c7aa00b52acfc788eb9f42
while(_first!=NULL )
{ p=first；first=first–>link； p–>link=head-link;
first=head–>link； delete _head ;}
．2．在顺序表中随机存取的数据，很容易在顺序表中实现按序号查找元素。代码如下所示，请在下划线处填上正确的语句。 template
x=elem[i–1]； return __true ； } ．3．线性表的插入操作是指在线性表的第m–1个数据元素和第m个数据元素之间插入一个新的数据元素x，其结果是使长度为n的线性表(a1, a2 ,…, am–1, am,…, an)变成长度为n+1的线性表(a1, a2 ,…, am–1, x, am,…, an)，并且数据元素am–1和am之间的逻辑关系发生了变化。
实现步骤如下：(1)合法性判断：插入位置i是否合法?表是否已满?(2)将第i至第n位的元素向后移动一个位置；(3)将要插入的元素写到第i个数据元素的位置；(4)表长加1。
具体算法如下，请在下划线处填上正确的语句。 template
Line_ListSqu
for(_int j=length-4；j>=i–1；j– –) elem[j+1]=elem[j]； elem[i–1]= _x_ ； length++； return _*this ； }
.4.-冒泡排序（Bubble Sort）的基本思想是：设数组a中存放了n个数据元素，循环进行n 趟如下的排序过程，请在下划线处填上正确的语句。
void BubbleSort(DataType a[ ], int n) {
int i, j, flag=1; DataType temp;
for(i = 1; _i〈﹠﹠flag==1_ ; i++)
{ flag = 0; for(j = 0; _j〈n-i ; j++) { if(_a[j].key〉a[j+1].key) { flag = 1;
temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; } } } }
.5.按值查找是指在线性表中查找与给定值x相等的数据元素，具体实现代码如下，请在下划线处填上正确的语句。
template
if (IsEmpty( )) return 0；//线性表为空时返回0 while(_i〈length﹠﹠！(x==elem[i] ) ) i++； if (elem[i]= =x) return ++i； else return ____0___ ； }
.6.线性表的删除操作是使长度为n的线性表(a1, a2,…, am–1, am,…,an)变为长度为n–1的线性表(a1, a2,…, am–1, am+1,,…,an)，并且数据元素am–1、am和am+1之间的逻辑关系也会发生变化，需要把第m+1～n个元素（共n–m个元素）依次向前移动一个位置来反映这种变化。具体实现步骤如下：①判断删除位置i是否合法，合法则将该位置元素放入x中，否则抛出异常；②将第i+1至第n位的元素向前移动一个位置；③表长减1。
具体算法如下，请在下划线处填上正确的语句。 template
Line_ListSqu
{ for(_int j=i_ ；j elem[__j-1_ ]=elem[j]； length – –； return __*this _ else throw OutOfBounds( )； } } .7. 假设以数组a[m]存放循环队列的元素，同时设变量rear 和length分别作为队尾指针和队中元素个数，试给出判别此循环队列的队满条件，并写出相应入队和出队的算法（在出队的算法中要返回队头元素）。请在下划线处填上正确的语句。 #define m 100 int enqueue(int a[], int rear, int length, int x) { if(___________) {printf(“queue is full”); return 0;} rear=(rear+1)% m; a[rear]=x; length ___________; return length; } int dequeue(int a[], int rear, int length, int *x) { if(___________) {printf(“queueempty”); return 0;} *x= a [(rear- length +m)%m]; Length ___________; return length; .8.--删除运算是将单链表的第i个结点删去。先在单链表中找到第i–1个结点，再删除其后的结点。具体算法代码如下所,请在下划线处填上正确的语句。 template Line_ListLink { if (__i〈1__|| !first) throw OutOfBounds( )；//删除位置不合法 Line_ListNode if (_i==1_) first=first–>link； else { Line_ListNode while(_q﹠﹠_j if (!q || _！q-〉link_) throw OutOfBounds( )；//没有第i个结点 p=q–>link；q–>link=p–>link； } .9. 删除运算是将单链表的第i个结点删去。先在单链表中找到第i–1个结点，再删除其后的结点。具体算法代码 如下所示：请在下划线处填上正确的语句。 template Line_ListLink { if (_i〈1‖！first_) throw OutOfBounds( )；//删除位置不合法 Line_ListNode if (_i==1__) first=first–>link； else { Line_ListNode while(q && j if (!q || _！q-〉link_) throw OutOfBounds( )；//没有第i个结点 p=q–>link；q–>link=p–>link； } x=p–>data；delete p； return *this；} .10.求子串Sub_String 已知串S，1 ≤ pos ≤ Length_Str(S)且0 ≤ len ≤Length_Str(S)–pos+1，用串Sub返回S的自第i个字符起长度为j的子串。请在下划线处填上正确的语句。 string Sub_String(string &Sub, string S, int i, int j); { int p; Sub.length = 0; if (i <= 0 || i > S.length || j<= 0 ||i-1+j〉s.length return Sub; //参数错误时，返回空串 for(p = i – 1; _p〈i-1+j_; p++) //把S.ch[i–1]至S.ch[i–1+j]复制到串Sub中 Sub.ch[p – i +1] = S.ch[p]; Sub.ch[j] ='\\0'; sub.length_ = j; return Sub; } } ．四．阅读理解题(描述算法思路,再综合出其功能) 本题说明: 算法思路指的是对某种数据结构(如,记录序列), 进行操作(如,移动位置), 的处理步骤(如,1,2,3….). 算法功能指的是要达到的处理目标(如,合并成有序的单链表.) .1. 阅读如下算法代码：描述算法思路,再综合出其功能. main(){ int i,max,a[10]; printf(“请输入10个整数:”); for(i=0;i<=10;i++) scanf(“%d”,&a[i]); max=a[0]; i=1; while(i<10) { if(a[i]>max) max=a[i]; i++; } printf(“值为:”,max); } 答：10个数字找出其最大值 .2. 阅读如下算法代码：描述算法思路,再综合出其功能. void delete(node *head,int x) { node *p,*q; q=head; p=head->next; while((p!=NULL) && (p->data!=x)) { q=p; p=p->next; } if(p==NULL) printf(\未找到x！\\n\ else if(q==head) printf(\为第一个结点，无前趋！\\n\ else { q->data=x; q->next=p->next; free(p); } } .3. 阅读如下算法代码：描述算法思路,再综合出其功能. int InsertPosList(struct List *L, int pos, ElemType x) { int i; if(pos<1 || pos>L->size+1) /*若pos越界则插入失败*/ return 0; if(L->size==L->MaxSize) /*重新分配更大的存储空间*/ againMalloc(L); for(i=L->size-1; i>=pos-1; i--) L->list[i+1]=L->list[i]; L->list[pos-1]=x; L->size++; return 1; } .4. 阅读如下算法代码：描述算法思路,再综合出其功能.