从零开始的数据结构与算法（C）(1)

一.线性表

文章目录

• 一.线性表
• • 1.顺序表及其算法实现
  • • (1).抽象类型的设计
    • (2).顺序表的初始化
    • (3).插入运算
    • (4).删除运算
    • (5).根据数值找位置
  • 2.单链表
  • • (1).抽象类型的设计
    • (2).头插法建立单链表
    • (3).尾插法建立单链表
    • (4).求表长
    • (5).查找操作
    • (6).按值查找定位
    • (7).插入操作
    • (8).删除操作
  • 3.循环链表
  • • (1).两个用尾指针标识的单循环链表的连接
  • 4.双向链表
  • • (1).抽象类型的设计
    • (2).双向链表的插入操作
    • (3).双向链表的删除操作
  • 5.单链表经典算法
  • • (1).链表反转
    • (2).删除重复结点
  • 6.顺序存储与链式存储的对比
  • 7.顺序栈(数组实现的栈)
  • • (1).抽象类型的设计
    • (2).建立顺序栈
    • (3).判空栈
    • (4).元素入栈
    • (5).元素出栈
    • (6).取栈顶元素
  • 8.链式栈(链表实现的栈)
  • • (1).抽象类型的设计
    • (2).建立链式栈
    • (3).判空栈
    • (4).元素入栈
    • (5).元素出栈
  • 9.栈的应用举例
  • • (1).数的进制转换：
    • (2).迷宫算法
    • (3).后缀表达式
  • 10.顺序循环队列(数组实现的队列)
  • • (1).抽象类型的设计
    • (2).顺序队列初始化
    • (3).元素入队
    • (4).元素出队
    • (5).判空队列
  • 11.链式队列(链表实现的队列)
  • • (1).抽象类型的设计
    • (2).链式队列初始化：
    • (3).元素入队
    • (4).判队列空
    • (5).元素出队
  • 12.一些关于线性表的例题

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).插入运算

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).删除运算

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).根据数值找位置

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).头插法建立单链表

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).尾插法建立单链表

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).求表长

带头结点的单链表

int Length_linkList1(linkList L){
    LNode *p = L;
    int count = 0;
    while(p->next){
        count++;
        p = p->next;
    }
    return count;
}

不带头结点的单链表

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).查找操作

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).按值查找定位

LNode * Locate_linkList(linkList L,datatype x){
    LNode *p = L->next;
    while(p!=NULL&&p->data!=x){
        p = p->next;
    }
    return p;
}

(7).插入操作

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).删除操作

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).两个用尾指针标识的单循环链表的连接

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).双向链表的插入操作

(与单链表类似，仅展示核心操作)
/
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).判空栈

int Empty_SeqStack(SeqStack *s){
    if(s->top == -1){
        return 1;
    }
    return 0;
}

(4).元素入栈

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).元素出栈

int Pop_SeqStack(SeqStack *s,datatype *x){
    //栈空不得出栈
    if(Empty_SeqStack(s)){
        return 0;
    }
    *x = s->data[s->top];
    s->top--;
    return 1;
}

(6).取栈顶元素

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).判空栈

int Empty_linkStack(linkStack top){
    if(top==NULL){
        return 1;
    }
    return 0;
}

(4).元素入栈

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).元素出栈

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;

//算法设计

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。

算法思路：对字符数组进行遍历，遍历到符号时，从栈中弹出两个值，进行对应的符号操作，遍历到其他字符时，将其压入栈。当栈空时，即可得出最终的计算结果。

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).顺序队列初始化

c_SeQueue* Init_SeQueue(){
    c_SeQueue q = malloc(sizeof(c_SeQueue));
    q->front = q->rear = MAXSIZE-1;
    q->num = 0;
    return q;
}

(3).元素入队

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).元素出队

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).判空队列

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).链式队列初始化：

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).元素入队

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).判队列空

int Empty_LQueue(LQueue *q){
    if(q->front == q->rear){
        return 1;
    }
    return 0;
}

(5).元素出队

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。