数据结构实验5

1、阅读以下算法，填充空格，使其成为完整的算法。其功能是在一个非递减的顺序存储线性表中，删除所有值相等的多余元素（参考源代码zuoye5_01.c）。

#include <stdio.h>
#define maxlen 30typedef struct
{int elem[maxlen];int lenth;		//存放顺序表中元素个数
} sqlisttp;void demo(sqlisttp *L)
{int i = 1, j = 0;while (i < L->lenth)       //当表不为空或只有一个数据{if (L->elem[i] != L->elem[j])     //如果第一个数据与第二个数据不同就将第一个数据保存在 elem[j], 相同则跳过，将不同的保存在elem[j]{j++;L->elem[j]=L->elem[i];}    i++;}L->lenth=j;
}int main(void)
{int i;sqlisttp L;for (i = 0; i <= 15; i++){L.elem[i] = i / 2;}L.lenth = i;for (i = 0; i <= L.lenth; i++){printf("%d, ", L.elem[i]);}// printf("\n ");demo(&L);for (i = 0; i <= L.lenth; i++){printf("%d, ", L.elem[i]);}printf("\n");return 0;}

2、对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为___O(1)_____，在给定值为x的结点后插入一个新结点的时间复杂度为____O(n)____。

3、在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点，则需执行下列语句：

s->next = p；s->prior = _p->piror__；p->prior = s；__p->piror-next__ = s；

4、对于双向链表，在两个结点之间插入一个新结点需修改的指针共__4__个，单链表为___2___个。

5、已给如下关于单链表的类型说明：

typedef struct _list

{

int data;

struct _list *next;

} list;

以下程序采用链表合并的方法，将两个已排序的单链表合并成一个链表而不改变其排序性（升序），这里两链表的头指针分别为p和q（参考源代码zuoye5_05.c）。

#include <stdio.h>
#include <malloc.h>typedef struct _list
{int data;struct _list *next;
} list;void mergelink(list *p, list *q)
{list *h, *r;h = (list *)malloc(sizeof(list));h->next = NULL;    r = h;while (p != NULL && q != NULL)   {if (p->data <= q->data)       {r->next=p;r = p; p = p->next;}else{r->next=q;r = q;q = q->next;}}if (p == NULL){r->next = q;}else{r->next=p;}p = h->next;free(h);
}void print(list *h)
{list *p;p = h;while (p != NULL){printf("%d, ", p->data);p = p->next;}printf("\n");
}int main(void)
{int i;list *h1, *h2;list *p1, *q1, *p2, *q2;h1 = q1 = p1 = (list *)malloc(sizeof(list));h2 = q2 = p2 = (list *)malloc(sizeof(list));h1->data = 1;h2->data = 1;h1->next = NULL;h2->next = NULL;for (i = 1; i <= 10; i++){p1 = (list *)malloc(sizeof(list));p2 = (list *)malloc(sizeof(list));p1->data = i * 2;p2->data = i * 3;p1->next = q1->next;q1->next=p1;q1 = p1;p2->next = q2->next;q2->next=p2;q2 = p2;}print(h1);print(h2);mergelink(h1, h2);print(h1);return 0;}

6、设pa，pb分别指向两个带头结点的有序（从小到大）单链表。仔细阅读如下的程序，并回答问题：

（1）程序的功能；

（2）s1，s2中值的含义；

（3）pa，pb中值的含义。

void exam(list *pa, list *pb)

{

list *p, *p1, *p2;

int s1, s2;

p1 = pa->next;//

p2 = pb->next;

pa->next = NULL;

s1 = 0;

s2 = 0;

while (p1 != NULL && p2 != NULL)

{

if (p1->data < p2->data)

{

p = p1;

p1 = p1->next;

s2++;

free(p);

}

else if (p1->data > p2->data)

{

p2 = p2->next;

}

else

{

p = p1;

p1 = p1->next;

p->next = pa->next;

pa->next = p;

p2 = p2->next;

s1++;

}

}

while (p1 != NULL)

{

p = p1;

p1 = p1->next;

free(p);

s2++;

}

}

答：（1）程序的功能是将pa链表中与pb中相同的元素留下来（删除其它不同元素），并倒序存放；

（2）s1中存放的是pa中与pb中相同元素的个数，s2中存放pa中被删除元素的个数（即与pb不同的元素的个数)

（3）pa中值是地址值，存放其中一个头结点的地址，pb中值同pa（存放另一个地址）。

7、已知L是一个数据类型linkedlist的单循环链表，pa和pb是指向L中结点的指针。简述下列程序段的功能（参考源代码zuoye5_07.c）。

typedef struct _linklist

{

int data;

struct _linklist *next;

} linklist;

void subp(linklist *s, linklist *q)

{

linklist *p;

p = s;

while (p->next != q)

{

p = p->next;

}

p->next = s;

}

void Mp(linklist *pa, linklist *pb)

{

subp(pa, pb);

subp(pb, pa);

}

