Question

数据结构（c语言版）题目求答案

1．已知一个带头结点的单链表L，结点结构为

typedef struct Node {

ElemType data; //数据域

struct Node *next; //指针域

} *Link;

设只给出链表头指针L和一个正整数k。试设计一个尽可能高效的算法Search(L, k)，用于查找L中倒数第k个位置上的结点。

¨3.28② 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点(注意不设头指针)，试编写相应的队列初始化、入队和出队的算法。

¨3.31③ 顺读和逆读相同的字符序列称为回文，例如“abcba”是回文，而“ababab”不是回文。试编写一个算法，判别读入的一个以“#”为结束符的字符序列是否为回文
顺便想知道新建链表有哪些方法，个人感觉好像不只一种，有点迷惑

Answer 1

3.28
void InitCiQueue(CiQueue&Q)//初始化循环链表表示的队列Q
{
Q=(CiLNode*)malloc(sizeof(CiLNode));
Q->next=Q;
}//InitCiQueue
voidEnCiQueue(CiQueue&Q,int x)//把元素x插入循环列表表示的队列Q,Q指向队尾元素，Q->next指向头结点，Q->next->next指向队尾元素
{
p=(CiLNode*)malloc(sizeof(CiLNode));
p->data=x;
p->next=Q->next;//直接把p加在Q的后面
Q->next=p;
Q=p;//修改尾指针
}
Status DeCiQueue(CiQueue&Q,int x)//从循环链表表示的队列Q头部删除元素x
{
if(Q==Q->next)return INFEASIBLE;//队列已空
p=Q->next->next;
x=p->data;
Q->next->next=p->next;
free(p);
rturn OK;
}//DeCiqueue

3.31

int Palindrome_Test()
{
InitStack(S);InitQueue(Q);
while((c=getchar())!='@')
{
Push(S,c);EnQueue(Q,c);
}
while(!StackEmpty(S))
{
pop(S,a);DeQueue(Q,b);
if(a!=b)return ERROR;
}
return OK;
}