从零开始的数据结构与算法（C）(1)
一.线性表
文章目录
1.顺序表及其算法实现
(1).抽象类型的设计
Const int MAXSIZE = 顺序表的容量
typedef struct
{
datatype data[MAXSIZE];
int last;
}SeqList;
(2).顺序表的初始化
SeqList * init_SeqList(){
SeqList *L;
L = malloc(sizeof(SeqList));
L->last = -1;
return L;
}
(3).插入运算
/*
@Param L:要操作的线性表
@Param i:要插入元素的位置
@Param x:要插入的元素值
@Return:插入成功返回1，插入失败返回其他
*/
int Insert_SeqList(SeqList *L,int i,datatype x){
//表满
if(L->last = MAXSIZE-1){
return (-1);
}
//插入位置不正确
if(i < 1||i > L->last+2){
return 0;
}
for(int j = L->last;j > i-1;j--){
L->data[j+1] = L->data[j];
}
datatype[i-1] = x;
L->last++;
return 1;
}
(4).删除运算
/*
@Param L:要操作的线性表
@Param i:要删除元素的位置
@Return:删除成功返回1，删除失败返回0
*/
int Delete_SeqList(SeqList *L,int i){
//表空或位置不存在
if(i < 1||i > L->next+1){
return 0;
}
for(j = i;j <= L->last;j++){
L->data[j-1] = L->data[j];
L->last--;
return 1;
}
}
(5).根据数值找位置
/*
@Param L:要操作的线性表
@Param x:要查找的数值
@Return:要查找数值的位置
*/
int Location_SeqList(SeqList *L,datatype x){
int i = 0;
while(i <= L->last&&L->data[i]!=x){
i++;
}
//没找到
if(i > L->Last){
return -1;
}
//找到了
else{
return i;
}
}
2.单链表
带头结点的单链表
(1).抽象类型的设计
typedef struct node
{
datatype data;
node *next;
}LNode,*LinkList;
(2).头插法建立单链表
/*
@Var L:新的链表
@Var s:新结点
@Return:创建好的单链表
*/
LinkList Create_LinkList1(){
LinkList L = NULL;//记录头结点
LNode *s;
int x;//存储元素的数据类型为int
scanf("%d",&x);
//输入是9999时结束录入
while(x != 9999){
s = malloc(sizeof(LNode));
s->data = x;
s->next = L;
L = s;
scanf("%d",&x);
}
return L;
}
(3).尾插法建立单链表
/*
@Var L:新的链表
@Var s:新结点
@Var r:始终指向尾结点
@Return:创建好的单链表
*/
LinkList Create_LinkList2(){
LinkList L = NULL;
LNode *s,*r=NULL;
int x;
scanf("%d",&x);
while(x != 9999){
s = malloc(sizeof(LNode));
s->data = x;
if(L == NULL){
L = s;
}else{
r->next = s;
}
r = s;
scanf("%d",&x);
}
if(r!=NULL){
r->next = NULL;
}
return L;
}
(4).求表长
带头结点的单链表
/*
@Param L:要操作的单链表
@Var count:记录链表的长度
@Return:链表的长度
*/
int Length_LinkList1(LinkList L){
LNode *p = L;
int count = 0;
while(p->next){
count++;
p = p->next;
}
return count;
}
不带头结点的单链表
/*
@Param L:要操作的单链表
@Var count:记录链表的长度
@Return:链表的长度
*/
int Length_LinkList2(LinkList L){
LNode *p = L;
int count = 0;
if(p==NULL){
return count;
}
count = 1;
while(p->next){
count++;
p = p->next;
}
return count;
}
(5).查找操作
/*
@Param i:查找的位置
@Return:查找到的结点
*/
LNode * Get_LinkList(LinkList L,int i){
LNode *p = L;
int count = 0;
while(p->next!=NULL&&count < i){
p = p->next;
count++;
}
if(count==i){
return p;
}
return null;
}
(6).按值查找定位
/*
@Param x:查找的元素
@Return:查找到的元素的位置
*/
LNode * Locate_LinkList(LinkList L,datatype x){
LNode *p = L->next;
while(p!=NULL&&p->data!=x){
p = p->next;
}
return p;
}
(7).插入操作
/*
@Param i:插入的位置
@Param x:插入的元素
@Return:插入成功返回1，失败返回0
@Var s:插入的新结点
@Var p:前驱结点
*/
int Insert_LinkList(LinkList L,int i,datatype x){
LNode *p,*s;
//找前驱元素
p = Get_LinkList(L,i-1);
if(p == NULL){
return 0;
}
s = malloc(sizeof(LNode));
s->data = x;
s->next = p->next;
p->next = s;
return 1;
}
(8).删除操作
/*
@Param i:删除的位置
@Return:删除成功返回1，失败返回0
@Var s:需要删除的结点
@Var p:前驱结点
*/
int Del_LinkList(LinkList L,int i){
LinkList p,s;
p = Get_LinkList(L,i-1);
if(p==NULL||p->next==NULL){
return 0;
}
s = p->next;
p = next = s->next;
free(s);
return 1;
}
3.循环链表
定义：在单链表的基础上，最后一个结点的next域连接上头结点，就构成了单循环链表。
(1).两个用尾指针标识的单循环链表的连接
/*
@Param R1:指向单循环链表L1的尾指针
@Param R2:指向单循环链表L2的尾指针
@Return:返回连接好的新链表的头指针
*/
LinkList merge(LNode *R1,LNode *R2){
if(R1 == NULL){
return R2
}
if(R2 == NULL){
return R1;
}
LNode *p = R1->next;//保存R1的头结点指针
R1->next = R2->next->next;//头尾连接
free(R2->next);//释放第二个表的头结点
R2->next = p;//组成新的循环链表
return p;
}
4.双向链表
(1).抽象类型的设计
typedef struct
{
datatype data;
struct dlnode *prior,*next;
}DLNode,*DLinkList;
(2).双向链表的插入操作
(与单链表类似，仅展示核心操作)
//*s是新结点，*p是要插入位置的后结点
s->prior = p->prior;//将插入前p的前一个结点赋给新结点s的前驱
s->next = p;//新结点的后继赋值为p
p->prior->next = s;//插入前p前一个结点的后继赋值为新结点
p->prior = s;//p的前驱赋值为新结点s
(3).双向链表的删除操作
(与单链表类似，仅展示核心操作)
//*p是要删除结点
p->prior->next = p->next;//让p的前驱元素的后继指向p的后继
p->next->prior = p->prior;//让p的后继元素的前驱指向p的前驱
free(p);
5.单链表经典算法
(1).链表反转
建立新的链表操作
算法思路：一次取原链表中的每个结点，将其作为第一个结点插入到新链表中取，指针p用来指向当前结点，p为空时结束。
void reverse(LinkList H){
LNode *p,*q;
*p = H->next;
H->next = NULL;
while(p){
q = p;
p = p->next;
q->next = H->next;
H->next = q;
}
}
在原有链表操作
LNode* reverse(LNode* head) {
struct LNode* prev = NULL;
struct LNode* curr = head;
while (curr) {
LNode* next = curr->next;//定义next指针指向头结点
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
递归版本（回溯思想）
struct LNode* reverse(struct LNode* head) {
if (head == NULL || head->next == NULL) {
return head;
}
struct LNode* newHead = reverse(head->next);
head->next->next = head;
head->next = NULL;
return newHead;
}
(2).删除重复结点
算法思路：用指针p指向第一个数据结点，从他的后继结点开始到表的结束，找到与其值相同的结点并删除，p指向下一个；以此类推，p指向最后结点时算法结束。
/*
@Var p:始终指向第一个结点
@Var q:遍历指针
@Var r:存储要删除的结点
*/
void pur_LinkList(LinkList H){
LNode *p,*q,*r;
p = H->next;
if(p==NULL) return;
while(p->next){
q = p;
while(q->next){
if(q->next->data==p->data){
r = q->next;
q->next = r->next;
free(r);
}
else{
q = q->next;
}
}
p = p->next;
}
}
6.顺序存储与链式存储的对比
顺序存储：
Ⅰ.方法简单，各大高级语言中都有数组，容易实现。
Ⅱ.不用为表示结点间的逻辑关系而增加额外的存储开销。
Ⅲ.顺序表有按照元素序号随机访问的特点。O(1)
Ⅳ.顺序表中做插入删除操作时，效率较低。O(n)
Ⅴ.需要预先分配足够大的存储空间，估计过大，会造成顺序表后部大量闲置；预分配过小，又会造成溢出。
链式存储：
Ⅰ.无需实现确定线性表长度，就可以编程实现线性表。
Ⅱ.允许线性表长度具有很强的可变性。
Ⅲ.采用链表的程序能够很方便进行插入，删除内部元素的操作。O(1)
7.顺序栈(数组实现的栈)
栈数据结构简介：
一种基于 先进后出（FILO) 原则 的数据结构。
(1).抽象类型的设计
#define MAXSIZE 1024
typedef struct
{
datatype data[MAXSIZE];//存储栈中元素的数组
int top;//指向栈顶的指针
}SeqStack;
(2).建立顺序栈
SeqStack * Init_SeqStack(){
SeqStack * s;
s = malloc(sizeof(SeqStack));
s->top = -1;//将栈顶指向-1(通常0下标设置为栈底)
return s;
}
(3).判空栈
/*
@Param *s:指向被操作的栈指针
@Return:为空返回1，反之返回0
*/
int Empty_SeqStack(SeqStack *s){
if(s->top == -1){
return 1;
}
return 0;
}
(4).元素入栈
/*
@Param *s:指向被操作的栈指针
@Param x:要入栈的元素
@Return:入栈成功返回1，反之返回0
*/
int Push_SeqStack(SeqStack *s,datatype x){
//栈满不得入栈
if(s->top == MAXSIZE-1){
return 0;
}
s->top++;//元素入栈，栈顶加一
s->data[s->top] = x;//栈顶元素赋值为x
return 1;
}
(5).元素出栈
/*
@Param *s:指向被操作的栈指针
@Param *x:存储出栈的元素，进行后续操作
@Return:出栈成功返回1，反之返回0
*/
int Pop_SeqStack(SeqStack *s,datatype *x){
//栈空不得出栈
if(Empty_SeqStack(s)){
return 0;
}
*x = s->data[s->top];
s->top--;
return 1;
}
(6).取栈顶元素
/*
@Param *s:指向被操作的栈指针
@Return:返回栈顶元素值
*/
Datatype Top_SeqStack(SeqStack *s){
if(Empty_SeqStack(s)){
return 0;
}
return s->data[s->top];
}
8.链式栈(链表实现的栈)
(1).抽象类型的设计
Typedef struct Node
{
datatype data;
struct Node *next;
}StackNode,*LinkStack;
//此外，添加top为栈顶指针：LinkStack top;
LinkStack top;
(2).建立链式栈
LinkStack Init_LinkStack(){
top = NULL;
return top;
}
(3).判空栈
/*
@Param top:指向栈顶的指针
@Return:栈空返回1，反之返回0
*/
int Empty_LinkStack(LinkStack top){
if(top==NULL){
return 1;
}
return 0;
}
(4).元素入栈
/*
@Param top:指向栈顶的指针
@Param x:要入栈的元素
@Return:返回新栈顶
*/
LinkStack Push_LinkStack(LinkStack top,datatype x){
StackNode * s;
s = malloc(sizeof(StackNode));
s->data = x;//给新指针的数据域赋值x
s->next = top;//新指针的指针域变为原来栈顶
top = s;//替换新栈顶
return top;
}
(5).元素出栈
/*
@Param top:指向栈顶的指针
@Param x:存储要出栈的元素，便于做其余操作
@Return:返回新栈顶
*/
LinkStack Pop_LinkStack(LinkStack top,datatype *x){
StackNode *p;//弹栈元素的指针，便于释放内存操作
if(Empty_LinkStack()){
return NULL;
}
*x = top->data;
p = top;
top = top->next;//置换新栈顶
free(p);
return top;
}
9.栈的应用举例
(1).数的进制转换：
题目要求：将十进制数N转换为R进制的数。
基本原理：N=(N/R)×R+N%R,使用辗转相除法，以N=3467，R=8为例。
栗子：
3467÷8 = 433…3
433÷8 = 54…1
54÷8 = 6…6
6÷8 = 0…6
∴ (3467)10 = (6613)8 ,余数出来的倒序是对应转换后的数，故采用栈数据结构。
void conversion(int N,int R){
SeqStack *s;
datatype *x;//存储弹出的元素值的指针
s = Init_SeqStack();
while(N!=0){
Push_SeqStack(s,N%R);
N = N/R;
}
while(!Empty_SeqStack(s)){
Pop_SeqStack(s,x);
printf("%d",x);
}
}
(2).迷宫算法
题目要求：心理学家将一只老鼠从一个无顶盖的大盒子入口赶进迷宫。迷宫中设置了许多墙壁，对前进方向形成了多种障碍，心理学家在迷宫的唯一出口处放置一块奶酪，吸引老鼠在迷宫中寻找通道以到达出口。
题目思想：采用回溯思想，回溯是一种不断试探且纠正错误的搜索方法，当一条路走不通时，返回上一个结点换另外的路。
求解过程中，为保证能正确返回到前一点，需要使用一个栈储存所能到达的每一点的下标及前进的方向。
迷宫的设计：当迷宫m行n列时，设计一个maze [m+2] [n+2]来表示迷宫，maze [i] [j] 为0或者1，0表示通路，1表示不通。四周多余的两行两列全部为1。（从(1,1)开始，到(m,n)终点）
试探方向的设计：每个点又八个方向去试探：上下左右，左上左下右上右下。使用一个结构体数组move[8]表示，在move数组中，每个元素有两个域组成，分别是x轴增量，和y轴增量。比如“右下”可以表示为move [1] [1]。
从而设计出增量数组(从正东开始为0)：
栈的设计：x,y用来表示某点的位置坐标，还需要一个成员变量d用来表示方向。
防止重复经过某点：当到达某点时，将该点数组值变为-1，以区别未到达的点。
//迷宫设计
#define m 6
#define n 8
int maze[m+2] [n+2];
//方向设计
typedef struct
{
int x,y;
}item;
item move[8];
//栈的设计
typedef struct
{
int x,y,d;
}datatype;
//算法设计
/*
@Param maze:迷宫数组
@Return :若迷宫有路，返回1，反之返回0
*/
int path(int maze[][]){
SeqStack *stack;//创建一个顺序栈指针
datatype temp;//位置信息
int x,y,d,i,j;
temp.x = 1,temp.y = 1,temp.d = -1;//设置起点信息
Push_SeqStack(stack,temp);
while(!Empty_SeqStack(stack)){
Pop_SeqStack(stack,&temp);
x = temp.x;
y = temp.y;
d = temp.d+1;//改变方向，测试各个方向是否通路
while(d < 8){
i = x+move[d].x;
j = y+move[d].y;//向指定方向移动一位
//如果走到通路
if(maze[i][j] == 0){
temp = {x,y,d};//存储位置信息
Push_SeqStack(stack,temp);//将位置信息存入栈中
x = i,y = j;//将位置信息更新
maze[x] [y] = -1;
//如果走到终点，返回1
if(x==m&&y==n){
return 1;
}
//没有走到终点，则将方向归零
d = 0;
}
//如果走到死路，变换方向，继续搜索
else{
d++;
}
}
}
//没有找到通路，返回0
return 0;
}
(3).后缀表达式
题目要求：根据 逆波兰表示法，求该后缀表达式的计算结果。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
比如：tokens = [“2”,“1”,"+",“3”,"*"]，该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9。
算法思路：对字符数组进行遍历，遍历到符号时，从栈中弹出两个值，进行对应的符号操作，遍历到其他字符时，将其压入栈。当栈空时，即可得出最终的计算结果。
/*
@Param *A:指向字符数组第一位的指针
@Return:返回最终的计算结果
@Var aint,bint:存储字符a,b的整型形式
@Var *result:指向结果的指针
@Var *ch:遍历数组的指针
*/
double evalRPN(char *A){
char *a,*b;//指向弹出的数字元素
double ad,bd;
double *result;
//创建和初始化栈
SeqStack *stack = Init_SeqStack();
char * ch = *A++;//存储数组下标0处的元素，并使指针向后移动一位
//如果没到终止符
while(ch!='#'){
switch(ch){
case '+':
Pop_SeqStack(stack,a);
Pop_SeqStack(stack,b);
ad = (double)*a;
bd = (double)*b;
Push_SeqStack(stack,ad+bd);
break;
case '-':
Pop_SeqStack(stack,a);
Pop_SeqStack(stack,b);
ad = (double)*a;
bd = (double)*b;
Push_SeqStack(stack,bd-ad);
break;
case '*':
Pop_SeqStack(stack,a);
Pop_SeqStack(stack,b);
ad = (double)*a;
bd = (double)*b;
Push_SeqStack(stack,ad*bd);
break;
case '/':
Pop_SeqStack(stack,a);
Pop_SeqStack(stack,b);
ad = (double)*a;
bd = (double)*b;
Push_SeqStack(stack,bd/ad);
break;
case '^':
Pop_SeqStack(stack,a);
Pop_SeqStack(stack,b);
ad = (double)*a;
bd = (double)*b;
Push_SeqStack(stack,bd^ad);
break;
default:
Push_SeqStack(stack,ch);
}
ch = *A++;
}
Pop_SeqStack(stack,result);
return *result;
}
10.顺序循环队列(数组实现的队列)
队列数据结构简介：
一种基于 先进先出（FIFO） 原则 的数据结构。
(1).抽象类型的设计
define MAXSIZE 1024
typedef struct
{
datatype data[MAXSIZE];
int rear,front;//队头队尾指针
}SeQueue;
SeQueue *sq;
sq = malloc(sizeof(SeQueue));
对头指针和尾指针的详解：
队头指针：
sq->front,设其指向队列头元素前面的一个位置。队尾指针：
sq->rear,设其指向队列尾元素。置空队列思想：
sq->front = sq->rear = -1不考虑溢出，入队列思想：
sq->rear++; sq->data[sq->rear] = x;不考虑队空，出队列思想：
sq->front++; x = sq->data[sq->front];队列中元素个数：
m = (sq->rear) - (sq->front);假溢出线象：随着队列的元素出入，队列整体向后移动，导致了虚假的满员，即栈溢出现象。为避免其现象发生，引入循环队列。
循环队列的相关操作简介：
循环队列：头尾相连的循环结构。
对循环队列来说：其相关操作可改为以下：
入队列思想：
sq->rear = (sq->rear+1) % MAXSIZE;出队列思想：
sq->front = (sq->front+1) % MAXSIZE;队满与队空条件：
front = rear区分队列满队列空可使用计数器，当计数器为0时为空，反之为满。
最终设计：
typedef struct
{
datatype data[MAXSIZE];
int front,rear;
int num;//队列中元素个数
}c_SeQueue;
(2).顺序队列初始化
/*
@Return:返回建立好的队列
*/
c_SeQueue* Init_SeQueue(){
c_SeQueue q = malloc(sizeof(c_SeQueue));
q->front = q->rear = MAXSIZE-1;
q->num = 0;
return q;
}
(3).元素入队
/*
@Param *q:指向要操作的队列
@Param x:需要入队的元素
@Return:入队列成功返回1，反之返回0
*/
int In_SeQueue(c_SeQueue *q,datatype x){
//队列满的情况
if(q->num == MAXSIZE){
return 0;
}
q->rear = (q->rear+1)%MAXSIZE;
q->data[q->rear] = x;
num++;
return 1;
}
(4).元素出队
/*
@Param *q:指向要操作的队列
@Param *x:指向需要出队的元素
@Return:出队列成功返回1，反之返回0
*/
int Out_SeQueue(c_SeQueue *q,datatype *x){
//队列空的情况
if(q->num == 0){
return 0;
}
q->front = (q->front+1) % MAXSIZE;
*x = q->data[q->front];
num--;
return 1;
}
(5).判空队列
/*
@Param *q:指向要操作的队列
@Return:队列为空返回1，否则返回0
*/
int Empty_SeQueue(c_SeQueue *q){
if(q->num == 0){
return 1;
}
return 0;
}
11.链式队列(链表实现的队列)
(1).抽象类型的设计
typedef struct node
{
datatype data;
struct node * next;
}QNode;
typedef struct
{
QNode *front,*rear;
}LQueue;
头尾指针声明：
头指针指向头结点，尾指针指向最后一个结点。
由此空队列的判断条件即为：头，尾指针均指向头结点。
(2).链式队列初始化：
/*
Return:返回创建好的链队列
*/
LQueue * Init_LQueue(){
LQueue *q;
QNode *p;
q = malloc(sizeof(LQueue));//头尾指针
p = malloc(sizeof(QNode));//头结点
p->next = NULL;
q->front = q->rear = p;
return q;
}
(3).元素入队
/*
@Param *q:指向要操作的队列
@Param x:需要入队的元素
*/
void In_LQueue(LQueue *q,datatype x){
QNode *p;
p = malloc(sizeof(QNode));
p->data = x;
p->next = NULL;
q->rear->next = p;
q->rear = p;
}
(4).判队列空
/*
@Param *q:指向要操作的队列
@Return:队列为空返回1，反之返回0
*/
int Empty_LQueue(LQueue *q){
if(q->front == q->rear){
return 1;
}
return 0;
}
(5).元素出队
/*
@Param *q:指向要操作的队列
@Param *x:指向需要出队的元素
@Return:出队列成功返回1，反之返回0
*/
int Out_LQueue(LQueue *q,datatype *x){
QNode *p;
//队空情况
if(Empty_LQueue(q)){
return 0;
}
p = q->front->next;//获取到要出队的结点
q->front->next = p->next;
*x = p->data;
free(p);
//如果队列只有一个结点，仍需修改队尾指针
if(q->front->next == NULL){
q->rear = q->front;
return 1;
}
}
12.一些关于线性表的例题
a.不带头结点的单链表head为空的判定条件是【head==NULL】。
b.带头结点的单链表head为空的判定条件是【head->next==NULL】。
c.若某表最常用的操作是在最后一个结点之后插入一个节点或者删除最后一个结点，则采用【带头结点的双循环链表】存储方式最省计算时间。
详解：带头结点的双循环链表可直接通过头结点的前驱访问到最后一个结点，随即进行插入或删除操作。
d.需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是【静态链表】。
e.在双循环链表中p所指的结点之前插入s所指结点的操作是【s->next = p,s->prior = p->prior,p->prior->next = s,p->prior = s】。
f.一个栈的进栈序列是a,b,c,d,e,则栈的不可能输出序列是【dceab】。
详解：a除非是开始就取出，否则不可能在b的前面被取出。
g.判断一个循环队列qu(最多元素为MAXSIZE)为空的条件是【qu->rear == qu->front】。
h.若用一个大小为6的数值来实现循环队列，且当前rear和front值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为【2，4】。
详解：删除一个元素，队头指针加1；增添一个元素，队尾指针加1。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
THE END
二维码