C語言之數據結構與算法
一、數據結構與算法：線性表
1、順序表
實現代碼：
#include <stdio.h>
#include <stdlib.h>
typedef int E; //定義順序表存儲的數據為int
struct List
{
E *array; //實現順序表的底層數組
int capacity; //表示底層數組的容量
int size; //已存多少數據
};
//插入元素
_Bool insertList(struct List *list, E element, int index){
if (index < 1 || index > list->size + 1) return 0; //index可能非法
if(list->size == list->capacity){ //判斷順序表是否滿了，若滿，則擴容。
int newCapacity = list->capacity + (list->capacity >> 1); //>>1 相當于/2
E * newList = realloc(list->array, newCapacity*sizeof(E));
if(newList == NULL) return 0;
list->array = newList;
list->capacity = newCapacity;
}
for (int i = list->size; i>=index; --i){
list->array[i] = list->array[i-1];
}
list->array[index - 1] = element;
list->size++;
return 1;
}
//刪除元素
_Bool deleteList(struct List *list,int index){
if(index < 1 || index > list->size) return 0;
for(int i = index - 1; i < list->size - 1; ++i){
list->array[i] = list->array[i+1];
}
list->size--;
}
//活得順序表大小
int sizeList(struct List *list){
return list->size;
}
//獲得元素
E * getList(struct List *list, int index){
if(index < 1 || index > list->size) return NULL;
return &list->array[index-1];
}
//查找元素
int findList(struct List *list,E element){
for(int i = 0; i < list->size; i++){
if(list->array[i] == element) return i + 1;
}
return -1;
}
/*
**
**
*/
_Bool initList(struct List *list ){
list->array = malloc(sizeof(E)*10); //malloc開辟的內存在堆區，函數生命周期結束后還存在（需要手動釋放或程序結束后由系統釋放）。
if (list->array == NULL) return 0; //若申請內存空間失敗，則返回0.
list->capacity = 10;
list->size = 0;
return 1;
}
void printList(struct List *list){
for(int i = 0; i<list->size; ++i){
printf("%d ", list->array[i]);
}
printf("\n");
}
int main(int argc,int* argv)
{
struct List * list = malloc(sizeof(struct List *));
/*結構體指針初始化，首先不能 “= NULL”，因為指針指向一個安全的區域，不能解析。
**也不能，不初始化，因為指針可能指向未知地址，對其操作造成的后果是未知的，
**初始化方式有：一、在堆區開辟一個空間；二、先定義一個結構體，用指針指向他；
*/
if(initList(list)){
for(int i = 0; i<10; ++i){
insertList(list,i*10,i+1);
}
deleteList(list,2);
printList(list);
printf("%d \n",*getList(list,2));
printf("%d",findList(list,30));
}
else{
printf("shibai");
}
free(list);
}
順序表是一種隨機存取的存儲結構。
2、鏈表
實現代碼：
#include <stdio.h>
#include <stdlib.h>
typedef int E; //定義順序表存儲的數據為int
struct ListNode{
E element;
struct ListNode *next;
};
typedef struct ListNode* Node;
void initList(Node node){
node->next = NULL;
}
_Bool insertList(Node head, E element, int index){
if(index < 0) return 0;
while(--index){
head = head->next;
if(head == NULL) return 0;
}
Node node = malloc(sizeof(struct ListNode));
if(node == NULL) return 0;
node->element = element;
node->next = head->next;
head->next = node;
return 1;
}
_Bool deleteList(Node head, int index){
if(index < 1) return 0;
while(--index){
head = head->next;
if(head == NULL) return 0;
}
if(head->next == NULL) return 0;
Node node = head->next;
head->next = head->next->next;
free(node);
return 1;
}
//獲得元素；
E *getList(Node head, int index){
if(index < 1) return 0;
if (head->next == NULL) return NULL; //若為空表，則返回為空；
do{
head = head->next;
if(head == NULL) return NULL;
}while(--index);
return &head->element;
}
//尋找元素下標
int findList(Node head, E element){
int i = 1;
if(head->next == NULL) return -1; //判斷是否為空表
do{
head = head->next;
if(head->element == element) return i;
i++;
}while(head->next);
return -1;
}
int sizeList(Node head){
int i = 0;
while(head->next){
i++;
head = head->next;
}
return i;
}
//函數都是值傳遞，傳值，值不變；傳指針，指針不變；傳指針，值會變
//對head->element或者head->next操作會改變值
void printfList(Node head){
while(head->next){
head = head->next;
printf("%d ",head->element);
}
printf("\n");
}
int main()
{
Node p1;
struct ListNode head;
initList(&head);
for(int i = 0; i < 3; ++i){
insertList(&head,i*10, i+1);
}
printfList(&head);
printf("%d",sizeList(&head));
}
鏈表表是一種順序訪問的存儲結構。
3、雙向鏈表
4、循環鏈表w
5、堆棧（Stack）
先進后出
6、隊列（Queue）
先進先出
實戰1、反轉鏈表
題目描述：給你單鏈表的頭節點 head ，請你反轉鏈表，并返回反轉后的鏈表。
解法一
#include <stdio.h>
#include <stdlib.h>
typedef int E; //定義順序表存儲的數據為int
struct ListNode{
int val;
struct ListNode *next;
};
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode *tmp,*newHead = NULL;
while (head)
{
//假設前面已被反轉。
tmp = head->next; //保存第二個節點，用于當作下一個節點的頭結點。
head->next = newHead; //指向前節點
newHead = head; //更新前節點
head = tmp; //新鏈表
}
return newHead;
}
解法二:遞歸
#include <stdio.h>
#include <stdlib.h>
typedef int E; //定義順序表存儲的數據為int
struct ListNode{
int val;
struct ListNode *next;
};
struct ListNode* reverseList(struct ListNode* head) {
if (head == NULL || head->next == NULL) {
return head;
}
struct ListNode* newHead = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return newHead;
}
實戰2、匹配字符串
給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判斷字符串是否有效。
有效字符串需滿足：
- 左括號必須用相同類型的右括號閉合。
- 左括號必須以正確的順序閉合。
- 每個右括號都有一個對應的相同類型的左括號。
方法：棧的應用
方法1：自己的
#include<stdio.h>
#include<string.h>
#include<stdlib.h>>
#define true 1
#define false 0
typedef char E;
struct LNode {
E val;
struct LNode *next;
};
typedef struct LNode* Node;
void initStack(Node head){
head->next = NULL;
}
void printStack(Node head){
printf("| ");
head = head->next;
while (head){
printf("%d ", head->val);
head = head->next;
}
printf("\n");
}
//入棧
_Bool pushStack(Node head, E val){
Node node = malloc(sizeof(struct LNode));
if(node == NULL) return 0;
node->next = head->next;
node->val = val;
head->next = node;
return 1;
}
//出棧
E popStack(Node head){
if(head->next == NULL) return 0;
Node node;
node = head->next;
E val = node->val;
head->next = head->next->next;
free(node);
return val;
}
_Bool isValid(char* s) {
struct LNode head;
initStack(&head);
unsigned int len = strlen(s);
if(len % 2 == 1) return false;
pushStack(&head,s[0]);
for(int i = 1; i < len; i++){
E top = popStack(&head);
if(top != 0)pushStack(&head,top);
if(top == '('){
if(s[i] == ')') popStack(&head);
else pushStack(&head,s[i]);
}
else if(top == '['){
if(s[i] == ']') popStack(&head);
else pushStack(&head,s[i]);
}
else if(top == '{'){
if(s[i] == '}') popStack(&head);
else pushStack(&head,s[i]);
}
else pushStack(&head,s[i]);
}
if(head.next == NULL) return true;
else return false;
}
int main(){
char *s = "()[]{}";
printf("%d ",isValid(s));
}
方法2：更快
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
typedef char E;
struct LNode {
E element;
struct LNode * next;
};
typedef struct LNode * Node;
void initStack(Node head){
head->next = NULL;
}
_Bool pushStack(Node head, E element){
Node node = malloc(sizeof(struct LNode));
if(node == NULL) return 0;
node->next = head->next;
node->element = element;
head->next = node;
return 1;
}
_Bool isEmpty(Node head){
return head->next == NULL;
}
E popStack(Node head){
Node top = head->next;
head->next = head->next->next;
E e = top->element;
free(top);
return e;
}
bool isValid(char * s){
unsigned long len = strlen(s);
if(len % 2 == 1) return false; //如果長度不是偶數，那么一定不能成功匹配
struct LNode head;
initStack(&head);
for (int i = 0; i < len; ++i) {
char c = s[i];
if(c == '(' || c == '[' || c == '{') {
pushStack(&head, c);
}else {
if(isEmpty(&head)) return false;
if(c == ')') {
if(popStack(&head) != '(') return false;
} else if(c == ']') {
if(popStack(&head) != '[') return false;
} else {
if(popStack(&head) != '{') return false;
}
}
}
return isEmpty(&head);
}
方法三：更快
char pairs(char a) {
if (a == '}') return '{';
if (a == ']') return '[';
if (a == ')') return '(';
return 0;
}
bool isValid(char* s) {
int n = strlen(s);
if (n % 2 == 1) {
return false;
}
int stk[n + 1], top = 0;
for (int i = 0; i < n; i++) {
char ch = pairs(s[i]);
if (ch) {
if (top == 0 || stk[top - 1] != ch) {
return false;
}
top--;
} else {
stk[top++] = s[i];
}
}
return top == 0;
}
二、數據結構與算法：樹
1、樹：理論
-
我們一般稱位于最上方的結點為樹的根結點（Root）；
-
每個結點連接的子結點數目（分支的數目），我們稱為結點的度（Degree），而各個結點度的最大值稱為樹的度；
-
每個結點延伸下去的下一個結點都可以稱為一棵子樹（SubTree）；
-
每個結點的層次（Level）按照從上往下的順序，樹的根結點為
1，每向下一層+1，比如G的層次就是3，整棵樹中所有結點的最大層次，就是這顆樹的深度（Depth）； -
與當前結點直接向下相連的結點，我們稱為子結點（Child）；相反即為父節點；
-
如果某個節點沒有任何的子結點（結點度為0時）那么我們稱這個結點為葉子結點；
-
如果兩個結點的父結點是同一個，那么稱這兩個節點為兄弟結點（Sibling）；
-
從根結點開始一直到某個結點的整條路徑的所有結點，都是這個結點的祖先結點（Ancestor）；
2、二叉樹的性質
- 性質一： 對于一棵二叉樹，第
i層的最大結點數量為 個2^i - 1; - 一棵深度為
k的二叉樹最大結點數量為 n = 2^k*?1，順便得出，結點的邊數為 E = n - 1。 - 于任何一棵二叉樹，如果其葉子結點個數為 n0，度為2的結點個數為 n2 ，那么兩者滿足以下公式：n0 = n2+1;
n個結點的完全二叉樹深度為 k = log2^n + 1 ;
3、二叉樹遍歷：前序、中序、后序遍歷
前序遍歷結果為：ABDECF；
中序遍歷結果為：DBEACF；
后序遍歷結果為：DEBFCA；
#include<stdio.h>
#include<string.h>
#include<stdlib.h>>
typedef char E;
struct TreeNode{
E element;
struct TreeNode *left;
struct TreeNode *right;
};
typedef struct TreeNode* Node;
//前序遞歸，利用函數棧的特性，不斷出棧入棧
void preOrder(Node root){
if(root == NULL) return;
printf("%c", root->element);
preOrder(root->left);
preOrder(root->right);
}
//中序遍歷
void inOrder(Node root){
if(root == NULL) return;
inOrder(root->left);
printf("%c",root->element);
inOrder(root->right);
}
//后序遍歷
void afOrder(Node root){
if(root == NULL) return;
afOrder(root->left);
afOrder(root->right);
printf("%c",root->element);
}
int main(){
Node a = malloc(sizeof(struct TreeNode));
Node b = malloc(sizeof(struct TreeNode));
Node c = malloc(sizeof(struct TreeNode));
Node d = malloc(sizeof(struct TreeNode));
Node e = malloc(sizeof(struct TreeNode));
Node f = malloc(sizeof(struct TreeNode));
a->element = 'A';
b->element = 'B';
c->element = 'C';
d->element = 'D';
e->element = 'E';
f->element = 'F';
a->left = b;
a->right = c;
b->left = d;
b->right = e;
c->right = f;
c->left = NULL;
d->left = e->right = NULL;
e->left = e->right = NULL;
f->left = f->right = NULL;
afOrder(a);
}
4、二叉樹遍歷：層序遍歷
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef char E;
typedef struct TreeNode {
E element; //存放元素
struct TreeNode * left; //指向左子樹的指針
struct TreeNode * right; //指向右子樹的指針
} *Node;
typedef struct initNode{ //定義隊列初始節點
Node element;
struct initNode *next;
} *INode;
struct Queue{ //隊列頭尾指針
INode front,rear;
};
typedef struct Queue* LinkedQueue;
_Bool initQueue(LinkedQueue queue){
INode node = malloc(sizeof(struct initNode));
if(node == NULL) return 0;
node->next = NULL;
queue->front = queue->rear = node;
}
//入隊
_Bool enQueue(LinkedQueue quene, Node element){
INode node = malloc(sizeof(struct initNode));
if(node == NULL) return 0;
node->next = NULL;
node->element = element;
quene->rear->next = node;
quene->rear = node;
return 1;
}
// 出隊
Node deQueue(LinkedQueue queue){
Node val = queue->front->next->element;
INode node;
node = queue->front->next;
queue->front->next = queue->front->next->next;
if(queue->rear == node) queue->rear = queue->front;
free(node);
return val;
}
_Bool isEmpty(LinkedQueue queue){
return (queue->front == queue->rear);
}
void levelQueue(Node root){
struct Queue queue;
initQueue(&queue);
enQueue(&queue,root);
while(!isEmpty(&queue)){
Node node = deQueue(&queue);
printf("%c",node->element);
if(node->left) enQueue(&queue,node->left);
if(node->right) enQueue(&queue,node->right);
}
}
int main(){
Node a = malloc(sizeof(struct TreeNode));
Node b = malloc(sizeof(struct TreeNode));
Node c = malloc(sizeof(struct TreeNode));
Node d = malloc(sizeof(struct TreeNode));
Node e = malloc(sizeof(struct TreeNode));
Node f = malloc(sizeof(struct TreeNode));
a->element = 'A';
b->element = 'B';
c->element = 'C';
d->element = 'D';
e->element = 'E';
f->element = 'F';
a->left = b;
a->right = c;
b->left = d;
b->right = e;
c->right = f;
c->left = NULL;
d->left = e->right = NULL;
e->left = e->right = NULL;
f->left = f->right = NULL;
levelQueue(a);
}
5、二叉樹的線索化(以前序為例)
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef char E;
typedef struct TreeNode {
E element; //存放元素
struct TreeNode * left; //指向左子樹的指針
struct TreeNode * right; //指向右子樹的指針
char leftFlag,rightFlag //線索化標志位
} *Node;
Node pre = NULL; //這里我們需要一個pre來保存后續結點的指向
void treeOrdered(Node root){
if(root == NULL) return;
//線索化規則：結點的左指針，指向其當前遍歷順序的前驅結點；結點的右指針，指向其當前遍歷順序的后繼結點。
if(root->left == NULL){ //判斷當前節點的左節點是否為空，若為空，則指向上一個節點。
root->leftFlag = 1;
root->left = pre;
}
if(pre && pre->right == NULL){ //判斷上一個節點的右節點是否為空，若為空，則指向當前節點
pre->right = root;
pre->rightFlag = 1;
}
pre = root;
if(root->leftFlag == 0) treeOrdered(root->left); //判斷左節點是否是線索化的，若不是，才能繼續。
if(root->rightFlag == 0) treeOrdered(root->right); //判斷可略，因為，我們對右節點的線索化，是在后面執行的
}
void preOrder(Node root){
while (root) { //到頭為止
printf("%c", root->element); //因為是前序遍歷，所以直接按順序打印就行了
if(root->leftFlag == 0)
root = root->left; //如果是左孩子，那么就走左邊
else
root = root->right; //如果左邊指向是線索，那么就直接走右邊。
}
}
Node createNode(E element){ //單獨寫了個函數來創建結點
Node node = malloc(sizeof(struct TreeNode));
node->left = node->right = NULL;
node->rightFlag = node->leftFlag = 0;
node->element = element;
return node;
}
int main() {
Node a = createNode('A');
Node b = createNode('B');
Node c = createNode('C');
Node d = createNode('D');
Node e = createNode('E');
a->left = b;
b->left = d;
a->right = c;
b->right = e;
treeOrdered(a);
preOrder(a);
}
六、二叉搜索樹（二叉查找樹）
七、平衡二叉樹
三、數據結構與算法：哈希表
1、哈希表
#include<stdio.h>
#include<stdlib.h>
#define SIZE 9
//結構體指針，直接用E->key訪問，避免用*E訪問
typedef struct Element { //這里用一個Element將值包裝一下
int key; //這里元素設定為int
} * E;
typedef struct HashTable{ //這里把數組封裝為一個哈希表
E * table;
} * HashTable;
int hash(int key){ //哈希函數
return key % SIZE;
}
void init(HashTable hashTable){ //初始化函數
hashTable->table = malloc(sizeof(struct Element) * SIZE);
for (int i = 0; i < SIZE; ++i)
hashTable->table[i] = NULL;
}
void insert(HashTable hashTable, E element){ //插入操作，為了方便就不考慮裝滿的情況了
int hashCode = hash(element->key); //首先計算元素的哈希值
hashTable->table[hashCode] = element; //對號入座
}
_Bool find(HashTable hashTable, int key){
int hashCode = hash(key); //首先計算元素的哈希值
if(!hashTable->table[hashCode]) return 0; //如果為NULL那就說明沒有
return hashTable->table[hashCode]->key == key; //如果有，直接看是不是就完事
}
E create(int key){ //創建一個新的元素
E e = malloc(sizeof(struct Element));
e->key = key;
return e;
}
int main() {
struct HashTable hashTable;
init(&hashTable);
insert(&hashTable, create(10));
insert(&hashTable, create(7));
insert(&hashTable, create(13));
insert(&hashTable, create(29));
printf("%d\n", find(&hashTable, 1));
printf("%d\n", find(&hashTable, 13));
}
2、哈希沖突（鏈地址法）
#include<stdio.h>
#include<stdlib.h>
#define SIZE 9
typedef struct ListNode { //結點定義
int key;
struct ListNode * next;
} * Node;
typedef struct HashTable{ //哈希表
struct ListNode * table; //這個數組專門保存頭結點
} * HashTable;
void init(HashTable hashTable){
hashTable->table = malloc(sizeof(struct ListNode) * SIZE);
for (int i = 0; i < SIZE; ++i) {
hashTable->table[i].key = -1; //將頭結點key置為-1，next指向NULL
hashTable->table[i].next = NULL;
}
}
int hash(int key){ //哈希函數
return key % SIZE;
}
Node createNode(int key){ //創建結點專用函數
Node node = malloc(sizeof(struct ListNode));
node->key = key;
node->next = NULL;
return node;
}
void insert(HashTable hashTable, int key){
int hashCode = hash(key);
Node head = hashTable->table + hashCode; //先計算哈希值，找到位置后直接往鏈表后面插入結點就完事了
while (head->next) head = head->next;
head->next = createNode(key); //插入新的結點
}
_Bool find(HashTable hashTable, int key){
int hashCode = hash(key);
Node head = hashTable->table + hashCode;
while (head->next && head->key != key) //直到最后或是找到為止
head = head->next;
return head->key == key; //直接返回是否找到
}
int main(){
struct HashTable table;
init(&table);
insert(&table, 10);
insert(&table, 19);
insert(&table, 20);
printf("%d\n", find(&table, 20));
printf("%d\n", find(&table, 17));
printf("%d\n", find(&table, 19));
}
浙公網安備 33010602011771號