复习数据结构，先用c思想写一个，同时顺便复习下c吧，操作下指针；督促下自己多写多调。

贴图标记自己坐标，先把基础的写一遍把

 

目录

单项链表

头文件dm_03_LinkList.h（链表的基本操作定义）

dm_03_linklistcpp.cpp(链表基本操作实现)

测试程序main()

测试结果：

循环链表：思路基本一样直接贴代码

循环链表头文件CircleLinkList.h：

实现文件CircleLinkList.cpp：

测试文件：

循环链表测试结果

双向链表：

头文件：

双向链表实现文件：

双向链表测试文件：

双向链表测试结果：

栈（用链表封装）：

栈的头文件

栈的实现文件

栈的测试文件

栈的测试结果

栈的两个应用：括号匹配和后缀表达式

                      运行结果：

用链表封装队列：

队列头文件：

队列实现文件：

队列测试文件：

队列测试结果：

---

单项链表

头文件dm_03_LinkList.h（链表的基本操作定义）

#pragma once
#include"iostream"using namespace std;typedef void Linklist;//定义抽象的链表句柄 链表节点 //底层库的函数参数 返回值类型 和上层业务可见具有普适性
typedef struct LinklistNode
{struct LinklistNode*next;
}LinklistNode;Linklist* LinklistCreat();//创建链表
void LinklistDestory(Linklist*list);//销毁
void LinklistClear(Linklist*list);//清空
int LinklistLength(Linklist*list);//返回长度
int LinklistInsert(Linklist*list, LinklistNode*node, int pos);//指定位置插入
LinklistNode* LinklistGet(Linklist*list, int pos);//指定位置读取
LinklistNode*LinklistDelete(Linklist*list, int pos);//指定位置删除

 

dm_03_linklistcpp.cpp(链表基本操作实现)

 

