数据结构算法.doc

顺序表插入SqList *Insert_SqList (SqList *L，int i，Elemtype x) { // 在顺序表L的第 i 个位置上插入一个值为 x 的新元素 if ((i<1) || ( i>L->length+1)) //检查插入位置的正确性 { printf (“插入位置i不合理！”); exit(1); } //不合理，中止程序运行 if (L->length >= L->MaxSize-1) // 顺序表是否已满 { printf (“顺序表已满，不能再插入！”); exit(1); } // 表满,不能插入 for (m=L->length-1; m>= i-1; --m) L->data [m+1] = L->data[m]; // 结点后移 L->data [i-1] = x; //新元素插入 L->length++; //表长+1 return L; //插入成功，返回 } 顺序表删除SqList *Delete_SqList(SqList *L, int i，Elemtype e){ // 删除顺序表L中第 i 个元素，删除元素的值保存在 e 中 if ((i<1) || (i>L->length)) // 检查删除位置的正确性 { printf (“插入位置i不合理！”); exit(1); } //插入位置不合理，中止程序运行 e = L->data[i-1]; //删除ai之后，该数据就不存在，如果需要，先取出ai的值保存 for ( i; i<=L->length-1; ++i ) L->data[i-1] = L->data[ i ]; //结点前移 L->length = L->length-1; //表长-1 return L; //插入成功，返回}顺序表按值查找int LocateElem_Sq(SqList *L，Elemtype x) { int i = 1; while( i <= L->length && L->data[i -1] != x) i ++; if (i >L->length) return -1; else return i; /*Return the position of x */ } 链表头插入法Linklist CreateList_L (int n) { LinkList L;LinkList p;int x; L= (LinkList) malloc(sizeof(Lnode)); L->next=NULL; //建立一个空表 Scanf(“%d”,&x);While(x!=0) { p= (LinkList) malloc(sizeof(Lnode)); p->data=x; //读入要插入元素值 p->next= L->next; L->next=p; scanf(“%d”,&x); } return L; }头插入法Linklist CreateList_L (int n) { LinkList L; 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; //修改链接关系 } return L; }单链表按值查找LinkList Locate_LinkList( LinkList L, ElemType x) /*在单链表L中查找值为x的结点，找到后返回其指针，否则返回空*/ { LinkList p; p=L->next; while ( p!=NULL && p->data != x) p=p->next; // 向后查找 return p; }单链表插入Linklist ListInsert (LinkList L, int i, Elemtype x ) { //在带头结点单链表第 i 个结点前插入新元素x p=L; j=0; while ( p != NULL && j< i -1 ) { p = p→next; j++; } //找第 i-1个结点 if ( p == NULL || j>i-1 ) return Error; newnode= (LinkList ) malloc(sizeof(Lnode)); //创建新结点,其数据为x newnode→data=x; newnode→next = p→next; p→next = newnode; return (L); }1. void Delete (SeqList * L, ElemType x )// 从顺序表中删除值为x的第一个元素{ int i=0; while(ilength&&L-> elem[i]!=x) i++; if( i= = L->length ) printf(“不存在值为x的元素”)； else { for(;i< L->length-1;i++) L-> elem[i]= L-> elem[i+1]; L->length--;}}2. void Insert_Prenode(LinkList L, ElemType x, ElemType e)// 在单链表L中值为x的结点前插入值为e的新元素 { LNode *p, *q; p=L->next; //p指向当前结点 q=L; //q指向p的直接前驱 while ( p&&p->data!=x) { q=p; p=p->next; } if( !p ) printf(“不存在值为x的结点”)； else { p=( LNode *)malloc(sizeof(LNode)); p->data=e;p->next= q->next; q->next=p; } }判断是否为空栈Int IsEmpty(Seqstack *s){return(s->top == -1) ?1:0;}进栈void Push(SeqStack *s, StackElementType x) { if (s->top == StackInitSize) { printf("栈满! 栈发生上溢，程序运行终止!\n"); exit(0); } else { s->top++; /* 栈顶指针加1，指向新的栈顶 */ s->data[s->top] = x; /* 将数据元素x压入栈 */ } return;}退栈（先取出元素）StackElementType Pop(SeqStack *s){ StackElementType temp; if(IsEmpty(s)) { printf("栈空！栈发生下溢，程序运行终止!\n"); exit(0); } else { temp=s->data[s->top]; s->top--; return temp; }}二叉链表数据类型描述typedef XXX Elemtype;typedef struct BiTnode { Elemtype data; struct BiTnode *lchild,*rchild; /*左右孩子指针*/ } BiTnode,*BiTree;typedef BiTnode *BiTree; 二叉树前序遍历的递归算法void PreOrder（BiTree bt） { /*先序遍历二叉树bt*/ if (bt==NULL) return; /*递归调用的结束条件*/ printf("%d",bt->data); /*访问结点的数据域*/ PreOrder（bt->lchild）; /*先序递归遍历bt的左子树*/ PreOrder（bt->rchild）; /*先序递归遍历bt的右子树*/ }二叉树中序遍历的递归算法 void InOrder（BiTree bt） { /*中序遍历二叉树bt*/ if (bt==NULL) return; /*递归调用的结束条件*/ InOrder（bt->lchild）; /*中序递归遍历bt的左子树*/ printf ("%d",bt->data); /*访问结点的数据域*/ InOrder（bt->rchild）; /*中序递归遍历bt的右子树*/ }二叉树后序遍历的递归算法 void PostOrder（BiTree bt） { /*后序遍历二叉树bt*/ if (bt==NULL) return; /*递归调用的结束条件*/ PostOrder（bt->lchild）; /*后序递归遍历bt的左子树*/ PostOrder（bt->rchild）; /*后序递归遍历bt的右子树*/ printf("%d",bt->data); /*访问结点的数据域*/ }二叉。