- 线性表的基本概念与实现
- 顺序表和链表的比较
- 顺序表的结构体定义和基本操作
- 链表的结构体定义和基本操作
线性表的基本概念与实现
- 线性表
- 定义：线性表是具有相同特性数据元素的一个有序
序列。所包含的元素个数叫做线性表的长度 - 逻辑特征：集合中必须存在唯一一个“第一个元素”
集合中必须存在唯一一个“最后一个元素”
除最后一个元素外，其他数据元素均有唯一的“后继”
除第一个元素外，其他元素均有唯一的“前驱” - 线性表存储结构：
顺序表-随机访问、占用连续的存储空间、静态分配
image.png
链表-不支持随机访问、节点的存储空间利用率较顺序表稍低一点、动态分配，线性表5中形式：
单链表：
带头节点：head 指向头结点，头结点不包含任何信息，头结点的下一个节点开始存储数据信息。头结点head 始终不等于NULL,head->next = NULL 时，链表为空
WeChat17ea89e49aea124a8f7a228892a24352.png
不带头节点：head 指针指向开始节点
双链表
是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点
image.png
循环单链表
将单链表的最后一个指针域指向链表中的第一个结点
image.png
循环双链表
和循环单链表类似，循环双链表的构造源自双链表，即将终端结点的next指针指向链表中的第一个结点，将链表中第一个结点的prior指针指向终端节点
image.png
静态链表
静态链表借助一维数组表示
image.png
对应的链表表示
image.png
顺序表和链表的比较
- 基于空间的比较：
- 存储分配方式：顺序表的存储空间使一次性分配的，链表的存储空间是多次分配的
- 存储密度：顺序表的存储密度=1，链表的存储密度<1
- 基于时间的比较：
- 顺序表可以随机存取，也可以顺序存取；链表只能顺序存取
- 插入、删除时移动的元素个数
顺序表平均需要移动一般的元素，链表不需要移动元素
顺序表的结构体定义和基本操作
- 结构体定义
#define maxsize 100
struct SqList{
int data[maxsize];// 存放顺序表元素的数组
int lenght;//存放顺序表的长度
};
// 简化写法
int A[maxsize];
int n;
- 基本操作
//初始化
void initList(SqList &l){
l.lenght = 0;
}
// 获取指定位置的值
int getElem(SqList L,int p,int &e){
if(p<0 || p>L.lenght){
return 0;
}
e = L.data[p];
return 1;
}
// 查找指定元素，如果存在返回所在的位置
int findElem(SqList L,int e){
int i = 0;
for (; i<L.lenght; i++) {
if (e == L.data[i]) {
return i;
}
}
return -1;
}
// 插入元素
int insertElem(SqList &L,int p,int e){
int i;
if (p<0 || p>L.lenght || L.lenght == maxsize) {
return 0;
}
for (i = L.lenght-1; i>=p; i--) {
L.data[i+1] = L.data[i];
}
L.data[p] = e;
++(L.lenght);
return 1;
}
// 删除元素
int deleteElem(SqList &L,int p,int &e){
int i;
if(p<0 || p>L.lenght){
return 0;
}
e = L.data[p];
for (i=p; i<L.lenght-1; i++) {
L.data[i] = L.data[i+1];
}
--L.lenght;
return 1;
}
链表的结构体定义和基本操作
- 结构体定义
单链表的结点定义
typedef struct LNode{
int data; // data 中存放结点的数据域
struct LNode *next;//指向后继结点的指针
}LNode;
image.png
- 基本操作
初始化操作
// 尾插法--创建链表
void creatListR(LNode *&C,int a[], int n){// 要改变的变量用引用类型
LNode *s,*r;
int i;
C = (LNode *)malloc(sizeof(LNode));
C->next = NULL;
r = C;
for (int i = 0;i<n ; i++) {
s = (LNode *)malloc(sizeof(LNode));
s->data = a[i];
r->next = s;
r = r->next;
}
r->next = NULL;
}
// 头插法--创建链表
void creatlistRH(LNode *&C,int a[], int n){
LNode *s;
int i;
C = (LNode *)malloc(sizeof(LNode));
C->next = NULL;
for (int i = 0; i<n; i++) {
s = (LNode *)malloc(sizeof(LNode));
s -> data = a[i];
s->next = C->next;
C->next = s;
}
}
删除操作
image.png
image.png
// 查找并删除
int findAndDelete(LNode *C,int x){
LNode *p,*q;
p = C;
// 查找部分
while (p->next != NULL) {
if (p->next->data == x) {
break;
}
p = p->next;
}
if (p->next == NULL) { // 没找到
return 0;
}
//执行删除操作
q = p->next;
p->next = q->next;
free(q);
return 1;
}
双链表的结点定义
typedef struct DLNode{
int data; // data 中存放结点的数据域
struct DLNode *prior; //指向前驱结点的指针
struct DLNode *next; //指向后继结点的指针
}DLNode;
image.png
- 基本操作
初始化和查找
// 尾插法创建双链表
void creatDlistR(DLNode *&L,int a[],int n){
DLNode *s,*r;
int i;
L = (DLNode *) malloc(sizeof(DLNode));
L->prior = NULL;
L->next = NULL;
r = L;
for (i = 0;i<n; i++) {
s = (DLNode *)malloc(sizeof(DLNode));
s->data = a[i];
r->next = s;
s->prior = r;
r = s;
}
r->next = NULL;
}
// 查找结点的算法
DLNode * findNode(DLNode *C,int x){
DLNode *p = C->next;
while (p != NULL) {
if (p->data == x) {
break
}
p = p->next;
}
return p;
}
插入操作
1. B ->next = A->next
2. B->prior = A;
3. A->next = B;
4. C->prior = B;
image.png
image.png
image.png
image.png
删除操作
删除操作与插入操作的过程相反,删除A结点的后继结点
B = A->next
A->next = B->next;
B->next->prior= A;
free(B)
结语：顺序表和单链表都是数据结构中需要经常使用的结构体，需要好好好好的掌握和理解
