ZAM'S BLOG 2.3.3

鲸了！数据结构居然如此复杂！

栈

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
栈可以根据是否可以动态增加存储空间，分为动态栈和静态栈两种。

动态栈

动态栈是建立在 malloc 函数的基础之上的一种栈结构

动态栈的数据结构定义

1
2
3
4
5
6
7
8
9
10
11
typedef struct Node         //定义一个链表式结点结构体
{
    int data;
    struct Node * last;
}*node;

typedef struct Stack        //定义链式栈结构体
{
    node top;               //栈顶指针
    int count;              //记录栈结点数量
}stack;

由于动态栈的数据是可以变化的。因此在动态栈中是没有 init()操作的，每一次 push 操作都会使得动态栈的大小动态扩大。

动态栈的入栈操作函数

1
2
3
4
5
6
7
8
void push(stack *S,int n)
{
	node curs = (node)malloc(sizeof(struct Node));//开辟新的存储空间用来存放链式表节点
	curs -> data = n;//存入节点
	curs -> last = S->top;
	S -> top = curs;//更新top指针
	S -> count ++;
}

动态栈的出栈操作函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int pop(stack *S){
    int output;
    node curs;                        //定义一个结点指针变量
    if(S->count == 0){              //判断栈是否为空
      printf("Error,Stack is empty!\n");
      exit(1);
    }
	  curs = S->top;                //让新定义的结点指针指向当前栈顶
    output = curs->data;          //保存当前节点的数据
	  S->top = curs->last;            //让栈顶指针指向栈顶结点的上一个结点
	  free(curs);                   //释放结点s的存储空间
	  S->count--;                //结点个数减一
    return output;             //返回栈顶元素
}

动态栈的取栈顶元素函数

1
2
3
4
5
6
7
8
9
int Gettop(stack *S)
{
    if(S->count == 0)                //判断栈是否为空
    {
	     printf("Error,Stack is empty!\n");
	     exit(1);
    }
    return S->top->data;
}

静态栈

静态栈是建立在静态数组的基础之上的一种栈结构。

静态栈的数据结构定义

1
2
3
4
5
6
#define MAXSIZE 1000
typedef struct Stack     //定义栈
{
    int data[MAXSIZE];   //栈中的数据
    int top;             //栈顶
}stack;

静态栈的初始化函数

1
2
3
4
5
stack Init(){             //初始化栈
    stack s;
    s->top = -1;
    return s;
}

静态栈的进栈操作函数

1
2
3
4
5
6
7
8
9
10
11
12
int Push(stack &s,int n){        //进栈操作，我们是对指针进行操作，因此需要添加取地址符
  if(s->top == P-1){              //进栈的时候必须判断是否栈满
    printf("stack full\n");
    exit(1);
  }
  s->top++;
  s->data[s->top] = n;             //将数据放入数组中
	if(s->top == P-1){              //进栈结束的时候判断是否栈满
		return 0;
	}
	return 1;
}

注意 由于静态表并不会自动增加存储空间，因此我们需要在进栈结束后判断栈是否已满，避免发生溢出情况。

静态栈的出栈操作函数

1
2
3
4
5
6
7
8
9
10
int Pop(stack &s){                      //出栈操作
  int n;                                //出栈元素
  if(s->top == -1){                     //出栈的时候必须判断是否栈空,避免数组越界
    printf("stack empty\n");
		exit(1);
	}
    n = s->data[s->top];
    s->top--;
    return n;
}

静态栈的取栈顶元素函数

1
2
3
4
5
6
7
int Gettop(stack *s){
  if(s->top == -1){                //判断栈是否为空
	   printf("Error,Stack is empty!\n");
	   exit(1);
    }
    return s->data[s->top];
}

栈的应用

LeetCode 20 有效的括号

思路

遇左括号就入栈，遇右括号就把栈顶元素拿出来比对。
如果栈空（用 top 指针判断）,则为 True。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool isValid(char * s){
    if( s == NULL )
        return false;
    char * stack = (char * ) malloc( sizeof(char) * ( strlen(s)+1 ) );
    int top = 0;
    for( int i=0; s[i]!='\0'; i++)
    {
        if(s[i]=='(' || s[i]=='[' || s[i]=='{') //左括号入栈
            stack[++top] = s[i];
        else if( (s[i]==')'&&stack[top]=='(') || (s[i]==']'&&stack[top]=='[') || (s[i]=='}'&&stack[top]=='{') ) //右括号比对
            top--;
        else    //比对失败
            return false;
    }
    if( stack!= NULL)
    {
        free(stack);
        stack = NULL;
    }
    if( top == 0 )  //字符串结束且栈空
        return true;
    else
        return false;
}

LeetCode 150 逆波兰表达式求值

思路

写个循环遍历字符串
碰到数字就压进栈
遇到运算符就把栈顶的两个元素弹出来
然后算了之后的结果再压进去
直到最后把栈里的最后一个元素输出即可

代码

