当前位置：文档之家 › 数据结构

数据结构

  • 格式：doc
  • 大小：43.00 KB
  • 文档页数：11

《数据结构上机习题》学生姓名：________ 学号：__________ 班级：____________ 专业：__________ 指导教师：________提交日期：2010-12-12ⅩⅩ大学目录一、上机习题1.线性表：（一）线性表的基本操作（二）插入（三）删除（四）归并2.线性链表：（一）线性表的基本操作（二）插入（三）删除（四）归并二、总结与心得（一）、上机习题1.线性表#include <malloc.h>//malloc#include <stdio.h>#include <stdlib.h>//exit#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;//类定义状态typedef int Elemtype;#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef struct{Elemtype *elem;int length;int listsize;}SqList;Status InitList(SqList &L)//构造一个空的线形表L{L.elem=(Elemtype *)malloc(LIST_INIT_SIZE*sizeof(Elemtype));if(!L.elem)exit (OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;return OK;}Status ListInsert(SqList &L,int i,Elemtype e)//插入{if(i<1||i>L.length+1) return ERROR;if(L.length>=L.listsize){Elemtype *newbase;newbase=(Elemtype*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(Elemtype));if(!newbase)exit (OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;}int *q,*p;q=&(L.elem[i-1]);for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;*q=e;++L.length;return OK;}Status ListDelete(SqList &L,int i,Elemtype &e)//删除{if(i<1||i>L.length+1) return ERROR;int *p,*q;p=&(L.elem[i-1]);//p为被删除元素的位置e=*p;//被删除元素的值赋给eq=L.elem+L.length-1;//表尾元素的位置for(++p;p<=q;++p) ////被删除元素的值赋给e*(p-1)=*p;--L.length;return OK;}void MergeList(SqList &La,SqList &Lb,SqList &Lc){//对俩个已知有序表进行非递减排序int *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(*pa<=*pb)*pc++=*pa++;else *pc++=*pb++;}while(pa<=pa_last) *pc++=*pa++;while(pb<=pb_last) *pc++=*pb++;}Status Listempty(SqList &L)//判空{if(L.length==0)return TRUE;else return FALSE;}Status ListLength(SqList &L)//求表长{if(Listempty(L)==0)return L.length;}Status GetElem(SqList &L,int i)//取出表中指定元素{Elemtype e;e=L.elem[i-1];return e;}Status compare(Elemtype m,Elemtype n){if(m==n)return 1;else return 0;}Status LocateElem(SqList L,Elemtype e){//查找，定位。