#include"dm_03_LinkList.h"typedef struct Tlinklist//底层链表业务句柄
{LinklistNode head;int length;
}Tlinklist;//创建链表
Linklist* LinklistCreat()
{Tlinklist*list = NULL;list = (Tlinklist*)malloc(sizeof(Tlinklist));if (list == NULL){cout << "malloc(sizeof(Tlinklist))失败" << endl;return NULL;}memset(list, 0, sizeof(list));//为了内存安全 初始化为0list->head.next = NULL;list->length = 0;return list;
}
//销毁链表 节点都是上层分配的内存，底层自己只能析构句柄内存
void LinklistDestory(Linklist*list)
{if (list !=NULL){free(list);list = NULL;}
}
//清空链表
void LinklistClear(Linklist*list)
{if (list == NULL){cout << "list == NULL";}else{Tlinklist *tlist =(Tlinklist *)(list);//强制类型转换为Tlinklist型链表tlist->head.next = NULL;tlist->length = 0;}
}
//求链表长度
int LinklistLength(Linklist*list)
{int ret = -1;if (list == NULL){cout << "list == NULL";return ret;}else{Tlinklist *tlist = (Tlinklist *)(list);ret = tlist->length;return ret;}
}//按照位置插入链表节点
int LinklistInsert(Linklist*list, LinklistNode*node, int pos)
{int ret = 0;if (list == NULL || node == NULL || pos < 0){ret = -1;cout << "LinklistInsert err  list == NULL || node == NULL || pos < 0" << endl;return ret;}Tlinklist *tlist = (Tlinklist*)(list);LinklistNode*pcurr = NULL;pcurr = &(tlist->head);for (int i = 0; i < pos && (pcurr->next != NULL); i++){pcurr = pcurr->next;//带头结点的链表，指针指向指定位置的前一个}node->next = pcurr->next;pcurr->next = node;tlist->length++;return ret;
}
//获取链表指定位置节点
LinklistNode* LinklistGet(Linklist*list, int pos)
{LinklistNode*listnode = NULL;if (list == NULL ||pos < 0){cout << "LinklistInsert err  list == NULL || node == NULL || pos < 0" << endl;return NULL;}Tlinklist *tlist = (Tlinklist*)(list);LinklistNode*pcurr = NULL;pcurr = &(tlist->head);for (int i = 0; i < pos && (pcurr->next != NULL); i++){pcurr = pcurr->next;}return pcurr->next;
}//删除指定位置节点
LinklistNode*LinklistDelete(Linklist*list, int pos)
{LinklistNode*listnode = NULL;if (list == NULL || pos < 0){cout << "LinklistInsert err  list == NULL || node == NULL || pos < 0" << endl;return NULL;}Tlinklist *tlist = (Tlinklist*)(list);LinklistNode*pcurr = NULL;pcurr = &(tlist->head);for (int i = 0; i < pos && (pcurr->next != NULL); i++){pcurr = pcurr->next;}LinklistNode*tmp = pcurr->next;pcurr->next = tmp->next;tlist->length--;return tmp;
}

测试程序main()

#define _CRT_SECURE_NO_WARNINGS //写在头文件前面可以消除warning
//因为在编译的过程中需要提前这个定义才能避开警告，如果写在头文件后面也是不行的
#include"iostream"
#include"dm_03_LinkList.h"
//#pragma warning(disable: 4996)
using namespace std;

//node写在首行可以避免复杂的结构体偏移量问题
struct Teacher {LinklistNode*node;//链表节点写在第一行 业务节点可以强制转换为链表节点int age;//首地址相同则链表节点地址即为业务节点Teacher地址,char name[32];//底层对node操作则可以建立关于Teacher的链表

};//链表节点不能包含任意节点，让任意节点包含链表节点

void main03()
{int ret = 0;//建立Linklist *l = NULL;l = LinklistCreat();if (l == NULL){ret = -1;cout << "func LinklistCreat err" << ret << endl;return;//跳出main()函数}Teacher t1, t2, t3, t4;strcpy(t1.name, "zhangsan33");strcpy(t2.name, "lisi33");strcpy(t3.name, "wangwu33");strcpy(t4.name, "maliu33");t1.age = 20;t2.age = 22;t3.age = 24;t4.age = 26;//插入链表LinklistInsert(l, (LinklistNode*)(&t1), 0);LinklistInsert(l, (LinklistNode*)(&t2), 0);LinklistInsert(l, (LinklistNode*)(&t3), 0);LinklistInsert(l, (LinklistNode*)(&t4), 0);//遍历for (int i = 0; i < LinklistLength(l); i++){Teacher *tmp = (Teacher*)LinklistGet(l, i);//上层应用知道自己传的是Teacher,别人不知道什么类型，if (tmp == NULL){ret = -2;cout << "func LinklistGet err" << ret << endl;return;}cout << tmp->name << tmp->age << endl;}//删除while (LinklistLength(l)>0){Teacher*tmp = NULL;tmp = (Teacher*)LinklistDelete(l, 0);//删0位置 即头if (tmp == NULL){ret = -3;cout << "func LinklistDelete err" << ret << endl;return;}cout << tmp->name << '\t' << tmp->age << endl;}//遍历检验是否已经全部清空for (int i = 0; i < LinklistLength(l); i++){Teacher *tmp = (Teacher*)LinklistGet(l, i);//上层应用知道自己传的是Teacher,别人不知道什么类型，if (tmp == NULL){ret = -2;cout << "func LinklistGet err" << ret << endl;return;}cout << tmp->name << tmp->age << endl;}system("pause");
}

 

测试结果：

循环链表：思路基本一样直接贴代码

循环链表头文件CircleLinkList.h：

#pragma once
#include"iostream"using namespace std;typedef void CircleLinklist;
typedef struct CircleLinklistNode
{struct CircleLinklistNode*next;
}CircleLinklistNode;CircleLinklist* CircleLinklistCreat();
void CircleLinklistDestory(CircleLinklist*clist);
void CircleLinklistClear(CircleLinklist*clist);
int CircleLinklistLength(CircleLinklist*clist);
int CircleLinklistInsert(CircleLinklist*clist, CircleLinklistNode*node, int pos);
CircleLinklistNode* CircleLinklistGet(CircleLinklist*clist, int pos);
CircleLinklistNode*CircleLinklistDelete(CircleLinklist*clist, int pos);
//add
//重置游标 游标放在第0个节点
CircleLinklistNode* CircleLinklist_Reset(CircleLinklist* clist);
//取当前游标的值
CircleLinklistNode* CircleLinklist_Current(CircleLinklist* clist);
//取当前值，将游标移动指向到链表中的下一个数据元素
CircleLinklistNode* CircleLinklist_Next(CircleLinklist* clist);//直接指定删除链表中的某个数据元素
CircleLinklistNode* CircleLinklist_DeleteNode(CircleLinklist* clist, CircleLinklistNode* node);

实现文件CircleLinkList.cpp：

#include"dm_04_CircleLinkList.h"/*typedef void CircleLinklist;
typedef struct CircleLinklistNode
{struct CircleLinklistNode*next;
}CircleLinklistNode;
*/
//底层链表具体实现
typedef struct TCircleLinklist
{CircleLinklistNode head;CircleLinklistNode*silder;int len;
}TCircleLinklist;CircleLinklist* CircleLinklistCreat()
{TCircleLinklist *clist = (TCircleLinklist*)malloc(sizeof(TCircleLinklist));if (clist == NULL){cout << "CircleLinklistCreat err malloc失败 " << endl;return NULL;}clist->head.next = NULL;clist->silder = NULL;clist->len = 0;return clist;
}
void CircleLinklistDestory(CircleLinklist*clist)
{if (clist != NULL){free(clist);clist = NULL;}
}void CircleLinklistClear(CircleLinklist*clist)
{if ( clist == NULL){cout << "clist == NULL CircleLinklistClear err" << endl;return;}TCircleLinklist *tclist = (TCircleLinklist*)(clist);tclist->len = 0;tclist->head.next = NULL;tclist->silder = NULL;
}int CircleLinklistLength(CircleLinklist*clist)
{if (clist == NULL){cout << "clist == NULL CircleLinklistClear err" << endl;return -1;}TCircleLinklist *tclist = (TCircleLinklist*)(clist);return tclist->len;
}int CircleLinklistInsert(CircleLinklist*clist, CircleLinklistNode*node, int pos)
{int ret = 0;if (clist == NULL || node == NULL || pos < 0){ret = -1;cout << "CircleLinklistInsert err clist == NULL || node == NULL || pos < 0" << endl;return ret;}TCircleLinklist *tclist = (TCircleLinklist*)(clist);CircleLinklistNode*pcurr = NULL;pcurr = &(tclist->head);for (int i = 0; i < pos; i++){pcurr = pcurr->next;//带头结点的链表，指针指向指定位置的前一个}//一般插入法node->next = pcurr->next;pcurr->next = node;//如果是第一次插入if (tclist->len == 0){node->next = node;}//若果是头插法（尾插法同一般插入一样）if (pcurr == (CircleLinklistNode*)clist)//pcurr没有动{//获取最后一个元素CircleLinklistNode *last = CircleLinklistGet(clist, CircleLinklistLength(clist));last->next = pcurr->next;}tclist->len++;return ret;
}CircleLinklistNode* CircleLinklistGet(CircleLinklist*clist, int pos)
{CircleLinklistNode* ret = NULL;if (clist == NULL|| pos < 0){cout << "CircleLinklistInsert err clist == NUL|| pos < 0" << endl;return ret;}TCircleLinklist *tclist = (TCircleLinklist*)(clist);CircleLinklistNode*pcurr = NULL;pcurr = &(tclist->head);for (int i = 0; i < pos ; i++){pcurr = pcurr->next;//带头结点的链表，指针指向指定位置的前一个}ret = pcurr->next;return ret;
}CircleLinklistNode*CircleLinklistDelete(CircleLinklist*clist, int pos)//底层库不关心上层业务的节点存储类型（堆栈）需要把删除后的节点返回
{CircleLinklistNode* ret = NULL;if (clist == NULL || pos < 0){cout << "CircleLinklistInsert err clist == NULL|| pos < 0" << endl;return ret;}TCircleLinklist *tclist = (TCircleLinklist*)(clist);CircleLinklistNode*pcurr = NULL;pcurr = &(tclist->head);for (int i = 0; i < pos; i++){pcurr = pcurr->next;//带头结点的链表，指针指向指定位置的前一个}ret = pcurr->next;//1 缓存删除的节点CircleLinklistNode*tmp = pcurr->next;//2 删除当前节点 长度-1pcurr->next = tmp->next;tclist->len--;//若删除的是游标 游标后移一位if (ret == tclist->silder){tclist->silder = ret->next;}//如果删除的是头结点if (pcurr == (CircleLinklistNode*)clist)//pcurr没有动{//获取最后一个元素CircleLinklistNode *last = CircleLinklistGet(clist, CircleLinklistLength(clist));last->next = pcurr->next;}//若删除后长度为0if (tclist->len == 0){tclist->head.next = NULL;tclist->silder = NULL;}return ret;
}
//add
//重置游标 游标放在第0个节点
CircleLinklistNode* CircleLinklist_Reset(CircleLinklist* clist)
{if (clist == NULL ){cout << "CircleLinklistInsert err clist == NULL" << endl;return NULL;}TCircleLinklist *tclist = (TCircleLinklist *)clist;CircleLinklistNode *tmp = tclist->silder;tclist->silder = tclist->head.next;return tmp;
}//取当前游标的值
CircleLinklistNode* CircleLinklist_Current(CircleLinklist* clist)
{if (clist == NULL){cout << "CircleLinklistInsert err clist == NULL" << endl;return NULL;}TCircleLinklist *tclist = (TCircleLinklist *)clist;CircleLinklistNode *tmp = tclist->silder;return tmp;
}
//取当前值，将游标移动指向到链表中的下一个数据元素
CircleLinklistNode* CircleLinklist_Next(CircleLinklist* clist)
{if (clist == NULL){cout << "CircleLinklistInsert err clist == NULL" << endl;return NULL;}TCircleLinklist *tclist = (TCircleLinklist *)clist;CircleLinklistNode *tmp = tclist->silder;tclist->silder = tclist->silder->next;return tmp;
}//直接指定删除链表中的某个数据元素CircleLinklistNode* CircleLinklist_DeleteNode(CircleLinklist* clist, CircleLinklistNode* node)
{if (clist == NULL|| node == NULL){cout << "CircleLinklistInsert err clist == NULL|| node == NULL" << endl;return NULL;}TCircleLinklist *tclist = (TCircleLinklist *)clist;CircleLinklistNode *pcurr = &(tclist->head);CircleLinklistNode *ret = NULL;int i = 0;for(i = 0;i<tclist->len;i++){if (pcurr->next == node){ret = pcurr->next;break;}pcurr = pcurr->next;}CircleLinklistDelete(clist, i);return ret;
}

测试文件：

#define _CRT_SECURE_NO_WARNINGS //写在头文件前面可以消除warning
//因为在编译的过程中需要提前这个定义才能避开警告，如果写在头文件后面也是不行的
#include"iostream"
#include"dm_04_CircleLinkList.h"
using namespace std;struct Teacher_04 {CircleLinklistNode*node;//因为第一个CircleLinklistNode*node的地址和结构体重合 所以可以强制转换为CircleLinklistNode*类型int age;char name[32];
};void main()
{int ret = 0;//建立CircleLinklist *l = NULL;l = CircleLinklistCreat();if (l == NULL){ret = -1;cout << "func LinklistCreat err" << ret << endl;return;//跳出main()函数}Teacher_04 t1, t2, t3, t4;strcpy(t1.name, "zhangsan44");strcpy(t2.name, "lisi44");strcpy(t3.name, "wangwu44");strcpy(t4.name, "maliu44");t1.age = 20;t2.age = 22;t3.age = 24;t4.age = 26;//插入链表 尾插法 和 头插法CircleLinklistInsert(l, (CircleLinklistNode*)(&t1), CircleLinklistLength(l));CircleLinklistInsert(l, (CircleLinklistNode*)(&t2), CircleLinklistLength(l));CircleLinklistInsert(l, (CircleLinklistNode*)(&t3), CircleLinklistLength(l));CircleLinklistInsert(l, (CircleLinklistNode*)(&t4),0);//遍历for (int i = 0; i < CircleLinklistLength(l); i++){Teacher_04 *tmp = (Teacher_04*)CircleLinklistGet(l, i);//上层应用知道自己传的是Teacher,别人不知道什么类型，if (tmp == NULL){ret = -2;cout << "func CircleLinklistGet err" << ret << endl;return;}cout << tmp->name<<"    " << tmp->age << endl;}//删除（按照内容删除）CircleLinklist_DeleteNode(l, (CircleLinklistNode*)(&t3));//遍历检验是否删除for (int i = 0; i < CircleLinklistLength(l); i++){Teacher_04 *tmp = (Teacher_04*)CircleLinklistGet(l, i);//上层应用知道自己传的是Teacher,别人不知道什么类型，if (tmp == NULL){ret = -2;cout << "func CircleLinklistGet err" << ret << endl;return;}cout << tmp->name << "    " << tmp->age << endl;}//删除（按照位置）while (CircleLinklistLength(l)>0){Teacher_04*tmp = NULL;tmp = (Teacher_04*)CircleLinklistDelete(l, 0);//删0位置 即头if (tmp == NULL){ret = -3;cout << "func CircleLinklistDelete err" << ret << endl;return;}cout << tmp->name << "    " << tmp->age << endl;}//遍历检验是否已经全部清空for (int i = 0; i < CircleLinklistLength(l); i++){Teacher_04 *tmp = (Teacher_04*)CircleLinklistGet(l, i);//上层应用知道自己传的是Teacher,别人不知道什么类型，if (tmp == NULL){ret = -2;cout << "func CircleLinklistGet err" << ret << endl;return;}cout << tmp->name << "    " << tmp->age << endl;}return 0;
}

循环链表测试结果

双向链表：

头文件：

#pragma once
#include"iostream"using namespace std;typedef void DoubleList;
typedef struct DoublelistNode
{struct DoublelistNode*pre;struct DoublelistNode*next;
}DoublelistNode;DoubleList* DoubleListCreat();
void DoubleListDestory(DoubleList*dlist);
void DoubleListClear(DoubleList*dlist);
int DoubleListLength(DoubleList*dlist);
int DoubleListInsert(DoubleList*dlist, DoublelistNode*node, int pos);
DoublelistNode* DoubleListGet(DoubleList*dlist, int pos);
DoublelistNode*DoubleListDelete(DoubleList*dlist, int pos);//add
//重置游标 游标放在第0个节点
DoublelistNode* DoubleList_Reset(DoubleList* dlist);
//取当前游标的值
DoublelistNode* DoubleList_Current(DoubleList* dlist);
//取当前值，将游标移动指向到链表中的下一个数据元素
DoublelistNode* DoubleList_Next(DoubleList* dlist);
//取当前值，将游标移动指向到链表中的上一个数据元素
DoublelistNode* DoubleList_Pre(DoubleList* dlist);

双向链表实现文件：

#include"iostream"
#include"dm_05_doubleList.h"
typedef void DoubleList;
struct Teacher_05 {DoublelistNode*node;//因为第一个CircleLinklistNode*node的地址和结构体重合 所以可以强制转换为CircleLinklistNode*类型int age;char name[32];
};typedef struct doublelist
{DoublelistNode head;DoublelistNode *silder;int len;
}doublelist;DoubleList* DoubleListCreat()
{doublelist *tdlist = NULL;tdlist = (doublelist*)malloc(sizeof(doublelist));if (tdlist == NULL){cout << "DoubleListCreat (doublelist*)malloc(sizeof(doublelist));" << endl;return NULL;}tdlist->head.next = NULL;tdlist->head.pre = NULL;tdlist->silder = NULL;tdlist->len = 0;return tdlist;
}
void DoubleListDestory(DoubleList*dlist)
{doublelist *tdlist = (doublelist*)(dlist);if (tdlist == NULL){cout << "DoubleListDestory  err tdlist == NULL" << endl;}else{free(tdlist);tdlist = NULL;}
}void DoubleListClear(DoubleList*dlist)
{doublelist *tdlist = (doublelist*)(dlist);if (tdlist == NULL){cout << "DoubleListClear  err tdlist == NULL" << endl;}else{tdlist->head.next = NULL;tdlist->head.pre = NULL;tdlist->len = 0;tdlist->silder = NULL;}
}int DoubleListLength(DoubleList*dlist)
{doublelist *tdlist = (doublelist*)(dlist);if (tdlist == NULL){cout << "DoubleListLength  err tdlist == NULL" << endl;return -1;}return tdlist->len;
}int DoubleListInsert(DoubleList*dlist, DoublelistNode*node, int pos)
{int ret = 0;doublelist *tdlist = (doublelist*)(dlist);if (tdlist == NULL||node==NULL||pos<0){ret = -1;cout << "DoubleListInsert  errtdlist == NULL||node==NULL||pos<0" << endl;return ret;}//DoublelistNode *pcurr = &(tdlist->head);DoublelistNode *pcurr = (DoublelistNode *)tdlist;DoublelistNode *pnext = NULL;Teacher_05*spy = (Teacher_05 *)node;for (int i = 0; i < pos; i++){pcurr = pcurr->next;}pnext = pcurr->next;//步骤12pcurr->next = node;node->next = pnext;//步骤34 当链表插入第一个元素需要特殊处理if (pnext != NULL)//若为NULL则没有前驱 即末尾位置或插入第一个元素时{pnext->pre = node;}node->pre = pcurr;//插入第一个元素 处理游标if (tdlist->len == 0){tdlist->silder = node;}//在0号位置插入需要特殊处理第一个节点前驱if (pcurr == (DoublelistNode *)tdlist){node->pre = NULL;}tdlist->len++;return ret;
}DoublelistNode* DoubleListGet(DoubleList*dlist, int pos)
{DoublelistNode* ret = NULL;doublelist *tdlist = (doublelist*)(dlist);if (tdlist == NULL || pos<0){cout << "DoubleListGet  errtdlist == NULL||pos<0" << endl;return ret;}DoublelistNode *pcurr = &(tdlist->head);for (int i = 0; i < pos; i++){pcurr = pcurr->next;}ret = pcurr->next;Teacher_05*t = (Teacher_05*)ret;return ret;
}DoublelistNode*DoubleListDelete(DoubleList*dlist, int pos)
{DoublelistNode* ret = NULL;doublelist *tdlist = (doublelist*)(dlist);if (tdlist == NULL || pos<0){cout << "DoubleListGet  errtdlist == NULL||pos<0" << endl;return ret;}DoublelistNode *pcurr = &(tdlist->head);for (int i = 0; i < pos; i++){pcurr = pcurr->next;}ret = pcurr->next;pcurr->next = ret->next;ret->pre = pcurr;tdlist->len--;return ret;
}//add
//重置游标 游标放在第0个节点
DoublelistNode* DoubleList_Reset(DoubleList* dlist)
{DoublelistNode* ret = NULL;doublelist *tdlist = (doublelist*)(dlist);if (tdlist == NULL){cout << "DoubleList_Reset  err (tdlist == NULL)" << endl;return ret;}tdlist->silder =tdlist->head.next;ret = tdlist->silder;return ret;
}
//取当前游标的值
DoublelistNode* DoubleList_Current(DoubleList* dlist)
{DoublelistNode* ret = NULL;doublelist *tdlist = (doublelist*)(dlist);if (tdlist == NULL){cout << "DoubleList_Reset  err (tdlist == NULL)" << endl;return ret;}ret = tdlist->silder;return ret;
}//取当前值，将游标移动指向到链表中的下一个数据元素
DoublelistNode* DoubleList_Next(DoubleList* dlist)
{DoublelistNode* ret = NULL;doublelist *tdlist = (doublelist*)(dlist);if (tdlist == NULL){cout << "DoubleList_Reset  err (tdlist == NULL)" << endl;return ret;}ret = tdlist->silder;tdlist->silder = tdlist->silder->next;return ret;
}//取当前值，将游标移动指向到链表中的上一个数据元素
DoublelistNode* DoubleList_Pre(DoubleList* dlist)
{DoublelistNode* ret = NULL;doublelist *tdlist = (doublelist*)(dlist);if (tdlist == NULL){cout << "DoubleList_Reset  err (tdlist == NULL)" << endl;return ret;}ret = tdlist->silder;tdlist->silder = tdlist->silder->pre;return ret;
}

双向链表测试文件：

#define _CRT_SECURE_NO_WARNINGS //写在头文件前面可以消除warning
//因为在编译的过程中需要提前这个定义才能避开警告，如果写在头文件后面也是不行的
#include"iostream"
#include"dm_05_doubleList.h"
using namespace std;struct Teacher_05 {DoublelistNode*node;//因为第一个CircleLinklistNode*node的地址和结构体重合 所以可以强制转换为CircleLinklistNode*类型int age;char name[32];
};void main()
{int ret = 0;//建立DoubleList *l = NULL;l = DoubleListCreat();if (l == NULL){ret = -1;cout << "func LinklistCreat err" << ret << endl;return;//跳出main()函数}Teacher_05 t1, t2, t3, t4;strcpy(t1.name, "zhangsan55");strcpy(t2.name, "lisi55");strcpy(t3.name, "wangwu55");strcpy(t4.name, "maliu55");t1.age = 20;t2.age = 22;t3.age = 24;t4.age = 26;//插入链表 尾插法 和 头插法DoubleListInsert(l, (DoublelistNode*)(&t2), DoubleListLength(l));DoubleListInsert(l, (DoublelistNode*)(&t3), DoubleListLength(l));DoubleListInsert(l, (DoublelistNode*)(&t4), 0);//遍历for (int i = 0; i < DoubleListLength(l); i++){Teacher_05 *tmp = (Teacher_05*)DoubleListGet(l, i);//上层应用知道自己传的是Teacher,别人不知道什么类型，if (tmp == NULL){ret = -2;cout << "func DoubleListLength err" << ret << endl;return;}cout << tmp->name << "    " << tmp->age << endl;}//用游标遍历cout << "用游标遍历" << endl;Teacher_05 *tmpsilder = NULL;tmpsilder =(Teacher_05 *)DoubleList_Reset(l);for (int i = 0; i < DoubleListLength(l); i++){tmpsilder = (Teacher_05 *)DoubleList_Next((DoubleList*)l);cout << tmpsilder->name << " " << tmpsilder->age << endl;}//删除（按照位置）cout << "删除掉的元素" << endl;while (DoubleListLength(l)>0){Teacher_05*tmp = NULL;tmp = (Teacher_05*)DoubleListDelete(l, 0);//删0位置 即头if (tmp == NULL){ret = -3;cout << "func DoubleListDelete err" << ret << endl;return;}cout << tmp->name << "    " << tmp->age << endl;}//遍历检验是否已经全部清空cout << "遍历检验是否完全清空" << endl;int flag = 0;for (int i = 0; i < DoubleListLength(l); i++){Teacher_05 *tmp = (Teacher_05*)DoubleListGet(l, i);//上层应用知道自己传的是Teacher,别人不知道什么类型，if (tmp == NULL){ret = -2;cout << "func DoubleListGet err" << ret << endl;return;}cout << tmp->name << "    " << tmp->age << endl;flag++;}if (flag == 0){cout << "已经完全清空" << endl;}system("pause");
}

双向链表测试结果：

栈（用链表封装）：

栈的头文件

#pragma once
#ifndef _MY_LINKSTACK_H_
#define _MY_LINKSTACK_H_typedef void LinkStack;LinkStack* LinkStack_Create();void LinkStack_Destroy(LinkStack* stack);void LinkStack_Clear(LinkStack* stack);int LinkStack_Push(LinkStack* stack, void* item);void* LinkStack_Pop(LinkStack* stack);void* LinkStack_Top(LinkStack* stack);int LinkStack_Size(LinkStack* stack);#endif //_MY_LINKSTACK_H_

栈的实现文件

#include"dm_07_LinkStack.h"
#include"iostream"
#include"dm_03_LinkList.h"using namespace std;//实际用的是链表实现的栈所以底层用链表的业务节点
//用链表的业务节点包含栈的业务节点，操作栈的业务节点即可
struct ListSNode
{LinklistNode node;void*item;//栈的业务节点
};//创建栈相当于创建一个线性表
LinkStack* LinkStack_Create()
{return LinklistCreat();
}void LinkStack_Destroy(LinkStack* stack)
{LinklistDestory((Linklist*)stack);
}
//清空栈相当于清空一个线性表 涉及到元素生命周期的管理
//需要把栈中底层链表分配的空间释放掉弹出即可
void LinkStack_Clear(LinkStack* stack)
{if (stack == NULL){return;}while (LinkStack_Size(stack) > 0){LinkStack_Pop(stack);//弹栈时释放底层分配的链表节点空间}
}
//压栈 相当于线性表的插入 从头结点插入从头结点弹出不需要遍历更简单
//把栈的业务节点转换为链表的业务节点 然后在通过头插法插入链表
int LinkStack_Push(LinkStack* stack, void* item)
{ListSNode * tmp = NULL;int ret = 0;tmp = (ListSNode*)malloc(sizeof(ListSNode));//希望将tmp插入后保存，函数结束后不会消失，堆区开辟空间if (tmp == NULL){ret = -1;cout << "LinkStack_Push err tmp == NULL" << endl;return ret;}memset(tmp, 0, sizeof(tmp));tmp->item = item;int tag = LinklistInsert((Linklist*)stack, (LinklistNode*)tmp, 0);if (tag != 0){ret = -2;cout << "LinkStack_Push err LinklistInsert err" << endl;if (tmp != NULL){free(tmp);//插入失败 释放内存}return ret;}return ret;
}
//从栈中弹出元素 相当于从线性表中头结点开始删除一个元素
//返回栈节点 需要将链表节点转换为栈节点
void* LinkStack_Pop(LinkStack* stack)
{void*ret = NULL;void *item = NULL;//业务节点ListSNode * tmp = NULL;tmp = (ListSNode *)LinklistDelete((Linklist*)stack, 0);if (tmp == NULL){cout << "LinkStack_Pop err" << endl;return ret;}item = tmp->item;free(tmp);//释放插入时 底层自己分配的链表节点空间ret = item;return ret;
}void* LinkStack_Top(LinkStack* stack)
{void*ret = NULL;ListSNode * tmp = NULL;tmp = (ListSNode *)LinklistGet((Linklist*)stack, 0);if (tmp == NULL){cout << "LinkStack_Top err" << endl;return ret;}return tmp->item;
}
//相当于求线性表的长度
int LinkStack_Size(LinkStack* stack)
{return LinklistLength((Linklist*)stack);
}

栈的测试文件

#include"dm_07_LinkStack.h"
#include"iostream"using namespace std;struct Teacher_07 {int age;char name[32];
};void main()
{LinkStack*stack;Teacher_07 t1, t2, t3, t4;strcpy(t1.name, "zhangsan66");strcpy(t2.name, "lisi66");strcpy(t3.name, "wangwu66");strcpy(t4.name, "maliu66");t1.age = 20;t2.age = 22;t3.age = 24;t4.age = 26;stack = LinkStack_Create();LinkStack_Push(stack, (void*)(&t1));LinkStack_Push(stack, (void*)(&t2));LinkStack_Push(stack, (void*)(&t3));LinkStack_Push(stack, (void*)(&t4));cout << "stack_size" << LinkStack_Size(stack) << endl;Teacher_07 * tmp = (Teacher_07 *)LinkStack_Top(stack);cout << "stackTop" << tmp->name << " " << tmp->age << endl;//弹栈 遍历int len = LinkStack_Size(stack);for (int i = 0; i<len; i++){tmp = (Teacher_07 *)LinkStack_Pop(stack);cout << tmp->name << " " << tmp->age << endl;}system("pause");
}

栈的测试结果

栈的两个应用：括号匹配和后缀表达式

#include"dm_07_LinkStack.h"
#include"iostream"using namespace std;int isleft(char c)
{int ret = 0;switch (c){case'<':case'(':case'{':case'\"':case'\'':case'[':ret = 1;break;default:ret = 0;break;}return ret;
}int isnum(char c)
{int ret = 0;switch (c){case'0':case'1':case'2':case'3':case'4':case'5':case'6':case'7"':case'8':case'9':ret = 1;break;default:ret = 0;break;}return ret;
}int isopera(char c)
{int ret = 0;switch (c){case'+':case'-':case'*':case'/':ret = 1;break;default:ret = 0;break;}return ret;
}int isright(char c)
{int ret = 0;switch (c){case'>':case')':case'}':case'\"':case'\'':case']':ret = 1;break;default:ret = 0;break;}return ret;
}int matchlabel(char left,char right)
{int ret = 0;switch (left){case'<':ret = (right == '>'); break;case'(':ret = (right == ')'); break;case'{':ret = (right == '}'); break;case'\"':ret = (right == '\"'); break;case'\'':ret = (right == '\''); break;case'[':ret = (right == ']'); break;}return ret;
}int scannercode(const char *code)
{LinkStack* stack = LinkStack_Create();int i = 0;while (code[i] != '\0'){if (isleft(code[i])){LinkStack_Push(stack, (void* )(code+i));}if (isright(code[i])){char *tmp = (char*)LinkStack_Pop(stack);if (tmp == NULL || !matchlabel(*tmp, code[i])){cout << *tmp <<"不匹配" << endl;return 0;}}i++;}if (LinkStack_Size(stack) == 0 && code[i] == '\0'){cout << "匹配成功" << endl;return 1;}else{cout << "匹配失败" << endl;return 0;}LinkStack_Destroy(stack);
}
// 算优先级的函数
int priority(char c)
{int pri = 0;switch (c){case '(':pri = 1; break;case'+':case'-':pri = 2; break;case'*':case'/':pri = 3; break;default:pri = 0; break;}return pri;
}
//后缀表达式
void transform(const char*exp,char*deststr)
{LinkStack* stack = LinkStack_Create();int i = 0;while (exp[i] != '\0'){int tag2 = LinkStack_Size(stack);if (isnum(exp[i])){cout << exp[i];}else if (isopera(exp[i])){char *test_c = ((char*)LinkStack_Top(stack));while (priority(exp[i] <= priority(*((char*)LinkStack_Top(stack))))){char *tmp = (char*)LinkStack_Pop(stack);cout << *tmp;}LinkStack_Push(stack, (void*)(exp + i));}else if (isleft(exp[i])){LinkStack_Push(stack, (void*)(exp + i));char c = (*((char*)LinkStack_Top(stack)));//cout << c;}else if (isright(exp[i])){while((*((char*)LinkStack_Top(stack)))!= '('){char *tmp = (char*)LinkStack_Pop(stack);cout << *tmp;}if ((*((char*)LinkStack_Top(stack))) == '('){char *tmp = (char*)LinkStack_Pop(stack);}else{cout << "括号不匹配";return;}}i++;}while ((LinkStack_Size(stack) > 0) && (exp[i] == '\0')){char *tmp = (char*)LinkStack_Pop(stack);cout << *tmp;}
}void main()
{char *str = "void main01(){int a[1000] = { 0 };srand(int(time));]maxNa, (1000);}";char *exp = "(8+(3-1)*5)";char buf[1024] = {0};transform(exp, buf);cout << endl;scannercode(str);system("pause");
}

运行结果：

用链表封装队列：

队列头文件：

#pragma once
#include"dm_03_LinkList.h"
typedef void LinkQueue;LinkQueue* LinkQueue_Create();void LinkQueue_Destroy(LinkQueue* queue);void LinkQueue_Clear(LinkQueue* queue);int LinkQueue_Append(LinkQueue* queue, void* item);void* LinkQueue_Retrieve(LinkQueue* queue);void* LinkQueue_Header(LinkQueue* queue);int LinkQueue_Length(LinkQueue* queue);

队列实现文件：

#include"dm_09_linkqueue.h"
#include"iostream"using namespace std;
//实际用的是链表实现的队列所以底层用链表的业务节点
//用链表的业务节点包含队列的业务节点，底层操作链表节点即可
struct ListSNode
{LinklistNode node;void*item;//栈的业务节点
};//创建一个队列相当于创建一个链表
LinkQueue* LinkQueue_Create()
{return LinklistCreat();
}
//销毁一个队列相当于销毁一个链表
void LinkQueue_Destroy(LinkQueue* queue)
{LinkQueue_Clear(queue);LinklistDestory(queue);
}
//清除一个队列相当于清除一个链表 
void LinkQueue_Clear(LinkQueue* queue)
{if (queue != NULL){while (LinklistLength(queue) >=0){LinkQueue_Retrieve(queue);}}
}int LinkQueue_Append(LinkQueue* queue, void* item)
{int ret = 0;ListSNode*tmp = NULL;tmp = (ListSNode*)malloc(sizeof(ListSNode));tmp->item = item;int tag = 0;ret = LinklistInsert(queue, (LinklistNode*)tmp, LinklistLength(queue));if (tag != 0){ret = -1;cout << "LinkQueue_Append err LinklistInsert err" << endl;if (tmp != NULL){free(tmp);//插入失败 释放内存}return ret;}return ret;
}void* LinkQueue_Retrieve(LinkQueue* queue)
{void*ret = NULL;void *item = NULL;//业务节点ListSNode * tmp = NULL;tmp = (ListSNode *)LinklistDelete((Linklist*)queue, 0);if (tmp == NULL){cout << "LinkQueue_Retrieve err" << endl;return ret;}item = tmp->item;free(tmp);//释放插入时 底层自己分配的链表节点空间ret = item;return ret;
}void* LinkQueue_Header(LinkQueue* queue)
{ListSNode*tmp = NULL;//必须用queue的节点去接，返回具体的业务节点tmp = (ListSNode*)LinklistGet(queue, 0);return tmp->item;//返回具体的业务节点 tmp->item;
}int LinkQueue_Length(LinkQueue* queue)
{return  LinklistLength(queue);
}

队列测试文件：

#include"dm_09_linkqueue.h"
#include"iostream"using namespace std;struct Teacher_09 {int age;char name[32];
};void main09()
{LinkQueue*linkqueue;Teacher_09 t1, t2, t3, t4;strcpy(t1.name, "zhangsan66");strcpy(t2.name, "lisi66");strcpy(t3.name, "wangwu66");strcpy(t4.name, "maliu66");t1.age = 20;t2.age = 22;t3.age = 24;t4.age = 26;linkqueue = LinkQueue_Create();LinkQueue_Append(linkqueue, (void*)(&t1));LinkQueue_Append(linkqueue, (void*)(&t2));LinkQueue_Append(linkqueue, (void*)(&t3));LinkQueue_Append(linkqueue, (void*)(&t4));cout << "linkqueue_size" << LinkQueue_Length(linkqueue) << endl;Teacher_09 * tmp = (Teacher_09 *)LinkQueue_Header(linkqueue);cout << "queueTop" << tmp->name << " " << tmp->age << endl;//弹栈 遍历int len = LinkQueue_Length(linkqueue);for (int i = 0; i<len; i++){tmp = (Teacher_09 *)LinkQueue_Retrieve(linkqueue);cout << tmp->name << " " << tmp->age << endl;}system("pause");
}

队列测试结果：

 

嗯嗯就这样，今天结束，看世界杯了