线性表的顺序表示
顺序表的实现（静态分配）
#include <stdio.h>
//静态创建一个顺序表
#include <stdio.h>
#define Maxsize 10
typedef struct{
int data[Maxsize];
int length;
}SqList;
//初始化一个顺序表
void InitList(SqList &L){
L.length = 0;
for(int i=0;i<Maxsize;i++)
L.data[i]=0;
}
int main(){
SqList L;
InitList(L);
for(int i=0;i<Maxsize;i++)
printf("data[%d]=%d\n",i,L.data[i]);
return 0;
}
顺序表的实现（动态分配）
//动态创建一个顺序表
#define InitSize 10
typedef struct{
int *data; //指示动态分配数组的指针
int MaxSize;
int length;
}SeqList;
//初始化
void InitList(SeqList &L){
//用malloc函数申请一片连续的存储空间
L.data=(int *)malloc(InitSize*sizeof(int));
L.length=0;
L.MaxSize=InitSize;
}
//增加动态数组的长度
void IncreaseSize(SeqList &L, int len){
int *p = L.data;//p指针跟data指针指向同一个地址
L.data = (int *)malloc((L.MaxSize+len)*sizeof(int));
for(int i=0;i<L.length;i++){
L.data[i]=p[i];
}
L.MaxSize=L.MaxSize+len;
free(p);
}
int main(){
SeqList L;
InitList(L);
IncreaseSize(L,5);
return 0;
}顺序表的基本操作--插入
#include <stdio.h>
#include <stdlib.h>
#define MaxSize 10
typedef struct {
int data[MaxSize]; // 存储数据
int length; // 顺序表长度
} SqList;
// 顺序表的基本操作--插入 ：在 L 的位序 i 处插入元素 e
bool ListInsert(SqList &L, int i, int e) {
if (i < 1 || i > L.length + 1) // 检查 i 是否越界
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; // 插入成功
}
// 初始化顺序表
void InitList(SqList &L) {
L.length = 0;
for (int i = 0; i < MaxSize; i++)
L.data[i] = 0;
}
int main() {
SqList L;
InitList(L);
// 输出初始化数据
for (int i = 0; i < MaxSize; i++)
printf("data[%d]=%d\n", i, L.data[i]);
// 插入元素
if (ListInsert(L, 1, 3)) {
printf("插入成功！\n");
} else {
printf("插入失败！\n");
}
// 输出插入后的数据
for (int i = 0; i < MaxSize; i++)
printf("data[%d]=%d\n", i, L.data[i]);
return 0;
}
因为
for (int j = L.length; j >= i; j--)
L.data[j] = L.data[j - 1];,说明插入操作从最后一个元素开始后移
注意：实行插入操作时，要避免当前列表是一个空列表，否则插入操作可能会失败，
因为你不能在空的顺序表里直接插入第 5 个元素，必须先插入 i=1、i=2……再到 i=5
顺序表的基本操作--删除
bool ListDelete(SqList &L, int i, int &e) {
if (i < 1 || i > L.length) // 检查 i 是否越界
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; // 插入成功
}注意：删除操作
for (int j = i; j < L.length; j++)
L.data[j-1] = L.data[j];说明从最前面的一个元素开始前移
顺序表的按位查找
int GetElem(SqList &L, int i) {
if (i < 1 || i > L.length) {
printf("索引 %d 超出范围，当前表长: %d\n", i, L.length);
return -1;
}
return L.data[i-1];
}注意：主函数中，应该返回的是函数值，而不是函数名
正确：printf("第 1 个元素: %d\n", GetElem(L, 1));
错误：printf("第 1 个元素: %d\n", GetElem);
顺序表的按值查找
//按值查找,找到顺序表L中的第一个元素值等于e的值，并返回其位序
int LocateElem(SqList L,int e){
for(int i=0;i<L.length;i++)
if (L.data[i]==e)
return i+1; //数组下标为i的元素值等于e，但位序是i+1
return 0;
}
顺序表作业部分：
01
我的代码：
bool Deletemin(Sqlist &L, int e){
for (int i=0;i<=L.length;i++)
if (L.data[i]>=L.data[i+1])
L.data[i]=L.data[i+1];
e=data[i];
for (int j = i; j < L.length; j++)
L.data[j-1] = L.data[j];
L.length--;
return true;
}
存在的问题：
正确的代码：
bool Deletemin(Sqlist &L, int &e) {
if (L.length == 0) return false; // 防止空表操作
// 1. 找到最小值及其索引
int minIndex = 0;
for (int i = 1; i < L.length; i++) {
if (L.data[i] < L.data[minIndex]) {
minIndex = i;
}
}
// 2. 记录最小值
e = L.data[minIndex];
// 3. 删除该元素，后面的元素前移
for (int i = minIndex; i < L.length - 1; i++) {
L.data[i] = L.data[i + 1];
}
// 4. 长度减少
L.length--;
return true;
}
02
线性表的链式表示
单链表的代码定义
//单链表的代码定义
typedef struct LNode{ //定义单链表的节点类型
ElemType data; //每个节点存放一个数据元素
struct LNode *next; //指针指向下一个节点位置
}LNode,*LinkList; 单链表的初始化和判空操作
带头节点
bool InitList(LinkList &L){
L = (LNode *)malloc(sizeof(LNode)); //创建头节点
L->next=NULL; //头节点之后暂时还没有节点，所以是空
return true;
}
bool Empty(LinkList &L){
if (L->next==NULL)
return true;
else
return false;
}不带头节点
bool InitList(LinkList &L){
L = NULL; //空表，无节点，防止脏数据设置为NULL
return true;
}
bool Empty(LinkList &L){
if(L==NULL)
return true;
else
return false;
}
bool Empty(LinkList L){
return (L==NULL);
}单链表的插入操作（按位序插入）
带头节点
//在第i个位置插入元素e（带头节点）
bool ListInsert(LinkList &L,int i,ElemType e){
if(i<1)
return false;
LNode *p; //指针p指向当前扫描到的节点
int j=0; //当前p指向的是第几个节点
p = L; //L指向头指针，头指针是第0个节点（不存数据）
while(p!=NULL && j<i-1) { //循环找到第i-1个节点
p=p->next;
j++;
}
if(p==NULL) //i值不合法
return false;
//用malloc函数申请新的节点空间，在空间里存放插入的数据元素和指针
LNode *s = (LNode *)malloc(sizeof(LNode));
s->data = e; //将参数e存到新节点
s->next = p->next; //将原本i节点的后继节点，即p指针的next
p->next=s; //将节点s连接到p之后
return true; //插入成功
} 
不带头节点
//按位序插入（不带头节点）
bool ListInsert(LinkList &L,int i,ElemType e){
if(i<1)
return false;
if(i==1){ //插入第1个节点与其他节点操作不同
LNode *s = (LNode *)malloc(sizeof(LNode));
if (s == NULL) return false; // 检查内存分配
s->data = e;
s->next = L;//因为此时的头指针是第一个节点，所以在表头插入，需要将下一个指针指向头指针
L = s; //头指针指向新节点
return true;
}
LNode *p;
int j=1; //因为无头节点，所以p指针一开始就指向第一个节点，所以j=1
p = L; //p指针指向第1个节点，（不是头节点）
while(p!=NULL && j<i-1) { //循环找到第i-1个节点
p=p->next;
j++;
}
if(p==NULL) //i值不合法
return false;
LNode *s = (LNode *)malloc(sizeof(LNode));
if (s == NULL) return false; // 检查内存分配
s->data = e; //将参数e存到新节点
s->next = p->next; //将原本i节点的后继节点，即p指针的next
p->next=s; //将节点s连接到p之后
return true; //插入成功
}
后插操作
//后插操作：在p节点之后插入元素e
bool InsertNextNode(LNode *p,ElemType e){
if(p==NULL) return false;
LNode *s = (LNode *)malloc(sizeof(LNode));
if (s == NULL) return false;
s->data = e; //将参数e存到新节点
s->next = p->next; //将原本i节点的后继节点，即p指针的next
p->next=s; //将节点s连接到p之后
return true; //插入成功
}
前插操作
//前插操作：在p节点之前插入元素e，偷梁换柱将p和s节点的数据和指针互换
bool InsertPriorNode (LNode *p,ElemType e){
if(p==NULL) return false;
LNode *s = (LNode *)malloc(sizeof(LNode));
if(s==NULL) return false;//内存空间分配失败
s->next = p->next; //将p节点指针的指向先赋值给s节点
p->next = s;//将新建立的s节点连接到p之后，以便后面与s节点交换
s->data = p->data;//将p中元素复制到s节点中，实现交换，此时在逻辑上，s节点就是p节点
p->data = e;//将原先的p节点数据更换为e，就是将p节点变换成实际的新插入的节点
return true;
}
单链表的删除操作
按位序删除（带头节点）
//按位序删除(带头节点)
bool ListDelete(LinkList &L,int i,ElemType &e){
if(i<1) return false;
LNode *p; //指针p指向当前扫描到的节点
int j=0; //当前p指向的是第几个节点
p = L; //L指向头指针，头指针是第0个节点（不存数据）
while(p!=NULL && j<i-1) { //循环找到第i-1个节点
p=p->next;
j++;
}
if(p==NULL) //i值不合法
return false;
if(p->next == NULL)//第i个节点之后已经没有其他节点
LNode *q = p->next; //让q指向要被删除的节点
e = q->data; //用e返回元素的值
p->next = q->next; //将*q节点从链中“断开”
free(q);
return true;
}
指定节点的删除
将 p 的后继节点的数据复制到 p，然后删除后继节点
//删除指定节点p
bool DeleteNode(LNode *p){
if(p==NULL) return false;
LNode *q = p->next; //令q指向*p的后继节点
p->data = p->next->data; // 和后继节点交换数据域
p->next = q->next; //将*q结点从链中‘断开’
free(q);
return true;
} 
bool DeleteNode(LNode *p) {
if (p == NULL) {
// 如果p为空，无法删除
return false;
}
if (p->next == NULL) {
// 如果p是最后一个节点，无法使用这种方法删除
// 因为没有后继节点可以复制数据
return false;
}
// 令q指向p的后继节点
LNode *q = p->next;
// 将后继节点的数据复制到p
p->data = q->data;
// 将q节点从链中“断开”
p->next = q->next;
// 释放q节点的内存
free(q);
return true;
}
单链表的按位查找（带头节点）
LNode *GetElem(LinkList L,int i){
if(i<0) return NULL;
LNode *p; //指针p指向当前扫描到的节点
int j=0; //当前p指向的是第几个节点
p = L; //L指向头指针，头指针是第0个节点（不存数据）
while(p!=NULL && j<i) { //循环找到第i个节点
p=p->next;
j++;
}
return p;
} 单链表的按值查找（带头节点）
//单链表的按值查找,找到数据域==e的结点
LNode * LocateElem(LinkList L,ElemType e){
//从第一个节点开始查找数据域为e的节点
LNode *p = L->next;
while(p!=NULL && p->data!=e)
p=p->next;
return p; //找到后返回该结点指针，否则返回NULL
} 尾插法建立单链表
//尾插法建立单链表
LinkList_TailInsert(LinkList &L){ //正向建立单链表
int x; //设ElemType为整形
L=(LinkList)malloc(sizeof(LNode));//建立头节点，初始化空表
//r为表尾指针，s是要新插入的结点指针，此时都指向L（头指针）
LNode *s,*r=L;
scanf("%d",&x);
while(x!=9999){
s=(LNode*)malloc(sizeof(LNode));
s->data=x;
//在r结点之后插入元素x
r->next=s;
r=s; //永远保持r指向新的表尾结点
scanf("%d",&x);
}
r->next=NULL;//表尾指针置空
return L;
} 头插法建立单链表
//头插法建立单链表
LinkList List_HeadInsert(LinkList &L){//逆向建立单链表
LNode *s；
int x; //设ElemType为整形
L=(LinkList)malloc(sizeof(LNode));//建立头节点
L->next=NULL; //初始化为空列表
scanf("%d",&x); //输入结点的值
while(x!=9999){
s=(LNode*)malloc(sizeof(LNode));//创建新结点
s->data=x;
s->next=L->next;
L->next=s; //将新节点插入表中，L为头指针
scanf("%d",&x);
}
return L;
}双链表
//用代码定义一个双链表
typedef struct DNode{
ElemType data;
struct DNode *prior,*next;
}; DNode,*DLinklist;初始化和判空操作
//初始化双链表
bool InitDLinklist(DLinklist &L){
L = (DNode *)malloc(sizeof(DNode))//分配一个头结点
if(L==NULL)
return false;
L->prior = NULL;
L->next = NULL;
return true;
}
//判空操作
bool Empty(DLinklist L){
if(L->next == NULL)
return true;
else
return false;
} 插入操作（后插）
bool InsertNextDNode(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;
} 
双链表的删除
//删除p的后继结点q
bool DeleteNextDNode(DNode *p){
if (p==NULL) return false;
DNode *q = p->next;//找到后继结点q
if (q==NULL) return false;//p没有后继
p->next=q->next;
if(q->next!=NULL)
q->next->prior=p;
free(q); //释放结点空间
return true;
}
循环链表
循环单链表
//循环单链表的初始化和判空
bool InitList(LinkList &L){
L = (LNode *)malloc(sizeof(LNode)); //创建头节点
if (L==NULL) return false;
L->next=L; //头节点next指向头结点
return true;
}
//判断结点p是否为循环单链表的表尾结点
bool Empty(LinkList &L，LNode *p){
if (p->next==L)
return true;
else
return false;
}
循环双链表
//初始化循环双链表
bool InitDLinklist(DLinklist &L){
L = (DNode *)malloc(sizeof(DNode))//分配一个头结点
if(L==NULL)
return false;
L->prior = L;//头结点的prior指向头结点
L->next = L;//头结点的next指向头结点
return true;
}
//判空操作
bool Empty(DLinklist L){
if(L->next == L)
return true;
else
return false;
}
//判断结点p是否为循环双链表的表尾结点
bool isTail(DLinklist L,DNode *p){
if(p->next==L)
return true;
else
return false;
}
