单链表的插入和删除实验报告

1、 . 实验一、单链表的插入和删除一、目的了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。二、要求：建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。三、程序源代码#include"stdio.h"#include"string.h"#include"stdlib.h"#include"ctype.h"typedef struct node /定义结点 char data10; /结点的数据域为字符串struct nod

2、e *next; /结点的指针域 ListNode;typedef ListNode * LinkList; / 自定义LinkList单链表类型LinkList CreatListR1(); /函数，用尾插入法建立带头结点的单链表ListNode *LocateNode(); /函数，按值查找结点void DeleteList(); /函数，删除指定值的结点void printlist(); /函数，打印链表中的所有值void DeleteAll(); /函数，删除所有结点，释放内存/=主函数=void main() char ch10,num10; LinkList head; head=

3、CreatListR1(); /用尾插入法建立单链表，返回头指针 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); /输入要删除的字符串 DeleteL

4、ist(head,ch); printlist(head); DeleteAll(head); /删除所有结点，释放内存/=用尾插入法建立带头结点的单链表= LinkList CreatListR1(void) char ch10; LinkList head=(LinkList)malloc(sizeof(ListNode); /生成头结点 ListNode *s,*r,*pp; r=head; r->next=NULL; printf("Input # to end "); /输入“#”代表输入结束 printf("Please input Node_d

5、ata:"); scanf("%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("

6、;Please input Node_data:"); 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=NU

7、LL则查找失败，否则p指向找到的值key的结点/=删除带头结点的单链表中的指定结点=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; f

8、ree(r); /释放结点/=打印链表=void printlist(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

9、 Insert(ListNode *head) / the insert 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(

10、"%s",in->data);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函数中会出现没有地址的情况

11、找不到地址就不能执行功能 然后把locate函数的判断语句改一下 避免矛盾的出现。实验二、二叉树操作一、 目的掌握二叉树的定义、性质及存储方式，各种遍历算法。二、 要求采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。三、 程序源代码#include"stdio.h"#include"string.h"#define Max 20 /结点的最大个数typedef struct node char data; struct node *lchild,*rchild;BinTNode; /自定义二

12、叉树的结点类型typedef BinTNode *BinTree; /定义二叉树的指针int NodeNum,leaf; /NodeNum为结点数，leaf为叶子数/=基于先序遍历算法创建二叉树=/=要求输入先序序列，其中加入虚结点“#”以示空指针的位置=BinTree CreatBinTree(void) BinTree T; char ch; if(ch=getchar()='#')return(NULL); /读入#，返回空指针 else T=(BinTNode *)malloc(sizeof(BinTNode); / 生成结点T->data=ch;T->lc

13、hild=CreatBinTree(); /构造左子树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(

14、"%c",T->data); /访问结点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=TreeDept

15、h(T->lchild); /求左深度hr=TreeDepth(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; /定义结点的指针数组cq cq

16、1=T; /根入队 while(front!=rear) front=(front+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,de

17、pth; printf("n");printf("Creat Bin_Tree； Input preorder:"); /输入完全二叉树的先序序列， / 用#代表虚结点，如ABD#CE#F# root=CreatBinTree(); /创建二叉树，返回根结点 do /从菜单中选择遍历方式，输入序号。printf("t* select *n");printf("t1: Preorder Traversaln"); printf("t2: Iorder Traversaln");printf(&qu

18、ot;t3: Postorder traversaln");printf("t4: PostTreeDepth,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

19、 Preorder: ");Preorder(root); /先序遍历break;case 2: printf("Print Bin_Tree Inorder: ");Inorder(root); /中序遍历break;case 3: printf("Print Bin_Tree Postorder: ");Postorder(root); /后序遍历break;case 4: depth=TreeDepth(root); /求树的深度及叶子数printf("BinTree Depth=%d BinTree Node number=%

20、d",depth,NodeNum);printf(" BinTree Leaf number=%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.预计先序遍历结果：abdhlm

21、iejncfkog2.预计中序遍历结果：lhmdibenjafokcg3.预计后序遍历结果：lmhidnjebokfgca4.结点数 15 高度5 叶子数 6实际结果：实验心得：这次实验主要是要让我们熟练树及其相关知识 熟练掌握先序中序后序遍历，层次遍历 然后我们自己画一个图 会实现以上功能 以及叶子数 结点数还有高度的计算 程序里面大量运用了递归以及队的应用， 实验三、图的遍历操作一、 目的掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储结构；掌握DFS及BFS对图的遍历操作；了解图结构在人工智能、工程等领域的广泛应用。二、 要求采用邻接矩阵和邻接链表作为图的存储结构，完成有向图

22、和无向图的DFS和BFS操作。三、 DFS和BFS 的基本思想深度优先搜索法DFS的基本思想：从图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 struct char vexsMaxVertexNum; /顶点表 int edgesMaxVertexNumMaxVertexNum; /邻接矩阵，可看作边表 int n,e; /图中的顶点数n和边数eMGraph; /用邻接矩阵表示的图的类型/=建立邻接矩阵=void CreatMGraph(MGra

24、ph *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; /读入顶点信息，建立顶点

25、表 for(i=0;i<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; /若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句 /=定义标志向量

26、，为全局变量=typedef enumFALSE,TRUE Boolean;Boolean visitedMaxVertexNum;/=DFS：深度优先遍历的递归算法=void DFSM(MGraph *G,int i) /以Vi为出发点对邻接矩阵表示的图G进行DFS搜索，邻接矩阵是0，1矩阵 int j; printf("%c",G->vexsi); /访问顶点Vi visitedi=TRUE; /置已访问标志 for(j=0;j<G->n;j+) /依次搜索Vi的邻接点if(G->edgesij=1 && ! visitedj)

27、DFSM(G,j); /（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) /Vi未访问过 DFSM(G,i); /以Vi为源点开始DFS搜索/=BFS：广度优先遍历=void BFS(MGraph *G,int k) /以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索 int i,j,f=0,r=0; int cqMaxVertexNum; /定义队列 for(i=0

28、;i<G->n;i+)visitedi=FALSE; /标志向量初始化 for(i=0;i<G->n;i+)cqi=-1; /队列初始化 printf("%c",G->vexsk); /访问源点Vk visitedk=TRUE; cqr=k; /Vk已访问，将其入队。注意，实际上是将其序号入队 while(cqf!=-1) /队非空则执行 i=cqf; f=f+1; /Vf出队 for(j=0;j<G->n;j+) /依次Vi的邻接点Vj if(G->edgesij=1 && !visitedj) /Vj未访问

29、 printf("%c",G->vexsj); /访问Vj visitedj=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: &quo

30、t;); BFS(G,3); /以序号为3的顶点开始广度优先遍历 printf("n");调试结果：自己画的图： 1对应顶点下标0 以此类推 9对应下标8预计运行结果：DFS:012345678BFS: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个元素作为哨兵in

32、t n; /顺序表实际的长度1、 直接插入排序的基本思想：每次将一个待排序的记录，按其关键字大小插入到前面已排序好的子文件中的适当位置，直到全部记录插入完成为止。/=直接插入排序法=void InsertSort(SeqList R) /对顺序表R中的记录R1n按递增序进行插入排序 int i,j; for(i=2;i<=n;i+) /依次插入R2，Rn if(Ri.key<Ri-1.key) /若Ri.key大于等于有序区中所有的keys，则Ri留在原位 R0=Ri;j=i-1; /R0是Ri的副本 do /从右向左在有序区R1i-1中查找Ri的位置Rj+1=Rj; /将关键字大

33、于Ri.key的记录后移j-; while(R0.key<Rj.key); /当Ri.keyRj.key 是终止 Rj+1=R0; /Ri插入到正确的位置上/endif2、 冒泡排序的基本思想：设想被排序的记录数组R1n垂直排序。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上“漂浮”（交换），如此反复进行，直到最后任意两个气泡都是轻者在上，重者在下为止。/=冒泡排序=typedef enumFALSE,TRUE Boolean; /FALSE为0，TRUE为1void BubbleSort(SeqList R) /自下向上扫描对R做冒泡排序

34、int i,j; Boolean exchange; /交换标志 for(i=1;i<n;i+) /最多做n-1趟排序exchange=FALSE; /本趟排序开始前，交换标志应为假for(j=n-1;j>=i;j-) /对当前无序区Rin 自下向上扫描 if(Rj+1.key<Rj.key) /两两比较，满足条件交换记录R0=Rj+1; /R0不是哨兵，仅做暂存单元Rj+1=Rj;Rj=R0;exchange=TRUE; /发生了交换，故将交换标志置为真 if(! exchange) /本趟排序未发生交换，提前终止算法 return; /endfor（为循环）3、 快速排序

35、的基本思想：在待排序的n个记录中任取一个记录（通常取第一个记录），把该记录作为支点（又称基准记录）（pivot），将所有关键字比它小的记录放置在它的位置之前，将所有关键字比它大的记录放置在它的位置之后(称之为一次划分过程)。之后对所分的两部分分别重复上述过程，直到每部分只有一个记录为止。/1.=一次划分函数=int Partition(SeqList R,int i,int j) / 对Rij做一次划分，并返回基准记录的位置 RecType pivot=Ri; /用第一个记录作为基准 while(i<j) /从区间两端交替向中间扫描，直到i=j while(i<j &&am

36、p;Rj.key>=pivot.key) /基准记录pivot相当与在位置i上 j-; /从右向左扫描，查找第一个关键字小于pivot.key的记录Rjif(i<j) /若找到的Rj.key < pivot.key，则 Ri+=Rj; /交换Ri和Rj，交换后i指针加1while(i<j &&Ri.key<=pivot.key) /基准记录pivot相当与在位置j上 i+; /从左向右扫描，查找第一个关键字小于pivot.key的记录Riif(i<j) /若找到的Ri.key > pivot.key，则 Rj-=Ri; /交换Ri和Rj

37、，交换后j指针减1 Ri=pivot; /此时，i=j，基准记录已被最后定位 return i; /返回基准记录的位置/2.=快速排序=void QuickSort(SeqList R,int low,int high) /Rlow.high快速排序 int pivotpos; /划分后基准记录的位置 if(low<high) /仅当区间长度大于1时才排序pivotpos=Partition(R,low,high); /对Rlow.high做一次划分，得到基准记录的位置QuickSort(R,low,pivotpos-1); /对左区间递归排序QuickSort(R,pivotpos+1

38、,high); /对右区间递归排序 4、 直接选择排序的基本思想：第i趟排序开始时，当前有序区和无序区分别为R1i-1和Rin（1in-1），该趟排序则是从当前无序区中选择出关键字最小的记录Rk，将它与无序区的的第一个记录Ri交换，有序区增加一个记录，使R1i,和Ri+1n分别为新的有序区和新的无序区。如此反复进行，直到排序完毕。/=直接选择排序=void SelectSort(SeqList R) int i,j,k; for(i=1;i<n;i+) /做第i趟排序（1in-1）k=i;for(j=i+1;j<=n;j+) /在当前无序区Rin中选key最小的记录Rk if(Rj

39、.key<Rk.key)k=j; /k记下目前找到的最小关键字所在的位置if(k!=i) / /交换Ri和Rk R0=Ri;Ri=Rk;Rk=R0; /endif /endfor5、 堆排序的基本思想：它是一种树型选择排序，特点是：在排序的过程中，将R1n看成是一个完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大（或最小）的记录。即：把待排序文件的关键字存放在数组R1n子中，将R看成是一棵二叉树，每个结点表示一个记录，源文件的第一个记录R1作为二叉树的根，以下各记录R2n依次逐层从左到右排列，构成一棵完全二叉树，任意结点Ri的左孩子

40、是R2i，右孩子是R2i+1，双亲是Ri/2。对这棵完全二叉树的结点进行调整，使各结点的关键字满足下列条件：Ri.keyR2i.key并且Ri.keyR2i+1.key 称小堆根或 Ri.keyR2i.key并且Ri.keyR2i+1.key 称大堆根/=大根堆调整函数=void Heapify(SeqList R,int low,int high) / 将Rlow.high调整为大根堆，除Rlow外，其余结点均满足堆性质 int large; /large指向调整结点的左、右孩子结点中关键字较大者 RecType temp=Rlow; /暂存调整结点 for(large=2*low; lar

41、ge<=high;large*=2) /Rlow是当前调整结点 /若large>high,则表示Rlow是叶子，调整结束；否则先令large指向Rlow的左孩子if(large<high && Rlarge.key<Rlarge+1.key) large+; /若Rlow的右孩子存在且关键字大于左兄弟，则令large指向它 /现在Rlarge是调整结点Rlow的左右孩子结点中关键字较大者if(temp.key>=Rlarge.key) /temp始终对应Rlow break; /当前调整结点不小于其孩子结点的关键字，结束调整Rlow=Rlarge;

42、 /相当于交换了Rlow和Rlargelow=large; /令low指向新的调整结点，相当于temp已筛下到large的位置 Rlow=temp; /将被调整结点放入最终位置上/=构造大根堆=void BuildHeap(SeqList R) /将初始文件R1.n构造为堆 int i; for(i=n/2;i>0;i-)Heapify(R,i,n); /将Ri.n调整为大根堆/=堆排序=void HeapSort(SeqList R) /对R1.n进行堆排序，不妨用R0做暂存单元 int i; BuildHeap(R); /将R1.n构造为初始大根堆 for(i=n;i>1;i-

43、) /对当前无序区R1.i进行堆排序，共做n-1趟。R0=R1; R1=Ri;Ri=R0; /将堆顶和堆中最后一个记录交换Heapify(R,1,i-1); /将R1.i-1重新调整为堆，仅有R1可能违反堆性质。 6、 二路归并排序的基本思想：假设初始序列n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或1的有序子序列；再两两归并，如此重复，直到一个长度为n的有序序列为止。/=将两个有序的子序列Rlow.m和Rm+1.high归并成有序的序列Rlow.high=void Merge(SeqList R,int low,int m,int high)

44、 int i=low,j=m+1,p=0; /置初始值 RecType *R1; /R1为局部量 R1=(RecType *)malloc(high-low+1)*sizeof(RecType); /申请空间 while(i<=m && j<=high) /两个子序列非空时取其小者输出到R1p上R1p+=(Ri.key<=Rj.key)? Ri+:Rj+; while(i<=m) /若第一个子序列非空，则复制剩余记录到R1R1p+=Ri+; while(j<=high) /若第二个子序列非空，则复制剩余记录到R1中R1p+=Rj+; for(p=0

45、,i=low;i<=high;p+,i+)Ri=R1p; /归并完成后将结果复制回Rlow.high/=对R1.n做一趟归并排序=void MergePass(SeqList R,int length) int i; for(i=1;i+2*length-1<=n;i=i+2*length)Merge(R,i,i+length-1,i+2*length-1); /归并长度为length的两个相邻的子序列 if(i+length-1<n) /尚有一个子序列，其中后一个长度小于lengthMerge(R,i,i+length-1,n); /归并最后两个子序列 /注意：若in且i+length-1n时，则剩余一个子序列轮空，无须归并/