/*--------------------数据结构部分------------------------*//*二.设有一个由正整数组成的无序单链表，编写完成下列功能的算法：1.找出最小值结点，且打印该数值；2.若该数值是奇数，则将其与直接后继结点的数值交换；3.若该数值是偶数，则将其直接后继结点删除。*/#include<stdio.h>#include<stdlib.h>#include<malloc.h>#define OK 1#define OVERFLOW -2typedef int Status;typedef int ElemType;typedef struct LNode{ElemType data;struct LNode *next;}LNode,* LinkList;Status CreateList(LinkList &L,int n){ //创建链表LinkList p,q;L=(LinkList)malloc(sizeof(LNode));p=L;for(int i=0;i<n;i++){q=(LinkList)malloc(sizeof(LNode));scanf("%d",&q->data);p->next=q;p=q;}p->next=NULL;return OK;}Status MinList(LinkList L){LinkList p,q;ElemType min;p=L->next;min=p->data;q=p;while(p){if(p->data>min) p=p->next;else{ min=p->data;q=p;p=p->next;}}printf("最小值结点值为：%d \n",min);if(q->next!=NULL){if(min%2==0){p=q->next;q->next=p->next;free(p);}else{p=q->next;q->data=p->data;p->data=min;}}else printf("最小值结点直接后继为空\n");return OK;}Status ShowList(LinkList L){LinkList p;p=L->next;while(p){printf("%4d",p->data);p=p->next;}printf("\n\n");return OK;}int main(){LinkList L;int n;printf("请输入元素个数为: ");scanf("%d",&n);CreateList(L,n);printf("输出当前单链表为: \n");ShowList(L);MinList(L);printf("输出当前单链表为: \n");ShowList(L);system("pause");}/*四.3.假设一个有向图g已经以十字链表形式存储在内存中，试编写一个判断该有向图中是否有环（回路）的算法*///对十字链表储存结构的有向图采用拓扑排序Status toposort (OLGraph G){findindegree (G, indegree); //对各项点求入度InitQueue (Q);//队列初始化Count=0; //计数器初始化for(i=0;i<G.Vernum;i++)if(G.Ver[ i ].indegree==0)Enqueue(Q,i); //入度为零的顶点入队While(！QueueEmpty (Q) ) ﹛Dequeue(Q,i); //队头出队Count++;P=G. ver [ i ].firstout; //取邻接点while(p) ﹛//处理邻接点的入度j=p→ headvex;G.ver [ j ].indegree--;if(G.ver [ j ].indegree==0)Enqueue (Q,j);//顶点j入队p=p→tlink;//指针后移｝//while｝//whileif ( (count<G.vernum) //有环return ERROR;elsereturn OK;} // toposort/*五、写出删除二叉排序树bt中值为x的结点的算法（二叉排序树以二叉链表形式存储，删除后仍保持二叉排序性质）*/Status delete(BiTree ﹠t ,ElemType x){// 删除二叉排序树中的x接点if(x<p→data{q=p;p=p->lchild;} // ifelse{q=p;p=p->rchild;} // elseif(!p) return false; // 来找到else if(!p->rchild){ //被删结点无右子权q=p; p=p->lchild;// 重接free(q);} // ifelse if(!p->rchild){ // 无左子树q=p;p=p->rchild;// 重接free(q);} // ifelse{ //左、右子树均不空q=p;s=p->rchild;while(s->rchild){ // 转左、右找q=s;s=s->rchild;} // whilep→data=s->data;// 置换if(q!=p)q->rchild=s->lchild;// 重接左子树elseq->rchild=s->lchild;// 重接右子树}// else} //delete/*六、设有n个大小不等的数据组（n个数据组中数据的总数为m），顺序存放在空间区D内，每个数据占一个存储单元。数据组的首地址由数组S给出（如下图所示），试编写将新数据x插入到第i个数据组的末尾且属于第i个数据组的算法，插入后，空间区D和数组S的相互关系仍保持正确。*/void lnsert_x(sqlist ﹠L, int I, ElemType x ){// 将数据x插入到D区，插入后D和S关系不变if( i>=I &&i <= L.length){for(j=0 , p=L. elem[ 0 ],j<=m; j+ +)p++; // 求D区空闲空间首地址if(i==L.lingth)*p=x;else{ // 不插入第n个数组for(q=L.elem[ i ]; p>=q;--p)*(p+l)=*p; //后移*p=x; //插入xfor(q = &L.elem[i],p = &L.elem[ L.length-I];p >= q;q++)(*q)++;m++;}}} //Insert_x/*--------------------C语言部分----------------------*//*二.编写一个函数void merge(int ary1[], int n, int ary2[], int m),其中n为数组ary1中元素的人数，m为数组ary2中元素的个数，数组ary1和ary2已按升序排序。该函数将ary1和ary2进行合并，合并后的结果存放在数组ary1中且保序。假定数组ary1有足够的存储空间。*/void merge(int ary1[], int n, int ary2[], int m){int i = 0, j = 0, k = 0, index;while(i < n && j < m){if(ary1[i] <= ary2[j])ary1[k++] = ary1[i++];elseary1[k++] = ary2[j++];}//将较长的数组中剩余元素继续插入到ary1中while(i < n){ary1[k++] = ary1[i++];}while(j < m){ary1[k++] = ary2[j++];}}/*三.写一递归函数，完成回文的判定。回文是只有如下形式的字符串"a","abccba","abcdcba"回文是指串正读和反读都一样*/int turn(char *str){char *p;p=str+strlen(str)-1;if(*str != *p)return 0;else{if(p->str <= 2)return 1;else{*p = '\0';return(turn(str+1));}}}/*五.对于仅含+、-、*、\的算术表达式（1）写一函数，建立表达式树，该函数的输入为算术表达式的字符串（2）写一函数，按逆波兰式（后序遍历）输出该表达式，该函数的输入为表达式树*/#include <stdio.h>#include <stdlib.h>typedef char Elem;typedef struct Node{Elem data;struct Node *pLchild;struct Node *pRchild;}BTreeNode, *BTree;BTree CreateBTree(BTree T, Elem *str)//创建二叉树{static int i = 0;if ('0' == str[i]){T = NULL;}else{T = (BTree) malloc (sizeof(BTreeNode));T->data = str[i++];T->pLchild = CreateBTree(T->pLchild, str);i++;T->pRchild = CreateBTree(T->pRchild, str);}return T;}void PostTraverseBTree(BTree T)//后序{if (NULL != T){PostTraverseBTree(T->pLchild);PostTraverseBTree(T->pRchild);printf("%c ", T->data);}}void InTraverseBTree(BTree T)//中序{if (NULL != T){InTraverseBTree(T->pLchild);printf("%c ", T->data);InTraverseBTree(T->pRchild); }}void PreTraverseBTree(BTree T)//前序{if (NULL != T){printf("%c ", T->data);PreTraverseBTree(T->pLchild);PreTraverseBTree(T->pRchild);}}int main(void){BTree T = NULL;Elem str[] = "+-/+a00b00c00d00*e00f00";T = CreateBTree(T, str);printf("\n\n");printf("先序遍历(前缀式):\n");PreTraverseBTree(T);printf("\n\n");printf("中序遍历(中缀式):\n");InTraverseBTree(T);printf("\n\n");printf("后序遍历(后缀式):\n");PostTraverseBTree(T);printf("\n\n");system("pause");}
