1，顺序表实现---动态分配
#include<stdlib.h>
#define InitSize 10
typedef struct {
int *data;//静态分配
int length;
int MaxSize;
}SqList;
void InitList(SqList& L)
{
L.data = (int*)malloc(InitSize * sizeof(int));//分配空间
L.length = 0;
L.MaxSize = InitSize;//初始空间为10
}
void ListInsert(SqList& L, int x, int a)
{
L.data[x] = a;
}
void Increaselength(SqList& L, int len)
{
int *p = L.data;
L.data = (int*)malloc((InitSize + len) * sizeof(int));//重新开辟空间
for (int i = 0; i < L.MaxSize;i++)
{
L.data[i] = p[i];
}
L.MaxSize = InitSize + len;
free(p);
}
int main()
{
SqList q;
InitList(q);
ListInsert(q, 2, 4);
Increaselength(q, 5);
ListInsert(q, 12, 2);
printf("data[2]=%d,data[12]=%d", q.data[2], q.data[12]);
system("pause");
return 0;
}
第i个元素中的i表示的是位序
2， 静态分配的插入元素操作：
typedef struct {
int data[MaxSize];
int length;
}SqList;
void InitList(SqList& L)
{
L.length = 0;
for (int i = 0; i <MaxSize-1; i++)
{
L.data[i] = i;//赋予原始数据，注意不要插满
L.length++;
}
}
bool ListInsert(SqList &L,int i,int e)//在第i个位置插入e
{
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] = e;
L.length++;
return true;
}
int main()
{
SqList L;
InitList(L);
if (ListInsert(L, 8, 1))
{
printf("data[7]=%d ", L.data[7]);//验证插入
}
system("pause");
return 0;
}
3，静态分配的删除元素操作：
typedef struct {
int data[MaxSize];
int length;
}SqList;
void InitList(SqList& L)
{
L.length = 0;
for (int i = 0; i < MaxSize - 1; i++)
{
L.data[i] = i;//赋予原始数据，注意不要插满
L.length++;
}
}
bool ListDelete(SqList &L,int i,int &e)//在第i个位置插入e
{
if (i<1 || i>L.length)
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;
}
int main()
{
SqList L;
InitList(L);
int e = -1;
if (ListDelete(L, 8, e))//位置8的元素是7
{
printf("删除的元素是%d data[7]=%d", e,L.data[7]);//验证删除，删除后data[7]=8
}
system("pause");
return 0;
}
顺序表的查找：
按位查找,动态分配和普通数组访问方式相同,时间复杂度为O（1）
GetElem(SqList L,int i)
{
return L.data[i-1];
}按值查找，动态分配方式：
int LocatElem(SqList L, int e)
{
for(int i=0;i<L.length;i++)
{
if(L.data[i]==e)
return i+1;
}
return 0;}
不带头结点的单链表的初始化：
与顺序表不同，单链表是用指针来定义
typedef struct LNode {
int data;
struct LNode* next;//每个元素包括数据和指向下一个节点的指针
}LNode,*LinkList;//LNode*等价于LinkList
bool InitList(LinkList &L)//声明是一个单链表
{
L = NULL;
return true;
}
bool IsEmpty(LinkList &L)//声明是一个单链表
{
return (L == NULL);
}
int main()
{
LinkList L;//声明一个指向单链表的指针
InitList(L);
if(IsEmpty(L))
printf("初始化成功");
system("pause");
return 0;
}带头结点的单链表的初始化：
typedef struct LNode {
int data;
struct LNode* next;//每个元素包括数据和指向下一个节点的指针
}LNode,*LinkList;//LNode*等价于LinkList
bool InitList(LinkList &L)//声明是一个单链表
{
L = (LNode*)malloc(sizeof(LNode));//头指针指向下一个节点：即为头节点
if (L == NULL)
return false;//没有内存，分配失败
L->next = NULL;//头节点暂时没有节点
return true;
}
bool IsEmpty(LinkList &L)//声明是一个单链表
{
return (L == NULL);
}
int main()
{
LinkList L;
InitList(L);
if(IsEmpty(L)==false)
printf("初始化成功");
system("pause");
return 0;
}
带头结点，按位序插入：
typedef struct LNode {
int data;
struct LNode* next;//每个元素包括数据和指向下一个节点的指针
}LNode,*LinkList;//LNode*等价于LinkList
//带头结点按位序插入
bool ListInsert(LinkList& L,int i,int e)//在第i个位置插入e
{
if (i < 1)
return false;
int j = 0;
LNode *p;
p= L;//是从第0个节点开始遍历，所以p应该与头节点相同
while (p != NULL && j < i - 1)//找到第i-1的节点
{
p = p->next;
j++;
}
if (p == NULL)//超出链表长度
{
return false;
}
LNode *s = (LNode*)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;
p->next = s;
return true;
}
bool InitList(LinkList &L)//声明是一个单链表
{
L = (LNode*)malloc(sizeof(LNode));//头指针指向下一个节点：即为头节点
if (L == NULL)
return false;//没有内存，分配失败
L->next = NULL;//头节点暂时没有节点
return true;
}
bool IsEmpty(LinkList &L)//声明是一个单链表
{
return (L == NULL);
}
int main()
{
LinkList L;
InitList(L);
if(IsEmpty(L)==false)
printf("初始化成功");
if(ListInsert(L, 1, 1))
printf("插入成功");
system("pause");
return 0;
}不带头节点按位序插入：
bool ListInsert(LinkList& L,int i,int e)//在第i个位置插入e
{
if (i < 1)
return false;
if (i == 1)//此处插入第一个节点和其他节点不同，直接与L交互
{
LNode* s = (LNode*)malloc(sizeof(LNode));
s->data = e;
s->next = L;//指向L指向的节点
L = s;//需要更改头结点的指向，比较麻烦
return true;
}
int j = 1;//没有第0个节点
LNode *p;
p= L;//是从第0个节点开始遍历，所以p应该与头节点相同
while (p != NULL && j < i - 1)//找到第i-1的节点
{
p = p->next;
j++;
}
if (p == NULL)//超出链表长度
{
return false;
}
LNode* s = (LNode*)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;
p->next = s;
return true;
}指定节点的后插操作：
//在指定节点后插入一个元素
bool InsertNextLNode(LNode *p,int e)//传入节点即可，不需要传入表
{
if (p == NULL)
return false;//节点选择错误
LNode* s = (LNode*)malloc(sizeof(LNode));
if (s == NULL)//内存分配不够
return false;
s->data = e;
s->next = p->next;
p->next = s;
return true;
} 
前插操作：
在p节点之前插入s节点
思路：无法找到前驱节点，因此可以插在p节点之后，然后将两个节点中的数据调换
bool InsertPriorNode(LNode* p, LNode* s)
{
if (p == NULL || s == NULL)
return false;
s->next = p->next;
p->next = s;
int temp = s->data;
s->data = p->data;
p->data = temp;
return true;
}带头结点按位序删除第i个节点：
思路：先找到第i-1节点，然后将前一个结点的next指针指向后一个结点的next指针
bool ListDelete(LinkList L, int i, int& e)
{
if (i < 1)
return false;
LNode* p = L;//当前指向结点
int j = 0;
while (p != NULL&&j<i-1) {//找到i-1结点
p = p->next;
j++;
}
if (p == NULL)
return false;
if (p->next== NULL)//需要删除的结点也为空
return false;
LNode* q = p->next;//应当被删除的结点
e = q->data;
p->next = q->next;
free(q);
return true;
}指定节点的删除p：
将p的后一个结点复制到p,然后将p的后一个结点释放掉
bool DeleteNode(LNode* p)
{
if (p == NULL)
return false;
LNode* q = p->next;
p->data = p->next->data;
p->next = q->next;
free(q);
return true;
}注意：如果p是最后一个结点，只能从表头依次寻找p的前驱