数据结构车厢调度

第一篇：数据结构车厢调度

#include #include

#define STACK_INIT_SIZE 20 #define STACK_SIZE

typedef struct { int *base;int *top;int stacksize;} SqStack;

bool InitStack(SqStack &S){ // 初始化栈

S.base =(int *)malloc(STACK_INIT_SIZE*sizeof(SqStack));if(!S.base)

exit(0);S.top = S.base;S.stacksize = STACK_INIT_SIZE;return true;} // InitStack

bool GetTop(SqStack S, int &e){ // if(S.top == S.base)

return false;e = *(S.topS.base >= S.stacksize){

S.base =(int *)realloc(S.base,(S.stacksize + STACK_SIZE)*sizeof(SqStack));

if(!S.base)

exit(0);

S.top = S.base + S.stacksize;

S.stacksize += STACK_SIZE;} *S.top++ = e;return true;} // Push

bool Pop(SqStack &S, int &e){ if(S.top == S.base)

return false;e = *--S.top;return true;}

///////////////////////////////////////////////////////////////////////////////////

bool Judement(int *Array, int n){ int Count = 0;for(int i = 1;i <= 2*n;i++)if(Array[i] == 1)

Count++;if(Count == n && Array[2*n] == 0)

一个是出栈

return true;else

return false;}

