c/c++数据结构知识笔记

1. 数据结构 数学以及逻辑模型的抽象视觉的数据类型（ADT）

2.数据类的实现

抽象数据类型是对数据和操作的定义，不存在实现。

数据结构类型：数组、链表、栈、队列、树、图等。

动态列表

创建空数组 size = 0;

插入、删除、 修改

列表类型（int float struct 等等）

链表数据结构

struct Node
{int data;Node* next;
}

Node中data实际数据，next是下个数据的内存地址。

链表头部插入数据例子

#include <stdio.h>
#include <stdlib.h>
Struct Node
{int data;Node* netxt;
};Node* Insert(Node* head, int x)
{Node* temp = new Node();temp->data = x;temp->next  = NULL;if(head != NULL)temp->next = head;head = temp;return head; 
}void Print(Node* head)
{printf("List is: ");//遍历链表while(head!= NULL){printf(" %d", head->data);head= head->next;}printf("\n");
}int main()
{Node* head = NULL;printf("How many numbers?\n");int i, n, x;scanf("%d", &n)for(i=0; i < n; ++i){printf("insert number\n");scanf("%d", &x);head = Insert(head, x);print(head);}system("pause");return 0;
}

链表任意位置插入、删除、翻转节点

#include <stdio.h>
#include <stdlib.h>struct Node
{int data;struct Node* next;
};struct Node* head;void Insert(int data, int n)
{Node* temp1 = new Node();temp1->data = data;temp1->next = NULL;if(n == 1) {temp1->next = head;head = temp1;return;}Node* temp2 = head;for(int i=0; i < n-2; ++i){temp2 = temp2->next;}temp1->next = temp2->next;temp2->next = temp1;
}void Delete(int n)
{Node* temp1 = head;if(n == 1){head = temp1->next;delete temp1;return;}    for(int i=0; i<n-2; ++i){temp1 = temp1->next;}Node* temp2 = temp1->next;temp1->next = temp2->next;delete temp2;
}Node* Reverse()
{Node* current = head;Node* prev = NULL;Node* next = NULL;while(current != NULL){next = current->next;current->next = prev;prev = current;current = next; }head = prev;return head;
}void Print()
{while(head != NULL){printf(" %d", head->data);head = head->next;}
}int main()
{head = NULL;Insert(2,1);Insert(3,2);Insert(6,1);Insert(8,2);Print();system("pause");return 0;
}

双向链表 插入 删除

#include <stdio.h>
#include <stdlib.h>struct Node
{int data;Node* next;Node* prev;
};Node* head;Node* GetNewNode(int x)
{Node* p = new Node();p->data = x;p->next = NULL;p->prev = NULL;return p;
}void InsertAtHead(int x)
{Node* p = GetNewNode(x);if (head == NULL){head = p;return;}head->prev = p;p->next = head;head = p;
}void InsertAtEnd(int x)
{Node* p = GetNewNode(x);if (head == NULL){head = p;return;}Node* tmp = head;while (tmp->next != NULL){tmp = tmp->next;}tmp->next = p;p->prev = tmp;
}int main()
{head = NULL;InsertAtHead(1);InsertAtHead(2);InsertAtHead(3);InsertAtHead(4);InsertAtEnd(10);InsertAtEnd(9);InsertAtEnd(5);InsertAtEnd(3);Print();return 0;
}