中国石油大学数据结构上机实验8

数据结构与算法实验指导书中国石油大学(北京)计算机科学与技术系前言《数据结构》是计算机及相关专业的一门核心基础课程，也是很多高校考研专业课之一。

它主要介绍线性结构、树结构、图结构三种逻辑结构元素的存储实现，在此基础上介绍一些典型算法及时、空效率分析。

这门课程的主要任务是培养学生的算法设计能力及良好的程序设计习惯。

通过学习，要求学生能够掌握典型算法的设计思想及程序实现，能够根据实际问题选取合适的存储方案，设计出简洁、高效、实用的算法，为后续课程的学习及软件开发打下良好的基础。

学习这门课程，习题和实验是两个关键环节。

学生理解算法，上机实验是最佳的途径之一。

因此，实验环节的好坏是学生能否学好《数据结构》的关键。

为了更好地配合学生实验，特编写实验指导书。

一、实验目的更好的理解算法的思想、培养编程能力。

二、实验要求1、每次实验前学生必须根据试验内容认真准备实验程序及调试时所需的输入数据。

2、在指导教师的帮助下能够完成实验内容，得出正确的实验结果。

3、实验结束后总结实验内容、书写实验报告。

4、遵守实验室规章制度、不缺席、按时上、下机。

5、实验学时内必须做数据结构的有关内容，不允许上网聊天或玩游戏，如发现上述现象，取消本次上机资格，平时成绩扣10分。

6、实验报告有一次不合格，扣5分，两次以上不合格者，平时成绩以零分记。

三、实验环境 VC++6.0或者VC2010四、说明1、本实验的所有算法中元素类型可以根据实际需要选择。

2、实验题目中带＊者为较高要求，学生可自选；其余部分为基本内容，应尽量完成（至少完成70%，否则实验不合格）。

3、数据结构是很多高校的硕士研究生入学考试的专业课之一，希望有志于考研的学生能够在学习过程中注意各种算法的理解，以便为考研做一定的准备。

五、实验报告的书写要求1．明确实验的目的及要求；2．记录实验的输入数据和输出结果；3．说明实验中出现的问题和解决过程；4．写出实验的体会和实验过程中没能解决的问题；六、参考书目《数据结构》（C++语言描述）王红梅等清华大学出版社《DATA STRUCTURE WITH C++》 William Ford,William Topp清华大学出版社（影印版）实验平台控制台程序1、启动Microsoft VC6.0集成开发环境如图所示：2、单击“文件”菜单，选择“新建”项。

《数据结构》实验报告学号2015011512 姓名胡明禹专业数学与应用数学时间2018.4.3一、实验题目实验3 顺序栈基本操作二、实验目的1.熟练掌握顺序栈的实现和基本操作2.理解栈后进先出的特点3.熟练应用顺序栈解决实际问题三、算法设计分析（一）数据结构的定义数据结构是计算机存储、组织数据的方式。

数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。

（二）总体设计此处给出主要函数功能、及函数间调用关系的的描述。

