第二章 线性表(8)

ListNode *p=L; int i=1;

printf(\有幸逃生的有：\ while(p->next!=L) {

printf(\ if(i==0) printf(\ p=p->next; }

printf(\}

14．有顺序表A和B，其元素均按从小到大的升序排列，编写一个算法将它们合并成一个顺序表C，要求C的元素也是从小到大升序排列。要求写出完整代码。（12分） 1．

#define MAXSIZE 20 typedef int datatype; typedef struct {

datatype data[MAXSIZE]; int last; }SeqList;

SeqList *init_SeqList(); void input(SeqList *L); void output(SeqList *L);

void merge(SeqList *A,SeqList *B,SeqList *C); main() {

SeqList *A,*B,*C; datatype x; int i,n;

A=init_SeqList(); B=init_SeqList(); C=init_SeqList(); input(A); input(B); merge(A,B,C); output(C); getch(); }

SeqList *init_SeqList() {

36

SeqList *L;

L=(SeqList *)malloc(sizeof(SeqList)); L->last=-1; return L; }

void merge(SeqList *A,SeqList *B,SeqList *C) {

int i,j,k; i=0;j=0;k=0;

while(i<=A->last&&j<=B->last) if(A->data[i]data[j])

C->data[k++]=A->data[i++]; else

C->data[k++]=B->data[j++]; while(i<=A->last)

C->data[k++]=A->data[i++]; while(j<=B->last)

C->data[k++]=A->data[j++]; C->last=k-1; }

void input(SeqList *L) {

int n;

printf(\ for(n=0;;n++) {

scanf(\ if(L->data[n]==0) break; L->last=n; } }

void output(SeqList *L) {

int n;

for(n=0;n<=L->last;n++)

printf(\}

15．对于List类型的线性表，编写出下列每个算法。

(1) 从线性表中删除具有最小值的元素并由函数返回，空出的位置由最后一个元素填补，若线性表为空则显示出错信息并退出运行。 (2) 从线性表中删除第i个元素并由函数返回。 (3) 向线性表中第i个元素位置插入一个元素。

37

(4) 从线性表中删除具有给定值x的所有元素。 (1) ElemType DMValue( List & L ) {

if ( ListEmpty(L) ) { // 空线性表

cerr <<”List is Empty!”<

ElemType x; // x存放最小元素 x = L.list[0];

int k = 0; // k存放最小元素的下标 for ( int i = 1; i

if ( L.list[i] < x ) { x = L.list[i] ; k = i; }

L.list[k] = L.list[L.size-1]; // 最后一个元素填补最

小元素位置

L.size--; // 线性表长度减1 return x; // 返回最小元素

}

(2)ElemType Delete( List & L, int i ) {

if ( i<1 || i>L.size ) { // 判断i的合法性

cerr <<”Index is out range!”<

}

ElemType x = L.list[i-1]; // 保存被删除元素

for ( int j = i-1; j

L.size--; // 长度减1 return x; // 返回被删元素 }

(3)void Insert( List & L, int i, ElemType x ) {

if ( i<1 || i>L.size+1 ) { // 判断i的合法性

cerr <<”Index is out range!”<

}

if ( L.size == MaxSize ) { // 判断线性表满

cerr <<”List overflow!”<

}

for ( int j = L.size-1 ; j>=i-1 ; j-- ) // 元素后移，产生插入位置

L.list[j+1] = L.list[j];

L.list[i-1] = x; // 元素插入 L.size++; // 长度加1 }

(4) void Delete( List & L, ElemType x ) { int i = 0;

38

while ( i

if ( L.list[i] == x ) { // 删除x元素

for ( int j = i+1; j

}

else i++; // 寻找下一个x元素的位置 }

16．对于结点类型为LNode的单链表，编写出下列每个算法。

(1) 删除单链表中的第i个结点。

(2) 在有序单链表中插入一个元素x的结点。 (3) 从单链表中查找出所有元素的最大值，该值由函数返回，若单链表为空，则显示出错信息并停止运行。

(4)统计出单链表中结点的值等于给定值x的结点数。

(1)void Delete( LNode * & HL, int i ) {

if ( i<1 || HL==NULL ) { // 判断i的合法性或空链表

cerr <<”index is out range!”<

}

LNode * ap , * cp;

ap = NULL ; cp = HL ; // cp指向当前结点，ap指向其前驱结点

int j = 1;

while ( cp != NULL ) // 查找第i个结点 if ( j == i ) // 找到第i个结点

break; // cp指向的结点即为第i个结点

else { // 继续向后寻找

ap = cp;

cp = cp->next; j++;

}

if ( cp == NULL ) { // 没有找到第i个结点

cerr <<”Index is out range!”<

}

if ( ap == NULL ) // 删除第1个结点（即i=1） HL = HL->nextl else

ap->next = cp->next; // 删除第i个结点

delete cp; // 释放被删除结点的空间 }

(2)void Insert( LNode * & HL, const ElemType & x ) { LNode * newptr = new LNode; // 申请一个新结点

39

if ( newptr == NULL ) { // 分配失败

cerr <<”Memory allocation failare!”<

}

newptr->data = x;

if ( HL == NULL || xdata ) { // 空表 或 x小于表头结点，

newptr->next = HL; // 作为新表头结点插入 HL = newptr; return;

}

// 查找插入位置

LNode * cp = HL->next; // 用cp指向当前结点（即待查结点）

LNode * ap = HL; // 用ap作为指向当前结点的前驱结点指针

while ( cp != NULL )

if ( xdata) break; // 找到插入位置

else { ap = cp; cp = cp->next; } // 继续查找插入位置

newptr->next = cp; ap->next = newptr; // 插入新结点 }

(3)ElemType MaxValue( LNode * HL ) {

if ( HL == NULL ) { // 空表

cerr <<”Linked list is empty!”<

ElemType max = HL->data; LNode * p = HL->next;

while ( p != NULL ) { // 寻找最大值 if ( max < p->data ) max = p->data; p = p->next; }

return max;

}

(4)int Count( LNode * HL , ElemType x ) { int n = 0;

LNode * p = HL;

while ( p != NULL ) {

if ( p->data == x ) n++; p = p->next; }

return n; }

40