数据结构(C语言版)第一部分——线性表基本概念及操作
1、基本概念
- 定义：具有相同特性数据元素的有限序列，所含元素的个数就是长度，长度可以为零。
- 逻辑特性：一个表头，一个表尾，表头无前驱，表尾无后继，其他元素一个前驱一个后继。
- 存储结构：顺序存储和链式存储（顺序表和链表）
顺序表：
按其逻辑顺序，存储于一块连续的存储空间
随机访问特性
存储分配预先进行，操作过程始终不变
随机增删较慢，需要移动元素
链表：
每个结点存储元素信息和元素之间逻辑信息
不支持随机访问
随机增删较快，不需要移动元素
节点的存储空间利用率较顺序表稍低
存储空间动态分配
链表的五种形式
- 单链表
每个结点出来数据域外，还有一个指针域，指向后继结点
带头结点的单链表：头指针指向头结点，头结点不存储数据
不带头结点的单链表：头指针直接指向开始结点
单链表只能从头走到尾
- 双链表
在单链表的基础上又增加了一个指针域指向前驱结点，方便由后往前
同单链表，分为是否有头结点
- 循环单链表
将单链表最后一个结点的指针域指向了链表中的第一个结点
它可以从任何一个结点出发访问任何结点
- 循环双链表
双链表终端结点的 next 指向第一个结点，第一个结点的 prior 指向终端结点
- 静态链表
静态链表借助一维数组表示
每一个结点包含两个分量：数据data， 整型变量指针（找后继结点）
2、基本定义
- 定义结构体
//定义常量
#define maxSize 100
//顺序表定义结构体
typedef struct
{
int data[maxSize];
int length;
}Sqlist;
//简洁定义
int A[maxSize];
int n;
- 单链表结点定义
typedef struct LNode
{
int data;
//指针
struct LNode *next;
}LNode;
- 单链表结点定义
typedef struct DLNode
{
int data;
//指针
struct DLNode *prior;
struct DLNode *next;
}DLNode;
- 例：定义一个名字为 A 的指针和 LNode 型结点，A 当做这个结点的名字
LNode *A = (LNode*)malloc(sizeof(LNode));
3、顺序表操作
- 初始化顺序表
void initList(Sqlist &L) //L本身要发生变化，所以用引用型
{
L.length=0;
}
- 按元素的值查找
int findElem(Sqlist L,int e)
{
int i;
for(i=0;i<L.length;++i)
if(e == L.data[i])
return i;
return -1;
}
- 插入数据元素
//L本身要发生变化，所以用引用型
int insertElem(Sqlist &L,int p,int e)
{
int i;
if(p<0 || p>L.length || L.length == maxSize)
return 0;
//后移腾出位置
for(i=L.length-1;i>=p;--i)
L.data[i+1] = L.data[i];
//插入，长度+1
L.data[p] = e;
++(L.length);
return 1;
}
- 删除下标p元素，并赋值给e
//需要改变的变量用引用型
int deleteElem(Sqlist &L,int p,int &e)
{
int i;
if(p<0 || p>L.length-1)
return 0;
e=L.data[p];
for(i=p;i<L.length-1;++i)
L.data[i]=L.data[i+1];
--(L.length);
return 1;
}
4、单链表的操作
- 尾插法建立链表，元素在数组a中
void createlistR(LNode *&C,int a[],int n)
{
LNode *s,*r; //s指向新申请的结点，r指向c的终端结点
int i;
C=(LNode *)malloc(sizeof(LNode));
C->next = NULL;
r=C;
for(i=0;i<n;++i)
{
s=(LNode *)malloc(sizeof(LNode));
s->data = a[i];
r->next=s;
r=r->next;
}
r->next=NULL;
}
- 头插法
void createlistF(LNode *&c,int a[],int n)
{
LNode *s;
int i;
C=(LNode *)malloc(sizeof(LNode));
C->next = NULL;
for(i=0;i<n;++i)
{
s=(LNode *)malloc(sizeof(LNode));
s->data = a[i];
//关键步骤
s->next = p->next;
p->next = s;
}
}
- A、B两个递增链表（带头结点），归并成非递减C链表
void merge(LNode *A,LNode *B,LNode *&C)
{
LNode *p = A->next;
LNode *q = B->next;
LNode *r; //r始终指向C的末端
//用A的头作为C的头
C=A;
C->next = NULL;
r=C;
//B的头结点就没有用了
free(B);
while(p!=NULL && q!=NULL)
{
if(p->data <= q->data)
{
r->next=p;
p=p->next;
r=r->next;
}else{
r->next=q;
q=q->next;
r=r->next;
}
}
r->next = NULL;
//剩余结点
if(p!=NULL) r->next = p;
if(q!=NULL) r->next = q;
}
- 删除结点（修改指针后，还有释放空间）
//p为删除结点的前驱结点，则
q = p->next;
p->next = p->next->next;
free(q);
5、双链表操作
- 尾插法建立双链表
void createDlistR(DLNode *&L,int a[],int n)
{
DLNode *s,*r;
int i;
L=(DLNode*)malloc(sizeof(DLNode));
L->prior = NULL;
L->next = NULL;
r=L; //r指向终端结点
for(i=0;i<n;++i)
{
s=(DLNode*)malloc(sizeof(DLNode));
s->data = a[i];
r->next = s;
s->prior=r;
r=s;
}
r->next=NULL;
}
- 查找结点
DLNode* findNode(DLNode *C,int x)
{
DLNode *p=C->next;
while(p!=NULL)
{
if(p->data == x)
break;
p=p->next;
}
return p;
}
- 插入结点（p结点后插入结点s）
s->next = p->next;
s->prior = p;
p->next = s;
s->next->prior = s;
- 删除结点（删除p的后继结点）
q = p->next;
p->next = q->next;
q->next->prior = p;
free(q);
OVER(∩_∩)O哈哈~