如何建设一个国外网站,建站平台的基础概念,建网站的优势,企业宣传类网站建设在数据结构逻辑层次上细分#xff0c;线性表可分为一般线性表和受限线性表。一般线性表也就是我们通常所说的“线性表”#xff0c;可以自由的删除或添加结点。受限线性表主要包括栈和队列#xff0c;受限表示对结点的操作受限制。一般线性表详解#xff0c;请参考文章线性表可分为一般线性表和受限线性表。一般线性表也就是我们通常所说的“线性表”可以自由的删除或添加结点。受限线性表主要包括栈和队列受限表示对结点的操作受限制。一般线性表详解请参考文章C语言数据结构一—— 数据结构理论、线性表【动态数组、链表企业版单向链表】1栈(Stack)1.1栈的基本概念概念首先它是一个线性表也就是说栈元素具有线性关系即前驱后继关系。只不过它是一种特殊的线性表而已。定义中说是在线性表的表尾进行插入和删除操作这里表尾是指栈顶而不是栈底。特性它的特殊之处在于限制了这个线性表的插入和删除的位置它始终只在栈顶进行。这也就使得栈底是固定的最先进栈的只能在栈底。符合先进后出的数据结构。操作栈的插入操作叫做进栈也成压栈。类似子弹入弹夹如下图所示栈的删除操作叫做出栈也有的叫做弾栈退栈。如同弹夹中的子弹出夹如下图所示遍历不重复不遗漏查看每个元素并且执行过后不会更改元素遍历算法属于非质变算法栈能否遍历不能1.2栈的顺序存储基本概念栈的顺序存储结构简称顺序栈它是运算受限制的顺序表。顺序栈的存储结构是利用一组地址连续的的存储单元依次存放自栈底到栈顶的数据元素同时附设指针top只是栈顶元素在顺序表中的位置。设计与实现因为栈是一种特殊的线性表所以栈的顺序存储可以通过顺序线性表来实现。数组首地址端做栈底尾地址端做栈顶方便数据插入和删除。对外接口设计初始化入栈出栈返回栈顶返回元素个数判断是否为空销毁栈#define _CRT_SECURE_NO_WARNINGS
#includestdlib.h
#includestdio.h
#includestring.h
#define MAX 1024struct SStack {//栈中的数组void * data[MAX];//栈的大小int m_Size;
};typedef void * SeqStack;//初始化栈
SeqStack init_SeqStack() {struct SStack * myStack malloc(sizeof(struct SStack));if (myStack NULL) {return NULL;}memset(myStack-data, 0, sizeof(void *) * MAX);myStack-m_Size 0;return myStack;
}//入栈
void push_SeqStack(SeqStack stack, void * data) {//本质 数组的尾插if (stack NULL) {return;}if (data NULL) {return;}//还原栈结构体struct SStack * myStack stack;//判断栈是否满if (myStack-m_Size MAX) {return;}//数组进行尾插myStack-data[myStack-m_Size] data;//更新栈大小myStack-m_Size;
}//出栈
void pop_SeqStack(SeqStack stack) {//本质 数组的尾删除if (stack NULL) {return;}//还原栈结构体struct SStack * myStack stack;if (myStack-m_Size 0) {return;}myStack-data[myStack-m_Size - 1] NULL;myStack-m_Size--;
}//返回栈顶
void * top_SeqStack(SeqStack stack) {//本质 返回数组的最后一个元素if (stack NULL) {return NULL;}//还原栈结构体struct SStack * myStack stack;if (myStack-m_Size 0) {return NULL;}return myStack-data[myStack-m_Size - 1];
}//返回栈大小
int size_SeqStack(SeqStack stack) {if (stack NULL) {return -1;}//还原栈结构体struct SStack * myStack stack;return myStack-m_Size;
}//判断栈是否为空
int isEmpty_SeqStack(SeqStack stack) {if (stack NULL) {return -1; //传入空指针 返回真 栈也是空}//还原栈结构体struct SStack * myStack stack;if (myStack-m_Size 0) {return 1; //1 代表真 栈确实为空}return 0;// 0假 不为空
}//销毁
void destroy_SeqStack(SeqStack stack) {if (stack NULL) {return;}free(stack);stack NULL;
}struct Person {char name[64];int age;
};void test() {//创建栈SeqStack myStack init_SeqStack();//创建数据struct Person p1 { 赵云, 18 };struct Person p2 { 张飞, 19 };struct Person p3 { 关羽, 20 };struct Person p4 { 刘备, 19 };struct Person p5 { 诸葛亮, 12 };struct Person p6 { 黄忠, 17 };//入栈push_SeqStack(myStack, p1);push_SeqStack(myStack, p2);push_SeqStack(myStack, p3);push_SeqStack(myStack, p4);push_SeqStack(myStack, p5);push_SeqStack(myStack, p6);printf(栈的大小为%d\n, size_SeqStack(myStack));//栈不为空 开始查看栈顶 并出栈while (isEmpty_SeqStack(myStack) 0) {struct Person * pTop top_SeqStack(myStack);printf(栈顶元素-姓名%s 年龄%d \n, pTop-name, pTop-age);//出栈pop_SeqStack(myStack);}printf(栈的大小为%d\n, size_SeqStack(myStack));}//程序入口
int main() {test();system(pause); // 按任意键暂停 阻塞功能return EXIT_SUCCESS; //返回 正常退出值 0}1.3栈的链式存储基本概念栈的链式存储结构简称链栈。思考如下问题栈只是栈顶来做插入和删除操作栈顶放在链表的头部还是尾部呢由于单链表有头指针而栈顶指针也是必须的那干嘛不让他俩合二为一呢所以比较好的办法就是把栈顶放在单链表的头部。另外都已经有了栈顶在头部了单链表中比较常用的头结点也就失去了意义通常对于链栈来说是不需要头结点的。设计与实现链栈是一种特殊的线性表链栈可以通过链式线性表来实现。头节点端做栈顶比较方便。对外接口设计初始化入栈出栈返回栈顶返回元素个数判断是否为空销毁栈#define _CRT_SECURE_NO_WARNINGS
#includestdlib.h
#includestdio.h
#includestring.h//节点结构体
struct LinkNode{//只维护指针域struct LinkNode * next;
};//链表结构体
struct LStack {struct LinkNode pHeader;//头节点int m_Size;//栈大小
};typedef void * LinkStack;//初始化
LinkStack init_LinkStack() {struct LStack * mystack malloc(sizeof(struct LStack));if (mystack NULL) {return NULL;}mystack-pHeader.next NULL;mystack-m_Size 0;return mystack;
}//入栈
void push_LinkStack(LinkStack stack, void * data) {//本质 头插if (stack NULL) {return;}if (data NULL) {return;}struct LStack * mystack stack;//取出用户的前4个字节struct LinkNode * myNode data;//建立节点之间的关系myNode-next mystack-pHeader.next;mystack-pHeader.next myNode;//更新栈的大小mystack-m_Size;
}//出栈
void pop_LinkStack(LinkStack stack) {//本质 头删if (stack NULL) {return;}struct LStack * mystack stack;if (mystack-m_Size 0) {return;}//记录指向第一个节点的指针struct LinkNode * pFirst mystack-pHeader.next;//更新节点指向mystack-pHeader.next pFirst-next;//更新栈大小mystack-m_Size--;
}//返回栈顶
void * top_LinkStack(LinkStack stack) {if (stack NULL) {return NULL;}struct LStack * mystack stack;if (mystack-m_Size 0) {return NULL;}return mystack-pHeader.next;
}//返回元素个数
int size_LinkStack(LinkStack stack) {if (stack NULL) {return -1;}struct LStack * mystack stack;return mystack-m_Size;
}//判断是否为空
int isEmpty_LinkStack(LinkStack stack) {if (stack NULL) {return -1;}struct LStack * mystack stack;if (mystack-m_Size 0) {return 1; //为空 返回真}return 0;
}//销毁栈
void destroy_LinkStack(LinkStack stack) {if (stack NULL) {return;}free(stack);stack NULL;
}struct Person {struct LinkNode node;char name[64];int age;
};void test() {//创建栈LinkStack myStack init_LinkStack();//创建数据struct Person p1 { NULL,赵云, 18 };struct Person p2 { NULL,张飞, 19 };struct Person p3 { NULL,关羽, 20 };struct Person p4 { NULL,刘备, 19 };struct Person p5 { NULL,诸葛亮, 12 };struct Person p6 { NULL,黄忠, 17 };//入栈push_LinkStack(myStack, p1);push_LinkStack(myStack, p2);push_LinkStack(myStack, p3);push_LinkStack(myStack, p4);push_LinkStack(myStack, p5);push_LinkStack(myStack, p6);printf(栈的大小为%d\n, size_LinkStack(myStack));//栈不为空 开始查看栈顶 并出栈while (isEmpty_LinkStack(myStack) 0) {struct Person * pTop top_LinkStack(myStack);printf(栈顶元素-姓名%s 年龄%d \n, pTop-name, pTop-age);//出栈pop_LinkStack(myStack);}printf(栈的大小为%d\n, size_LinkStack(myStack));
}//程序入口
int main() {test();system(pause); // 按任意键暂停 阻塞功能return EXIT_SUCCESS; //返回 正常退出值 0}1.4 栈的应用(案例)1.4.1 就近匹配几乎所有的编译器都具有检测括号是否匹配的能力那么如何实现编译器中的符号成对检测如下字符串: 55*(6)9/3*1)-(13(算法思路从第一个字符开始扫描当遇见普通字符时忽略当遇见左括号时压入栈中当遇见右括号时从栈中弹出栈顶符号并进行匹配匹配成功继续读入下一个字符匹配失败立即停止并报错结束成功: 所有字符扫描完毕且栈为空失败匹配失败或所有字符扫描完毕但栈非空总结当需要检测成对出现但又互不相邻的事物时可以使用栈“后进先出”的特性栈非常适合于需要“就近匹配”的场合1.4.2 中缀表达式和后缀表达式后缀表达式由波兰科学家在20世纪50年代提出将运算符放在数字后面 》 符合计算机运算我们习惯的数学表达式叫做中缀表达式》符合人类思考习惯实例5 4 5 4 1 2 * 3 1 2 3 * 8 (3 – 1 ) * 5 8 3 1 – 5 * 中缀转后缀算法遍历中缀表达式中的数字和符号对于数字直接输出对于符号左括号进栈 运算符号与栈顶符号进行优先级比较若栈顶符号优先级低此符号进栈 默认栈顶若是左括号左括号优先级最低若栈顶符号优先级不低将栈顶符号弹出并输出之后进栈右括号将栈顶符号弹出并输出直到匹配左括号,将左括号和右括号同时舍弃遍历结束将栈中的所有符号弹出并输出动手练习将我们喜欢的读的中缀表达式转换成计算机喜欢的后缀表达式中缀表达式: 8 ( 3 – 1 ) * 5 后缀表达式: 8 3 1 – 5 * 1.4.3 基于后缀表达式计算思考计算机是如何基于后缀表达式计算的例如8 3 1 –5 * 计算规则遍历后缀表达式中的数字和符号对于数字进栈对于符号从栈中弹出右操作数从栈中弹出左操作数根据符号进行运算将运算结果压入栈中遍历结束栈中的唯一数字为计算结果2队列(Queue)2.1队列基本概念队列是一种特殊的受限制的线性表。 队列queue是只允许在一端进行插入操作而在另一端进行删除操作的线性表。队列是一种先进先出的tFirst In First Out的线性表简称FIFO。允许插入的一端为队尾允许删除的一端为队头。队列不允许在中间部位进行操作假设队列是qa1a2……an那么a1就是队头元素而an是队尾元素。这样我们就可以删除时总是从a1开始而插入时总是在队列最后。这也比较符合我们通常生活中的习惯排在第一个的优先出列最后来的当然排在队伍最后。如下图2.3队列的顺序存储基本概念队列也是一种特殊的线性表可以用线性表顺序存储来模拟队列。对外接口设计初始化队列 init入队 push出队 pop返回队头 front返回队尾 back返回队列大小 size判断是否为空 isEmpty销毁队列 destroy头文件 dynamicArray.h:#pragma once
#define _CRT_SECURE_NO_WARNINGS
#includestdio.h
#includestring.h
#includestdlib.h//动态数据结构体
struct dynamicArray
{void ** pAddr; // 维护开辟到堆区真实数组的指针int m_Capacity; //数组容量int m_Size; //数组大小
};//初始化数组 参数代表 初始化的容量
struct dynamicArray * init_dynamicArray(int capacity);//插入元素
void insert_dynamicArray(struct dynamicArray * arr, int pos, void * data);//遍历数组
void foreach_dynamicArray(struct dynamicArray * arr, void(*myPrint)(void *));//删除数组
void removeByPos_dynamicArray(struct dynamicArray * arr, int pos);//按照值 来删除数组中数据
void removeByValue_dynamicArray(struct dynamicArray * arr, void * data, int(*myCompare)(void *, void *));//销毁数组
void destroy_dynamicArray(struct dynamicArray * arr);
头文件dynamicArray.h :#pragma once
#define _CRT_SECURE_NO_WARNINGS
#includestdio.h
#includestring.h
#includestdlib.h
#include dynamicArray.h#define MAX 1024typedef void * seqQueue;//初始化队列
seqQueue init_SeqQueue();
//入队
void push_SeqQueue( seqQueue queue , void * data);
//出队
void pop_SeqQueue(seqQueue queue);
//返回队头元素
void * front_SeqQueue(seqQueue queue);//返回队尾元素
void * back_SeqQueue(seqQueue queue);//队列大小
int size_SeqQueue(seqQueue queue);//判断是否为空
int isEmpty_SeqQueue(seqQueue queue);//销毁队列
void destroy_SeqQueue(seqQueue queue);源文件 dynamicArray.c :#include dynamicArray.h//初始化数组 参数代表 初始化的容量
struct dynamicArray * init_dynamicArray(int capacity)
{struct dynamicArray * array malloc(sizeof(struct dynamicArray));if (array NULL){return NULL;}//给数组属性初始化array-m_Capacity capacity;array-m_Size 0;array-pAddr malloc(sizeof(void *)* capacity);if (array-pAddr NULL){return NULL;}return array;
}//插入元素
void insert_dynamicArray(struct dynamicArray * arr, int pos, void * data)
{if (arr NULL){return;}if (data NULL){return;}if (pos 0 || pos arr-m_Size){//无效的位置 进行尾插pos arr-m_Size;}//判断是否有空间进行插入如果没有空间了那么动态扩展if (arr-m_Size arr-m_Capacity){//1、计算申请空间大小int newCapacity arr-m_Capacity * 2;//2、创建新空间void ** newSpace malloc(sizeof (void *)* newCapacity);//3、 将原有数据拷贝到新空间下memcpy(newSpace, arr-pAddr, sizeof(void*)* arr-m_Capacity);//4、 释放原有空间free(arr-pAddr);//5、 更新指针的指向arr-pAddr newSpace;//6、更新新数组容量arr-m_Capacity newCapacity;}//插入数据for (int i arr-m_Size - 1; i pos; i--){//数据后移arr-pAddr[i 1] arr-pAddr[i];}//将新数据放入到指定位置中arr-pAddr[pos] data;//更新数组大小arr-m_Size;
}//遍历数组
void foreach_dynamicArray(struct dynamicArray * arr, void(*myPrint)(void *))
{if (arr NULL){return;}if (myPrint NULL){return;}for (int i 0; i arr-m_Size; i){myPrint(arr-pAddr[i]);}
}//删除数组
void removeByPos_dynamicArray(struct dynamicArray * arr, int pos)
{if (arr NULL){return;}//无效位置 就直接returnif (pos 0 || pos arr-m_Size - 1){return;}//移动数据for (int i pos; i arr-m_Size - 1; i){arr-pAddr[i] arr-pAddr[i 1];}//更新大小arr-m_Size--;}//按照值 来删除数组中数据
void removeByValue_dynamicArray(struct dynamicArray * arr, void * data, int(*myCompare)(void *, void *))
{if (arr NULL){return;}if (data NULL){return;}for (int i 0; i arr-m_Size; i){if (myCompare(arr-pAddr[i], data)){//如果对比成功了那么要删除i下标的元素removeByPos_dynamicArray(arr, i);break;}}}//销毁数组
void destroy_dynamicArray(struct dynamicArray * arr)
{if (arr NULL){return;}if (arr-pAddr ! NULL){free(arr-pAddr);arr-pAddr NULL;}free(arr);arr NULL;}源文件 seqQueue.c :#include seqQueue.h//初始化队列
seqQueue init_SeqQueue()
{struct dynamicArray * array init_dynamicArray(MAX);return array;
}
//入队
void push_SeqQueue(seqQueue queue, void * data)
{//等价于 尾插if (queue NULL){return;}if (data NULL){return;}struct dynamicArray * array queue;if (array-m_Size MAX){return;}insert_dynamicArray(array, array-m_Size, data);
}
//出队
void pop_SeqQueue(seqQueue queue)
{//等价于 头删除if (queue NULL){return;}struct dynamicArray * array queue;if (array-m_Size 0){return;}removeByPos_dynamicArray(array, 0);
}
//返回队头元素
void * front_SeqQueue(seqQueue queue)
{if (queue NULL){return NULL;}struct dynamicArray * array queue;return array-pAddr[0];}//返回队尾元素
void * back_SeqQueue(seqQueue queue)
{if (queue NULL){return NULL;}struct dynamicArray * array queue;return array-pAddr[array-m_Size - 1];}//队列大小
int size_SeqQueue(seqQueue queue)
{if (queue NULL){return -1;}struct dynamicArray * array queue;return array-m_Size;}//判断是否为空
int isEmpty_SeqQueue(seqQueue queue)
{if (queue NULL){return -1;}struct dynamicArray * array queue;if (array-m_Size 0){return 1;}return 0;
}//销毁队列
void destroy_SeqQueue(seqQueue queue)
{if (queue NULL){return ;}destroy_dynamicArray(queue);queue NULL;
}源文件test.c :#define _CRT_SECURE_NO_WARNINGS
#includestdio.h
#includestring.h
#includestdlib.h
#include seqQueue.hstruct Person
{char name[64];int age;
};void test01()
{//初始化队列seqQueue myQueue init_SeqQueue();//准备数据struct Person p1 { aaa, 10 };struct Person p2 { bbb, 20 };struct Person p3 { ccc, 30 };struct Person p4 { ddd, 40 };struct Person p5 { eee, 50 };//入队push_SeqQueue(myQueue, p1);push_SeqQueue(myQueue, p2);push_SeqQueue(myQueue, p3);push_SeqQueue(myQueue, p4);push_SeqQueue(myQueue, p5);printf(队列大小为%d\n, size_SeqQueue(myQueue));while (isEmpty_SeqQueue(myQueue) 0) {//队头元素struct Person * pFront front_SeqQueue(myQueue);printf(队头元素姓名%s 年龄%d \n, pFront-name, pFront-age);//队尾元素struct Person * pBack back_SeqQueue(myQueue);printf(队尾元素姓名%s 年龄%d \n, pBack-name, pBack-age);//出队pop_SeqQueue(myQueue);}printf(队列大小为%d\n, size_SeqQueue(myQueue));//销毁队列destroy_SeqQueue(myQueue);myQueue NULL;
}int main(){test01();system(pause);return EXIT_SUCCESS;
}2.4队列的链式存储基本概念队列也是一种特殊的线性表可以用线性表链式存储来模拟队列的链式存储。头文件 linkQueue.h :#pragma once
#define _CRT_SECURE_NO_WARNINGS
#includestdio.h
#includestring.h
#includestdlib.h//节点结构体
struct QueueNode
{struct QueueNode * next;};//链表的结构体 --- 队列
struct LQueue
{struct QueueNode pHeader; //头节点int m_Size; //队列的大小struct QueueNode * pTail; //记录尾节点的指针
};typedef void * LinkQueue;//初始化队列
LinkQueue init_LinkQueue();
//入队
void push_LinkQueue(LinkQueue queue, void * data);
//出队
void pop_LinkQueue(LinkQueue queue);
//返回队头
void * front_LinkQueue(LinkQueue queue);
//返回队尾
void * back_LinkQueue(LinkQueue queue);
//返回队列大小
int size_LinkQueue(LinkQueue queue);
//判断队列是否为空
int isEmpty_LinkQueue(LinkQueue queue);
//销毁队列
void destroy_LinkQueue(LinkQueue queue);源文件 linkQueue.c :#include linkQueue.h//初始化队列
LinkQueue init_LinkQueue()
{struct LQueue * myQueue malloc(sizeof(struct LQueue));if (myQueue NULL){return NULL;}myQueue-m_Size 0;myQueue-pHeader.next NULL;myQueue-pTail myQueue-pHeader; //尾节点开始指向的就是头节点return myQueue;
}
//入队
void push_LinkQueue(LinkQueue queue, void * data)
{//等价于 尾插if (queue NULL){return;}if (data NULL){return;}struct LQueue * myQueue queue;struct QueueNode * myNode data; //更改指针指向myQueue-pTail-next myNode;myNode-next NULL;//更新尾节点myQueue-pTail myNode;//更新队列大小myQueue-m_Size;}
//出队
void pop_LinkQueue(LinkQueue queue)
{//等价于 头删 if (queue NULL){return;}struct LQueue * myQueue queue;if (myQueue-m_Size 0){return;}if (myQueue-m_Size 1){myQueue-pHeader.next NULL;myQueue-pTail myQueue-pHeader; //维护尾节点指针myQueue-m_Size 0;return;}//记录第一个节点struct QueueNode * pFirst myQueue-pHeader.next;myQueue-pHeader.next pFirst-next;//更新队列大小myQueue-m_Size--;}
//返回队头
void * front_LinkQueue(LinkQueue queue)
{if (queue NULL){return NULL;}struct LQueue * myQueue queue;return myQueue-pHeader.next;}
//返回队尾
void * back_LinkQueue(LinkQueue queue)
{if (queue NULL){return NULL;}struct LQueue * myQueue queue;return myQueue-pTail;}
//返回队列大小
int size_LinkQueue(LinkQueue queue)
{if (queue NULL){return -1;}struct LQueue * myQueue queue;return myQueue-m_Size;}
//判断队列是否为空
int isEmpty_LinkQueue(LinkQueue queue)
{if (queue NULL){return -1;}struct LQueue * myQueue queue;if (myQueue-m_Size 0){return 1;}return 0;}
//销毁队列
void destroy_LinkQueue(LinkQueue queue)
{if (queue NULL){return;}free(queue);queue NULL;
}源文件 test.c :#define _CRT_SECURE_NO_WARNINGS
#includestdio.h
#includestring.h
#includestdlib.h
#include linkQueue.hstruct Person
{void * node;char name[64];int age;
};void test01()
{//初始化队列LinkQueue myQueue init_LinkQueue();//准备数据struct Person p1 { NULL, aaa, 10 };struct Person p2 { NULL, bbb, 20 };struct Person p3 { NULL, ccc, 30 };struct Person p4 { NULL, ddd, 40 };struct Person p5 { NULL, eee, 50 };//入队push_LinkQueue(myQueue, p1);push_LinkQueue(myQueue, p2);push_LinkQueue(myQueue, p3);push_LinkQueue(myQueue, p4);push_LinkQueue(myQueue, p5);printf(队列大小为%d\n, size_LinkQueue(myQueue));while (isEmpty_LinkQueue(myQueue) 0){//队头元素struct Person * pFront front_LinkQueue(myQueue);printf(链式存储 队头元素姓名%s 年龄%d \n, pFront-name, pFront-age);//队尾元素struct Person * pBack back_LinkQueue(myQueue);printf(链式存储 队尾元素姓名%s 年龄%d \n, pBack-name, pBack-age);//出队pop_LinkQueue(myQueue);}printf(队列大小为%d\n, size_LinkQueue(myQueue));//销毁队列destroy_LinkQueue(myQueue);myQueue NULL;
}int main(){test01();system(pause);return EXIT_SUCCESS;
}一般线性表详解请参考文章C语言数据结构一—— 数据结构理论、线性表【动态数组、链表企业版单向链表】
