启航网站管理系统,网站域名选择,关于信用体系建设的网站,一键优化表格目录
第一章#xff1a;绪论
1.1 数据结构的基本概念
1.2 算法与算法评价
第二章#xff1a;线性表
2.1 线性表的定义和基本操作
2.2 线性表的顺序表示#xff08;顺序表#xff09; 应用题
2.3 线性表的链式表达#xff08;链表#xff09;
2.3.1 单链表
2.3.2…目录
第一章绪论
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 i0;in;i){for(int j0;jm;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 i0;iL.length;i){L.data[i]0;}L.length 0;
}//插入操作
bool ListInsert(SqList L, int i, int e){if(i1||iL.length1) return false;if(L.length MAX_SIZE) return flasefor(int j L.length;ji;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(i1||iL.length) return false;if(L.length0) return false;e L.data[i-1]for(int ji;jL.length;j){L.data[j-1]L.data[j];}L.length--;return true;
}
//按值查找
int LocateElem(SqList L, int e){for(int i0;iL.length;i){if(L.data[i]e){return i1;//返回位序}}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(i1||iL.length1) return false;if(L.lengthL.max_size) return false;for(int jL.length;ji;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(i1||iL.length) return false;if(L.length0) return false;e L.data[i-1]for(int ji;jL.length;j){L.data[j-1]L.data[j];}L.length--;return true;
}
//按值查找
int LocateElem(SqList L, int e){for(int i0;iL.length;i){if(L.data[i]e){return i1;//返回位序}}return -1;//查找失败
} 应用题
1. 原地逆置顺序表
void function(SqList L){int temp;for(int i0;iL.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 i0;iL.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 i0;int j1;for(j;jL.length;j){if(L.data[j]L.data[i]) continue;i;L.data[i] L.data[j];}L.length i1;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_L1L1.length i_L2L2.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_L1L1.length){result[pos] L1.data[i_L1];pos;i_L1;}while(i_L2L2.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 length1;//不带头节点
}//按位序号查找节点(带头节点)
LNode* GetElem(LinkList L, int i){if(i1) return false;int pos 0;LNode* temp L;while(posi || 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(i1) return false;int pos 0;LNode* p L;while(posi-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(pNULL || 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(LNULL){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(LNULL){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(i1 || LNULL) 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(i1 || LNULL) 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(LNULL) return false;L-next L;
}//双循环链表的初始化
void InitList(DLinkList L){L (DNode*)malloc(sizeof(DNode));if(LNULL) 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)但是链表比顺序表快得多。顺序表需要移动大量数据 评价两种数据结构的方式 存储结构逻辑结构对应的相关运算效率比较得出结论…… 注意 链表节点内的存储单元地址为连续的建立一个有序单链表的最低时间复杂度为O(nlogn)数组排序最快为O(nlogn)排序后建立链表为O(n)综上为O(nlogn)需要分配大量空间且删除和插入无需移动元素的线性表为静态链表
