数据结构|数据结构基本概念以及线性表的基本操作算法|链表|指针

数据结构

抽象数据类型（ADT）：数据对象、数据关系、基本操作
数据结构：

一、逻辑结构
（1）、线性结构：线性表、栈、队列、串
（2）、非线性结构：树、图

（1）、集合结构：集合
（2）、线性结构：1:1
（3）、树形结构：1：n
【数据结构|数据结构基本概念以及线性表的基本操作】（4）、图状结构或网状结构：M:N

二、存储结构（物理结构）：顺序存储结构、链式存储结构、索引存储结构、散列存储结构

三、数据的运算和实现

线性表基本概念

1、线性表是具有相同特性数据元素的一个有限序列。

2、逻辑特性：直接前驱、直接后继

3、存储结构：
（1）顺序存储结构：顺序表：随机访问特性、占用连续的存储空间。随机存储（也可以顺序存储）
（2）链式存储结构：链表：不支持随机访问、结点的存储空间利用率较低、动态分配。只能顺序存储

顺序表操作 1、初始化算法2.1：顺序表的初始化

#define MAXSIZE 100 typedef struct{ ElemType elem[MAXSIZE]; int length; }SqList; typedef struct{ ElemType *elem; int length; }SqList; //顺序表类型L.elem = (ElemType*)malloc(sizeof(ElemType)*MAXSIZE); //2.1 线性表L的初始化（参数用引用） Status InitList_Sq(SqList &L){//构造一个空的顺序表L L.elem = new ElemType[MAXSIZE]; //为顺序表分配空间 if(!L.elem) exit(OVERFLOW); //存储分配失败 L.length = 0; //空表长度为0 return OK; }

补充操作

//补充操作： //销毁线性表L void DestroyList(SqList &L){ if(L.elem) delete L.elem; //释放存储空间 } //清空线性表： void ClearList(SqList &L){ L.length = 0; //将线性表的长度置为零 } //求线性表L的长度 int GetLength(SqList L){ return (L.length); } //判断线性表L是否为空 int IsEmpty(SqList L){ if(L.length == 0) return 1; else return 0; }

2、取值算法2.2 顺序表的取值（根据位置i获取相应位置数据元素的内容）

//2.2顺序表的取值 int GetElem(SqList L, int i, ElemType &e){ if(i < 1 || i > L.length) return ERROR; //判断i是否合理 e = L.elem[i-1]; //第i-1的单元存储着第i个数据 return OK; }

3、查找算法2.3 顺序表的查找

//2.3顺序表的查找 int LocateElem(SqList L, ElemType e){ //在线性表L中查找值为e的数据元素，返回其序号（是第几号元素） for(i = 0; i < L.length; i++){ if(L.elem[i] == e) return i+1; //查找成功，返回序号 } return 0; //查找失败，返回 } //while 实现 int LocateElem(SqList L, ElemType e){ //在线性表L中查找值为e的数据元素，返回其序号（是第几个元素） i = 0; while(i < L.length && L.elem[i] != e) i++; if(i < L.length) return i+1; //查找成功，返回序号 return 0; //查找失败，返回0 }

ASL = （n+1)/2
o(n)

4、插入算法2.4 顺序表的插入

//算法2.4 顺序表的插入 //算法2.4 顺序表的插入 Status ListInsert_Sq(SqList &L, int i, ElemType e){ //在第i个位置插入,物理序号为i，逻辑位置为i-1 if(i<1 || i>L.length+1) return ERROR; //i值不合法 if(L.length == MAXSIZE) return ERROR; //当前存储空间已满 for(j = L.length-1; j >= i-1; j--) L.elem[j+1] = L.elem[j]; //插入位置及之后的元素后移 L.elem[i-1] = e; //将新元素e放入第i个位置 L.length++; //表长加一 return OK; }

E = n/2
O(n)

5、删除算法2.5 顺序表的删除

//算法2.5 顺序表的删除 Status ListDelete Sq(SqList &L, int i){ if((i<1)||(i>L.length)) return ERROR; //i值不合法 for(j = i; j <= L.length-1; j++) L.elem[j-1] = L.elem[j]; //被删除元素之后的元素前移 L.length--; return OK; }

E = （n-1）/2
O(n)

顺序表的操作算法分析时间复杂度 o(n)
空间复杂度 o(1)
链表操作单链表的操作 1、初始化
算法2.6 单链表的初始化（带头结点）

//算法2.6 单链表的初始化typedef struct LNode{ ElemType data; struct LNode *next; }LNode, *LinkList; LinkList L; LNode *p, *s; p = L; //p指向头结点 s = L->next; //s指向首元结点 p = p->next; //p指向下一结点Status InitList_L(LinkList &L){ L = new LNode; //生成新结点作为头结点，用头指针指向头结点 //或者是L = (LinkList) malloc (sizeof(LNode)); L->next = NULL; return OK; }

补充算法判断链表是否为空

//判断链表是否为空 int ListEmpty(LinkList L){//若L为空表，则返回1，否则返回0 if(L->next) //非空 return 0; else return 1; }

单链表的销毁：销毁即不存在

//单链表的销毁，从头开始，依次释放所有结点 Status DestroyList_L(LinkList &L){//销毁单链表L Lnode *p; //或 LinkList p; while(L){ p = L; L = L->next; delete p; } return OK; }

清空链表，链表仍然存在，但是表中无元素，成为空链表依次释放所有结点，将头结点指针域设置为空

