顺序结构存储
顺序表元素地址连续、类型相同，可以用一位数组表示。但是顺序表长度随着增加和删除是可变的，所以另需一个变量记录数组长度。
#define LIST_INIT_SIZE 100
typedef struct{
ElemType elem[LIST_INIT_SIZE];
int len;
}SqList;
#define MAXSIZE 100
typedef struct{
ElemType *data;
int length;
}SqList;
// 创建时
SqList L;
L.data = (ElemType*)malloc(sizeof(ElemType) * MAXSIZE);
顺序存储举例
多项式
#define MAXSIZE 1000 // 多项式最大长度
typedef struct{ // 定义多项式非零项
float p; // 系数
int e; // 指数
}Polynomial;
typedef struct{
int length; // 当前长度
Polynomial *ele; // 基地址
}SqList;
图书
#define MAXSIZE 1000 // 图书最大长度
typedef struct{ // 定义多项式非零项
float price; // 价格
char name[50]; // 名称
char no[20]; // isbn
}Book;
typedef struct{
int length; // 当前图书个数
Book *ele; // 基地址
}SqList;
实现
线性表初始化
Status InitList(SqList L){
L.elem = (ElemType*)malloc(sizeof(ElemType) * MAXSIZE);
if(!L.elem) exit(OVERFLOW);
L.length = 0;
return OK;
}
销毁
void DestroyList(SqList L){
free(L.elem);
}
清空
void ClearList(SqList L){
L.length = 0;
}
线性表长度
int GetLength(SqList L){
return L.length;
}
是否为空
int IsEmpty(SqList L){
if(L.length == 0) return 1;
else return 0;
}
取指定下标的元素
ElemType GetElem(SqList L, int i, int *res){
if(i<0 || i>L.length) return ERROR;
*res = L.elem[i];
return OK;
}
指定值元素的下标
int LocateElem(SqList L, ElemType e){
for(int i = 0; i < L.length; i++)
if(L.elem[i] == e) return i;
return 0; // 失败返回 0
}
在指定下标处插入元素
int ListInsert(SqList L, int i, ElemType e){
if(i<0 || i>L.length) return ERROR; // 不能隔着存
if(L.length == MAXSIZE) return ERROR; // 满了
for(int j = L.length-1; j > i; j--)
L.elem[j + 1] = L.elem[j];
L.elem[i] = e;
L.length++;
return OK;
}
删除指定下标处元素
int ListDelete(SqList L, int i){
if(i<0 || i>L.length) return ERROR;
for(int j = i + 1; j < L.length; j++)
L.elem[j - 1] = L.elem[j];
L.length--;
return OK;
}
链式存储结构
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
学生链表
typedef struct{
char name[8];
char num[8];
int score;
}ElemType;
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
单链表
单链表初始化
Status InitList(LinkList L){
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL;
return OK;
}
链表是否为空
// 为空返回 1
int IsEmpty(LinkList L){
if(L->next) return 0;
return 1;
}
销毁
// 依次释放所有节点，包括头节点
void DestroyList(LinkList L){
LinkList p = NULL;
while(L){
p = L;
L = L->next;
free(p);
}
}
销毁
// 依次释放所有节点，保留头节点
void DestroyList(LinkList L){
LinkList p = L.next;
LinkList q = NULL;
while(p){
q = p->next;
free(p);
p = q;
}
L->next = NULL;
retutn OK;
}
求长度
int GetLength(LinkList L){
int length = 0;
LinkList p = L.next;
while(p){
p = p->next;
length++;
}
return length
}
取第i个元素的内容
i 从1开始
Status GetItem(LinkList L, int i, ElemType *e){
int j = 1;
LinkList p = L->next;
while(p && j < i){
p = p->next;
j++;
}
if(!p || j > i) return ERROR;
*e = p->data;
return OK;
}
查找指定元素的地址
LinkList LocateElem(LinkList L, ElemType e){
LinkList p = L->next;
while(p && p->data != e) p = p->next;
return p;
}
查找指定元素是第i个？
i 从1开始
int LocateElem(LinkList L, ElemType e){
int j = 1;
LinkList p = L->next;
while(p && p->data != e){
p = p->next;
j++;
}
if(p) return j;
else return 0;
}
在第i个前插入
Status InsertElem(LinkList L, int i, ElemType e){
int j = 1;
LinkList p = L;
while(p && j < i-1){
p = p->next;
j++;
}
if(!p || j > i - 1) return ERROR; // 大于表长+1或小于1
LinkList q = (LinkList)malloc(sizeof(LNode));
q->data = e;
q->next = p->next;
p->next = q;
return OK;
}
删除第i个节点
Status ListDelete(LinkList L, int i, ElemType *e){
int j = 0;
LinkList p = L;
while(p->next && j < i-1){
p = p->next;
j++;
}
if(!p->next || j > i - 1) return ERROR; // 大于表长+1或小于1
LinkList q = p->next;
p->next = q->next;
*e = q->data;
free(q);
return OK;
}
创建单链表
头插法
void CreateList_F(LinkList L, int N){
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL;
for(int i = N; i > 0; i--){
LinkList p = (LinkList)malloc(sizeof(LNode));
scanf("%d", &p->data);
p->next = L->next;
L->next = p;
}
}
尾插法
void CreateList_E(LinkList L, int N){
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL;
LinkList r = L;
for(int i = 0; i < N; i++){
LinkList p = (LinkList)malloc(sizeof(LNode));
scanf("%d", &p->data);
p->next = NULL;
r->next = p;
r = p;
}
}
循环链表
用尾指针更方便
合并两个循环链表
void Connect(LinkList Ta, LinkList Tb){
LinkList Head = Ta->next;
Ta->next = Tb->next->next;
free(Tb->next);
Tb->next = Head;
}
双向链表
typedef struct DualNode{
ElemType data;
struct DualNode *prior, *next;
}DualNode, *DualLinkList;
插入
// 在第i个位置之前插入节点e
Status ListInsert(DualLinkList L, int i, ElemType e){
if(!GetItem(L, i)) return ERROR;
DualLinkList s = (DualLinkList)malloc(sizeof(DualNode));
s->data = e;
s->prior = p->prior;
p->prior->next = s;
s->next = p;
p->prior = s;
return OK;
}
删除
// 删除第i个位置返回给e
Status ListDelete(DualLinkList L, int i, ElemType *e){
if(!GetItem(L, i)) return ERROR;
*e = p->data;
p->prior->next = p->next;
p->next->prior = p->prior;
free(p);
return OK;
}
顺序表与链表比较
