当前位置：文档之家 › 《数据结构》基本操作指导

《数据结构》基本操作指导

  • 格式：doc
  • 大小：266.50 KB
  • 文档页数：55

目录指导一、单链表的操作----------------------------------------------------- 2指导二、栈及其应用------------------------------------------------------- 10指导三、串的基本操作---------------------------------------------------- 16指导四、二叉树的基本操作---------------------------------------------- 21指导五、图的存储和遍历------------------------------------------------- 31指导六、查找--------------------------------------------------------------- 41 指导七、排序--------------------------------------------------------------- 49指导一、单链表的操作一、指导目的1、掌握线性表的链式存储结构。

2、掌握利用链式存储结构实现线性表的基本操作。

3、掌握链式存储结构中的算法实现。

二、指导内容1、建立带头结点的单链表，并输出该单链表。

2、实现带头结点的单链表上的插入、删除、查找、修改操作。

三、操作指导1、定义单链表的结点结构单链表的结点结构可为一个结构体类型(slnodetype)，其成员是数据域和指针域，数据域可以是整数。

2、模块划分和程序控制流程根据实验要完成的各功能，设置初始化、建立单链表、输出单链表、插入、删除、查找、修改和主函数8个模块，对于要完成的各功能，采用适当的人机界面，用循环和分支结构构成菜单进行选择。

3、初始化模块int initiate(slnodetype **h)该模块中产生一个只有头结点的空单链表，用指针h作为函数的参数返回，因为h是指针变参，所以在函数的参数位置要以二级指针出现。

在函数里，申请一个头结点空间。

4、建立单链表模块int createlink(slnodetype *h)该模块中建立有若干个结点的单链表，用循环控制输入若干个整数，申请相应的结点空间，以输入的整数作为结点中的数据，依次链接到初始只有头结点的单链表h中，可以把输入0作为建立链表的结束。

5、输出单链表模块void display(slnodetype *h)对于传入的单链表h，依次输出单链表中的结点(数据)。

6、插入结点模块int inserti(slnodetype *h)设在第i个结点前插入数据为data的结点。

在该函数模块中输入i和数据data，对于传入的单链表h，先查找是否存在插入的位置(单链表h中至少要有i-1个结点)，若不存在插入位置，则不做任何操作；若存在插入位置，则申请一个结点，其数据为data，挂在第i-1个结点的后面。

7、删除结点模块int delete(slnodetype *h)在该函数模块中，首先可以调用输出模块输出传入的单链表h，以便选择要删除的结点，然后输入要删除结点的数据data，再查找是否存在要删除的结点，若不存在要删除的结点，则显示相应的信息；若存在要删除的结点，则删除该结点(包括删除该结点空间)。

8、查找模块int search(slnodetype *h)在该函数模块中，首先可以调用输出模块输出传入的单链表h，以便选择要查找的结点，然后输入要查找结点的数据data，再查找该结点是否存在，若不存在要查找的结点，则显示相应的信息；若存在要查找的结点，也显示相应的信息。

9、修改模块int modify(slnodetype *h)在该函数模块中，首先可以调用输出模块输出传入的单链表h，以便选择要修改的结点，然后输入要修改结点的数据data，再查找该结点是否存在，若不存在要查找的结点，则显示相应的信息；若存在要查找的结点，则显示原结点的数据，再提示输入新的数据，输入新的数据后，可以再调用输出模块输出修改结点数据后的单链表h，以便查看修改后的单链表h中的数据。

10、主函数main()主函数中定义指向单链表的指针等变量，首先调用初始化操作initiate( )，考虑人机界面，进入如下操作菜单的循环控制结构：========== menu ==========1--- create 2--- display3--- insert 4--- delete5--- search 6--- modify0--- exitchoose the number between 0 to 6:对于要进行的操作，进入接受选择的循环控制(对于不合法的选择，重新提示选择)，对与合法的选择，退出接受选择的循环控制，进入多分支结构，以执行相应的功能，执行完毕后回到操作菜单的循环控制中，依然显示菜单，提示选择。

