《单链表的插入和删除实验报告.docx》由会员分享，可在线阅读，更多相关《单链表的插入和删除实验报告.docx（42页珍藏版）》请在三一文库上搜索。
1、参考医学实验一、单链表的插入和删除一、目的了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。二、要求：建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。三、程序源代码#include"stdio.h"#include"string.h"#include"stdlib.h"#include"ctype.h"typedef struct node/定义结点char data10;/结点的数据域为字符串struct node
2、*next;/结点的指针域ListNode;typedef ListNode * LinkList; /自定义LinkList单链表类型LinkList CreatListR1();/函数，用尾插入法建立带头结点的单链表参考医学ListNode *LocateNode();/函数，按值查找结点void DeleteList();/函数，删除指定值的结点void printlist();/函数，打印链表中的所有值void DeleteAll();/函数，删除所有结点，释放内存/=主函数 =void main()char ch10,num10;LinkList head;head=CreatLis
3、tR1();/用尾插入法建立单链表，返回头指针printlist(head);/遍历链表输出其值printf(" Delete node (y/n):");/输入“ y”或“ n”去选择是否删除结点scanf("%s",num);if(strcmp(num,"y")=0 | strcmp(num,"Y")=0) printf("Please input Delete_data:");scanf("%s",ch);/输入要删除的字符串DeleteList(head,ch);pr
4、intlist(head);DeleteAll(head);/删除所有结点，释放内存参考医学/=用尾插入法建立带头结点的单链表=LinkList CreatListR1(void)char ch10;LinkListhead=(LinkList)malloc(sizeof(ListNode);/ 生成头结点ListNode *s,*r,*pp;r=head;r->next=NULL;printf("Input # to end "); / printf("Please input Node_data:");输入“ #”代表输入结束scanf(&qu
5、ot;%s",ch); / while(strcmp(ch,"#")!=0) 输入各结点的字符串pp=LocateNode(head,ch);/ 按值查找结点，返回结点指针if(pp=NULL) / 没有重复的字符串，插入到链表中 s=(ListNode *)malloc(sizeof(ListNode);strcpy(s->data,ch);r->next=s;r=s;r->next=NULL;printf("Input # to end ");参考医学printf("Please input Node_data:
6、");scanf("%s",ch);return head;/返回头指针/=按值查找结点，找到则返回该结点的位置，否则返回NULL=ListNode *LocateNode(LinkList head, char *key)ListNode *p=head->next; /从开始结点比较while(p&&strcmp(p->data,key)!=0 ) /直到p 为NULL或p->data为key止p=p->next;/扫描下一个结点return p;/若 p=NULL则查找失败，否则p 指向找到的值key 的结点/=删除带
7、头结点的单链表中的指定结点=void DeleteList(LinkList head,char *key)ListNode *p,*r,*q=head;p=LocateNode(head,key);/按key值查找结点的if(p=NULL ) /若没有找到结点，退出参考医学printf("position error");exit(0);while(q->next!=p)/p为要删除的结点， q 为 p 的前结点q=q->next;r=q->next;q->next=r->next;free(r);/释放结点/=打印链表 =void prin
8、tlist(LinkList head)ListNode *p=head->next;while(p)printf("%s,",p->data);p=p->next;/从开始结点打印printf("n");/=删除所有结点，释放空间=void DeleteAll(LinkList head)参考医学ListNode *p=head,*r;while(p->next)r=p->next;free(p);p=r;free(p);运行结果：加的添加结点的代码：int Insert(ListNode *head)/ the inse
9、rt functionListNode *in,*p,*q;int wh;printf("input the insert node:");参考医学in=(ListNode *)malloc(sizeof(ListNode);in->next=NULL; p=(ListNode *)malloc(sizeof(ListNode);p->next=NULL; q=(ListNode *)malloc(sizeof(ListNode);q->next=NULL; if(!in)return 0;scanf("%s",in->data)
10、;printf("input the place where you want to insert you data:");scanf("%d",&wh);for(p=head;wh>0;p=p->next,wh-);q=p->next;p->next=in;in->next=q;return 1;参考医学运行结果：最后提示为 OK 添加成功。实验心得：这个实验中 主要修改的是 ch 和 num 把它们由指针改成数组 因为不改的话在后面 delect函数中会出现没有地址的情况 找不到地址就不能执行功能 然后把 loc
11、ate函数的判断语句改一下 避免矛盾的出现。参考医学实验二、二叉树操作一、目的掌握二叉树的定义、性质及存储方式，各种遍历算法。二、要求采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。三、程序源代码#include"stdio.h"#include"string.h"#define Max 20/typedef struct nodechar data;struct node *lchild,*rchild;结点的最大个数BinTNode;/自定义二叉树的结点类型typedef BinTNod
12、e *BinTree;/定义二叉树的指针int NodeNum,leaf;/NodeNum为结点数，leaf为叶子数/=基于先序遍历算法创建二叉树=/= 要求输入先序序列，其中加入虚结点“#”以示空指针的位置=参考医学BinTree CreatBinTree(void)BinTree T;char ch;if(ch=getchar()='#')return(NULL);/读入 #，返回空指针elseT=(BinTNode *)malloc(sizeof(BinTNode); / T->data=ch;生成结点T->lchild=CreatBinTree();/构造左
13、子树T->rchild=CreatBinTree();/构造右子树return(T);/=NLR 先序遍历 =void Preorder(BinTree T)if(T) printf("%c",T->data);/访问结点Preorder(T->lchild);/先序遍历左子树Preorder(T->rchild);/先序遍历右子树参考医学/=LNR 中序遍历 =void Inorder(BinTree T)if(T) Inorder(T->lchild);/中序遍历左子树printf("%c",T->data);/访
14、问结点Inorder(T->rchild);/中序遍历右子树/=LRN 后序遍历 =void Postorder(BinTree T)if(T) Postorder(T->lchild);/后序遍历左子树Postorder(T->rchild);/后序遍历右子树printf("%c",T->data);/访问结点/= 采用后序遍历求二叉树的深度、结点数及叶子数的递归算法=int TreeDepth(BinTree T)参考医学int hl,hr,max;if(T)hl=TreeDepth(T->lchild);/ 求左深度hr=TreeDept
15、h(T->rchild);/求右深度max=hl>hr? hl:hr;/取左右深度的最大值NodeNum=NodeNum+1;/求结点数if(hl=0&&hr=0) leaf=leaf+1;/ 若左右深度为0，即为叶子。return(max+1);else return(0);/= 利用“先进先出”（FIFO）队列，按层次遍历二叉树 =void Levelorder(BinTree T)int front=0,rear=1;BinTNode *cqMax,*p;/定义结点的指针数组cqcq1=T;/根入队while(front!=rear)front=(front+
16、1)%NodeNum;p=cqfront;/出队参考医学printf("%c",p->data);/if(p->lchild!=NULL)rear=(rear+1)%NodeNum;出队，输出结点的值cqrear=p->lchild;/左子树入队if(p->rchild!=NULL)rear=(rear+1)%NodeNum;cqrear=p->rchild;/右子树入队/=主函数 =void main()BinTree root;int i,depth;printf("n");printf("Creat Bin_
17、Tree；Input preorder:");/ 输入完全二叉树的先序序列，/用#代表虚结点，如ABD#CE#F#root=CreatBinTree();/创建二叉树，返回根结点do /从菜单中选择遍历方式，输入序号。参考医学printf("t* select *n");printf("t1: Preorder Traversaln");printf("t2: Iorder Traversaln");printf("t3: Postorder traversaln");printf("t4: P
18、ostTreeDepth,Node number,Leaf numbern");printf("t5: Level Depthn"); /按层次遍历之前，先选择4，求出该树的结点数。printf("t0: Exitn");printf("t*n");scanf("%d",&i);/输入菜单序号（ 0-5 ）switch (i)case 1: printf("Print Bin_tree Preorder: ");Preorder(root);/先序遍历break;case 2:
19、 printf("Print Bin_Tree Inorder: ");Inorder(root);/中序遍历break;case 3: printf("Print Bin_Tree Postorder: ");Postorder(root);/后序遍历break;case 4: depth=TreeDepth(root);/求树的深度及叶参考医学子数printf("BinTreeDepth=%dBinTreeNodenumber=%d",depth,NodeNum);printf(" BinTree Leaf number
20、=%d",leaf);break;case 5: printf("LevePrint Bin_Tree: ");Levelorder(root);/按层次遍历break;default: exit(1);printf("n"); while(i!=0);执行程序1. 先序遍历2. 中序遍历参考医学3. 后序遍历4. 结点数 叶子数 高度5.层次遍历自己设计的：abdhl#m#i#e#jn#cf#ko#g#1.预计先序遍历结果：abdhlmiejncfkog2.预计中序遍历结果：lhmdibenjafokcg3.预计后序遍历结果：lmhidnje
21、bokfgca4.结点数15 高度 5 叶子数6参考医学实际结果：实验心得 ：这次实验主要是要让我们熟练树及其相关知识熟练掌握先序中序后序遍历， 层次遍历然后我们自己画一个图会实现以上功能 以及叶子数结点数还有高度的计算程序里面大量运用了递归以及队的应用，参考医学实验三、图的遍历操作一、目的掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储结构；掌握 DFS 及 BFS 对图的遍历操作；了解图结构在人工智能、工程等领域的广泛应用。二、要求采用邻接矩阵和邻接链表作为图的存储结构，完成有向图和无向图的 DFS 和 BFS 操作。三、DFS 和 BFS 的基本思想深度优先搜索法 DFS 的
22、基本思想：从图 G 中某个顶点 Vo 出发，首先访问 Vo，然后选择一个与 Vo 相邻且没被访问过的顶点 Vi 访问，再从 Vi 出发选择一个与 Vi 相邻且没被访问过的顶点 Vj 访问， 依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则回退到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点 W ，从 W 出发按同样方法向前遍历。直到图中所有的顶点都被访问。广度优先算法 BFS 的基本思想： 从图 G 中某个顶点 Vo 出发，首先访问 Vo，然后访问与 Vo 相邻的所有未被访问过的顶点 V1 ，V2， ， Vt ；再依次访问与 V1， V2， ， Vt 相邻的起且未被参考医
23、学访问过的的所有顶点。如此继续，直到访问完图中的所有顶点。四、程序源代码1邻接矩阵作为存储结构的程序示例#include"stdio.h"#include"stdlib.h"#define MaxVertexNum 100/定义最大顶点数typedef structchar vexsMaxVertexNum;/顶点表int edgesMaxVertexNumMaxVertexNum;/邻接矩阵，可看作边表int n,e;/图中的顶点数n 和边数eMGraph;/用邻接矩阵表示的图的类型/=建立邻接矩阵 =void CreatMGraph(MGraph *
24、G)int i,j,k;char a;printf("Input VertexNum(n) and EdgesNum(e): ");scanf("%d,%d",&G->n,&G->e);/输入顶点数和边数scanf("%c",&a);printf("Input Vertex string:");for(i=0;i<G->n;i+)参考医学scanf("%c",&a);G->vexsi=a;/读入顶点信息，建立顶点表for(i=0;i&
25、lt;G->n;i+)for(j=0;j<G->n;j+)G->edgesij=0; / 初始化邻接矩阵 printf("Input edges,Creat Adjacency Matrixn");for(k=0;k<G->e;k+) /读入e 条边，建立邻接矩阵scanf("%d%d",&i,&j);/输入边（ Vi ，Vj ）的顶点序号G->edgesij=1;G->edgesji=1;/ 若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句/=定义标志向量，为全局变量=typedef
26、 enumFALSE,TRUE Boolean;Boolean visitedMaxVertexNum;/=DFS：深度优先遍历的递归算法=void DFSM(MGraph *G,int i) / 以 Vi 为出发点对邻接矩阵表示的图 G进行 DFS搜索，邻接矩阵是 0，1 矩阵参考医学int j;printf("%c",G->vexsi);/访问顶点Vivisitedi=TRUE;/置已访问标志for(j=0;j<G->n;j+)/依次搜索Vi的邻接点if(G->edgesij=1 && ! visitedj)DFSM(G,j);/
27、（Vi ，Vj ） E，且Vj未访问过，故 Vj 为新出发点void DFS(MGraph *G)int i;for(i=0;i<G->n;i+)visitedi=FALSE;/标志向量初始化for(i=0;i<G->n;i+)if(!visitedi)DFSM(G,i);/Vi/未访问过以 Vi 为源点开始DFS搜索/=BFS：广度优先遍历 =void BFS(MGraph *G,int k)/以 Vk为源点对用邻接矩阵表示的图G进行广度优先搜索int i,j,f=0,r=0;参考医学int cqMaxVertexNum;/定义队列for(i=0;i<G->
28、;n;i+)visitedi=FALSE;/标志向量初始化for(i=0;i<G->n;i+)cqi=-1;/队列初始化printf("%c",G->vexsk);/访问源点Vkvisitedk=TRUE;cqr=k;/Vk已访问，将其入队。注意，实际上是将其序号入队while(cqf!=-1) /队非空则执行i=cqf; f=f+1;/Vf出队for(j=0;j<G->n;j+)/依次Vi的邻接点Vjif(G->edgesij=1 && !visitedj) /Vj未访问printf("%c",G-&
29、gt;vexsj);/访问Vjvisitedj=TRUE;r=r+1; cqr=j;/访问过Vj入队/=main=void main()参考医学int i;MGraph *G;G=(MGraph*)malloc(sizeof(MGraph);/为图 G申请内存空间CreatMGraph(G); / printf("Print Graph DFS: ");建立邻接矩阵DFS(G);/深度优先遍历printf("n");printf("Print Graph BFS: ");BFS(G,3);/以序号为3 的顶点开始广度优先遍历print
30、f("n");参考医学调试结果：自己画的图：1 对应顶点下标0 以此类推9 对应下标 8预计运行结果：DFS:012345678参考医学BFS:324105687对应我这个图：DFS：123456789BFS：435216798实验心得：图在数据结构中是相当重要的一部分联系很多现实问题图的根本就是顶点和边通过顶点和边建立邻接矩阵以及邻接链表广度搜索和深度搜索是此算法着重关注的地方。要学会自己画图然后写出这两种搜索的结果， 程序中用了队的算法是亮点 通过 TRUE和 FAUSE 来标记顶点是否以及访问避免重复参考医学实验四、排序一、目的掌握各种排序方法的基本思想、排序过程、算
31、法实现，能进行时间和空间性能的分析， 根据实际问题的特点和要求选择合适的排序方法。二、要求实现直接排序、冒泡、直接选择、快速、堆、归并排序算法。比较各种算法的运行速度。三、程序示例#include"stdio.h"#include"stdlib.h"#define Max 100/假设文件长度typedef struct/定义记录类型int key;/关键字项RecType;typedef RecType SeqListMax+1; /SeqList为顺序表，表中第0个元素作为哨兵int n;/顺序表实际的长度1、直接插入排序的基本思想： 每次将一个待排序的记录， 按其关键字大小插入到前面已排序好的子文件中的适当位置，直到全部记录插入完成为止。参考医学/=直接插入排序法 =void InsertSort(SeqList R)/对顺序表 R 中的记录 R1n 按递增序进行插入排序int i,j;for(i=2;i<=n;i+)/依次插入R2， ， Rnif(Ri.key<Ri-1.key) /若Ri.key大于等于有序区中所有