数据结构

您所在的位置：网站首页 › 数组链表各自特点 › 数据结构

数据结构

2023-07-06 06:12| 来源: 网络整理| 查看: 265

前言

学习所记录，如果能对你有帮助，那就泰裤辣。

1.线性表概念

定义

基本操作

2.顺序表

定义

顺序表的实现--静态分配

动态分配

顺序表的特点

顺序表的插入和删除

顺序表的查找

按位查找

按值查找

3.单链表

定义

单链表的初始化

不带头节点的单链表

带头节点的单链表

插入按位序插入

指定结点的后插操作

指定结点的前插操作

按位序删除

指点结点的删除

单链表的查找

按位查找

按值查找

表的长度

单链表的建立

尾插法

头插法

4.双链表

插入

删除

5.循环链表

循环单链表

循环双链表

初始化

与双链表基本操作的不同

6.静态链表

7.顺序表和链表的异同

逻辑结构

存储结构

基本操作

1.线性表概念定义

线性表是具有相同数据类型的n (n>=0）个数据元素的有限序列，其中n为表长，当n = 0时线性表是一个空表。若用 L 命名线性表，则其一般表示为 L= (A1, A2, ... , Ai, Ai+1.…. , An)

注

1.Ai 是线性表中的 “ 第 i 个” 元素线性表中的位序( 位序从1开始,数组下标从0开始 ) 2.A1 是表头元素 ; an 是表尾元素。 3.除第一个元素外，每个元素有且仅有一个直接前驱;除最后一个元素外，每个元素有且仅有一个直接后继

基本操作

基本操作主要包括：创建、销毁、增删改查

基本操作 lnitList(&L):初始化表。构造一个空的线性表L，分配内存空间。DestroyList(&L):销毁操作。销毁线性表，并释放线性表L所占用的内存空间。ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素e。ListDelete(&L,i,&e)ListDelete(&L,i,&e):删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。LocateElem(Le):按值查找操作。在表L中查找具有给定关键字值的元素。GetElem(L,i):按位查找操作。获取表L中第i个位置的元素的值。

其他常用操作 Length(L):求表长。返回线性表L的长度，即L中数据元素的个数。PrintList(L):输出操作。按前后顺序输出线性表L的所有元素值。Empty(L):判空操作。若L为空表，则返回true，否则返回false。

2.顺序表定义

顺序表――用顺序存储的方式实现线性表顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

顺序表的实现--静态分配 #include #define MaxSize 10 //定义最大长度 typedef struct{ int data[MaxSize]; int length; //当前长度 }SqList; // 初始化顺序表 void InitList(SqList &L){ for(int i=0; inext = L; L = s; return true; } LNode *p; //指针指向当前扫描到的结点 int j=0; //当前p指向的是第几个结点 p = L; while (p!=NULL && jdata = e; s->next = p->next; p->next = s; return true; } 指定结点的后插操作 //后插操作:在p结点之后插入元素e bool InsertNextNode (LNode *p,ElemType e){ if(p==NULL) return false; LNode *s = (LNode *)malloc(sizeof(LNode)); if(s==NULL) //内存分配失败 return false; s->data = e; s->next = p->next; p->next = s; //将结点s保存数据元素e return true; } //在第i个位置插入元素e（带头结点） bool ListInsert(LinkList &L,int i,ElemType e){ if(inext = p->next; p->next = s; //将新结点连到p之后 s->data = p->data; //将p中的元素复制到s中 p->data = e; //p中元素覆盖为e return true; } 按位序删除 //按位序删除（带头结点） bool ListDelete(LinkList &L,int i,ElemType &e){ if(inext == NULL) return false; LNode *q = p->next; //令q指向被删除结点 e = q->data; //用e返回元素的值 p->next=q->next; //将*q结点从链中“断开” free(p); //释放结点的存储空间 return true; } 指点结点的删除

即将p后继结点的值赋给p，再将p的后继删除。

//删除指点结点p bool DeleteNode(LNode *p){ if(p==NULL) return false; LNode *q=p->next; //令q指向*p的后继结点 p->data=p->next->data; //和后继结点交换数据域 p->next=q->next; //将*q结点从链中“断开” free(q); //释放后继结点的存储空间 return true; } 单链表的查找按位查找 //按位查找，返回第i个元素(带头结点) LNode * GetElem(LinkList L,int i){ int j=1; LNode *p=p->next; if(i==0)//若获取的是第一个结点 return L; if(inext; //从第1个结点开始查找数据域为e的结点 while(p!=NULL && p->data!=e) p=p->next; return p; //若找到则返回结点指针，否则返回NULL } 表的长度 //表的长度 int length(LinkList L){ int len=0; LNode *p =L; while(p->next!=NULL){ p = p->next; len++; } return len; } 单链表的建立尾插法

//尾插法 bool List_TailInsert(LinkList &L){ int x; L = (LinkList)malloc(sizeof(LNode)); LNode *s,*r=L; //r为表尾指针 scanf("%d",&x); //输入结点的值 while(x!=9999){ //输入9999则结束输入 //在r结点之后插入元素x s = (LNode*)malloc(sizeof(LNode)); s->data = x; r->next = s; r=s; //确保r为表尾指针 scanf("%d",&x); } r->next=NULL; return L; } 头插法

即每次插入一个元素都插入到单链表头结点后面。

LinkList List_HeadInsert(LinkList &L){ LNode *s; int x; L = (LinkList)malloc(sizeof(LNode));//创建头结点 scanf("%d",&x); //输入结点的值 while(x!=9999){ //输入9999则结束输入 //在头结点之后插入元素x s = (LNode*)malloc(sizeof(LNode)); s->data = x; s->next = L->next; L->next = s; scanf("%d",&x); } return L; }

4.双链表

与单链表相比，多了个前驱指针，可以逆向检索

#include #include #define ElemType int typedef struct DNode{ ElemType data; struct DNode *prior,*next; }DNode,*DLinklist; //初始化双链表(带头结点) bool InitDLinkList(DLinklist &L){ L = (DNode *)malloc(sizeof(DNode)); if(L==NULL) //内存不足，分配失败 return false; L->prior = NULL; //头结点的prior永远指向NULL L->next = NULL; return true; } int main(){ //初始化双链表 DLinklist L; InitDLinkList(L); return 0; } 插入 //在p结点后插入s结点 bool InsertNextDNode(DNode *p,DNode *s){ if(p==NULL || s==NULL) return false; s->next = p->next; if(p->next != NULL) //如果p结点有后继结点 p->next->prior = s; s->prior = p; p->next = s; return true; } 删除 //删除p结点的后继结点 bool DeleteNextDNode(DNode *p){ if(p==NULL) return false; DNode *q = p->next; //找到p的后继结点q if(q==NULL) //p没有后继结点q return false; p->next = q->next; if(q->next!=NULL) //q结点不是最后一个结点 q->next->prior = p; free(q); //释放结点空间 return true; } 5.循环链表循环单链表

将表尾指针指向头结点

#include #include #define ElemType int typedef struct LNode{ //定义单链表结点类型 ElemType data; //每个节点存放一个数据元素 struct LNode *next; //指针指向下一个节点 }LNode,*LinkList; //判断循环单链表是否为空 bool Empty( LinkList L) { if(L->next == L) return true; else return false; } //判断结点p是否为循环单链表的表尾结点 bool isTail( LinkList L, LNode *p){ if (p->next==L) return true; else return false; } //初始化一个循环单链表 bool InitList(LinkList &L) { L = (LNode *) malloc(sizeof( LNode) );//分配一个头结点 if (L==NULL) //内存不足，分配失败 return false; L->next = L; //头结点next指向头结点 return true; } 循环双链表

双链表: 表头结点的prior指向NULL;

表尾结点的next指向NULL循环双链表: 表头结点的prior指向表尾结点;

表尾结点的next指向头结点

初始化 #include #include #define ElemType int typedef struct DNode{ ElemType data; struct DNode *prior ,*next;}DNode,*DLinklist; //初始化空的循环双链表 bool InitDLinkList(DLinklist &L){ L = ( DNode *) malloc(sizeof( DNode) );//分配一个头结点 if (L==NULL) //内存不足，分配失败 return false; L->prior = L; //头结点的prior指向头结点 L->next = L; //头结点的next指向头结点 return true; } //判断循环双链表是否为空 bool Empty(DLinklist L) { if(L->next == L) return true; else return false; } //判断结点p是否为循环链表的表尾结点 bool isTail(DLinklist L,DNode *p){ if( p->next==L) return true; else return false; } void testDLinkList() { //初始化循环双链表 DLinklist L; InitDLinkList(L); // ...后续代码... } 与双链表基本操作的不同

在p结点后插入新结点、删除p结点后面的结点时不用考虑p后继结点是否为空的问题

删除

//删除p结点的后继结点 bool DeleteNextDNode(DNode *p){ if(p==NULL) return false; DNode *q = p->next; //找到p的后继结点q //注释的内容为双链表所需进行的条件判断 //if(q==NULL) //p没有后继结点q // return false; p->next = q->next; //if(q->next!=NULL) //q结点不是最后一个结点 // q->next->prior = p; free(q); //释放结点空间 return true; }

插入

//在p结点后插入s结点 bool InsertNextDNode(DNode *p,DNode *s){ if(p==NULL || s==NULL) return false; s->next = p->next; //注释的内容为双链表所需进行的条件判断 // if(p->next != NULL) //如果p结点有后继结点 // p->next->prior = s; s->prior = p; p->next = s; return true; } 6.静态链表

单链表:各个结点在内存中随机存储。静态链表:分配一整片连续的内存空间，各个结点集中存储。用数组的方式实现的链表。

#define MaxSize //静态链表的最大长度 typedef struct { //静态链表结构类型的定义 int data; //存储数据元素 int next; //下一个元素的数组下标 }SLinkList[MaxSize];

基本操作的实现逻辑

初始化静态链表: 把a[o] 的next 设为1 把其他结点的next设为一个特殊值用来表示结点空闲，如-2

查找: 从头结点出发挨个往后遍历结点

插入位序为i的结点: ①找到一个空的结点，存入数据元素

②从头结点出发找到位序为i-1的结点

③修改新结点的next ④修改i-1号结点的next

删除某个结点: ①从头结点出发找到前驱结点

②修改前驱结点的游标 ③被删除结点next设置一个特殊值以表示已经被删除

7.顺序表和链表的异同逻辑结构

都属于线性表，都是线性结构

存储结构

顺序表（顺序存储）：

优点:支持随机存取、存储密度高缺点:大片连续空间分配不方便,改变容量不方便

链表（链式存储）：

优点:离散的小空间分配方便、改变容量方便缺点:不支持随机存取、存储密度低

基本操作

创销、增删改查

创建

顺序表：

需要预分配大片连续空间。若分配空间过小，则之后不方便拓展容量;若分配空间过大，则浪费内存资源链表：

只需分配一个头结点（也可以不要头结点，只声明一个头指针），之后方便拓展

销毁

顺序表：

静态分配:静态数组 -->系统自动回收空间动态分配:动态数组( malloc、 free) --> 需要手动free链表：

依次删除各个结点（ free)

增删

顺序表：

插入/删除元素要将后续元素都后移/前移链表：

插入/删除元素只需修改指针即可

查

顺序表：

按位查找:O(1) 按值查找:O(n)若表内元素有序，可在O( $\log_{2}n$ )时间内找到链表：

按位查找:O(n) 按值查找:O(n)

综上所述

表长难以预估、经常要增加/删除元素—―链表表长可预估、查询（搜索）操作较多――顺序表

开放式问题的答题思路:

问题:请描述顺序表和链表的bla bla bla.... 交规线性表时,用顺序表还是链表好?(6分) 一一顺序表和链表的逻辑结构都是线性结构，都属于线性表。但是二者的存储结构不同，顺序表采用顺序存储...(特点，带来的优点缺点);链表采用链式存储...(特点、导致的优缺点）。由于采用不同的存储方式实现，因此基本操作的实现效率也不同。当初始化时...;当插入一个数据元素时...;当删除一个数据元素时...;当查找一个数需元素时...

【本文地址】

数据结构

数据结构

今日新闻

推荐新闻