新学菜鸟请教“两道简单的数据结构实验题”，高手请进，在线等，急求证！~~

数据结构 实验题~ （高手请进）~

单链表的操作，我已经写得差不多了，你只要改一下数据结构，应该可以满足你的要求！
#include
#include
#include

/************************************************************************/
/* 常量定义 */
/************************************************************************/
#define ElemType int
#define Status int
#define TRUE 1
#define OK 1
#define FALSE 0
#define ERROR -1

/************************************************************************/
/* 线性表的单链表存储结构*/
/************************************************************************/
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode, *LinkList;

//////////////////////////////////////////////////////////////////////////
//
// 带有头结点的单链表的基本操作(13个)
//
//////////////////////////////////////////////////////////////////////////

/************************************************************************/
/* 操作结果：构造一个空的线性表L */
/************************************************************************/
void InitList(LinkList *L)
{
*L = (LinkList)malloc(sizeof(struct LNode)); /* 产生头结点，并使L指向此头结点 */
if( !*L ) /* 存储分配失败 */
exit(OVERFLOW);
(*L)->next = NULL; /* 指针域为空 */
}

/************************************************************************/
/* 初始条件：线性表L已存在。*/
/* 操作结果：销毁线性表L */
/************************************************************************/
void DestroyList(LinkList *L)
{
LinkList q;
while(*L)
{
q = (*L)->next;
free(*L);
*L=q;
}
}
/************************************************************************/
/* 初始条件：线性表L已存在。*/
/* 操作结果：将L重置为空表 */
/************************************************************************/
void ClearList(LinkList L) /* 不改变L */
{
LinkList p, q;
p = L->next; /* p指向第一个结点 */
while(p) /* 没到表尾 */
{
q = p->next;
free(p);
p = q;
}
L->next = NULL; /* 头结点指针域为空 */
}

/************************************************************************/
/* 初始条件：线性表L已存在。*/
/* 操作结果：若L为空表，则返回TRUE，否则返回FALSE */
/************************************************************************/
Status ListEmpty(LinkList L)
{
/* 非空 */
return (L->next) ? FALSE : TRUE;
}

/************************************************************************/
/* 初始条件：线性表L已存在。操作结果：返回L中数据元素个数 */
/************************************************************************/
int ListLength(LinkList L)
{
int i = 0;
LinkList p = L->next; /* p指向第一个结点 */
while(p) /* 没到表尾 */
{
i++;
p = p->next;
}
return i;
}

/************************************************************************/
/* L为带头结点的单链表的头指针。*/
/* 当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR */
/************************************************************************/
Status GetElem(LinkList L, int i, ElemType *e) /* 算法2.8 */
{
int j = 1; /* j为计数器 */
LinkList p = L->next; /* p指向第一个结点 */
while(p && j < i) /* 顺指针向后查找，直到p指向第i个元素或p为空 */
{
p = p->next;
j++;
}
if( !p || j > i) /* 第i个元素不存在 */
return ERROR;
*e = p->data; /* 取第i个元素 */
return OK;
}

/************************************************************************/
/* 初始条件: 线性表L已存在，compare()是数据元素判定函数(满足为1，否则为0)*/
/* 操作结果: 返回L中第1个与e满足关系compare()的数据元素的位序。 */
/* 若这样的数据元素不存在，则返回值为0 */
/************************************************************************/
int LocateElem(LinkList L, ElemType e, Status(*compare)(ElemType, ElemType))
{
int i = 0;
LinkList p = L->next;
while(p)
{
i++;
if(compare(p->data,e)) /* 找到这样的数据元素 */
return i;
p=p->next;
}
return 0;
}

/************************************************************************/
/* 初始条件: 线性表L已存在 */
/* 操作结果: 若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱 */
/* 返回OK；否则操作失败，pre_e无定义，返回INFEASIBLE */
/************************************************************************/
Status PriorElem(LinkList L, ElemType cur_e, ElemType *pre_e)
{
LinkList q, p = L->next; /* p指向第一个结点 */
while(p->next) /* p所指结点有后继 */
{
q = p->next; /* q为p的后继 */
if(q->data == cur_e)
{
*pre_e = p->data;
return OK;
}
p = q; /* p向后移 */
}
return ERROR;
}

/*************************************************************************/
/* 初始条件：线性表L已存在 */
/* 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继*/
/* 返回OK; 否则操作失败，next_e无定义，返回INFEASIBLE */
/*************************************************************************/
Status NextElem(LinkList L, ElemType cur_e, ElemType *next_e)
{
LinkList p = L->next; /* p指向第一个结点 */
while(p->next) /* p所指结点有后继 */
{
if(p->data == cur_e)
{
*next_e = p->next->data;
return OK;
}
p = p->next;
}
return ERROR;
}