若找到，返回在L中的位序，否则返回0 int i=1;int *p=L.elem;//p的初值为第一个元素的存储位置while(i<=L.length&&!(*compare)(*p++,e)) ++i;if(i<=L.length) return i;else return 0;}void input(SqList &L)//输入表中各元素{int n;printf("输入表长n的值:");scanf("%d",&n);//n为需要的表长printf("输入表中%d个元素:\n",n);int i;for(i=0;i<n;i++)scanf("%d",&L.elem[i]);L.length=n;}void output(SqList &L)//输出表中各元素{int n=L.length;printf("输出L表中%d元素为:\n",n);for(int j=0;j<n;j++)printf("%d ",L.elem[j]);printf("\n");}void main(){int a,i,e;SqList L1,L2,L3;InitList(L1);InitList(L2);InitList(L3);//构造一个空的线形表Linput(L1);input(L2);output(L1);output(L2);printf("\n线形表的基本操作:\n");printf("\n求表长:L1的长度%d , L2的长度%d\n",ListLength(L1),ListLength(L2));printf("\n取出表中指定元素:输入i,取出L1中i位置的元素:\n");scanf("%d",&i);printf("\n取出表L1中指定元素值为:%d\n",GetElem(L1,i));printf("\n(一)、线形表的定位\n");printf("\n输入在L1中要查找的元素!!\n");scanf("%d",&e);a=LocateElem(L1,e);//查找e元素在L1中的位置printf("查找元素%d在L1中的位序为:%d\n",e,a);printf("\n(二)、线形表的归并\n");MergeList(L1,L2,L3);//对俩个已知有序表进行非递减排序printf("对俩个有序表L1,L2进行非递减排序，并输出新表L3:");output(L3);printf("\n(三)、线形表的插入\n");printf("\n输入i与元素e,把元素e插入到L1中i位置:\n");scanf("%d %d",&i,&e);ListInsert(L1,i,e);printf("\n");//向L1中插入元素output(L1);printf("\n(四)、线形表的删除\n");printf("\n输入i,删除L1中i位置的元素并赋给e:\n");scanf("%d",&i);ListDelete(L1,i,a);//向L1删除中元素printf("\n输出被删除的元素e:%d\n",e);//输出被删除的元素output(L1);}2.线性链表#include <malloc.h>//malloc#include <stdio.h>#include <stdlib.h>//exit#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;//类定义状态typedef int Elemtype;#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef struct LNode//定义一个新类型{ //结点类型Elemtype data;struct LNode *next;}LNode,*LinkList;Status ListDelete(LinkList &L,int i,Elemtype &e)//删除{LNode *p;LNode *q;p=L;int j=0;while(p->next&&j<i-1)//寻找第i个结点,并使p指向其前趋{p=p->next;++j;}if(!(p->next||j>i-1)) return ERROR;q=p->next;p->next=q->next;e=q->data;free(q);return OK;}void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc){//对俩个已知有序表进行非递减排序LNode *pa,*pb,*pc;Lc=(LinkList)malloc(sizeof(LNode));Lc->next=NULL;pc=Lc;pa=La->next;pb=Lb->next;while(pa&&pb){if(pa->data<=pb->data){La->next=pa->next;//截取点pa->next=pc->next;//将pa插入pc之后pc->next=pa;pc=pa;pa=La->next;}else{Lb->next=pb->next;//截取点pb->next=pc->next;//将pb插入pc之后pc->next=pb;pc=pb;pb=Lb->next;}}pc->next=pa?pa:pb;free(Lb);}Status InitList(LinkList &L)//构造一个空的线形链表L {L=(LinkList)malloc(sizeof(LNode));L->next=NULL;return OK;}void CreatList(LinkList &L)//初始化一个线形链表L {LNode *p,*q;int n;L=(LinkList)malloc(sizeof (LNode));L->next=NULL;//建立一个带头结点的单链表p=L;printf("输入一个线形链表的长度:");scanf("%d",&n);printf("输入链表中%d元素\n",n);for(int i=0;i<n;i++){q=(LinkList)malloc(sizeof(LNode));//生成新结点scanf("%d",&q->data);q->next=p->next;p->next=q;p=p->next;}}void output(LinkList L)//输出链表中各元素{LNode *p;p=L->next;printf("\n输出链表中所有元素:\n");while(p){printf("%d ",p->data);p=p->next;}printf("\n");}Status ListInsert(LinkList &L,int i,Elemtype e)//插入{LNode *p;LNode *s;p=L;int j=0;while(p&&j<i-1){p=p->next; ++j;//寻找第i-1个结点}if(!p||j>i-1) return ERROR;s=(LinkList)malloc(sizeof (LNode));//生成新结点s->data=e;s->next=p->next;p->next=s;output(L);return OK;}void main(){LinkList L1,L2,L3;int i,e,a;CreatList(L1);output(L1);//初始化一个线形链表CreatList(L2);output(L2);//初始化一个线形链表printf("\n(一)、线形链表的归并\n");MergeList(L1,L2,L3);//对俩个已知有序表进行非递减排序printf("对俩个有序链表L1,L2进行非递减排序，并输出新表L3:");output(L3);printf("\n(二)、线形链表的插入\n");printf("\n输入i与元素e,把元素e插入到L3中i位置:\n");scanf("%d %d",&i,&e);ListInsert(L3,i,e);printf("\n");//向L1中插入元素output(L3);printf("\n(三)、线形链表的删除\n");printf("\n输入i,删除L3中i位置的元素并赋给e:\n");scanf("%d",&i);ListDelete(L3,i,a);printf("\n");//向L1删除中元素printf("\n输出被删除的元素e:%d\n",e);//输出被删除的元素output(L3);}学号：2009072304 姓名：朱学青 班级：20090202By 朱学青 11 （二）总结与心得经过这几周的上机实验，我觉得自己编程的能力又上了一个层面，回想以前的上机课，我总是照搬笔记或者书本，对那些密密麻麻的程序式，我总是觉得脑子里似懂非懂。

合集下载

常用八种数据结构

常用八种数据结构

常见的数据结构包括数组、链表、队列、栈、树、堆、哈希表和图，每种数据结构都有其特点，如下：常见数据结构• 1.数组• 2.链表• 3.队列• 4.栈• 5.树• 6.图•7.哈希表•8.堆1.数组特点：•固定大小的线性数据结构•支持快速随机访问•插入和删除效率比较低一般应用于需要快速随机访问元素的场景。