void operation(SqStack S, int n){ // n代表获得数量，分别标记为1,2,3....n int *Array;int nCount = 0, e;Array =(int *)malloc((2 * n + 1)* sizeof(int));

if(!Array)

exit(0);// 将其初始化为1234..n的形式

for(int i = 1;i <= 2*n;i++)

if(i%2 == 1)

Array[i] = 1;

else

Array[i] = 0;

while(1){

if(Judement(Array, n))

{

nCount = 0;

for(int i = 1;i <= 2*n;i++)

{

if(Array[i] == 1)

Push(S, ++nCount);

// 必须保证最后

//从1开始

// 代表入栈

// 代表出栈

else

{

Pop(S, e);

printf(“%d ”, e);

}

}

printf(“n”);

}

Array[2*n] += 1;

// 最后一个自增1，等于2时本为为0前一位加1

for(int i = 2*n;i >= 1;i--)

{

if(Array[i] == 2)

{

Array[i-1] += 1;

Array[i] = 0;

}

}

nCount = 0;

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

{

if(Array[i] == 1)

nCount++;

}

if(nCount == n && Array[2*n] == 1)

break;

// 退出循环的条件为前n个为1同时最后一位也为1 } }

void main(){ // 这个是在左边有1,2,3...n节车厢的情况，得出在右边所有的情况

SqStack S;InitStack(S);int n;scanf_s(“%d”, &n);if(n <= 1){

printf(“输入数字小于1”);

return;} operation(S, n);

第二篇：数据结构 任务调度 实验报告

实验报告

实验名称：表达式求值 任务调度 实验类型：综合性实验 班级：

学号：

姓名：

实验日期：2014.5.28

表达式求值 1.问题描述

表达式是数据运算的基本形式。人们的书写习惯是中缀式，如：11+22*(7-4)/3。中缀式的计算按运算符的优先级及括号优先的原则，相同级别从左到右进行计算。表达式还有后缀式（如：22 7 4-* 3 / 11 +）和前缀式（如：+ 11 / * 22 – 7 4 3）。后缀表达式和前缀表达式中没有括号，给计算带来方便。如后缀式计算时按运算符出现的先后进行计算。本设计的主要任务是进行表达式形式的转换及不同形式的表达式计算。2.数据结构设计

建立栈，算数表达式的计算往往是通过栈来实现的，所以建立结构体，如下 typedef struct{ float *base;//栈底指针

float *top;//栈顶指针

int stacksize;}SqStack_f;//实数栈

typedef struct{ char *base;char *top;int stacksize;}SqStack_c;//字符栈

3.算法设计

void Translate(char *s1)

//中缀转后缀

{ char s2[80];SqStack_c Optr;int i=0,j=0;char t;InitStack_c(&Optr);

//初始化一个运算符栈

Push_c(&Optr,'(');while(s1[i]!='#'){

if(s1[i]>='0' && s1[i]<='9' || s1[i]=='.')

{

s2[j++]=s1[i];

if((s1[i+1]<'0' || s1[i+1]>'9')&& s1[i+1]!='.')

s2[j++]=' ';

//将完整的字符型数字存入 然后存入空格

}

else

switch(s1[i])

{

case'(':Push_c(&Optr,s1[i]);break;

//遇到左括号 将其压栈

case')':Pop_c(&Optr,&t);

//遇到右括号时

将栈内运算符弹出并压入数组s2 直到遇到左括号

while(t!='(')

{

s2[j++]=t;

Pop_c(&Optr,&t);

}

break;

default:while(GetTop_c(&Optr,&t),precede(t,s1[i]))//与栈顶元素比较 若栈顶元素级别高 则进行以下循环

{

Pop_c(&Optr,&t);

s2[j++]=t;

//弹出栈顶元素 并存入数组s2

}

Push_c(&Optr,s1[i]);

//将当前遇到运算符压栈

}

i++;} Pop_c(&Optr,&t);while(t!='('){

s2[j++]=t;

Pop_c(&Optr,&t);} for(i=0;i

s1[i]=s2[i];s1[i]='#';s1[i+1]='';}

void Calculate(SqStack_f *s,char *s2)

//计算表达式的值

{ float m,x,y,z;

int p,i=0,j=0;while(s2[i]!='#'){ if(s2[i]>='0' && s2[i]<='9' || s2[i]=='.'){

m=0;

while(s2[i]!=' ' && s2[i]!='.')

m=m*10+(float)(s2[i++]-'0');

if(s2[i]=='.')

{

j=0;i++;

while(s2[i]!=' ')

{

m=m*10+(float)(s2[i++]-'0');

j++;

}

while(j>0)

{

m/=10;

j--;

}

}

i++;

Push_f(s,m);

GetTop_f(s,&m);} else {

Pop_f(s,&x);

Pop_f(s,&y);

switch(s2[i])

{

case '+':z=y+x;Push_f(s,z);break;

case '-':z=y-x;Push_f(s,z);break;

case '*':z=y*x;Push_f(s,z);break;

case '/':if(x==0)

{

printf(“表达式出错，除数为‘0’，无意义n”);

exit(1);

}

else

{

z=y/x;

Push_f(s,z);

break;

}

case '%':if(x==0||(int)x!=x||(int)y!=y)

{

printf(“表达式出错n”);

exit(1);

}

else

{

p=(int)y%(int)x;

Push_f(s,p);

break;

}

}

i++;} } }

int precede(char Top_char,char s1_char)

//比较运算符的优先级

{ int i,pre[2];char op[2];op[0]=Top_char;op[1]=s1_char;for(i=0;i<2;i++)

switch(op[i])

{

case'(':case')':pre[i]=0;break;

case'+':case'-':pre[i]=1;break;

case'*':case'/':case’%’:pre[i]=2;break;

} if(pre[0]>=pre[1])

//栈顶元素top char>=s1 char就返回1

return 1;else

return 0;}

void convert(char *s,char *output)

//中缀转前缀

{

int j=0;int top=0;

char stack[50];strcpy(output,“");

for(int i=strlen(s)-1;i>=0;)

{

if((s[i]>=48&&s[i]<=57)||s[i]=='.')

output[j++]=s[i];

if(s[i]==')')

{

top++;

stack[top]=s[i];

}

while(s[i]=='+'||s[i]=='-'||s[i]=='*'||s[i]=='/'||s[i]=='%')

{

output[j++]=' ';

if(top==0||stack[top]==')'||precede(s[i],stack[top]))

{

top++;

stack[top]=s[i];

break;

}

else

{

output[j++]=stack[top];

top--;

}

}

if(s[i]=='(')

{

while(stack[top]!=')')

{

output[j++]=stack[top];

top--;

}

top--;

}

i--;

}

while(top!=0)

{

output[j++]=stack[top];

top--;

}

}

4.界面设计

printf(”请输入算术表达式，结束前请输入#号！n“);

5.运行、测试与分析

6、实验收获与思考

1．熟练掌握栈的定义及使用。

2．了解表达式求值的转换算法。设计前、后缀表达式求值算法。

3．设计操作数为多位实数，操作符为加、减、乘、除、求模的中缀表达式求值算法。定义算数符号的优先级。

7、源代码

#include #include #include #include #include #define TTACK_INIT_SIZE 100 #define STACKINCREMENT 10

typedef struct{ float *base;float *top;int stacksize;}SqStack_f;//实数栈

typedef struct{ char *base;char *top;int stacksize;}SqStack_c;//字符栈

void InitStack_f(SqStack_f *s){ s->base=(float *)malloc(TTACK_INIT_SIZE*sizeof(float));if(!s->base)

exit(1);s->top=s->base;s->stacksize=TTACK_INIT_SIZE;} void InitStack_c(SqStack_c *s){ s->base=(char *)malloc(TTACK_INIT_SIZE*sizeof(char));if(!s->base)

exit(1);s->top=s->base;s->stacksize=TTACK_INIT_SIZE;} void GetTop_f(SqStack_f *s,float *e){ if(s->top==s->base){

printf(”ERROR!n“);

exit(1);} *e=*(s->top-1);} void GetTop_c(SqStack_c *s,char *e){ if(s->top==s->base){

printf(”ERROR!n“);

exit(1);} *e=*(s->top-1);} void Push_f(SqStack_f *s,float e){ if(s->top-s->base>=s->stacksize){

s->base=(float *)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(float));

if(!s->base)

{

printf(”OVERFLOW!n“);

exit(1);

}

s->top=s->base+s->stacksize;

s->stacksize+=STACKINCREMENT;} *s->top++=e;} void Push_c(SqStack_c *s,char e){ if(s->top-s->base>=s->stacksize){

s->base=(char *)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(char));

if(!s->base)

{

printf(”OVERFLOW!n“);

exit(1);

}

s->top=s->base+s->stacksize;

s->stacksize+=STACKINCREMENT;} *s->top++=e;} void Pop_f(SqStack_f *s,float *e){ if(s->top==s->base)

exit(1);*e=*--s->top;} void Pop_c(SqStack_c *s,char *e){ if(s->top==s->base)

exit(1);*e=*--s->top;} int precede(char Top_char,char s1_char)

//比较运算符的优先级

{ int i,pre[2];char op[2];op[0]=Top_char;op[1]=s1_char;for(i=0;i<2;i++)

switch(op[i])

{

case'(':case')':pre[i]=0;break;

case'+':case'-':pre[i]=1;break;

case'*':case'/':case'%':pre[i]=2;break;

} if(pre[0]>=pre[1])

//栈顶元素top char>=s1 char就返回1

return 1;else

return 0;} void Translate(char *s1)

//中缀转后缀

{ char s2[80];SqStack_c Optr;int i=0,j=0;char t;InitStack_c(&Optr);

//初始化一个运算符栈

Push_c(&Optr,'(');while(s1[i]!='#'){

if(s1[i]>='0' && s1[i]<='9' || s1[i]=='.')

{

s2[j++]=s1[i];

if((s1[i+1]<'0' || s1[i+1]>'9')&& s1[i+1]!='.')

s2[j++]=' ';

//将完整的字符型数字存入 然后存入空格

}

else

switch(s1[i])

{

case'(':Push_c(&Optr,s1[i]);break;

//遇到左括号 将其压栈

case')':Pop_c(&Optr,&t);

//遇到右括号时

将栈内运算符弹出并压入数组s2 直到遇到左括号

while(t!='(')

{

s2[j++]=t;

Pop_c(&Optr,&t);

}

break;

default:while(GetTop_c(&Optr,&t),precede(t,s1[i]))//与栈顶元素比较 若栈顶元素级别高 则进行以下循环

{

Pop_c(&Optr,&t);

s2[j++]=t;

//弹出栈顶元素 并存入数组s2

}

Push_c(&Optr,s1[i]);

//将当前遇到运算符压栈

}

i++;} Pop_c(&Optr,&t);while(t!='('){

s2[j++]=t;

Pop_c(&Optr,&t);} for(i=0;i

s1[i]=s2[i];s1[i]='#';s1[i+1]='';} void Calculate(SqStack_f *s,char *s2)

//计算表达式的值

{ float m,x,y,z;int p,i=0,j=0;while(s2[i]!='#'){

if(s2[i]>='0' && s2[i]<='9' || s2[i]=='.')

{

m=0;

while(s2[i]!=' ' && s2[i]!='.')

m=m*10+(float)(s2[i++]-'0');

if(s2[i]=='.')

{

j=0;i++;

while(s2[i]!=' ')

{

m=m*10+(float)(s2[i++]-'0');

j++;

}

while(j>0)

{

m/=10;

j--;

}

}

i++;

Push_f(s,m);

GetTop_f(s,&m);

}

else

{

Pop_f(s,&x);

Pop_f(s,&y);

switch(s2[i])

{

case '+':z=y+x;Push_f(s,z);break;

case '-':z=y-x;Push_f(s,z);break;

case '*':z=y*x;Push_f(s,z);break;

case '/':if(x==0)

{

printf(”表达式出错，除数为‘0’，无意义n“);

exit(1);

}

else

{

z=y/x;

Push_f(s,z);

break;

}

case '%':if(x==0||(int)x!=x||(int)y!=y)

{

printf(”表达式出错n“);

exit(1);

}

else

{

p=(int)y%(int)x;

Push_f(s,p);

break;

}

}

i++;} } } void result(SqStack_f *s){ float v;GetTop_f(s,&v);printf(”The final result is:%gn“,v);}

void convert(char *s,char *output)

//中缀转前缀

{

int j=0;int top=0;

char stack[50];strcpy(output,”“);

for(int i=strlen(s)-1;i>=0;)

{

if((s[i]>=48&&s[i]<=57)||s[i]=='.')

output[j++]=s[i];

if(s[i]==')')

{

top++;

stack[top]=s[i];

}

while(s[i]=='+'||s[i]=='-'||s[i]=='*'||s[i]=='/'||s[i]=='%')

{

output[j++]=' ';

if(top==0||stack[top]==')'||precede(s[i],stack[top]))

{

top++;

stack[top]=s[i];

break;

}

else

{

output[j++]=stack[top];

top--;

}

}

if(s[i]=='(')

{

while(stack[top]!=')')

{

output[j++]=stack[top];

top--;

}

top--;

}

i--;

}

while(top!=0)

{

output[j++]=stack[top];

top--;

}

}

int main(){

int i;SqStack_f stack;char str[80];char output[80];

printf(”请输入算术表达式，结束前请输入#号！n“);

gets(str);

InitStack_f(&stack);

printf(”前缀表达式为：n“);

convert(str,output);

for(i=strlen(output)-1;i>=0;i--)

printf(”%c“,output[i]);

printf(”n“);

Translate(str);

printf(”后缀表达式为：n“);

puts(str);

Calculate(&stack,str);

result(&stack);}

任务调度 1.问题描述

多用户多任务操作系统中，多个任务同时共享计算机系统资源。为了使多个任务均能够顺利执行，操作系统要按一定的原则对它们进行调度，使它们按一定的次序进行。设只有一个CPU，现有多个任务，它们需要CPU服务的时间已知。在下列假设下，按平均等待时间最短为原则，设计算法求出任务的执行顺序。

 忽略任务提交的时间差，即认为各任务同时提交。 各任务不同时提交。2.数据结构设计

struct task { }T[100];int order,ne,t,sta,wa,end;//任务顺序，需要时间，提交时间，开始时间，等待时间，结束时间

3.算法设计 同时

int cmp(const void *a,const void *b)

//相同时间排序

{ return(*(struct task *)a).ne>(*(struct task *)b).ne;}

void sametime(int n){ double sum,sum2;int i;for(i=0;i

{

printf(”请输入第%d个任务所需要的时间n“,i+1);

T[i].t=0;

scanf(”%d“,&T[i].ne);

T[i].order=i+1;} t=0;sum=0;printf(”序号 开始时间 等待时间

结束时间n“);for(i=0;i

{

printf(”%-7d“,i+1);

printf(”%-7d“,t);

printf(”%-8d“,t);

t+=T[i].ne;

printf(”%-8d“,t);

printf(”n“);

sum+=((n-i-1)*T[i].ne);} printf(”n“);printf(”序号 开始时间 等待时间

结束时间n“);qsort(T,n,sizeof(T[0]),cmp);//按最短时间排序

t=0;sum2=0;for(i=0;i

{

printf(”%-7d“,T[i].order);

printf(”%-7d“,t);

printf(”%-8d“,t);

t+=T[i].ne;

printf(”%-8dn“,t);

printf(”n“);

sum2+=((n-i-1)*T[i].ne);} printf(”顺序执行等待平均时间为

%.3lfn“,sum/n);} printf(”最短等待平均时间为

%.3lfn“,sum2/n);不同时

int comp(const void *a,const void *b)//不同时间排序

{ return T[*(int *)a].ne>T[*(int *)b].ne;}

void dele(){ int i;printf(”%-10d%-10d%-10d%-20dnn“,T[que[0]].order,T[que[0]].sta,T[que[0]].wa,T[que[0]].end);for(i=0;i

que[i]=que[i+1];rear--;}

int check(int num1){ int i;T[que[0]].ne--;if(T[que[0]].ne<=0){

T[que[0]].end=t;

dele();

for(i=0;i

T[que[i]].wa++;

return 1;} else {

for(i=1;i

T[que[i]].wa++;

return 0;} }//时间段移动查寻当前队列

void insert(int n){ int i,rec;for(i=0;i

if(T[que[i]].ne>T[n].ne)

break;} rec=i;for(i=rear;i>rec;i--)

que[i]=que[i-1];que[rec]=n;

rear++;}

void difftime(int n)//输入本来按照先后顺序

{ int tdiff;double sum;int i,j;rear=0;sum=0;for(i=0;i

{

printf(”请输入第%d个任务提交时刻和第%d个任务执行时间n“,i+1,i+1);

scanf(”%d%d“,&T[i].t,&T[i].ne);

T[i].order=i+1;

T[i].sta=-1;T[i].end=-1;T[i].wa=0;} printf(”序号

开始时间

等待时间

结束n“);que[0]=0;rear=1;T[0].sta=0;i=0;t=0;j=1;while(i

t++;//时间移动

i+=check(tdiff);//时间移动后检查是否有完成的任务，并且就算等待时间

if(t>=T[j].t&&j

{

insert(j);//把任务插入到队列

j++;

qsort(que,rear,sizeof(que[0]),comp);//按时间长短排序

}

if(T[que[0]].sta==-1)//给队列最前点赋起始值

T[que[0]].sta=t;} for(i=0;i

sum+=T[i].wa;printf(”平均等待时间为 %.3lfsnn“,sum/n);

} 4.界面设计

printf(”请输入任务数n“);

5.运行、测试与分析

同时

不同时

6.实验收获及思考

写出一个程序不仅仅是算法的考究，更是细节的较量。

从理论到实践，我学到很多很多的东西。不仅巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的内容。

7、源代码

同时

#include #include #include int que[100],rear=0,t=0;struct task { int order,ne,t,sta,wa,end;//任务顺序，需要时间，提交时间，开始时间，等待时间，结束时间

}T[100];int cmp(const void *a,const void *b)

//相同时间排序

{ return(*(struct task *)a).ne>(*(struct task *)b).ne;} void sametime(int n){ double sum,sum2;int i;for(i=0;i

printf(”请输入第%d个任务所需要的时间n“,i+1);

T[i].t=0;

scanf(”%d“,&T[i].ne);

T[i].order=i+1;} t=0;sum=0;printf(”序号 开始时间 等待时间

结束时间n“);for(i=0;i

{

printf(”%-7d“,i+1);

printf(”%-7d“,t);

printf(”%-8d“,t);

t+=T[i].ne;

printf(”%-8d“,t);

printf(”n“);

sum+=((n-i-1)*T[i].ne);} printf(”n“);printf(”序号 开始时间 等待时间

结束时间n“);qsort(T,n,sizeof(T[0]),cmp);//按最短时间排序

t=0;sum2=0;for(i=0;i

{

printf(”%-7d“,T[i].order);

printf(”%-7d“,t);

printf(”%-8d“,t);

t+=T[i].ne;

printf(”%-8dn“,t);

printf(”n“);

sum2+=((n-i-1)*T[i].ne);} printf(”顺序执行等待平均时间为

%.3lfn“,sum/n);printf(”最短等待平均时间为

%.3lfn“,sum2/n);} int main(){ int n;printf(”请输入任务数:n“);while(scanf(”%d“,&n)!=EOF){

if(n<=0)

{

printf(”输入错误,程序结束“);

break;

}

sametime(n);} system(”pause“);return 0;}

不同时

#include #include #include int que[100],rear=0,t=0;struct task { int order,ne,t,sta,wa,end;//任务顺序，需要时间，提交时间，开始时间，等待时间，结束时间

}T[100];int comp(const void *a,const void *b)//不同时间排序

{ return T[*(int *)a].ne>T[*(int *)b].ne;} void dele(){ int i;printf(”%-10d%-10d%-10d%-20dnn“,T[que[0]].order,T[que[0]].sta,T[que[0]].wa,T[que[0]].end);for(i=0;i

que[i]=que[i+1];rear--;} int check(int num1){ int i;T[que[0]].ne--;if(T[que[0]].ne<=0){

T[que[0]].end=t;

dele();

for(i=0;i

T[que[i]].wa++;

return 1;} else {

for(i=1;i

T[que[i]].wa++;

return 0;} }//时间段移动查寻当前队列

void insert(int n){ int i,rec;for(i=0;i

if(T[que[i]].ne>T[n].ne)

break;} rec=i;for(i=rear;i>rec;i--)

que[i]=que[i-1];que[rec]=n;

rear++;} void difftime(int n)//输入本来按照先后顺序

{ int tdiff;double sum;int i,j;rear=0;sum=0;for(i=0;i

{

printf(”请输入第%d个任务提交时刻和第%d个任务执行时间n“,i+1,i+1);

scanf(”%d%d“,&T[i].t,&T[i].ne);

T[i].order=i+1;

T[i].sta=-1;T[i].end=-1;T[i].wa=0;} printf(”序号

开始时间

等待时间

结束n“);que[0]=0;rear=1;T[0].sta=0;i=0;t=0;j=1;while(i

t++;//时间移动

i+=check(tdiff);//时间移动后检查是否有完成的任务，并且就算等待时间

if(t>=T[j].t&&j

{

insert(j);//把任务插入到队列

j++;

qsort(que,rear,sizeof(que[0]),comp);//按时间长短排序

}

if(T[que[0]].sta==-1)//给队列最前点赋起始值

T[que[0]].sta=t;} for(i=0;i

sum+=T[i].wa;printf(”平均等待时间为 %.3lfsnn“,sum/n);

} int main(){ int n;printf(”请输入任务数n“);while(scanf(”%d“,&n)!=EOF){

if(n<=0)

{

printf(”输入错误,程序结束“);

break;

}

difftime(n);} system(”pause");return 0;}

第三篇：硬卧车厢读后感

上周四（12月1日）拍了西门媚短篇小说集《硬卧车厢》，看她总不在线的样子，以为不知道何时能收到，硬卧车厢读后感。其实也不急，是准备春节假期出行时路上看的书。没想到4号就到手了。

书的手感象以前单位里偶尔发给大家学习的政治书，生硬、冷淡。半边白板，半边灰突突的风景，象是太过漫长的旅途中正在坏掉的心情。

几年前我看到西门媚的博客，那时文章要多些，记录些生活中的花啊草，有点小资。后来针砭时弊，和保安大妈喝茶。再后来说写小说了，录了些她的朋友写的书评。西门媚的博客少有更新，我翻收藏夹时看到她的链接就会进去看看。上周开始为出行采购，随手拍了一本《硬卧车厢》。

这本书如果放在书店的书架上，会有人拿起来翻么？

这是本不讨人喜欢的书，不亲和。当然我是指封面。而且，我们这里的书店，书是用热缩膜包好的，反正是爱买不买。而我总觉得撕掉那膜有点费事也有点不礼貌。但它特别。我想会有人拿起来看看，再放下。放下是正常的—— 陈洁在书评中说“前些天买到后还没看呢”正是暗合此意，不放下而拿去付了款，总觉得不合常理。

因为不是准备马上看的，所以快快地付了款，写了友好的评价，说作者写了签名给我，谢谢。后来看书看到一半，去看她朋友写的书评，才发现上面清楚地写着“可以订制签名”。

本来是准备春节看的书，还是翻开，读后感《硬卧车厢读后感》。我看书慢，在每天固定的时间看。现在看完了。

故事写得清朗，象十一月下午的阳光。大约只有到十一月还穿着衬衣的人才感受得到那样的阳光。

以我喜欢的程度排序，依次是：《只有味蕾记得住》；《铁路边上》《不知火》；《亲爱的史密斯》《还记得李志吗》；《硬卧车厢》《车上情书》；《杜微微的四月》《收藏者朱玉》。

如果周朗改变得不是那么彻底，也许他会和小朦好下去。

而如果周朗不做彻底的改变，他内心里一定会一直痛苦着。在现实中的我和理想中的我 这两个角色中不断切换，每天都要经受“变身”时的巨痛。这只有“暴火强尼”能做得到。

小朦爱周朗，这本书里我只觉得这段爱情是真实的。在报摊前静静地等待着周朗的出现，那种安心的样子，好象已经可以到“永远”了。

所以就觉得可惜。男生总是很粗心的，说话得罪了人自己还不定知道；丢三落四，丢了小情人也丢了原来的自己。是不是根基不够牢呢？以或是原本就不是一路人。总之我希望周朗是内心纯净，外表圆熟，经历痛苦还能保全旧我。穷也要做男人，然后演绎出许多勇敢的故事。

这本书还让我想起一些生活的意义。好吃的菜、有趣的人、舞蹈、绘画和碟等等，都可以收藏起来，这个就是基础。然后，自己去创造这些有意义的东西，做为自己存在的意义。

这本书是本好书，因为我看了两遍仍觉得好看。是我喜欢的风格。

这本书除了内容什么都没有。常理下该有的也没有。那个封面硬是内容的一部分。

“愿这本书带给你一段美好的旅程。——西门媚”——老婆问：“你说了你是准备路上看的么？”

我说：“没有。”

“12月2日，正好是我生日咧。”

我说：“好巧。”

第四篇：微笑在车厢

关于认真开展“微笑在车厢”创先争优活动方案

二0一0年六月二十五日

为进一步抓好科学发展观学习实践活动整改落实工作，推进企业党建工作创新，加强党员队伍和职工队伍建设，提高客运从业人员的整体素质，提高客运服务质量，树立文明礼貌，优质服务的窗口新形象，更好地为人民群众服务，促进客运生产的发展，从二0一0年七月一日起至二0一二年六月三十日止，开展 “微笑在车厢” 创先争优活动，制订活动方案如下：

一、指导思想：

坚持以邓小平理论、“三个代表”重要思想为指导，认真贯彻十七大和十七届三中、四中全会精神，深入贯彻科学发展观，以科学发展观为引领，以旅客满意为目标，站在“为湘桥科学发展、服务旅客群众”的高度，把开展创先争优活动与“微笑在车厢”活动结合起来，与加强党政领导班子建设和提高职工队伍素质结合起来，与推进客运质量提升和促进客运生产发展结合起来，以争做“四优”共产党员为载体，深化“四好”领导班子建设，争创“四强”“五个好”党组织，推进党建工作创新，加强党团员队伍、职工队伍建设，为旅客提供安全方便、整洁舒适、文明和谐的出行环境，增强企业经济活力和可持续发展的能力，提高企业经济效益和社会效益。

二、目的要求：

通过“微笑在车厢” 创先争优活动，开展“三亮三比三

创”（亮身份,比形象,创优质服务标兵；亮承诺,比业绩,创旅客满意窗口；亮标准,比创新,创一流品牌）。发挥“共产党员示范岗”作用，提高企业经营管理水平，提升基层党组织和党员为旅客服务水平，树立争创文明客运站、文明站务员、文明售票员新风，文明司乘员，提高客运从业人员的整体素质，建设一支高素质的客运队伍，创造文明礼貌、安全舒适、优质高效的服务体系，树立文明礼貌优质服务的客运企业新形象，促进客运生产发展。

具体为：

1，推出“一瓶水、一句欢迎词、一个笑脸、一站式服务”的“四个一”服务模式（给旅客送上一瓶水，递上一句话“你好！欢迎光临”“你好！欢迎你乘坐本次班次，我们将竭诚为您服务”，和电话订票、上门接客、代办托运、随车服务等 一站式服务），提升服务理念和服务意识，完善服务功能，提高综合服务质量。在车厢、售票窗口、候车室等处设立“党团员微笑服务示范岗”，放置标牌，在车辆张贴笑脸标志、“安全告知书”，全力打造“微笑在车厢”，构建“微笑服务” 和谐氛围。

2，加大行业陋习整治，提升文明服务水平。要落实行业服务规范，按照交通部“三优三化”的目标，加强站场管理，全面推广文明服务用语，强化行业陋习和车辆环境“脏乱差”不文明行为的专项整治；

要提倡党团员和干部职工采用“四心工作法”（即“服务乘客要耐心，关爱乘客要贴心，帮助乘客要真心，照顾特需乘客要热心”），开展微笑服务，弘扬行业文明新风。制作微笑徽章下发给党团员和干部职工，用太阳般温暖可爱的小笑脸，提醒和激励所有员工干部，时刻遵守微笑服务的要求，时刻展现微笑服务的精神，时刻用微笑的服务迎接旅客。

要做好旅客服务设施检查，整治“脏乱差”。要做好候车室卫生工作，设置旅客问询处，茶水供应处，充分发挥“青年文明号”的作用，为旅客提供交通安全常识宣传、交通信息查询等方面的服务。对各售票窗口，要加强保安值班工作，严防扒窃和各种治安事故；要设立和公布24小时举报投诉电话，接受旅客和社会的监督；要加强运输调度指挥，保证车辆正班、正点，提高班车始发正点率。

3，净化车辆环境，靓丽行业形象。全面清理和规范车辆，标志标识，整治车容车貌，严格执行车辆进站后、出车前检查制度，为旅客提供整洁、清新、舒适的乘坐环境。

4，树立服务品牌，凸现服务亮点。进一步拓展微笑服务车队的覆盖面，打造微笑服务精品示范线路，推行特色服务，树立行业服务典范，凸显交通服务新亮点。

5，改善消费环境，提升服务功能。开通网上定、售票服务，增加城市周边售票网点，努力推行联网刷卡消费，延伸客运服务范围，方便旅客群众出行乘车。

6，坚持标本兼治，依靠科技进步，创造平安出行环境。要狠抓安全生产，全面使用汽车GPS监控系统，做好全天候值班监控，提升行业科技管理和服务水平，遏制车辆违章超速和疲劳驾车，杜绝安全生产责任事故的发生；要加强治安防控，打击扒窃行为，严格三品检查，保证站场、候车室的安全；要严格实行车辆出站刷卡管理，全面推进信息化、智能化建设，全力创造平安乘车环境。

三、活动领导和机构：

为加强“微笑在车厢” 创先争优活动的领导，现成立“微笑在车厢” 创先争优活动领导小组。领导小组成员下设办公室，负责活动的具体工作。

四、参加活动对象：

全体党团员及客运工作人员

五、活动时间：

自二0一0年七月一日起至二0一二年六月三十日。

六、活动方法和步骤： 成立以各部门第一把手为小组长的“微笑服务月”领导小组，召开动员大会，传达开展“微笑在车厢” 创先争优活动的文件精神，把“微笑在车厢” 创先争优活动作为培养自身职业修养的方式积极投身到活动中，让“微笑在车厢” 创先争优活动精神深入到每一位员工的思想中，让广大员工深刻领悟微笑服务的真谛；

通过板报、宣传栏等形式，进行广泛宣传，形成“微笑服务”从我做起、从现在做起、从每项工作做起、从每个细节做起”的浓厚氛围和“崇尚微笑服务，在员工通道或活动区域设立了“微笑在车厢”专栏，制作“今天你微笑了吗？”等各种充满人性化的宣传标语和图画，张贴在员工经常经过的地方，广泛宣传、营造氛围，促使员工时刻提醒自己保持职业化的微笑，时刻纠正自己不得当的行为，逐渐把微笑训练为一种职业习惯。

组织党团员和干部职工学政治、讲思想，开展思想道德教育，文化素质教育和业务技术培训，学习企业规章制度和岗位责任制度，按“三优三化”的要求，通过“微笑在车厢” 创先争优服务活动，比学赶帮、争做贡献，争当先进，争创文明优秀司乘、文明优秀站长、副站长、文明优秀站务员、售票员、后勤、保卫人员。不断完善服务设施，抓好公共设施卫生工作，提高服务质量，以全新的管理和优质的服务，为旅客提供一个整洁、美观、舒适的旅行环境。

活动步骤：

第一阶段：二0一0年六月二十五日至六月三十日，成立机构，制订方案。

第二阶段：二0一0年七月一日至七月十日，学习动员阶段。

第三阶段：二0一0年七月十一日至二0一二年五月三十

日开展活动、检查、整改阶段，建立健全各项有关规章制度。

第四阶段：二0一二年六月一日至六月三十日，评比总结阶段，表彰先进，树立样板，巩固活动成效。

七、奖惩办法： 为调动广大员工参与“微笑在车厢” 创先争优活动的积极性，评优学优，树立榜样和典范，公司每季度举行“微笑大使”“服务之星”的评选活动。在候车室设立投票箱、车上发放征求旅客意见表，由旅客投票，推选微笑服务做的好的员工。对“微笑大使”“服务之星”给予了物质和精神上的奖励。

第五篇：数据结构参考材料

数据结构参考题目

一、选择

1.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（）

A.栈 B.队列 C.树 D.图 2.下面程序段的时间复杂度为（）for(i=0;inext =HL;B.P->next=HL;HL=p;C.P->next=HL;p=HL;D.P->next=HL->next;HL->next=p;4.两个字符串相等的条件是（）

A.串的长度相等 B.含有相同的字符集

C.都是非空串 D.串的长度相等且对应的字符相同 5．若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列是（）

A.SXSSXXXX B.SXXSXSSX C.SXSXXSSX D.SSSXXSXX 6.已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（）A.0 B.1 C.48 D.49 7.已知用某种排序方法对关键字序列（51，35，93，24，13，68，56，42，77）进行排序时，前两趟排序的结果为

（35，51，24，13，68，56，42，77，93）

（35，24，13，51，56，42，68，77，93）所采用的排序方法是（）

A.插入排序 B.冒泡排序 C.快速排序 D.归并排序

8.已知散列表的存储空间为T[0..16]，散列函数H（key）=key%17,并用二次探测法处理冲突。散列表中已插入下列关键字：T[5]=39，T[6]=57和T[7]=7，则下一个关键字23插入的位置是（）

A.T[2] B.T[4] C.T[8] D.T[10] 9.如果将矩阵An×n的每一列看成一个子表，整个矩阵看成是一个广义表L，即L=((a11,a21,…,an1),(a12,a22,…,an2),…，（a1n,a2n,…,ann）),并且可以通过求表头head和求表尾tail的运算求取矩阵中的每一个元素，则求得a21的运算是（）A.head(tail(head(L)))B.head(head(head(L)))C.tail(head(tail(L)))D.head(head(tail(L)))10.在一个具有n个顶点的有向图中，所有顶点的出度之和为Dout，则所有顶点的入度之和为（）

A.Dout B.Dout-1 C.Dout+1 D.n 11．从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是（）A线性结构 B.树形结构 C.线性结构和树型结构 D.线性结构和图状结构

12．栈的插入和删除操作在()进行。

A．栈顶 B.栈底 C.任意位置 D指定位置 13．由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）A.24 B.71 C.48 D.53 14．一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是()A.2 3 1 B.3 2 1 C.3 1 2 D.1 2 3 15．关于栈和队列的说法中正确的是（）

A．栈和队列都是线性结构 B.栈是线性结构，队列不是线性结构 C.栈不是线性结构，队列是线性结构 D.栈和队列都不是线性结构 16．关于存储相同数据元素的说法中正确的是（）A．顺序存储比链式存储少占空间 B.顺序存储比链式存储多占空间

C.顺序存储和链式存储都要求占用整块存储空间 D.链式存储比顺序存储难于扩充空间

17．已知一个单链表中，指针q指向指针p的前趋结点，若在指针q所指结点和指针p所指结点之间插入指针s所指结点，则需执行（）A.q→next=s；p→next=s； B.q→next=s；s→next=p； C.q→next=s；q→next=p； D.q→next=s；s→next=q；

18．设一组记录的关键字key值为{62，50，14，27，19，35，47，56，83}，散列函数为H(key)=key mod 13，则它的开散列表中散列地址为1的链中的结点个数是（）A.1 B.2 C.3 D.4 19．执行下面程序段时，S语句被执行的次数为：（）for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)S;A.n*n B.n*n/2 C.n(n+1)D.n(n+1)/2 20．在长度为n的线性表中删除一个指针p所指结点的时间复杂度是（）A．O(n)B.O(1)C.O(log2n)D.O(n2)21．设一个栈的输入序列是a，b，c，d，则所得到的输出序列（输入过程中允许出栈）不可能出现的是（）

A.a，b，c，d B.a，b，d，c C.d，c，b，a D.c，d，a，b 22．关于串的叙述中，正确的是（）A．空串是只含有零个字符的串 B.空串是只含有空格字符的串

C.空串是含有零个字符或含有空格字符的串

D.串是含有一个或多个字符的有穷序列

23．在具有m个单元的循环队列中，队头指针为front，队尾指针为rear，则队满的条件是（）

A．front==rear

B.(front+1)%m==rear

C.rear+1==front

D.(rear+1)%m==front 24．设有二维数组

1A［n］［n］表示如下：23456，则A［i］［i］（0≤i≤n-1）的D.i2/2 值为（）

A．i*(i-1)/2 B.i*(i+1)/2 C.(i+2)*(i+1)/2 25．高度为h的完全二叉树中，结点数最多为（）

hA．2h-1 B.2h+1 C.2-1 D.2h 26．由m棵结点数为n的树组成的森林，将其转化为一棵二叉树，则该二叉树中根结点的右子树上具有的结点个数是（）

A.mn B.mn-1 C.n(m-1)D.m(n-1)27．在一个具有n个顶点的无向图中，每个顶点度的最大值为（）A.n B.n-1 C.n+1 D.2(n-1)28．关于无向图的邻接矩阵的说法中正确的是（）A.矩阵中非全零元素的行数等于图中的顶点数

B.第i行上与第i列上非零元素总和等于顶点Vi的度数 C.矩阵中的非零元素个数等于图的边数

D.第i行上非零元素个数和第i列上非零元素个数一定相等

29．设一组记录的关键字key值为{62，50，14，28，19，35，47，56，83}，散列函数为H(key)=key mod 13，则它的开散列表中散列地址为1的链中的结点个数是（）A.1 B.2 C.3 D.4 30．设有一组初始关键字值序列为（49，81，55，36，44，88），则利用快速排序的方法，以第一个关键字值为基准得到的一次划分为（）

A.36，44，49，55，81，88 B.44，36，49，55，81，88 C.44，36，49，81，55，88 D.44，36，49，55，88，81

二、填空题

1.数据是计算机加工处理的对象（）。2.数据结构的概念包括数据的逻辑结构、数据在计算机中的存储方式和数据的运算三个方面()。

3.线性表是由n≥0个相同类型组成的有限序列（）。4.栈是一种后进先出的线性表（）。

5.从循环链表的某一结点出发，只能找到它的后继结点，不能找到它的前驱结点（）。6.单链表设置头结点的目的是为了简化运算（）。7.树的最大特点是一对多的层次结构（）。8.组成数据的基本单位称为数据元素（）。

9.从非循环链表的某一结点出发，既能找到它的后继结点，又能找到它的前驱结点（）。

10.单链表结点的指针域是用来存放其直接后继结点的首地址的（）

11.数据的存储结构是数据的逻辑结构的存储映象（）。

12.用顺序表来存储线性表时，不需要另外开辟空间来保存数据元素之间的相互关系（）。

13.在非线性结构中，至少存在一个元素不止一个直接前驱或不止一个直接后驱（）。14.树的最大特点是一对多的层次结构（）。15.队列的特点是先进先出（）。

16.由后序遍历序列和中序遍历序列能唯一确定一颗二叉树（）。17.数据的存储结构独立于计算机（）。18.线性表简称为”顺序表”。（）

19.对数据的任何运算都不能改变数据原有的结构特性（）。20.从循环单链表的任一结点出发，可以找到表中的所有结点（）。21.栈是一种先进先出的线性表（）。22.链表的主要缺点是不能随机访问（）。23.二叉树是树的特殊形式（）。24.冒泡排序法是稳定的排序（）。25.算法是对解题方法和步骤的描述（）。26.算法可以用任意的符号来描述（）。

27.数据的逻辑结构可以看作是从具体问题抽象出来的数学模型（）。

28.线性表的顺序存储方式是按逻辑次序将元素存放在一片地址连续的空间中（）。29.栈是一种先进后出的线性表（）。

30.将插入和删除限定在表的同一端进行的线性表是队列（）。

三、画图题

1.请根据下列二元组画出相应的数据结构

K={15,11,20,8,14,13 } R={<15,11>,<15,20>,<11,8>,<11,14>,<14,13>} 2.请根据下列二元组画出相应的数据结构

K={A,B,C,D,E,F,G,H,I,J} R={,,,,,,,,} 3．请根据下列二元组画出相应的数据结构 K={1,2,3,4,5,6,7} R={<1,2>,<1,3>,<1,4>,<2,1>,<2,4>,<3,5>,<3,6>,<3,7>,<4,1>,<4,5>,<5,1>,<5,3>,<5,4>,<6,5>,<6,7>,<7,3>} 4.请根据下列二元组画出相应的数据结构

K={1,2,3,4,5} R={<1,2>,<1,3>,<2,3>,<2,4>,<2,5>,<3,4>,<4,5>,<5,1>} 5．请根据下列二元组画出相应的数据结构 K={0,1,2,3,4,5,6,7} R={(0,1),(0,2),(1,3),(1,4),(2,5),(2,6),(3,7),(4,7),(5,6)} 6．请根据下列二元组画出相应的数据结构

K={1,2,3,4,5,6,7} R={(1,2),(1,3),（2,3），(2,4),(2,5),(3,7),(4,6),(5,6)，（6,7）}

四、运算题

1．已知一个图的顶点集V和边集H分别为：

V＝{0，1，2，3，4，5，6，7}

E＝{（0，1）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20}；

按照克鲁斯卡尔算法得到最小生成树，拭写出在最小生成树中依次得到的各条边。______，______，______，______，______，______，______。

2.一个线性表为B=（12，23，45，57，20，03，78，31，15，36），设散列表为HT[0..12]，散列函数为H（key）= key % 13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。

平均查找长度：（写出计算过程）

3．已知一个图的顶点集V和边集H分别为：

V＝{0，1，2，3，4，5，6，7}

E＝{（0，1）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20}；

按照普里姆算法得到最小生成树，试写出在最小生成树中依次得到的各条边。（从顶点2出发）

____

__，___

_，___

___，__

____，___ ___，__ ____，___ ___。4.写出下图所示的二叉树的前中后序遍历结果：

前序： 中序： 后序：

5.设有一个输入数据的序列是 { 46, 25, 78, 62, 12, 80 }, 试画出从空树起，逐个输入各个数据而生成的二叉排序树。

五、编程题

1.请编写一个算法，实现十进制整数与二进制数的转换。Void shi_to_er(unsigned x){ 2.写出二分法查找的算法：

Int search_bin(Keytype k,sstable st){ 3.请编写一个算法，实现单链表的就地逆置（单链表不带头结点）。LINKLIST *INVERTLINK(LINKLIST *H){