数据结构之链表、栈
数据结构之链表、栈
·
-
- 链表
【1】线性表
分为顺序存储和链式存储
链表是一种基础的数据结构类型，一种能够动态维护数据的线性数据表。链表的数据以结点形式存储信息，并通过结点之间的指针实现结点之间的衔接。
为什么要用链表？
链表和数组类似，但是功能比数组强大得多，数组的空间是固定的，在定义数组的时候，数组的大小已经被固定，在使用时有可能会造成空间的浪费或者面临空间不够的风险，而链表的空间是动态的，则避免了这一问题。
【2】逻辑结构
【3】操作
（1）尾部插入
head-101 -103-null
102
[1]102-next=103:
head-101 -103-null
102-103
[2]101-next=102:
head-101 -102-103-null
[-1]101-next=102:
h-101-102 null
头部插入
head=101
101(head)-102-103
100
100-n=101
head=100
虚拟头结点
head->dataXXXX
->next
dummyhead-101-102-103
100
101(head)-102-103
100
d-101
100
99-101
100
（2）中间插入
（3）头部插入
（4）删除
b-c-d
[1]b-next=b-n-n
[1]c=b-n,
b-n=c-n
单指针、双指针
0==false,1,2,3,-1==true
p=head
while((n-1)--){
for(i=0,i<=n-1,i++)
p=p-n}
//p=b
p-n=p-n-n
free(c)
p=head-n
pr=head
while(n--)
p=p-n
while n-1--
pr=pr-n
pr双指针
//p=c,pr=b
pr-n=p-n
【4】C
#include <stdio.h>
#include <stdlib.h>
struct link* AppendNode(struct link* head);
void DisplayNode(struct link* head);
void DeleteMemory(struct link* head);
struct link* DeleteNode(struct link* head,int nodeData);
struct link* InsertNode(struct link* head, int nodeData);
struct link
{
int data;
struct link* next;
};
int main() {
struct link* head = NULL;
printf("Do you want to append a new node(Y/N)?");
char c;
scanf("%c", &c);
while (c == 'Y' || c == 'y') {
head = AppendNode(head);
DisplayNode(head);
printf("Do you want to append a new node(Y/N)?");
scanf("%c", &c);
}
DeleteMemory(head);
}
//malloc、free
//分配内存：成功时返回内存段首地址，否则返回NULL
//p1 = (int*)malloc(n*sizeof(int));
//p2 = (struct link*)malloc(sizeof(struct link));
//free(p1);
//free(p2);
//末位加节点
struct link* AppendNode(struct link* head) {
struct link* p = NULL, * pr = head;
p = (struct link*)malloc(sizeof(struct link));
if (p == NULL) {
printf("No enough memory to allocate!\n");
exit(0);
}
//避免NULL->next
if (head == NULL) head = p;
else {
while (pr->next != NULL) pr = pr->next;
pr->next = p;
}
int data;
printf("Input node data:");
scanf("%d", &data);
p->data = data;
p->next = NULL;
return head;
}
void DisplayNode(struct link* head) {
struct link* p = head;
while (p != NULL) {
printf("%d\n", p->data);
p = p->next;
}
}
void DeleteMemory(struct link* head) {
struct link* p = head, * pr = NULL;
while (p != NULL) {
pr = p;
p = p->next;
free(pr);
}
}
删除=遍历+释放
a-b-c-d
p=a
pr=nul
双指针
pr=a
p=b
free(a)
p=c
struct link* DeleteNode(struct link* head, int nodeData) {
struct link* p = head, * pr = head;
if (head == NULL) {
printf("Empty!\n");
return head;
}
while (nodeData != p->data && p->next != NULL) {
pr = p;
p = p->next;
}
// ...->pr->p->...
if (nodeData == p->data) {
if (p == head) head = p->next;
else pr->next = p->next;
free(p);
}
else printf("Not founded!\n");
return head;
}
//已按升序排列的链表中插入新节点1,3,5,7,9 8
struct link* InsertNode(struct link* head, int nodeData) {
struct link* p = head, * pr = head, * tmp = NULL;
p = (struct link*)malloc(sizeof(struct link));
if (p == NULL) {
printf("No enough memory!\n");
exit(0);
}
p->next = NULL;
p->data = nodeData;
if (head == NULL) head = p;
else {
while (pr->data < nodeData && pr->next != NULL) {
tmp = pr;
pr = pr->next;
}
if (pr->data >= nodeData) {
if (pr == head) {
pr->next = head;
head = p;
}
else {
pr = tmp;
p->next = pr->next;
pr->next = p;
}
}
else pr->next = p;
}
return head;
}【5】C++
#include<iostream>
using namespace std;
class MyLinkedList {
public:
struct LinkedNode {
int val;
LinkedNode* next;
LinkedNode(int x) : val(x), next(nullptr) {}
};
MyLinkedList() {
_dummyHead = new LinkedNode(0);
_size = 0;
}
int get(int index) {
if (index > (_size - 1) || index < 0) return -1;
LinkedNode* p = _dummyHead->next;
while (index--) p = p->next;
return p->val;
}
void addAtHead(int val) {
LinkedNode* p = new LinkedNode(val);
p->next= _dummyHead->next;
_dummyHead->next = p;
++_size;
}
void addAtTail(int val) {
LinkedNode* q = new LinkedNode(val);
LinkedNode* p = _dummyHead;
while (p->next)p = p->next;
p->next = q;
++_size;
}
void addAtIndex(int index, int val) {
if (index > _size || index < 0) return;
LinkedNode* q = new LinkedNode(val);
LinkedNode* p = _dummyHead;
while (index--)p = p->next;
q->next = p->next;
p->next = q;
++_size;
}
void deleteAtIndex(int index) {
if (index > (_size - 1) || index < 0) return ;
LinkedNode* p = _dummyHead;
while (index--) p = p->next;
LinkedNode* q = p->next;
p->next = p->next->next;
delete q;
--_size;
}
void printList() {
LinkedNode* p = _dummyHead->next;
while (p) {
cout << p->val<<' ';
p = p->next;
}
cout << endl;
}
void reverseList() {
LinkedNode* head = _dummyHead->next;
if (!head || !head->next) printList();
else if (!head->next->next) {
LinkedNode* p = _dummyHead->next->next;
p->next = _dummyHead->next;
_dummyHead->next->next = NULL;
_dummyHead->next = p;
printList();
}
else {
LinkedNode* p = head, * q = p->next, * r = q->next;
p->next = NULL;
while (r) {
q->next = p;
p = q;
q = r;
r = r->next;
}
_dummyHead->next = q;
_dummyHead->next->next = p;
printList();
}
}
dh-a-b-c-d-e-null dh-e-d-c-b-a-null
private:
int _size;
LinkedNode* _dummyHead;
};
int main() {
MyLinkedList* obj = new MyLinkedList();
obj->addAtTail(1);
obj->addAtTail(2);
obj->addAtTail(3);
obj->addAtTail(4);
obj->addAtTail(5);
obj->printList();
obj->reverseList();
}
//Your MyLinkedList object will be instantiated and called as such:
//MyLinkedList* obj = new MyLinkedList();
//int param_1 = obj->get(index);
//obj->addAtHead(val);
//obj->addAtTail(val);
//obj->addAtIndex(index,val);
//obj->deleteAtIndex(index);
【6】员工信息
void test()
{
struct list *head;
struct staff *people1,*people2;
//初始化链表
head=List_Init(NULL);//头节点不存储数据，参数为NULL
people1=(struct staff *)malloc(sizeof(struct staff));
people2=(struct staff *)malloc(sizeof(struct staff));
people1->iStaffID=1001;
strcpy(people1->acName,"张三");
strcpy(people1->acPasswd,"123456");
people2->iStaffID=1002;
strcpy(people2->acName,"李四");
strcpy(people2->acPasswd,"123456");
//添加链表节点
List_Add(head,people1);
List_Add(head,people2);
//员工信息打印函数
Staff_Print(head);
}
-
- 栈
【1】逻辑结构(LIFO)
【2】memcpy
memcpy(&stack->data[stack->top], &data, sizeof(NodeType));【3】C
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
#define INT 1
#define FLT 2
#define N 20
typedef struct node {
int ival;
}NodeType;
typedef struct stack {
NodeType data[N];
int top;
}Stack;
void Push(Stack* stack, NodeType data);
NodeType Pop(Stack* stack);
NodeType OpInt(int d1, int d2, int op);
NodeType OpData(NodeType* d1, NodeType* d2, int op);
int main() {
char word[N];
NodeType d1, d2, d3;
Stack stack;
stack.top = 0;
while (scanf("%s", word) == 1 && word[0] != '#') {
if (isdigit(word[0])) {
d1.ival = atoi(word);
Push(&stack, d1);
}
else {
d2 = Pop(&stack);
d1 = Pop(&stack);
d3 = OpData(&d1, &d2, word[0]);
Push(&stack, d3);
}
}
d1 = Pop(&stack);
printf("%d\n", d1.ival);
return 0;
}
void Push(Stack* stack, NodeType data) {
memcpy(&stack->data[stack->top], &data, sizeof(NodeType));
stack->top = stack->top + 1;
}
NodeType Pop(Stack* stack) {
stack->top = stack->top - 1;
return stack->data[stack->top];
}
NodeType OpInt(int d1, int d2, int op) {
NodeType res;
switch (op) {
case'+':
res.ival = d1 + d2;
break;
case'-':
res.ival = d1 - d2;
break;
case'*':
res.ival = d1 * d2;
break;
case'/':
res.ival = d1 / d2;
break;
}
return res;
}
NodeType OpData(NodeType* d1, NodeType* d2, int op) {
NodeType res;
res = OpInt(d1->ival, d2->ival, op);
return res;
}【4】有效括号C++
class Solution {
public:
bool isValid(string s) {
if (s.size() % 2 != 0) return false;
stack<char> st;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(') st.push(')');
else if (s[i] == '{') st.push('}');
else if (s[i] == '[') st.push(']');
else if (st.empty() || st.top() != s[i]) return false;
else st.pop();
}
return st.empty();
}
};【5】逆波兰表达式C++
逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
逆波兰表达式主要有以下两个优点：
去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> st;
for (int i = 0; i < tokens.size(); i++) {
if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
int num1 = st.top();
st.pop();
int num2 = st.top();
st.pop();
if (tokens[i] == "+") st.push(num2 + num1);
if (tokens[i] == "-") st.push(num2 - num1);
if (tokens[i] == "*") st.push(num2 * num1);
if (tokens[i] == "/") st.push(num2 / num1);
} else {
st.push(stoi(tokens[i]));
}
}
int result = st.top();
st.pop();
return result;
}
};3.队列
4.codeblocks快捷键
Ctrl + A：全选
Ctrl + C：复制
Ctrl + X: 剪切
Ctrl + V：粘贴
Ctrl + Z：撤销
Ctrl + S：保存
Ctrl + Y / Ctrl + Shift + Z:重做
Ctrl+Shift+C：注释掉当前行或选中块
Ctrl+Shift+X：解除注释
Tab：缩进当前行或选中块
Shift+Tab：减少缩进
按住Ctrl，滚动鼠标滚轮，放大或缩小字体
F8：debug
Ctrl + C：终止正在运行的程序
Ctrl + Z：终止输入
F5：在当前光标所在行设置断点
F4：运行到光标所在行
F8：开始调试
Shift + F8：停止调试
F7：下一行代码
Shift + F7：进入下一行代码
代码格式化：
5.资源
【1】真题
公众号：哈工大网盘计划
【2】bilibili
程序设计：浙大翁恺
数据结构：王道论坛
算法：代码随想录
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
0
0- 0
已为社区贡献1条内容
所有评论(0)