大前端

前端学习之家-大前端

数据结构实验

数据结构实验5

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

#include <stdio.h>
#define maxlen 30

typedef 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)))))))。

发表评论:

Copyright Your WebSite.Some Rights Reserved.