|
? 线性表
————————————————————————
?li2.1两个线性表的整合
void union(List &La,List Lb){
//先求出两表的长度
?? ?La_len=ListLength(La);
?? ?Lb_len=ListLength(Lb);
?? ?for(int i=1;i<=Lb_len;i++){
?? ??? ?GetElem(Lb,i,e);
?? ??? ?if(!LocalElem(La,e,equal)){//Lb中的元素没有和La中的相等
?? ??? ??? ?ListInsert(La,++La_len,e);?? ??? ?
?? ??? ?}
?? ?}
}//union
li2.2归并算法
//前提是两个线性表都是非递减排列
void MergeList(List La,List Lb,List &Lc){
?? ?InitList(Lc);
?? ?int i=1,j=1,k=0;
?? ?La_len=ListLength(La);
?? ?Lb_len=ListLength(Lb);
?? ?while((i<=La_len)&&(j<=Lb_len)){
?? ??? ?GetElem(La,i,ai);
?? ??? ?GetElem(Lb,j,bj);
?? ??? ?if(ai<=bj){
?? ??? ? ? ? ListInsert(Lc,++k,ai);
?? ??? ? ? ? ?i++;?? ?
?? ??? ?}else{
?? ??? ? ? ? ?ListInsert(Lc,++k,bj);
?? ??? ? ? ? ?j++;
?? ??? ?}
?? ?}
?? ?while(i<=La_len){
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?GetElem(La,i++,ai);
?? ??? ?ListInsert(Lc,++k,ai);
?? ?}
?? ?while(j<=Lb_len){
?? ??? ?GetElem(Lb,j++,bj);
?? ??? ?ListInsert(Lc,++k,bj);
?? ?}?? ?
}//MergeList
//动态数组
#define LIST_INIT_SIZE 100
#difine INITINCREMENT 10
typedef struct{
?? ?ElemType *elem;
?? ?int length;
?? ?int listsize;
}Sqlist
Status InitList_Sq(Sqlist &L){
?? ?L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
?? ?if(!L.elem)
?? ? ? ? exit(OVERFLOW);//数据溢出
?? ?L.length=0;
?? ?L.listsize=LIST_INIT_SIZE;
?? ?return OK;
}//InistList_Sq
?li2.3线性表的元素插入
Status ListInsert_Sq(SqList &L,int i,ElemType e){
?? ?if(i<1||i>L.length+1)
?? ??? ?return ERROR;
?? ?if(L.length>=L.Listsize){
?? ??? ?newbases=(ElemType *)realloc(L.elem,(L.Listsize+INCREMENT)*sizeof(ElemType));
?? ??? ?if(!newbases)
?? ??? ? ? ? ? exit(OVERFLOW);
?? ??? ?L.elem=newbases;
?? ??? ?L.listsize+=LISTINITCERMENT;
?? ?}
?? ?q=&(L.elem[i-1]);
?? ?for(p=&(L.elem[L.length-1]);p>=q;p--){
?? ? ? ? ?*(p+1)=*p;?? ?
?? ?}
?? ?*q=e;
?? ?++L.length;
? ? ??? ?return OK;
}?
li2.4线性表的元素删除
Status ListDelete_Sq(SqList &L,int i,ElemType &e){
?? ?if(i<1||i>L.length)
?? ??? ?return ERROR;
? ?? ?p=&(L.elem[i-1]);
?? ?e=*p;
?? ?q=&(L.elem[L.length-1])
?? ?for(++p;p<=q;++p){
?? ??? ?*(p-1)=*p;
?? ?}
?? ?--L.length;
?? ?return OK;
}//ListDelete_Sq
li2.5定位元素位置
status LocalElem_Sq(Sqlist L,int i,Status(*compare)(ElemType，ElemType)){
?? ?i=1;
?? ?p=L.elem;
?? ?while(i<=L.length&&!(*compare)(*p++,e))
?? ??? ?++i;
?? ?if(i<=L.length){//查找成功
? ? ? ? ? ? ? ? ? ? ? ?return i;
?? ?}else//查找失败
?? ? ? ? ?return 0;
}//LocalElem_Sq
li2.6归并算法（指针版）
void MergeList(Sqlist La,Sqlist Lb,Sqlist &Lc){
?? ?pa=La.elem;
?? ?pb=Lb.elem;
?? ?Lc.listsize=Lc.length=La.length+Lb.length;
?? ?pc=Lc.elem=(ElemType *)malloc(Lc.listsize*sizeof(Elemtype));
?? ?if(!Lc.elem)
?? ? ? ? exit(OVERFLOW);
?? ?pa_last=La.elem+La.length-1;//这里pa_last指的是尾指针，相当于&（La.elme[La.length-1]）
? ? ? ? ?? ?pb_last=Lb.elem+Lb.length-1;
?? ?while(pa<=pa_last&&pb<=pb_last){
?? ??? ?if(*pa<=*pb)
?? ??? ? ? ? ?*pc++=*pa++;
?? ??? ?else
?? ??? ? ? ? ? *pc++=*pb++;
?? ?}
?? ?while(pa<=pa_last)
?? ??? ?*pc++=*pa++;
?? ?while(pb<=pb_lase)
?? ??? ?*pc++=*pb++;
}//MergeList_Sq
链表
————————————————————
li 2.7
//线性表的单链表存储结构
typedef struct LNode{
?? ?ElemType data;
??? ?struct LNode *next;
}LNode,*LinkList;
//在链表中获取元素
Status GetElem_L(LinkList L,int i,ElemType &e){
?? ?//L为头指针
?? ?p=L->next;
?? ?j=1;//计数器
?? ?while(p&&j<i){
?? ? ? ? ?p=p->next;
?? ? ? ? ? j++;
?? ?}
?? ?if(!p||j>i)
?? ? ? ?return ERROR;
?? ?else
?? ? ? ? e=p->data;
?? ?return OK;
}//GetElem_L
//在链表中插入元素
Status ListInsert_L(LinkList &L,int i,ElemType e){
? ? ? ?? ?p=L;
?? ?j=0;//这里查找元素方式不同是因为包含了是第一个元素的情况，也可以用之前查找元素的方法，但是要多加判断两种情况
?? ?while(p&&j<i-1){
?? ??? ?p=p->next;
?? ??? ?j++;
?? ?}
?? ?if(!p||j>i-1)
?? ? ? ? ? ?? ?return ERROR;
?? ?s=(LinkList)malloc(sizeiof(LNode));
?? ?s->data=e;
?? ?s->next=p->next;
?? ?p->next=s;
?? ?return OK;
}//LinkInsert_L
//在链表中删除元素
Status LinkDelete_L(LinkList &L,int i,ElemType &e){
?? ?p=L;
?? ?j=0;
?? ?while((p->next)&&j<i-1){//这里因为查找的是第i-1个元素，来删除后面一个元素，所以后面一个元素必须存在，所以是p->next
?? ? ? ? ?p=p->next;
?? ? ? ? ?j++;
?? ?}
??? ?if(!(p->next)||j>i-1)
?? ??? ?return ERROR;
?? ?q=p->next;
?? ?p->next=q->next;
?? ?e=q->data;
?? ?free(q);
??? ?rerurn OK;
}//LinkDelete_L
//建立链表
void CreatList_L(LinkList &L,int n){
?? ?L=(LinkList)malloc(sizeof*(LNode));
?? ?L->next=NULL;
?? ?
?? ?for(i=n;i>0;i--){
?? ? ? ? ? ?? ?p=(LinkList)malloc(sizeof*(LNode));
?? ??? ?scanf(&p->data);
?? ??? ?p->next=L->next;
?? ??? ?L->next=p;
?? ?}
}//CreatList_L
//线性表的静态单链表的存储结构
#define MAXSIZE 100//链表最大长度
typedef struct{
?? ?ElemType data;
?? ?int cur;
}component,SLinkList[MAXSIZE];
//静态链表中的查找操作
int LocalElem_SL(LinkList S，ElemType e){
?? ?i=S[0].cur;
?? ?while(i&&S[i]!=e){
?? ??? ?i=S[i].cur;
?? ?}
?? ?return i;
}//LocalElem_SL
//---------栈---------
//栈的顺序存储结构
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10//当我们实现入栈操作时，发现栈满的时候可以增加最大容量，一般用realloc（）语法
typedef struct {
?? ?SElmeType *top;
?? ?SElmeType *base;
?? ?int stacksize;
}Sqstack;
//初始化建立一个空的栈
Status InitStack(Sqstack &S){
?? ?S.base = (SqElmeType *)malloc(sizeof*(SqElmeType));
?? ?if(!S.base){
?? ? ? ? ? ? exit(OVERFLOW);
?? ?}
?? ?S.top=S.base;
?? ?S.stacksize=STACK_INIT_SIZE;
??? ?return OK;
}//InitStack
//获取栈顶元素
Status GetTop(Sqstack S,SqElmeType &e){
?? ?//若栈不空则返回栈顶元素，反之则return ERROR；
?? ?if(S.base==S.top) return ERROR;
?? ?e=*(S.top-1);
?? ?return OK;
}//GetTop
//插入元素
Status Push(Sqstack &S,SElmeType e){
?? ?//首先要判断栈是否满
?? ?if(S.top-S.base>=S.stacksize){//栈满
?? ??? ?S.base = (SElemType *)realloc(S.base,(S.base+SIZEINCREMENT)*sizeof(SElmeType)));
?? ??? ?if(!S.base) exit(OVERFLOW);
? ? ? ? ? ?? ??? ?S.top=S.base+S.stacksize;
?? ??? ?S.stacksize+=STACKINCREMENT;
?? ?}
?? ?*S.top++=e;
?? ?return OK;
}//Push
//删除栈顶元素
Status Pop(SqStack &S,SElmeType &e){
?? ?if(S.top==S.base) return ERROR;
?? ?e = *(--S.top);
?? ?return OK;
}//Pop
//------关于汉诺塔------
核心思想：
?? ?
?? ?假设有塔a,b,c,此时都在塔a上，先将最上面的两个分别移到两个塔，b，c上，再将最小的那一个移到那个刚分出来的大的上面，此时空出一个塔，就可以将此时原来的塔中的最上面的移到空塔上，目的就是将最下面的
移出来，重复操作，一直要想着用我前面说的方法来移开上面的，将最下面的移出来。
//单链队列---队列的链式存储结构
//先创建节点，再创建队列
typedef struct QNode {
?? ?QElemType data;
?? ?struct QNode *next;
}QNode,*QueuePtr;
typedef struct {
?? ?QueuePtr front;
?? ?QueuePtr rear;
}LinkQueue;
//初始化队列
Status InitQueue(LinkQueue &Q)//默认存在队列Q{
?? ?Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
?? ?if(!Q.front) exit(OVERFLOW);
?? ?Q.front=Q.rear=NULL;
?? ?return OK;
}//InitQueue
//销毁链队列
Status DestroyQueue(LinkQueue &Q){
?? ?Q.rear=Q.front->next;
?? ?free(Q.front);
?? ?Q.front=Q.rear;
?? ?return OK;
}//DestroyQueue
//插入新元素
Status EnQueue(LinkQueue &Q,QElemType e){
?? ?p=(QueuePtr)malloc(sizeof(QNode));
?? ?p->data=e;
?? ?p->next=NULL;
?? ?Q.rear->next=p;
?? ?Q.rear=p;
?? ?return OK;
}//EnQueue
//删除队列头部的元素
Status DeQueue(LinkQueue &Q,QElemType &e){
?? ?if(Q.front==Q.rear)
?? ??? ?return ERROR;
?? ?p=Q.front->next;
?? ?e=p->data;
?? ?Q.front->next=p->next;
?? ?if(Q.rear==p)
?? ??? ?Q.rear=Q.front;
?? ?free(p);
?? ?return OK;
}//DeQueue
//---串联结----
#define MAXSTRLEN 255
#define unsigned char SString[MAXSTRLEN-1]
(S[0]用来存储串的长度)
Status Concat(SString &T,SString S1,SString S2){
?? ?if(S1[0]+S2[0]<=MAXSTRLEN){
?? ??? ?for(int i=1;i<=S1[0];i++){
?? ??? ??? ?T[i]=S1[i];
?? ??? ?}
?? ??? ?for(i=1;i<=S2[0];i++){
?? ??? ??? ?T[S1[0]+i]=S2[i];
?? ??? ?}
?? ??? ?uncut=TURE;?? ?
?? ?}
?? ?
?? ?if(S1[0]<MAXSTRLEN){
?? ? ? ? ? ?? ?for(int j=1;j<=S1[0];j++){
?? ??? ??? ?T[j]=S1[i];
?? ??? ?}
?? ??? ?for(j=1;j<=MAXSTRLEN-S2[0];j++){
?? ??? ??? ?T[S1[0]+i]=S2[MAXSTRLEN-S2[0]];
?? ??? ?}
?? ??? ?uncut=ERROR;
?? ?}
?? ?if(S1[0]==MAXSTRLEN){
?? ??? ?for(int k=1;k<=MAXSTRLEN；k++){
?? ??? ??? ?T[k]=S1[k];
?? ??? ?}
?? ??? ?uncut=ERROR;
?? ?}
? ? ? ? ? ? ? ? return uncut;
}//Concat
//----求字串---
Status SString(SString &Sub,SString S,int pos,int len){
?? ?if(pos<1||pos>StrLength(S)||len<1||len>StrLength(S)-pos+1)
?? ??? ?return ERROR;
?? ?for(int i=1;i<len;i++){
?? ??? ?Sub[i]=S[pos+i-1];
?? ?}
?? ?Sub[0]=len;
?? ?return OK;
}//SString
//---ADT String 的实现--
//串的堆分配表示
typedef struct {
? ??? ?char *ch;
?? ?int length;
}HString;
//--串的复制--
Status StrAssign(HString &T,char *chars){
?? ?if(T.ch) {
?? ??? ?free(T.ch);?? ?
?? ?}
?? ?//求串的长度i
?? ?for(int i= 0,c=chars;c;++i,++c);
?? ?if(!i){
?? ??? ?T.ch = NULL;
?? ??? ?T.length = 0;
?? ?}else{
?? ??? ?if(!(T.ch=(char *)malloc(i*sizeof(char))))
?? ??? ??? ?exit(OVERFLOW);
?? ??? ?for(int j=0;j<=i;j++){
?? ??? ??? ?T.ch[j]=chars[j];
?? ??? ?}
? ? ? ? ? ? ? ? }
? ? ??? ?return OK;?? ?
}//StrAssign
//求串的长度
int StrLength(HString S){
?? ?return S.length;
}//StrLength
//比较串的大小
int StrCompare(HString S,HString T) {
?? ?for(int i=0;i<T.length&&i<S.length;i++) {
?? ??? ?if(S.ch[i]!=T.ch[i])
?? ??? ??? ?return S.ch[i]-T.ch[i];
?? ?}
?? ?return S.length-T.length;
}//StrCompare
//清空串
Status ClearString(HString &S) {
?? ?if(S.ch){
?? ??? ?free(S.ch);
?? ??? ?S.ch = NULL;
?? ?}
?? ?S.length= 0;
?? ?return OK;
}//ClearString?
//拼接串
Status Concat(HString &T,HString S1,HString S2) {
?? ?if(T.ch)
?? ? ? ? ?free(T.ch);
?? ?if(!(T.ch=(char *)malloc(S1.length+S2.length)*sizeof(char)))
?? ??? ?exit(OVERFLOW);
?? ?for(int i=0;i<=S1.length-1;i++){
?? ??? ?T.ch[i]=S1.ch[i];
?? ?}
?? ?T.length=S1.length+S2.length;
?? ?for(i=0;i<=S2.length-1;i++) {
?? ??? ?T.ch[S1.length+i]= S2.[i];
?? ?}
? ?? ?return OK;
}//Concat
//截取字串
Status SubString(HString &Sub,HString S,int pos ,int len) {
? ? ??? ?if(pos<1||pos>S.length||len<0||len>S.length-pos+1)
?? ??? ?return ERROR;
?? ?if(Sub.ch){
?? ??? ?free(Sub.ch);
?? ?}
?? ?//当串为空串时
?? ?if(!len){
?? ??? ?Sub.ch=NULL;
?? ??? ?Sub.length=0;
?? ?}else{
?? ??? ?if(!Sub.ch=(char *)malloc(len*sizeof(char)))
?? ??? ??? ?exit(OVERFLOW);
?? ??? ?for(int i=0;i<=len-1;i++){
?? ??? ??? ?Sub.ch[i]=S.ch[pos+i-1];
?? ??? ?}
?? ?}
?? ?return OK;
}//SubString?
//--串的块链存储
#define CHUNKSIZE 80
typedef struct Chunk{
?? ?char ch[CHUNKSIZE];
?? ?struct Chunk *next;
}Chunk;
typedef struct {
? ??? ?Chunk *head,*tail;
?? ?int curlen;?? ?
}LString;
//建立二叉树
//存储结构
typedef struct BiTNode {
?? ?char data;
?? ?struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
Status CreatBiTree (BiTree){
?? ?char ch;
?? ?scanf("%c",&ch);
?? ?if(ch=="#")
?? ??? ?*T= NULL;
?? ?else{
?? ??? ?*T=(BiTree)malloc(sizeof(BiTNode));
?? ??? ?if(!*T)
?? ??? ??? ?exit(-1);
?? ??? ?CreatBiTree(T->lchild);
?? ??? ?CreatBiTree(T->rchild);//递归创建左右子树
?? ?}
}
//先序遍历(中序以及后序与之类似，只需要调整if中的语句顺序即可)递归算法
void Pre(BiTree T){
?? ?if(T!=NULL){
?? ??? ?printf("%d\t",T->data);
?? ??? ?Pre(T->lchild);
?? ??? ?Pre(T->rchild);
?? ?}
}
//计算深度
int Depth(BiTree T) {
?? ?if(T==NULL) return 0;
?? ?else{
?? ??? ?m= Depth(T->lchild);
?? ??? ?n= Depth(T->rchild);
?? ??? ?if(m>n)
?? ??? ??? ?return m+1;
?? ??? ?else
?? ??? ??? ?return n+1;
?? ?}
}
//节点数计算
int NodeCount(BiTree) {
?? ?if(T==NULL)
?? ??? ?return 0;
?? ?else {
?? ??? ?return(NodeCount(T->lchild)+NodeCount(T->rchild)+1);
?? ?}
}
//叶子节点计算
int LeafCount(BiTree T){
?? ?if(T==NULL)
?? ??? ?return 0;
?? ?if(T->lchild== NULL&&T->rchild==NULL)
?? ??? ?return 1;
?? ?else{
?? ??? ?return LeafCount(T->lchild)+LeafCount(T->rchild);
?? ?}
}
//线索二叉树
//存储结构
typedef struct BiThrTree {
?? ?int data;
?? ?int ltag,rtag;
?? ?struct BiThrTree *lchild,*rchild;
}BiThrTree,*BiThrTree;
//树
//每个节点的存储结构
typedef struct PTNode {
?? ?TElemType data;
?? ?int parent;//双亲位置域
}PTNode;
//树结构
#define MAX_TREE_SIZE 100
typedef struct {
?? ?PTNode nodes[MAX_TREE_SIZE]；
?? ?int r,n;
}PTree;
//树结构的孩子链表形式
typedef struct CTNode {
?? ?int child;
?? ?struct CTNode *next;
}*ChildPtr;
typedef struct {
?? ?TElemType data;
?? ?ChildPtr firstchild;
}CTBox;
typedef struct {
?? ?CTBox nodes[MAX_TREE_SIZE];
?? ?int r,n;
}CTree;
//树的孩子兄弟表示法的存储结构
typedef struct CSNode {
?? ?TElemType data;
?? ?struct CSNode *firstchild,*nextsibling;
}CSNode,*CSTree;
//哈夫曼树
//顺序存储结构
typedef struct {
?? ?int weight;
?? ?int parent,lch,rch;
}HTNode,*HuffmanTree;
//开始建树
void CreatHuffmanTree (HuffmanTree HT,int n){
//初始化数据
?? ?if(n<=1) return ;
?? ?m= 2*n-1;
?? ?HT= new HTNode[m+1];//这里不算C语言的语法，可以算为伪代码，用java语法来理解
?? ?for(i= 1;i<=m;i++) {
?? ??? ?HT[i].parent= 0;
?? ??? ?HT[i].lch= 0;
?? ??? ?HT[i].rch= 0;
?? ?}
?? ?for(i= 1;i<=n;++i) {
?? ??? ?cin>>HT[i].weight;
//这里也是伪代码，可与理解为输入weight的值 ?在c++中
?? ?}
?? ?for(i= n+1;i<=m;++i) {
?? ??? ?Select(HT,i-1,s1,s2);//这里可以用打擂台的方法来选出最小的两个值的索引 ，简而言之的封装
?? ??? ?HT[s1].parent= i;
?? ??? ?HT[s2].parent= i;
?? ??? ?HT[i].weight= HT[s1].weight+HT[s2].weight;
?? ??? ?HT[i].lch=s1;
?? ??? ?HT[i].rch= s2;?? ?
?? ?}
?? ?
}
//图的邻接矩阵存储结构
#define MAZINT 32767
#define MVNum 100
typedef char VerTexType;
typedef int ArcType;
typedef struct {
?? ?VerTexType vexs[MVNum];//用来输入点
?? ?ArcType arcs[MVNum][MVNum];//网时用于存储点的权值
?? ?int vexnum,arcnum;//总的点数和边数
?? ?
}AMGraph;
Status CreatUDN(AMGraph &G) {
?? ?int quanzhi;
?? ?char v1,v2;
?? ?scanf("%c",&G.vexnum);
?? ?scanf("%c",&G.arcnum);
?? ?
?? ?for(int i=0;i<G.vexnum;i++){
?? ??? ?scanf("%c",&vexs[i]);
?? ?}
?? ?for(int i=0;i<G.vexnum;i++)
?? ??? ?for(int j= 0;j<G.vexnum;j++)
?? ??? ??? ?arcs[i][j]=MAXINT;
?? ?for(int i=0;i<G.vexnum;i++) {
?? ??? ?scanf("%d",&quanzhi);
?? ??? ?scanf("%c",&v1);
?? ??? ?scanf("%c",&v2);
?? ??? ?i=LocateVex(G,v1);
a?? ??? ?j=LocateVex(G,v2);
?? ??? ?arcs[i][j]= w;
?? ??? ?arcs[i][j]=arcs[j][i];
?? ?}
?? ?return OK;
}
int LocateVex(AMGraph G,VerTexType u) {
?? ?int i;
?? ?for(i=o;i<G.vexnum;i++) {
?? ??? ?if(u==G.vexs[i])
?? ??? ??? ?return 1;
?? ?}
?? ?return -1;
}
//无向网：无方向但又权值
有向网：有方向也有权值
无向图：无方向也无权值，但是在创建是都认为权值默认为1，初始化时为0
//采用邻接矩阵的图的DFS（深度优先遍历）
void DFS(AMGraph G,int v){
//v 是你输入的起始点
//如果visit数组为0则未访问，1则已经访问
?? ?scanf("%d",&v);
?? ?visit[v]= true;
?? ?for(int w= 0;w<G.vexnum;w++)
?? ??? ?if((G.arcs[v][w]!=0)&&(!visit[w]))
?? ??? ??? ?DFS(G，w)；//递归调用DFS
}
//邻接表表示方法创建无向网
Status CreatUDG(ALGraph &G) {
?? ?scanf("%d%d",&vexnum,&arcsnum)
//输入总结数和边数
?? ?for(int i=0;i<G.vexnum;i++) {
?? ??? ?scanf("%c",&G.vertice[i]);
?? ??? ?G.vertice[i].firstarc=NULL;
?? ?}
?? ?//构造邻接表
?? ?for(int j=0;j<G.arcsnum;j++) {
?? ??? ?scanf("%c%c",&v1,&v2);
?? ??? ?i=LocalVex(G,v1);
?? ??? ?j=LocalVex(G,v2);
?? ??? ?p->adjex=j;
?? ??? ?p=(ANode *)malloc(sizeof(ANode));
?? ??? ?//尾插法
?? ??? ?p->next=G.vertices[i].firstarc;
?? ??? ?G.vertices[i].firstarc=p;
?? ??? ?p->adjex=j;
?? ??? ?//用相同操作操作另一个对称节点
?? ??? ?p1->next=G.vertices[j].firstarc;
?? ??? ?G.vertices[j].firstarc=p1;
?? ??? ?p1->adjex=i;
?? ??? ?
?? ?}
}
|