数据结构实验源代码

《数据结构实验源代码》由会员分享，可在线阅读，更多相关《数据结构实验源代码（62页珍藏版）》请在装配图网上搜索。

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健康 宓顽芳10000004女20计17健康提示：循环表#include #include #include / malloc()等 #include / INT_MAX等 #include / EOF(=Z或F6),NULL #include / atoi() #include /

3、eof() #include / floor(),ceil(),abs() #include / 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是布尔类型,其值是TRUE或FALSE s

4、truct 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(sizeof(LNode);

5、 / 生成头结点 q=L;um,L-date.sex,&L-date.age,L-date.clas,L-date.health); for(i=1;i date.name,p-date.num,p-date.sex,&p-date.age,p-date.clas,p-date.health); q-next=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 next; printf(%s %s %s %d %s %sn,p-date.name

6、,p-date.num,p-date.sex,p-date.age,p-date.clas,p-date.health); q-next=p-next; free(p); p = q-next; if(p=p-next) break; printf(%s %s %s %d %s %s,p-date.name,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;标题：学生信息管理描述：

7、用链式存储结构实现对一个班级学生信息管理。设计程序求出每个人的平均成绩并按平均成绩由高到底排序后输出学生记录。输入：人数n人员记录1 (格式为： 学号 姓名 成绩1 成绩2 成绩3)人员记录2输出：人员记录x1人员记录y2 人员记录z n输入样例：31 孙俪莉 76 78 89 2 章子怡 72 56 67 3 刘德华 56 84 90输出样例：1 孙俪莉76788981.0013 刘德华 56849076.6722 章子怡 72 566765.003#include#include#define MaxSize 1000typedef struct Student long num; cha

8、r 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(SLNode)=NULL)exit(1); (*L)-next=NULL;int ListInsert(S

9、LNode *L,int i,DataType x) SLNode *p,*q; int j; p=L; j=0; while(p-next!=NULL&jnext; j+; if(j!=i-1) printf(error); return 0; if(q=(SLNode *)malloc(sizeof(SLNode)=NULL)exit(1); q-data=x; q-next=p-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-n

10、ext; 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.ave_scoredata.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

11、=L; i=1; while(p-next!=NULL) p=p-next; p-data.rank=i+; void Destroy(SLNode * *L) SLNode *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; inext!=NULL) p=p-next; printf(%ld

12、 ,p-data.num); printf(%s ,p-data.name); printf(%.2f ,p-data.score_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（数值有序，为降

13、序）要插入到线性表中的数字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 1098 5请输入要插入到线性表La中的数字x和要插入的位置：7 6线性表La=15 13 1098 7 5(输出)请输入要

14、删除的数字的位置：4线性表La=15 13 108 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#include#define OK 1#define ERROR 0#define OVERFLOW -2typedef int ElemType;typedef int Status;#define LIST_INIT_SIZE 4 / 线性表存储空间的初始分配量#define LIS

15、TINCREMENT 2 / 线性表存储空间的分配增量struct SqList ElemType *elem; / 存储空间基址 int length; / 当前长度 int listsize; / 当前分配的存储容量(以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; / 空表长

16、度为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(iL.length+1) / i值不合法 return ERROR; if(L.length=L.listsize) / 当前存储空间已满,增加分配 if(!(newbase=(ElemType *)real

17、loc(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) / 插入位置及之后的元素右移 *(p+1)=*p; *q=e; / 插入e ListInsert(Lb,) +L.length; / 表长增1 return OK;Status Listprint_Sq(SqL

18、ist &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(iL.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

19、,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_Sq(SqList &L) ElemType e; ElemType *p,*q; q=&L.elemL.length-1; for( p=L.elem;pq;p+) e=*p; *p=*q; *q=e; q-; return OK; void MergeList_Sq(SqList La,SqList Lb,SqLi

20、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;ength-1; while(pa=pa_last&pb=pb_last) if(*pa=*pb) *pc+=*pa+; else *pc+

21、=*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; jn; 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=);

22、 Listprint_Sq(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); printf(逆置后的线性表La=);/逆置线性表La Listprint_Sq(La); SqList Lb,L

23、c; int l,C; InitList_Sq(Lb);/建立线性表Lb scanf(%d,&l); for(j=0;jl;j+) 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;标题：顺序表上的基本操作实现描述：在顺序存储结构实现基本操作：初始化、创建、插入、删除、查找、遍历、逆置、合并运算。输入：请输入线性表La的长度:na1 a2 a3 .an（数值有序，为

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

25、=14 11 1089 5请输入要删除的数字的位置：4线性表La=14 11 109 5请输入要查找的数字：10找到，10在第3个位置逆置后的线性表La=59 10 11 14请输入线性表Lb的长度：4请输入线性表Lb中的元素：1 3 6 9合并La和Lb后的线性表为：1 3 5 69 9 10 11 14#include#include#define OK 1#define ERROR 0#define OVERFLOW -2typedef int ElemType;typedef int Status;#define LIST_INIT_SIZE 4 / 线性表存储空间的初始分配量#def

26、ine LISTINCREMENT 2 / 线性表存储空间的分配增量struct SqList ElemType *elem; / 存储空间基址 int length; / 当前长度 int listsize; / 当前分配的存储容量(以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

27、; / 空表长度为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(iL.length+1) / i值不合法 return ERROR; if(L.length=L.listsize) / 当前存储空间已满,增加分配 if(!(newbase=(ElemType

28、 *)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) / 插入位置及之后的元素右移 *(p+1)=*p; *q=e; / 插入e ListInsert(Lb,) +L.length; / 表长增1 return OK;Status Listprint

29、_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(iL.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(S

30、qList 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_Sq(SqList &L) ElemType e; ElemType *p,*q; q=&L.elemL.length-1; for( p=L.elem;pq;p+) e=*p; *p=*q; *q=e; q-; return OK; void MergeList_Sq(SqList La,SqList

31、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.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=pb_last) if(*

32、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; jn; j+) scanf(%d,&c); ListInsert_Sq(La,j+1,c); printf(创建好的线性表La=); Listprint_Sq(La); scanf(%d %d,&x,&i); ListInsert_Sq(La,i

33、,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; scanf(%d,&a); t=LocateElem_Sq(La,a); if(t) printf(找到，%d在第%d个位置n,a,t); else printf(没找到n); ListNiZhi_Sq(La); printf(逆置后的线性表La=);/逆置线性表La L

34、istprint_Sq(La); SqList Lb,Lc; int l,C; InitList_Sq(Lb);/建立线性表Lb scanf(%d,&l); for(j=0;jl;j+) 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;第六章 树和

35、二叉树标题：从先序中序重建二叉树输出层序后序描述：由树的先序和中序遍历生成树的层序遍历后序遍历给定一个树的先序和中序的遍历结果，构建一棵树，并输出这个棵树的层序遍历和后序遍历结果注：这棵树的结点是由整数描述输入：树结点总数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 #include #include struct BiTree

36、 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 number = am;m+; CreatBiTree(root-lchild, a, b, start, i);

37、CreatBiTree(root-rchild, a, b, i+1, end);typedef void (*Func)(BiTree *root);void PostTraverse(BiTree *root, Func visit) if(root) PostTraverse(root-lchild, visit); PostTraverse(root-rchild, visit); visit(root); void PrintTree(BiTree *root) printf(%d , root-number);struct Queue BiTree *Base; int Front

38、; int Rear;void InitQueue(Queue &queue) queue.Base = (BiTree *)malloc(sizeof(BiTree) * 2000); queue.Front = queue.Rear = 0;bool 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

39、; bool DeQueue(Queue &queue, BiTree* &root) if(queue.Front = queue.Rear) return false; root = queue.Basequeue.Front; 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(que

40、ue.Front != queue.Rear) DeQueue(queue, node); visit(node); if(node-lchild != NULL) Enqueue(queue, node-lchild); 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+)

41、 scanf(%d, &ai); for(i = 0; i n; i+) scanf(%d, &bi); BiTree *root; CreatBiTree(root, a, b, 0, n); LevelOrderTraverse(root, PrintTree);printf(n); PostTraverse(root, PrintTree); return 0;标题：Huffman树描述：Huffman树对输入的英文大写字母进行统计概率 然后构建哈夫曼树,输出是按照概率降序排序输出Huffman编码。输入：大写字母个数 n第一个字母 第二个字母 第三个字母 . 第n个字母输出：字母1 出

42、现次数 Huffman编码字母2 出现次数 Huffman编码字母3 出现次数 Huffman编码字母n 出现次数 Huffman编码输入样例：10I I U U U I U N U U输出样例：U 6 1I 3 01N 1 00#include #include #include #define MAX 27#define MAX_INT 99999/哈夫曼树和哈夫曼编码的存储表示typedef struct int weight; int parent,lchild,rchild; HTNode,*HuffmanTree; / 动态分配数组存储哈夫曼树typedef char *Huffm

43、anCode; /动态分配数组存储赫夫曼编码表typedef struct Charnode char c; int weight; CharNode,*CharNodePtr;CharNode *b;int min(HuffmanTree t,int i) int j,flag; int k=MAX_INT; / 取k为不小于可能的值 for(j=1; j=i; j+) if(tj.weightk&tj.parent=0) k=tj.weight,flag=j; tflag.parent=1; return flag;void select(HuffmanTree t,int i,int &

44、s1,int &s2) s2=min(t,i); s1=min(t,i);int Chat_get() char c; int j=0; int m; int i; scanf(%d,&m); getchar(); b=(CharNodePtr)malloc(sizeof(CharNode)*MAX); int aMAX; for(i=0; iMAX; i+) ai=0; for(i=0; im; i+) scanf(%c,&c); getchar(); ac-A+; for(i=0; i26; i+) if(ai!=0) bj.c=char(i+A); bj.weight=ai; j+; r

45、eturn j;/得到不同字符的个数和数组void PrintHuffmanTree(HuffmanTree &HT,HuffmanCode &HC, int n) int i, c, cdlen; char *cd; HC=(HuffmanCode)malloc(n+1)*sizeof(char*); / 分配n个字符编码的头指针向量(0不用) cd=(char*)malloc(n*sizeof(char); / 分配求编码的工作空间 c=2*n-1; cdlen=0; for(i=0; i=c; +i) HTi.weight=0; / 遍历赫夫曼树时用作结点状态标志 while(c) if(HTc.weight=0) / 向左 HTc.weight=1; if(HTc.lchild=0 & HTc.rchild=0) / 登记叶子结点字符编码 HCc=(char *)mall