/************************************************************************/
/* 在带头结点的单链线性表L中第i个位置之前插入元素e */
/************************************************************************/
Status ListInsert(LinkList L, int i, ElemType e)
{
int j = 0;
LinkList p = L, s;
while( p && j < i-1) /* 寻找第i-1个结点 */
{
p = p->next;
j++;
}
if( !p|| j > i-1) /* i小于1或者大于表长 */
return ERROR;
s = (LinkList)malloc(sizeof(struct LNode)); /* 生成新结点 */
s->data = e; /* 插入L中 */
s->next = p->next;
p->next = s;
return OK;
}

/************************************************************************/
/* 在带头结点的单链线性表L中，删除第i个元素，并由e返回其值 */
/************************************************************************/
Status ListDelete(LinkList L, int i, ElemType *e)
{
int j = 0;
LinkList p = L, q;
while(p->next && j < i-1) /* 寻找第i个结点，并令p指向其前岖 */
{
p = p->next;
j++;
}
if( !p->next || j > i-1) /* 删除位置不合理 */
return ERROR;
q = p->next; /* 删除并释放结点 */
p->next = q->next;
*e = q->data;
free(q);
return OK;
}

/************************************************************************/
/* 初始条件：线性表L已存在。操作结果：依次对L的每个数据元素调用函数vi() */
/************************************************************************/
void ListTraverse(LinkList L, void(*vi)(ElemType))
{
LinkList p = L->next;
while(p)
{
vi(p->data);
p = p->next;
}
printf("
");
}

/************************************************************************/
/* 初始条件：线性表L已存在。打印链表的data域 */
/************************************************************************/
void ListPrint(LinkList L)
{
LinkList p = L->next;
while(p)
{
printf("%d ", p->data);
p = p->next;
}
printf("
");
}

void printInt(int data)
{
printf("%d ", data);
}

/************************************************************************/
/* 插入排序 */
/************************************************************************/
void ListSort(LinkList L)
{
LinkList first, p, q; //为原链表剩下用于直接插入排序的节点头指针
LinkList t; //临时指针变量：插入节点

//原链表剩下用于直接插入排序的节点链表
first = L->next;

//只含有一个节点的链表的有序链表
L->next = NULL;

//遍历剩下无序的链表
while (first != NULL)
{
//无序节点在有序链表中找插入的位置
for (t = first, q = L; ((q != NULL) && (q->data data)); p = q, q = q->next);

//退出for循环，就是找到了插入的位置
first = first->next;

p->next = t;

//完成插入动作
t->next = q;
}
}

//排序，指针交换法
void ListSort1(LinkList L)
{
LinkList head = L->next;//head指向除头结点以外的链表
LinkList pre_p; //p的前驱结点
LinkList pre_q; //q的前驱结点
LinkList min; //最小的结点
LinkList p, q, temp;

for(p = head; p->next; pre_p = min, p = min->next)
{
//找出最小的结点
for(min = p, q = p; q->next; q = q->next)
{
if(q->next->data data)
{
pre_q = q;
min = q->next;
}
}

//如果最小是自己 就不需要交换
if(min == p) continue;

//如果p是指向head的结点，则链表直接指向min
if(p == head)
L->next = min;
else
pre_p->next = min;

temp = min->next;
if(p->next == min)
{
min->next = p;
p->next = temp;
}
else
{
min->next = p->next;
pre_q->next = p;
p->next = temp;
}
}
}

//排序，数据选择法排序
void ListSort2(LinkList L)
{
LinkList head = L->next;//head指向除头结点以外的链表
LinkList min; //最小的结点
LinkList p, q; //遍历链表指针
int temp;
for (p = head; p->next; p = p->next)
{
//在p指针后的链表选取最小的结点
for (min = p, q = p->next; q; q = q->next)
{
if (q->data data)
min = q;
}

//两者结点值不相等，数据交换
if (min->data != p->data)
{
temp = min->data;
min->data = p->data;
p->data = temp;
}
}
}

void main()
{
LinkList L;
InitList(&L);
ListInsert(L, 1, 6);
ListInsert(L, 1, 3);
ListInsert(L, 1, 67);
ListInsert(L, 1, 2);
ListInsert(L, 1, 15);
ListInsert(L, 1, 13);
ListInsert(L, 1, 10);

ListSort2(L);
ListTraverse(L, printInt);
}

1.3，既然是图，那么D就代表顶点，r代表边，很容易就画出来了

1 读程序段，回答问题
int main(int argc,char *argv[])
{
int c=9,d=0;
c=c++%5;
d=c;
printf("d=%d\n",d);
return 0;
}
a) 写出程序输出
b) 在一个可移植的系统中这种表达式是否存在风险？why?