案例：2.链表特点：•动态大小的数据结构•插入和删除效率比较高•不支持快速随机访问适用于需要频繁插入和删除元素的场景案例：3.队列特点：•先进先出•插入操作在队尾进行，删除操作在队头进行应用于需要先进先出访问元素的场景，如任务调度、消息队列等案例：4.栈特点：•先进后出•插入和删除在栈顶进行应用于需要后进先出访问元素的场景，如函数调用栈、表达式求值等案例：5.树特点：•非线性，由节点和边组成•树中的节点有层次关系，一个节点可以有多个子节点应用于需要表示层次结构的场景，比如文件系统、组织结构等案例：6.图特点：•非线性，由节点和边组成•图中的节点可以通过边来相互连接应用于需要表示网络结构的场景，如社交网络、交通网络等。

案例：7.哈希表特点：•基于哈希函数实现的键值对数据结构•支持快速的插入、删除和查找操作应用于需要快速查找和插入操作的场景，如字典、缓存等。

案例：8.堆特点：•堆是一颗完全二叉树•分为最大堆和最小堆•最大堆：每个节点的值都大于或等于其子节点的值。

•最小堆：每个节点的值都小于或等于其子节点的值。

•支持快速获取最大值或最小值的操作。

适用于优先队列，堆排序和实现高效的合并K个有序链表问题。

案例。

什么是数据结构

什么是数据结构

什么是数据结构数据结构是计算机科学中的基础概念之一，它是指组织和存储数据的方式，以及数据之间的关系和操作。

在计算机程序设计中，数据结构是指特定数据的组织形式，这些数据可以是数字、字符、实体对象等。

数据结构的选择对于程序的效率和功能具有重要影响。

一、数据结构的基本概念数据结构主要包括以下几个基本概念：1. 数据元素：数据元素是构成数据的最小单位，可以是单个的基本数据类型，也可以是多个基本数据类型组合而成的复合数据类型。

2. 数据项：数据元素中的一个个数据项是可以进行操作的最小单位，也可以理解为一个字段或属性。

3. 数据对象：数据对象是指具有相同性质的数据元素的集合，是数据集合的抽象。

4. 数据结构：数据结构是指数据元素之间的关系以及支持的操作，可以是线性的、非线性的、顺序的、层次的等不同的组织方式。

5. 数据类型：数据类型是一种特定的数据结构，用于描述数据的存储格式和支持的操作。

常见的数据类型包括整型、浮点型、字符型等。

6. 数据存储：数据存储是指数据在计算机中的具体储存形式，可以是内存中的数组、链表，也可以是硬盘中的文件等。

二、常见的数据结构1. 数组：数组是把具有相同类型的数据元素按照一定顺序排列并以连续的内存空间表示的数据结构，通过下标可以快速定位元素。

2. 链表：链表是由若干个结点组成，每个结点包含数据元素和指向下一个结点的指针，它的特点是空间不连续，插入、删除操作较灵活。

3. 栈：栈是一种先进后出的数据结构，只允许在栈顶进行插入和删除操作，类似于弹夹。

4. 队列：队列是一种先进先出的数据结构，只允许在队尾插入元素，在队头删除元素，类似于排队。

5. 树：树是由若干个结点组成的层次结构，每个结点可以有多个子结点，用于表示具有层次关系的数据。

6. 图：图是由若干个结点和边组成，结点表示数据元素，边表示结点之间的关系，用于表示具有复杂关系的数据。

三、数据结构的应用数据结构在计算机领域有广泛的应用，常见的应用包括：1. 数据库管理系统：数据库中的数据需要通过适当的数据结构进行组织和管理，如B+树、散列表等。

数据结构大纲知识点

数据结构大纲知识点

数据结构大纲知识点一、绪论。

1. 数据结构的基本概念。

- 数据、数据元素、数据项。

- 数据结构的定义（逻辑结构、存储结构、数据的运算）- 数据结构的三要素之间的关系。

2. 算法的基本概念。

- 算法的定义、特性（有穷性、确定性、可行性、输入、输出）- 算法的评价指标（时间复杂度、空间复杂度的计算方法）二、线性表。

1. 线性表的定义和基本操作。

- 线性表的逻辑结构特点（线性关系）- 线性表的基本操作（如初始化、插入、删除、查找等操作的定义）2. 顺序存储结构。

