数据结构与算法整理复习（一）：数据结构概念与线性表

目录

第一章：绪论

1.1 数据结构的基本概念

1.2 算法与算法评价

第二章：线性表

2.1 线性表的定义和基本操作

2.2 线性表的顺序表示（顺序表）

 应用题

2.3 线性表的链式表达（链表）

2.3.1 单链表

2.3.2 双链表

 2.3.3 循环链表

2.3.4 静态链表

2.3.5 顺序表与链表的比较 

---

第一章：绪论

1.1 数据结构的基本概念

可以用“抽象数据类型（ADT）”定义一个完整的数据结构

抽象数据类型（ADT）为一个数学模型以及其定义在数学模型上的一组操作。包含（数据对象、数据关系、以及其基本操作集），故为一个完整的数据结构。

数据的逻辑结构独立于存储结构，但数据的存储结构不能独立于其逻辑结构

1.2 算法与算法评价

好算法应该达到的目标：正确性、可读性、健壮性、高效率与低存储要求。

空间复杂度O(1)：辅助空间的大小与问题规模n无关

时间复杂度O(n^2)：执行时间与n^2成正比。

for(int i=0;i<n;i++){for(int j=0;j<m;j++){printf("111");}
}

上诉代码是时间复杂度为O(nm)。

#include <stdio.h>// 递推方式求解斐波那契数列
long long fibonacci_iterative(int n) {if (n <= 0) return 0;if (n == 1) return 1;long long a = 0, b = 1, c;for (int i = 2; i <= n; i++) {c = a + b;a = b;b = c;}return b;
}// 递归方式求解斐波那契数列
long long fibonacci_recursive(int n) {if (n <= 0) return 0;if (n == 1) return 1;return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2);
}int main() {int n;printf("请输入一个非负整数: ");scanf("%d", &n);printf("斐波那契数列第%d项是: %lld\n", n, fibonacci_iterative(n));printf("斐波那契数列第%d项是: %lld\n", n, fibonacci_recursive(n));return 0;
}

第二章：线性表

2.1 线性表的定义和基本操作

每一个元素有且只有一个前驱和后继。

线性表的特性：

• 表中元素个数有限
• 元素具有逻辑上的顺序性，有先后顺序
• 表中元素都是你数据元素，每个数据元素可以包含多个数据项
• 表中元素的数据类型都相同（每个元素占相同大小的空间）
• 元素具有抽象性

InitList(List &L)//初始化表
Length(List L)//求表长
LocateElem(List L,ElemType e)//按值查找，返回位序
GetElem(List L,int i)//按位查找
ListInsert(List &L,int i, ElemType e)//插入操作，在表L的第i位序插入元素e
ListDelete(List &L,int i,ElemType &e)//删除第i位序的元素，并用e返回删除元素
PrintList(List L)//输出操作
Empty(List L)//判空操作
DestroyList(List &L)//销毁线性表

2.2 线性表的顺序表示（顺序表）

逻辑顺序与其物理顺序相同

顺序表的任意一个数据元素都可以随机存取。

顺序存储结构是一种随机存取的存储结构。

优点：

• 支持随机访问O(1)
• 存储密度高

缺点：

• 元素的插入（平均需要n/2次操作）和删除（平均需要(n-1)/2次操作）需要移动大量元素
• 分配需要一段连续的存储空间，灵活性较差

静态分配顺序表代码如下：

