无锡高端网站设计开发,群晖wordpress外网仿问设置,企业流程管理系统,网站图标 psd文章目录 顺序存储链式存储单向链表循环链表 线性表的定义 (1)概念定义#xff1a;用数据元素的有限序列表示叫做线性表#xff1b;线性表中数据元素的类型可以为简单类型#xff0c;也可以为复杂类型。许多实际应用问题所涉的基本操作有很大相似性#xff0c;不应为每个具… 文章目录 顺序存储链式存储单向链表循环链表 线性表的定义 (1)概念定义用数据元素的有限序列表示叫做线性表线性表中数据元素的类型可以为简单类型也可以为复杂类型。许多实际应用问题所涉的基本操作有很大相似性不应为每个具体应用单独编写一个程序。从具体应用中抽象出共性的逻辑结构和基本操作抽象数据类型然后实现其存储结构和基本操作。(2)类型定义首先抽象出ADT List表的结构在C/C中一般都是采用struct来实现的。基本操作有如下InitList(L)创建一个新表DestroyList(L)销毁一个线性表ClearList(L)清空表ListEmpty(L)判断表是否为空ListLength(L)求表的长度GetElem(L,i,e)读取表的元素LocateElem(L,e)查找表的元素 PriorElem(L,cur_ e,pre _e)求表的前驱NextElem(L,cur_ e,next_e) 求表的后继ListInsert(L,i,e) 前插表ListDelete(L,i,e)删除表TraverseList (L)遍历表顺序存储 顺序存储结构将线性表中的元素存储在连续的内存空间中。每个元素占据固定大小的存储空间其物理位置和索引号相对应。顺序存储结构的优点是访问元素的速度快缺点是插入和删除操作复杂需要移动后续元素。 顺序存储的底层实现就是使用数组来实现主要就是对数组进行操作。当内存不足时重新分配一块新的内存这块内存为原来内存的2倍并将原来内存的值复制到新的内存里。 DynamicArray.h
#pragma once
#ifndef DYNAMIC_ARRAY_H
#define DYNAMIC_ARRAY_H#includestdio.h
#includestdlib.h
#includestring.h//动态增长内存策略将存放数据的内存放到那堆上
//动态数组 如果5个元素 申请内存 拷贝数据 释放内存 6插入第七个
//容量capacity表示我的这块内存空间一共可以存放多少元素
// size概念记录当前数组中具体的元素个数了typedef struct DYNAMICARRAY {int* pAddr; //存放数据的地址int size; //当前有多少个元素int capacity; // 容量我容器当前最大能容纳多少元素
}Dynamic_Array;//写一系列的相关对DYNAMICARRAY结构体操作的函数
//初始化
Dynamic_Array* Init_Array();
//插入
void Push_Back_Array(Dynamic_Array* arr, int value);
//根据位置删除
void RemoveByPos_Array(Dynamic_Array* arr, int pos);
//根据值删除
void RemoveByValue_Array(Dynamic_Array* arr, int value);
//查找
int Find_Array(Dynamic_Array* arr, int value);
//打印
void Print_Array(Dynamic_Array* arr);
//释放动态数组的内存
void FreeSpace_Array(Dynamic_Array* arr);
// 清空数组
void Clear_Array(Dynamic_Array* arr);
//获得动态数组容量
int Capacity_Array(Dynamic_Array* arr);
//获得动态数据当前元素个数
int Size_Array(Dynamic_Array* arr);
// 根据位置获得某个位置元素
int At_Array(Dynamic_Array* arr, int pos);#endifDynamicArray.c
#include DynamicArray.h//初始化
Dynamic_Array* Init_Array()
{Dynamic_Array* myarray (Dynamic_Array*)malloc(sizeof(Dynamic_Array));//初始化myarray-capacity 20;myarray-size 0;myarray-pAddr (int*)malloc(sizeof(int) * myarray-capacity);return myarray;
}//插入
void Push_Back_Array(Dynamic_Array* arr, int value)
{if (!arr){return;}//查看空间是否足够if (arr-size arr-capacity){//扩大容量为原来的两倍int* newSpace (int*)malloc(sizeof(int) * arr-capacity * 2);memcpy(newSpace, arr-pAddr, arr-capacity * sizeof(int));//释放旧空间的内存free(arr-pAddr);arr-pAddr newSpace;arr-capacity * 2;}//插入新元素 arr-pAddr[arr-size] value;arr-size;
}
//根据位置删除
void RemoveByPos_Array(Dynamic_Array* arr, int pos)
{if (!arr){return;}for (int i pos; i arr-size - 1; i){arr-pAddr[i] arr-pAddr[i 1];}arr-size--;}
//根据值删除
void RemoveByValue_Array(Dynamic_Array* arr, int value)
{//找到值的位置int pos Find_Array(arr, value);//根据位置删除RemoveByPos_Array(arr, pos);
}//查找
int Find_Array(Dynamic_Array* arr, int value)
{if (!arr){return -1;}int pos -1;for (int i 0; i arr-size; i){if (arr-pAddr[i] value){pos i;break;}}return pos;
}//打印
void Print_Array(Dynamic_Array* arr)
{if (!arr){return;}for (int i 0; i arr-size; i){printf(%d , arr-pAddr[i]);}printf(\n);
}//释放动态数组的内存
void FreeSpace_Array(Dynamic_Array* arr)
{if (!arr){return;}if (arr-pAddr ! NULL){free(arr-pAddr);}free(arr);
}// 清空数组
void Clear_Array(Dynamic_Array* arr)
{if (!arr){return;}arr-size 0;
}//获得动态数组容量
int Capacity_Array(Dynamic_Array* arr)
{if (!arr){return -1;}return arr-capacity;
}
//获得动态数据当前元素个数
int Size_Array(Dynamic_Array* arr)
{if (!arr){return -1;}return arr-size;
}// 根据位置获得某个位置元素
int At_Array(Dynamic_Array* arr, int pos)
{return arr-pAddr[pos];
}main.c
#include DynamicArray.hvoid test01()
{//初始化动态数组Dynamic_Array* myArray Init_Array();//打印容量printf(数组容量%d\n, Capacity_Array(myArray));printf(数组大小%d\n, Size_Array(myArray));//插入元素for (int i 0; i 30; i) {Push_Back_Array(myArray, i);}printf(数组容量%d\n, Capacity_Array(myArray));printf(数组大小%d\n, Size_Array(myArray));//打印Print_Array(myArray);//删除RemoveByPos_Array(myArray, 0);RemoveByValue_Array(myArray, 27);//打印Print_Array(myArray);//查找5个位置int pos Find_Array(myArray, 5);printf(查找第5处位置的下标(pos值):%d值: %d\n, pos, At_Array(myArray, pos));//销毁FreeSpace_Array(myArray);
}int main()
{test01();return 0;
}链式存储 链式存储结构将线性表中的元素存储在分散的内存空间中。每个元素由一个节点组成包含数据和指向下一个节点的指针。链式存储结构的优点是插入和删除操作简单无需移动其他元素。缺点是访问元素的速度较慢需要遍历链表。
单向链表 主要就是定义了一个数据结构里面包含了一个数据域和一个指针域每一个节点的指针域指向下一个节点的地址通过这种方式使用一个头节点就可以遍历整个链表。 LinkList.h
#pragma once
#ifndef LINKLIST_H
#define LINKLIST_H#includestdio.h
#includestdlib.h//链表节点
typedef struct LINKNODE {void* data; //指向任何类型的数据struct LINKNODE* next;
}LinkNode;//链表结构体
typedef struct LINKLIST {LinkNode* head;int size;}LinkList;//打印函数指针,自定义类型写法
typedef void(*PRINTLINKNODE)(void*);//比较函数指针
//typedef int(*COMPARENODE)(LinkNode*, LinkNode*);//初始化链表
LinkList* Init_LinkList();
//指定位置插入
void Insert_LinkList(LinkList* list, int pos, void* data);
//删除指定位置的值
void RemoveByPos_LinkList(LinkList* list, int pos);
//获得链表的长度
int Size_LinkList(LinkList* list);
//查找
//int Find_LinkList(LinkList* list, void* data, COMPARENODE compare);
int Find_LinkList(LinkList* list, void* data);
//返回第一个结点
void* Front_LinkList(LinkList* list);
//打印链表结点
void Print_LinkList(LinkList* list, PRINTLINKNODE print);
//释放链表内存
void FreeSpace_LinkList(LinkList* list);#endif // !LINKLIST_H
LinkList.c
#include LinkList.h//初始化链表
LinkList* Init_LinkList()
{LinkList* myList (LinkList*)malloc(sizeof(LinkList));myList-size 0;//头结点不保存数据myList-head (LinkNode*)malloc(sizeof(LinkNode));myList-head-data NULL;myList-head-next NULL;return myList;
}//指定位置插入
void Insert_LinkList(LinkList* list, int pos, void* data)
{if (!list){return;}if (pos 0 || pos list-size){pos list-size;}//创建新节点LinkNode* newNode (LinkNode*)malloc(sizeof(LinkNode));newNode-next NULL;newNode-data data;//找到辅助指针变量LinkNode* pCurrent list-head;for (int i 0; i pos; i){pCurrent pCurrent-next;}//新节点联入表newNode-next pCurrent-next;pCurrent-next newNode;list-size;
}//删除指定位置的值
void RemoveByPos_LinkList(LinkList* list, int pos)
{if (!list){return;}if (pos 0 || pos list-size){return;}LinkNode* pCurrent list-head;for (int i 0; i pos; i) {pCurrent pCurrent-next;}LinkNode* pDel pCurrent-next;pCurrent-next pDel-next;free(pDel);list-size--;
}//获得链表的长度
int Size_LinkList(LinkList* list)
{return list-size;
}
//查找
int Find_LinkList(LinkList* list, void* data)
{if (!list || !data){return -1;}LinkNode* pCurrent list-head-next;int index 0;int flag -1;while (pCurrent){if (pCurrent-data data){flag index;break;}index;pCurrent pCurrent-next;}return flag;
}
//返回第一个结点
void* Front_LinkList(LinkList* list)
{return list-head-next-data;
}
//打印链表结点
void Print_LinkList(LinkList* list, PRINTLINKNODE print)
{if (!list){return;}LinkNode* pCurrent list-head-next;while (pCurrent){print(pCurrent-data);pCurrent pCurrent-next;}
}//释放链表内存
void FreeSpace_LinkList(LinkList* list)
{if (!list){return;}LinkNode* pCurrent list-head-next;while (pCurrent){LinkNode* pNode pCurrent-next;free(pCurrent);pCurrent pNode;}list-size 0;free(list);
}main.c
#include LinkList.h//自定义数据类型
typedef struct PERSON {char name[64];int age;int score;
}Person;void MyPrint(void* data)
{Person* person (Person*)data;printf(结点数据Name:%s, Age:%d, Score:%d\n, person-name, person-age, person-score);
}int main()
{//创建一个链表LinkList* list Init_LinkList();//创建数据Person p1 { 青铜, 18, 80 };Person p2 { 白银, 19, 85 };Person p3 { 黄金, 20, 90 };Person p4 { 钻石, 21, 95 };Person p5 { 星耀, 22, 100 };//数据插入链表Insert_LinkList(list, 0, p1);Insert_LinkList(list, 0, p2);Insert_LinkList(list, 0, p3);Insert_LinkList(list, 0, p4);Insert_LinkList(list, 0, p5);//打印Print_LinkList(list, MyPrint);//删除3RemoveByPos_LinkList(list, 3);//打印printf(--------------------\n);Print_LinkList(list, MyPrint);//返回第一个结点printf(--------------------\n);Person* ret (Person*)Front_LinkList(list);printf(首结点数据Name:%s, Age:%d, Score:%d\n, ret-name, ret-age, ret-score);/*//查找(比较的是已有指针类型的data),返回其索引值Person f1 { 青铜2, 18, 80 };Person f2 { 青铜, 18, 80 };int index Find_LinkList(list, f1, MyCompare);printf(查到的索引值%d, index);*///销毁链表FreeSpace_LinkList(list);return 0;
}循环链表 循环链表和单链表的主要区别就是循环链表的尾节点的指针域会指向头结点的节点。 CircleLinkList.h
#pragma once
#ifndef CIRCLELINKLIST_H
#define CIRCLELINKLIST_H#include stdlib.h
#include stdio.h//链表的小节点
typedef struct CIRCLELINKNODE {struct CIRCLELINKNODE* next;
}CircleLinkNode;//链表结构体
typedef struct CIRCLELINKLIST {CircleLinkNode head;int size;
}CircleLinkList;//编写针对链表结构体操作的API函数#define CIRCLELINKLIST_TRUE 1
#define CIRCLELINKLIST_FALSE 0//比较回调
typedef int(*COMPARENODE)(CircleLinkNode*, CircleLinkNode*);//打印回调
typedef void(*PRINTNODE)(CircleLinkNode*);//初始化函数
CircleLinkList* Init_CircleLinkList();
//插入函数
void Insert_CircleLinkList(CircleLinkList* clist, int pos, CircleLinkNode* data);
// 获得第一个元素
CircleLinkNode* Front_CircleLinkList(CircleLinkList* clist);
//根据位置删除
void RemoveByPos_CircleLinkList(CircleLinkList* clist, int pos);
//根据值去删除
void RemoveByValue_CircleLinkList(CircleLinkList* clist, CircleLinkNode* data, COMPARENODE compare);
//获得链表的长度
int Size_CircleLinkList(CircleLinkList* clist);
//判断是否为空
int IsEmpty_CircleLinkList(CircleLinkList* clist);
//查找
int Find_CircleLinkList(CircleLinkList* clist, CircleLinkNode* data, COMPARENODE compare);
//打印节点
void Print_CircleLinkList(CircleLinkList* clist, PRINTNODE print);
//释放内存
void FreeSpace_CircleLinkList(CircleLinkList* clist);#endif // !CIRCLELINKLIST_H
CircleLinkList.c
#include CircleLinkList.h//初始化函数
CircleLinkList* Init_CircleLinkList()
{CircleLinkList* list (CircleLinkList*)malloc(sizeof(CircleLinkList));list-head.next (list-head);list-size 0;return list;
}
//插入函数
void Insert_CircleLinkList(CircleLinkList* clist, int pos, CircleLinkNode* data)
{if (!clist){return;}if (pos0 || posclist-size){pos clist-size;}CircleLinkNode* pCurrent (clist-head);for (int i 0; i pos; i){pCurrent pCurrent-next;}data-next pCurrent-next;pCurrent-next data;clist-size;
}
// 获得第一个元素
CircleLinkNode* Front_CircleLinkList(CircleLinkList* clist)
{return clist-head.next;
}//根据位置删除
void RemoveByPos_CircleLinkList(CircleLinkList* clist, int pos)
{if (!clist){return;}if (pos 0 || pos clist-size){return;}CircleLinkNode* pCurrent (clist-head);for (int i 0; i pos; i){pCurrent pCurrent-next;}pCurrent-next pCurrent-next-next;clist-size--;
}//根据值去删除
void RemoveByValue_CircleLinkList(CircleLinkList* clist, CircleLinkNode* data, COMPARENODE compare)
{if (!clist || !data){return;}CircleLinkNode* pPrev (clist-head);CircleLinkNode* pCurrent pPrev-next;for (int i 0; i clist-size; i){if (compare(pCurrent, data) CIRCLELINKLIST_TRUE){pPrev-next pCurrent-next;clist-size--;break;}pPrev pCurrent;pCurrent pCurrent-next;}
}//获得链表的长度
int Size_CircleLinkList(CircleLinkList* clist)
{return clist-size;
}//判断是否为空
int IsEmpty_CircleLinkList(CircleLinkList* clist)
{if (clist-size 0) {return CIRCLELINKLIST_TRUE;}return CIRCLELINKLIST_FALSE;
}//查找
int Find_CircleLinkList(CircleLinkList* clist, CircleLinkNode* data, COMPARENODE compare)
{if (!clist || !data){return -1;}int index 0;int flag -1;CircleLinkNode* pCurrent clist-head.next;for (int i 0; i clist-size; i){if (compare(pCurrent, data) CIRCLELINKLIST_TRUE){flag index;break;}pCurrent pCurrent-next;index;}return index;
}//打印节点
void Print_CircleLinkList(CircleLinkList* clist, PRINTNODE print)
{if (!clist){return;}CircleLinkNode* pCurrent clist-head.next;for (int i 0; i clist-size * 2; i){if (pCurrent (clist-head)){pCurrent pCurrent-next;printf(-----------------------\n);}print(pCurrent);pCurrent pCurrent-next;}
}//释放内存
void FreeSpace_CircleLinkList(CircleLinkList* clist)
{if (!clist){return;}free(clist);
}main.c
#define _CRT_SECURE_NO_WARNINGS
#include stdio.h
#include stdlib.h
#include string.h
#include CircleLinkList.htypedef struct PERSON {CircleLinkNode node;char name[64];int age;int score;
} Person;void MyPrint(CircleLinkNode* data) {Person* p (Person*)data;printf(Name:%s, Age:%d, Score:%d\n, p-name, p-age, p-score);
}int MyCompare(CircleLinkNode* data1, CircleLinkNode* data2) {Person* p1 (Person*)data1;Person* p2 (Person*)data2;if (strcmp(p1-name, p2-name) 0 p1-age p2-age p1-score p2-score) {return CIRCLELINKLIST_TRUE;}return CIRCLELINKLIST_FALSE;
}
int main(void) {//创建循环链表CircleLinkList* clist Init_CircleLinkList();//创建数据Person p1, p2, p3, p4, p5;strcpy(p1.name, aaa);strcpy(p2.name, bbb);strcpy(p3.name, ccc);strcpy(p4.name, ddd);strcpy(p5.name, eee);p1.age 10;p2.age 20;p3.age 30;p4.age 40;p5.age 50;p1.score 50;p2.score 60;p3.score 70;p4.score 80;p5.score 90;//数据入链表Insert_CircleLinkList(clist, 100, (CircleLinkNode*)p1);Insert_CircleLinkList(clist, 100, (CircleLinkNode*)p2);Insert_CircleLinkList(clist, 100, (CircleLinkNode*)p3);Insert_CircleLinkList(clist, 100, (CircleLinkNode*)p4);Insert_CircleLinkList(clist, 100, (CircleLinkNode*)p5);//打印Print_CircleLinkList(clist, MyPrint);Person pDel;strcpy(pDel.name, ccc);pDel.age 30;pDel.score 70;//根据值删除RemoveByValue_CircleLinkList(clist, (CircleLinkNode*)pDel, MyCompare);//打印printf(------------\n);Print_CircleLinkList(clist, MyPrint);//释放内存FreeSpace_CircleLinkList(clist);system(pause);return 0;
}
