数据结构-栈、队列和链表

一、栈stack

  1. 是后进先出的数据结构
  2. 栈顶指针指的始终是栈最上方元素的一个标记,即放在最上面的元素。栈顶元素为空时令top为-1.
  3. 在使用pop()函数和top()函数时,需要使用empty()判断栈是否为空。
  4. 在STL中stack容器来编写代码,STL定义stack的复杂度是O(1)。
  5. 常见函数:
    • clear()
    • size()
    • empty()
    • push()
    • pop()
    • top()

二、队列queue

  1. 是一种先进先出的数据结构
  2. 需要一个队首指针front来指向队首元素的前一个位置,而使用一个队尾指针rear来指向队尾元素。
  3. 同样可以在STL中使用queue容器进行使用,定义的queue的复杂度是O(1)
  4. 同样在pop()前需要使用empty()进行判断是否为空。
  5. 常见函数:
    • clear()
    • size()
    • empty()
    • push()
    • pop()
    • front()取队首元素,这里已经是直接在队首指针的基础上加1了,然后得到的直接是队首元素。
    • rear()而这里队尾指针指的直接是队尾元素,所以不用加减。

三、链表

1. 我们使用的链表一般是数据域和指针域组成

2. 使用malloc函数(C语言中)和new运算符(C++中)

1. malloc()函数是C语言中stdlib.h用于申请动态内存的函数,其返回的类型是同变量类型的指针。如果申请失败,就会返回空指针NULL
2.  new是C++中用来申请动态空间的运算符,其返回类型同样是申请的同样变量类型指针。如果申请失败会启动C++中异常机制处理而不是返回空指针NULL
3.  内存泄漏是指使用malloc与new开辟出来的空间在使用过后没有释放,导致其在程序结束前始终占据空间。
4.  free()是对应于malloc函数,在stdlib.h中,只需要在free的参数中填写需要释放的内存空间的指针变量即可。free函数只要实现两个效果:<1>释放指针变量p所指向的内存空间;<2>将指针变量p指向空地址NULL。在free函数执行之后,指针变量p本身没有消失,只不过让他指向了空地址NULL,但是它原指向的内存确实被释放。
5.  delete运算符是对应new运算符的,使用方法和free相同。
6.  一般是成对出现的,但是在考试中一般是内存够使用的,但是在实际情况中可以注意。
malloc
typename* p = (typrname*)malloc(sizeof(typename));
以int和node类型为例子
int* p = (int*)malloc(sizeof(int));
node* p = (node*)malloc(sizeof(node));
free(p)


new
typename* p = new typename;
int* p = new int;
node* p = new node;
delete(p)

3. 链表的基本操作

1.创建链表
#inlcude<stdio.h>
#include<stdlib.h>
struct node{
    int data;
    node* next;
};
//创建链表
node* create(int Array[]){
    node *p, *pre, *head;//pre保存当前结点的前驱结点,head为头结点
    head = new node;
    head->next = NULL;//头结点不需要数据域,指针域初始为NULL
    pre = head;//记录pre为head
    for(int i = 0; i < 5; i++){
        p = new node;//新建结点
        //将Array[i]赋值给新建的结点作为数据域,也可以scanf输入
        p->data = Array[i];
        p->next = NULL;
        pre->next = p;//前驱结点的指针域设为当前新建结点的地址
        pre = p;
    }
    return head;
}
int main(){
    int Array[5] = {5, 3, 6, 1, 2};
    node* L = create(Array);//新建链表,返回的头指针head赋给L;
    L = L->next;
    while(L != NULL){
        printf("%d", L->data);
        L = L->next;
    }
    return 0;
}
2.查找元素
//以head为头结点的链表上计数元素的个数
int search(node* head, int x){
    int count = 0;//计数器
    node* p = head->next;//从第一个结点开始
    while(p != NULL){
        if(p->data == x){
            count++;
        }
        p = p->next;//指针移动到下一个结点
    }
    return count;//返回计数器count
}
3.插入元素
void insert(node* head, int pos, int x){
    node* p = head();
    for(int i = 0; i < pos-1; i++){
        p = p->next;//pos-1是为了到插入位置的前一个结点
    }
    node* q = new node;//新建结点
    q->data = x;//新结点的数据域为x
    q->next = p->next;//新结点的下一个结点指向原先插入位置的结点
    p->next = q;//前一个结点指向新结点
}
4.删除元素
//删除以head为头结点的链表中所有数据域为x的结点
void del(node* head, int x){
    node* p = head->next;//从第一个结点开始枚举
    node* pre = head;//pre保存p的前驱结点的指针
    while(p != NULL){
        if(p -> data == x){
            pre->next = p->next;
            delete(p);
            p = pre->next;
        }else{
            pre = p;
            p = p->next;
        }
    }
}

相关推荐