当输入0(选择exit)，则程序实行结束。

四、算法实现#include "stdio.h"#include "alloc.h"#include "stdlib.h"typedef struct slnode{int data;struct slnode *next;}slnodetype;int initiate(slnodetype **h){if((*h=(slnodetype *)malloc(sizeof(slnodetype)))==NULL) return 0;(*h)->next=NULL;return 1;}int createlink(slnodetype *h){int i=1,data;slnodetype *p,*s;printf("\n create link \n");p=h;printf(" NO: %d: ",i); scanf("%d",&data);while(data!=0){s=(slnodetype *)malloc(sizeof(slnodetype)); s->data=data;s->next=NULL;p->next=s;p=s;printf(" NO: %d: ",++i); scanf("%d",&data); }}void display(slnodetype *h){slnodetype *p;printf("\n linklist:\n");p=h->next;while(p){printf("%5d",p->data);p=p->next;}}int inserti(slnodetype *h){slnodetype *s,*p;int i,data,j=0;printf("\n input i: ");scanf("%d",&i);printf(" input data: ");scanf("%d",&data); p=h;while(p!=NULL&&j<i-1){p=p->next;j++;}if(p!=NULL){s=(slnodetype *)malloc(sizeof(slnodetype)); s->data=data;s->next=p->next;p->next=s;}}int delete(slnodetype *h){slnodetype *p,*q;int data;display(h);printf("\n input data: ");scanf("%d",&data);q=h;p=h->next;while(p!=NULL&&p->data!=data){q=p;p=p->next;}if(p==NULL) printf("\n data %d nod found!",data); else{q->next=p->next;free(p);}}int search(slnodetype *h){slnodetype *p,*q;int data;display(h);printf("\n input data: ");scanf("%d",&data);q=h;p=h->next;while(p!=NULL&&p->data!=data){q=p;p=p->next;}if(p==NULL) printf("\n data %d nod found!",data); else printf("\n data find!");}int modify(slnodetype *h){slnodetype *p,*q;int data;display(h);printf("\n input data: ");scanf("%d",&data);q=h;p=h->next;while(p!=NULL&&p->data!=data){q=p;p=p->next;}if(p==NULL) printf("\n data %d nod found!",data); else{printf("\n old data: %d",p->data);printf("\n new data: "); scanf("%d",&(p->data));display(h);}}main(){slnodetype *la;char ch;initiate(&la);clrscr(); ch=10;while(ch!=48){clrscr();textcolor(13);gotoxy(28,3);cprintf("==========");textcolor(14);gotoxy(38,3);cprintf(" menu ");textcolor(13);gotoxy(44,3);cprintf("==========");textcolor(12);gotoxy(24,5);cprintf("1---");textcolor(10);gotoxy(29,5);cprintf("create");textcolor(12);gotoxy(46,5);cprintf("2---");textcolor(10);gotoxy(51,5);cprintf("display");textcolor(12);gotoxy(24,7);cprintf("3---");textcolor(10);gotoxy(29,7);cprintf("insert");textcolor(12);gotoxy(46,7);cprintf("4---");textcolor(10);gotoxy(51,7);cprintf("delete");textcolor(12);gotoxy(24,9);cprintf("5---");textcolor(10);gotoxy(29,9);cprintf("search");textcolor(12);gotoxy(46,9);cprintf("6---");textcolor(10);gotoxy(51,9);cprintf("modify");textcolor(12);gotoxy(36,11);cprintf("0---");textcolor(10);gotoxy(41,11);cprintf("exit");ch=10;while(ch<48 || ch>64){textcolor(11);gotoxy(16,13);cprintf("choose the number between 0 to 6: "); textcolor(14);ch=getche();}switch(ch){case '1': createlink(la);break;case '2': display(la);break;case '3': inserti(la);break;case '4': delete(la);break;case '5': search(la);break;case '6': modify(la);break;}getch();}}五、运行和测试结果========== menu ========== 1--- create 2--- display 3--- insert 4--- delete 5--- search 6--- modify 0--- exitchoose the number between 0 to 6: 1create linkNO: 1: 15NO: 2: 23NO: 3: 46NO: 4: 8NO: 5: 76NO: 6: 59NO: 7: 61NO: 8: 2NO: 9: 30NO: 10: 0========== menu ========== 1--- create 2--- display 3--- insert 4--- delete 5--- search 6--- modify 0--- exitchoose the number between 0 to 6: 2linklist:15 23 46 8 76 59 61 2 30========== menu ========== 1--- create 2--- display 3--- insert 4--- delete 5--- search 6--- modify 0--- exitchoose the number between 0 to 6: 3input i: 5input data: 28========== menu ========== 1--- create 2--- display 3--- insert 4--- delete 5--- search 6--- modify 0--- exitchoose the number between 0 to 6: 2linklist:15 23 46 8 28 76 59 61 2 30========== menu ========== 1--- create 2--- display 3--- insert 4--- delete 5--- search 6--- modify 0--- exitchoose the number between 0 to 6: 4linklist:15 23 46 8 28 76 59 61 2 30input data: 100data 100 not found!========== menu ========== 1--- create 2--- display 3--- insert 4--- delete 5--- search 6--- modify 0--- exitchoose the number between 0 to 6: 4linklist:15 23 46 8 28 76 59 61 2 30input data: 76========== menu ========== 1--- create 2--- display 3--- insert 4--- delete 5--- search 6--- modify 0--- exitchoose the number between 0 to 6: 2linklist:15 23 46 8 28 59 61 2 30========== menu ========== 1--- create 2--- display 3--- insert 4--- delete 5--- search 6--- modify0--- exitchoose the number between 0 to 6: 5linklist:15 23 46 8 28 59 61 2 30input data: 59data find!========== menu ========== 1--- create 2--- display 3--- insert 4--- delete 5--- search 6--- modify 0--- exitchoose the number between 0 to 6: 6linklist:15 23 46 8 28 59 61 2 30input data: 46old data: 46new data: 89linklist:15 23 89 8 28 59 61 2 30========== menu ========== 1--- create 2--- display 3--- insert 4--- delete 5--- search 6--- modify 0--- exitchoose the number between 0 to 6: 0指导二、栈及其应用一、指导目的1、掌握栈的数据类型描述及栈的特点。

