数据结构实验源代码

1、数据结构实验源代码第二章 线性表标题：约瑟夫环描述：约瑟夫环编号为1，2，3，n的n个人按顺时针方向围坐一圈。任选一个正整数作为报数上限m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。设计程序输出出列顺序。输入：人数n 报数上限m人员记录1 (格式为：姓名 学号 性别 年龄 班级 健康状况)人员记录2人员记录n输出：第1次报数出列的人员记录第2次报数出列的人员记录第n次报数出列的人员记录输入样例：5 3安弥邵 10000001 女 28 计43 一般宰觅 10000002 男 23

2、计79 健康顾健 10000003 男 27 计29 一般宓顽芳 10000004 女 20 计17 健康能纸垄 10000005 男 18 计11 健康输出样例：顾健 10000003 男 27 计29 一般  安弥邵 10000001 女 28 计43 一般  能纸垄 10000005 男 18 计11 健康  宰觅 10000002 男 23 计79 健康

3、60; 宓顽芳 10000004 女 20 计17 健康提示：循环表#include<string.h> #include<ctype.h> #include<malloc.h> / malloc()等 #include<limits.h> / INT_MAX等 #include<stdio.h> / EOF(=Z或F6),NULL #include<stdlib.h> / atoi() #include<io.h> / eof() #include<ma

4、th.h> / floor(),ceil(),abs() #include<process.h> / exit() / 函数结果状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 / #define OVERFLOW -2 因为在中已定义OVERFLOW的值为3,故去掉此行 typedef int Status; / Status是函数的类型,其值是函数结果状态代码，如OK等 typedef int Boolean; / Boolean是布尔类型,其值是T

5、RUE或FALSE struct stud char name12; char num12; char sex4; int age; char clas10; char health16;typedef stud ElemType;typedef struct LNode ElemType date; struct LNode *next;LNode,*LinkList;void CreateList2(LinkList &L,int n) / 正位序(插在表尾)输入n个元素的值，建立带表头结构的单链线性表 int i; LinkList p,q; L=(LinkList)malloc