#include "stdio.h"
int a=0;
int b;
static char c;
int main(int argc,char *argv[])
{
char d=4;
static short e;

a++;
b=100;
c=(char)++a;
e=(++d)++;
printf("a=%d, b=%d, c=%d, d= %d, e=%d",a,b,c,d,e);
return 0;
}
a) 写出程序输出
b) 编译器如果安排各个变量(a,b,c,d)在内存中的布局(eg. stack,heap,data section,bss section),最好用图形方式描述。

2 中断是嵌入式系统中重要的组成部分，这导致了许多编译开发商提供一种扩展：让标准C支持中断，产生了一个新的关键字__interrupt。下面的代码就使用了__interrupt关键字去定义了一个中断服务子程序(ISR),请评论以下这段代码。
__interrupt double compute_area(double radius)
{
double area = PI * radius *radius;
printf("nArea = %f", area);
return area;
}

3 C/C++基础知识问题
a) 关键字volatile在编译时有什么含义?并给出三个不同使用场景的例子(可以伪代码或者文字描述)。
b) C语言中static关键字的具体作用有哪些 ?
c) 请问下面三种变量声明有何区别?请给出具体含义
int const *p;
int* const p;
int const* const p;

4 嵌入式系统相关问题
a) 对于整形变量A=0x12345678,请画出在little endian及big endian的方式下在内存中是如何存储的。
b) 在ARM系统中，函数调用的时候，参数是通过哪种方式传递的?
c) 中断(interrupt,如键盘中断)与异常(exception,如除零异常)有何区别?

5 设周期性任务P1,P2,P3的周期为T1,T2,T3分别为100，150，400；执行时间分别为20，40，100。请设计一种调度算法进行任务调度，满足任务执行周期及任务周期。

6 优先级反转问题在嵌入式系统中是一中严重的问题，必须给与足够重视。
a) 首先请解释优先级反转问题
b) 很多RTOS提供优先级继承策略(Priority inheritance)和优先级天花板策略(Priority ceilings)用来解决优先级反转问题，请讨论这两种策略。

参考答案:
1 5
存在风险，因为c=c++%5;这个表达式对c有两次修改，行为未定义，c的值不确定
int a=0; // data section
int b; // data section
static char c; // BSS
int main(int argc,char *argv[])
{
char d=4; // stack
static short e; // BSS
a++;
b=100;
c=(char)++a;
e=(++d)++;
printf("a=%d, b=%d, c=%d, d= %d, e=%d",a,b,c,d,e);
return 0;
}
a=2,b=100,c=2,d=6,e=5

2 a)ISR不能返回一个值；
b)ISR不能传递参数；
c)浮点一般都是不可重入的；
d)printf函数有重入和性能上的问题。

3 a) 用volatile关键字定义变量，相当于告诉编译器，这个变量的值会随时发生变化，每次使用时都需要去内存里
重新读取它的值，并不要随意针对它作优化。
建议使用volatile变量的场所：
(1) 并行设备的硬件寄存器
(2) 一个中断服务子程序中会访问到的非自动变量（全局变量）
(3) 多线程应用中被几个任务共享的变量
b) 在函数体，一个被声明为静态的变量在这一函数被调用过程中维持其值不变。
在模块内（但在函数体外），一个被声明为静态的变量可以被模块内所用函数访问，但不能被模块外其它函数
访问。它是一个本地的全局变量。
在模块内，一个被声明为静态的函数只可被这一模块内的其它函数调用。那就是，这个函数被限制在声明它的
模块的本地范围内使用。
static全局变量与普通的全局变量有什么区别：static全局变量只初使化一次，防止在其他文件单元中被引用;
static局部变量和普通局部变量有什么区别：static局部变量只被初始化一次，下一次依据上一次结果值；
static函数与普通函数有什么区别：static函数在内存中只有一份，普通函数在每个被调用中维持一份拷贝
c) 一个指向常整型数的指针
一个指向整型数的常指针
一个指向常整型数的常指针
4