例如：①初始化并建立一个新栈表函数②栈清空函数③栈判断是否为空函数④进栈函数⑤出栈函数⑥取栈顶元素函数⑦输出栈元素函数⑧计算栈中元素个数函数⑨销毁栈函数（1）主函数：统筹调用各个函数以实现相应功能void main()（2）①初始化并建立一个新栈表SqStack *InitStack(SqStack *s){int i;s=(SqStack*)malloc(sizeof(SqStack));s->top=-1;printf("输入顺序栈元素（以0结束）：\n");scanf("%d",&i);do{s->top++;//栈顶指针增加一s->data[s->top]=i; //将新插入元素赋值给栈顶空间scanf("%d",&i);while(i!=0);printf("成功\n");return s;}②栈清空函数void SetNULL(SqStack *s){//清空栈s->top=-1;//当栈存在一个元素时，top等于0,因此通常把空栈的条件定位top等于-1 }③栈判断是否为空函数int EMPTY(SqStack *s){//判断栈空if(s->top>=0)return 0;else return 1;}④进栈函数SqStack *Push(SqStack *s){//进栈int a;printf("插入数字：");scanf("%d",&a);if(s->top==maxsize-1)//判断是否栈满{printf("overflow");//溢出return NULL;}else{s->top++;//栈顶指针增加1s->data[s->top]=a;//将新插入元素赋值给栈顶空间}return s;}⑤出栈函数SqStack *Pop(SqStack *s){//出栈if(s->top==-1)//当栈存在一个元素时，top等于0,因此通常把空栈的条件定位top等于-1 {printf("underlow");return s;}else{s->top--;//栈顶指针减一printf("删除的栈顶元素：");printf("%d\n",(s->data[s->top+1]));//若栈不为空，则删除s的栈顶元素}return s;}⑥取栈顶元素函数void GetTop(SqStack *s){//取栈顶if(s->top==-1){printf("SqStack is empty");//当栈存在一个元素时，top等于0,因此通常把空栈的条件定位top 等于-1}else{printf("当前栈顶元素是：");printf("%d\n",(s->data[s->top]));//取栈顶元素地址}}⑦输出栈元素函数void print(SqStack *s){//输出栈int i=0;if(s->top==-1){printf("成功！");}while(i<=s->top){//遍历栈中所有元素printf("%d ",s->data[i]);i++;}}⑧计算栈中元素个数函数void Count(SqStack *s){//计算栈中元素int i=0;while(i<=s->top){i++;}printf("个数为%d",i);}⑨销毁栈函数int DestroyStack_Sq(SqStack *s){ //销毁一个顺序栈Sfree(s);s=NULL;return 1;}四、实验测试结果及结果分析（一）测试结果（此处给出程序运行截图）（二）结果分析成功完成了题目所要求的插入，删除，查找等基本操作。

实验一单链表的基本操作（必做）一、实验目的1.掌握单链表的存储、初始化、插入、删除等操作的程序实现。

2.加深对单链表基本概念,基本理论及相应算法的掌握与理解。

3.了解链表的处理方式，学习体会简单的单链表程序实现相关知识。

二、实验内容1.建立一个链表、设计链表的基本操作实现算法、输出一个链表表，调试并输出结果。

2.编写一个程序实现如下功能：让计算机产生出50个0~9之间的随机数并依次保存到单链表中;输出遍历单链表；从单链表中删除与给定值相等的所有结点；输出遍历单链表；输出单链表长度，调试并输出结果。

三、实验步骤1.定义一个链表结构体。

2.利用插入功能插入一个结点。

3.利用删除功能删除一个结点。

四、程序运行测试1.利用插入功能插入一个结点。

2.利用删除功能删除一个结点。

五、实验报告要求1.绘制链表操作实现的流程图。

2.详细给出程序运行测试结果（包括测试数据和测试结果）。

3.选试验步骤2-3中的任意一个，给出程序的详细注释。

4.参考程序中某一部分功能的改进（选做）5.实验心得与体会6.附录，实验用源程序六、参考源代码#include <iostream.h>#include <malloc.h>typedef struct LNode{int data;struct LNode *next;}Lnode, *LinkList;//假设下面的单链表均为带头结点。

void CreatLinkList(LinkList &L,int j){//建立一个单链表L,数据为整数，数据由键盘随机输入。

LinkList p,q;L=(LinkList )malloc(sizeof(Lnode));L->next=NULL;q=L;cout<<"在单链表内输入整数："<<endl;for(int i=0;i<j;i++) p=(LinkList)malloc(sizeof(Lnode)); cin>>p->data;p->next=q->next;q->next=p;q=p; }int PrintLinkList(LinkList &L){//输出单链表L的数据元素LinkList p;p=L->next;if(L->next==NULL){cout<<"链表没有元素!"<<endl;return 0;}cout<<"单链表的数据元素为:";while(p){cout<<p->data<<" ";p=p->next;}cout<<endl;return 1;}void LinkListLengh(LinkList &L){//计算单链表L的数据元素个数。

目录第1章绪论——上机实验题1解析实验题1.1求素数实验题1.2求一个正整数的各位数字之和实验题1.3求一个字符串是否为回文第2章线性表——上机实验题2解析实验题2.1实现顺序表各种基本运算的算法/*文件名:algo2-1.cpp*/#include <stdio.h>#include <malloc.h>#define MaxSize 50typedef char ElemType;typedef struct{ElemType elem[MaxSize];int length;} SqList;void InitList(SqList *&L){L=(SqList *)malloc(sizeof(SqList));L->length=0;}void DestroyList(SqList *L){free(L);}int ListEmpty(SqList *L){return(L->length==0);}int ListLength(SqList *L){return(L->length);}void DispList(SqList *L){int i;if (ListEmpty(L)) return;for (i=0;i<L->length;i++)printf("%c",L->elem[i]);printf("\n");}int GetElem(SqList *L,int i,ElemType &e){if (i<1 || i>L->length)return 0;e=L->elem[i-1];return 1;}int LocateElem(SqList *L, ElemType e){int i=0;while (i<L->length && L->elem[i]!=e) i++;if (i>=L->length)return 0;elsereturn i+1;}int ListInsert(SqList *&L,int i,ElemType e){int j;if (i<1 || i>L->length+1)return 0;i--; /*将顺序表位序转化为elem下标*/for (j=L->length;j>i;j--) /*将elem[i]及后面元素后移一个位置*/L->elem[j]=L->elem[j-1];L->elem[i]=e;L->length++; /*顺序表长度增1*/return 1;}int ListDelete(SqList *&L,int i,ElemType &e){int j;if (i<1 || i>L->length)return 0;i--; /*将顺序表位序转化为elem下标*/e=L->elem[i];for (j=i;j<L->length-1;j++)L->elem[j]=L->elem[j+1];L->length--;return 1;}实验题2.2实现单链表各种基本运算的算法*文件名:algo2-2.cpp*/#include <stdio.h>#include <malloc.h>typedef char ElemType;typedef struct LNode /*定义单链表结点类型*/{ElemType data;struct LNode *next;} LinkList;void InitList(LinkList *&L){L=(LinkList *)malloc(sizeof(LinkList)); /*创建头结点*/L->next=NULL;}void DestroyList(LinkList *&L){LinkList *p=L,*q=p->next;while (q!=NULL){free(p);p=q;q=p->next;}free(p);}int ListEmpty(LinkList *L){return(L->next==NULL);}int ListLength(LinkList *L){LinkList *p=L;int i=0;while (p->next!=NULL){i++;p=p->next;}return(i);}void DispList(LinkList *L){LinkList *p=L->next;while (p!=NULL){printf("%c",p->data);p=p->next;}printf("\n");}int GetElem(LinkList *L,int i,ElemType &e) {int j=0;LinkList *p=L;while (j<i && p!=NULL){j++;p=p->next;}if (p==NULL)return 0;else{e=p->data;return 1;}}int LocateElem(LinkList *L,ElemType e){LinkList *p=L->next;int n=1;while (p!=NULL && p->data!=e){p=p->next;n++;}if (p==NULL)return(0);elsereturn(n);}int ListInsert(LinkList *&L,int i,ElemType e)int j=0;LinkList *p=L,*s;while (j<i-1 && p!=NULL){j++;p=p->next;}if (p==NULL) /*未找到第i-1个结点*/return 0;else /*找到第i-1个结点*p*/{s=(LinkList *)malloc(sizeof(LinkList)); /*创建新结点*s*/s->data=e;s->next=p->next; /*将*s插p->next=s;return 1;}}int ListDelete(LinkList *&L,int i,ElemType &e){int j=0;LinkList *p=L,*q;while (j<i-1 && p!=NULL){j++;p=p->next;}if (p==NULL) /*未找到第i-1个结点*/return 0;else /*找到第i-1个结点*p*/{q=p->next; /*q指向要删除的结点*/p->next=q->next; /*从单链表中删除*q结点*/free(q); /*释放*q结点*/return 1;}}第3章栈和队列——上机实验题3解析实验题3.1实现顺序栈各种基本运算的算法*文件名:algo3-1.cpp*/#include <stdio.h>#include <malloc.h>#define MaxSize 100typedef char ElemType;typedef struct{ElemType elem[MaxSize];int top; /*栈指针*/} SqStack;void InitStack(SqStack *&s){s=(SqStack *)malloc(sizeof(SqStack));s->top=-1;}void ClearStack(SqStack *&s){free(s);}int StackLength(SqStack *s){return(s->top+1);}int StackEmpty(SqStack *s){return(s->top==-1);}int Push(SqStack *&s,ElemType e){if (s->top==MaxSize-1)return 0;s->top++;s->elem[s->top]=e;return 1;}int Pop(SqStack *&s,ElemType &e){if (s->top==-1)return 0;e=s->elem[s->top];s->top--;return 1;int GetTop(SqStack *s,ElemType &e){if (s->top==-1)return 0;e=s->elem[s->top];return 1;}void DispStack(SqStack *s){int i;for (i=s->top;i>=0;i--)printf("%c ",s->elem[i]);printf("\n");}实验题3.2实现链栈各种基本运算的算法/*文件名:algo3-2.cpp*/#include <stdio.h>#include <malloc.h>typedef char ElemType;typedef struct linknode{ElemType data; /*数据域*/struct linknode *next; /*指针域*/} LiStack;void InitStack(LiStack *&s){s=(LiStack *)malloc(sizeof(LiStack));s->next=NULL;}void ClearStack(LiStack *&s){LiStack *p=s->next;while (p!=NULL){free(s);s=p;p=p->next;}}int StackLength(LiStack *s){int i=0;LiStack *p;p=s->next;while (p!=NULL){i++;p=p->next;}return(i);}int StackEmpty(LiStack *s){return(s->next==NULL);}void Push(LiStack *&s,ElemType e){LiStack *p;p=(LiStack *)malloc(sizeof(LiStack));p->data=e;p->next=s->next; /*插入*p结点作为第一个数据结点*/s->next=p;}int Pop(LiStack *&s,ElemType &e){LiStack *p;if (s->next==NULL) /*栈空的情况*/return 0;p=s->next; /*p指向第一个数据结点*/e=p->data;s->next=p->next;free(p);return 1;}int GetTop(LiStack *s,ElemType &e){if (s->next==NULL) /*栈空的情况*/return 0;e=s->next->data;return 1;}void DispStack(LiStack *s){LiStack *p=s->next;while (p!=NULL){printf("%c ",p->data);p=p->next;}printf("\n");}实验题3.3实现顺序队列各种基本运算的算法/*文件名:algo3-3.cpp*/#include <stdio.h>#include <malloc.h>#define MaxSize 5typedef char ElemType;typedef struct{ElemType elem[MaxSize];int front,rear; /*队首和队尾指针*/} SqQueue;void InitQueue(SqQueue *&q){q=(SqQueue *)malloc (sizeof(SqQueue));q->front=q->rear=0;}void ClearQueue(SqQueue *&q){free(q);}int QueueEmpty(SqQueue *q){return(q->front==q->rear);}int QueueLength(SqQueue *q){return (q->rear-q->front+MaxSize)%MaxSize; }int enQueue(SqQueue *&q,ElemType e){if ((q->rear+1)%MaxSize==q->front) /*队满*/return 0;q->rear=(q->rear+1)%MaxSize;q->elem[q->rear]=e;return 1;}int deQueue(SqQueue *&q,ElemType &e){if (q->front==q->rear) /*队空*/return 0;q->front=(q->front+1)%MaxSize;e=q->elem[q->front];return 1;}实验题3.4实现链队各种基本运算的算法/*文件名:algo3-4.cpp*/#include <stdio.h>#include <malloc.h>typedef char ElemType;typedef struct qnode{ElemType data;struct qnode *next;} QNode;typedef struct{QNode *front;QNode *rear;} LiQueue;void InitQueue(LiQueue *&q){q=(LiQueue *)malloc(sizeof(LiQueue));q->front=q->rear=NULL;}void ClearQueue(LiQueue *&q){QNode *p=q->front,*r;if (p!=NULL) /*释放数据结点占用空间*/{r=p->next;while (r!=NULL){free(p);p=r;r=p->next;}}free(q); /*释放头结点占用空间*/ }int QueueLength(LiQueue *q){int n=0;QNode *p=q->front;while (p!=NULL){n++;p=p->next;}return(n);}int QueueEmpty(LiQueue *q){if (q->rear==NULL)return 1;elsereturn 0;}void enQueue(LiQueue *&q,ElemType e){QNode *s;s=(QNode *)malloc(sizeof(QNode));s->data=e;s->next=NULL;if (q->rear==NULL) /*若链队为空,则新结点是队首结点又是队尾结点*/q->front=q->rear=s;else{q->rear->next=s; /*将*s结点链到队尾,rear指向它*/q->rear=s;}}int deQueue(LiQueue *&q,ElemType &e){QNode *t;if (q->rear==NULL) /*队列为空*/return 0;if (q->front==q->rear) /*队列中只有一个结点时*/{t=q->front;q->front=q->rear=NULL;}else /*队列中有多个结点时*/{t=q->front;q->front=q->front->next;}e=t->data;free(t);return 1;}第4章串——上机实验题4解析实验题4.1实现顺序串各种基本运算的算法/*文件名:algo4-1.cpp*/#include <stdio.h>#define MaxSize 100 /*最多的字符个数*/typedef struct{ char ch[MaxSize]; /*定义可容纳MaxSize个字符的空间*/ int len; /*标记当前实际串长*/} SqString;void StrAssign(SqString &str,char cstr[]) /*str为引用型参数*/ {int i;for (i=0;cstr[i]!='\0';i++)str.ch[i]=cstr[i];str.len=i;}void StrCopy(SqString &s,SqString t) /*s为引用型参数*/ {int i;for (i=0;i<t.len;i++)s.ch[i]=t.ch[i];s.len=t.len;}int StrEqual(SqString s,SqString t){int same=1,i;if (s.len!=t.len) /*长度不相等时返回0*/same=0;else{for (i=0;i<s.len;i++)if (s.ch[i]!=t.ch[i]) /*有一个对应字符不相同时返回0*/same=0;}return same;}int StrLength(SqString s){return s.len;}SqString Concat(SqString s,SqString t){SqString str;int i;str.len=s.len+t.len;for (i=0;i<s.len;i++) /*将s.ch[0]～s.ch[s.len-1]复制到str*/ str.ch[i]=s.ch[i];for (i=0;i<t.len;i++) /*将t.ch[0]～t.ch[t.len-1]复制到str*/ str.ch[s.len+i]=t.ch[i];return str;}SqString SubStr(SqString s,int i,int j){SqString str;int k;str.len=0;if (i<=0 || i>s.len || j<0 || i+j-1>s.len){printf("参数不正确\n");return str; /*参数不正确时返回空串*/}for (k=i-1;k<i+j-1;k++) /*将s.ch[i]～s.ch[i+j]复制到str*/str.ch[k-i+1]=s.ch[k];str.len=j;return str;}SqString InsStr(SqString s1,int i,SqString s2){int j;SqString str;str.len=0;if (i<=0 || i>s1.len+1) /*参数不正确时返回空串*/{printf("参数不正确\n");return s1;}for (j=0;j<i-1;j++) /*将s1.ch[0]～s1.ch[i-2]复制到str*/str.ch[j]=s1.ch[j];for (j=0;j<s2.len;j++) /*将s2.ch[0]～s2.ch[s2.len-1]复制到str*/str.ch[i+j-1]=s2.ch[j];for (j=i-1;j<s1.len;j++) /*将s1.ch[i-1]～s.ch[s1.len-1]复制到str*/str.ch[s2.len+j]=s1.ch[j];str.len=s1.len+s2.len;return str;}SqString DelStr(SqString s,int i,int j){int k;SqString str;str.len=0;if (i<=0 || i>s.len || i+j>s.len+1) /*参数不正确时返回空串*/{printf("参数不正确\n");return str;}for (k=0;k<i-1;k++) /*将s.ch[0]～s.ch[i-2]复制到str*/str.ch[k]=s.ch[k];for (k=i+j-1;k<s.len;k++)/*将s.ch[i+j-1]～ch[s.len-1]复制到str*/ str.ch[k-j]=s.ch[k];str.len=s.len-j;return str;}SqString RepStr(SqString s,int i,int j,SqString t){int k;SqString str;str.len=0;if (i<=0 || i>s.len || i+j-1>s.len) /*参数不正确时返回空串*/ {printf("参数不正确\n");return str;}for (k=0;k<i-1;k++) /*将s.ch[0]～s.ch[i-2]复制到str*/str.ch[k]=s.ch[k];for (k=0;k<t.len;k++) /*将t.ch[0]～t.ch[t.len-1]复制到str*/str.ch[i+k-1]=t.ch[k];for (k=i+j-1;k<s.len;k++) /*将s.ch[i+j-1]～ch[s.len-1]复制到str*/str.ch[t.len+k-j]=s.ch[k];str.len=s.len-j+t.len;return str;}void DispStr(SqString str){int i;if (str.len>0){for (i=0;i<str.len;i++)printf("%c",str.ch[i]);printf("\n");}}实验题4.2实现链串各种基本运算的算法*文件名:algo4-2.cpp*/#include <stdio.h>#include <malloc.h>typedef struct snode{char data;struct snode *next;} LiString;void StrAssign(LiString *&s,char t[]){int i;LiString *r,*p;s=(LiString *)malloc(sizeof(LiString));s->next=NULL;r=s;for (i=0;t[i]!='\0';i++){p=(LiString *)malloc(sizeof(LiString));p->data=t[i];p->next=NULL;r->next=p;r=p;}}void StrCopy(LiString *&s,LiString *t){LiString *p=t->next,*q,*r;s=(LiString *)malloc(sizeof(LiString));s->next=NULL;s->next=NULL;r=s;while (p!=NULL) /*将t的所有结点复制到s*/{q=(LiString *)malloc(sizeof(LiString));q->data=p->data;q->next=NULL;r->next=q;r=q;p=p->next;}}int StrEqual(LiString *s,LiString *t){LiString *p=s->next,*q=t->next;while (p!=NULL && q!=NULL && p->data==q->data){p=p->next;q=q->next;}if (p==NULL && q==NULL)return 1;elsereturn 0;}int StrLength(LiString *s){int i=0;LiString *p=s->next;while (p!=NULL){i++;p=p->next;}return i;}LiString *Concat(LiString *s,LiString *t){LiString *str,*p=s->next,*q,*r;str=(LiString *)malloc(sizeof(LiString));str->next=NULL;r=str;while (p!=NULL) /*将s的所有结点复制到str*/ {q=(LiString *)malloc(sizeof(LiString));q->data=p->data;q->next=NULL;r->next=q;r=q;p=p->next;}p=t->next;while (p!=NULL) /*将t的所有结点复制到str*/ {q=(LiString *)malloc(sizeof(LiString));q->data=p->data;q->next=NULL;r->next=q;r=q;p=p->next;}return str;}LiString *SubStr(LiString *s,int i,int j){int k;LiString *str,*p=s->next,*q,*r;str=(LiString *)malloc(sizeof(LiString));str->next=NULL;r=str;if (i<=0 || i>StrLength(s) || j<0 || i+j-1>StrLength(s)) {printf("参数不正确\n");return str; /*参数不正确时返回空串*/ }for (k=0;k<i-1;k++)p=p->next;for (k=1;k<=j;k++) /*将s的第i个结点开始的j个结点复制到str*/{q=(LiString *)malloc(sizeof(LiString));q->data=p->data;q->next=NULL;r->next=q;r=q;p=p->next;}return str;}LiString *InsStr(LiString *s,int i,LiString *t){int k;LiString *str,*p=s->next,*p1=t->next,*q,*r;str=(LiString *)malloc(sizeof(LiString));str->next=NULL;r=str;if (i<=0 || i>StrLength(s)+1) /*参数不正确时返回空串*/{printf("参数不正确\n");return str;}for (k=1;k<i;k++) /*将s的前i个结点复制到str*/{q=(LiString *)malloc(sizeof(LiString));q->data=p->data;q->next=NULL;r->next=q;r=q;p=p->next;}while (p1!=NULL) /*将t的所有结点复制到str*/ {q=(LiString *)malloc(sizeof(LiString));q->data=p1->data;q->next=NULL;r->next=q;r=q;p1=p1->next;}while (p!=NULL) /*将*p及其后的结点复制到str*/ {q=(LiString *)malloc(sizeof(LiString));q->data=p->data;q->next=NULL;r->next=q;r=q;p=p->next;}return str;}LiString *DelStr(LiString *s,int i,int j){int k;LiString *str,*p=s->next,*q,*r;str=(LiString *)malloc(sizeof(LiString));str->next=NULL;r=str;if (i<=0 || i>StrLength(s) || j<0 || i+j-1>StrLength(s)) {printf("参数不正确\n");return str; /*参数不正确时返回空串*/ }for (k=0;k<i-1;k++) /*将s的前i-1个结点复制到str*/{q=(LiString *)malloc(sizeof(LiString));q->data=p->data;q->next=NULL;r->next=q;r=q;p=p->next;}for (k=0;k<j;k++) /*让p沿next跳j个结点*/p=p->next;while (p!=NULL) /*将*p及其后的结点复制到str*/{q=(LiString *)malloc(sizeof(LiString));q->data=p->data;q->next=NULL;r->next=q;r=q;p=p->next;}return str;}LiString *RepStr(LiString *s,int i,int j,LiString *t){int k;LiString *str,*p=s->next,*p1=t->next,*q,*r;str=(LiString *)malloc(sizeof(LiString));str->next=NULL;r=str;if (i<=0 || i>StrLength(s) || j<0 || i+j-1>StrLength(s)) {printf("参数不正确\n");return str; /*参数不正确时返回空串*/ }for (k=0;k<i-1;k++) /*将s的前i-1个结点复制到str*/{q=(LiString *)malloc(sizeof(LiString));q->data=p->data;q->next=NULL;r->next=q;r=q;p=p->next;}for (k=0;k<j;k++) /*让p沿next跳j个结点*/p=p->next;while (p1!=NULL) /*将t的所有结点复制到str*/{q=(LiString *)malloc(sizeof(LiString));q->data=p1->data;q->next=NULL;r->next=q;r=q;p1=p1->next;}while (p!=NULL) /*将*p及其后的结点复制到str*/{q=(LiString *)malloc(sizeof(LiString));q->data=p->data;q->next=NULL;r->next=q;r=q;p=p->next;}return str;}void DispStr(LiString *s){LiString *p=s->next;while (p!=NULL){printf("%c",p->data);p=p->next;}printf("\n");}第5章数组和稀疏矩阵——上机实验题5解析实验题5.1求5×5阶螺旋方阵/*文件名:exp5-1.cpp*/#include <stdio.h>#define MaxLen 10void fun(int a[MaxLen][MaxLen],int n){int i,j,k=0,m;if (n%2==0) //m=én/2ùm=n/2;elsem=n/2+1;for (i=0;i<m;i++){for (j=i;j<n-i;j++){k++;a[i][j]=k;}for (j=i+1;j<n-i;j++){k++;a[j][n-i-1]=k;}for (j=n-i-2;j>=i;j--){k++;a[n-i-1][j]=k;}for (j=n-i-2;j>=i+1;j--){k++;a[j][i]=k;}}}void main(){int n,i,j;int a[MaxLen][MaxLen];printf("\n");printf("输入n(n<10):");scanf("%d",&n);fun(a,n);printf("%d阶数字方阵如下:\n",n);for (i=0;i<n;i++){for (j=0;j<n;j++)printf("%4d",a[i][j]);printf("\n");}printf("\n");}实验题5.2求一个矩阵的马鞍点/*文件名:exp5-2.cpp*/#include <stdio.h>#define M 4#define N 4void MinMax(int A[M][N]){int i,j,have=0;int min[M],max[N];for (i=0;i<M;i++) /*计算出每行的最小值元素,放入min[0..M-1]之中*/{min[i]=A[i][0];for (j=1;j<N;j++)if (A[i][j]<min[i])min[i]=A[i][j];}for (j=0;j<N;j++) /*计算出每列的最大值元素,放入max[0..N-1]之中*/{max[j]=A[0][j];for (i=1;i<M;i++)if (A[i][j]>max[j])max[j]=A[i][j];}for (i=0;i<M;i++)for (j=0;j<N;j++)if (min[i]==max[j]){printf(" A[%d,%d]=%d\n",i,j,A[i][j]); /*显示马鞍点*/have=1;}if (!have)printf("没有鞍点\n");}void main(){int i,j;int A[M][N]={{9, 7, 6, 8},{20,26,22,25},{28,36,25,30},{12,4, 2, 6}};printf("A矩阵:\n");for (i=0;i<M;i++){for (j=0;j<N;j++)printf("%4d",A[i][j]);printf("\n");}printf("A矩阵中的马鞍点:\n");MinMax(A); /*调用MinMax()找马鞍点*/}实验题5.3求两个对称矩阵之和与乘积/*文件名:exp5-3.cpp*/#include <stdio.h>#define n 4#define m 10int value(int a[],int i,int j){if (i>=j)return a[(i*(i-1))/2+j];elsereturn a[(j*(j-1))/2+i];}void madd(int a[],int b[],int c[n][n]){int i,j;for (i=0;i<n;i++)for (j=0;j<n;j++)c[i][j]=value(a,i,j)+value(b,i,j);}void mult(int a[],int b[],int c[n][n]){int i,j,k,s;for (i=0;i<n;i++)for (j=0;j<n;j++){s=0;for (k=0;k<n;k++)s=s+value(a,i,k)*value(b,k,j); c[i][j]=s;}}void disp1(int a[]){int i,j;for (i=0;i<n;i++){for (j=0;j<n;j++)printf("%4d",value(a,i,j));printf("\n");}}void disp2(int c[n][n]){int i,j;for (i=0;i<n;i++){for (j=0;j<n;j++)printf("%4d",c[i][j]);printf("\n");}}void main(){int a[m]={1,2,3,4,5,6,7,8,9,10};int b[m]={1,1,1,1,1,1,1,1,1,1};int c1[n][n],c2[n][n];madd(a,b,c1);mult(a,b,c2);printf("\n");printf("a矩阵:\n");disp1(a);printf("b矩阵:\n");disp1(b);printf("a+b:\n");disp2(c1);printf("a*b:\n");disp2(c2);printf("\n");}实验题5.4实现稀疏矩阵（采用三元组表示）的基本运算/*文件名:exp5-4.cpp*/#include <stdio.h>#define N 4typedef int ElemType;#define MaxSize 100 /*矩阵中非零元素最多个数*/ typedef struct{ int r; /*行号*/int c; /*列号*/ElemType d; /*元素值*/} TupNode; /*三元组定义*/typedef struct{ int rows; /*行数值*/int cols; /*列数值*/int nums; /*非零元素个数*/TupNode data[MaxSize];} TSMatrix; /*三元组顺序表定义*/void CreatMat(TSMatrix &t,ElemType A[N][N]){int i,j;t.rows=N;t.cols=N;t.nums=0;for (i=0;i<N;i++){for (j=0;j<N;j++)if (A[i][j]!=0){t.data[t.nums].r=i;t.data[t.nums].c=j;t.data[t.nums].d=A[i][j];t.nums++;}}}void DispMat(TSMatrix t){int i;if (t.nums<=0)return;printf("\t%d\t%d\t%d\n",t.rows,t.cols,t.nums);printf("\t------------------\n");for (i=0;i<t.nums;i++)printf("\t%d\t%d\t%d\n",t.data[i].r,t.data[i].c,t.data[i].d); }void TranMat(TSMatrix t,TSMatrix &tb){int p,q=0,v; /*q为tb.data的下标*/tb.rows=t.cols;tb.cols=t.rows;tb.nums=t.nums;if (t.nums!=0){for (v=0;v<t.cols;v++) /*tb.data[q]中的记录以c 域的次序排列*/for (p=0;p<t.nums;p++) /*p为t.data的下标*/if (t.data[p].c==v){tb.data[q].r=t.data[p].c;tb.data[q].c=t.data[p].r;tb.data[q].d=t.data[p].d;q++;}}}int MatAdd(TSMatrix a,TSMatrix b,TSMatrix &c){int i=0,j=0,k=0;ElemType v;if (a.rows!=b.rows || a.cols!=b.cols)return 0; /*行数或列数不等时不能进行相加运算*/c.rows=a.rows;c.cols=a.cols; /*c的行列数与a的相同*/while (i<a.nums && j<b.nums) /*处理a和b中的每个元素*/{if (a.data[i].r==b.data[j].r) /*行号相等时*/{if(a.data[i].c<b.data[j].c) /*a元素的列号小于b 元素的列号*/{c.data[k].r=a.data[i].r;/*将a元素添加到c中*/c.data[k].c=a.data[i].c;c.data[k].d=a.data[i].d;k++;i++;}else if (a.data[i].c>b.data[j].c)/*a元素的列号大于b元素的列号*/{c.data[k].r=b.data[j].r; /*将b元素添加到c中*/c.data[k].c=b.data[j].c;c.data[k].d=b.data[j].d;k++;j++;}else /*a元素的列号等于b元素的列号*/{v=a.data[i].d+b.data[j].d;if (v!=0) /*只将不为0的结果添加到c中*/{c.data[k].r=a.data[i].r;c.data[k].c=a.data[i].c;c.data[k].d=v;k++;}i++;j++;}}else if (a.data[i].r<b.data[j].r) /*a元素的行号小于b元素的行号*/{c.data[k].r=a.data[i].r; /*将a元素添加到c中*/c.data[k].c=a.data[i].c;c.data[k].d=a.data[i].d;k++;i++;}else /*a元素的行号大于b元素的行号*/{c.data[k].r=b.data[j].r; /*将b元素添加到c中*/c.data[k].c=b.data[j].c;c.data[k].d=b.data[j].d;k++;j++;}c.nums=k;}return 1;}int value(TSMatrix c,int i,int j){int k=0;while (k<c.nums && (c.data[k].r!=i || c.data[k].c!=j))k++;if (k<c.nums)return(c.data[k].d);elsereturn(0);}int MatMul(TSMatrix a,TSMatrix b,TSMatrix &c){int i,j,k,p=0;ElemType s;if (a.cols!=b.rows) /*a的列数不等于b的行数时不能进行相乘运算*/return 0;for (i=0;i<a.rows;i++)for (j=0;j<b.cols;j++){s=0;for (k=0;k<a.cols;k++)s=s+value(a,i,k)*value(b,k,j);if (s!=0) /*产生一个三元组元素*/{c.data[p].r=i;c.data[p].c=j;c.data[p].d=s;p++;}}c.rows=a.rows;c.cols=b.cols;c.nums=p;return 1;}void main(){ElemType a1[N][N]={{1,0,3,0},{0,1,0,0},{0,0,1,0},{0,0,1,1}};ElemType b1[N][N]={{3,0,0,0},{0,4,0,0},{0,0,1,0},{0,0,0,2}};TSMatrix a,b,c;CreatMat(a,a1);CreatMat(b,b1);printf("a的三元组:\n");DispMat(a);printf("b的三元组:\n");DispMat(b);printf("a转置为c\n");TranMat(a,c);printf("c的三元组:\n");DispMat(c);printf("c=a+b\n");MatAdd(a,b,c);printf("c的三元组:\n");DispMat(c);printf("c=a*b\n");MatMul(a,b,c);printf("c的三元组:\n");DispMat(c);}实验题5.5实现广义表的基本运算#include <stdio.h>#include <malloc.h>typedef char ElemType;typedef struct lnode{ int tag; /*结点类型标识*/ union{ElemType data;struct lnode *sublist;}val;struct lnode *link; /*指向下一个元素*/} GLNode;extern GLNode *CreatGL(char *&s);extern void DispGL(GLNode *g);void Change(GLNode *&g,ElemType s,ElemType t) /*将广义表g中所有原子s 替换成t*/{if (g!=NULL){if (g->tag==1) /*子表的情况*/Change(g->val.sublist,s,t);else if (g->val.data==s) /*原子且data域值为s的情况*/g->val.data=t;Change(g->link,s,t);}}void Reverse(GLNode *&g) /*将广义表g所有元素逆置*/{GLNode *p,*q,*t;t=NULL;if (g!=NULL){p=g;while (p!=NULL) /*将同级的兄弟逆置*/{q=p->link;if (t==NULL){t=p;p->link=NULL;}else{p->link=t;t=p;}p=q;}g=t;p=g;while (p!=NULL){if (p->tag==1)Reverse(p->val.sublist);p=p->link;}}}int Same(GLNode *g1,GLNode *g2) /*判断两个广义表是否相同*/ {int s;if (g1==NULL && g2==NULL) /*均为NULL的情况*/return 1;else if ((g1==NULL && g2!=NULL) || (g1!=NULL && g2==NULL)) /*一个为NULL,另一不为NULL的情况*/return 0;else{s=1;while (g1!=NULL && g2!=NULL && s==1){if (g1->tag==1 && g2->tag==1)/*均为子表的情况*/s=Same(g1->val.sublist,g2->val.sublist);else if (g1->tag==0 && g2->tag==0)/*均为原子的情况*/{if (g1->val.data!=g2->val.data)s=0;}else /*一个为原子,另一为子表的情况*/s=0;g1=g1->link;g2=g2->link;}if (g1!=NULL || g2!=NULL) /*有一个子表尚未比较完时*/s=0;return s;}}ElemType MaxAtom(GLNode *g) /*求广义表g中最大的原子*/{ElemType m=0,m1; /*m赋初值0*/while (g!=NULL){if (g->tag==1) /*子表的情况*/{m1=MaxAtom(g->val.sublist); /*对子表递归调用*/if (m1>m) m=m1;}else{if (g->val.data>m) /*为原子时,进行原子比较*/m=g->val.data;}g=g->link;}return m;}void DelAtom(GLNode *&g,ElemType x) /*删除广义表g中的第一个为x原子*/{GLNode *p=g,*q,*pre;while (p!=NULL){q=p->link;if (p->tag==1) /*子表的情况*/DelAtom(p->val.sublist,x); /*对子表递归调用*/else{if (p->val.data==x) /*为原子时,进行原子比较*/{if (p==g)/*被删结点是本层的第1个结点*/{g=q;free(p); /*释放结pre=g;}else /*被删结{pre->link=q;free(p);}return;}}pre=p;p=q;}}void DelAtomAll(GLNode *&g,ElemType x) /*删除广义表g中的所有为x原子*/{GLNode *p=g,*q,*pre;while (p!=NULL){q=p->link;if (p->tag==1) /*子表的情况*/DelAtomAll(p->val.sublist,x); /*对子表递归调用*/else{if (p->val.data==x) /*为原子时,进行原子比较*/if (p==g)/*被删结点是本层的第1个结点*/{g=q;free(p); /*释放结pre=g;}else /*被删结{pre->link=q;free(p);}}pre=p;p=q;}}void PreOrder(GLNode *g) /*采用先根遍历g*/{if (g!=NULL){if (g->tag==0) /*为原子结点时*/printf("%c ",g->val.data);elsePreOrder(g->val.sublist); /*为子表时*/ PreOrder(g->link);}}void main(){GLNode *g1,*g2,*g3,*g4;char *str1="(a,(a),((a,b)),((a)),a)";char *str2="(a,(b),((c,d)),((e)),f)";char *str3="(a,(a,b),(a,b,c)))";char *str4="(a,(b),((c,d)),((e)),f)";g1=CreatGL(str1);printf("\n");printf(" 广义表g1:");DispGL(g1);printf("\n");printf(" 将广义表g1中所有'a'改为'b'\n");Change(g1,'a','b');printf(" 广义表g1:");DispGL(g1);printf("\n\n");g2=CreatGL(str2);printf(" 广义表g2:");DispGL(g2);printf("\n");printf(" 广义表g2中最大原子:%c\n",MaxAtom(g2));printf(" 将g2的元素逆置\n");Reverse(g2);printf(" 广义表g2:");DispGL(g2);printf("\n\n");printf(" 广义表g1和g2%s\n\n",(Same(g1,g2)?"相同":"不相同"));g3=CreatGL(str3);printf(" 广义表g3:");DispGL(g3);printf("\n");printf(" 删除广义表g3的第一个为'a'的原子\n");DelAtom(g3,'a');printf(" 广义表g3:");DispGL(g3);printf("\n\n");printf(" 删除广义表g3中的所有'a'原子\n");DelAtomAll(g3,'a');printf(" 广义表g3:");DispGL(g3);printf("\n\n");g4=CreatGL(str4);printf(" 广义表g4:");DispGL(g4);printf("\n");printf(" 采用先根遍历g4的结果:");PreOrder(g4);printf("\n\n");}。

《数据结构》实验报告学号2015011512 姓名胡明禹专业数学与应用数学时间2018.4.24一、实验题目实验5 稀疏矩阵的转置二、实验目的1. 稀疏矩阵的压缩存储方法2. 掌握稀疏矩阵的转置算法三、算法设计分析（一）实验内容1.从键盘输入数据，建立稀疏矩阵的三元组顺序存储2.实现稀疏矩阵的转置算法3.输出原矩阵及转置后的矩阵4．实现矩阵的快速转置算法（二）总体设计此处给出主要函数功能、及函数间调用关系的的描述。

例如：①创建稀疏矩阵函数②转置矩阵T函数③快速转置函数④输出函数⑤输出原矩阵和转置函数其功能描述如下：（1）主函数：统筹调用各个函数以实现相应功能Status main()（2）①创建稀疏矩阵函数Status CreateSMatrix(TSMatrix &M){printf("请输入原矩阵：\n");printf("行数、列数：");scanf("%d%d", &M.mu, &M.nu);printf("元素总数：");scanf("%d", &M.tu);printf("输入各个对应压缩值：\n");for (int i = 1; i <= M.tu; ++i)scanf("%d%d%d", &M.data[i].i, &M.data[i].j, &M.data[i].e); return OK;}②转置矩阵T函数Status TransposeSMatrix(TSMatrix M, TSMatrix &T){ int p, q, col;T.mu = M.nu; T.nu = M.mu; T.tu = M.tu;if (T.tu){q = 1;for (col = 1; col <= M.nu; ++col)for (p = 1; p <= M.tu; ++p)if (M.data[p].j == col){T.data[q].i = M.data[p].j;T.data[q].j = M.data[p].i;T.data[q].e = M.data[p].e;++q;}}printf("\n\n稀疏矩阵M转置成功。

〈数据结构〉上机实验指导数据结构是计算机科学中的一门重要课程，它研究的是数据的组织、存储和管理方式，以及对数据进行操作和处理的算法。

上机实验是数据结构课程的重要组成部分，通过实践操作，能够更好地理解和掌握数据结构的基本概念、算法和应用。

在进行〈数据结构〉上机实验之前，首先需要准备实验环境。

通常情况下，我们会使用一种编程语言来实现数据结构的相关操作，比如C++、Java等。

根据自己的实际情况和实验要求，选择一种合适的编程语言，并确保在实验环境中已经正确安装了相应的编译器或解释器。

接下来，我们可以开始进行具体的上机实验了。

下面以链表为例，介绍一下〈数据结构〉上机实验的指导步骤和要求：1. 实验目的：掌握链表的基本概念、操作和应用，理解链表与数组的区别和联系。

2. 实验原理：链表是一种动态数据结构，它由一系列的节点组成，每个节点包含数据和指向下一个节点的指针。

链表的特点是插入和删除操作的时间复杂度为O(1)，但是查找操作的时间复杂度为O(n)。

3. 实验步骤：3.1 创建链表：首先，我们需要定义一个链表的结构体，包含数据和指针两个成员变量。

然后，通过动态内存分配来创建链表的节点，并将节点之间通过指针连接起来，形成一个完整的链表。

3.2 插入节点：可以在链表的任意位置插入一个新的节点。

插入节点的操作包括：创建一个新的节点，将新节点的指针指向插入位置的下一个节点，将插入位置的前一个节点的指针指向新节点。

3.3 删除节点：可以删除链表中的任意一个节点。

删除节点的操作包括：将要删除的节点的前一个节点的指针指向要删除的节点的下一个节点，然后释放要删除的节点的内存空间。

3.4 遍历链表：可以通过遍历链表来访问链表中的每一个节点，并对节点进行相应的操作。

遍历链表的操作包括：从链表的头节点开始，依次访问每个节点，直到链表的尾节点。

3.5 查找节点：可以根据节点的值来查找链表中的某一个节点。

查找节点的操作包括：从链表的头节点开始，依次比较每个节点的值，直到找到目标节点或者链表结束。

《数据结构》实验报告学号2015011512 姓名胡明禹专业数学与应用数学时间2018.5.8一、实验题目实验6 二叉树的遍历二、实验目的1. 掌握二叉树的存储思想与建立算法2. 掌握二叉树各种遍历方法的实现思想3. 实现二叉链表的递归遍历算法与非递归遍历算法三、算法设计分析（一）实验内容1.从键盘输入数据，建立一颗含有n个结点的二叉树2.从对二叉树进行先序，中序和后序遍历的递归算法实现，输出遍历序列3.实现先序遍历或中序遍历的非递归算法实现（二）总体设计此处给出主要函数功能、及函数间调用关系的的描述。

例如：①先序创建二叉树函数②先序遍历函数③中序遍历函数④后序遍历函数⑤前序遍历非递归算法⑥中序遍历非递归算法其功能描述如下：（1）主函数：统筹调用各个函数以实现相应功能void main()（2）①先序创建二叉树Status CreateBiTree(BiTree &T){char ch;scanf("%c",&ch);if(ch==' ')T=NULL;else{if(!(T = (BiTNode *)malloc(sizeof(BiTNode))))exit(OVERFLOW); T->data = ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}return OK;}②先序遍历Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e)) {if(T){if(Visit(T->data))if(PreOrderTraverse(T->lchild,Visit))if(PreOrderTraverse(T->rchild,Visit)) return OK;return ERROR;}else return OK;}③中序遍历Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e)) {if(T){if(InOrderTraverse(T->lchild,Visit))if(Visit(T->data))if(InOrderTraverse(T->rchild,Visit)) return OK;return ERROR;}else return OK;}④后序遍历函数Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType e)) {if(T){if(PostOrderTraverse(T->lchild,Visit))if(PostOrderTraverse(T->rchild,Visit))if(Visit(T->data))return OK;return ERROR;}else return OK;}⑤先序遍历非递归算法Status IPreOrderTraverse(BiTree T,Status(*Visit)(TElemType e)) {BiTree p;p=T;int NUM=-1;BiTNode *stack[30];while(p||NUM>0){Visit(p->data);NUM++;stack[NUM]=p;p=p->lchild;while(!p&&NUM>-1){p=stack[NUM];NUM--;p=p->rchild;}}return OK;}⑥中序遍历非递归算法Status IInOrderTraverse(BiTree T,Status(*Visit)(TElemType e)) {BiTree p;p=T;int NUM=0;BiTNode *stack[30];while(p||NUM>0){if(p){stack[NUM++]=p;p=p->lchild;}else{NUM--;p=stack[NUM];if(!Visit(p->data)) return ERROR;p=p->rchild;}}return OK;四、实验测试结果及结果分析（一）测试结果（此处给出程序运行截图）（二）结果分析成功完成了题目的基本操作。

中国石油大学（华东）操作系统课程设计设计报告中国石油大学（华东）计算机科学与技术学院要求（本页打印）：1、双面打印，内容篇幅不要过长（每个实验不要超过3页），禁止贴全部程序，只贴关键代码即可。

2、禁止抄袭3、4、实验1：螺旋矩阵实验——Linux下的C编程一、实验情景描述完成一个程序，要求输入两个数字即可形成相应的字母螺旋矩阵。

例如输入5，6，则程序会生成如下5行6列的矩阵，Z之后循环至A：A B C D E FR S T U V GQ B C D W HP A Z Y X IO N M L K J二、实验原理完成程序ju.c,并用Makefile完成编译。

三、关键代码Makefile如下CC=gccOBJS=ju.oEXEC=juall:$(EXEC)$(EXEC):$(OBJS)$(CC) -o $@ $(OBJS)clean:rm -f $(OBJS) $(EXEC)ju.c部分代码如下int total = 1;char digit = 65;x = 0, y = 0;a[x][y] = 65;while(total < m*n){while(y+1<n&&!a[x][y+1]){if(digit>=90){digit = 64;}a[x][++y] = ++digit;++total;}while(x+1<m&&!a[x+1][y]){if(digit>=90){digit = 64;}a[++x][y] = ++digit;++total;}while(y-1>=0&&!a[x][y-1]){if(digit>=90){digit = 64;}a[x][--y] = ++digit;++total;}while(x-1>=0&&!a[x-1][y]){if(digit>=90){ digit = 64;}a[--x][y] = ++digit;++total; }}四、实验结果实验2：字符串对比实验——Linux下的C编程一、实验情景描述完成一个程序，输入两个字符串，判断其中一个字符串是否是另一个的子串，如果是则输出true，否则输出false。

《数据结构》实验报告学号2015011512 姓名胡明禹专业数学与应用数学时间2018320一、实验题目实验2单链表基本操作二、实验目的1.熟练掌握线性表的顺序存储方式下，基本操作的实现算法，巩固和体会单链表操作特点；2.理解体会动态内存申请与释放；3.通过本次实验，熟练掌握C语言指针的使用三、算法设计分析(一)实验内容1.创建一个空的带头结点的单链表2.采用头插法在单链表中插入n个元素3.删除单链表中第i个元素4.实现单链表按关键字查找操作5.计算单链表的表长并输出单链表6.销毁单链表(二)总体设计此处给出主要函数功能、及函数间调用关系的的描述。

例如：1.构造一个空的单链表的函数；2.插入函数；3.删除函数4.查找函数；5.计算并输出函数；6.销毁函数。

其功能描述如下：(1 )主函数：统筹调用各个函数以实现相应功能void mai n()(2)①构造一个空的单链表的函数Status In itList_L(Li nkList &L){L=(LinkList)malloc(sizeof(LNode));// 构造一个空的线性表L f(!L) exit (OVERFLOW);// 存储分配失败L->next=NULL;〃空表长度为Osystem("cls");〃清空屏幕printf("\n\n 初始化成功\n\n\n"); system("PAUSE");〃按任意键继续return OK;}void CreateList_L(LinkList &L){// 创建一个新表int i,count;LinkList p;system("cls");// 清屏printf("\n 输入总结点数:");scanf("%d",&count);printf("\n 输入各个结点数值，每输一个按下回车：\n");for(i = count; i > 0; i--){p = (LinkList)malloc(sizeof(LNode)); scanf("%d",&p->data);p->next = L->next;L-> next = p;〃赋值}system("cls");// 清屏printf("\n 录入成功\n");}②插入函数Status ListInsert_L(LinkList &L, int i, int newnode){// 在顺序线性表L 中第i 个位置之前插入新的元素LinkList p = L;LinkList s;int j = 0;while(p&&j<i-1){p = p->next;++j;}if(!p||j>i-1)//i 插入的位置不合法{printf("error\n");}s = (LinkList)malloc(sizeof(LNode));s->data = newnode;s->next = p->next;// 将p 的后继结点给s 的后继结点p->next = s;// 将s 给p 的后继结点return OK;}③删除函数Status ListDelete_L(LinkList &L, int i){//在顺序线性表L中删除第i个元素，并用e返回其值LinkList p=L;LinkList q;int j=0;while(p->next&&j<i-1)// 如果满足这样的条件{p = p->next;++j;}if(!(p->next)||j>i-1) return ERROR;// 删除位置非法q= p->next;// 将p 的后继结点给qp->next = q->next;// 将q 的后继结点给p 的后继结点printf("\n\n 删除成功\n\n 被删除的结点是：%d\n",q->data); free(q);return OK;}④查找函数Status FindElemList_L(LinkList &L){// 单链表按照关键字查询LinkList p;int i=1,NUMBER;int n=0;p = L->next;printf("\n 输入查询数字：");scanf("%d",&NUMBER);while(p){if(p->data==NUMBER){printf("\n 查询成功！该数字位于结点%d\n",i);n++;}p = p->next;i++;}if(!n){printf("\n 查询失败！未找到该元素！\n");}return OK;}⑤计算并输出函数Status PrintList_L(LinkList &L){// 输出链表m=0;LinkList p;p=L;printf("\n");while(p->next!=NULL)// 当链表非空{p=p->next;printf("%d: %d\n",++m,p->data);// 输出}printf("\n");return OK;}⑥销毁函数Status DestroyList_L(LinkList &L) // 销毁单链表{ LinkList p, q;p=L;while(p){q=p;p=p->next;free(q); // 释放}if(p==NULL)printf("\n 成功，请退出\n\n");elseprintf （” 失败 \n"）;return OK;}四、实验测试结果及结果分析（一）测试结果（此处给出程序运行截图）'D:\Microsoft Visual Studio\Common\MSDev98\Bin\Debug\hmy_3 27nexe'入成功I 希W'.羊.:-*;-辛吊fi:j ^_ 单— —ic*i3.l wi 6On 冷】•♦•***・*2默#欲譎值：9 • 'O A IA^OW H Vnual Stu4»o \Com«i^rAM$0«vW^rAD<^u9\hn»yJ.2?.ex ,■ ' •WMcp'S V HIO I JwdoXQnvrcrAMSO^v^VBAQ^bvgfmy,業单»<»<»«><> 歩 兀奠 单屢 S 8S —i2c *s 4-u i&7.a年％去的去长为，7 请祐儀泄注・・・12J 15 门7 £ 4Z 人人障九 2r 44u *j 6x a • • •0\Mig5e 々、“2 女u£*OE»M \M5De*^2"d>e0jaE谓捜衽苜槌熨冬•・・ 7 6 L4 9 2匝内，诵怎出清馬任社情辭紈・■!• ■D H \ME M H 七畔叽|细6占说“血射衬翻、伯e 翱诃津《jwbuqmb 」£T ・Ee"（二）结杲分析 成功完成了题冃所要求的插入，删除，查找等基本操作。

数据库实验上机答案解析整编中国石油大学龚安实验四SQL练习2一、实验目的1．掌握索引的建立、删除及使用；2．掌握单表查询、连接查询、嵌套查询和集合查询；3．掌握插入数据、修改数据和删除数据语句的非常用形式。

二、实验学时2学时三、实验内容1．利用Query Analyzer完成以下操作：⑴在预算日期、结算日期和入账日期上分别建立索引，并在查询操作中体会索引的作用。

⑵在完成第2题的查询操作后，删除预算日期、结算日期和入账日期上的索引。

2．利用Query Analyzer完成以下操作：⑴采油一矿二队2016-5-1到2016-5-28有哪些项目完成了预算，列出相应明细。

⑵采油一矿二队2016-5-1到2016-5-28有哪些项目完成了结算，列出相应明细。

⑶采油一矿二队2016-5-1到2016-5-28有哪些项目完成了结算，列出相应的材料费消耗明细。

⑷采油一矿二队2016-5-1到2016-5-28有哪些项目完成了入账，列出相应明细。

⑸列出采油一矿二队2016-5-1到2016-5-28总的预算金额。

⑹列出采油一矿二队2016-5-1到2016-5-28总的结算金额。

⑺列出采油一矿二队2016-5-1到2016-5-28总的入账金额。

⑻列出采油一矿2016-5-1到2016-5-28总的入账金额。

⑼有哪些人员参与了入账操作。

⑽列出2016-5-1到2016-5-28进行了结算但未入账的项目。

⑾列出采油一矿二队的所有项目，按入账金额从高到低排列。

⑿列出有哪些施工单位实施了项目，并计算各单位所有项目结算金额总和。

⒀找出消耗了材料三且消耗超过了2000元的项目，列出相应消耗明细(利用子查询)。

⒁作业公司二队参与了哪些项目。

⒂作业公司一队和二队参与了哪些项目（利用union）。

⒃采油一矿的油井是哪些作业队参与施工的。

3．利用Query Analyzer完成以下操作：⑴建立数据表(包含3个属性列：★施工单位、★年月、◆结算金额)保存各个施工单位每月的结算金额总和。

中国石油大学（北京）远程教育学院期末考试《数据结构》课程设计1.课程设计题目从下面四个题目中任选一题完成。

1.1 通讯录的制作用单链表作为数据结构，结合C或者C++语言基本知识，编写一个班级的通讯录管理系统。

系统包括下面几方面的功能：第1：输入信息：输入某同学的信息；第2：显示信息：显示全部通讯录中学生的信息；第3：查找功能：实现按姓名进行查找，并给出查找信息；第4：删除功能：实现按姓名进行删除，并给出操作结果；第5：每名同学的信息包括：姓名、性别、电话、城市；第6：界面友好，每步给出适当的操作提示；第7：系统具有一定的容错能力。

1.2 图书管理系统设计一个计算机管理系统完成图书管理几本业务。

系统要满足下面基本要求：第1：每种图书的登记内容包括：书名、书号、作者、出版社、现存量和库存量；第2：采编入库：新购图书，确定书号后，登记到图书账目表中，如果表中存在该书，则只将库存量增加；第3：借阅：如果该书的库存量大于0，则借出一本，登记借阅者的书证号和归还期限，改变库存量；第4：归还：注销对借阅者的登记，改变该书的库存量；第5：界面友好，每步给出适当的操作提示；第6：系统具有一定的容错能力。

1.3 产品进销管理系统针对某个行业的库房产品进销存情况进行管理，系统要求具有下列功能：第1：采用一定的存储结构对库房的货品及其数量进行分类管理；第2：可以进行产品类的添加、产品的添加、产品数量的添加；第3：能够查询库房每种产品的总量、进货日期、销出数量、销售时间等；第4：每种产品至少包含信息：产品名、进货日期、进货数量、销出数量、销售时间、库存量；第5：界面友好，每步给出适当的操作提示；第6：系统具有一定的容错能力。

1.4 校园导航问题设计中国石油大学（北京）的校园平面图，至少包括10个场所，可以实现任意两个场所的最短路径。

2.课程设计报告书写规范课程设计报告包括该题目的需求分析、概要设计、详细设计、程序测试、感想与体会几部分内容。

上机实验要求及规范《数据结构》课程具有比较强的理论性，同时也具有较强的可应用性和实践性，因此上机实验是一个重要的教学环节。

一般情况下学生能够重视实验环节，对于编写程序上机练习具有一定的积极性，但是容易忽略实验的总结，忽略实验报告的撰写。

对于一名大学生必须严格训练分析总结能力、书面表达能力。

需要逐步培养书写科学实验报告以及科技论文的能力。

拿到一个题目，一般不要急于编程，而是应该按照面向过程的程序设计思路（关于面向对象的训练将在其它后继课程中进行），首先理解问题，明确给定的条件和要求解决的问题，然后按照自顶向下，逐步求精，分而治之的策略，逐一地解决子问题。

具体步骤如下：1.问题分析与系统结构设计充分地分析和理解问题本身，弄清要求做什么（而不是怎么做），限制条件是什么。

按照以数据结构为中心的原则划分模块，搞清数据的逻辑结构（是线性表还是树、图？），确定数据的存储结构（是顺序结构还是链表结构？），然后设计有关操作的函数。

在每个函数模块中，要综合考虑系统功能，使系统结构清晰、合理、简单和易于调试。

最后写出每个模块的算法头和规格说明，列出模块之间的调用关系（可以用图表示），便完成了系统结构设计。

2.详细设计和编码详细设计是对函数（模块）的进一步求精，用伪高级语言（如类C语言）或自然语言写出算法框架，这时不必确定很多结构和变量。

编码，即程序设计，是对详细设计结果的进一步求精，即用某种高级语言（如C/C++语言）表达出来。

尽量多设一些注释语句，清晰易懂。

尽量临时增加一些输出语句，便于差错矫正，在程序成功后再删去它们。

3.上机准备熟悉高级语言用法，如C语言。

熟悉机器（即操作系统），基本的常用命令。

静态检查主要有两条路径，一是用一组测试数据手工执行程序（或分模块进行）；二是通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑，在这个过程中再加入一些注释和断言。

如果程序中逻辑概念清楚，后者将比前者有效。

4.上机调试程序调试最好分块进行，自底向上，即先调试底层函数，必要时可以另写一个调用驱动程序，表面上的麻烦工作可以大大降低调试时所面临的复杂性，提高工作效率。

实验八数据库应用编程1．查阅资料，了解并理解数据库的数据访问接口技术，如：ODBC、JDBC、OLE DB、ADO、等，并形成一个简要的数据访问接口技术总结；所谓访问接口是指分布式环境中保证操作系统、通信协议、数据库等之间进行对话、互操作的软件系统。

访问接口的作用是保证网络中各部件（软件和硬件）之间透明地连接，即隐藏网络部件的异构性，尤其保证不同网络、不同DBMS和某些访问语言的透明性，即下面三个透明性。

⑴网络透明性：能支持所有类型的网络。

⑵服务器透明性：不管服务器上的DBMS是何种型号（ORACLE、SYBASE、DB2等），一个好的访问接口都能通过标准的SQL语言与不同DBMS上的SQL语言连接起来。

⑶语言透明性：客户机可用任何开发语言进行发送请求和接受回答，被调用的功能应该像语言那样也是独立的。

ＯＤＢＣ：Mcrosoft推出的ODBC(Open Database Connectivity)技术为异质数据库的访问提供了统一的接口。

ODBC基于SQL(Structured Query Language),并把它作为访问数据库的标准。

这个接口提供了最大限度的相互可操作性:一个应用程序可以通过一组通用的代码访问不同的数据库管理系统。

一个软件开发者开发的客户/服务器应用程序不会被束定于某个特定的数据库之上。

ODBC可以为不同的数据库提供相应的驱动程序。

ODBC的灵活性表现在以下几个方面：应用程序不会受制于某种专用的APISQL语句以源代码的方式直接嵌入在应用程序中应用程序可以以自己的格式接收和发送数据ODBC的设计完全和ISO Call-Level Interface兼容一些与ODBC有关的名词：ODBC驱动程序：是一个动态链接库(DLL)，用以将特定的开放式数据库连接的数据源和另一个应用程序（客户端）相连接。

ODBC数据源：作为数据源使用的数据库或数据库服务器。

ODBC数据源通过它们的数据源名称来引用，或者通过具体引用ODBC驱动程序和服务器名称来引用。

⽯⼤数据结构实验报告1实验⼀1、题⽬：折半法查找有序数组中数据元素。

2、问题描述：分别设计折半查找问题的递归函数，循环结构函数，并设计测试主函数进⾏测试，⾄少包括⼀个查找成功例⼦和⼀个失败例⼦。

3、基本要求：1）将0~9999，10000个有序的整型数据元素放在数组a中。

2）设计折半查找问题的递归函数。

3）设计折半查找问题的循环结构函数。

4）设计测试主程序，4、测试数据：SLNode *head;//定义头指针变量int i,x;ListInitiate(&head);//初始化for(i=0;i<10;i++)//插⼊10个数据元素ListInsert(head,i,2*i);printf("原数据元素输出为：");Listprint(head);//调⽤输出函数，依次输出原数据元素ListDelete(head,4,&x);//删除第5个数据元素printf("\n删除后数据元素输出为：");Listprint(head);//调⽤输出函数，依次输出删除后的数据元素printf("\n");Destroy(&head);//撤销循环单链表5、算法思想：初始化函数：初始化操作前，头指针参数head没有具体的地址值，在初始化操作后，头指针参数head才得到了具体的地址值，⽽这个地址值要返回给调⽤函数，所以，此时头指针参数head要设计成指针类型的指针。

求当前数据元素个数函数：循环前，指针变量p指向头结点，计数变量size等于0；循环的结束条件为p->next!=head,循环中，每次让头指针p指向它的直接后继点，让计数数量size加1；最终函数循环返回数值size。

插⼊函数：使指针p指向第i-1个结点，动带申请⼀个结点存储空间并由指针q 指⽰，把数据元素x的值赋予新结点的数据元素域，最后修改新结点的指针域指向i个结点，并修改i-1结点的指针域使之指向新结点p；循环条件由条件逻辑与组成，其中⼦条件p->next!=head保证指针所指向结点存在，⼦条件j删除函数：使指针p指向第i-1个结点，然后让指针s指向i结点，并把数据元素的数据域值赋予x，最后把第i个结点脱链，并动态释放结点的存储空间；循环条件有三个⼦条件逻辑与组成，其中⼦条件p->next!=head保证第i-1个结点存在，⼦条件p->next->!=head保证第i个结点存在，⼦条件j取数据元素函数：和删除函数基本相同，主要差别是，取数据元素函数的循环的循环条件改为j6、模块划分：1）定义单链表结点的结构体。

中国⽯油⼤学数据结构课程设计——数据结构（C语⾔）课程设计题⽬：可视化弗洛伊德最短路径⼀．实习⽬的通过实习，了解并初步掌握设计、实现较⼤系统的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作⽅法，为进⼀步的应⽤开发打好基础。

⼆．问题描述设计、实现随机或⼿动建⽴⼀个有向图，可以使⽤弗洛伊德算法输出有向图中节点之间最短路径及权值，并把有向图和弗洛伊德算法得出的最短路径及最⼩权值可视化。

三．需求分析（1）可随机建⽴有向图，并在屏幕上使图可视化；（2）可⼿动建⽴有向图，添加节点、删除节点、移动节点、添加边、删除边、设置权值，并在屏幕上使图可视化；（3）对已建⽴的有向图实现弗洛伊德算法找出最短路径，并在屏幕上使最短路径及最⼩权值矩阵可视化；四．概要设计．系统中⼦程序及功能要求：数据对象V：⼀个集合，该集合中的所有元素具有相同的特性数据关系R：R={VR}VR={|P(x,y)^(x,y属于V)}（1）OnButtonCreategraph()//随机建图按钮；（2）OnButtonHuman()//⼿动建图按钮；（3）OnButtonAddvertex()//添加节点按钮；（4）OnButtonDeletevertex()//删除节点按钮；（5）OnButtonMovevertex()//移动节点按钮；（6）OnButtonAddedge()//添加边按钮；（7）OnButtonDeleteedge()//删除边按钮；（8）OnButtonSetweight()//设置权值按钮；（9）OnButtonFloyd()//弗洛伊德算法按钮；（10）DrawDGRandom(TCenterPoint, pDC)//随机建图；（11）DrawDiGraph(CDC *pDC)//图可视化；（12）DrawVexs(CDC *pDC)//节点可视化；（14）InitHand()//存储节点；（15）CreateDGHand(CPoint centerpoint)//⼿动建图；（16）AddVertsHand()//添加节点；（17）DeleteVex(CPoint vPoint)//删除节点；（18）AddEdgesHand()//添加边；（19）DeleteEdge(CGraphVertex* pBeginVex, CGraphVertex* pEndVex)//删除边；（20）SetEdgeWeightHand ()//设置权值；（21）Floyd()//弗洛伊德算法；（22）DrawFloyd(CDC *pDC)//弗洛伊德可视化；各程序模块之间的调⽤关系（⼦程序编号见上）：主函数可调⽤⼦程序 1、2、3、4、5、6、7、8、9⼦程序1可调⽤⼦程序10⼦程序2、3可调⽤⼦程序14、15⼦程序3可调⽤⼦程序16⼦程序4可调⽤⼦程序17⼦程序6可调⽤⼦程序18⼦程序7可调⽤⼦程序19⼦程序8可调⽤⼦程序20⼦程序9可调⽤⼦程序21⼦程序10可调⽤⼦程序11⼦程序16可调⽤⼦程序12⼦程序17可调⽤⼦程序12、19⼦程序18、19、20可调⽤⼦程序13⼦程序21可调⽤⼦程序22五．测试分析按照附录中的测试数据，得出如下测试、分析结果：1.建图功能：（1）随机建图：随机去顶节点的个数与位置及节点之间边的连接、⽅向与权值⼤⼩，并在屏幕上输出图结构；测试结果：可随机输出⼀有向图。