合集下载

《数据结构》树的基本操作

《数据结构》树的基本操作

《数据结构》树的基本操作数据结构是计算机科学中的重要概念，它是指在计算机内存中组织数据的方式。

树是一种重要的数据结构，它具有层次结构和非线性的特点。

树的基本操作包括插入、删除、和遍历。

本文将详细介绍树的基本操作。

首先，我们先了解一下树的基本概念。

树由节点和边组成，每个节点可以有多个子节点，但每个子节点只能有一个父节点。

树有一个根节点，根节点没有父节点。

除了根节点之外，每个节点都有且仅有一个父节点。

节点之间的连接称为边。

树的基本操作之一是插入操作。

插入操作是指在树中添加新节点的过程。

要插入一个节点，需要找到它的父节点，然后将父节点的子节点指针指向新节点。

插入操作的时间复杂度为O(1)，因为它只需要修改指针。

另一个基本操作是删除操作。

删除操作是指将一个节点及其所有子节点从树中移除的过程。

要删除一个节点，需要找到它的父节点，然后将父节点的子节点指针指向它的子节点。

删除操作的时间复杂度取决于树的结构，通常为O(logn)到O(n)之间。

操作是树的另一个重要操作。

操作是指在树中查找一个特定节点的过程。

要一个节点，可以使用深度优先（DFS）或广度优先（BFS）算法。

DFS通过递归地遍历树的子节点，找到与目标节点相同的节点。

BFS通过遍历树的层次结构，逐层地目标节点。

