个人简介
作者是一个来自河源的大三在校生，以下笔记都是作者自学之路的一些浅薄经验，如有错误请指正，将来会不断的完善笔记，帮助更多的Java爱好者入门。
文章目录
- 个人简介
- C语言数据结构与算法
- BF和KMP算法
- 循环链表
- 斐波那契和阶乘
- 并查集Disjoint Set
- 哈希表
- 链式队列
- 链式栈
- 优先队列priority queue
- 查找算法
- 循环队列
- 顺序表
- 顺序栈
- 单链表
- 排序算法
- 双向单链表
C语言数据结构与算法
BF和KMP算法
#include <stdio.h>
int slen(char* s)
{
int i = 0;
if (s == NULL) {
return 0;
}
else {
while (s[i] != '\0')
{
i++;
}
return i;
}
}
//BF
int* bf(char* str,char *ptr)
{
int i=0, j=0;
int index = 0;
int strlen = slen(str);
int ptrlen = slen(ptr);
while (i<strlen&&j<ptrlen)
{
if (str[i]==ptr[j]) {
i++;
j++;
}
else {
index++;
i = index;
j = 0;
}
}
if (j == ptrlen) {
return i-j;
}
else {
return -1;
}
}
//kmp
int* kmp(char* haystack, char* needle)
{
int i = 0, j = 0;
int strlen = slen(haystack);
int ptrlen = slen(needle);
while (i < strlen && j < ptrlen)
{
if (haystack[i] == needle[j]) {
i++;
j++;
}
else {
i = i-j+1;
j = 0;
}
}
if (j == ptrlen) {
return i - j;
}
else {
return -1;
}
}
int main(void)
{
char *str= "hello";
char* ptr = "ll";
//int res=bf(str, ptr);
int res = kmp(str, ptr);
printf("%d \n",res);
return 0;
}
循环链表
#include <stdio.h>
#include <stdlib.h>
#define true 1
#define false 0
//C语言实现循环链表
//链表结点
typedef struct Node {
int data;
struct Node* next;
} node;
typedef struct Node* linklist;
void initList(linklist head)
{
printf("初始化循环链表......\n");
if (head == NULL) {
head = (node*)malloc(sizeof(node));
}
head->data = 0;
head->next = head; //初始化给head的指针指向自己
}
//插入(尾插法)
void tailAddNode(linklist head,int data) {
node* p = (node*)malloc(sizeof(node));
p->next = head;
node* newNode = (node*)malloc(sizeof(node));
newNode->data = data;
while (true) {
if (p->next->next == head) { //当前p->next就是尾
p->next->next = newNode;
newNode->next = head;
head->data++;
printf("插入结点成功......\n");
break;
}
else {
p->next = p->next->next;
}
}
}
//删除
void deleteNode(linklist head,int index)
{
node* p = (node*)malloc(sizeof(node));
p->next = head;
int cur = 0;
//int in = index % (head->data); //in是取模后的下标
while (true)
{
if ((cur+1)==index) //此时下一个结点就是我们要删除的结点
{
node* temp = p->next->next;
p->next->next = p->next->next->next;
head->data--;
free(temp);
printf("删除结点成功......\n");
break;
}
else {
p->next = p->next->next;
cur++;
}
}
}
void printList(linklist head)
{
node* p = (node*)malloc(sizeof(node));
p->next = head->next;
while (true) {
if (p->next->next == head) {
printf("%d ", p->next->data);
printf("进入循环-> %d ", p->next->next->next->data);
break;
}
else {
printf("%d ",p->next->data);
p->next = p->next->next;
}
}
}
int main(void)
{
linklist head = (node*)malloc(sizeof(node));
initList(head);
tailAddNode(head, 15);
tailAddNode(head, 22);
tailAddNode(head, 33);
printList(head);
deleteNode(head,3);
printList(head);
return 0;
}
斐波那契和阶乘
#include <stdio.h>
#include <stdlib.h>
//递归题 easy
//1.斐波那契数列
int fib(int n) {
if (n == 0)
{
return 0;
}
if (n == 1)
{
return 1;
}
return fib(n - 1) + fib(n - 2);
}
//2.阶乘
int jiecheng(int n)
{
if (n==0||n == 1)
{
return 1;
}
else {
return n * jiecheng(n - 1);
}
}
int main(void)
{
int res=jiecheng(10);
printf("%d\n",res);
return 0;
}
并查集Disjoint Set
#include <stdio.h>
#include <stdlib.h>
#define sz 5 //数组大小常量
typedef int elemtype;
//C语言实现并查集Disjoint Set
//并查集结构体
typedef struct disjointSet
{
int size; //fa数组的大小
elemtype* fa; //存储父节点的数组
} disjointSet;
disjointSet* initSet(disjointSet* ds)
{
if (ds == NULL)
{
ds = (disjointSet*)malloc(sizeof(disjointSet));
}
ds->size = sz;
//给fa数组分配内存
ds->fa = malloc(sizeof(elemtype) * ds->size + 1);
int i;
for (i = 1; i <=ds->size; i++)
{
//默认父结点数组元素指向0，其实就是指向它自己
ds->fa[i] = 0;
}
printf("初始化并查集成功......\n");
return ds;
}
//并查集的递归查找元素的‘’最顶层‘’的父节点，因为fa数组存储的是结点的父节点（有可能不是最顶层结点）
int findSet(disjointSet* disjointSet,int n)
{
if (disjointSet->fa[n] == 0) //说明n结点指向自己,也说明这是最顶层的结点
{
return n;
}
else {
//路径压缩,提高查询性能
disjointSet->fa[n]=findSet(disjointSet, disjointSet->fa[n]); //递归找到最顶层的结点
}
}
//并查集的合并（核心）,合并n1-n2
void unionSet(disjointSet* disjointSet, int n1, int n2)
{
//找到n1-n2的最顶层的父节点进行合并
int f1 = findSet(disjointSet, n1);
int f2 = findSet(disjointSet, n2);
if (f1 == f2) //如果f1=f2，说明是在同一个集合中，不需要合并
{
printf("n1和n2已经在同一个集合中，不需要合并......\n");
return;
}
else {
disjointSet->fa[f1] = f2; //合并
printf("合并成功......\n");
return;
}
}
int main(void)
{
disjointSet* disjointSet = NULL;
disjointSet = initSet(disjointSet);
unionSet(disjointSet, 6, 2);
unionSet(disjointSet, 5, 4);
unionSet(disjointSet, 4, 1);
unionSet(disjointSet, 3, 1);
int f1=findSet(disjointSet, 6);
printf("findset:%d\n",f1);
int f2 = findSet(disjointSet, 1);
printf("findset:%d\n", f2);
return 0;
}
哈希表
#include <stdio.h>
#include <stdlib.h>
#define max 5
#define defaultNum 95535
//哈希表 （数组实现闭散列）
typedef struct Hashtable
{
int cur; //当前元素个数
int maxSize; //最大容量
int* table; //数据存储空间
} Hashtable;
//初始化哈希表
Hashtable* init(Hashtable *hashtable)
{
if (hashtable == NULL)
{
hashtable = (Hashtable*)malloc(sizeof(hashtable));
}
hashtable->cur = 0; //初始化元素个数为0
hashtable->maxSize = max;
hashtable->table=(int*)malloc(sizeof(int) * max); //这里一定要给int*数组分配内存---------
int i = 0;
for ( i = 0; i < hashtable->maxSize; i++)
{
hashtable->table[i] = defaultNum;
}
printf("init success......\n");
return hashtable;
}
//散列函数
int hash(Hashtable* hashtable, int data)
{
return data % hashtable->maxSize;
}
//添加元素
void put(Hashtable* hashtable, int data)
{
if (hashtable->cur >= hashtable->maxSize)
{
printf("哈希表已满，插入失败......\n");
return;
}
else {
int index = hash(hashtable, data); //获取散列后的index
if (hashtable->table[index] == defaultNum) //说明没有发生哈希冲突，可以直接插入
{
hashtable->cur++;
hashtable->table[index] = data;
printf("插入元素成功......\n");
return;
}
else
{
int i = 1;
while (1)
{
index =hash(hashtable,data+i);
i++;
if (hashtable->table[index] == defaultNum) //再哈希
{
hashtable->cur++;
hashtable->table[index] = data;
printf("再哈希，插入元素成功......\n");
break;
}
if (i == hashtable->maxSize - 1)
{
printf("已遍历完整个哈希表，没有合适位置插入.......\n");
break;
}
}
}
}
}
int search(Hashtable* hashtable, int data)
{
int index = hash(hashtable, data);
if (hashtable->table[index] == defaultNum)
{
printf("没有该元素......\n");
return -99;
}
else {
if (hashtable->table[index] == data)
{
printf("查找成功......\n");
return index;
}
else {
int i = 1;
while (1)
{
index = hash(hashtable, data+i);
i++;
if (hashtable->table[index] == data)
{
printf("查找成功......\n");
return index;
}
if (i == hashtable->maxSize - 1)
{
printf("查找失败......\n");
break;
}
}
return -99;
}
}
}
void printHash(Hashtable* hashtable)
{
printf("开始打印......\n");
int i = 0;
for ( i = 0; i < hashtable->maxSize; i++)
{
printf("%d ",hashtable->table[i]);
}
printf("\n打印结束......\n");
}
int main(void)
{
Hashtable* hashtable = NULL;
hashtable = init(hashtable);
put(hashtable, 13);
put(hashtable, 10);
put(hashtable, 17);
put(hashtable, 15);
put(hashtable, 13);
put(hashtable, 16);
printHash(hashtable);
int x1=search(hashtable,15);
printf("search:%d\n",x1);
return 0;
}
链式队列
#include <stdio.h>
#include <stdlib.h>
#define true 1
#define false 0
typedef int status;
typedef int Elemtype;
//C 实现链式队列
typedef struct Node {
Elemtype data;
struct Node* next;
} node;
typedef struct LinkedQueue
{
struct Node* front; //指向队首的指针
struct Node* rear; //指向队尾的指针
} LinkedQueue;
//init queue
LinkedQueue* initQueue(LinkedQueue* linkedQueue)
{
if (linkedQueue == NULL)
{
linkedQueue = (LinkedQueue*)malloc(sizeof(LinkedQueue));
}
//创建一个结点作为队列的头结点（不是队头）
linkedQueue->front = linkedQueue->rear = (node*)malloc(sizeof(node));
printf("init queue success......\n");
return linkedQueue;
}
//入队
status enQueue(LinkedQueue* linkedQueue,int data)
{
if (linkedQueue == NULL)
{
printf("入队失败...\n");
return false;
}
else {
node* newNode = (node*)malloc(sizeof(node));
newNode->data = data;
//入队
linkedQueue->rear->next = newNode;
newNode->next = NULL;
//入队后尾指针后移到新节点
linkedQueue->rear = newNode;
printf("入队成功...\n");
return true;
}
}
//出队
int* deQueue(LinkedQueue* linkedQueue)
{
if (linkedQueue == NULL || (linkedQueue->front == linkedQueue->rear))
{
printf("队列没有任何元素，出队失败......\n");
return -99999;
}
else {
node* p = linkedQueue->front->next; //保存待出队结点
int res = p->data;
//队首结点的指针指向待出队结点的下一个结点即可
linkedQueue->front->next = p->next;
free(p); //释放出队结点资源
return res;
}
}
void printQueue(LinkedQueue* linkedQueue)
{
printf("打印队列......\n");
//(linkedQueue->front == linkedQueue->rear) 如果为true，则队列没有任何元素
if (linkedQueue == NULL || (linkedQueue->front == linkedQueue->rear))
{
printf("队列没有任何元素......\n");
}
else {
//创建一个指针指向队首结点
node* temp=(node*)malloc(sizeof(node));
temp->next = linkedQueue->front;
while (temp->next->next!=NULL)
{
printf("%d ",temp->next->next->data);
temp->next = temp->next->next;
}
printf("\n打印成功......\n");
}
}
int main(void)
{
LinkedQueue* linkedQueue = NULL;
linkedQueue = initQueue(linkedQueue);
enQueue(linkedQueue, 20);
enQueue(linkedQueue, 50);
enQueue(linkedQueue, 115);
enQueue(linkedQueue, 95);
printQueue(linkedQueue);
printf("出队结点：%d\n", deQueue(linkedQueue));
printf("出队结点：%d\n", deQueue(linkedQueue));
printf("出队结点：%d\n", deQueue(linkedQueue));
printQueue(linkedQueue);
return 0;
}
链式栈
#include <stdio.h>
#include <stdlib.h>
#define true 1
#define false 0
typedef int status;
typedef int Elemtype;
//C实现链式栈
typedef struct Node {
Elemtype data; //每个结点的数据
struct Node* next; //指向下一个结点的指针
} node;
typedef struct LinkedStack
{
struct node* top; //栈顶指针
} LinkedStack;
//初始化
LinkedStack* init(LinkedStack* linkedStack)
{
if (linkedStack == NULL)
{
linkedStack=(LinkedStack*)malloc(sizeof(linkedStack));
}
linkedStack->top = 0; //这段代码等价于===》linkedStack->top=NULL
printf("初始化链栈完成......\n");
return linkedStack;
}
status push(LinkedStack* linkedStack,int data)
{
node* newNode = (node*)malloc(sizeof(node));
newNode->data = data;
newNode->next = linkedStack->top;
linkedStack->top = newNode;
return true;
}
status pop(LinkedStack* linkedStack)
{
if (linkedStack->top == 0)
{
printf("没有元素......\n");
return false;
}
else {
node* p = (node*)malloc(sizeof(node));
p->next = linkedStack->top;
printf("弹出元素：%d\n",p->next->data);
linkedStack->top = p->next->next; //栈顶下移
return true;
}
}
void printStack(LinkedStack* linkedStack)
{
printf("print start......\n");
//创建一个指针指向栈顶
node* temp = (node*)malloc(sizeof(node));
temp->next = linkedStack -> top;
//如果栈顶为NULL就退出
while (temp->next != 0)
{
printf("%d\n",temp->next->data);
temp->next = temp->next->next;
}
printf("print success......\n");
}
int main(void)
{
LinkedStack* linkedStack = NULL;
linkedStack =init(linkedStack);
push(linkedStack,12);
push(linkedStack, 22);
push(linkedStack, 32);
printStack(linkedStack);
pop(linkedStack);
printStack(linkedStack);
return 0;
}
优先队列priority queue
#include <stdio.h>
#include <stdlib.h>
#define sz 5 //final queue size
#define true 1
#define false 0
typedef int elemtype;
//优先队列priority queue
typedef struct priorityQueue
{
int cur; //priorityQueue current index
int size; //priorityQueue size
elemtype* queue; //priorityQueue arr
} priorityQueue;
//init queue
priorityQueue* initQueue(priorityQueue* q)
{
if(q==NULL)
{
q=(priorityQueue*)malloc(sizeof(priorityQueue)*2);
}
q->cur=0;
q->size=sz;
q->queue=(elemtype*)malloc(sizeof(elemtype)*q->size+2);
return q;
}
//队列满
int hasFull(priorityQueue* q)
{
if(q->cur>=q->size)
{
return true; //满了
}else{
return false;
}
}
//insert q->queue[1] is head-Node
void insert(priorityQueue* q,int x)
{
if(hasFull(q)==true) //队列满
{
printf("queue is full......\n");
return;
}
if(q->cur==0) //if queue is null
{
++q->cur;
q->queue[1]=x;
printf("insert success......\n");
return;
}else{
int i; //插入index
for(i=++q->cur;q->queue[i/2]>q->queue[i];i=i/2)
{
q->queue[i]=q->queue[i/2];
}
q->queue[i]=x;
printf("queue insert success......\n");
return;
}
}
//find min
int find_min(priorityQueue* q)
{
return q->queue[1]; //index=1 is min
}
int main(void)
{
priorityQueue* q=NULL;
q=initQueue(q);
insert(q,25);
insert(q,33);
insert(q,12);
insert(q,19);
printf("min=%d\n",find_min(q));
return 0;
}
查找算法
#include <stdio.h>
#include <stdlib.h>
//查找算法
//二分查找 1
int search1(int* nums, int numsSize, int target) {
int left = 0; //left指针
int right = numsSize - 1; //right指针
int mid = (left + right) / 2;
while (left <= right)
{
if (nums[mid] == target)
{
return mid;
}
else if (nums[mid] > target)
{
right = mid - 1;
mid= (left + right) / 2;
}
else if (nums[mid] < target)
{
left = mid + 1;
mid = (left + right) / 2;
}
}
return -1;
}
//二分查找 2
int search(int* nums, int numsSize, int target) {
int left = 0; //left指针
int right = numsSize - 1; //right指针
while (left <= right)
{
int mid = left + (right - left) / 2; //防止数据过大导致溢出
if (nums[mid] == target)
{
return mid;
}
else if (nums[mid] > target)
{
right = mid - 1;
}
else if (nums[mid] < target)
{
left = mid + 1;
}
}
return -1;
}
int main(void)
{
int arr[]= {1,6,8,12,16,18,22,33,66,77,79};
int numsSize = 11;
int target = 66;
int res=search(arr, numsSize, target);
printf("res=%d\n",res);
return 0;
}
循环队列
#include <stdio.h>
#include <stdlib.h>
#define true 1
#define false 0
#define max_size 5 //队列最大容量
typedef int status;
typedef int ElemType;
//C语言实现循环队列
typedef struct SeqQueue {
ElemType data[max_size]; //存放data
int front; //队首
int rear; //队尾
} SeqQueue;
//初始化
SeqQueue* initQueue(SeqQueue* seqQueue)
{
if (seqQueue == NULL)
{
seqQueue=(SeqQueue*)malloc(sizeof(SeqQueue));
}
seqQueue->front = seqQueue->rear = 0; //循环队列初始化指针指向0
printf("初始化成功......\n");
return seqQueue;
}
//队列空(和普通队列一样，都是队首=队尾就为空)
status hasNull(SeqQueue* seqQueue)
{
if (seqQueue->front == seqQueue->rear) {
return true;
}
else {
return false;
}
}
//队列满(和普通队列不一样,循环队列是队尾+1模上数组长度=队首就为满)
status hasFull(SeqQueue* seqQueue)
{
if (((seqQueue->rear) + 1) % max_size == seqQueue->front) {
return true;
}
else {
return false;
}
}
//入队
status enQueue(SeqQueue* seqQueue,int data)
{
if (hasFull(seqQueue) == true)
{
printf("队列已满，不能入队......\n");
return false;
}
else {
seqQueue->data[seqQueue->rear] = data;
//队尾指针后移
seqQueue->rear = ((seqQueue->rear) + 1) % max_size; //等价于普通队列的rear+1
printf("入队成功......\n");
return true;
}
}
//出队
status deQueue(SeqQueue* seqQueue)
{
if (hasNull(seqQueue) == true)
{
printf("队列空，出队失败......\n");
return false;
}
else {
printf("出队成功......\n");
seqQueue->front=(seqQueue->front + 1) % max_size;
return true;
}
}
void printQueue(SeqQueue* seqQueue)
{
if (hasNull(seqQueue) == true)
{
printf("队列空，打印失败......\n");
}
else {
printf("正在打印队列......\n");
int temp = (seqQueue->front ) % max_size; //指向队首结点下一个
//分情况
//if (seqQueue->front > seqQueue->rear) {
while (temp != (seqQueue->rear)) {
printf("%d ",seqQueue->data[temp]);
temp = (temp + 1) % max_size;
}
//else if(seqQueue->front < seqQueue->rear) {
//while (temp != (seqQueue->rear) + 1)
//{}
//}
printf("\n打印成功......\n");
}
}
int main(void)
{
SeqQueue* seqQueue = NULL;
seqQueue=initQueue(seqQueue);
enQueue(seqQueue,10);
enQueue(seqQueue, 20);
enQueue(seqQueue, 30);
deQueue(seqQueue);
deQueue(seqQueue);
enQueue(seqQueue, 50);
enQueue(seqQueue, 60);
printQueue(seqQueue);
return 0;
}
顺序表
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 5 //顺序表最大容量
#define true 1 //成功
#define false 0 //失败
typedef int status;
//C语言实现顺序表
//定义顺序表结构体
typedef struct List {
int data[MAX_SIZE]; //模拟顺序表
int length; //顺序表实际长度 length>=0 && length<=MAX_SIZE ,线性表是从1开始的，数组才是从0开始
} list;
status init(list *plist) {
//如果plist=NULL则分配内存
if (plist == NULL) {
printf("正在分配内存....\n");
plist = (list*)malloc(sizeof(list));
}
plist->length = 0;
}
//顺序表插入（尾部直接插入）
status insertData(list* list, int dt) {
//如果list没有初始化
if (hasInit(list) == false) {
printf("list没有初始化，操作失败\n");
return false;
}
//判断顺序表是否满了
if (list->length >= MAX_SIZE) {
printf("顺序表满了,插入失败......\n");
return false;
}
list->data[list->length]=dt;
list->length++;
printf("插入成功......\n");
return true;
}
//顺序表插入（自定义位置插入）
status insertData_zi(list* list, int n, int dt) {
//如果list没有初始化
if (hasInit(list) == false) {
printf("list没有初始化，操作失败\n");
return false;
}
//判断顺序表是否满了
if (list->length >= MAX_SIZE) {
printf("顺序表满了,插入失败......\n");
return false;
}
//判断自定义的位置n是否合法
if (n <= 0 || n >= MAX_SIZE) {
return false;
}
else {
int i;
for (i = list->length; i >= n; i--) {
list->data[i] = list->data[i - 1];
}
list->data[n - 1] = dt; //插入
list->length++; //长度+1
return true;
}
}
//删除元素
status deleteData(list *list,int n) {
//如果list没有初始化
if (hasInit(list) == false) {
printf("list没有初始化，操作失败\n");
return false;
}
//如果列表为空，则不能删除
if (list->length == 0) {
printf("列表为空，不能删除\n");
return false;
}
//如果n不合法，则删除失败
if (n<1||n>MAX_SIZE) {
printf("参数n不合法，删除失败\n");
return false;
}
int i;
for (i = n - 1; i < list->length - 1; i++) {
list->data[i] = list->data[i + 1];
}
list->length--;
return true;
}
//判断是否初始化表
status hasInit(list* list) {
if (list == NULL) {
return false;
}
else {
return true;
}
}
//修改指定元素
status changeData(list *list,int n,int dt)
{
//如果list没有初始化
if (hasInit(list) == false) {
printf("list没有初始化，操作失败\n");
return false;
}
//线性表为空
if (list->length == 0) {
return false;
}
//判断n是否合法
//if (n<1 || n>MAX_SIZE) { //这里不能使用n>MAX_SIZE，要n>list->length
if (n<1 || n>list->length) {
return false;
}
else
{ //此时可以修改
list->data[n - 1] = dt;
return true;
}
}
//查找元素(按照值进行查找，并把“下标”保存到res数组中,最多查找出10个)
status getElem(list *list,int dt,int res[10],int *count) {
//如果list没有初始化
if (hasInit(list) == false) {
printf("list没有初始化，操作失败\n");
return false;
}
int i;
int index = 0;
for (i = 0; i < list->length; i++)
{
if (list->data[i] == dt) {
printf("index:%d\n",i);
res[index] = i;
index++;
}
}
*count = index;
return true;
}
status printList(list *list)
{
//如果list没有初始化
if (hasInit(list) == false) {
printf("list没有初始化，操作失败\n");
return false;
}
int i;
printf("打印顺序表list......\n");
for (i = 0; i < list->length; i++)
{
printf("%d ",list->data[i]);
}
printf("\n.........................\n");
return true;
}
int main(void)
{
list* plist = (list*)malloc(sizeof(list));
init(plist);
insertData(plist,10);
insertData(plist, 20);
printList(plist);
int res[10] = { 0 };
int *len = (int*)malloc(sizeof(int));
getElem(plist,30,res,len);
printf("getElem长度为：%d\n", *len);
printf("%d\n",res[0]);
return 0;
}
顺序栈
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define true 1
#define false 0
#define max_size 5
typedef int elemtype;
typedef int status;
//C语言实现顺序栈
typedef struct Stack {
int top; //栈顶索引
elemtype data[max_size]; //栈数组
}Stack;
Stack* init(Stack* stack)
{
printf("init stack start......\n");
stack = (Stack*)malloc(sizeof(stack));
if (stack == NULL)
{
printf("分配内存失败......\n");
exit(0);
}
stack->top = -1; //初始化栈顶指针
printf("init stack success......\n");
return stack;
}
//栈空
status hasNull(Stack* stack)
{
if (stack->top <= -1) {
return true;
}
else {
return false;
}
}
//栈满
status hasFull(Stack* stack)
{
if (stack->top==max_size-1) {
return true;
}
else {
return false;
}
}
//入栈
status push(Stack *stack,int data)
{
if (hasFull(stack) == true)
{
printf("stack is full......\n");
return false;
}
else {
stack->data[++stack->top] = data;
printf("push success......\n");
return true;
}
}
//弹栈
status pop(Stack* stack)
{
if (hasNull(stack)==true)
{
printf("stack is Null......\n");
return false;
}
else {
printf("弹出元素: %d \n",stack->data[stack->top--]);
return true;
}
}
void printStack(Stack* stack)
{
if (hasNull(stack) == true) //如果栈空
{
printf("栈为空......\n");
}
else {
int i;
printf("正在打印栈......\n");
for (i = stack->top; i >= 0; i--)
{
printf("%d\n",stack->data[i]);
}
printf("打印完成......\n");
}
}
int main(void)
{
Stack* stack = NULL;
stack=init(stack);
printStack(stack);
push(stack, 13);
push(stack, 23);
push(stack, 66);
push(stack, 16);
push(stack, 25);
push(stack, 33);
printStack(stack);
pop(stack);
pop(stack);
printStack(stack);
return 0;
}
单链表
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//宏定义常量
#define true 1
#define false 0
//C语言实现单链表
//链表结点结构体
typedef struct Node {
int data; //数据域(头结点的数据域存储链表结点数量，其他普通结点存储用户输入的数据)
struct Node *next; //指针域
} node;
//初始化链表
void initList(node *head)
{
if (head == NULL) {
head = (node*)malloc(sizeof(node));
}
head->next = NULL; //头结点指针指向空
head->data = 0; //头结点的数据源存储链表长度
printf("初始化链表成功......\n");
}
//自定义插入(index就是第几个结点位置插入)，比如10 20 30，index=2 data=40 =>10 40 20 30
int addNodeByIndex(node *head,int index,int data)
{
if (index<1 || index>head->data) {
printf("参数index不合法，请检查......\n");
return false;
}
else {
node* newNode = (node*)malloc(sizeof(node));
newNode->data = data;
node* p = (node*)malloc(sizeof(node));
p->next = head;
int cur = 0; //当前指针p指向的下标
while (true) {
if ((cur+1) == index) { //如果下一个结点是，则找到
newNode->next = p->next->next;
p->next->next = newNode;
head->data++;
printf("自定义插入成功......\n");
break;
}
else { //继续遍历
p->next = p->next->next;
cur++;
}
}
}
}
//往链表添加结点（头插法）
int headAddNode(node *head,int data) {
if (head == NULL) {
printf("链表头为空,自动初始化链表......\n");
initList(head);
printf("初始化链表成功......\n");
}
node* newNode = (node*)malloc(sizeof(node));
newNode->data = data;
//尾插法插入，有两种情况
//1：head->next!=NULL //这种情况是第一次插入元素的情况下执行，否则链表会断
if (head->next != NULL) {
addNodeByIndex(head,1,data);
}
//2:head->next==NULL //这种情况是在已经插入过元素的情况下执行
else{
head->next = newNode;
newNode->next = NULL;
//结点数量++
head->data++;
}
printf("头插法插入成功......\n");
return true;
}
//往链表添加结点（尾插法）
int tailAddNode(node *head,int data) {
if (head == NULL) {
printf("链表头为空,自动初始化链表......\n");
initList(head);
printf("初始化链表成功......\n");
}
node* newNode = (node*)malloc(sizeof(node)); //新结点
newNode->data = data;
node* p = (node*)malloc(sizeof(node));
p->next = head;
//找链表尾
while (1) {
if (p->next->next != NULL) {
p->next = p->next->next;
}
else {
//可以插入
p->next->next = newNode;
newNode->next = NULL;
//头结点的数据域+1（也就是链表长度+1）
head->data++;
printf("插入成功......\n");
break;
}
}
return true;
}
//修改结点数据
int updateNode(node *head,int index,int newDate) {
if (index<1 || index>head->data) {
printf("参数index不合法，修改失败......\n");
return false;
}
else {
int cur = 1;
node* p = (node*)malloc(sizeof(node));
p->next = head->next;
while (true) {
if (cur == index) {
p->next->data = newDate;
printf("修改结点数据成功......\n");
break;
}
else {
p->next = p->next->next;
cur++;
}
}
}
}
//清空链表
int clear(node* head)
{
head == NULL;
free(head); //释放内存
return true;
}
//删除指定index元素
int deleteNode(node *head,int index) {
if (index<1 || index>head->data) {
printf("参数index不合法，修改失败......\n");
return false;
}
else {
int cur = 0;
node* p = (node*)malloc(sizeof(node));
p->next = head;
while (true) {
if (cur+1 == index) {
node* d = p->next->next; //保存需要删除的结点，以便释放内存
p->next->next = p->next->next->next;
free(d);
printf("删除结点成功......\n");
break;
}
else {
p->next = p->next->next;
cur++;
}
}
}
}
//判断链表是否为空或者是否长度为0（也就是头结点的数据域是否为0）
int hasNULL(node *head) {
return (head == NULL || head->data == 0) ? true : false;
}
//遍历打印链表元素
void printList(node *head)
{
if (hasNULL(head) == true) {
printf("链表为空，遍历失败......\n");
return;
}
else
{
node* p = head->next; //创建一个指针p指向头结点的下一个
printf("打印链表元素......\n");
while (true)
{
if (p == NULL) {
printf("\n遍历完成......\n");
break;
}
else
{
printf("%d ", p->data);
p = p->next; //移动指针
}
}
}
}
int main(void) {
node* head = (node*)malloc(sizeof(node));
initList(head);
printList(head);
tailAddNode(head, 15);
tailAddNode(head, 25);
headAddNode(head,33);
headAddNode(head, 66);
updateNode(head, 3, 99);
printList(head);
deleteNode(head,1);
//clear(head);
printList(head);
return 0;
}
排序算法
#include <stdio.h>
#include <stdlib.h>
//排序数组 -leetCode
//冒泡排序 ---超时
int* sortArray1(int* nums, int numsSize, int* returnSize) {
returnSize = &numsSize; //*returnSize = numsSize; leetcode测试时需要改成这段代码，不然无法通过
printf("开始排序\n");
int i = 0;
int j = 0;
for ( i = 0; i < numsSize-1; i++)
{
for ( j = 1; j < numsSize-i; j++)
{
if (nums[j] < nums[j - 1])
{
int temp = nums[j - 1];
nums[j - 1] = nums[j];
nums[j] = temp;
}
}
}
return nums;
}
//选择排序 ---超时
int* sortArray2(int* nums, int numsSize, int* returnSize) {
returnSize = &numsSize;
int i = 0;
int j = 0;
for ( i = 0; i < numsSize-1; i++)
{
int minIndex = i; //假设的最小值，等待后续选出真正的最小值出来
int minData = nums[i];
for ( j = i+1; j < numsSize; j++)
{
if (nums[j] < minData)
{
//更新选择出来的最小值（但不一定是真正的最小值，最起码比假设出来的小）
minIndex = j;
minData = nums[j];
}
}
int temp = nums[i];
nums[i] = minData;
nums[minIndex] = temp;
}
return nums;
}
//插入排序 --超时
int* sortArray3(int* nums, int numsSize, int* returnSize) {
int j;
for ( j=1; j < numsSize; j++) //遍历无序表
{
int temp = j - 1; //指向有序表的最后一个元素，也就是无序表头的前一个元素
if (nums[j] < nums[temp]) //符合这个条件就要遍历有序表，找插入的位置
{
int cur=nums[j];
//for (temp; temp >= 0; temp--)
//{
// if (cur < nums[temp])
//{
// nums[temp+1] = nums[temp]; //后移
//}
//else {
// break;
// }
//}
//nums[temp + 1] = cur; //插入
//循环寻找插入点
while (1)
{
if (temp < 0|| cur >= nums[temp])
{
break;
}
else {
nums[temp + 1] = nums[temp];
temp--;
}
}
nums[temp + 1] = cur; //插入
}
}
return nums;
}
//快排
//找基准值的（下标）
int getPoint(int* nums,int left,int right)
{
//假设基准值是第一个左边元素
int p = nums[left];
while (left < right) //这里一定要进行循环判断,不然意思就是值比较一轮
{
//先比较右边
while (left < right && nums[right] >= p)
{
right--;
}
//进行交换
if (left < right)
{
int temp = nums[right];
nums[right] = nums[left];
nums[left] = temp;
}
//再比较左边
while (left < right && nums[left] <= p)
{
left++;
}
//进行交换
if (left < right)
{
int temp = nums[right];
nums[right] = nums[left];
nums[left] = temp;
}
}
return left; //返回基准值下标
}
void quickSort(int *nums,int left,int right)
{
if (left < right)
{
int point=getPoint(nums, left, right);
quickSort(nums,left,point-1); //以基准值的左边进行递归
quickSort(nums, point + 1, right);//以基准值的右边进行递归
}
}
int* sortArray4(int* nums, int numsSize, int* returnSize) {
printf("开始排序\n");
quickSort(nums,0,numsSize-1);
returnSize = &numsSize;
printf("排序结束\n");
return nums;
}
int main(void)
{
int arr[] = { 12,36,22,8,63,11,12,16,5,33,50,27 };
int numsSize = 12;
printf("排序前\n");
int i = 0;
for ( i = 0; i < numsSize; i++)
{
printf("%d ",arr[i]);
}
printf("\n");
//调用排序函数
int* returnSize = -1;
//int *resArr =sortArray1(arr, numsSize, returnSize);
//int* resArr = sortArray2(arr, numsSize, returnSize);
int* resArr = sortArray3(arr, numsSize, returnSize);
//int* resArr = sortArray4(arr, numsSize, returnSize);
printf("排序后\n");
int j = 0;
for (j = 0; j < numsSize; j++)
{
printf("%d ", resArr[j]);
}
printf("\n");
}
双向单链表
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define true 1
#define false 0
typedef int status;
typedef int elemtype;
//C实现双向单链表
typedef struct Node
{
elemtype data;
struct Node* pre; //指向上一个结点
struct Node* next; //指向下一个结点
} node;
typedef struct Node* linklist;
node* init(linklist head)
{
printf("init start......\n");
if (head == NULL)
{
head = (linklist)malloc(sizeof(node));
}
head->data = 0;
head->pre = NULL;
head->next = NULL;
if (head == NULL) {
printf("init fail......\n");
exit(0); //退出函数
}
else {
printf("init success......\n");
return head;
}
}
//头插法
status headInsertNode(linklist head,int data)
{
node* newNode = (node*)malloc(sizeof(node));
newNode->data=data;
if (head == NULL) {
init(head);
}
if (head->next == NULL) {
head->next = newNode;
newNode->next = NULL;
newNode->pre = head;
head->data++;
printf("insert success......\n");
return true;
}
else {
node* temp = (node*)malloc(sizeof(node)*1);
temp->next = head;
newNode->next = temp->next->next;
newNode->pre = temp->next;
temp->next->next = newNode;
temp->next->next->pre = newNode;
head->data++;
printf("insert success......\n");
return true;
}
}
//尾插
status tailInsertNode(linklist head, int data)
{
node* newNode = (node*)malloc(sizeof(node));
newNode->data = data;
if (head == NULL) {
init(head);
}
else {
node* temp = (node*)malloc(sizeof(node) * 1);
temp->next = head;
while (temp->next->next!=NULL)
{
temp->next = temp->next->next;
}
temp->next->next = newNode;
newNode->pre = temp->next;
newNode->next = NULL;
head->data++;
printf("insert success......\n");
return true;
}
}
//删除
status deleteNode(linklist head,int index)
{
if (index<1 || index>head->data) {
printf("参数index不合法，删除失败......\n");
exit(0);
}
else {
int cur = 0;
node* temp = (node*)malloc(sizeof(node));
temp->next = head;
while ((cur + 1) != index)
{
temp->next = temp->next->next;
cur++;
}
node* d = temp->next->next;
temp->next->next = temp->next->next->next;
head->data--;
free(d); //释放内存
printf("delete node success......\n");
return true;
}
}
void printList(linklist head)
{
printf("print start......\n");
node* p = (node*)malloc(sizeof(node));
p->next = head->next;
while (p->next!=NULL)
{
printf("%d ",p->next->data);
p->next = p->next->next;
}
printf("\nprint success......\n");
}
int main(void)
{
linklist head=NULL;
head=init(head);
printList(head);
headInsertNode(head, 11);
headInsertNode(head, 22);
tailInsertNode(head, 33);
tailInsertNode(head, 66);
printList(head);
deleteNode(head, 2);
printList(head);
return 0;
}
更多推荐
数据结构与算法入门教程（C语言实现版）
发布评论