家庭网站建设,找人做淘宝网站,申请域名的方法和流程,国内好用的搜索引擎线性表 数据结构之线性表一、基本定义1、线性表的概念、定义#xff0c;特点#xff0c;线性表抽象数据类型定义2、其他 二、线性表的顺序表示与实现1、静态顺序表2、静态表 三、线性表的链式表示与实现1、单链表包含了指针的知识#xff0c;是第一部分的重难点2、特点3、代… 线性表 数据结构之线性表一、基本定义1、线性表的概念、定义特点线性表抽象数据类型定义2、其他 二、线性表的顺序表示与实现1、静态顺序表2、静态表 三、线性表的链式表示与实现1、单链表包含了指针的知识是第一部分的重难点2、特点3、代码实现 数据结构之线性表
一、基本定义
1、线性表的概念、定义特点线性表抽象数据类型定义
1、定义具有相同数据类型的nn≥0个数据元素的有限序列(线性表是逻辑结构)
2、特点个数有限、顺序性、每个元素所占存储空间相同2、其他
顺序表有序的时候折半查找时间复杂度为O(log2(n))
线性表顺序存储结构是一个随机存取的存储结构(随机存取指的是读写)二、线性表的顺序表示与实现
1、静态顺序表
#include bits/stdc.h
#define MaxSize 10
#define ElemType intusing namespace std;// 静态顺序表
typedef struct {ElemType data[MaxSize];int length;
}Sqlist;// Initiate List
void InitList(Sqlist L) {for(int i 0; i MaxSize; i)L.data[i] 0;L.length 0;
}int main() {Sqlist L;InitList(L);
}2、静态表
静态表是动态存储的其实简单来讲就是动态数组后面的栈和队列就是以此为基础的// 动态顺序表
#include bits/stdc.h
#include stdlib.h#define InitSize 10
#define AddSize 10
#define ElemType intusing namespace std;typedef struct {ElemType *data; int MaxSize;int length;
}SeqList;// 初始化顺序表
void InitList(SeqList L) {L.data (int *) malloc(InitSize * sizeof(ElemType));L.MaxSize InitSize;L.length 0;
}// 动态增加顺序表长度
void IncreaseSize(SeqList L, int len) {ElemType *p L.data;L.data (int *) malloc((L.MaxSize len) * sizeof(ElemType));for(int i 0; i L.length; i)L.data[i] p[i];L.MaxSize len;free(p);
}// 增, O(n)
bool ListInsert(SeqList L, int i, ElemType e) {if (i 1 || i L.length 1)return false;if (L.length L.MaxSize)IncreaseSize(L, AddSize);for(int j L.length; j i; j--)L.data[j] L.data[j-1];L.data[i-1] e;L.length;return true;
}// 删, O(n)
bool ListDelete(SeqList L, int i, ElemType e) {if(i L.length || i 1)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;
}// 按位查找, O(1)
ElemType GetElem(SeqList L, int i) {if (i L.length || i 1)return 0;return L.data[i-1];
}// 按值查找, O(n)
int LocateElem(SeqList L, ElemType e) {for (int i 0; i L.length; i){if (L.data[i] e)return i 1;}return 0; // 查找失败
} void PrintAll(SeqList L) {for (int i 0; i L.length; i)coutL.data[i] ;coutendl;
}// 测试信息
//int main() {
// SeqList L;
// InitList(L);
// ListInsert(L, 1, 1);
// ListInsert(L, 2, 2);
// ListInsert(L, 3, 3);
// PrintAll(L);
// int e -1;
// ListDelete(L, 2, e);
// cout删除的数为:eendl;
// cout3在第LocateElem(L, 3)个位置endl;
// PrintAll(L);
// return 0;
//}三、线性表的链式表示与实现
1、单链表包含了指针的知识是第一部分的重难点
2、特点
单链表便于插入删除但是查找需要遍历整个链表才可以3、代码实现
#include bits/stdc.h#define ElemType intusing namespace std;typedef struct LNode {ElemType data;LNode *next;
}LNode, *LinkList; 初始化:不带头指针的单链表
//bool InitList(LinkList L) {
// L NULL;
// return true;
//}// 初始化: 带头指针的单链表
// LinkList和LNode * 其实代指一样只是前面强调为链表后面强调为一个节点
bool InitList(LinkList L) {L (LNode *) malloc(sizeof(LNode));if (L NULL)return false;L-next NULL;return true;
}// 按位查找, 返回第i个元素
LNode *GetElem(LinkList L, int i) {if (i 0)return NULL;// 如果i 0, 返回的是头结点 LNode *p L;int j 0;while(p ! NULL j i) {p p - next;j;}return p;
}// 按值查找
LNode *LocateElem(LinkList L, ElemType e) {LNode *p L - next;while (p ! NULL p - data ! e)p p - next;return p;
} // 指定节点后插操作
bool InsertNextNode(LNode *p, ElemType e) {if (p NULL)return false;LNode *s (LNode *) malloc(sizeof(LNode));s - data e;s - next p - next;p - next s;return true;
}// 指定节点的前插操作
bool InsertBeforeNode(LNode *p, ElemType e) {if (p NULL)return false;LNode *s (LNode *) malloc(sizeof(LNode));s - next p - next;p - next s;// 换一下数据即可, 复杂度为O(1) s - data p - data;p - data e;return true;
}// 按照位序插入, O(n)
bool ListInsert(LinkList L, int i, ElemType e) {// 找到要插入位置的前一個LNode *p GetElem(L, i - 1); if (p NULL)return false;// 下面全部代码可以换成// return InsertNextNode(p, e); LNode *s (LNode *) malloc(sizeof(LNode));s - data e;s - next p - next;p - next s;return true;
}// 按位序删除, O(n)
bool ListDelete(LinkList L, int i, ElemType e) {LNode *p GetElem(L, i - 1);if (p NULL)return false;LNode *q p - next;e q - data;p - next q - next;free(q);return true;
}// 求表的长度
int Length(LinkList L) {int len 0;LNode *p L;while(p - next ! NULL){p p- next;len;}return len;
}// 建立单链表(尾插法)
LinkList List_TailInsert(LinkList L) {ElemType input;L (LinkList) malloc(sizeof(LNode));L - next NULL;LNode *r L;cininput;while(input ! -1) {LNode *s (LNode *) malloc(sizeof(LNode));s - data input;s - next r - next;r - next s;r r - next;cininput;}return L;
}// 建立单链表(头插法)
LinkList List_HeadInsert(LinkList L) {L (LinkList) malloc(sizeof(LNode));L - next NULL;ElemType input;cininput;while(input ! -1) {LNode *s (LNode *) malloc(sizeof(LNode));s - data input;s - next L - next;L - next s;cininput;}return L;
}// 链表逆置
LinkList ReverseList(LinkList L) {if(L - next NULL || L - next - next NULL)return L;LNode *p L - next, *s;while(p - next ! NULL) {// 刪除了后面节点 s p - next;p - next s - next;// 头插法s - next L - next;L - next s;}
}// 打印所有
bool PrintAll(LinkList L) {LNode *p L;while(p - next ! NULL) {p p - next;coutp - data ;}coutendl;
} // 测试用
int main() {LinkList L;int e;LNode *p;// 输入1, 2, 3, -1 List_TailInsert(L);PrintAll(L); // 1, 2, 3ListInsert(L, 3, 4);p LocateElem(L, 2);coutp - dataendl; // 2InsertBeforeNode(p, 5);PrintAll(L); // 1, 5, 2, 4, 3ListDelete(L, 1, e);couteendl; // 1PrintAll(L); // 5, 2, 4, 3ReverseList(L); // 3, 4, 2, 5PrintAll(L);coutLength(L); // 4
}