操作的时间复杂度取决于树的深度，通常为O(logn)到O(n)之间。

最后，树的遍历操作是指按照一定顺序访问树中的所有节点。

常见的遍历方式有前序遍历、中序遍历和后序遍历。

前序遍历先访问根节点，然后递归地遍历左子树和右子树。

中序遍历先递归地遍历左子树，然后访问根节点，最后遍历右子树。

后序遍历先递归地遍历左子树和右子树，最后访问根节点。

树的遍历操作的时间复杂度为O(n)，其中n是树的节点数。

综上所述，树的基本操作包括插入、删除、和遍历。

这些操作在解决各种实际问题和算法中起着重要的作用。

掌握了树的基本操作，可以更好地理解和应用数据结构和算法。

同时，对于日常编程工作和面试准备也是非常有帮助的。

《数据结构》参考教案

《数据结构》参考教案


13
2、链队列的算法： ： 算法一：构造一个空队列 算法二：销毁一个队列 算法三：判队列是否为空： 算法四：入队列 算法五：出队列
3．循环队列的重要算法： 算法一：构造一个空队列 算法二：队列长度 int { QueueLength(SqQueue Q)
return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE; }
(2) 重要算法的实现：
入栈操作 取栈顶元素操作 取栈顶元素与出栈不同之处在于出栈操作改变栈顶指针 top 的位置，而取栈顶元素操作不改 出栈操作 判栈空操作 2． 链栈 一个链栈可由栈顶指针 top 唯一确定，当 top 为 NULL 时，是一个空栈。
12
第9讲
课程名称：数据结构 授 课 总课序 第9次 时 间 第4周 任 课 教 师 备课日期 讲 课 内 容 3.4 节
点
教 学 难 点 与关键
算法时间复杂度的计算
教学内容及板书纲要： 课程概述 对课程性质等课程相关情况进行介绍
第 1 章 绪论 1.1 什么是数据结构 用 3 个引例： 1．图书书目自动检索 2．人机对奕 3．交通灯管理 引出《数据结构》的研究内容 数据结构的基本概念和术语 1.2 数据结构的基本概念和术语 1. 数据 2. 数据元素、数据项 3. 数据对象、数据结构 4. 四类基本结构：集合、线性结构、树形结构、图形结构或网状结构。 5. 数据结构一般包括三方面的内容： 逻辑结构 存储结构(物理结构) 数据的运算 算法的设计取决于选定的数据逻辑结构，而算法的实现依赖于采用的存储结构。 6. 数据的两种存储结构： 顺序存储结构 链式存储结构 1.3 抽象数据类型的表示与实现 类 C 语言 1.4 算法和算法分析 1.4.1 算法 算法的定义 算法具有五个重要特性： 有穷性、确定性、可行性、输入、输出
数据结构试验报告-图的基本操作

数据结构试验报告-图的基本操作

中原工学院《数据结构》实验报告学院：计算机学院专业：计算机科学与技术班级：计科112姓名：康岩岩学号：201100814220 指导老师：高艳霞2012-11-22实验五图的基本操作一、实验目的1、使学生可以巩固所学的有关图的基本知识。

2、熟练掌握图的存储结构。

3、熟练掌握图的两种遍历算法。

二、实验内容[问题描述]对给定图，实现图的深度优先遍历和广度优先遍历。

[基本要求]以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。

以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。

【测试数据】由学生依据软件工程的测试技术自己确定。

三、实验前的准备工作1、掌握图的相关概念。

2、掌握图的逻辑结构和存储结构。

3、掌握图的两种遍历算法的实现。

四、实验报告要求1、实验报告要按照实验报告格式规范书写。

2、实验上要写出多批测试数据的运行结果。

3、结合运行结果，对程序进行分析。

