计算机与通信工程学院

天津理工大学

计算机与通信工程学院

实验报告 （试做）

2009 至 2010 学年 第 一 学期

计算机与通信工程学院

2

计算机与通信工程学院

3

计算机与通信工程学院

4

计算机与通信工程学院

（1） 顺序堆栈

? 源代码：

#include<stdio.h>

#include <process.h>

#include<stdlib.h>

#define MAX_LEN 100

// 堆栈元素类型

// 这里采用 typedef 别名机制，便于修改为别的类型, 如： typedef double ELEMENT; typedef int ELEMENT;

// 结构体 Stack

struct Stack{

ELEMENT * List; // 用来存储元素的顺序表

int curNumber; // 用来存储当前元素的总个数

};

void iniStack(struct Stack * A); // 初始化堆栈

void clearStack(struct Stack * A); //清空堆栈

void push(struct Stack * A, ELEMENT obj); //将元素obj压入堆栈的栈顶

void pop(struct Stack * A); //将当前栈顶的元素弹出栈。要求：栈不为空

ELEMENT get_top(struct Stack * A); //返回当前栈顶的元素值。要求：栈不为空 int is_empty(struct Stack * A); //判断当前堆栈是否为空，空返回1，非空返回0 void display(struct Stack * A); //自顶向下显示堆栈中的元素

void main()

{

const int max_input=5; //用户输入的次数

int loop;

ELEMENT user_input;

struct Stack * S=(struct Stack*)malloc(sizeof(struct Stack)); //申请一个堆栈对象 // 初始化

iniStack(S);

for(loop=1;loop<=max_input;loop++)

{

printf("Input no. %d :",loop);

scanf("%d",&user_input);

push(S, user_input);

}

display(S);

for(loop=1;loop<=max_input;loop++)

{

if(! is_empty(S))

{

user_input=get_top(S);

pop(S);

5

计算机与通信工程学院

printf("Output no. %d :",loop);

printf("%d \n",user_input);

}

}

// 内存释放

clearStack(S);

free(S);

}

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

/*

初始化堆栈

*/

void iniStack(struct Stack * A)

{

if(A!=NULL)

{

A->List=(ELEMENT *)malloc(sizeof(ELEMENT)*MAX_LEN); A->curNumber=0;

}

}

/*

清空堆栈

*/

void clearStack(struct Stack * A)

{

if(A!=NULL)

{

free(A->List);

A->curNumber=0;

}

}

/*

将元素obj压入以 top 为栈顶的堆栈的栈顶

*/

void push(struct Stack * A, ELEMENT obj)

{

if(A->curNumber>MAX_LEN)

{

printf(" \n 堆栈中的元素总数超过最大容量 ! \n");

return;

}

A->List[A->curNumber]=obj;

A->curNumber++;

}

6

计算机与通信工程学院

/*

将当前栈顶的元素弹出栈。要求：栈不为空 */

void pop(struct Stack * A)

{

if(!is_empty(A))

{

A->curNumber--;

}

}

/*

返回当前栈顶的元素值。要求：栈不为空 */

ELEMENT get_top(struct Stack * A)

{

if(is_empty(A))

{

printf("Error: Get top from empty stack. \n"); exit(1); //终止程序

}

return A->List[A->curNumber-1];

}

/*

判断当前堆栈是否为空，空返回1，非空返回0 */

int is_empty(struct Stack * A)

{

return (A->curNumber==0);

}

/*

自顶向下显示堆栈中的元素

*/

void display(struct Stack * A)

{

int i;

printf(" Stack 中的元素 自顶向下 为： \n"); for(i=A->curNumber-1;i>=0;i--)

{

printf("%d \n",A->List[i]);

}

}

（2） 学生信息链表

7

计算机与通信工程学院

? 源代码：

void main()

{

STUDENT_LINK* tjut;

tjut=new STUDENT_LINK;

iniStudentLink(tjut);

Add(tjut,2007002,"Tom",'M',19);

Add(tjut,2007007,"Jack",'M',20);

Add(tjut,2007004,"Mary",'F',20);

ShowALL(tjut);

Modify(tjut,2007002,"Tom Smith",'M',19);

Search(tjut,2007002);

Delete(tjut,2007004);

ShowALL(tjut);

clearStudentLink(tjut);

delete tjut;

}

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

/*

初始化学生链表

*/

void iniStudentLink(STUDENT_LINK * L)

{

L->top=new STUDENT_NODE; //top结点是个内容为空的"结点"，注意其作用

L->top->id=0;

L->top->next=NULL;

}

/*

清空学生链表

*/

void clearStudentLink(STUDENT_LINK * L)

