《数据结构实验C语言版(共72页).doc》由会员分享,可在线阅读,更多相关《数据结构实验C语言版(共72页).doc(72页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、精选优质文档-倾情为你奉上南阳理工学院数据结构(C语言版)上机实验指导书软件学院软件工程目 录476 4专心-专注-专业实验1 线性表应用一、 实验目的3,了解和掌握线性表顺序存储和链式存储在计算机中的表示,基本操做在计算机中的实2,能够利用线性表结构对实际问题进行分析建模,利用计算机求解。1,能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。二、实验内容及步骤 1、利用程序设计语言分别实现顺序表和链表的抽象数据类型。2、掌握程序分文件(头文件和实现文件)书写的方式。3、分别用顺序表和链表实现课本算法2.2:合并两个非递减有序序列,并对其时间性能做出分析。三、实验步
2、骤与调试过程 以线性表来描述一元多项式,储存结构采用单链表,每个结点储存的多项式中某一项的系数和指数,建立单链表时指数高的结点列于指数低的结点之后,即线性表的元素按指数递增有序排列。四、实验结果五、疑难小结 当线性表的长度变化较大,难以估计其存储规模,另外对线性表频繁进行插入和删除操作时,则采用链表作为存储结构可能会更好一些。在实际应用中应该考虑以下因素:(1)应有利于运算的实现;(2)应有利于数据的特性;(3)应有利于软件环境。六、主要算法和程序清单顺序表的非递减数列合并#include/*包含输入输出头文件*/#define ListSize 100typedef int DataType
3、;typedef structDataType listListSize;int length;SeqList;void InitList(SeqList *L) /*将线性表初始化为空的线性表只需要把线性表的长度length置为0*/L-length=0;/*把线性表的长度置为0*/int ListEmpty(SeqList L) /*判断线性表是否为空,线性表为空返回1,否则返回0*/ if(L.length=0)/*判断线性表的长度是否为9*/ return 1;/*当线性表为空时,返回1;否则返回0*/ else return 0;int GetElem(SeqList L,int i
4、,DataType *e) /*查找线性表中第i个元素。查找成功将该值返回给e,并返回1表示成功;否则返回-1表示失败。*/if(iL.length) /*在查找第i个元素之前,判断该序号是否合法*/ return -1;*e=L.listi-1;/*将第i个元素的值赋值给e*/ return 1;int LocateElem(SeqList L,DataType e) /*查找线性表中元素值为e的元素,查找成功将对应元素的序号返回,否则返回0表示失败。*/ int i;for(i=0;iL.length;i+) /*从第一个元素开始比较*/ if(L.listi=e)return i+1;r
5、eturn 0;int InsertList(SeqList *L,int i,DataType e) /*在顺序表的第i个位置插入元素e,插入成功返回1,如果插入位置不合法返回-1,顺序表满返回0*/ int j;if(iL-length+1)/*在插入元素前,判断插入位置是否合法*/ printf(插入位置i不合法!n); return -1;else if(L-length=ListSize)/*在插入元素前,判断顺序表是否已经满,不能插入元素*/printf(顺序表已满,不能插入元素。n);return 0;elsefor(j=L-length;j=i;j-)/*将第i个位置以后的元素
6、依次后移*/L-listj=L-listj-1; L-listi-1=e;/*插入元素到第i个位置*/ L-length=L-length+1;/*将顺序表长增1*/return 1;int DeleteList(SeqList *L,int i,DataType *e) int j; if(L-length=0) printf(顺序表已空不能进行删除!n); return 0; else if(iL-length) printf(删除位置不合适!n); return -1; else *e=L-listi-1; for(j=i;jlength-1;j+) L-listj-1=L-listj;
7、 L-length=L-length-1; return 1; int ListLength(SeqList L) return L.length;void ClearList(SeqList *L)L-length=0;void MergeList(SeqList A,SeqList B,SeqList *C);/*合并顺序表A和B中元素的函数声明*/void main()int i,flag;DataType a=6,11,11,23;DataType b=2,10,12,12,21;DataType e;SeqList A,B,C;/*声明顺序表A,B和C*/InitList(&A);/
8、*初始化顺序表A*/InitList(&B);/*初始化顺序表B*/InitList(&C);/*初始化顺序表C*/for(i=1;i=sizeof(a)/sizeof(a0);i+)/*将数组a中的元素插入到顺序表A中*/if(InsertList(&A,i,ai-1)=0)printf(位置不合法);return;for(i=1;i=sizeof(b)/sizeof(b0);i+)/*将数组b中元素插入到顺序表B中*/if(InsertList(&B,i,bi-1)=0)printf(位置不合法);return;printf(顺序表A中的元素:n);for(i=1;i=A.length;i
9、+)/*输出顺序表A中的每个元素*/flag=GetElem(A,i,&e);/*返回顺序表A中的每个元素到e中*/if(flag=1)printf(%4d,e);printf(n);printf(顺序表B中的元素:n);for(i=1;i=B.length;i+)/*输出顺序表B中的每个元素*/flag=GetElem(B,i,&e);/*返回顺序表B中的每个元素到e中*/if(flag=1)printf(%4d,e);printf(n);printf(将在A中出现B的元素合并后C中的元素:n);MergeList(A,B,&C);/*将在顺序表A和B中的元素合并*/for(i=1;i=C.
10、length;i+)/*显示输出合并后C中所有元素*/flag=GetElem(C,i,&e);if(flag=1)printf(%4d,e);printf(n);getch();void MergeList(SeqList A,SeqList B,SeqList *C)/*合并顺序表A和B的元素到C中,并保持元素非递减排序*/int i,j,k;DataType e1,e2;i=1;j=1;k=1;while(i=A.length&j=B.length)GetElem(A,i,&e1);/*取出顺序表A中的元素*/GetElem(B,j,&e2);/*取出顺序表B中的元素*/if(e1=e2
11、)/*比较顺序表A和顺序表B中的元素*/InsertList(C,k,e1);/*将较小的一个插入到C中*/i+;/*往后移动一个位置,准备比较下一个元素*/k+;elseInsertList(C,k,e2);/*将较小的一个插入到C中*/j+;/*往后移动一个位置,准备比较下一个元素*/k+;while(i=A.length)/*如果A中元素还有剩余,这时B中已经没有元素*/GetElem(A,i,&e1);InsertList(C,k,e1);/*将A中剩余元素插入到C中*/i+;k+;while(jlength=A.length+B.length;/*C的表长等于A和B的表长的和*/l
12、链式表的非递减数列合并/*包含头文件*/#include#include#include/*宏定义和单链表类型定义*/#define ListSize 100typedef int DataType;typedef struct Node DataType data; struct Node *next;ListNode,*LinkList;void MergeList(LinkList A,LinkList B,LinkList *C);/*将单链表A和B的元素合并到C中的函数声明*/void InitList(LinkList *head)/*将单链表初始化为空。动态生成一个头结点,并将头
13、结点的指针域置为空。*/if(*head=(LinkList)malloc(sizeof(ListNode)=NULL)/*为头结点分配一个存储空间*/exit(-1);(*head)-next=NULL;/*将单链表的头结点指针域置为空*/int ListEmpty(LinkList head) /*判断单链表是否为空,就是通过判断头结点的指针域是否为空*/ if(head-next=NULL)/*判断单链表头结点的指针域是否为空*/ return 1;/*当单链表为空时,返回1;否则返回0*/ else return 0;ListNode *Get(LinkList head,int i)
14、 /*查找单链表中第i个结点。查找成功返回该结点的指针表示成功;否则返回NULL表示失败。*/ListNode *p;int j;if(ListEmpty(head)/*在查找第i个元素之前,判断链表是否为空*/return NULL;if(inext!=NULL&jnext;j+;if(j=i)return p;/*找到第i个结点,返回指针p*/elsereturn NULL;/*如果没有找到第i个元素,返回NULL*/ListNode *LocateElem(LinkList head,DataType e) /*查找线性表中元素值为e的元素,查找成功将对应元素的结点指针返回,否则返回NU
15、LL表示失败。*/ListNode *p;p=head-next;/*指针p指向第一个结点*/while(p)if(p-data!=e)/*找到与e相等的元素,返回该序号*/p=p-next;elsebreak;return p;int LocatePos(LinkList head,DataType e) /*查找线性表中元素值为e的元素,查找成功将对应元素的序号返回,否则返回0表示失败。*/ListNode *p;int i;if(ListEmpty(head)/*在查找第i个元素之前,判断链表是否为空*/return 0;p=head-next;/*指针p指向第一个结点*/i=1;whi
16、le(p)if(p-data=e)/*找到与e相等的元素,返回该序号*/return i;elsep=p-next;i+;if(!p)/*如果没有找到与e相等的元素,返回0,表示失败*/return 0;int InsertList(LinkList head,int i,DataType e)/*在单链表中第i个位置插入一个结点,结点的元素值为e。插入成功返回1,失败返回0*/ListNode *p,*pre;/*定义指向第i个元素的前驱结点指针pre,指针p指向新生成的结点*/int j;pre=head;/*指针p指向头结点*/j=0;while(pre-next!=NULL&jnext
17、;j+;if(!pre)/*如果没找到,说明插入位置错误*/printf(插入位置错);return 0;/*新生成一个结点,并将e赋值给该结点的数据域*/if(p=(ListNode*)malloc(sizeof(ListNode)=NULL)exit(-1);p-data=e;/*插入结点操作*/p-next=pre-next;pre-next=p;return 1;int DeleteList(LinkList head,int i,DataType *e)/*删除单链表中的第i个位置的结点。删除成功返回1,失败返回0*/ListNode *pre,*p;int j; pre=head;
18、 j=0; while(pre-next!=NULL&pre-next-next!=NULL&jnext; j+; if(j!=i-1)/*如果没找到要删除的结点位置,说明删除位置错误*/ printf(删除位置错误); return 0;/*指针p指向单链表中的第i个结点,并将该结点的数据域值赋值给e*/ p=pre-next;*e=p-data;/*将前驱结点的指针域指向要删除结点的下一个结点,也就是将p指向的结点与单链表断开*/ pre-next=p-next; free(p);/*释放p指向的结点*/ return 1;int ListLength(LinkList head) Lis
19、tNode *p; int count=0; p=head; while(p-next!=NULL) p=p-next; count+; return count;void DestroyList(LinkList head) ListNode *p,*q; p=head; while(p!=NULL)q=p; p=p-next; free(q); void main()int i;DataType a=6,7,9,14,37,45,65,67;DataType b=3,7,11,34,45,89;LinkList A,B,C;/*声明单链表A和B*/ListNode *p;InitList(
20、&A);/*初始化单链表A*/InitList(&B);/*初始化单链表B*/for(i=1;i=sizeof(a)/sizeof(a0);i+)/*将数组a中元素插入到单链表A中*/if(InsertList(A,i,ai-1)=0)printf(位置不合法);return;for(i=1;i=sizeof(b)/sizeof(b0);i+)/*将数组b中元素插入单链表B中*/if(InsertList(B,i,bi-1)=0)printf(位置不合法);return;printf(单链表A中的元素有%d个:n,ListLength(A);for(i=1;idata);/*输出单链表A中的每
21、个元素*/printf(n);printf(单链表B中的元素有%d个:n,ListLength(B);for(i=1;idata);/*输出单链表B中的每个元素*/printf(n);MergeList(A,B,&C);/*将单链表A和B中的元素合并到C中*/printf(将单链表A和B的元素合并到C中后,C中的元素有%d个:n,ListLength(C);for(i=1;idata);/*显示输出C中所有元素*/printf(n);getch();void MergeList(LinkList A,LinkList B,LinkList *C)/*单链表A和B中的元素非递减排列,将单链表A和
22、B中的元素合并到C中,C中的元素仍按照非递减排列*/ListNode *pa,*pb,*pc;/*定义指向单链表A,B,C的指针*/pa=A-next;pb=B-next;*C=A;/*将单链表A的头结点作为C的头结点*/(*C)-next=NULL;pc=*C;/*依次将链表A和B中较小的元素存入链表C中*/while(pa&pb)if(pa-datadata)pc-next=pa;/*如果A中的元素小于或等于B中的元素,将A中的元素的结点作为C的结点*/pc=pa;pa=pa-next;elsepc-next=pb;/*如果A中的元素大于B中的元素,将B中的元素的结点作为C的结点*/pc=
23、pb;pb=pb-next;pc-next=pa?pa:pb;/*将剩余的结点插入C中*/free(B);/*释放B的头结点*/实验2 栈和队列的应用一、实验目的1、掌握栈和队列这两种抽象数据类型的特点,并能在相应的应用问题中正确选用它们。2、熟练掌握栈类型的两种实现方法。3、熟练掌握循环队列和链队列的基本操作实现算法。二、实验内容及步骤 1、用程序设计语言实现栈和队列的抽象数据类型。2、在第一题的基础上完成以下选择:选择一:1) 设计并实现括号匹配算法。2) 用队列实现在屏幕上打印杨辉三角。选择二:分别用栈和队列实现迷宫问题求解。选择三:分别用栈和队列实现一个列车调度系统。三、实验步骤与调试
24、过程 首先只只置操作数栈为空,表达式起始符“#”为运算符栈的栈底元素,依次读入表达式中每个字符,直至整个表达式求值完毕。四、实验结果五、疑难小结对栈的顺序存储结构用了更深刻的了解,同时也对程序设计能力有了提高,加深了对栈先进后出性质的理解,对数组的应用也十分熟练。六、主要算法:l 括号匹配算法。#include#include#include#include string.h/*宏定义和链栈类型定义*/typedef char DataType;int Match(DataType e,DataType ch);typedef struct node DataType data; struct
25、 node *next;LStackNode,*LinkStack;void InitStack(LinkStack *top)/*将链栈初始化为空。动态生成头结点,并将头结点的指针域置为空。*/if(*top=(LinkStack)malloc(sizeof(LStackNode)=NULL)/*为头结点分配一个存储空间*/exit(-1);(*top)-next=NULL;/*将链栈的头结点指针域置为空*/int StackEmpty(LinkStack top) /*判断链栈是否为空,就是通过判断头结点的指针域是否为空*/ if(top-next=NULL)/*判断链栈头结点的指针域是否
26、为空*/ return 1;/*当链栈为空时,返回1;否则返回0*/ else return 0;int PushStack(LinkStack top, DataType e)/*进栈操作就是要在链表的第一个结点前插入一个新结点,进栈成功返回1*/LStackNode *p;/*定义指向第i个元素的前驱结点指针pre,指针p指向新生成的结点*/if(p=(LStackNode*)malloc(sizeof(LStackNode)=NULL)printf(内存分配失败!);exit(-1);p-data=e;/*指针p指向头结点*/p-next=top-next;top-next=p;retu
27、rn 1;int PopStack(LinkStack top,DataType *e)/*删除单链表中的第i个位置的结点。删除成功返回1,失败返回0*/LStackNode *p; p=top-next; if(!p)/*判断链栈是否为空*/ printf(栈已空); return 0; top-next=p-next;/*将栈顶结点与链表断开,即出栈*/*e=p-data;/*将出栈元素赋值给e*/ free(p);/*释放p指向的结点*/ return 1;int StackLength(LinkStack top) LStackNode *p; int count=0; p=top;
28、while(p-next!=NULL) p=p-next; count+; return count;void DestroyStack(LinkStack top) LStackNode *p,*q; p=top; while(!p) q=p; p=p-next; free(q); int GetTop(LinkStack top,DataType *e)LStackNode *p; p=top-next; if(!p)/*判断链栈是否为空*/ printf(栈已空); return 0; *e=p-data;/*将出栈元素赋值给e*/ return 1;void main() LinkSt
29、ack S;char *p;DataType e;DataType ch60;InitStack(&S);/*初始化链栈*/printf(请输入带括号的表达式(,().n);gets(ch);p=ch;while(*p)switch(*p)case (:case :case :PushStack(S,*p+);break;case ):case :case :if(StackEmpty(S)printf(缺少左括号.n);return;elseGetTop(S,&e);if(Match(e,*p)PopStack(S,&e);elseprintf(左右括号不配对.n);return;defau
30、lt:p+;if(StackEmpty(S)printf(括号匹配.n);elseprintf(缺少右括号.n);int Match(DataType e,DataType ch)if(e=(&ch=)return 1;else if(e=&ch=)return 1;else if(e=&ch=)return 1;elsereturn 0;l 用队列实现在屏幕上打印杨辉三角/*包含头文件*/#include#includetypedef int DataType;/*定义链式队列元素的类型为整数类型*/#define MaxSize 100void PrintArray(int a,int n
31、);void YangHuiTriangle(int N);typedef struct QNodeDataType data;struct QNode* next;LQNode,*QueuePtr;typedef structQueuePtr front;QueuePtr rear;LinkQueue;void InitQueue(LinkQueue *LQ) /*将带头结点的链式队列初始化为空队列需要把头结点的指针域置为0*/LQ-front=(LQNode*)malloc(sizeof(LQNode);if(LQ-front=NULL) exit(-1); LQ -front-next=
32、NULL;/*把头结点的指针域置为为0*/LQ-rear=LQ-front;int QueueEmpty(LinkQueue LQ) /*判断链式队列是否为空,队列为空返回1,否则返回0*/if(LQ.front-next=NULL)/*当链式队列为空时,返回1,否则返回0*/ return 1; else return 0;int EnterQueue(LinkQueue *LQ,DataType e)/*将元素e插入到链式队列LQ中,插入成功返回1*/ LQNode *s;s=(LQNode*)malloc(sizeof(LQNode);/*为将要入队的元素申请一个结点的空间*/if(!s
33、) exit(-1);/*如果申请空间失败,则退出并返回参数-1*/s-data=e;/*将元素值赋值给结点的数据域*/s-next=NULL;/*将结点的指针域置为空*/LQ-rear-next=s;/*将原来队列的队尾指针指向p*/LQ-rear=s;/*将队尾指针指向p*/ return 1;/int DeleteQueue(LinkQueue *LQ,DataType *e)/*删除链式队列中的队头元素,并将该元素赋值给e,删除成功返回1,否则返回0*/ LQNode *s;/if(LQ-front=LQ-rear)/*在删除元素之前,判断链式队列是否为空*/ return 0;/ e
34、lse/ s=LQ-front-next;/*使指针p指向队头元素的指针*/ *e=s-data;/*将要删除的队头元素赋值给e*/ LQ-front-next=s-next;/*使头结点的指针指向指针p的下一个结点*/ if(LQ-rear=s) LQ-rear=LQ-front;/*如果要删除的结点是队尾,则使队尾指针指向队头指针*/ free(s);/*释放指针p指向的结点*/ return 1;/ /int GetHead (LinkQueue LQ,DataType *e)/*取链式队列中的队头元素,并将该元素赋值给e,取元素成功返回1,否则返回0*/ LQNode *s;if(LQ
35、.front=LQ.rear)/*在取队头元素之前,判断链式队列是否为空*/return 0;elses=LQ.front-next;/*将指针p指向队列的第一个元素即队头元素*/*e=s-data;/*将队头元素赋值给e,取出队头元素*/return 1;/*出队操作。*/int DeleteQueue(LinkQueue *Q,DataType *x) /* 将队列Q的队头元素出队,并存放到x所指的存储空间中 */LQNode * p;if(Q-front=Q-rear)return(0);p=Q-front-next;Q-front-next=p-next; /* 队头元素p出队 */if(Q-front=NULL) /* 如果队中只有一个元素p,则p出队后成为空队 */Q-rear=Q-front; *x=p-data;free(p); /* 释放存储空间 */return(1);void YangHuiTriangle(int N)/*链式队列实现打印杨辉三角*/ int i,j,k,n;DataType e,t;int temp
限制150内