C语言课堂代码案例 数据结构 持续补充

数据结构 持续补充"/>

C语言课堂代码案例 数据结构 持续补充

数据结构部分，从P21课开始

21.数据结构_哔哩哔哩_bilibili

1.线性关系

1.1.顺序表 -动态数组

文中创建的动态数组可以存放任意类型数据，因为里面有一个2级指针void ** 。指向一个任意类型的数组 的指针。

顺序表的初始化、插入、删除（没写） 销毁 和遍历 

遍历 牵扯到函数指针的使用，也叫做回调函数。

1.1.1 存放数字的顺序表 （代码还没写全）

#include <stdio.h>
#include <stdlib.h>  
#include<string.h> struct List{void **arr;int maxsize;int msize;
};//初始化
struct List * initL(int num){struct List* myseq=(struct List *)malloc(sizeof(struct List));myseq->maxsize=num;myseq->msize=0;myseq->arr=(void **)malloc(sizeof(void *)*num);return myseq;
}//charu插入数据//注意！！ 如果现在容量满了，要求重新开辟内存 
void inserL(struct List *s, int pos,void *data){if(s->maxsize==s->msize){//开辟新空间 void **newspace=(void **)malloc(sizeof(void *)*(s->maxsize+1));//将原动态数组拷贝到新空间memcpy(newspace,s->arr,sizeof(void *)*(s->maxsize)); //释放原来空间free(s->arr);s->arr=NULL;s->arr=newspace; }if((pos<0)||(pos>s->msize)){perror("POS IS NOT VALID\n");return;}for(int i=s->msize;i>pos;i--){s->arr[i]=s->arr[i-1];}s->arr[pos]=data;s->msize++;
}void foreachL(struct List *list,void (*myprint)(void *)){if(list==NULL){return;}if(myprint==NULL){return;}for(int i=0;i<list->msize;i++){myprint(list->arr[i]);}
}void myprintInt(void* dig){int *d=(int *)dig;printf("%d   ",*d);
}void test(){int a1=5;int a2=6;int a3=7;int a4=8;int a5=9;
struct List *  myseq=initL(10);inserL(myseq,0,&a1);inserL(myseq,9,&a2);inserL(myseq,0,&a3);inserL(myseq,2,&a4);inserL(myseq,1,&a5);foreachL(myseq,myprintInt);
}int main(){test();system( "pause");return 0;
} 

1.1.2 存放任意类型的顺序表

老师写的。初学者容易犯的错误——反复释放空指针！！报错哭死 

#include <stdio.h>
#include <stdlib.h>  
#include<string.h> struct SeqList {void** arr;int maxsize;int msize;
};struct Pet {int age;char color[32];char name[32];
};//初始化
struct SeqList* initL(int num) {struct SeqList* myseq = (struct SeqList*)malloc(sizeof(struct SeqList));if (!myseq) {perror("MALLOC FAILS\n");exit(0);}myseq->maxsize = num;myseq->msize = 0;myseq->arr = (void**)malloc(sizeof(void*) * num);//void * =malloc (sizeof (void))就不必了 //因为谁都不知道是什么数据类型所以sizeof不行 return myseq;
}//插入数据 如果现在容量满了，要求重新开辟原来的两倍内存 
void inserL(struct SeqList* s, int pos, void* data) {if ( s->msize== s->maxsize) {//开辟新空间 void** newspace = (void**)malloc(sizeof(void*) * (2 * (s->maxsize)));if (!newspace){perror("MALLOC FAILS\n");exit(0);}//将原动态数组拷贝到新空间memcpy(newspace, s->arr, sizeof(void*) * (s->maxsize));//这句话出警告，void*4 字节 int 8字节？？int 不也是4字节么//释放原来空间free(s->arr);s->arr = NULL;s->arr = newspace;s->maxsize = 2 *( s->maxsize);printf("满了\n");//return;}//强制尾插 if ((pos < 0) || (pos > s->msize)) {printf("POS IS NOT VALID\n");s->arr[s->msize] = data;s->msize++;return;}//找到位置 把i 开始所有数据往后移动一位 //大于等于 不是大于for (int i = s->msize; i > pos; i--) {s->arr[i] = s->arr[i - 1];}s->arr[pos] = data;s->msize++;
}
//遍历打印  函数指针 
void foreachL(struct SeqList* s, void (*myprint)(void*)) {if (s == NULL) {return;}if (myprint == NULL) {return;}for (int i = 0; i < s->msize; i++) {myprint(s->arr[i]);}
}void myprintS(void* pet) {struct Pet* p = (struct Pet*)pet;printf("年龄%d  名字%s   颜色%s  \n ", p->age, p->name, p->color);
}//销毁顺序表
void clearL(struct SeqList* s) {if (!s){printf("顺序表不存在 不用删除\n");return;}//之前写了一个for循环 挨个free(arr[i])//绝对不行！因为指向的已经是宠物结构体了所以反复报错if (s->arr!=NULL){free(s->arr);s->arr = NULL;}s->msize = 0;s->maxsize = 0;free(s);s = NULL;
}//按照位置删除
void delEle(struct SeqList* s, int pos) {if (s == NULL) {return;}if (pos > s->msize) {printf("删除位置不对\n");return;}for (int i = pos; i < s->msize - 1; i++) {s->arr[i] = s->arr[i + 1];}s->msize--;//free(s->arr[s->msize - 1]);//s->arr[s->msize - 1] = NULL;//上边两行代码写了就错，因为现在void *都是Pet结构体的指针，//不能无缘无故把结构体的内容释放掉.
}//按照值删除，代码待补充//查找 按照位置查找太简单不写了
// 
// 自己写的---姓名为dami的宠物 按照值查找 compare函数指针
int  findif(struct SeqList* s, int (*parefun)(void*)) {if (s == NULL) {perror("ARR DOES NOT EXIST");return -1;}for (int i = 0; i < s->msize; i++) {if (parefun(s->arr[i])) {return i;}}return -1;}//自己写的比较函数，，跟老师写的比起来有缺点。
int pet_parefun(struct Pet* p) {if (strcmp(p->name, "dami") == 0) {return 1;}else {return 0;}
}
//模仿老师写的 按照值查找函数和比较函数指针
//有个缺点 只能找到第一个。
int  findif222(struct SeqList* s,void *tar,  int (*parefun222)(void*, void *)) {if (s == NULL) {perror("ARR DOES NOT EXIST");exit(0);}for (int i = 0; i < s->msize; i++) {//如果两个值相等返回0  if (!parefun222(s->arr[i], tar)) {return i;}}return -1;
}
int mypare222(void* data1, void* data2) {struct Pet* p1 = (struct Pet*)data1;struct Pet* p2 = (struct Pet*)data2;if ((p1->age==p2->age)&&(strcmp(p1->name, p2->name)==0 )){return 0;//年龄相等  名字strcmp=0相等 就判断是自己想要的}else {return 1;}
}void test01() {struct Pet p1 = { 10,"yellow", "cream" };struct Pet p2 = { 8,"white", "cc" };struct Pet p3 = { 5,"black", "apple" };struct Pet p4 = { 12,"grey", "rice" };struct Pet p5 = { 3,"white", "miao" };struct SeqList* mylist = initL(5);printf("%d\n ", mylist->maxsize);inserL(mylist, 0, &p1); printf("p1 charu\n ");inserL(mylist, 1, &p2); printf("p2 charu\n ");inserL(mylist, 2, &p3); printf("p3 charu\n ");inserL(mylist, 6, &p4); printf("p4 charu\n ");inserL(mylist, 1, &p5); printf("p5 charu\n ");foreachL(mylist, myprintS);delEle(mylist,3);printf("---------\n");foreachL(mylist,myprintS);printf("---------\n");struct Pet p6 = { 3,"blue", "miao" };int findpos = findif222(mylist, &p6, mypare222);printf("找到了位置再%d\n ", findpos);//找到了位置再1clearL(mylist);//这里可千万别再写free(mylist)了 释放空指针报错了一天！！mylist = NULL;
}
int main() {test01();system("pause");return 0;
}

1.2 链表

1.2.1 单向链表

1.2.1.1 存储整数的单向链表

首先写出每个结点的结构体，有数据域和指针域。接着写出链表结构体，（这是老师课程讲的 但是我看《数据结构》一书中 张青主编，就没有链表结构体，直接用一个节点结构体的 指针代表了链表）

所以这个代码就变得麻烦起来，时时兼顾msize++ 或者-- ，好处是随时返回长度

注意while循环条件！！里面有if 判断跳出循环的， 千万别让if 里面可能有空指针指向！！不然无限循环，后面的代码自动不执行！

这里我跟老师讲的有点区别的地方：老师讲的是，位置不合理强制尾插，我这里按失败返回

//单向链表 
struct ListNode{int num;struct ListNode *next;
};struct Link {struct ListNode header;int msize;
};struct Link *initlink(){struct Link *mylink=(struct Link *)malloc(sizeof(struct Link));if(mylink==NULL){perror("malloc FAIL");//	return;}mylink->header.next=NULL;mylink->header.num=NULL;mylink->msize=0;return mylink;
};//pos必须大于0，从1开始，例如pos==2那么意思就是把第二个节点变成新节点。 
//0算头结点的编号。 
void insert_Linklist(struct Link * head, int pos,int newdata){if(head==NULL){printf("????\n");return;}if(pos<=0){perror("POS IS WRONG\n");return;}//尾插的情况 但是这部分代码不用写！！底下的代码也适用尾插！ 
//	if(((pos==1)&&(head->msize==0))||(head->msize==pos-1)){
//		struct ListNode *pre1=&(head->header);
//		int k1=0;
//		while(pre1&&(k1<pos-1)){
//			pre1=pre1->next;
//			k1++; 
//		}
//	  	struct ListNode *newnode1=(struct ListNode *)malloc(sizeof(struct ListNode));
//	  	newnode1->num=newdata;
//	  	newnode1->next=NULL;
//		pre1->next=newnode1;
//	  	head->msize++;
//	  	return;
//	}//前后都有节点，中间插入，最简单 struct ListNode *pre=&(head->header);int k=0;while(pre&&(k<pos-1)){ pre=pre->next;//找到前驱结点k++; }struct ListNode *newnode=(struct ListNode *)malloc(sizeof(struct ListNode));newnode->num=newdata;newnode->next=pre->next;pre->next=newnode;head->msize++;}void forEachLink(struct Link * head){if(head==NULL){printf("不能遍历，链表不存在\n");return;}if((head->header).next==NULL){printf("不能遍历，链表只有一个头节点，为空链表\n");return;}struct ListNode* pcurrent=(head->header).next;while(pcurrent!=NULL){printf("%d  ",pcurrent->num);pcurrent=pcurrent->next;}printf("\n");//!!!课本上没写msize 也没有Link结构体 弄混了 
}//返回链表长度
int len(struct Link * head) {return head->msize;
}//删除节点  思路一样 先找到前驱 //按照位置删除节点 delpos=3表示删除第3个节点，头结点算第0个
int del_by_pos(struct Link * head,int delpos) {if(head==NULL){printf("链表不存在");return FALSE;}if(head->msize==0){printf("链表只有一个头节点，为空链表");return FALSE;}int k=0;struct ListNode *p=&(head->header);//找到前驱节点 while(p&&(k<delpos-1)){p=p->next;k++;}if((p==NULL)||(p->next==NULL)){perror("没有找到要删除的位置\n");return FALSE;}struct ListNode *pdel=p->next;p->next=p->next->next;free(pdel);pdel=NULL;head->msize--;return true;
}//按照值删除节点  delval=50表示在链表中删除 数据域等于50的节点 
int del_by_val(struct Link * head,int delval) {if(head==NULL){printf("链表不存在");return FALSE;}if((head->header).next==NULL){printf("链表只有一个头节点，为空链表");return FALSE;}struct ListNode *p=&(head->header);//找到前驱节点 p//这里循环判断条件必须写p->next 不然找到最后一个节点，if里面无法判断//因为p0>next 就是NULL了，它指向的Num算空指针了 while(p->next){if((p->next->num)==delval){break;}p=p->next;}if((p==NULL)||(p->next==NULL)){printf("链表里没有存这个值的节点\n");return FALSE;}struct ListNode *pdel=p->next;p->next=p->next->next;free(pdel);pdel=NULL;head->msize--;return true;
}//清空整个链表 
//如果要摧毁 最后free(head) head=NULL ，主函数里再重复一遍。 
void clear(struct Link * head){if((head==NULL)||(head->msize==0)){printf("链表本来就是空的\n");return;}struct ListNode *pcur=(head->header).next;while(pcur){struct ListNode *pnext=pcur->next;free(pcur);pcur=NULL;head->msize--;pcur=pnext;}(head->header).next=NULL;//pcur指向第一个数值 
}//按照位置信息查找链表//按照值查找链表void test03(){struct Link *mylin=initlink();insert_Linklist(mylin,1,13);insert_Linklist(mylin,2,14);insert_Linklist(mylin,3,15);insert_Linklist(mylin,4,16);insert_Linklist(mylin,4,20);insert_Linklist(mylin,4,30);printf("现在链表长度为%d\n ",len(mylin));forEachLink(mylin);//13  14  15  30  20  16del_by_pos(mylin,3); forEachLink(mylin);//13  14  30  20  16del_by_val(mylin,100);//链表里没有存这个值的节点 forEachLink(mylin);//13  14  30  20  16clear(mylin);printf("现在链表长度为%d\n ",len(mylin));forEachLink(mylin);
}int main(){test03();system( "pause");return 0;
} 

1.2.1.2 企业级别的单向链表

用户自己开辟节点，存放自己的姓名，年龄，但是指针由企业维护，（指针指向下一个节点）

于是，企业的节点结构体，里面只有指针域，没有数据域。

struct Node{struct Node *next;
};

用户上传Person结构体，但是 链表却只取前4个字节存到自己的节点里。

待补充。。。

//企业级别
struct Node {struct Node *next;
};
struct comLink {struct Node head;int msize;
};
struct Person {void *addr;char name[64];int age;
};//初始化链表
//老师把函数类型写成了返回void * 试了下都一样 
struct comLink* initLink(){struct comLink* mylink=(struct comLink*)malloc(sizeof(struct comLink));if(!mylink){printf("初始化失败\n");exit(0);}return mylink;}; void test04(){struct Person p1={NULL,"Tom",28 };struct Person p2={NULL,"Zhang",18 };struct Person p3={NULL,"Jenny",35 };struct Person p4={NULL,"Jim",40 };struct Person p5={NULL,"Lily",3 };
}
int main(){test04();system( "pause");return 0;
}  

1.3 受限制线性表

1.3.1 栈

栈是一个线性表，具有前驱后继的关系，但是只能在表尾进行插入删除操作，表尾指的是栈顶。

特点：插入删除操作只能在栈顶进行，先进入的元素只能在栈底呆着。

操作：

        进栈，插入操作。也叫作压栈。

        出栈，删除操作。也叫作弹 退栈。

1.3.1.1 栈的顺序存储 （数组形式）

先辨析两个概念 

指针数组  -语法 -   int *arr[ 3 ]   实际上是 int * ( arr[ 3 ] )，这是一个数组，里面每个成员都是一个指针变量。栈的顺序存储会用到这个语法

	int a=10;int b=20;int c=30;int *p1=&a;int *p2=&b;int*p3=&c;int *arr1[3]={p1,p2,p3};

或者这么写

	int a=10;int b=20;int c=30;int *p1=&a;int *p2=&b;int*p3=&c;
int *arr1[3];
arr1[0]=p1;
arr1[1]=p2;
arr1[2]=p3;

 数组指针 ，一个地址 ，指向数组首元素的地址。

语法  int (*arr ) [3]   

int arr3[3]={20,22,24};int (*arr2)[3];arr2=&arr3;for(int i=0;i<3;i++){printf("%d  ",*(*arr2+i));}
//打印结果  20  22 24

栈的顺序存储

#include <stdio.h>
#include <stdlib.h>  
#include<string.h> 
#define MAX 128struct Person {char name[64];int age;
};struct Mstack{void *arr[MAX];//指针数组 int msize;
};//初始化 
struct Mstack *init(){struct Mstack* myss=(struct Mstack *)malloc(sizeof(struct Mstack));//myss->arr=malloc( sizeof(void *)*MAX);没有这句if(!myss){perror("开辟空间失败\n");exit(0);}memset(myss,0,sizeof(void *)*MAX);myss->msize=0;return myss; 
};//入栈 
void inserS(struct Mstack *s, void *data){if((!s)||(!data)){return;}if(s->msize==MAX){printf("满了\n");return;}s->arr[s->msize]=data;s->msize++;
} //出站
void delS(struct Mstack *s) {if(!s){return;}//空战 返回if(s->msize==0){printf("现在栈里没元素\n");return;} s->arr[s->msize-1]=NULL;s->msize--;
}//返回栈顶元素
void *gettop(struct Mstack *s){if(!s){exit(0);}//空战 返回if(s->msize==0){printf("现在栈里没元素\n");exit(0);} return s->arr[s->msize-1];
} void test05(){struct Person p1={"Tom",28 };struct Person p2={"Zhang",18 };struct Person p3={"Jenny",35 };struct Person p4={"Jim",40 };struct Person p5={"Lily",3 };struct Mstack *myst=init();inserS(myst,&p1);inserS(myst,&p2);inserS(myst,&p3);inserS(myst,&p4);inserS(myst,&p5);delS(myst);struct Person *ptr=(struct Person *)gettop(myst);printf("%d 名字是%s",ptr->age,ptr->name);
}int main(){test05();system( "pause");return 0;
}  

1.3.1.2 栈的链表存储

链表的头节点做栈顶，方便插入和删除（这样就不用从头节点一直遍历）；

//初始化，入栈，出站，，打印长度， 打印栈顶元素，
struct Person {void * addr; //4zijie char name[64];int age;
}; 
// node in the Stack  only 4 bits
struct LSNode{struct LSNode *next;
}; struct LinkStack {struct LSNode head;int msize;
};//init 
struct LinkStack *init(){struct LinkStack *ls=(struct LinkStack *)malloc(sizeof(struct LinkStack));if(!ls){perror("MALLOC FAIL\n");exit(0);}(ls->head).next=NULL;ls->msize=0;return ls;};//入栈，写错了，不用找位置了就直接放头结点后面 
void inserLS(struct LinkStack *pls,void *newdata){if((!pls)||(!newdata)){return;}//int k=0;struct LSNode *cnode=&(pls->head);
//	//找到前驱节点cnode 这些操作都不用了 
//	while((cnode->next)&&(k<pos-1)){
//		cnode=cnode->next;
//		k++;
//	}
//	struct LSNode*  newnode=(struct LSNode*)malloc(sizeof(struct LSNode));
struct LSNode*  newnode=(struct LSNode* )newdata;newnode->next=cnode->next;cnode->next=newnode;pls->msize++;
}//出站
void  popstack(struct LinkStack *pls) {//保存一下要删除的节点，记住后面不要free它//因为存着用户写进的内容struct LSNode *p1=(pls->head).next;pls->head.next=p1->next;p1->next=NULL;pls->msize--;
}//查看栈顶元素  注意 函数里面是节点结构体i指针，
//返回的是void *都是4个字节 
void * gettop(struct LinkStack *pls) {if(!pls){perror("no STACK\n");exit(0);}if(pls->msize==0){perror("no element\n");exit(0);}struct LSNode *topdata=(pls->head.next);return topdata;
}//返回栈中元素个数
int getnum(struct LinkStack *pls) {if(!pls){return -1;}
}
//判断是否为空
int isempty(struct LinkStack *pls) {if(!pls){return -1;}if(pls->msize==0){return 1;}return 0;
}void test06(){struct Person p1={NULL,"Tom",28 };struct Person p2={NULL,"Zhang",18 };struct Person p3={NULL,"Jenny",35 };struct Person p4={NULL,"Jim",40 };struct Person p5={NULL,"Lily",3 };struct LinkStack *myll=init();inserLS(myll,&p1);inserLS(myll,&p2);inserLS(myll,&p3);inserLS(myll,&p4);inserLS(myll,&p5);//看一下栈顶元素然后出站 直到 栈为空while(!isempty(myll)){struct Person *pget=(struct Person *)gettop(myll);printf("姓名%s   年龄 %d",pget->name,pget->age);printf("\n");popstack(myll);} 
}int main(){test06();system( "pause");return 0;
}

1.3.1.3 栈的应用案例1- 左右括号的匹配

绝大多数编译器都有检测括号匹配的功能。  (  ) 这个案例中 使用顺序存储的栈。SeqStack

#include <stdio.h>
#include <stdlib.h>  
#include<string.h> //通用的栈 可以存一切数据类型。这里用于左右括号匹配 
struct Seqstack{void *arr[64];//指针数组 int msize;
};//初始化 struct Seqstack *init(){struct Seqstack* myss=(struct Seqstack *)malloc(sizeof(struct Seqstack));//myss->arr=malloc( sizeof(void *)*MAX);没有这句if(!myss){perror("开辟空间失败\n");exit(0);}memset(myss,0,sizeof(void  *)*64);myss->msize=0;return myss; };//入栈 
void inserS(struct Seqstack *s, void *data){if((!s)||(!data)){return;}if(s->msize==64){printf("满了\n");return;}s->arr[s->msize]=data;s->msize++;
} 
//出站
void delS(struct Seqstack *s) {if(!s){return;}//空战 返回if(s->msize==0){printf("现在栈里没元素\n");return;} s->arr[s->msize-1]=NULL;s->msize--;
}//返回栈顶元素
void *gettop(struct Seqstack *s){if(!s){//	exit(0);}//空战 返回if(s->msize==0){printf("现在栈里没元素\n");//	exit(0);} return s->arr[s->msize-1];
} //判断栈为空
int isempty(struct Seqstack *s){if(!s){printf("栈不存在\n");return -1;}if(s->msize==0){return 1;}return 0;
}//打印第一个多余的右括号的位置
void printErr(const char *s, const char *Msg,char * pos){printf("错误信息%s\n",Msg);printf("%s\n",s);int num=pos-s;for(int i=0;i<num;i++){printf(" ");}printf("^\n"); 
} //清空栈
void clearS(struct Seqstack *s){while(!isempty(s)){delS(s);}
} 
//销毁栈
void destroS(struct Seqstack *s){clearS(s);free(s);s=NULL;
} 
void test05(){struct Seqstack *mys=init();char str[]="1+(2+3)+7-(8+11)+2)-15";char *p=str;while(*p!='\0'){if(*p=='('){//如果是左括号，入栈 inserS(mys,p);}if(*p==')'){if(isempty(mys)){//注意这个函数，可以把p这个位置当参数传进去//这样就不用把代码写这里了 printErr(str,"没有任何符号来匹配右括号\n",p);break;}else{char  *nowtop=(char *)gettop(mys);if(*nowtop=='('){delS(mys);}else {printf("没有找到匹配的左括号\n");break;}}}p++;}if(!isempty(mys)){printf("whilejieshu 有多余的左边括号\n");}destroS(mys);
free(mys);
mys=NULL;		
}int main(){test05();system( "pause");return 0;
}  

1.3.1.4 栈的应用案例2  中缀表达式变成后缀表达式。

对于一个数学表达式，人的思维习惯 5 +3=8 属于中缀表达式，

5，  3   + 属于后缀表达式，更符合计算机读取的“思维”

1.3.2 队列

1.3.2.1 队列的顺序存储

队列可以看作是一个特殊的线性表，只能再队头删除（出队），再队尾插入（入队）。所以用1.1.2里面哪个代码，把它的源代码分文件编写成dymic.h   dymic.c两个文件，然后复制到解决方案queue的文件夹下。项目右键-添加-已有项 -  选中这两个文件。

创建queue.h 和 queue.c 两个文件，把动态数组进行封装 如下

// 老师写的每个函数都要把void * 转化成动态数组指针
// 我图省事，有些函数没强制转化 指针的类型。 运行也一样。 晕
#include "Myqueue.h"//初始化队列Myqueue* initQ(int qcapacity) {struct SeqList* myq = initL(qcapacity);return myq;
}int Qlen( Myqueue* q) {int num = retlen(q);return num;
}//插入数据 weisha 
void insertQ( Myqueue* q, void* data) {int tailpos = Qlen(q);inserL(q, tailpos, data);
}//删除元素，出队，
void delEleQ(Myqueue* q) {delEle(q, 0);
}//特有接口，返回队头
void* getQtop(Myqueue* q) {if (!q) {exit(0);}if (Qlen(q) == 0) {printf("长度为0");exit(0);}struct SeqList* myslist = (struct SeqList*)q;void* topdata = myslist->arr[0];return topdata;
}// 特有，返回队尾
void* getQtail(Myqueue* q) {if (!q) {exit(0);}int m = Qlen(q);if (m == 0) {printf("长度为0");exit(0);}struct SeqList* myslist = (struct SeqList*)q;void* taildata = myslist->arr[m-1];return taildata;
}
//判断队列为空
int isemptyQ(Myqueue* q) {if (!q) {return -1;}struct SeqList* myslist = (struct SeqList*)q;if (myslist->msize == 0) {return 1;}return 0;
}//没有遍历队列这个接口  队列不遍历//销毁队列
void clearQ(Myqueue* q) {if (!q) {printf("队列不存在");exit(0);}struct SeqList* myslist = (struct SeqList*)q;clearL(myslist);
}

在主启动文件里时这样的

#include "Myqueue.h"struct Teacher {int age;char name[32];char subject[32];
};void test111() {struct Teacher t1 = { 32, "Bruce", "biology" };struct Teacher t2 = { 29, "Lily", "math" };struct Teacher t3 = { 25, "Tom", "English" };struct Teacher t4 = { 20, "Jenny", "geography" };struct Teacher t5 = { 18, "Hanmeimei", "anthropathy" };printf("????\n");//注意不是5 初始化长度Myqueue* myque = initQ(10);//事实上这个队列可以1000个长度大小，但是仍然只能队尾插入，队头删除（出队）//插入数据insertQ(myque, &t1);insertQ(myque, &t2);insertQ(myque, &t3);insertQ(myque, &t4);insertQ(myque, &t5);//当队列不为空时，看一下队头和队尾 然后出队 直到为空，删除队列while (isemptyQ(myque)==0){struct Teacher* topteacher = (struct Teacher*)getQtop(myque);struct Teacher* ailteacher = (struct Teacher*)getQtail(myque);printf("队头姓名%s 学科%s 年龄%d\n", topteacher->name, topteacher->subject, topteacher->age);printf("尾巴姓名%s 学科%s 年龄%d\n", ailteacher->name, ailteacher->subject, ailteacher->age);delEleQ(myque);}clearQ(myque);
}
int main() {test111();system("pause");return 0;
}

1.3.2.2。  队列的链式存储

三个文件，queue.h  queue.h   use.c 

queue.c 的文件

#include "LINKQue.h"//初始化队列
LQ initLQ(int qcapacity) {LQ  mylinkq = (LQ)malloc(sizeof(struct LinkQue));if (!mylinkq) {printf("开辟内存失败\n ");return;}mylinkq->maxsize = qcapacity;mylinkq->msize = 0;mylinkq->headN.next = NULL;mylinkq->tailN = &(mylinkq->headN);return mylinkq;
}//返回长度
int LQlength(LQ lq) {if (!lq){return -1;}int num = lq->msize;return num;
}//入队，从尾部插入数据
void enterLQ(LQ lq, void* data) {if (!lq){printf("bucunzai ");return ;}if (lq->msize==lq->maxsize){printf("已经满了");}struct LinkQNode* newnode = data;lq->tailN->next = newnode;newnode->next = NULL;lq->tailN = newnode;lq->msize++;
}//删除元素，出队，从队头
void popLQ(LQ lq) {if (!lq){printf("bucunzai ");return;}if (lq->msize == 1){lq->headN.next = 0;lq->tailN = &(lq->headN);lq->msize = 0;return;}struct LinkQNode* delNode = lq->headN.next;lq->headN.next = delNode->next;lq->msize--;
}//返回队头
void* topLQ(LQ lq) {if (!lq){printf("bucunzai所以队头元素也不存在\n ");return;}return lq->headN.next;
}// 返回队尾
void* tailLQ(LQ lq) {if (!lq){printf("bucunzai所以尾巴元素也不存在\n ");return;}return lq->tailN;
}//判断队列为空
int isemptyLQ(LQ lq) {if (!lq){printf("bucunzai\n ");exit(0);}if (lq->msize==0){return 1;}return 0;
}//销毁队列
void destroLQ(LQ lq) {if (!lq){	return;}else{free(lq);lq = NULL;}
}

主文件 use.c代码

#include "LINKQue.h"struct LTeacher {void* addr;int age;char name[32];char subject[32];
};void test222() {struct LTeacher t1 = { NULL, 32, "Bruce", "biology" };struct LTeacher t2 = { NULL, 29, "Lily", "math" };struct LTeacher t3 = { NULL,  25, "Tom", "English" };struct LTeacher t4 = { NULL,  20, "Jenny", "geography" };struct LTeacher t5 = { NULL, 18, "Hanmeimei", "anthropathy" };//注意不是5 初始化长度LQ mylinkQ = initLQ(10);//事实上这个队列可以1000个长度大小，但是仍然只能队尾插入，队头删除（出队）//插入数据enterLQ(mylinkQ, &t1);enterLQ(mylinkQ, &t2);enterLQ(mylinkQ, &t3);enterLQ(mylinkQ, &t4);enterLQ(mylinkQ, &t5);//当队列不为空时，看一下队头和队尾 然后出队 直到为空，删除队列while (isemptyLQ(mylinkQ) == 0){struct LTeacher* topteacher = (struct LTeacher*)topLQ(mylinkQ);struct LTeacher* ailteacher = (struct LTeacher*)tailLQ(mylinkQ);printf("队头姓名%s 学科%s 年龄%d\n", topteacher->name, topteacher->subject, topteacher->age);printf("尾巴姓名%s 学科%s 年龄%d\n", ailteacher->name, ailteacher->subject, ailteacher->age);popLQ(mylinkQ);printf("\n");}destroLQ(mylinkQ);
}
int main() {test222();system("pause");return 0;
}

2.树和二叉树

树的基本概念

树的表达方式

        图形表示

         广义表

        左孩子右兄弟

二叉树的概念

二叉树的表示

二叉树的遍历

2.1 简单模拟二叉树的遍历 叶子数目

     这里的代码非常简单。。树没有开辟内存在堆上，而是在栈上开辟的。具体更复杂代码去查阅《数据结构》的大学课本吧

#include <stdio.h>
#include<stdlib.h>
#include <string.h>//二叉树 三层， 根A  第二层B C  第三层从左网友 D E F G
//我自己定义的 满二叉树。
struct  Treenode
{char nodechar;struct Treenode* leftn;struct Treenode* rightn;
};//计算叶子数量
void leaf(struct Treenode* root, int* leafnum) {//一开始写了这个 会导致无限循环while (root!=NULL)if (root == NULL) {return;}else {if ((root->leftn == NULL) && (root->rightn == NULL)){(*leafnum)++;}leaf(root->leftn, leafnum);leaf(root->rightn, leafnum);}
}void visit(struct Treenode* node) {printf("bianli NODE  %c\n", node->nodechar);
}//先根遍历
//A B C E C F G
void forchTree1(struct Treenode* root) {struct Treenode* tptr = root;// xian gen  leftChild -RightChildif (tptr ==NULL){return;}else{visit(tptr);forchTree1(tptr->leftn);forchTree1(tptr->rightn);}}//中序遍历  做孩子 根  右孩子
//D B E A F C G
void forchTree2(struct Treenode* root) {struct Treenode* tptr = root;if (tptr == NULL){return;}else{forchTree2(tptr->leftn);visit(tptr);forchTree2(tptr->rightn);}}//后序遍历   左孩子 右孩子 根
void forchTree3(struct Treenode* root) {struct Treenode* tptr = root;if (tptr == NULL){return;}else{forchTree3(tptr->leftn);forchTree3(tptr->rightn);visit(tptr);}}//我自己尝试写叶子数量 犯错原因 每次函数开始前，都重置为0 了！！
int mylef = 0;
//解决办法  弄一个全局变量
int caleaf2(struct Treenode* root) {if (root == NULL){return;}else{if ((root->leftn == NULL) && (root->rightn == NULL)){mylef++;	}caleaf2(root->leftn);caleaf2(root->rightn);}return mylef;
}//每个节点的深度是它的高度最大的子树+1
//自己写的函数
int getDep(struct Treenode* root) {int depth = 0;if (root==NULL){return;}if( (root->leftn==NULL)&&(root->rightn==NULL)){depth = 1;}else{int leftDep = getDep(root->leftn);int rDep = getDep(root->rightn);int ret = leftDep > rDep ? leftDep : rDep;depth = ret + 1;}return depth;
}//老师写的求树高度的，更好
int getDep222(struct Treenode* root) {int depth = 0;if (root == NULL){return 0;}int leftDep = getDep(root->leftn);int rDep = getDep(root->rightn);int ret = leftDep > rDep ? leftDep+1 : rDep+1;return  ret;
}void test() {struct Treenode t1 = { 'A',NULL, NULL };struct Treenode t2 = { 'B', NULL, NULL };struct Treenode t3 = { 'C', NULL, NULL };struct Treenode t4 = { 'D', NULL, NULL };struct Treenode t5 = { 'E', NULL, NULL };struct Treenode t6 = { 'F', NULL, NULL };struct Treenode t7 = { 'G', NULL, NULL };t1.leftn = &t2;t1.rightn = &t3;t2.leftn = &t4;t2.rightn = &t5;t3.leftn = &t6;t3.rightn = &t7;//老师写的函数，计算叶子数量/*int num = 0;leaf(&t1, &num);printf("叶子数量是%d\n", num);*/int myresult = caleaf2(&t1);printf("我自己写的函数，计算得到叶子数量是%d\n", myresult);//三种方式遍历//forchTree1(&t1);//forchTree2(&t1);//forchTree3(&t1);//求树的高度int mydep = getDep(&t1);printf("我自己写的函数，计算得到树的高度是%d\n", mydep);
}int main()
{test();system("pause");return 0;
}

拷贝二叉树的代码就没写，因为老师把新节点开辟在堆上。。老树在栈上，新树在堆上。

2.2。二叉树的非递归遍历

// root进栈 （树节点多设置一项属性flag并且均等于0）
// 栈非空  循环开始//出栈  如果栈顶元素为真 直接输出 //如果为假  flag改为1  把右孩子 左孩子 本身压入占中
//栈为空 循环结束
void recursion(struct Treenode* root) {//初始化栈struct Mstack* trstack = init();inserS(trstack, root);while (isempty(trstack)!=1){struct  Treenode* nowtop = (struct  Treenode*)gettop(trstack);delS(trstack);if (nowtop->flag==1){visit(nowtop);//break;}if (nowtop->flag==0){nowtop->flag = 1;if (nowtop->rightn!=NULL){inserS(trstack, nowtop->rightn);}if (nowtop->rightn != NULL){inserS(trstack, nowtop->leftn);}inserS(trstack, nowtop);}}}