【设计思路】【代码整理】#include "stdafx.h"#include <iostream>#include <malloc.h>using namespace std;typedef int Status;#define OK 1#define ERROR 0#define OVERFLOW -1#define MAX_SIZE 20typedef enum{DG,DN,UDG,UDN}Kind;typedef struct ArcNode{int adjvex; //顶点位置struct ArcNode *nextarc; //下一条弧int *info; //弧信息};typedef struct{char info[10]; //顶点信息ArcNode *fistarc; //指向第一条弧}VNode,AdjList[MAX_SIZE];typedef struct{AdjList vertices;int vexnum,arcnum; //顶点数，弧数int kind; //图的种类，此为无向图}ALGraph;//这是队列的节点，仅用于广度优先搜索typedef struct Node{int num;struct Node* next;};//队列的头和尾typedef struct{Node * front;Node *rear;}PreBit;int LocateV ex(ALGraph G,char info[]);//定位顶点的位置Status addArcNode(ALGraph &G,int adjvex); //图中加入弧Status CreatGraph(ALGraph&G);//创建图的邻接表Status DFSTraverse(ALGraph G);//深度优先搜索Status BFSTraverse(ALGraph G);//广度优先搜索Status DFS(ALGraph G,int v);//深度优先搜索中的数据读取函数，用于递归bool visited[MAX_SIZE]; // 访问标志数组//初始化队列Status init_q(PreBit&P_B){P_B.front=P_B.rear=(Node*)malloc(sizeof(Node));if(!P_B.front){exit(OVERFLOW);}P_B.front->next=NULL;}//将数据入队Status en_q(PreBit & P_B,int num){Node *p=(Node*)malloc(sizeof(Node));if(!p){exit(OVERFLOW);}p->num=num;p->next=NULL;P_B.rear->next=p;P_B.rear=p;return OK;}//出队Status de_q(PreBit & P_B){if(P_B.front==P_B.rear){return ERROR;}Node* p=P_B.front->next;P_B.front->next=p->next;if(P_B.rear==p){P_B.rear=P_B.front;}free(p);return OK;}Status CreatGraph(ALGraph&G){cout<<"请输入顶点数目和弧数目"<<endl;cin>>G.vexnum>>G.arcnum;//依次输入顶点信息for(int i=0;i<G.vexnum;i++){cout<<"请输入顶点名称"<<endl;cin>>G.vertices[i].info;G.vertices[i].fistarc=NULL;}//依次输入弧信息for(int k=1;k<=G.arcnum;k++){char v1[10],v2[10]; //用于表示顶点名称的字符数组int i,j; //表示两个顶点的位置BACK: //返回点cout<<"请输入第"<<k<<"条弧的两个顶点"<<endl;cin>>v1>>v2;i=LocateV ex(G,v1); //得到顶点v1的位置j=LocateV ex(G,v2); //得到顶点v2的位置if(i==-1||j==-1){ //头信息不存在则返回重输cout<<"不存在该节点!"<<endl;goto BACK; //跳到BACK 返回点}addArcNode(G,i); //将弧的顶点信息插入表中addArcNode(G,j);}return OK;}//倒序插入弧的顶点信息Status addArcNode(ALGraph &G,int adjvex){ArcNode *p; //弧节点指针p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=adjvex;p->nextarc=G.vertices[adjvex].fistarc;//指向头结点的第一条弧G.vertices[adjvex].fistarc=p; //头结点的第一条弧指向p，即将p作为头结点的第一条弧return OK;}//定位顶点的位置int LocateV ex(ALGraph G,char info[]){for(int i=0;i<G.vexnum;i++){if(strcmp(G.vertices[i].info,info)==0){ //头结点名称与传入的信息相等，证明该头节点存在return i; //此时返回位置}}return -1;}//深度优先搜索Status DFSTraverse(ALGraph G){for(int v=0;v<G.vexnum;v++){visited[v]=false;}char v1[10];int i;BACK:cout<<"请输入首先访问的顶点"<<endl;cin>>v1;i=LocateV ex(G,v1);if(i==-1){cout<<"不存在该节点!"<<endl;goto BACK;}DFS(G,i);return OK;}//深度优先搜索递归访问图Status DFS(ALGraph G,int v){visited[v]=true;cout<<G.vertices[v].info<<" ";//输出信息ArcNode *p;p=G.vertices[v].fistarc; //向头节点第一条while(p) //当弧存在{if(!visited[p->adjvex]){DFS(G,p->adjvex); //递归读取}p=p->nextarc;}return OK;}//广度优先搜索Status BFSTraverse(ALGraph G){for(int v=0;v<G.vexnum;v++){visited[v]=false;}char v1[10];int v;BACK:cout<<"请输入首先访问的顶点"<<endl;cin>>v1;v=LocateV ex(G,v1);if(v==-1){cout<<"不存在该节点!"<<endl;goto BACK;}PreBit P_B;init_q(P_B);ArcNode *p;visited[v]=true;cout<<G.vertices[v].info<<" ";//输出信息en_q(P_B,v); //将头位置v入队while(P_B.front!=P_B.rear){//当队列不为空时，对其进行访问int w=P_B.front->next->num;//读出顶点位置de_q(P_B);//顶点已经访问过，将其出队列p=G.vertices[w].fistarc;//得到与顶点相关的第一条弧while(p){if(!visited[p->adjvex]){en_q(P_B,p->adjvex);//将弧入队，但不读取，只是将其放在队尾}p=p->nextarc;}}return OK;}int _tmain(int argc, _TCHAR* argv[]){ALGraph G;CreatGraph(G);cout<<"深度优先搜索图:"<<endl;DFSTraverse(G);cout<<endl;cout<<"广度优先搜索图:"<<endl;BFSTraverse(G);cout<<endl;system("pause");return 0;}。

