线性表
- 两者都属于线性表
- 线性表：逻辑结构------必连续
- 物理结构------不一定连续
- 顺序表的物理结构 -----连续 ，链表的物理结构 ----不连续
- 顺序表的本质是数组，数组是一块地址连续的空间。而链表只是像细线一样，将不同地址的节点串起来。（通过next指针实现）
- 若需要经常头删，链表更合适
- 顺序表可以通过下标，随机访问
一.顺序表
是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
代码实现
1初始化：
在声明线性表的顺序存储结构，定义一个数组来存储顺序表的所有元素，还定义一个整形变量size来存储顺序表的实际长度
#include <stdio.h>
typedef int datatype;//定义类型int,别名为datatype
#define M 100typedef 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; }//12345for (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);//把最后一个不为空的前节点释放
}6 删除
bool ListDelete(LinkNode *&L, int i, ElemType &e) {int j = 0;LinkNode *p = L, *q;if (i <= 0)return false; //i错误返回假while (j < i - 1 && p != NULL) //查找第i-1个结点{j++;p = p->next;}if (p == NULL) //未找到位序为i-1的结点return false;else //找到位序为i-1的结点p{q = p->next; //q指向要删除的结点if (q == NULL)return false; //若不存在第i个结点,返回falsee = q->data;p->next = q->next; //从单链表中删除q结点free(q); //释放q结点return true;}
}