a) 0x12345678
little endian big endian 刚好反过来
高地址--〉 0x12 低地址--〉 0x12
0x34 0x34
0x56 0x56
低地址--〉 0x78 高地址--〉 0x78
b)参数<=4时候，通过R0~R3传递，>4的通过压栈方式传递
c) 异常：在产生时必须考虑与处理器的时钟同步，实践上，异常也称为同步中断。在处理器执行到由于编程失误而导致的错误指令时，或者在执行期间出现特殊情况(如缺页)，必须靠内核处理的时候，处理器就会产生一个异常。
所谓中断应该是指外部硬件产生的一个电信号，从cpu的中断引脚进入，打断cpu当前的运行；
所谓异常，是指软件运行中发生了一些必须作出处理的事件，cpu自动产生一个陷入来打断当前运行，转入异常处理流程。
异步与同步的区别`
5

6 高优先级任务需要等待低优先级任务释放资源，而低优先级任务又正在等待中等优先级任务的现象叫做优先级反转
优先级继承策略(Priority inheritance):继承现有被阻塞任务的最高优先级作为其优先级，任务退出临界区，恢
复初始优先级。
优先级天花板策略(Priority ceilings):控制访问临界资源的信号量的优先级天花板。
优先级继承策略对任务执行流程的影响相对教小，因为只有当高优先级任务申请已被低优先级任务占有的临界资源
这一事实发生时，才抬升低优先级任务的优先级

---

哈尔滨市17144745198： 新学菜鸟请教“两道简单的数据结构实验题”,高手请进,在线等,急求证!~~ - ？
咸曲丽泉： 1 读程序段,回答问题 int main(int argc,char *argv[]) { int c=9,d=0; c=c++%5; d=c; printf(＂d=%d\n＂,d); return 0; } a) 写出程序输出 b) 在一个可移植的系统中这种表达式是否存在风险?why?#include ＂stdio.h＂ int a=0; int b; static char c; int ...

哈尔滨市17144745198： 请教两个超简单的数据结构题? - ？
咸曲丽泉： (1) 1 3 2 4 按照后进先出的原则,1先进栈马上又出栈,第一个数为1,之后2,3先后进栈,出来是后进先出,所以3出来后才是2,第二三个数为3,2,之后4先进栈后又出栈,第四个数是4,所以得到出栈序列为1 3 2 4 (2)是不能得到的.原因是上式...

哈尔滨市17144745198： (求助!)解两道数据结构题~! - ？
咸曲丽泉： 1、由于对称性a85与a58是相同的,由于按照行存储,第一行存储10个;第二行存储9个,开始元素为a22;第三行存储8个,开始元素为a33;……;第五行开始元素为:a55,所以a58在地四个 故 总的存储为:10+9+8+7+4=38 2、由于3^5=243,3^6=243*3>244,所以为6层

哈尔滨市17144745198： 请教两个数据结构的问题.求大神 给出答案和解释~ - ？
咸曲丽泉： 第一题C.查找序列是二分的过程.比如D选项,查找F,则F>D,向右走到G,FE,向右走找到F.C选项不符合这个逻辑,查找F,已知F>D,是不可能向左走去查找B的.第二题B.我的证明:设N[h]表示高度为h的AVL树最少含有的节点数,则...

哈尔滨市17144745198： 两道数据结构选择题求详解 - ？
咸曲丽泉： 2.答案,A,这个是根据循环队列的定义来了,教材在处理循环队列的溢出时,是空一位不用,所以队列中元素的个数(rear-front+m)%m;为什么+m是因为可能出现rear-front<0;3.对于空队列刚开始时front=0;这个没问题的.队列非空时front和rear分别指向队头元素和队尾元素,这与书中的队尾指针指向即将要入队的位置是不同的,所以队中元素个数的计算方法为:(rear-front+1+n)%n;front=0;刚开始队中无元素,所以rear=n-1;所以选B

哈尔滨市17144745198： 请教几道数据结构题目？
咸曲丽泉： 1.D 2.

哈尔滨市17144745198： 数据结构的菜鸟问题？
咸曲丽泉： K就是数据的集合,比如K={k1,k2...} R就是关系的意思,关系集合,r是R中间的一个关系,r应该是∈KxK 关系的,就是r是一个(k,k)关系

哈尔滨市17144745198： 数据结构菜鸟求助... - ？
咸曲丽泉： 完全 可以用L.elem[L.length-1]来确定,只不过表尾位置用L.elem+L.length-1时,在访问元素时,写起来方便,程序也简洁

哈尔滨市17144745198： 数据结构C语言简单小程序,求注解,本人菜鸟入门. - ？
咸曲丽泉： #include int main() { int a[10],i,max; scanf(＂%d＂,&a[0]); max = a[0]; for ( i = 0 ; imax ) max = a[i]; } printf(＂the max one is %d\n＂,max); return 0; }

哈尔滨市17144745198： 帮我看一下这个数据结构的最简单的程序 我是菜鸟,写的详细点 - ？
咸曲丽泉： #include <stdio.h>#include <stdlib.h>#define TRUE 1-------定义最终变量(是不可以修改的变量),必须大写#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2#define LIST_INIT_SIZE 100 #define ...