**一、顺序表** \#define MAXNUM 100 /* 表示线性表可能达到的最大长度 */ typedef int DataType; /* 数据元素类型定义 */ typedef struct { DataType data[MAXNUM]; /* 存放线性表的数据元素 */ //int last; /* 用来存放线性表最后一个数据元素在数组中的下标 */ ​ int length; }SeqList; 1. 顺序表定位运算 int SeqLLocate(SeqList l, DataType x) { int i; for(i=0;il.length+1) { printf("\t 插入位置不正确 \n"); return ERROR; } else { for (j=l.length-1;j>=i-1;j--) l.data[j+1]=l.data[j]; l.data[i-1]=x; l.length++; } return OK; } 3. 顺序表删除运算 int SeqLDelete(SeqList l,int i) { int j; if (i<1||i>l.length) { printf("\t 删除位置不正确 \n"); return ERROR; } else { for(j=i;j<=l.length-1;j++) l.data[j-1]=l.data[j]; l.length--; } return OK; } 4. 建立顺序表 void SeqLCreate(SeqList l) { int i,n; printf("\t请输入表的长度:"); scanf("%d",&n); l.length=n; printf("\t依次输入表中的数据元素（整数）:\n"); for(i=0;inext; j=0; while(p!=NULL) { p=p->next; j++; } return j; } 6. 单链表取结点 LinkedList * GetLListElem(LinkedList *L, int i) /*在带头结点的单链表L中查找第i个结点*/ { /*若找到(1≤i≤n)，则返回该结点的存储位置; 否则返回NULL*/ int j; LinkedList *p; p=L; j=0; /*从头结点开始扫描*/ while ((p->next!=NULL)&&(jnext; /* 扫描下一结点*/ j++; /* 已扫描结点计数器 */ } if(i == j) return p; /* 找到了第i个结点 */ else return NULL; /* 找不到，i≤0或i>n */ } 7. 单链表定位运算 LinkedList *LocateLListElem( LinkedList *L,DataType key) /*在带头结点的单链表L中查找其*/ { /*结点值等于key的结点，若找到则返回该结点的位置p，否则返回NULL*/ LinkedList *p; p=L->next; /* 从表中第一个结点开始 */ while (p!=NULL) { if (p->data!=key) p=p->next; else break; /* 找到结点值=key时退出循环 */ } return p; } 8. 单链表插入运算 int InsertLList(LinkedList *L,int i,DataType x) { /*在带头结点的单链表L中第i个位置插入值为e的新结点s*/ LinkedList *pre,*s; int k; pre=L; k=0; /* 从"头"开始，查找第i-1个结点 */ while(pre!=NULL&&knext; k=k+1; } /* 查找第i-1结点 */ if(!pre) /* 如当前位置pre为空表，说明插入位置不合理 */ { printf("插入位置不合理!"); return ERROR; } s=(LinkedList*)malloc(sizeof(LinkedList)); /* 申请一个新的结点s */ s->data=x; /* 值x置入s的数据域 */ s->next=pre->next; /* 修改指针，完成插入操作 */ pre->next=s; return OK; } 9. 单链表删除运算 int DeleteLList(LinkedList *L,int i,DataType *e) { /*在带头结点的单链表L中删除第i个元素，并将删除的元素保存到变量*e中*/ LinkedList *pre,*r; int k; pre=L; k=0; while(pre->next!=NULL && knext; k=k+1; } /* 查找第i-1个结点 */ if(!(pre->next)) /* 即while循环是因为p->next=NULL或i<1而跳出的,*/ { /*而是因为没有找到合法的前驱位置，说明删除位置i不合法。*/ printf("删除结点的位置i不合理!"); return ERROR; } r=pre->next; pre->next=pre->next->next; /* 修改指针，删除结点r */ *e = r->data; free(r); /* 释放被删除的结点所占的内存空间 */ printf("成功删除结点!"); return OK; } 10. 建立不带头结点的单链表（头插法建表） LinkedList *CreateLList() { char ch; LinkedList *head,*s; head=NULL; ch=getchar(); while(ch!='$') /* 循环输入表中元素值，将建立的新结点s插入表头，输入'$'结束 */ { s=(LinkedList *)malloc(sizeof(LinkedList)); s->data=ch; s->next=head; head=s; ch=getchar(); } return head; } 11. 建立带头结点的单链表（尾插法建表） LinkedList *CreateLListR() { char ch; LinkedList *head,*s,*r; head=(LinkedList *)malloc(sizeof(LinkedList)); r=head; ch=getchar(); while(ch!='$') /* 循环输入表中元素值，将建立的新结点s插入表尾，输入'$'结束 */ { s=(LinkedList *)malloc(sizeof(LinkedList)); s->data=ch; r->next=s; r=s; ch=getchar(); } r->next=NULL; /* 将最后一个结点的next链域置为空，表示链表的结束 */ return head; } **三、顺序栈** typedef struct/*顺序栈定义*/ { DataType data[MAXNUM]; /* 存放栈的数据元素 */ int top; /* 栈顶指针，用来存放栈顶元素在数组中的下标 */ }SeqStack; 12. 入栈 int SStackPush(SeqStack *s, DataType x) { if (s->top==MAXNUM) { ​ printf("栈上溢出!\n"); ​ return FALSE; } else { ​ s->top = s->top + 1; ​ s->data[s->top]=x; ​ return TRUE; } } 13. 出栈 int SStackPop(SeqStack *s, DataType *x) { if (s->top==-1) { ​ printf("栈下溢出!\n"); ​ return FALSE; } else { ​ *x=s->data[s->top]; ​ s->top--; ​ return TRUE; } } **四、链栈** typedef struct node { DataType data; /*数据域*/ struct node * next; /*指针域*/ }LinkStack; /*链栈结点类型*/ 14. 初始化链栈 LinkStack* LStackInit()/*初始化链栈*/ { LinkStack *h; h=(LinkStack*)malloc(sizeof(LinkStack)); h->data=1; h->next=NULL; return h; } 15. 入链栈 LinkStack *LStackPush(LinkStack *ls,DataType x)/*入栈*/ { LinkStack *p; p=(LinkStack *)malloc(sizeof(LinkStack));/*分配空间*/ p->data=x; /*设置新结点的值*/ p->next=ls; /*将新元素插入栈中*/ ls=p; /*将新元素设为栈顶*/ return ls; } 16. 出链栈 LinkStack *LStackPop(LinkStack *ls,DataType *e)/*出栈*/ { LinkStack *p; if(!ls)/*判断是否为空栈*/ { printf("\n链栈是空的!"); return NULL; } p=ls; /*指向被删除的栈顶*/ *e=p->data;/*返回栈顶元素*/ ls=ls->next; /*修改栈顶指针*/ free(p); return ls; } **五、顺序队列** typedef struct /*顺序队列类型定义*/ { int front, rear; DataType data[MAXNUM]; }SeqQueue; 17. 创建空队列 SeqQueue *SQueueCreate() /*创建一个空队列*/ { SeqQueue *sq = (SeqQueue*)malloc(sizeof(SeqQueue)); if (sq==NULL) ​ printf("溢出!! \n"); else ​ sq->front = sq->rear = 0; return sq; } 18. 入队 void SQueueEnQueue( SeqQueue *sq, DataType x )/* 循环队列的进队操作，x进队 */ { if( (sq->rear + 1) % MAXNUM == sq->front ) /* 修改队尾指针 */ ​ printf( "队列满!\n" ); else { sq->data[sq->rear] = x; sq->rear = (sq->rear + 1) % MAXNUM; } } 19. 出队 int SQueueDeQueue( SeqQueue *sq ,DataType *e) /* 循环队列的出队操作，出队元素存入e中 */ { if( sq->front == sq->rear ) { printf( "队空!\n" ); return ERROR; } else { ​ *e=sq->data[sq->front]; sq->front = (sq->front + 1) % MAXNUM; /* 修改队头指针 */ return OK; } } **六、链队列** typedef struct LQNode/* 链队结点结构 */ { DataType info; struct LQNode *next; }LQNode; typedef struct/* 链接队列类型定义 */ { struct LQNode *front; /* 头指针 */ struct LQNode *rear; /* 尾指针 */ }LinkQueue; 20. 创建空链队 LinkQueue *LQueueCreateEmpty()/*创建空链队,返回头指针*/ { LinkQueue *plq = (LinkQueue *)malloc(sizeof(LinkQueue)); if (plq != NULL) ​ plq->front = plq->rear = NULL; else { ​ printf("内存不足!! \n"); ​ return NULL; } return plq; } 21. 入链队 void LQueueEnQueue( LinkQueue *plq, DataType x)/*入链队*/ { LQNode *p = (LQNode *)malloc(sizeof(LQNode)); if ( p == NULL ) ​ printf("内存分配失败!\n"); else { ​ p->info = x; ​ p->next = NULL; ​ if (plq->front == NULL)/*原来为空队*/ ​ plq->front = p; ​ else ​ plq->rear->next = p; ​ plq->rear = p; } } 22. 出链队 int LQueueDeQueue( LinkQueue *plq,DataType * x)/*出链队*/ { LQNode *p; if( plq->front == NULL ) { ​ printf( "队列空!!\n " ); ​ return ERROR; } else { ​ p = plq->front; ​ *x=p->info; ​ plq->front = plq->front->next; ​ free(p); ​ return OK; } } **七、串** \#define MAXSTRLEN 255 // 用户可在255以内定义最大串长 typedef unsigned char Sstring[MAXSTRLEN + 1];// 0号单元存放串的长度 23. 串的简单匹配 int Index(SString S, SString T, int pos) { // 返回子串T在主串S第pos个字符之后的位置。若不存在，则函数值为0。其中，T非空，1≤pos≤StrLength(S)。 i = pos; j = 1; while (i <= S[0] && j <= T[0]) { if (S[i] == T[j]) { ++i; ++j; }// 继续比较后继字符 else { i = i-j+2; j = 1; } // 指针后退重新开始匹配 } if (j > T[0]) return i-T[0]; else return 0; } // Index 24. 串的联接 Status Concat(SString S1, SString S2, SString &T) { // T返回S1和S2接成的新串。若无截断, 返回TRUE，否则FALSE。 if (S1[0]+S2[0] <= MAXSTRLEN) {// 未截断 ​ T[1..S1[0]] = S1[1..S1[0]]; ​ T[S1[0]+1..S1[0]+S2[0]] = S2[1..S2[0]]; T[0] = S1[0]+S2[0]; uncut = TRUE; } else if (S1[0] data=ch; ​ s->lchild=NULL; ​ s->rchild=NULL; ​ } ​ rear++; ​ Q[rear]=s; /* 空结点和新结点都入队 */ ​ if(rear==1) ​ root=s; /* rear是1，是根结点，用root指向它 */ ​ else ​ { ​ if(s&&Q[front]) /* 当前结点和双亲结点都非空 */ ​ if(rear%2==0)/*rear是偶数，新结点为双亲的左孩子*/ ​ Q[front]->lchild=s; ​ else /* rear是奇数，新结点为双亲的右孩子 */ ​ Q[front]->rchild=s; ​ if(rear%2==1) /* rear是奇数*/ ​ front++; /* 头指针front指向下一个双亲*/ ​ } ​ ch=getchar(); } return root; } 26. 递归方法求二叉树的高度 int BiTreeDepthPost(BiTree *t) /*递归算法后序遍历求二叉树的高度*/ { int hl,hr,max; if(t) { ​ hl=BiTreeDepthPost(t->lchild); /* 求左子树的深度 */ ​ hr=BiTreeDepthPost(t->rchild); /* 求右子树的深度 */ ​ max=hl>hr?hl:hr; /* 得到左、右子树深度较大者*/ ​ return max+1; /* 返回树的深度 */ } else ​ return ERROR; /* 如果是空树，则返回0 */ } 27. 中序遍历的非递归算法 BiTNode *GoFarLeft(BiTree T, Stack &S) { /*寻找第一个要访问的结点*/ if (!T ) return NULL; while (T->lchild ) { // 直到左端 Push(S, T); T = T->lchild; } return T; } void Inorder_I(BiTree T, void (*visit)(TelemType& e)) {/*寻找下一个要访问的结点*/ Stack S; InitStack(S); t = GoFarLeft(T, S); // 找到最左下的结点 while (t) { visit(t->data); if (t->rchild) t = GoFarLeft(t->rchild, S); else if ( !StackEmpty(S )) // 栈不空时退栈 ​ t = Pop(S); else t = NULL; // 栈空表明遍历结束 } } **九、图** typedef struct EdgeNode/*图的边结构定义*/ { int endvex; /* 相邻顶点字段 */ AdjType weight; /* 边的权，非带权图可以省略 */ struct EdgeNode *nextedge; /* 链字段 */ }EdgeNode; /* 边表中的结点 */ typedef struct /*图的顶点结构定义*/ { VexType vertex; /* 顶点信息 */ EdgeNode *edgelist; /* 边表头指针 */ } VexNode; /* 顶点表中的结点 */ typedef struct /*图的数据结构定义*/ { int vexNum; /* 图的顶点个数 */ int edgeNum; /* 图的边的条数 */ VexNode vexs[MAXVEX]; } GraphList;/*图的邻接表存储结构*/ 28. 创建无向网邻接表 void LUDGCreate(GraphList *g)/*创建无向网邻接表*/ { int i,j,k; EdgeNode *s; float w;/*权值*/ printf("\n请输入无向网的顶点的个数(不超过%d个)\n",MAXVEX); scanf("%d",&g->vexNum); printf("\n请输入网中各个顶点的数据信息(如v1)!\n"); getchar();/*去掉回车符*/ for(i=0;ivexNum;i++)/*初始化*/ { ​ gets(g->vexs[i].vertex); ​ g->vexs[i].edgelist=NULL; } printf("\n请输入该网中边的数目(不超过%d条)\n",g->vexNum*(g->vexNum-1)/2); scanf("%d",&g->edgeNum);/*读入边的数目*/ for(k=0;kedgeNum;k++) { ​ printf("\n请输入第%d条边的相关信息(起始顶点(序号从0开始) 终止顶点 权值,如0 3 10.5)\n",k+1); ​ scanf("%d%d%f",&i,&j,&w);/*读入边的起止点及权值*/ ​ s=(EdgeNode *)malloc(sizeof(EdgeNode));/*生成边结点*/ ​ s->endvex = j; ​ s->nextedge=g->vexs[i].edgelist; ​ s->weight=w; ​ g->vexs[i].edgelist=s; ​ s=(EdgeNode *)malloc(sizeof(EdgeNode));/*无向网,边对称*/ ​ s->endvex = i; ​ s->nextedge=g->vexs[j].edgelist; ​ s->weight=w; ​ g->vexs[j].edgelist=s; } } 29. 连通图的广度优先遍历 void LUDGbfs( GraphList* g , DataType v ,int visited[]) /*连通图的邻接表存储广度优先遍历,需要使用队列*/ { /*visited数组变量,用于标记访问过的顶点*/ DataType v1 , v2; SeqQueue *q = SQueueCreate( ) ; /* 队列元素的类型为DataType* */ SQueueEnQueue( q ,v ) ;/*初始顶点入队*/ printf("%d ",v); visited[v] = TRUE ;/*置访问标志*/ while ( !SQueueIsEmpty(q) ) /*队列不空情况下循环*/ { ​ SQueueDeQueue( q,&v1 );/*队头元素出队*/ ​ v2 = LUDGFirstAdjacent ( g ,v1 );/*找到v1的第一个邻接顶点*/ ​ while ( v2 != ERROR )/*当v1的邻接顶点存在*/ ​ { ​ if ( visited[v2] == FALSE )/*未访问过,则置访问标志,同时入队*/ ​ { ​ SQueueEnQueue( q, v2 ); ​ visited[v2] = TRUE ; ​ printf("%d ",v2); ​ } ​ v2 = LUDGNextAdjacent ( g , v1 , v2 ) ;/*再取下一个邻接顶点*/ ​ } } } 30. 非连通图的广度优先遍历 void LUDGbft( GraphList* g,int visited[])/*非连通图的邻接表存储广度优先遍历*/ { DataType v ; for ( v = LUDGFirstVertex ( g ) ; v != ERROR ; v = LUDGNextVertex ( g , v ) ) ​ if ( visited[v] == FALSE ) LUDGbfs ( g , v,visited ) ;/*对图中每一个未访问过的顶点,递归遍历*/ } 31. 连通图的深度优先遍历 void LUDGdfs(GraphList* g , DataType v,int visited[])/*连通图的邻接表表示深度优先遍历*/ { EdgeNode *p; printf("%d",v);/*输出顶点信息,置访问标志*/ visited[v]=TRUE; p=g->vexs[v].edgelist;/*取出邻接顶点链表头*/ while(p!=NULL)/*邻接顶点存在*/ { ​ if(!visited[p->endvex])/*未访问过则递归访问*/ ​ LUDGdfs(g,p->endvex,visited); ​ p=p->nextedge;/*取下一邻接顶点*/ } } 32. 非连通图的深度优先遍历 void LUDGdft( GraphList* g,int visited[] )/*非连通图的邻接表表示深度优先遍历*/ { DataType v ; for ( v=0 ; vvexNum ; v++ )/*对图中每一个未访问过的顶点,递归遍历*/ ​ if ( visited[v] == FALSE ) LUDGdfs ( g , v,visited ) ; }