6、(sizeof(LNode); / 生成头结点 q=L;um,L->date.sex,&L->date.age,L->date.clas,L->date.health); for(i=1;i < n;i+) p=(LinkList)malloc(sizeof(LNode); scanf("%s%s%s%d%s%s",p->,p->date.num,p->date.sex,&p->date.age,p->date.clas,p->date.health); q->next

7、=p; q=q->next; p->next=L; void run(LinkList L,int m) int i; LinkList p,q; p = L; while (p) for(i = 1 ;i < m;i+) q = p; p = p->next; printf("%s %s %s %d %s %sn",p->,p->date.num,p->date.sex,p->date.age,p->date.clas,p->date.health); q->next=p->next

8、; free(p); p = q->next; if(p=p->next) break; printf("%s %s %s %d %s %s",p->,p->date.num,p->date.sex,p->date.age,p->date.clas,p->date.health); printf("n"); free(p);/要将P释放掉，应为在前面L已经被释放掉 int main() int n,m; LinkList La;标题：学生信息管理描述：用链式存储结构实现对一个班级学生信息管

9、理。设计程序求出每个人的平均成绩并按平均成绩由高到底排序后输出学生记录。输入：人数n人员记录1 (格式为： 学号 姓名 成绩1  成绩2  成绩3)人员记录2输出：人员记录x                                  

10、;                      1人员记录y                           

11、;                             2  人员记录z                  

12、0;                                     n输入样例：31 孙俪莉  76  78  89  2 章子怡  72  56  67

13、60; 3 刘德华  56  84  90输出样例：1 孙俪莉  76 78  89  81.00  13 刘德华 56  84  90  76.67  22 章子怡 72  56  67  65.00  3 #include<stdio.h>#include<stdlib.h>#define

14、MaxSize 1000typedef struct Student long num; char name10; float score_1; float score_2; float score_3; float ave_score; long rank; StudentType;typedef StudentType DataType;typedef struct Node DataType data; struct Node *next; SLNode;void ListInitiate(SLNode * * L) if(*L=(SLNode *)malloc(sizeof(SLNod

15、e)=NULL)exit(1); (*L)->next=NULL;int ListInsert(SLNode *L,int i,DataType x) SLNode *p,*q; int j; p=L; j=0; while(p->next!=NULL&&j<i-1) p=p->next; j+; if(j!=i-1) printf("error"); return 0; if(q=(SLNode *)malloc(sizeof(SLNode)=NULL)exit(1); q->data=x; q->next=p->

16、next; p->next=q; return 0;void Ranking(SLNode *L) SLNode *p,*q,*s; long i=0; p=L; while(p->next!=NULL) p=p->next; p->data.ave_score=(p->data.score_1+p->data.score_2+p->data.score_3)/3; i+; p=L; while(i-) p=L; s=p; p=p->next; q=p->next; while(p->next!=NULL) if(p->data

17、.ave_score<q->data.ave_score) if(q->next!=NULL) p->next=q->next; else p->next=NULL; q->next=p; s->next=q; q=p->next; s=s->next; else/后移 s=p; p=p->next; q=p->next; p=L; i=1; while(p->next!=NULL) p=p->next; p->data.rank=i+; void Destroy(SLNode * *L) SLNode

18、*p,*p1; p=*L; while(p!=NULL) p1=p; p=p->next; free(p1); *L=NULL;int main(void) SLNode *L,*p; StudentType xMaxSize; int n; int i; ListInitiate(&L); p=L; scanf("%d",&n);/班级人数 for(i=1; i<=n; i+) scanf("%ld",&xi.num); scanf("%s", ); scanf("%f&q

19、uot;, &xi.score_1); scanf("%f", &xi.score_2); scanf("%f", &xi.score_3); ListInsert(L,i,xi); Ranking(L); while(p->next!=NULL) p=p->next; printf("%ld " ,p->data.num); printf("%s " ,p->); printf("%.2f " ,p->data.score

20、_1); printf("%.2f " ,p->data.score_2); printf("%.2f " ,p->data.score_3); printf("%.2f " ,p->data.ave_score); printf("%ldn" ,p->data.rank); Destroy(&L); return 0; 标题：链表上的基本操作实现描述：在单链表存储结构上实现基本操作：初始化、创建、插入、删除、查找、遍历、逆置、合并运算。输入：线性表长度na1 a2 a3 .an（数

21、值有序，为降序）要插入到线性表中的数字x和插入的位置i要删除的数字的位置i要查找的数字x线性表长度mb1 b2.bm(数值有序，为升序)输出：创建的线性表a1 a2.an插入一个数字后的线性表a1 a2.an+1删除一个数字后的线性表a1 a2.an查找一个输入的数字后如果找到，输出该数字的位置i,如果没有找到，输出“没有找到x”的信息。逆置a1 a2.an后的线性表an an-1.a1合并两个线性表后的线性表输入样例：请输入线性表La的长度：6请输入线性表La中的元素：15 13 10 9 8 5请输入要插入到线性表La中的数字x和要插入的位置：7 6线性表La=15 1

22、3 10 9 8 7 5(输出)请输入要删除的数字的位置：4线性表La=15 13 10 8 7 5(输出)请输入要查找的数字：10找到，10在第3个位置逆置线性表La=5 7 8 10 13 15请输入线性表Lb的长度：4请输入线性表Lb中的元素：1 3 6 9合并La和Lb后的线性表为：1 3 5 6 7 8 9 10 13 15 #include<stdio.h>#include<stdlib.h>#define OK 1#define ERROR 0#define OVERFLOW -2typedef int ElemTy

23、pe;typedef int Status;#define LIST_INIT_SIZE 4 / 线性表存储空间的初始分配量#define LISTINCREMENT 2 / 线性表存储空间的分配增量struct SqList ElemType *elem; / 存储空间基址 int length; / 当前长度 int listsize; / 当前分配的存储容量(以sizeof(ElemType)为单位)Sqlist;Status InitList_Sq(SqList &L) / 操作结果：构造一个空的顺序线性表 L.elem=(ElemType*)malloc(LIST_INIT_

24、SIZE*sizeof(ElemType); if(!L.elem) exit(OVERFLOW); / 存储分配失败 L.length=0; / 空表长度为0 L.listsize=LIST_INIT_SIZE; / 初始存储容量 return OK;Status ListInsert_Sq(SqList &L,int i,ElemType e) / 初始条件：顺序线性表L已存在，1iListLength(L)+1 / 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 ElemType *newbase,*q,*p; if(i<1|i>L.length+1)

25、 / i值不合法 return ERROR; if(L.length>=L.listsize) / 当前存储空间已满,增加分配 if(!(newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType) exit(OVERFLOW); / 存储分配失败 L.elem=newbase; / 新基址 L.listsize+=LISTINCREMENT; / 增加存储容量 q=L.elem+i-1; / q为插入位置 for(p=L.elem+L.length-1; p>=q; -p) / 插入位

26、置及之后的元素右移 *(p+1)=*p; *q=e; / 插入e ListInsert(Lb,) +L.length; / 表长增1 return OK;Status Listprint_Sq(SqList &L) int i; for(i=0; i<=L.length-1; i+) printf("%d ",L.elemi); printf("n"); return OK;Status ListDelete_Sq(SqList &L,int i,ElemType &e) ElemType *p,*q; if(i<1)

27、|(i>L.length) return ERROR; p=L.elem+i-1; e=*p; q=L.elem+L.length-1; for(p=L.elem+i;p<=q;+p) *(p-1)=*p; -L.length; return OK;int LocateElem_Sq(SqList L,ElemType e) int i=1; ElemType *p,*q; q=L.elem+L.length-1; for(p=L.elem;p<=q;p+) if(*p=e) return i; break; i+; return ERROR;Status ListNiZhi

28、_Sq(SqList &L) ElemType e; ElemType *p,*q; q=&L.elemL.length-1; for( p=L.elem;p<q;p+) e=*p; *p=*q; *q=e; q-; return OK; void MergeList_Sq(SqList La,SqList Lb,SqList &Lc) ElemType *pa,*pb,*pc,*pa_last,*pb_last; pa=La.elem;pb=Lb.elem; Lc.listsize=Lc.length=La.length+Lb.length; pc=Lc.ele

29、m=(ElemType*)malloc(Lc.listsize*sizeof(ElemType); if(!Lc.elem) exit(OVERFLOW); pa_last=La.elem+La.length-1;ength-1; while(pa<=pa_last&&pb<=pb_last) if(*pa<=*pb) *pc+=*pa+; else *pc+=*pb+; while(pa<=pa_last) *pc+=*pa+; while(pb<=pb_last) *pc+=*pb+;int main() SqList La;/建立线性表La

30、InitList_Sq(La); int j,n,c,i,x; scanf("%d",&n); for(j=0; j<n; j+) scanf("%d",&c); ListInsert_Sq(La,j+1,c); printf("创建好的线性表La="); Listprint_Sq(La); scanf("%d %d",&x,&i); ListInsert_Sq(La,i,x); printf("插入一个元素后的线性表La="); Listprint_Sq(

31、La); ElemType e; int m; scanf("%d",&m); ListDelete_Sq(La,m,e); printf("删除一个元素后的线性表La="); Listprint_Sq(La); ElemType a; int t; scanf("%d",&a); t=LocateElem_Sq(La,a); if(t) printf("找到，%d在第%d个位置n",a,t); else printf("没找到n"); ListNiZhi_Sq(La); pri

32、ntf("逆置后的线性表La=");/逆置线性表La Listprint_Sq(La); SqList Lb,Lc; int l,C; InitList_Sq(Lb);/建立线性表Lb scanf("%d",&l); for(j=0;j<l;j+) scanf("%d",&C); ListInsert_Sq(Lb,j+1,C); InitList_Sq(Lc); MergeList_Sq(La,Lb,Lc); printf("合并La和Lb后的线性表=");/合并线性表La和Lb Listpr

33、int_Sq(Lc); return 0;标题：顺序表上的基本操作实现描述：在顺序存储结构实现基本操作：初始化、创建、插入、删除、查找、遍历、逆置、合并运算。输入：请输入线性表La的长度:na1 a2 a3 .an（数值有序，为降序）请输入要插入到线性表La中的数字x和插入的位置i:x i请输入要删除数字的位置:i请输入要查找的数字:x请输入线性表长度:mb1 b2.bm(数值有序，为升序)输出：创建好的线性表La=a1 a2.an插入一个数字后的线性表a1 a2.an+1删除一个数字后的线性表a1 a2.an查找一个输入的数字后如果找到，输出该数字的位置i,如果没有找到，输出"没有

34、找到x"的信息。逆置a1 a2.an后的线性表an an-1.a1合并两个线性表后的线性表输入样例：请输入线性表La的长度：5请输入线性表La中的元素：14 11 10 9 5请输入要插入到线性表La中的数字x和插入的位置i：8 4线性表La=14 11 10 8 9 5请输入要删除的数字的位置：4线性表La=14 11 10 9 5请输入要查找的数字：10找到，10在第3个位置逆置后的线性表La=5 9 10 11 14请输入线性表Lb的长度：4请输入线性表Lb中的元素：1 3 6 9合并La和Lb后的线性表为：1 3 5 6 9

35、9 10 11 14 #include<stdio.h>#include<stdlib.h>#define OK 1#define ERROR 0#define OVERFLOW -2typedef int ElemType;typedef int Status;#define LIST_INIT_SIZE 4 / 线性表存储空间的初始分配量#define LISTINCREMENT 2 / 线性表存储空间的分配增量struct SqList ElemType *elem; / 存储空间基址 int length; / 当前长度 int listsize; /

36、 当前分配的存储容量(以sizeof(ElemType)为单位)Sqlist;Status InitList_Sq(SqList &L) / 操作结果：构造一个空的顺序线性表 L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType); if(!L.elem) exit(OVERFLOW); / 存储分配失败 L.length=0; / 空表长度为0 L.listsize=LIST_INIT_SIZE; / 初始存储容量 return OK;Status ListInsert_Sq(SqList &L,int i,ElemT

37、ype e) / 初始条件：顺序线性表L已存在，1iListLength(L)+1 / 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 ElemType *newbase,*q,*p; if(i<1|i>L.length+1) / i值不合法 return ERROR; if(L.length>=L.listsize) / 当前存储空间已满,增加分配 if(!(newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType) exit(OVERFLOW); / 存储分配

38、失败 L.elem=newbase; / 新基址 L.listsize+=LISTINCREMENT; / 增加存储容量 q=L.elem+i-1; / q为插入位置 for(p=L.elem+L.length-1; p>=q; -p) / 插入位置及之后的元素右移 *(p+1)=*p; *q=e; / 插入e ListInsert(Lb,) +L.length; / 表长增1 return OK;Status Listprint_Sq(SqList &L) int i; for(i=0; i<=L.length-1; i+) printf("%d ",

39、L.elemi); printf("n"); return OK;Status ListDelete_Sq(SqList &L,int i,ElemType &e) ElemType *p,*q; if(i<1)|(i>L.length) return ERROR; p=L.elem+i-1; e=*p; q=L.elem+L.length-1; for(p=L.elem+i;p<=q;+p) *(p-1)=*p; -L.length; return OK;int LocateElem_Sq(SqList L,ElemType e) int

40、 i=1; ElemType *p,*q; q=L.elem+L.length-1; for(p=L.elem;p<=q;p+) if(*p=e) return i; break; i+; return ERROR;Status ListNiZhi_Sq(SqList &L) ElemType e; ElemType *p,*q; q=&L.elemL.length-1; for( p=L.elem;p<q;p+) e=*p; *p=*q; *q=e; q-; return OK; void MergeList_Sq(SqList La,SqList Lb,SqLi

41、st &Lc) ElemType *pa,*pb,*pc,*pa_last,*pb_last; pa=La.elem;pb=Lb.elem; Lc.listsize=Lc.length=La.length+Lb.length; pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType); if(!Lc.elem) exit(OVERFLOW); pa_last=La.elem+La.length-1; pb_last=Lb.elem+Lb.length-1; while(pa<=pa_last&&pb<

42、=pb_last) if(*pa<=*pb) *pc+=*pa+; else *pc+=*pb+; while(pa<=pa_last) *pc+=*pa+; while(pb<=pb_last) *pc+=*pb+;int main() SqList La;/建立线性表La InitList_Sq(La); int j,n,c,i,x; scanf("%d",&n); for(j=0; j<n; j+) scanf("%d",&c); ListInsert_Sq(La,j+1,c); printf("创

43、建好的线性表La="); Listprint_Sq(La); scanf("%d %d",&x,&i); ListInsert_Sq(La,i,x); printf("插入一个元素后的线性表La="); Listprint_Sq(La); ElemType e; int m; scanf("%d",&m); ListDelete_Sq(La,m,e); printf("删除一个元素后的线性表La="); Listprint_Sq(La); ElemType a; int t; sc

44、anf("%d",&a); t=LocateElem_Sq(La,a); if(t) printf("找到，%d在第%d个位置n",a,t); else printf("没找到n"); ListNiZhi_Sq(La); printf("逆置后的线性表La=");/逆置线性表La Listprint_Sq(La); SqList Lb,Lc; int l,C; InitList_Sq(Lb);/建立线性表Lb scanf("%d",&l); for(j=0;j<l;j+)

45、scanf("%d",&C); ListInsert_Sq(Lb,j+1,C); InitList_Sq(Lc); MergeList_Sq(La,Lb,Lc); printf("合并La和Lb后的线性表=");/合并线性表La和Lb Listprint_Sq(Lc); return 0; scanf("%d%d",&n,&m); CreateList2(La,n); run(La,m); return 0;第六章 树和二叉树标题：从先序中序重建二叉树输出层序后序描述：由树的先序和中序遍历生成树的层序遍历后序遍

46、历给定一个树的先序和中序的遍历结果，构建一棵树，并输出这个棵树的层序遍历和后序遍历结果注：这棵树的结点是由整数描述输入：树结点总数m先序输出序列中序输出序列输出：层序输出序列后续输出序列输入样例：101 2 5 10 3 6 13 7 14 152 10 5 1 6 13 3 14 7 15输出样例：1 2 3 5 6 7 10 13 14 1510 5 2 13 6 14 15 7 3 1提示：先序遍历的第一个输出是根结点#include <stdio.h>#include <stdlib.h>#include <string.h>struct BiTre

47、e int number; BiTree *lchild; BiTree *rchild;void InitBiTree(BiTree &root) root.lchild = NULL; root.rchild = NULL; root.number = 0;int m = 0;void CreatBiTree(BiTree* &root, int *a, int *b, int start, int end) int i, sign = 0; for(i = start; i < end; i+) if(bi = am) sign = 1; break; if(!si

48、gn) return; root = (BiTree *)malloc(sizeof(BiTree); InitBiTree(*root); root->number = am;m+; CreatBiTree(root->lchild, a, b, start, i); CreatBiTree(root->rchild, a, b, i+1, end);typedef void (*Func)(BiTree *root);void PostTraverse(BiTree *root, Func visit) if(root) PostTraverse(root->lch

49、ild, visit); PostTraverse(root->rchild, visit); visit(root); void PrintTree(BiTree *root) printf("%d ", root->number);struct Queue BiTree *Base; int Front; int Rear;void InitQueue(Queue &queue) queue.Base = (BiTree *)malloc(sizeof(BiTree) * 2000); queue.Front = queue.Rear = 0;boo

50、l Enqueue(Queue &queue, BiTree *root) if(queue.Rear + 1) % 2000 = queue.Front) return false; else queue.Basequeue.Rear = root; queue.Rear = (queue.Rear+1) % 2000; return true; bool DeQueue(Queue &queue, BiTree* &root) if(queue.Front = queue.Rear) return false; root = queue.Basequeue.Fron

51、t; queue.Front = (queue.Front+1) % 2000; return true;void LevelOrderTraverse(BiTree *root, Func visit) BiTree *node = NULL; Queue queue; InitQueue(queue); Enqueue(queue, root); while(queue.Front != queue.Rear) DeQueue(queue, node); visit(node); if(node->lchild != NULL) Enqueue(queue, node->lch

52、ild); if(node->rchild != NULL) Enqueue(queue, node->rchild); int main() int i, n, *a, *b; scanf("%d", &n); a = (int *)malloc(sizeof(int) * n); b = (int *)malloc(sizeof(int) * n); for(i = 0; i < n; i+) scanf("%d", &ai); for(i = 0; i < n; i+) scanf("%d",