#数据结构（一）
线性表
- 两者都属于线性表
- 线性表：逻辑结构------必连续
- 物理结构------不一定连续
- 顺序表的物理结构 -----连续 ，链表的物理结构 ----不连续
- 顺序表的本质是数组，数组是一块地址连续的空间。而链表只是像细线一样，将不同地址的节点串起来。（通过next指针实现）
- 若需要经常头删，链表更合适
- 顺序表可以通过下标，随机访问
一.顺序表
是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
代码实现
1初始化：
在声明线性表的顺序存储结构，定义一个数组来存储顺序表的所有元素，还定义一个整形变量size来存储顺序表的实际长度
#include <stdio.h>
typedef int datatype;//定义类型int,别名为datatype
#define M 100
typedef struct{
datatype data[M];
int size;
} seqlist;2 创造顺序表
传参一个结构体类型的指针，一个数组用于赋值，数组长度
int Creatlist(seqlist* p, datatype a[], int n) {//创造顺序表
if (n > M) {
printf_s("顺序表空间不够");
return 0;
}
for (int i = 0; i < n; i++) {
p->data[i] = a[i];
p->size = n;
}
return 1;
}3 判断是否为空
int Empty(seqlist* p) {//判断是不是空的
if (p->size == 0) return 1;
else return 0;
}4遍历输出
void Printlist(seqlist* p) {//遍历输出
for (int i = 0; i < p->size; i++) {
printf_s("%d ", p->data[i]);
}
printf_s("\n");
}5 查找索引位置
传入结构体指针，数据，再进行遍历
int Locate(seqlist* p,datatype x) {//查找这个数在第几个位置
for (int i = 0; i < p->size; i++) {
if (p->data[i] == x) {
return i + 1;
}
}
return 0;
}6 删除
删除固定索引位置的元素，需判断索引位置
int Delect(seqlist* p, int i) {//i是第几个数从：1开始到，删除
if (i<1 || i>p->size) {
printf_s("删除失败");
return 0;
}
if (p->size == 0)return 0;
//*x = p->data[i - 1];
for (int j = i; j < p->size; j++) {
p->data[j] = p->data[j + 1];
}
p->size -= 1;
return 1;
}7 在固定位置插入
在固定索引位置插入，需进行判断索引是否存在
int Insert(seqlist* p, int i, datatype x) {//i是第几个位置，数据x插入
if (i<1 || i>p->size) { printf_s("位置错误，插入失败"); return 0; }
if (p->size > M) { printf_s("上溢错误，插入失败"); return 0; }
//12345
for (int j = p->size; j >= i; j--) {
p->data[j] = p->data[j - 1];
}
p->data[i - 1] = x;
p->size++;
return 1;
}二 单链表
单链表是一种链式的存储结构，逻辑上相邻的元素的存储位置是通过指针连接的，因而每个节点的存储位置可以任意安排不需要相邻，所以插入删除操作只需要修改相关节点的指针域即可，
补充：单链表有带头结点和不带头结点两种类型。
通常每个链表带有一个头节点，并通过头结点的指针唯一标识该链表，称之为头指针，相应的指向首节点或者开始节点的指针称为首指针，指向尾节点的称为尾指针。
- 引入头结点的好处：①便于第一个结点的处理：增加头结点后，第一个结点的地址保存在头结
- 点的指针域中，则对链表的第一个元素的操作和其他元素相同，无需进行特殊处理。
- （若单链表不带头结点，则第一个结点无前驱结点，在其前插入结点和删除该结点操作复杂些。）
- ②便于空表和非空表的统一处理：增加头结点后，无论链表是否为空，头指针都是指向头结点的非空指针。
1 初始化
#include <stdio.h>
#include <malloc.h>
typedef int ElemType;
typedef struct LNode {
ElemType data;//数值域
struct LNode *next;//指针域
} LinkNode;2 头插法创建单链表
头插法的核心点是一直在头节点的后面添加元素，导致单链表是倒置的。
void CreatHeadMethod(LinkNode *&L, ElemType arr[], int len) {//传入链表，数组，数组长度
LinkNode *s;//创建一个结构体指针节点（插入节点）
L = (LinkNode *) malloc(sizeof(LinkNode));//为头节点开辟空间
L->next = NULL;//头节点的指针域初始化为空
for (int i = 0; i < len; i++) {
s = (LinkNode *) malloc(sizeof(LinkNode));//为插入节点开辟空间
s->data = arr[i];//数值域赋值
s->next = L->next;
L->next = s;//指针域连接
}
}3 尾插法创建单链表
存在一个工具指针一直指向最后的节点，便于在最后添加元素。
元素添加完向后赋值。
void CreatTailMethod(LinkNode *&L, ElemType arr[], int len) {
LinkNode *s, *tail;//工作指针
L = (LinkNode *) malloc(sizeof(LinkNode));//头节点开辟空间
L->next = NULL;//头结点的初始化
tail = L;//初始化（头节点不可进行更改）
for (int i = 0; i < len; i++) {
s = (LinkNode *) malloc(sizeof(LinkNode));
s->data = arr[i];
tail->next = s;
tail = s;//tail不断更替为新插入的节点
}
tail->next = NULL;
}4 遍历输出单链表
void ListPList(LinkNode *L) {
LinkNode *p = L->next;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
}5 销毁单链表
void Destroy(LinkNode *&L) {
LinkNode *S;//工具节点
S = L->next;//指向L的下一个节点（前节点）
while (S != NULL) {//前节点不为空
free(L);//释放后面的
L = S;
S = L->next;
}
free(L);//把最后一个不为空的前节点释放
}原文地址：https://blog.csdn.net/2302_79847831/article/details/142996185
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！