数据结构实验总结及源代码.doc

实验1 线性表1 问题描述： 使用线性表实现一个通讯录，通讯录内容有：学号、姓名、电话号码。使其完成以下功能。（1） 建立一个通讯录 （2） 插入一个数据元素 （3） 删除一个元素，返回其值 （4） 结束程序 请写出基本的算法思想，以及源程序代码。实验2 括号匹配问题描述 编写一程序判断从键盘输入的子符串括号是否匹配。假设需判断的括号只有“（”，“）”，“”，“”四种。实验4 病人看病模拟程序【问题描述】 编写一个程序，反映病人到医院看病，排队看医生的情况。在病人排队的过程中，主要重复两件事：（1） 病人到达诊室，将病历本交给护士，排到等待队列中候诊。（2） 护士从等待队列中取出下一位病人的病历，该病人进入诊室就诊。要求模拟病人等待就诊这一过程。程序采用菜单方式，其选项及功能说明如下：（1） 排队输入排队病人的病历号，加入病人排队队列中。（2） 就诊病人排队队列中最前面的病人就诊，并将其从队列中删除；（3） 查看排队从对首到队尾列出所有的排队病人的病历号；（4） 不再排队，余下一次就诊从对首到队尾列出所有的排队病人的病历号，并退出运行；（5） 下班退出运行； 线性表实验源代码#include #include #include #include /-struct ElemType / 数据元素的类型 int numb; char name20; long tel; ;const int MAXSIZE=100; / 数组的容量class Sqlist private: ElemType elemMAXSIZE; /结构体的数组 int length; public: Sqlist( void); Sqlist() ; void SetData(); /建立通讯录； void Insert( int i, ElemType e); /在位置i,插入一条记录 ElemType Delet(int i); /删除位置i 的记录 void PrintOut(); /打印结果 ;/-/Sqlist:Sqlist( ) length=0；/Sqlist:Sqlist( ) length=0；Sqlist:Sqlist()length=0;void Sqlist:SetData( ) /初步建立一个通讯录 coutlength;for(int i=0;ilength;i+) coutelemi.numb;cout ;coutelemi.tel; void Sqlist:Insert( int i, ElemType e) int j; i-; if(ilength) cout i Error!i; j-) elemj=elemj-1; / for(j=length; ji; j-) elemj=elemj-1; elemi=e; length+; ElemType Sqlist:Delet(int i) ElemType x; int j; i-; if(ilength-1) cout i Error!endl; x.numb=-1; else x=elemi; for(j=i; jlength-1; j+) elemj=elemj+1;/for(j=i; jlength; j+) elemj=elemj+1; length-; return x;void Sqlist:PrintOut() /输出 coutn 通讯录总人数：length; coutn PrintOut Data:n;coutsetw(16)学号 setw(20)姓名setw(20)电话号endl; ; for(int k=0; klength;k+) coutsetw(16)elemk.numb setw(20)setw(20)elemk.telcoutendl; /-int main( ) int i,k; ElemType e,x; Sqlist as; coutn 通讯录演示; do coutnn; coutnn 1. 初步建立一个通讯录（线性表） ; coutnn 2. 插入一个数据元素 ; coutnn 3. 删除一个元素，返回其值; coutnn 4. 结束程序; coutn* ; coutk;switch(k) case 1: as.SetData(); as.PrintOut(); break; case 2: couti; coute.numb; ; coute.tel; as.Insert(i,e); as.PrintOut(); break; case 3: couti; x=as.Delet(i); coutn 被删除的元素数值= setw(10)x.numb setw(10)setw(10)=1&k4); coutn 再见!; coutn 按任意键，返回。; _getch(); return 0;/-括号匹配源代码#include #include #define OK 1#define ERROR 0/定义顺序堆栈#define STACK_SIZE 100 /存储空间初始分配量#define STACK_INC 10 /存储空间分配增量/*typedef char Elem;*/typedef struct char *base; /栈底指针 char *top; /栈顶指针 int size; /当前已分配的存储空间SqStack;/*typedef int Status;*/创建空堆栈,栈顶指针和栈底指针相等时,栈为空int CreatStack(SqStack &S) S.base=(char *)malloc(STACK_SIZE*sizeof(char); S.top=S.base; S.size=STACK_SIZE; return OK;/堆栈是否为空int StackEmpty(SqStack S) if(S.top!=S.base) return ERROR; return OK;/进栈int Push(SqStack &S,char e) if(S.top-S.base=S.size) /栈满,追加存储空间 S.base=(char *)realloc(S.base,(S.size+STACK_INC)*sizeof(char); S.top=S.base+S.size; S.size+=STACK_INC; *S.top=e; S.top+=1; return OK;/出栈int Pop(SqStack &S,char &e) if(S.top=S.base) return ERROR; S.top-=1; e=*S.top; return OK;/括号匹配int Bracket(SqStack &S,char *str) int i=0,flag1=0,flag2; char e; while(stri!=0) switch(stri) case (:Push(S,();break; /(进栈 case :Push(S,);break; /进栈 case ):Pop(S,e); if(e!=() flag1=1; break; /出栈，判断是否为( case :Pop(S,e); if(e!=) flag1=1;break; /出栈，判断是否为 default: break; if(flag1) break; /出现不匹配，立即结束循环 i+; flag2=StackEmpty(S); /flag2判断堆栈是否为空 if(!flag1 & flag2) printf(括号匹配!n); else printf(括号不匹配!n); return OK;/主函数void main() char temp,flag=y; while(flag=y) char str255; SqStack S; printf(请输入字符串:); scanf(%s,str); scanf(%c,&temp); /接受输入的回车键 CreatStack(S); Bracket(S,str); printf(你想再试一次吗(按y继续): ); scanf(%c,&flag); printf(n); printf(程序结束.n); 医院看病程序源代码#include#includetypedef struct qnode int data; struct qnode *next;QNode; /链队结点类型typedef structQNode *front,*rear;QuType; /链队类型void seedoctor() /模拟病人看病的过程int sel,flag=1,find,no;QuType *qu;QNode *p;qu=(QuType *)malloc(sizeof(QuType); /创建空队qu-front=qu-rear=NULL;while(flag=1)printf(1:排队 2：就诊 3：查看排队 4：不再排队，余下依次就诊 5：下班 请选择：);scanf(%d,&sel);switch(sel)case 1: printf(输入病历号：); do scanf(%d,&no); find=0; p=qu-front; while(p!=NULL & !find) if(p-data=no) find=1; else p=p-next; if(find) printf(输入的病历号重复，重新输入：);while(find=1);p=(QNode *)malloc(sizeof(QNode); /创建结点p-data=no; p-next=NULL;if(qu-rear=NULL) /第一个病人排队qu-front=qu-rear=p;elsequ-rear-next=p;qu-rear=p; /将*p结点入队 break;case 2: if(qu-front=NULL) /队空printf(没有排队的病人!n);else p=qu-front;printf(病人%d就诊n,p-data);if(qu-rear=p) /只有一个病人排队的情况qu-front=qu-rear=NULL;elsequ-front=p-next;free(p);break;case 3:if(qu-front=NULL) / 队空 printf(没有排队的病人!n);else /队不空 p=qu-front; printf(排队病人：); while(p!=NULL) printf(%d,p-data); p=p-next; printf(n);break;case 4:if(qu-front=NULL) / 队空 printf(没有排队的病人!n);else /队不空 p=qu-front; printf(排队病人：); while(p!=NULL) printf(%d,p-data); p=p-next; printf(n);flag=0; /退出break;case 5: if(qu-front!=NULL) /队不空printf(请排队的病人明天就医！n);flag=0;break;void main() seedoctor(); 练习题第二章 线性表习题1 线性表是具有n个（ ）的有限序列。（清华98年研究生试题） A 表元素 B 字符 C 数据元素 D 数据项 E 信息项 2 线性表的静态链表存储结构与顺序存储结构相比优点是（ ）。（中科院软件所01年研究生试题） A 所有的操作算法实现简单 B 便于随机存取 C 便于插入和删除 D 便于利用零散的存储器空间3 将如图所示的s所指结点加到p所指结点之后，其语句应为（ ） （浙大99年研究生试题） ps A s-next=p+1；p-=s； B (*p).next=s； (*s).next=(*p).next； C s-next=p-next； p-next=s-next； D s-next=p-next； p-next=s；4 线性表有两种存储结构：一是顺序表，二是链表，试问：（西安电子科大99年研究生试题）（1） 如果有n个线性表同时共存，并且在处理过程中各表的长度会动态地发生变化，线性表地总数也会自动地改变。在此情况下，应选用哪种存储结构？为什么？ （2） 若线性表地总数基本稳定，且很少进行插入和删除，但要求以最快地速度存取线性表中地元素，那么应采用哪种存储结构？为什么？5 用线性表地顺序存储结构来描述一个城市地设计和规划是否合适？为什么？第3章 栈和队列作业1 若用一个大小为6的数组来实现循环队列，且当rear和front的值分别为0和3时，从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？（复旦大学98年）2 设栈S和队列Q的初始状态为空，元素e1, e2,e3,e4,e5和e6依次通过栈S,一个元素出栈后即进入队列Q,若6个元素出对的序列是e2,e4, e3,e6, e5、e1 则栈S的容量至少应该是多少？ （南京理工2000年）3 已知一算术表达式的中缀形式为A+B*C-D/E,后缀形式为ABC*+DE/