一、顺序表
自定义:
#define MaxSize 10
typedef int ElemType;
1、静态分配
1)定义:
typedef struct {
ElemType data[MaxSize];
int len;
}SqList;
2)初始化顺序表:
void InitList(SqList& L) {
for (int i = 0; i < MaxSize; i++) {
L.data[i] = 0;
}
L.len = 0;
}
3)插入数据:
bool ListInsert(SqList& L, int i, ElemType e) {
if (L.len + 1 >= MaxSize || i<1 || i > L.len+1) {
return false;
}
for (int j = L.len; j >= i; j--) {
L.data[j] = L.data[j-1];
}
L.data[i-1] = e;
L.len++;
return true;
}
4)删除:
bool ListDelete(SqList& L, int i, ElemType& e) {
if (i < 1 || i > L.len) {
return false;
}
e = L.data[i - 1];
for (int j = i; j < L.len; j++) {
L.data[j - 1] = L.data[j];
}
L.len--;
return true;
}
5)查找:
- 按值查找:
int LocateElem(SqList L, ElemType e) {
for (int i = 0; i < L.len; i++) {
if (L.data[i] == e) {
return i + 1; //返回的是该元素的位序
}
}
return 0;
}
- 按位查找:
ElemType GetElem(SqList L, int i) { //i是位序
if (i > L.len || i < 0) {
return (ElemType)0;
}
return L.data[i - 1];
}
2、动态分配
自定义:
#define InitSize 10
typedef int ElemType;
1)定义:
typedef struct {
ElemType* data;
int MaxSize;
int len;
}SeqList;
2)初始化顺序表:
void InitList(SeqList& L) {
//用malloc函数申请一片连续空间
L.data = (ElemType*)malloc(InitSize * sizeof(ElemType));
L.MaxSize = InitSize;
L.len = 0;
}
3)插入数据:
因为是动态分配,当数据超过最大空间MaxSize时,需要重新申请一个更大的空间,并把数据复制到新空间上。
//动态分配,所以得再申请大一片的空间然后把数据搬过去
void ExpandList(SeqList& L, SeqList& L_temp) {
L_temp.data = (ElemType*)malloc(L.MaxSize * 2 * sizeof(ElemType));
L_temp.MaxSize = L.MaxSize * 2;
L_temp.len = L.len;
//将L的值赋给L_temp
for (int i = 0; i < L.len; i++) {
L_temp.data[i] = L.data[i];
}
free(L.data);
L = L_temp;
// free(L_temp.data); 这一步是错误的!!!
}
//插入
bool ListInsert(SeqList& L, int i, ElemType e) {
if (i<1 || i > L.len + 1)
return false;
if (L.len + 1 >= L.MaxSize) {//扩展空间后再进行下一步
SeqList L_temp;
ExpandList(L, L_temp);
}
for (int j = L.len; j >= i; j--) {
L.data[j] = L.data[j - 1];
}
L.data[i - 1] = e;
L.len++;
return true;
}
在实现ExpandList时,我犯了一个低级错误,本来认为新空间赋给L后L_temp.data需要释放掉,运行发现L也跟着释放了。因为L=L_temp后,L.data是直接指向新的空间,并不是再复制一份数据给L.data。其实是我将L_temp与新申请的空间混淆了,L_temp是一个结构体,在ExpandList运行结束后就自动释放了。
4)删除、查找
代码与静态分配一模一样!!!
二、链表
1、单链表
1) 带头结点单链表
1)定义
typedef int ElemType;
typedef struct LNode {
ElemType data;
struct LNode* next; //指向下一个结点
}LNode, *LinkList; //结点和链表
2)初始化一个单链表
bool InitList(LinkList& L) {
L = (LNode*)malloc(sizeof(LNode));
if (L == NULL) //内存不足分配失败
return false;
L->next = NULL;
return true;
}
3)获取链表长度
int L_Length(LinkList L) {
int count = 0;
while (L->next != NULL)
{
count++;
L = L->next;
}
return count;
}
4)查找
- 按位查找
LNode* GetElem(LinkList L, int i) {
if (i < 0)
return NULL;
int j = 1; //记录当前结点位置
LNode* ergodic = L; //扫描结点到i-1的位置
while (ergodic != NULL && j <= i) {
ergodic = ergodic->next;
j++;
}
return ergodic;
}
- 按值查找
LNode* LocateElem(LinkList L, ElemType e) {
LNode* p = L->next;
while (p != NULL && p->data != e)
p = p->next;
return p; //找不到返回null
}
5)插入
- 指定结点的前插操作
// 在p结点之前插入元素e
bool InsertPriorNode(LNode* p, ElemType e) {
if (p == NULL) {
return false;
}
LNode* temp = (LNode*)malloc(sizeof(LNode));
if (temp == NULL)
return false;
//无法获取p结点之前的结点,所以使用数据的替换
temp->data = p->data;
p->data = e;
temp->next = p->next;
p->next = temp;
return true;
}
- 指定结点的后插操作
//在p节点之后插入元素e
bool InsertNextNode(LNode* p, ElemType e) {
if (p == NULL) {
return false;
}
LNode* temp = (LNode*)malloc(sizeof(LNode));
if (temp == NULL)
return false;
temp->data = e;
temp->next = p->next;
p->next = temp;
return true;
}
- 按位序插入
bool ListInsert(LinkList& L, int i, ElemType e) {
if (i<1)
return false;
LNode* ergodic; //遍历寻找位置为i的结点的指针
ergodic = GetElem(L, i-1);
if (ergodic == NULL)
return false;
return InsertNextNode(ergodic, e);
}
6)删除
- 按位序删除
bool ListDelete(LinkList& L, int i, ElemType &e) {
if (i < 1)
return false;
LNode* ergodic; //扫描结点到i-1的位置
ergodic = GetElem(L, i - 1);
if (ergodic == NULL || ergodic->next == NULL)
return false;
LNode* temp = ergodic->next;
e = temp->data;
ergodic->next = temp->next;
free(temp);
return true;
}
- 指定结点删除
//未知前面区域的结点,所以使用数据的替换(当p为最后一个结点时不可用)
bool DeleteNode(LNode* p) {
if (p == NULL)
return false;
LNode* temp = p->next;
p->data = temp->data;
p->next = temp->next;
free(temp);
return false;
}
7)建立单链表
- 单链表建立——尾插法
LinkList List_TailInsert(LinkList& L) {
int x;
//L = (LinkList)malloc(sizeof(LNode));//建立头结点
LNode* temp, * r = L; //r为尾指针
scanf("%d", &x);
while (x != 9999) {
temp = (LNode*)malloc(sizeof(LNode));
temp->data = x;
r->next = temp;
r = temp;
scanf("%d", &x);
}
r->next = NULL;
return L;
}
- 单链表建立——头插法
LinkList List_HeadInsert(LinkList& L) {
LNode* temp;
int x;
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL;
scanf("%d", &x);
while (x != 9999) {
temp = (LNode*)malloc(sizeof(LNode));
temp->data = x;
temp->next = L;
L = temp;
scanf("%d", &x);
}
return L;
}
2)不带头结点单链表
1)判断单链表是否为空
bool Empty(LinkList L) {
if (L == NULL)
return true;
else
return false;
}
2)初始化单链表
bool InitList(LinkList& L) {
L = NULL;
return true;
}
3)获取链表长度
int L_Length(LinkList L) {
if (Empty(L))
return 0;
int count = 1;
while (L->next != NULL)
{
count++;
L = L->next;
}
return count;
}
4)查找
- 按位查找
LNode* GetElem(LinkList L, int i) {
if (i < 0)
return NULL;
int j = 1;//记录当前结点位置
LNode* ergodic = L;//扫描结点到i-1的位置
while (ergodic != NULL && j < i) {
ergodic = ergodic->next;
j++;
}
return ergodic;
}
- 按值查找
LNode* LocateElem(LinkList L, ElemType e) {
LNode* p = L;
while (p != NULL && p->data != e)
p = p->next;
return p; //找不到返回null
}
5)建立链表
- 尾插法
LinkList List_TailInsert(LinkList& L) {
int x;
L = (LinkList)malloc(sizeof(LNode));//建立头结点
scanf("%d", &x);
L->data = x;
L->next = NULL;
LNode* temp, * r = L; //r为尾指针
while (true) {
scanf("%d", &x);
if (x == 9999)
break;
temp = (LNode*)malloc(sizeof(LNode));
temp->data = x;
r->next = temp;
r = temp;
}
r->next = NULL;
return L;
}
- 头插法
LinkList List_HeadInsert(LinkList& L) {
LNode* temp;
int x;
scanf("%d", &x);
L = (LinkList)malloc(sizeof(LNode));
L->data = x;
L->next = NULL;
while (true) {
scanf("%d", &x);
if (x == 9999)
break;
temp = (LNode*)malloc(sizeof(LNode));
temp->data = x;
temp->next = L;
L = temp;
}
return L;
}
3)小调试
int main(){
LinkList L;
InitList(L);
List_HeadInsert(L);
//List_TailInsert(L);
//获取链表长度
int len = L_Length(L);
printf("长度为%d",len);
//查找——按位查找
LNode* p = GetElem(L, 2);
//查找——按值查找
LNode* p2 = LocateElem(L, 4);
// 在p结点之前插入元素e
LNode* p3 = L->next->next->next;
InsertPriorNode(p3, 11);
//插入——按位序插入
ListInsert(L, 3, 12);
//按位序删除
ElemType e;
ListDelete(L, 3, e);
//指定结点删除
LNode* p4 = L->next->next;
DeleteNode(p4);
}
可以用此主函数断点调试,查看数据的改变过程。
2、双链表
1)定义
typedef int ElemType;
typedef struct DNode {
ElemType data;
struct DNode* prior, * next;
}DNode, *DLinklist;
2)初始化双链表
bool InitDLinkList(DLinklist& L) {
L = (DNode*)malloc(sizeof(DNode));
if (L == NULL)
return false;
L->prior = NULL;
L->next = NULL;
return true;
}
3)判空
bool Empty(DLinklist L) {
if (L->next == NULL)
return true;
else
return false;
}
4)插入
bool InsertNextNode(DNode* p, DNode* s) {
if (p == NULL || s == NULL)
return false;
s->next = p->next;
s->prior = p;
if (p->next != NULL)
p->next->prior = s;
p->next = s;
return true;
}
5)删除
//删除p结点
bool DeleteNextNode(DNode* p) {
if (p == NULL)
return false;
if (p->next != NULL) {
p->prior->next = p->next;
p->next->prior = p->prior;
}
else
{
p->prior->next = NULL;
}
free(p);
return true;
}
3、循环链表
1)循环单链表初始化
bool InitList(LinkList& L) {
L = (LNode*)malloc(sizeof(LNode));
if (L == NULL)
return false;
L->next = L;
return true;
}
2)循环双链表初始化
bool InitList(DLinkList& L) {
L = (DNode*)malloc(sizeof(DNode));
if (L == NULL)
return false;
L->next = L;
L->prior = L;
return true;
}
4、静态链表
#define MaxSize 10
typedef int ElemType;
typedef struct{
ElemType data;
int next;
}SLinkList[MaxSize];