《数据结构》说课稿

《数据结构》说课稿

《数据结构》说课稿引言概述：数据结构是计算机科学的基础，它研究数据的组织、存储和管理方式，是计算机程序设计的重要组成部分。

本文将从四个方面介绍数据结构的基本概念、常见数据结构类型、数据结构的应用以及学习数据结构的重要性。

一、基本概念1.1 数据结构的定义：数据结构是指一组数据元素及其之间的关系，是数据的逻辑结构和物理结构的抽象。

1.2 数据结构的分类：数据结构可以分为线性结构、非线性结构和文件结构三类，每类又可以细分为多种具体类型。

1.3 数据结构的基本操作：数据结构的基本操作包括插入、删除、查找和修改等，这些操作是对数据进行增删改查的基础。

二、常见数据结构类型2.1 数组：数组是一种线性结构，它由相同类型的数据元素组成，通过下标访问元素，具有随机访问的特点。

2.2 链表：链表是一种非线性结构，它由节点组成，每个节点包含数据和指向下一个节点的指针，可以实现灵活的插入和删除操作。

2.3 栈和队列：栈和队列是两种特殊的线性结构，栈具有先入后出的特点，而队列具有先入先出的特点，它们在算法中有广泛的应用。

2.4 树和图：树和图是两种常见的非线性结构，树是一种层次结构，图是由节点和边组成的网络结构，它们在数据库、网络等领域有重要的应用。

三、数据结构的应用3.1 数据库管理系统：数据库管理系统是基于数据结构的软件，它通过合理的数据结构来存储和管理大量的数据，提供高效的数据访问和操作功能。

3.2 图像处理：图像处理涉及大量的像素数据，通过合适的数据结构可以高效地存储和处理图像，实现图像的压缩、滤波、特征提取等操作。

3.3 算法设计：算法是解决问题的步骤和方法，合适的数据结构可以提高算法的效率和性能，常见的排序、查找和图算法都离不开数据结构的支持。

四、学习数据结构的重要性4.1 提高编程能力：学习数据结构可以培养抽象思维和逻辑思维能力，提高编程的效率和质量。

4.2 解决实际问题：数据结构是解决实际问题的基础，通过合适的数据结构可以更好地组织和管理数据，实现高效的数据处理和分析。