答：该Mp函数功能是将pa所指结点到pb前一个结点的这些结点形成一个循环链表(pa是入口），将pb所指结点到pa前一个结点的结点形成另一个循环链表(pb是入口)。

8、表达式23+((12*3-2)/4+34*5/7)+108/9的后缀表达式是_23 12 3*2-4/34 5*7/++108 9 /+_。

9、栈是________的线性表，其运算遵循_先出后进_的原则。队列是________的线性表，其运算遵循________的原则。

操作受限   后进先出          允许一端插入一段删除      先进先出

10、一个栈的输入序列是：1，2，3则不可能的栈输出序列是________。

3，1，2

11、设有一个空栈，栈顶指针为1000H（十六进制），现有输入序列为1，2，3，4，5，经过PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH之后，输出序列是________，而栈顶指针值是________H。设栈为顺序栈，每个元素占4个字节。

两个pop   分别 2 3   100C

12、设输入序列为2，3，4，5，6，利用一个栈能得到序列2，5，3，4，6吗？栈可以用单链表实现吗？    不能     栈可以使用单链表实现，将单链表的表头作为栈底。

13、设循环队列用数组A[1..M]表示，队首、队尾指针分别是FRONT和TAIL，判定队满的条件为_(TAIL+1)%M==FRONT%M_。

14、设Q[0..N-1]为循环队列，其头、尾指针分别为P和R，则队Q中当前所含元素个数为_(R-P+N)%N_。

1. 下列程序判断字符串s是否对称，对称则返回1+，否则返回0；如f("abba")返回1，f("abab")返回0。

int f(_char s[]_)

{

int i = 0, j = 0;

while (s[j])

{

_j++_;

}

for (j--; i < j && s[i] == s[j]; i++, j--)

{

;

}

return _i>=j_;

}

16、设二维数组A[-20..30,-30..20]，每个元素占有4个存储单元，存储起始地址为200H（十六进制）。如按行优先顺序存储，则元素A[25,18]的存储地址为_269CH_；如按列优先顺序存储，则元素A[-18,-25]的存储地址为_604H_。

17、二维数组a[4][5][6]（下标从0开始计，a有4*5*6个元素），每个元素的长度是2，则a[2][3][4]的地址是_10A4H_。(设a[0][0][0]的地址是1000H十六进制,数据以行为主方式存储)

18、n阶对称矩阵a满足a[i][j]=a[j][i],i,j=1..n,，用一维数组t[1..m]存储(按行向存储左下三角)时，t的长度为_n(n+1)/2_， 当i=j， a[i][j] = t[_j*(j+1)/2_], i>j, a[i][j] = t[_i*(i-1)/2+j_], i<j, a[i][j] = t[_j*(j-1)/2+i_]。

19、已知a数组元素共5个，依次为12，10，5，3，1；b数组元素共4个，依次为4，6，8，15，则执行如下所示的过程语句sort后得到c数组各元素依次为15，12，10，8，6，5，4，3，1；数组a，b，c的长度分别为l=5，m=4，n=9请在程序中方框内填入正确的成分，完成上述要求。

void sort(int a[], int b[], int c[])

{

int i, j, k, x;

int d[M];

for (i = 0; i < M; i++)

{

d[i] = _b[M-i-1]_;

}

i = 0;

j = 0;

k = 0;

while (i < L && j < M)

{

if (a[i] > d[j])

{

_x=a[i]_;

_i++_;

}

else

{

_x=d[j]_;

_j++_;

}

c[k] = x;

_k++_;

}

while (_i<L_)

{

c[k] = a[i];

k++;

i++;

}

while (_j<M_)

{

c[k] = d[j];

k++;

j++;

}

}

20、完善下列程序。下面的程序将数列1,2,3,…,n*n,依次按蛇型方式存放在二维数组A[1..n,1..n]中。如下图。

#include <stdio.h>

#define NMAX 10

int main(void)

{

int i, j, n, k, p, q, m;

int a[NMAX][NMAX]={0};

scanf("%d", &n);

m = 1;

for (k = 1; _k<2*n_; k++)

{

if (k < n)

{

q = k;

}

else

{

_q=2*n-k_;

}

for (p = 1; p <= q; p++)

{

if (_q%2==1_)

{

i = q-p+1;

j=p;

}

else

{

i = p;

j = q-p+1;

}

if (_k>=n_)

{

i = i+n-q;

j=j+n-q;

}

a[i][j] = m;

_m++_;

}

}

for (i = 1; i <= n; i++)

{

for (j = 1; j <= n; j++)

{

printf("%4d", a[i][j]);

}

printf("\n");

}

}

21、约瑟夫环问题：设有n个人围坐一圈，并按顺时针方向1—n编号。从第s个人开始进行报数，报数到第m个人，此人出圈，再从他的下一个人重新开始从1到m的报数进行下去 ，直到所有的人都出圈为止。

void Josef(int a[N+1], int s, int m)

{

int i, j, w, s1;

for (i = 1; i <= N; i++)

{

a[i] = i;

}

s1 = s;

for (i = N; i>= 2; i--)

{

s1 = _(s1+m-1)%i_; //计算出圈人数

if (s1== 0)

{

_s1=i_;

}

w = a[s1]; //a[s1]出圈

for (j = s1;_j<=i_; j++)

{

a[j] = a[j+1];

}

a[i]=w;

}

printf("出圈序列为：");

for (i = N; i>=1;i--)

{

printf("%d ", a[i]);

}

printf("\n");

}

22、算法Print及所引用的数组A的值如下，写出调用Print(1)的运行结果（其中n=15）。

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
A	B	C	D	E	F	G	O	O	H	0	I	J	K	L
1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
A	B	C	D	E	F	G	O	O	H	0	I	J	K	L

（1）

2

0

0

0

3

0

4

0

0

0

（2）

i	1	1	2	3	4
j	1	4	3	2	1
v	2	4	3	3	4

（3）

24、已知广义表A=(9，7，(8，10，(99))，12)，试用求表头和表尾的操作Head( )和Tail( )将原子元素99从A中取出来。

答：Head(Head(Tail(Tail(Head(Tail(Tail(A)))))))。