数据结构课程设计实验1-4(C语言)

1、实验一 顺序表的操作1、实验目的和要求：1）了解顺序表的基本概念、顺序表结构的定义及在顺序表上的基本操作(插入、删除、查找以及线性表合并)。2) 通过在visual C+实现以上操作的C语言代码。3）提前了解实验相关的知识（尤其是C语言）。2、实验内容：1) 顺序表的插入算法,删除算法,顺序表的合并算法2) 顺序表应用的实例（二选一）a) 利用顺序表的基本运行，实现如果在顺序表A中出现的元素，在顺序表B中也出现，则在顺序表A中将该元素删除。及实现A-B。b) 顺序表A和B的元素都是非递减排列，将他们合并成一个顺序表C，要求C也是非递减排列。3、部分参考实验代码： 顺序表结构的定义：#inclu

2、de #define ListSize 100typedef int DataType;typedef structDataType listListSize;int length;SeqList; 顺序表插入（在第i号元素前插入一个新的元素）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-l

3、ength=ListSize)/*在插入元素前，判断顺序表是否已经满，不能插入元素*/printf(顺序表已满，不能插入元素。n);return 0;elsefor(j=L-length;j=i;j-)/*将第i个位置以后的元素依次后移*/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

4、); 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; L-length=L-length-1; return 1; 实验二 单链表的操作1、实验目的 1）掌握用Visual C+6.0上机调试单链表的基本方法2）理解链表的基本操作、了解链表的建立和输出3）掌握链表的插入、删除、合并和归并等实现方法2、实现内容 1、单链表基本操作的实现2、链表应用的实例（二选一）a) 利用链表的基本运行，实现如果在链表A中出

5、现的元素，在链表B中也出现，则在链表A中将该元素删除。b)、约瑟夫（Josephus）问题的求解（循环链表的使用，使用C和C+语言均可）。假设有编号为1，2，n的n个人围坐成一圈，约定从编号为k（n=k=1）的人开始报数，数到m的那个人出列，他的下一个人从1开始重新报数，数到m的那个人出列，依次类推，直到所有的人全部出列为止，由此产生一个出队编号的序列。1、给定一个8个人的圈（n=8），约定从第3个人开始报数（k3），数到第4个人时的那个人出列（m4），使用循环链表，产生一个出队编号的序列。2、参考的出队序列为：。3、部分参考实验代码：1、结点定义typedef int DataType;ty