{

STUDENT_NODE *ptr;

while(L->top != NULL) {

ptr=L->top;

L->top=L->top->next;

delete ptr;

}

return;

}

/*

判断该学号的学生信息是否存在: 存在返回1，不存在返回0

*/

8

计算机与通信工程学院

int isExist(STUDENT_LINK * L,long int id)

{

int exist;

STUDENT_NODE *ptr;

exist=0;

ptr=L->top;

while(ptr!=NULL)

{

if(id==ptr->id) //此学生信息已存在

{

exist=1;

break;

}

ptr=ptr->next;

}

return exist;

}

/*

添加一个新同学的信息

*/

int Add(STUDENT_LINK * L, long int id,char name[],char sex, int age)

{

int error;

int exist;

STUDENT_NODE *ptr;

STUDENT_NODE *node;

error=0;

exist=isExist(L,id);

if(exist==1)

{

error=1;

cout<<"Error!!! 错误添加：id = "<<id<<" 此学生信息已存在!!"<<endl; return error;

}

ptr=L->top;

while((ptr->next!=NULL)&&(ptr->next->id<id))

{

ptr=ptr->next;

}

node=new STUDENT_NODE;

node->id=id;

9

计算机与通信工程学院

strcpy(node->name,name);

node->sex=sex;

node->age=age;

//新结点插入到ptr结点之后

node->next=ptr->next;

ptr->next=node;

cout<<"添加：id = "<<id<<" 学生信息成功 !!"<<endl;

return error;

}

// 根据学号，修改该同学的信息

int Modify(STUDENT_LINK * L,long int id,char name[],char sex, int age) {

int error;

int exist;

STUDENT_NODE *ptr;

error=0;

exist=isExist(L,id);

if(exist==0)

{

error=1;

cout<<"Error!!! 错误修改：id = "<<id<<" 此学生信息不存在!!"<<endl; return error;

}

ptr=L->top;

while((ptr!=NULL)&&(ptr->id!=id))

{

ptr=ptr->next;

}

// 修改ptr中的信息

strcpy(ptr->name,name);

ptr->sex=sex;

ptr->age=age;

cout<<"修改：id = "<<id<<" 学生信息成功 !!"<<endl;

return error;

}

// 根据学号，从链表中删除该同学的信息

int Delete(STUDENT_LINK * L,long int id)

{

int error;

int exist;

STUDENT_NODE *ptr;

10

计算机与通信工程学院

STUDENT_NODE *node;

error=0;

exist=isExist(L,id);

if(exist==0)

{

error=1;

cout<<"Error!!! 错误删除：id = "<<id<<" 此学生信息不存在!!"<<endl; return error;

}

ptr=L->top;

while((ptr->next!=NULL)&&(ptr->next->id!=id))

{

ptr=ptr->next;

}

//结点ptr->next就是要删除的结点

node=ptr->next;

ptr->next=ptr->next->next;

delete node;

cout<<"删除：id = "<<id<<" 学生信息成功 !!"<<endl;

return error;

}

// 根据学号，输出显示该同学信息

int Search(STUDENT_LINK * L,long int id)

{

int error;

int exist;

STUDENT_NODE *ptr;

error=0;

exist=isExist(L,id);

if(exist==0)

{

error=1;

cout<<"Error!!! 错误显示：id = "<<id<<" 此学生信息不存在!!"<<endl; return error;

}

ptr=L->top;

while((ptr!=NULL)&&(ptr->id!=id))

{

ptr=ptr->next;

}

// 结点ptr中就是要找的结点的信息

cout<<"显示：id = "<<id<<" 学生信息："<<endl;

cout<<"id : "<<ptr->id<<endl;

cout<<"name : "<<ptr->name<<endl;

11

计算机与通信工程学院

cout<<"sex : "<<ptr->sex<<endl;

cout<<"age : "<<ptr->age<<endl;

cout<<"显示：id = "<<id<<" 学生信息成功 !!"<<endl; return error;

}

// 从头到尾，输出当前所有的同学信息

void ShowALL(STUDENT_LINK * L)

{

int k;

STUDENT_NODE *ptr;

cout<<"\n\n**************目前所有学********************"<<endl;

ptr=L->top->next;

k=1;

while(ptr!=NULL)

{

// 结点ptr中就是要找的结点的信息

cout<<"------第 "<<k<<" 个学生信息-----------"<<endl; cout<<"id : "<<ptr->id<<endl;

cout<<"name : "<<ptr->name<<endl;

cout<<"sex : "<<ptr->sex<<endl;

cout<<"age : "<<ptr->age<<endl;

cout<<"------------------------------"<<endl;

ptr=ptr->next;

k++;

}

cout<<"************** 共有 "<<k-1<<" ********************\n\n"<<endl;

}

12 生信个学生 息