//清空链表L Status ClearList(LinkList &L){//将L重置为空表 Lnode *p, *q; //或LinkList p,q p = L->next; while(p){//没到表尾 q = p->next; delete p; p = q; } L->next = NULL; //头结点指针域为空 return OK; }

求单链表L的表长

//求单链表L的表长 int ListLength_L(LinkList L){//返回L中数据元素的个数 LinkList p; p = L->next; //p指向第一个结点 int i = 0; while(p){//遍历单链表，统计结点数 i++; p = p->next; } return i; }

2、取值
算法2.7 单链表的取值

//算法 2.7单链表的取值 Status GetElem_L(LinkList L, int i, ElemType &e){//获取线性表L中的某个数据元素的内容，通过变量e返回 p = L->next; j = 1; //初始化 while(p && jnext; ++j; } if(!p || j>i) return ERROR; //第i个元素不存在 e = p->data; //取第i个元素 return OK; }

3、查找
算法2.8 单链表的按值查找

//算法2.8 单链表的查找 Lnode *LocateElem_L(LinkList L, Elemtype e){ //在线性表L中查找值为e的数据元素 //找到，则返回L中值为e的数据元素的地址，查找失败返回NULL p = L->next; while(p && p->data != e) p = p->next; return p; }

按值查找，返回位置序号

//按值查找-根据指定数据获取该数据位置序号 int LocateElem_L(LinkList L, Elemtype e){ //在线性表L中查找值为e的数据元素的位置序号 //返回L中值为e的数据元素的位置序号，查找失败返回0 p = L->next; j = 1; while(p && p->data != e){ p = p->next; j++; } if(p) return j; else return 0; }

4、插入
算法2.9 单链表的插入

//算法2.9 单链表的插入 Status ListInsert_L(LinkList &L, int i, ElemType e){ //在L中第i个元素之前插入数据元素e p = L； j = 0; while(p && j < i-1){ //寻找第i-1个结点，p指向i-1结点 p = p->next; ++j; } if(!p || j>i-1) return ERROR; //i大于表长+1或者小于1，插入位置非法 s = new LNode; s->data = https://www.it610.com/article/e; //生成新结点s, 将结点s的数据域置为e s->next = p->next; //将结点s插入L中 p->next = s; return OK; }

5、删除
算法2.10 单链表的删除

//算法2.10 单链表的删除 Status ListDelete_L(LinkList &L, int i, ElemType &e){ //将线性表L中第i个数据元素删除 p = L; j = 0; while(p->next && j < i-1){ p = p->next; ++j; //寻找第i个结点，并令其指向其前驱 } if(!(p->next) || j > i-1)return ERROR; //删除位置不合理 q = p->next; //临时保存被删除结点的地址以备释放 p->next = q->next; //改变删除结点前驱结点的指针域 e = q->data; //保存删除结点的数据域 delete q; //释放删除结点的空间return OK }

6、创建单链表
算法2.11 前插法创建单链表

//算法2.11 创建单链表：头插法-元素插入在链表头部 void CreatList_H(LinkList &L, int n){ L = new LNode; L->next = NULL; //先建立一个带头结点的空链表 for(i = n; i > 0; --i) { p = new LNode; //生成新结点 p = (LNode*)malloc(sizeof(LNode)); cin >> p->data; //输入元素值 scanf(&p->data); p->next = L->next; //插入到表头 L->next = p; } }

算法2.12 后插法创建单链表

//算法2.12 建立单链表：尾插法-元素插入在链表尾部 void CreatList_R(LinkList &L, int n){ //正位序输入n个元素的值，建立带表头结点的单链表L L = new LNode; L->next = NULL; r = L; //尾指针r指向头结点 for(i = 0; i < n; ++i){ p = new LNode; cin >> p->data; //生成新结点，输入元素值 p->next = NULL; r->next = p; //插入到表尾 r = p; //r指向新的尾结点 } }

循环链表尾指针表示循环链表
带尾指针循环链表的合并

//带尾指针循环链表的合并 LinkList Connect(LinkList Ta, LinkList Tb){ //假设Ta、Tb都是非空的单循环链表 p = Ta->next; //p存表头结点 Ta->next = Tb->next->next; //Tb表头连接Ta表尾 delete Tb->next; //释放Tb表头结点或者 free(Tb->next); Tb->next = p; //修改指针 return Tb; }

双向链表双向链表的结构定义

//双向链表的结构定义 typedef struct DuLNode{ Elemtype data; struct DuLNode *prior, *next; }DuLNode, *DuLinkList

算法2.13 双向链表的插入

//算法2.13 双向链表的插入 void ListInsert_DuL(DuLinkList &L, int i, ElemType e){ //在带头结点的双向循环链表L中的第i个位置之前插入元素e if(!(p = GetElemP_DuL(L, i))) return ERROR; //在L中确认第i个元素的位置指针p s = new DuLNode; s->data = https://www.it610.com/article/e; s->prior = p->prior; p->prior->next = s; s->next = p; p->prior = s; return OK; }

算法2.14 双向链表的删除

//算法2.14 双向链表的删除 void ListDelete_DuL(DuLink &L, int i, ElemType &e){ //删除带头结点的双向循环链表L的第i个元素，并用e返回 if(!(p = GetElemP_DuL(L, i)))return ERROR; e = p->data; p->prior->next = p->next; p->next->prior = p->prior; free(p); //或者是 delete p; return OK; }