#define MAX_SIZE 100//静态顺序表定义
typedef struct{int data[MAX_SIZE];int length;
}SqList;//线性表初始化
InitList(SqList &L){for(int i=0;i<L.length;i++){L.data[i]=0;}L.length = 0;
}//插入操作
bool ListInsert(SqList &L, int i, int e){if(i<1||i>L.length+1) return false;if(L.length >= MAX_SIZE) return flasefor(int j = L.length;j>=i;j--){L.data[j] = L.data[j-1];}L.data[i-1] = e;L.length++;return true;
}
//静态线性表删除操作
bool ListDelete(SqList &L, int i,int &e){if(i<1||i>L.length) return false;if(L.length<=0) return false;e = L.data[i-1]for(int j=i;j<L.length;j++){L.data[j-1]=L.data[j];}L.length--;return true;
}
//按值查找
int LocateElem(SqList L, int e){for(int i=0;i<L.length;i++){if(L.data[i]==e){return i+1;//返回位序}}return -1;//查找失败
}

动态分配顺序表代码如下：

//动态顺序表定义
typedef struct{int *data;int length;int max_size;
}SqList;//线性表初始化
InitList(SqList &L){L.data = (int *)malloc(sizeof(int)*INIT_SIZE)L.length = 0;L.max_size = INIT_SIZE;
}
//线性表插入
bool ListInsert(SqList &L,int i, int e){if(i<1||i>L.length+1) return false;if(L.length>=L.max_size) return false;for(int j=L.length;j>=i;j--){L.data[j] = L.data[j-1];}L.data[i-1] = e;L.length++;return true;
}
//动态线性表删除操作
bool ListDelete(SqList &L, int i,int &e){if(i<1||i>L.length) return false;if(L.length<=0) return false;e = L.data[i-1]for(int j=i;j<L.length;j++){L.data[j-1]=L.data[j];}L.length--;return true;
}
//按值查找
int LocateElem(SqList L, int e){for(int i=0;i<L.length;i++){if(L.data[i]==e){return i+1;//返回位序}}return -1;//查找失败
}

 应用题

1. 原地逆置顺序表

void function(SqList &L){int temp;for(int i=0;i<L.length/2;i++){temp = L.data[i];L.data[i] = L.data[L.length-1-i];L.data[L.length-1-i] = L.data[i];}
}

2.删除所有值为e的元素，要求时间复杂度为O(n)，空间复杂度为O(1)

void function(SqList &L, int e){int pos = 0;for(int i=0;i<L.length;i++){if(L.data[i] != e){L.data[pos] = e;pos++;}}L.length = pos;
}

3. 有序顺序表中删除所有值重复的元素

bool function(SqList &L){if(L.length < 1) return false;int i=0;int j=1;for(j;j<L.length;j++){if(L.data[j]==L.data[i]) continue;i++;L.data[i] = L.data[j];}L.length = i+1;return true;
}

4. merge两个有序顺序表，并返回新的表

SqList mergeList(SqList L1, SqList L2, SqList &result){if(L1.length + L2.length > result.maxsize) return false;int i_L1 = 0,i_L2 = 0;int pos = 0;while(i_L1<L1.length && i_L2<L2.length){if(L1.data[i_L1]<=L2.data[i_L2]){result[pos] = L1.data[i_L1];pos++;i_L1++;}result[pos] = L2.data[i_L2];pos++;i_L2++;}while(i_L1<L1.length){result[pos] = L1.data[i_L1];pos++;i_L1++;}while(i_L2<L2.length){result[pos] = L2.data[i_L2];pos++;i_L2++;}result.length = pos;return result;
}

5. 顺序表循环左移p个单位

void reserve(SqList &L, int start, int end){int temp;for(int i = 0;i <= (start-end)/2; i++){temp = L.data[start + i];L.data[start + i] = L.data[end - i];L.data[end - i] = temp;}
}
void function(SqList &L, int p){reserve(L, 0, p-1);reserve(L, p, L.length-1);reserve(L, 0, L.length-1);
}

6. 求两个等长的升序顺序表L1、L2的并集的中位数

void fucntion(SqList L1, SqList L2){int mid_L1 = L1.data[L1.length/2];int mid_L2 = L2.data[L2.length/2];}

2.3 线性表的链式表达（链表）

2.3.1 单链表

定义与初始化

//单链表的定义
typedef struct LNode{ElemType data;LNode *next;
}LNode, *LinkList;//带头节点的初始化（仅需要初始化头节点）
bool InitList(LinkList &L){L = (LNode *)malloc(sizeof(LNode));L->next = NULL;return true;
}//不带头节点的初始化（仅需设定为NULL）
bool InitList(LinkList &L){L = NULL;return true;
}

单链表的相关操作 

//获取单链表长度
int Length(LinkList L){int length = 0;LNode *temp = L;while(temp->next != NULL){length++;temp = temp->next;}return length;//带头节点return length+1;//不带头节点
}//按位序号查找节点(带头节点)
LNode* GetElem(LinkList L, int i){if(i<1) return false;int pos = 0;LNode* temp = L;while(pos<i || temp->next!=NULL){pos++;temp = temp->next;}if(pos == i) return temp;return NULL;
}//按值查找节点(带头节点)
LNode* GetElem(LinkList L, ElemType e){LNode* temp = L->next;while(temp->data != e && temp!=NULL){temp = temp->next;}return temp;
}//在第i位序插入元素e
bool ListInsert(LinkList &L, int i, ElemType e){if(i<1) return false;int pos = 0;LNode* p = L;while(pos<i-1 && p!=NULL){pos++;p = p->next;}if(p == NULL) return false;LNode* temp = (LNode *)malloc(sizeof(LNode*));temp->data = e;temp->next = p->next;p->next = temp;
}//删除位序为i的元素并用e返回被删除元素的值
bool ListDelete(LinkList &L, int i, ElemType* e){int pos = 0;LNode* p = L;while(pos < i-1 && p != NULL){pos++;p = p->next;}if(p==NULL || p->next == NULL) return false;e = p->next->data;LNode* temp = p->next;p->next = temp->next;free(temp);return true;
}//头插法建立链表
LinkList ListHeadInsert(LinkList &L){if(L==NULL){L = (LNode*)malloc(sizeof(LNode*));//初始化头节点L->next = NULL;}int x;scanf("%d", &x)while(x!=999){LNode* p = (LNode *)malloc(sizeof(LNode*));p->data = x;p->next = L->next;L->next = p;scanf("%d", &x)}return L;
}//尾插法建立链表
LinkList ListHeadInsert(LinkList &L){if(L==NULL){L = (LNode*)malloc(sizeof(LNode*));//初始化头节点L->next = NULL;}LNode* p = L;int x;scanf("%d", &x)while(x!=999){LNode* temp = (LNode *)malloc(sizeof(LNode*));temp->data = x;p->next = temp;p = temp;scanf("%d", &x)}p->next = NULL;//注意！return L;
}

2.3.2 双链表

定义与初始化

//双链表定义
typedef struct DNode{struct DNode* prior;struct DNode* next;ElemType data;
}DNode, *DLinkList;//双链表初始化
void InitList(DLinkList &L){L = (DNode*)malloc(sizeof(DNode));L->prior = NULL;L->next = NULL;
}

双链表的操作 

//双链表的后继插入
bool ListInster_after(DLinkList &L, int i, ElemType e){if(i<1 || L==NULL) return false;DNode *p = L;int pos = 0;while(pos < i-1 && p!=NULL){p = p->next;pos++;}if(p == NULL) return false;DNode* temp = (DNode*)malloc(sizeof(DNode*));temp->data = e;temp->prior = p;temp->next = p->next;if(p->next != NULL){p->next->prior = temp;}p->next = temp;return true;
}//双链表的删除操作
bool ListDelete(DLinkList &L, int i){if(i<1 || L==NULL) return false;DNode *p = L;int pos = 0;while(pos < i && p!=NULL){p = p->next;pos++;}if(p == NULL) return false;p->prior->next = p->next;if(p->next!=NULL) p->next->prior = p->prior;free(p);
}

 2.3.3 循环链表

循环链表的定义与初始化

//单循环链表的定义
typedef struct LNode{struct LNode* next;ElemType data;
}LNode, *LinkList;//双循环链表的定义
typedef struct DNode{struct LNode *next, *prior;ElemType data;
}DNode, *DLinklist;//单循环链表的初始化
void InitList(LinkList &L){L = (LNode*)malloc(sizeof(LNode));if(L==NULL) return false;L->next = L;
}//双循环链表的初始化
void InitList(DLinkList &L){L = (DNode*)malloc(sizeof(DNode));if(L==NULL) return false;L->next = L;L->prior = L;
}

 循环链表的操作

//判断是否为空
bool Empty(LinkList L){return L->next == L;
}//判断是否为尾节点
bool is_Tail(LinkList L, LNode *p){return p->next == L;
}//插入和删除和之前一样，但是不需要进行边界的判空操作！

2.3.4 静态链表

2.3.5 顺序表与链表的比较 

逻辑结构：均为线性结构

存储结构：

顺序表为顺序存储，链表为链式存储

顺序表：

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

链表：

• 优点：离散的小空间，分配方便，改变容量方便
• 缺点：不可随机存取，存储密度低

操作方式：

• 按值查找：顺序表无序时，时间复杂度为O(n);顺序表有序时，时间复杂度为O(logn);链表始终为O(n)。
• 按位查找：顺序表为O(1)，链表为O(n)。
• 插入和删除：顺序表和链表均为O(n)，但是链表比顺序表快得多。（顺序表需要移动大量数据）

评价两种数据结构的方式：

1. 存储结构
2. 逻辑结构
3. 对应的相关运算效率比较
4. 得出结论……

注意 

•  链表节点内的存储单元地址为连续的
• 建立一个有序单链表的最低时间复杂度为O(nlogn)（数组排序最快为O(nlogn)，排序后建立链表为O(n)，综上为O(nlogn)）
• 需要分配大量空间，且删除和插入无需移动元素的线性表为：静态链表