6、pedef struct Node DataType data; struct Node *next;ListNode,*LinkList;2、单链表初始化void InitList(LinkList *head)/*将单链表初始化为空。动态生成一个头结点，并将头结点的指针域置为空。*/if(*head=(LinkList)malloc(sizeof(ListNode)=NULL) /*为头结点分配一个存储空间*/exit(-1);(*head)-next=NULL;/*将单链表的头结点指针域置为空*/ListNode *Get(LinkList head,int i) /*查找单链表中第i个

7、结点。查找成功返回该结点的指针表示成功；否则返回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的元素，查找成功将对应元素的结点指针返回，否则返回NULL表示失败。*/Lis

8、tNode *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;while(p)if(p-da

9、ta=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*/自己完成int DeleteList(LinkList head,int i,DataType *e)/*删除单链表中的第i个位置的结点。删除成功返回1，失败返回0*/ListNode *pre,*p;int j; pre=head; j=0

10、; 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;实验三 双链表的操作1、目的理解双链表的基本操作了解双链表的建立和输出掌握

11、双链表的插入、删除等实现方法2、内容和要求基本要求编写一个程序，实现双链表的各种基本运算（假设双链表的元素类型为char），并在此基础上设计一个程序，完成如下功能：（1）初始化双链表h；（2）采用尾插法依次插入元素a，b，c，d，e；（3）输出双链表h；（4）输出双链表h长度；（5）判断双链表h是否为空；（6）输出双链表h的第3个元素；（7）输出元素a的位置；（8）在第4个位置上插入元素f；（9）输出双链表h；（10）删除h的第3个元素；（11）输出双链表h；（12）释放双链表h。#include stdio.h#include malloc.htypedef char ElemType;ty

12、pedef struct DNode /定义双链表结点类型ElemType data;struct DNode *prior;/指向前驱结点struct DNode *next;/指向后继结点 DLinkList; void InitList(DLinkList *&L) L=(DLinkList *)malloc(sizeof(DLinkList); L-prior=L-next=NULL; void DestroyList(DLinkList *&L) DLinkList *p=L, *q=p-next; while(q!=NULL) free(p); p=q; q=q-next; fre

13、e(p); int ListEmpty(DLinkList *L) return(L-next=NULL); int ListLength(DLinkList *L) DLinkList *p=L; int i=0;while(p-next!=NULL)i+;p=p-next; return(i); void DispList(DLinkList *L) DLinkList *p=L-next; while(p!=NULL) printf(%c,p-data); p=p-next; printf(n); int GetElem(DLinkList *L,int i,ElemType &e) i

14、nt j=0; DLinkList *p=L; while(jnext; if(p=NULL)return 0;else e=p-data;return 1; int LocateElem(DLinkList *L,ElemType e) int i=1; DLinkList *p=L-next; while(p!=NULL&p-data!=e) p=p-next; i+; if(p=NULL) return(0); else return(i); int ListInsert(DLinkList *&L,int i,ElemType e) int ListDelete(DLinkList *

15、&L,int i,ElemType &e) . void main()DLinkList *h;ElemType e;printf(双链表的基本运算如下:n);printf( (1)初始化双链表hn);InitList(h);printf( (2)依次采用尾插法插入a,b,c,d,e元素n);ListInsert(h,1,a);ListInsert(h,2,b);ListInsert(h,3,c);ListInsert(h,4,d);ListInsert(h,5,e);printf( (3)输出双链表h:);DispList(h);printf( (4)双链表h长度=%dn,ListLengt

16、h(h);printf( (5)双链表h为%sn,(ListEmpty(h)?空:非空);GetElem(h,3,e);printf( (6)双链表h的第3个元素=%cn,e);printf( (7)元素a的位置=%dn,LocateElem(h,a);printf( (8)在第4个元素位置上插入f元素n);ListInsert(h,4,f);printf( (9)输出双链表h:);DispList(h);printf( (10)删除h的第3个元素n);ListDelete(h,3,e);printf( (11)输出双链表h:);DispList(h);printf( (12)释放双链表hn)

17、;DestroyList(h); 实验4：栈的定义及基本操作一、实验目的：. 熟练掌握栈和队列的特点. 掌握栈的定义和基本操作，熟练掌握顺序栈的操作及应用. 掌握对列的定义和基本操作，熟练掌握链式队列的操作及应用 加深对栈结构的理解，逐步培养解决实际问题的编程能力二、实验内容:定义顺序栈，完成栈的基本操作：空栈、入栈、出栈、取栈顶元素；实现十进制数与八进制数的转换，十进制数与十六进制数的转换和任意进制之间的转换；定义链式队列，完成队列的基本操作：入队和出队；1问题描述：利用栈的顺序存储结构,设计一组输入数据（假定为一组整数），能够对顺序栈进行如下操作：. 初始化一个空栈，分配一段连续的存储空间

18、，且设定好栈顶和栈底；. 完成一个元素的入栈操作，修改栈顶指针；. 完成一个元素的出栈操作，修改栈顶指针；. 读取栈顶指针所指向的元素的值；. 将十进制数 N 和其它 d 进制数的转换是计算机实现计算的基本问题，其解决方案很多，其中最简单方法基于下列原理：即除 d取余法。例如：（1348）10=（2504）8N N div 8 N mod 81348 168 4168 21 0 21 2 52 0 2从中我们可以看出， 最先产生的余数 4 是转换结果的最低位， 这正好符合栈的特性即后进先出的特性。所以可以用顺序栈来模拟这个过程。以此来实现十进制数与八进制数的转换，十进制数与十六进制数的转换；.

19、 编写主程序，实现对各不同的算法调用。2实现要求：对顺序栈的各项操作一定要编写成为 C（C+）语言函数，组合成模块化的形式，每个算法的实现要从时间复杂度和空间复杂度上进行评价。.“初始化栈算法”操作结果：构造一个空栈 S；.“销毁栈算法”操作结果：销毁栈 S，S不再存在；.“置空栈算法” 操作结果：把 S 置为空栈；.“判是否空栈算法” 操作结果：若栈 S为空栈，则返回 TRUE，否则返回 FALSE；.“求栈的长度算法” 操作结果：返回 S的元素个数，即栈的长度；.“取栈顶元素算法” 操作结果：若栈不空，则用e 返回S 的栈顶元素，并返回 OK；否则返回 ERROR；.“入栈算法”操作结果：

20、插入元素 e为新的栈顶元素.“出栈算法”操作结果：若栈不空，则删除 S的栈顶元素，用 e 返回其值，并返回 OK；否则返回 ERROR.“实现十进制数与八进制数的转换算法”操作结果：输入任意一个非负的十进制数，输出对应的八进制数；.“实现十进制数与十六进制数的转换算法”操作结果：输入任意一个非负的十进制数，输出对应的十六进制数；三、实验指导（一）顺序栈的实验指导1首先将顺序栈存储结构定义放在一个头文件：如取名为 SqStackDef.h。2将顺序栈的基本操作算法也集中放在一个文件之中，如取名为 SqStackAlgo.h。如：InitStack、DestroyStack、 ClearStack

21、、 StackEmpty、 StackLength、 GetTop、 Push、 Pop、 conversion10_8、 conversion10_16等。3将函数的测试和主函数组合成一个文件，如取名为 SqStackUse.cpp。四、参考程序一）编写一个程序，实现顺序栈（假设栈中元素类型为char）的各种基本运算，并在此基础上设计一个程序完成如下功能：（1）初始化栈s；（2）判断栈s是否非空；（3）依次进栈元素a，b，c，d，e；（4）判断栈s是否非空；（5）输出栈长度；（6）输出从栈顶到栈底元素；（7）输出出栈序列；（8）判断栈s是否非空；（9）释放栈。程序代码如下：#include

22、#include #define MaxSize 100typedef char ElemType;typedef struct ElemType dataMaxSize;int top;/栈顶指针 SqStack;void InitStack(SqStack *&s)s=(SqStack *)malloc(sizeof(SqStack);s-top=-1;/栈顶指针置为-1void DestroyStack(SqStack *&s)free(s);int StackLength(SqStack *s)return(s-top+1);bool StackEmpty(SqStack *s)ret

23、urn(s-top=-1);bool Push(SqStack *&s,ElemType e)if (s-top=MaxSize-1)/栈满的情况，即栈上溢出return false;s-top+;/栈顶指针增1s-datas-top=e;/元素e放在栈顶指针处return true;bool Pop(SqStack *&s,ElemType &e)if (s-top=-1)/栈为空的情况，即栈下溢出return false;e=s-datas-top;/取栈顶指针元素的元素s-top-;/栈顶指针减1return true; bool GetTop(SqStack *s,ElemType &

24、e)if (s-top=-1)/栈为空的情况，即栈下溢出return false;e=s-datas-top;/取栈顶指针元素的元素return true;void DispStack(SqStack *s) int i; for (i=s-top;i=0;i-) printf(%c ,s-datai); printf(n); void main()ElemType e;SqStack *s;printf(栈s的基本运算如下:n);printf( (1)初始化栈sn);InitStack(s);printf( (2)栈为%sn,(StackEmpty(s)?空:非空);printf( (3)依

25、次进栈元素a,b,c,d,en);Push(s,a);Push(s,b);Push(s,c);Push(s,d);Push(s,e);printf( (4)栈为%sn,(StackEmpty(s)?空:非空);printf( (5)输出栈长度:%dn,StackLength(s);printf( (6)输出从栈顶到栈底元素:); printf(n); printf( (7)出栈序列:); while (!StackEmpty(s)Pop(s,e);printf(%c ,e);printf(n);printf( (8)栈为%sn,(StackEmpty(s)?空:非空);printf( (9)释

26、放栈n);DestroyStack(s);二）编写一个程序，实现链栈（假设栈中元素类型为char）的各种基本运算，并在此基础上设计一个程序，完成如下功能：（1）初始化链栈s；（2）判断链栈s是否非空；（3）依次进链栈元素a，b，c，d，e；（4）判断链栈s是否非空；（5）输出链栈长度；（6）输出从链栈顶到栈底元素；（7）输出出链栈序列；（8）判断链栈s是否非空；（9）释放链栈。程序代码如下：#include #include typedef char ElemType;typedef struct linknodeElemType data;/数据域struct linknode *next;

27、/指针域 LiStack;void InitStack(LiStack *&s)/初始化栈ss=(LiStack *)malloc(sizeof(LiStack);s-next=NULL;void DestroyStack(LiStack *&s)/销毁栈LiStack *p=s,*q=s-next;while (q!=NULL)free(p);p=q;q=p-next;free(p);/此时p指向尾节点,释放其空间bool StackEmpty(LiStack *s)/判断栈是否为空return(s-next=NULL);void Push(LiStack *&s,ElemType e)/进

28、栈LiStack *p;p=(LiStack *)malloc(sizeof(LiStack);p-data=e;/新建元素e对应的节点*pp-next=s-next;/插入*p节点作为开始节点s-next=p;bool Pop(LiStack *&s,ElemType &e)/出栈LiStack *p;if (s-next=NULL)/栈空的情况return false; p=s-next;e=p-data; s-next=p-next; free(p);return true;bool GetTop(LiStack *s,ElemType &e)/取栈顶元素if (s-next=NULL)

29、/栈空的情况return false;e=s-next-data;return true;int StackLength(LiStack *&s) int i=0; LiStack *p=s; while(p-next!=NULL) i+; p=p-next; return i;void DispStack(LiStack *s)LiStack *p=s-next;while(p!=NULL)printf(%c,p-data);p=p-next;printf(n);void main()ElemType e;LiStack *s;printf(栈s的基本运算如下:n);printf( (1)初

30、始化栈sn);InitStack(s);printf( (2)栈为%sn,(StackEmpty(s)?空:非空);printf( (3)依次进栈元素a,b,c,d,en);Push(s,a);Push(s,b);Push(s,c);Push(s,d);Push(s,e);printf( (4)栈为%sn,(StackEmpty(s)?空:非空); printf( (5)栈的长度为：%dn,StackLength(s);printf( (6)从链栈顶到栈底元素:); DispStack(s); printf( (7)出栈序列:);while (!StackEmpty(s)Pop(s,e);pr

31、intf(%c ,e);printf(n);printf( (8)栈为%sn,(StackEmpty(s)?空:非空);printf( (9)释放栈n);DestroyStack(s);三）利用堆栈实现进制转换1文件 SqStackDef.h中实现了栈的顺序存储表示#define STACK_INIT_SIZE 10 /* 存储空间初始分配量 */#define STACKINCREMENT 2 /* 存储空间分配增量 */#define OK 1typedef int Status ;typedef struct SqStackSElemType *base； /* 在栈构造之前和销毁之后，

32、base 的值为NULL */SElemType *top； /* 栈顶指针 */int stacksize； /* 当前已分配的存储空间，以元素为单位 */SqStack； /* 顺序栈 */2文件 SqStackAlgo.h中实现顺序栈的基本操作（存储结构由 SqStackDef.h定义）#include “SqStackDef.h” #includeStatus InitStack(SqStack &S) /* 构造一个空栈 S */S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)；if(!S.base)exit(O

33、VERFLOW)； /* 存储分配失败 */S.top=S.base；S.stacksize=STACK_INIT_SIZE；return OK；Status DestroyStack(SqStack &S) /* 销毁栈 S，S不再存在 */free(S.base)；S.base=NULL；S.top=NULL；S.stacksize=0；return OKStatus ClearStack(SqStack &S) /* 把 S 置为空栈 */S.top=S.base；return OK；Status StackEmpty(SqStack S) /* 若栈 S为空栈，则返回 TRUE，否则返

34、回 FALSE */if(S.top=S.base)return TRUE；elsereturn FALSE；int StackLength(SqStack S) /* 返回 S的元素个数，即栈的长度 */return S.top-S.base；Status GetTop(SqStack S,SElemType &e) /* 若栈不空，则用 e返回 S的栈顶元素，并返回OK；否则返回ERROR */if(S.topS.base)e=*(S.top-1)；return OK；elsereturn ERROR；Status Push(SqStack &S,SElemType e) /* 插入元素

35、e为新的栈顶元素 */if(S.top-S.base=S.stacksize) /* 栈满，追加存储空间 */S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType)；if(!S.base)exit(OVERFLOW)； /* 存储分配失败 */S.top=S.base+S.stacksize；S.stacksize+=STACKINCREMENT；*(S.top)+=e；return OK；Status Pop(SqStack &S,SElemType &e) /* 若栈不空，则删除 S的栈顶元素，用 e返回其值，并返回 OK；否则返回 ERROR */if(S.top=S.base)return ERROR；e=*-S.top；return OK；Status StackTraverse(SqStack S,Status(*visit)(SElemTyp