这题真的很迷，每次运行都报数组越界，无奈只好放弃，就把有 bug 的源代码贴上来好了
报错信息

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int evalRPN(char ** tokens, int tokensSize){
    int stack[10000], top = 0;//使用数组实现栈
    int num1, num2;
    int i;
    for(i = 0; i < tokensSize; i++){
        if(tokens[i] == '+' || tokens[i] == '-' || tokens[i] == '*' || tokens[i] == '/'){//如果碰到运算符
            num2 = stack[--top]; //将栈中的顶部两元素pop
            num1 = stack[--top];//先出栈的是除数/减数，后出栈的是被除数/除数
            switch(tokens[i][0]){//用switch_case语句确定不同运算情况
                case '-' :
                    stack[top++] = num1 - num2;
                    break;
                case '+' :
                    stack[top++] = num1 + num2;
                    break;
                case '* ' :
                    stack[top++] = num1 * num2;
                    break;
                case '/' :
                    stack[top++] = num1 / num2;
                    break;
            }
        }
        else{
            stack[top++] = atoi(tokens[i]);//将字符串中的字符转化为数字push进栈
        }
    }
    return stack[--top];//将最终结果返回
}

队列

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

队列的实现

队列的数据结构定义

1
2
3
4
5
6
7
8
9
10
typedef struct Node//数据域
{
    int data;
    struct Node * next;
}Node,*DNode;
typedef struct Queue//指针域
{
    DNode front;
    DNode rear;
}Queue,*DQueue;

队列的初始化函数

1
2
3
4
void initQueue(DQueue Q){
    Q=(DQueue)malloc(sizeof(Queue));//申请队节点的内存空间
    Q->front=Q->rear=NULL;
}

队列的入队操作函数

1
2
3
4
5
6
7
8
9
10
11
12
void inQueue(DQueue Q,int n){
    DNode q;
    q=(DNode)malloc(sizeof(Node));  //申请队节点的内存空间
    q->next=NULL;
    q->data=n;将值放入节点中
    if(Q->rear==NULL)               //判断如果队空，则插入结点为队首结点
        Q->front=Q->rear=q;
    else{                           //若队不为空，尾指针所指的结点的next连接上q，同时后移尾指针
        Q->rear->next=q;
        Q->rear=q;
    }
}

由于队的存储空间大小是动态变化的，因此我们不需要判断队列是否已满。

队列的出队操作函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int outQueue(DQueue Q,int x){
    if(Q->front==NULL || Q->rear==NULL)     //判断队列是否为空
        return -1;
    DNode q;
    //出队结点是front指向的结点,用一个结点q存储和释放出队结点
    q=Q->front;
    //判断是否仅有一个结点
    if(Q->front==Q->rear)
        Q->front=Q->rear=NULL;//仅有一节点则该元素出队后队列即空
    else
        Q->front=Q->front->next;//将front指针指向下一个节点
    x=q->data;
    free(q);                                //释放节点内存空间
    return x;
}

队列的取队尾元素函数

1
2
3
4
5
int getFront(DQueue Q){
    if(Q->front==NULL || Q->rear==NULL)     //判断队列是否为空
        return -1;
    return Q->front->data;
}

队列的应用

LeetCode 21 合并两个有序链表

思路

定义一个新链表。
比较两个原链表中元素的大小，并把它放到新链表中。
然后再把放入了新元素的链表的指针向后移一个节点，没有放入新元素的链表的指针不动。
如果一个链表指针已经指向队尾，那么就把另外一个链表之后的所有节点原封不动全部放入新链表中。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    struct ListNode output;
    output.next = NULL;
    struct ListNode * ear = &output;
    struct ListNode * node = NULL;

    while(l1 && l2){
        rear->next = l1->val < l2->val ? l1 : l2;

        if(l1->val < l2->val){
            l1 = l1->next;
        }
        else{
            l2 = l2->next;
        }
        rear = rear->next;
    }
    if(l1){
        rear->next = l1;
    }
    if(l2){
        rear->next = l2;
    }
    return output.next;
}

LeetCode 2 两数相加

思路

懒得写了全部写在代码的注释当中……

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

int value = 0;//使用全局变量，来实现进位

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){//使用递归将链表各个对应的元素相加
    if(l1==NULL&&l2==NULL&&value==0){//判断输入的链表节点是否已经超过的链表的末尾，是否还有没存入最终输出链表的元素
        return NULL;
    }
    if(l1!=NULL){
        value+=l1->val;//如果当前链表节点存在，则把它的值取出来加到value上
        l1=l1->next;//使得指针指向下一个节点
    }
    else{
        value+=0;
    };
    if(l2!=NULL){
        value+=l2->val;
        l2=l2->next;
    }
    else{
        value+=0;
    }
    struct ListNode *outList=(struct ListNode *)malloc(sizeof(struct ListNode));//开辟数组空间储存当前的链表节点
    outList->val=value%10;//使用取模计算符保证val的值是value的个位数部分
    value=value/10;//使用整除来保存value中需要进位的十位数的值
    outList->next=addTwoNumbers(l1,l2);
    return outList;
}

还有两道困难题……

就先咕为敬了，告辞
有空再补
咕咕咕


博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：http://blog.zam-meow.cn/2019/11/02/AST-Task3/

评论




博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本站使用 Zam's Blog 作为主题，总访问量为 次
字数统计：47k 载入天数...载入时分秒...

Copyright © 2019-2021 Zam