第二章 线性表
1、将以顺序表A中的元素逆置。例如原来顺序表A中的元素是100，90，80，sizeof是什么70，60，50，40，逆置后为40，50，60，70，80，90，100。算法所用的辅助空间要尽量可能地少。用非形式算法描述，并编写C语言程序。
答：描述：该顺序表A有N个元素，分别将第1个与第N个对换，第2个与第N－1个对换，依此类推第i个与第N－i个对换。
C语言程序：
#include <stdio.h>
#include <conio.h>
int main(void)
{
char elem[100],t;
int i, n, t;
printf("Please input number(1~100):"); /*输入要输入的元素的个数*/
scanf("%d", &n);
printf("***************************************************************\n");
printf("Please input element:\n");/*输入元素*/
flushall();
for(i=0; i<n; ++i)
{
scanf("%c", &elem[i]);
}
for(i=0; i<n; ++i)
{
printf("%c ", elem[i]);
}
printf("\n");
for(i=0; i<n/2; ++i)
{
t = elem[i];
elem[i] = elem[n-i-1];
elem[n-i-1] = t;
}
for(i=0; i<n; ++i)
{
printf("%c ", elem[i]);
}
getch();
return 0;
}
2、写一算法输出已知顺序表A中元素的最大值和次最大值。用非形式算法描述，并编写C语言程序。
#include <stdio.h>
#include <conio.h>
void printFstAndSndValue(SeqList sq)
{
int firstmax = 0;
int secondmax = 0;
int i = 0;
if(sq.last == -1)
{
printf(“List is empty!”);
return;
}
firstmax = sq.data[0];
secondtmax = 0;
for(i=1; i<=sq.last; ++i)
{
if(firstmax < sq.data[i])
{
firstmax = sq.data[i];
}
else if(secondmax < sq.data[i])
{
scondmax = sq.data[i];
}
}
printf(“%d %d”, firstmax, secondmax);
}
3、设一顺序表中元素值递增有序。写一算法，将元素x插到表中适当地位置，并保持顺序表地有序性，且分析算法地时间复杂度。
算法的C语言实现：
int *Insert_SeqList(SeqList *L, datatype x)
{
int i, j, t = 1;
for(i=0; i<L->last; ++i)
{
if(L->data[i] < x)
{
continue;
}
if(L->data[i] >= x)
{
for(j=L->last; j>i; --j)
{
L->data[j] = L->data[j-1];
}
L->data[i] = x;
t = 0;
break;
}
}
if(t > 0)
{
L->data[i+1] = x;
}
}
时间复杂度：O(n)。
4、设有两个安元素值递增有序的顺序表A和B（单链表A和B），编一程序将A表和B表归并成一个新的递增有序的顺序表C（单链表），值相同的元素均保留在C表中。
C程序：
#include <stdio.h>
#include <conio.h>
int main(void)
{
int A[8]={1,3,4,6,8,12,34,37};
int B[9]={14,16,17,19,26,30,41,88,91};
int C[17];
int i = 0;
int j = 0;
int k = 0;
printf("A array:");
for(i=0; i<8; ++i)
{
printf("%d ", A[i]);
}
printf("\n");
printf("B array:");
for(j=0; j<9; ++j)
{
printf("%d ", B[j]);
}
printf("\n");
i = 0;
j = 0;
while((i<8) && (j<9))
{
if(A[i] < B[j])
{
C[k++] = A[i++];
}
else if(B[j] < A[i])
{
C[k++] = B[j++];
}
else
{
C[k++] = A[i++];
}
}
while(i < 8)
{
C[k++] = A[i++];
}
while(j < 9)
{
C[k++] = B[j++];
}
printf("C array:");
for(k=0; k<17; ++k)
{
printf("%d ", C[k]);
}
getch();
return 0;
}
5、已知L是无表头结点的单链表，且p结点既不是首结点，试从下列提供的语句中选出合适的语句序列。
(1)在p结点后插入s结点：/4 /1。
(2)在p结点前插入s结点：/8 /12 /9 /4 /1。
(3)在表首插入s结点：/5。
(4)在表尾插入s结点：/8 /10 /1 /7。
/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 = p;
/7 s->next = NULL;
/8 q = p;
/9 while(p->next != Q) {p = p->next;}
/10 while(q->next != NULL) {q = q->next;}
/11 p = q;
/12 p = L;
/13 L = s;
/14 L = p;
6、已知p结点是某双向链表的中间结点，试从下列提供的语句中选出合适的语句序列。
(1)在p结点后插入s结点：/7 /12 /3 /6
(2)在p结点前插入s结点：/13 /8 /5 /4
(3)删除p结点的直接后继结点：
q = p->next; p->next = q->next; q->next->prior = q->prior; free(q);
(4) 删除p结点的直接前趋结点：q = p->prior;p->prior = q->prior;
q->prior->next = q->next; free(q);
(5)删除p结点：p->prior->next=p->next; p->next->prior=p->prior; free(p);
7、设有两个线性表A和B皆是单链表存储结构。同一个表中的元素各不相同，且递增有序。写一算法，构成一个新的线性表C，使C为A和B的交集，且C中的元素也递增有序。
void new(LinkList A LinkList B)
{
LinkList C;
LNode *a, *b, *c, *ap, *bp;
a = A->next;
b = B->next;
c = C->next;
while((a->next!=NULL) && (b->next!=NULL))
{
c = (LNode *)malloc(sizeof(LNode));
if(a->data <= b->data)
{
c->next = a;
c = c->next;
ap = a->next;
free(a);
a = ap;
}
else
{
c->next = b;
c = c->next;
bp = b->next;
free(b);
b = bp;
}
}
while(a->next != NULL)
{
c = (LNode *)malloc(sizeof(LNode));
c->next = a;
c = c->next;
ap = a->next;
free(a);
a = ap;
}
while(b->next != NULL)
{
c = (LNode *)malloc(sizeof(LNode));
c->next = b;
c = c->next;
bp = b->next;
free(b);
b = bp;
}
c->next = NULL;
return 0;
}
8、删除线性表a中第i个元素起的k个元素。
Status DeleteK(SeqList &a,int i,int 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];
}
发表评论