- 顺序表的定义（用数组实现线性表）- 顺序表的基本操作实现（插入、删除操作的时间复杂度分析）- 顺序表的优缺点。

3. 链式存储结构。

- 单链表的定义（结点结构，头指针、头结点的概念）- 单链表的基本操作实现（建立单链表、插入、删除、查找等操作的代码实现及时间复杂度分析）- 循环链表（与单链表的区别，操作特点）- 双向链表（结点结构，基本操作的实现及特点）三、栈和队列。

1. 栈。

- 栈的定义（后进先出的线性表）- 栈的基本操作（入栈、出栈、取栈顶元素等操作的定义）- 顺序栈的实现（存储结构，基本操作的代码实现）- 链栈的实现（与单链表的联系，基本操作的实现）- 栈的应用（表达式求值、函数调用栈等）2. 队列。

- 队列的定义（先进先出的线性表）- 队列的基本操作（入队、出队、取队头元素等操作的定义）- 顺序队列（存在的问题，如假溢出）- 循环队列的实现（存储结构，基本操作的代码实现，队空和队满的判断条件）- 链队列的实现（结点结构，基本操作的实现）- 队列的应用（如操作系统中的进程调度等）四、串。

1. 串的定义和基本操作。

- 串的概念（字符序列）- 串的基本操作（如连接、求子串、比较等操作的定义）2. 串的存储结构。

- 顺序存储结构（定长顺序存储和堆分配存储）- 链式存储结构（块链存储结构）3. 串的模式匹配算法。

- 简单的模式匹配算法（Brute - Force算法）的实现及时间复杂度分析。

数据结构基础知识

数据结构基础知识

复习提纲第一章数据构造概述根本概念与术语〔P3〕1．数据构造是一门研究非数值计算程序设计问题中计算机的操作对象以及他们之间的关系和操作的学科.2．数据是用来描述现实世界的数字,字符,图像,声音,以及能够输入到计算机中并能被计算机识别的符号的集合2．数据元素是数据的根本单位3．数据对象一样性质的数据元素的集合4．数据构造三方面容:数据的逻辑构造.数据的存储构造.数据的操作.〔1〕数据的逻辑构造指数据元素之间固有的逻辑关系.〔2〕数据的存储构造指数据元素及其关系在计算机的表示( 3 ) 数据的操作指在数据逻辑构造上定义的操作算法,如插入,删除等.5.时间复杂度分析--------------------------------------------------------------------------------------------------------------------1、名词解释：数据构造、二元组2、根据数据元素之间关系的不同，数据的逻辑构造可以分为集合、线性构造、树形构造和图状构造四种类型。

3、常见的数据存储构造一般有四种类型，它们分别是___顺序存储构造_____、___链式存储构造_____、___索引存储构造_____和___散列存储构造_____。

4、以下程序段的时间复杂度为___O(N2)_____。

int i,j,*;for(i=0;i<n:i++) n+1for(j=0;j<n;j++) n+1*+=i;------------------------------------------------------------------------------------------------------------------第二章线性表1.顺序表构造由n(n>=0)个具有一样性质的数据元素a1,a2,a3……,an组成的有穷序列//顺序表构造#define MA*SIZE 100typedef int DataType;Typedef struct{DataType items[MA*SIZE];Int length;}Sqlist,*LinkList;2.单链表（1）链表结点构造//链表的节点构造Typedef struct Node{int data;struct Node *ne*t;} Lnode,*Pnode,*LinkList;（2）结点遍历void TraverseList(LinkList t){LinkList p;while(t){p=t;t=t->ne*tfree(p);}}（3）链表操作算法：初始化、插入、输出、删除void InitList(LinkList *h){*h=(LinkList)malloc(sizeof(LNode));if(!h){print("初始化错误〞);return;}(*h)->ne*t=NULL;}void InsertList(LinkList h,int pos,datatype *){ LinkList p=h,q;int i=0;while(p&&i<pos-1){p=p->ne*t;i++;}if(!p||i>pos-1)print("插入位置出错!!〞);InitList(&q);q->ne*t=NULL;q->data=*;}void DeleteList(LinkList h,int pos){LinkList p=h,q;int i=0;while(p&&i<pos-1){p=p->ne*t;i++;}if(!p||i>pos-1){cout<<〞删除位置错误〞;return;}q=p->ne*t;p->ne*t=q->ne*t;free(q);}-----------------------------------------------------------------------------------------------------------------1、线性表中，第一个元素没有直接前驱，最后一个元素没有直接后驱。