特点：
用数组实现的
//因为L会改变，所以要引用
bool ListInsert(SqList &L, int i, ElemType element)
{
//判断不合法情况
if (i<1 || i>L.length + 1)
{
return false;
}
//存储空间满了也不能插入
if (L.length == MaxSize)
{
return false;
}
//插入元素，插入位置后的元素后移
for (int j = L.length; j >= i; j--)
{
L.data[j] = L.data[j - 1];
}
L.data[i - 1] = element;//插入位置的元素
L.length++;
return true;
}
//删除顺序表 要删除的，有所改变的就加&
//i 是删除元素的位置，del是被删除元素的值
bool ListDelete(SqList& L, int i, ElemType& del) {
//判断被删除元素的位置是否合法
if (i < 1 || i>L.length + 1) {
return false;
}
del = L.data[i - 1];
for (int j = i; j < L.length; j++) {
L.data[j - 1] = L.data[j];//j赋值为i-1的话，L.data[j] = L.data[j+1],此时需要j<L.length+1,不然多复制了一个
}
L.length--;//顺序表长度必须减一
return true;
}
//查找顺序表
int LocateElem(SqList& L, ElemType element) {
int i;
for (i = 0; i < L.length; i++) {
if (element == L.data[i]) {
return i + 1;//返回位置，不是下标
}
}
return 0;
}
顺序表进行操作移动了大量元素，会造成碎片，因此使用链式结构
一般学习的是具有头结点的链表：
头结点：单链表的第一个结点之前附加了一个结点。头结点的数据域可以不设任何信息，也可以记录表长等信息。头结点的指针域指向线性表的第一个元素结点。
头插法就是把每个节点插在头结点后面
存储的顺序和输入的顺序是相反的
//1. 头插法
// LNode* 和 LinkList 等价
void list_head_insert(LNode*& L)//这里的LNode* 是结构体指针，&是引用 结构体要改变
{
L = (LinkList)malloc(sizeof(LNode));//申请头结点空间，头指针指向头结点
L->next = NULL;
ElemType x;
scanf("%d", &x);
LNode* s;//指向新的节点的指针
while (x != 9999)
{
s = (LinkList)malloc(sizeof(LNode)); // 每次申请一个新的节点
s->data = x;
s->next = L->next;//插到头结点后面
L->next = s;
scanf("%d", &x);
}
}
尾插法就是把节点插在链表尾部，存储顺序与输入顺序是相同的。
把节点连接到链表尾部
//2. 尾插法
void list_tail_insert(LNode*& L)
{
L = (LinkList)malloc(sizeof(LNode));//头结点
L->next = NULL;
ElemType x;
scanf("%d", &x);
//r是一个指针，s也是一个指针变量
LNode* s, * r = L;//L始终指向头结点，r现在也指向头结点
while (x != 9999)
{
s = (LinkList)malloc(sizeof(LNode));//申请新节点，实际上s指向的就是这块空间的首地址
s->data = x;
r->next = s;//r始终指向链表尾部，把新节点连接到尾结点的next
r = s;//r指向新的尾部
scanf("%d", &x);
}
从单链表的第一个结点开始，依次比较表中各个结点的数据域的值，若某结点数据域的值等于x，则返回该结点的指针；
若整个单链表中没有这样的结点，则返回空。
//3. 按值查找
LinkList LocateElem(LinkList L, ElemType SearchVal)
{
while (L)
{
if (L->data == SearchVal)
{
return L;
}
L = L->next;
}
return NULL;
}
从单链表的第一个结点开始，顺着指针域逐个往下搜索，直到找到第 i 个结点为止，否则返回最后一个结点的指针域NULL。
//4.按位置查找
LinkList GetElem(LinkList L, int SearchPos)
{
int j = 0;
//判断不合法情况
if (SearchPos < 0)
{
return NULL;
}
while (L && j < SearchPos)
{
L = L->next;
j++;
}
return L;
}
首先保证第i个位置的合法性。从表头开始遍历，查找第 i-1个结点，即插入位置的前驱结点为p，然后令新结点q的指针域指向p的后继结点，再令结点p的指针域指向新结点q。
//5. 插入一个元素
bool ListFrontInsert(LinkList L, int i, ElemType InsertVal) //第i个位置
{
LinkList p = GetElem(L, i - 1); // 利用了按位查找的函数，首先保证该位置的合法性
if (NULL == p)
{
return false;
}
LinkList q;
q = (LinkList)malloc(sizeof(LNode));//为新插入的节点申请空间
q->data = InsertVal;
q->next = p->next; //p指针就是插入位置前一个位置
p->next = q;
return true;
}
先检查删除位置的合法性，然后从头开始遍历，找到表中的第 i-1 个结点，即被删除结点的前驱结点p，被删除结点为q，修改p的指针域，将其指向q的下一个结点，最后再释放结点q的存储空间。
//5.删除节点
bool ListDelete(LinkList L, int i)
{
LinkList p = GetElem(L, i - 1);//查找前驱节点是否存在
if (NULL == p)
{
return false;
}
LinkList q = p->next;//指向要删除的节点
p->next = q->next;//断链
free(q);//释放，删除操作要释放空间
return true;
}
// 6. 打印链表
void print_list(LinkList L)
{
L = L->next;
while (L != NULL)
{
printf("%3d", L->data);
L = L->next;
}
printf("\n");
}
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LNode {
ElemType data;
struct LNode* next;
}LNode, * LinkList;//结构体指针
//1. 头插法
// LNode* 和 LinkList 等价
void list_head_insert(LNode*& L)//这里的LNode* 是结构体指针，&是引用 结构体要改变
{
L = (LinkList)malloc(sizeof(LNode));//申请头结点空间，头指针指向头结点
L->next = NULL;
ElemType x;
scanf("%d", &x);
LNode* s;//指向新的节点的指针
while (x != 9999)
{
s = (LinkList)malloc(sizeof(LNode)); // 每次申请一个新的节点
s->data = x;
s->next = L->next;//插到头结点后面
L->next = s;
scanf("%d", &x);
}
}
//2. 尾插法
void list_tail_insert(LNode*& L)
{
L = (LinkList)malloc(sizeof(LNode));//头结点
L->next = NULL;
ElemType x;
scanf("%d", &x);
//r是一个指针，s也是一个指针变量
LNode* s, * r = L;//L始终指向头结点，r现在也指向头结点
while (x != 9999)
{
s = (LinkList)malloc(sizeof(LNode));//申请新节点，实际上s指向的就是这块空间的首地址
s->data = x;
r->next = s;//r始终指向链表尾部，把新节点连接到尾结点的next
r = s;//s指向新节点
scanf("%d", &x);
}
r->next = NULL;//
}
// 5. 打印链表
void print_list(LinkList L)
{
L = L->next;
while (L != NULL)
{
printf("%3d", L->data);
L = L->next;
}
printf("\n");
}
//4.按位置查找
LinkList GetElem(LinkList L, int SearchPos)
{
int j = 0;
//判断不合法情况
if (SearchPos < 0)
{
return NULL;
}
while (L && j < SearchPos)
{
L = L->next;
j++;
}
return L;
}
//3. 按值查找
LinkList LocateElem(LinkList L, ElemType SearchVal)
{
while (L)
{
if (L->data == SearchVal)
{
return L;
}
L = L->next;
}
return NULL;
}
//5. 插入一个元素
bool ListFrontInsert(LinkList L, int i, ElemType InsertVal) //第i个位置
{
LinkList p = GetElem(L, i - 1); // 利用了按位查找的函数，首先保证该位置的合法性
if (NULL == p)
{
return false;
}
LinkList q;
q = (LinkList)malloc(sizeof(LNode));//为新插入的节点申请空间
q->data = InsertVal;
q->next = p->next; //p指针就是插入位置前一个位置
p->next = q;
return true;
}
int main() {
LinkList L, search;
// list_head_insert(L);
list_tail_insert(L);
print_list(L);
// search=GetElem(L,2);
// if(search!=NULL)
// {
// printf("Succeeded in searching by serial number\n");
// printf("%d\n",search->data);
// }
// search=LocateElem(L,6);
// if(search!=NULL)
// {
// printf("Search by value succeeded\n");
// printf("%d\n",search->data);
// }
bool ret;
ret = ListFrontInsert(L, 4, 99);
print_list(L);
return 0;
}