设为首页收藏本站
开启辅助访问

数据结构算法（C,C++）南邮考研自用

 您所在的位置：网站首页 › 算法与数据结构c语言版知识点 › 数据结构算法（C,C++）南邮考研自用

数据结构算法（C,C++）南邮考研自用

2024-07-04 14:47| 来源: 网络整理| 查看: 265

数据结构算法

南邮数据结构自己整理的基础算法，掺杂了南邮的C语言教材和王道教材

章节目录 数据结构算法&2 线性表&2.1 顺序表&2.2 链式存储&2.2.1单链表类型定义&2.2.2带表头结点的单链表&2.2.3循环单链表&2.2.4双向链表&2.2.5循环双链表&2.2.6静态链表&2.2.7线性表应用 &3 栈和队列&3.1 栈&3.1.1 栈顺序结构实现&3.1.2 栈的基本运算&3.1.3 栈的链式存储 &3.2 队列&3.2.1 队列顺序表示&3.2.2 循环队列&3.2.3 链式队列 &4 数组和字符串&4.1 稀疏矩阵&4.1.1 定义&4.1.2 快速转置 &4.2 字符串&4.2.1 串的定义&4.2.2 模式匹配&4.2.2.1 简单模式匹配&4.2.2.2 改进字符串匹配（KMP）&4.2.2.3 KMP进一步优化 &5 树与二叉树&5.2 二叉树&5.3 二叉树遍历&5.3.1 递归&5.3.1.1 先序遍历&5.3.1.2 中序遍历&5.3.1.3 后序遍历 &5.3.2 非递归&5.3.2.1 中序遍历&5.3.2.2 先序遍历&5.3.2.3 后序遍历 &5.3.3 层次遍历 &5.4 线索二叉树&5.4.1 存储结构&5.4.2 线索化&5.4.3 遍历 &5.5 树、森林&5.5.1 树的存储结构&5.5.1.1 双亲表示法&5.5.1.2 孩子兄弟表示法 &5.6 树、二叉树应用&5.6.1 二叉排序树&5.6.2 平衡二叉树 &6 图&6.1 图的存储及操作&6.1.1 邻接矩阵&6.1.2 邻接表法 &6.2 图的遍历&6.2.1 广度优先搜索&6.2.1.1 搜索算法伪代码&6.2.1.2 BFS求解单源最短路径 &6.2.2 深度优先搜索&6.2.2.1 搜索算法伪代码&6.2.2.2 输出所有简单路径 &6.3 图的应用&6.3.1 最小生成树&6.3.1.1 通用最小生成算法&6.3.1.2 Prim算法（普里姆）&6.3.1.3 Kruskal算法（克鲁斯卡尔） &6.3.2 拓扑排序 &6.4 归纳总结&6.4.1 取邻接顶点的下一个邻接顶点 &7 查找&7.1 顺序查找和折半查找&7.1.1 一般线性表的顺序查找&7.1.2 折半查找 &8 排序&8.1 插入排序&8.1.1 直接插入排序&8.1.2 折半插入排序&8.1.3 希尔排序 &8.2 交换排序&8.2.1 冒泡排序&8.2.2 快速排序 &8.3 选择排序&8.3.1 简单选择排序&8.3.2 堆排序 &8.4 归并排序和基数排序&8.4.1 归并排序

&2 线性表 &2.1 顺序表

顺序存储类型：

#define MaxSize 50 //线性表最大长度 typedef struct { ElemType data[ MaxSize ]; //创建数据元素数组 int length; //线性表当前长度 } SqList; //线性表静态顺序实现sqlist

动态分配线性表：

#define InitSize 100 //线性表最大长度 typedef struct { ElemType *data; //指示动态数组的指针 int MaxSize; //数组最大容量 int length; //数组当前长度 } SeqList; //线性表动态顺序实现seqlist

初始化动态分配：

#define error 0 #define ok 1 typedef int Status ; //类型定义 Status Init ( SeqList *L , int size ) { //Init初始化函数，status为整型=int L -> MaxSize = size; //线性表最大长度 L -> length = 0; //当前长度 L -> data = ( ElemType *) malloc ( sizeof ( ElemType ) * size ); //动态分配数组空间，malloc动态分配函数 if ( !L -> data ) { //动态数组为空执行 return error; //0 } return ok; //1 }

查找（按位查找）：

Status Find ( SeqList L , int i , ElemType *x) { //按位查找函数 if ( i L -> length - 1 ) { //越界判断 return error; } *x = L -> data[ i ]; //取出data[i]通过参数x返回 return ok; }

查找（按值查找）：

int LocateElem ( SeqList L , ElemType e ) { //按值查找函数 int i; //位序 for ( i = 0 ; i lentgh ; i++ ) { //循环查找 if ( L -> data[ i ] == e ) { //判断是否相等 return i + 1; //返回位序 } } return 0; }

插入（在Ai后面插入x）：

Status Insert ( SeqList *L , int i , ElemType x ) { //插入函数 int j; //循环下标 if ( i L -> length -1 ) { //越界判断 return error; } if ( L -> length == L -> MaxSize ) { //数组是否满长 return error; } for ( j = L -> length - 1 ; j > i ; j-- ) { //从后往前依次将数组元素往后移一位 L->data[ j + 1 ] = L->data[ j ]; } L -> data[ i + 1 ] = x; //将元素放入后一位位置 L -> length = L -> length + 1; //表长长度+1 return ok; }

删除（Ai位置删除）：

Status Delete ( SeqList *L , int i , ElemType *x ) { //删除函数 int j; //循环下标 if ( i L -> length - 1 ) { //越界判断 return error; } if ( !L -> length ) { //线性表是否为空 return error; } e = L -> data[ i ]; //取出data[i]通过参数x返回 for ( j = length + 1 ; j length ; j++ ) { //从后往前依次将数组元素往前移一位 L -> data[ j - 1 ] = L -> data[ j ]; } L->length --; //表长长度-1 return ok; }

输出（顺序表元素依次输出）：

Status Output ( SeqList *L ) { //输出顺序表元素 int i; //循环下标 if ( L -> length == 0 ) { //线性表是否为空 return error; } for ( i = 0 ; i length ; i++ ) { //从前往后数组依次输出 printf( "%d " , L -> data[ i ] ); } printf( "\n" ); return ok; }

撤销（释放动态分配空间，防止内存泄漏）：

void Destory ( SeqList *L ) { L -> length = 0; L -> MaxSize = 0; free( L -> data ); } &2.2 链式存储 &2.2.1单链表类型定义 typedef struct node { //单链表结点 ElemType element; //结点数据域 struct node *link; //结点指针域 } Node; typedef struct singleList { //单链表 Node *first; //头指针 int n; //单链表元素个数 } SingleList;

单链表初始化：

Status Init ( SingleList *L ) { L -> first = NULL; //第一个结点为空结点 L -> n = 0; //元素个数为0 return ok; }

头插法建立单链表：

SingleList List_HeadInsert ( SingleList &L ) { //头插法 Node *s; int x; //数据域 L = ( SingleList ) malloc ( sizeof ( Node ) ); //创建头结点 L -> next = NULL; //指针域为空 scanf( "%d" , &x ); while ( x != 9999 ) { //9999表示结束 s = ( Node* ) malloc ( sizeof ( Node ) ); //创建新结点 s -> element = x; //赋值 s -> next = L -> next; //将原来头结点的指针域赋给插入结点 L -> next = s; //将插入结点作为头结点的指针域 scanf( "%d" , &x ); } return L; }

尾插法建立单链表：

SingleList List_TailInsert ( SingleList &L ) { int x; L = ( SingleList ) malloc ( sizeof ( Node ) ); //创建头结点 Node *s; //插入结点 Node *r = L; //表尾指针 scanf( "%d" , &x ); while ( x != 9999 ) { //9999表示结束 s = ( Node* ) malloc ( sizeof ( Node ) ); //创建新结点 s -> element = x; //数据域赋值 r -> next = s; //表尾指针结点域赋值 r = s; //表尾指针更换 scanf( "%d" , &x ); } r -> next = NULL; //表尾指针结点域为NULL return L; }

按序号查找（数据域）：

Status Find_Element ( SingleList L , int i , ElemType *x ) { //链表,位序,值 Node *p; int j; if ( i L-> n - 1 ) { //越界判断 return error; } p = L -> first; //头结点 for ( j = 0 ; j link; } *x = p -> element; //取出指定结点的元素值 return ok; }

按序号查找（结点）：

Node *Find_Node ( SingleList L , int i ) { //链表,位序,值 Node *p; int j; if ( i L-> n - 1 ) { //越界判断 return error; } p = L -> first; //头结点 for ( j = 0 ; j link; } //取出指定结点的元素值 return p; }

按结点值查找：

Node *Locate_Elem ( SingleList L , ElemType e ) { //链表,值 Node *p = L -> first; //头结点 p = p -> link; //第一个结点 while ( p != NULL && p -> element != e ) { //判断空结点和数据域值 p = p -> link; } return p; }

插入（前插在i位置）：

p = Find_Node ( L , i - 1 ); //找到插入位置前一个位置 s -> link = p -> link; //结点域赋值 p -> link = s; //结点域赋值

完整插入：

Status Insert ( SingleList *L , int i , ElemType x ) { Node *p , *q; int j; if ( i L -> n - 1 ) { //越界判断 return error; } p = L -> first; for ( j = 0 ; j link; } q = ( Node* ) malloc ( sizeof( Node ) ); //生成新结点 q -> element = x; if ( i > -1 ) { q -> link = p -> link; //放入后面结点 p -> link = q; } else { q -> link = L -> first; //变成头结点 L -> first = q; } L -> n ++; return ok; }

插入（s插入到p之前）：

s -> link = p -> link; //结点域赋值 p -> link = s; //交换位置 temp = p -> element; //交换数据域 p -> element = s -> element; s -> element = temp;

删除：

p = Find_Node( L , i - 1 ); //找前驱 q = p -> link; //找到被删除结点 p -> link = q -> link; //删除结点域赋值给前驱结点的结点域 free( q ); //释放结点

删除（赋值）：

q = p -> link; //找后继结点 p -> element = p -> link -> element; //后继值赋值 p -> link = q -> link; //后继的后继为后继 free( q );

完整删除：

Status Delete ( SingleList *L , int i ) { int j; Node *p, *q; if ( !L -> n ) { //空表判断 return error; } if ( i L -> n - 1 ) { //月结判断 return error; } q = L -> first; p = L -> first; for ( j = 0 ; j link; } if ( i == 0 ) { L -> first = L -> first -> link; //头结点为头结点的结点域 } else { p = q -> link; //后继的后继为后继 q -> link = p -> link; } free( q ); L -> n--; return ok; }

输出：

Status Output( SingleList *L ) { Node *p; if ( !L -> n ) { //空表判断 return error; } p = L -> first; while( p ) { printf( "%d" , p -> element ); p = p -> link; } return ok; }

撤销：

void Destory( SingleList *L ) { Node *p; while ( L -> first ) { p = L -> first -> link; //保存后继 free( L -> first ); L -> first = p; } } &2.2.2带表头结点的单链表 typedef struct headerList { //同SingleList Node *head; int n; } HeaderList;

初始化：

Status Init ( HeaderList *h ) { h -> head = ( Node* ) malloc ( sizeof( Node ) ); if ( ! h -> head ) { return error; } h -> head -> link = NULL; h -> n = 0; return ok; }

插入：

Status Insert ( HeaderList *h , int i , ElemType x ) { Node *p, *q; int j; if ( i h -> n - 1 ) { return error; } p = h -> head; for ( j = 0 ; j link; } q = ( Node* ) malloc ( sizeof( Node ) ); q -> element = x; q -> link = p -> link; //后继为插入的后继 p -> link = q; h -> n ++; return ok; }

删除：

Status Delete ( HeaderList * h , int i ) { int j; Node *p, *q; if ( !h -> n ) { return error; } if ( i h -> n - 1 ) { return error; } q = h -> head; for ( j = 0 ; j link; } p = q -> link; q -> link = p -> link; //后继结点替换 free( p ); h -> n --; return ok; } &2.2.3循环单链表 r -> link = L -> head; //表尾指针的结点域为表头结点 &2.2.4双向链表 typedef struct duNode { ElemType element; struct duNode *llink; //左结点 struct duNode *rlink; //右结点 } DuNode , Dulist;

插入：

q -> llink = p -> link; //先把插入的两端赋值 q -> rlink = p; p -> llink -> rlink = q; //先赋值前端 p -> link = q; //最后赋值两个结点关联的结点域

删除：

p -> llink -> rlink = p -> rlink; //左右结点直接赋值 p -> rlink -> llink = p -> llink; free( p ); &2.2.5循环双链表 p -> llink = L -> head; //p为尾结点 L -> head -> llink = L; //空表 L -> head -> rlink = L; &2.2.6静态链表 #define MaxSize 50 typedef struct { ElemType data; //存储数据元素 int next; //结点域为数组下标 } SLinkList[ MaxSize ]; &2.2.7线性表应用

多项式类型定义：

typedef struct pNode { int coef; int exp; struct pNode* link; } PNode; typedef struct polunominal { PNode *head; } Polynominal;

多项式创建：

void Create ( Polynominal *p ) { PNode *pn, *pre, *q; //插入结点,前驱结点,后继结点 p -> head = ( PNode* ) malloc ( sizeof( PNode ) ); p -> head -> exp = - 1; p -> head -> link = p -> head; for ( ; ; ) { pn = ( PNode* ) malloc ( sizeof( PNode ) ); printf( "coef:\n" ); scanf( "%d" , &pn -> coef ); printf( "exp:\n" ); scanf( "%d" , &pn -> exp ); if ( pn -> exp head; q = p -> head -> link; while ( q && q -> exp > pn -> exp ) { //q为小于pn的结点，pre为大于pn的结点 pre = q; q = q -> link; } pn -> link = q; pre -> link = pn; } }

多项式加法：

void Add ( Polynominal *px , Polynominal *qx ) { PNode *q, *q1 = qx -> head , *p, *p1, *temp; p = px -> head -> link; //px第一个结点 q = q1 -> link; //q1是q的前驱 while ( p -> exp >= 0 ) { while ( p -> exp exp ) { //跳过系数大的项 q1 = q; q = q -> link; } if ( p -> exp == q -> exp ) { //指数相等 q -> coef = q -> coef + p -> coef; if ( q -> coef == 0 ) { //系数和为0则删除结点 q1 -> link = q -> link; free( q ); q = q1 -> link; p = p -> link; } else { //不为0则不管 q1 = q; q = q -> link; p = p -> link; } } else { //不存在相对应指数项，插入相关项 temp = ( PNode* ) malloc ( sizeof( PNode ) ); temp -> coef = p -> coef; temp -> exp = p -> exp; temp -> link = q1 -> link; q1 -> link = temp; q1 = q1 -> link; p = p -> link; } } } &3 栈和队列 &3.1 栈 &3.1.1 栈顺序结构实现 typedef struct stack { int top; //当前栈顶位置下标,初始为-1,栈长为top+1 int maxSize; //maxSize-1为堆栈最大栈顶位置下标 ElemType *element; //存储堆栈元素的一维数组首地址指针 //ElemType data[ maxSize ]; } Stack; &3.1.2 栈的基本运算

初始化（创建）

void Create ( Stack *s , int mSize ) { S -> maxSize = mSize; S -> element = ( ElemType * ) malloc ( sizeof ( ElemType ) * mSize ); S -> top = -1; }

销毁栈，释放数组空间：

void Destroy ( Stack *S ) { S -> maxSize = 0; free( S -> element ); S -> top = -1; }

判断空栈：

bool IsEmpty ( Stack *S ) { return S -> top == -1; }

判断栈满：

bool IsFull ( Stack *S ) { return S -> top == S -> maxSize - 1; }

获取栈顶元素：

bool Top ( Stack *S , ElemType *x ) { if ( IsEmpty ( S ) ) { return false; } *x = S -> element [ S -> top ]; return true; }

入栈操作：

bool Push ( Stack *S , ElemType x ) { if ( IsFull ( S ) ) { return false; } S -> top ++; S -> element [ S -> top ] = x; return true; }

出栈操作：

bool Pop ( Stack *S ) { if ( IsEmpty ( S ) ) { return false; } S -> top --; return true; }

清除堆栈中所有元素，不释放空间：

void Clear ( Stack *S ) { S -> top = -1; } &3.1.3 栈的链式存储

链式存储类型：

typedef struct Linknode { ElemType data; struct Linknode *next; } *LiStack; &3.2 队列 &3.2.1 队列顺序表示 typedef struct queue { int front; //指向队头元素前一个位置 int rear; //指向队尾元素 int maxSize; ElemType *element; } Queue;

队空：

Q -> front == Q -> rear; &3.2.2 循环队列

循环队列结构体定义：

typedef struct queue { int front; int rear; int maxSize; ElemType *element; } Queue;

创建空队列：

void create( Queue *Q , int mSize ) { Q -> maxSize = mSize; Q -> element = ( ElemType *) malloc ( sizeof( ElemType) * mSize ); Q -> front = Q -> rear = 0; }

销毁队列，释放空间：

void Destory( Queue *Q ) { Q -> maxSize = 0; free( Q -> element ); Q -> front = Q -> rear = -1; }

判断队列是否为空：

bool IsEmpty( Queue *Q ) { return Q -> front == Q -> rear; }

判断队列是否满：

bool IsFull( Queue *Q ) { return ( Q -> rear + 1 ) % Q -> maxSize = Q -> front; }

获取队头元素：

bool Front( Queue *Q , ElemType *x ) { if( IsEmpty( Q ) ) { return false; } *x = Q -> element[ ( Q -> front + 1 ) % Q -> maxSize ]; return true; }

队尾插入元素（入队）：

bool EnQueue( Queue *Q , ElemType x ) { if( IsFull( Q ) ) { return false; } Q -> rear = ( Q -> rear + 1 ) % Q -> maxSize; Q -> element[ Q -> rear ] = x; return true; }

删除队头元素（出队）：

bool DeQueue( Queue *Q ) { if( IsEmpty( Q ) ) { return false; } Q ->front = ( Q -> front + 1 ) % Q -> maxSize; return true; }

清除队列中全部元素，不释放空间：

void Clear( Queue *Q ) { Q -> front = Q -> rear = 0; }

队列判断条件：

( Q -> rear + 1 ) % Q -> maxSize = Q -> front; //队满条件 Q -> front == Q -> rear; //队空条件 ( Q -> rear - Q -> front + maxSize ) % maxSize; //元素个数 &3.2.3 链式队列

链式存储类型定义：

typedef struct { ElemType data; struct LinkNode *next; } LinkNode; typedef struct { LinkNode *front , *rear; }

链式队列判断条件：

Q -> front == Q -> rear == NULL;

初始化：

void InitQueue( LinkQueue &Q ) { Q -> front = Q -> rear = ( LinkNode *) malloc ( sizeof( LinkNode ) ); Q -> front -> next = NULL; }

判队空：

bool IsEmpty( LinkQueue Q ) { if( Q -> front == Q -> rear ) { return true; } else { return false; } }

入队：

void EnQueue( LinkQueue &Q , ElemType x ) { LinkNode *s = ( LinkNode *) malloc ( sizeof( LinkNode ) ); s -> data = x; s -> next = NULL; Q -> rear -> next = s; Q -> rear = s; }

出队：

bool DeQueue( LinkQueue &Q , ElemType &x ) { if( Q -> front == Q -> rear ) { return false; } LinkNode *p = Q -> front -> next; if( Q -> rear == p ) { Q -> rear = Q -> front; } free( p ); return true; } &4 数组和字符串 &4.1 稀疏矩阵 &4.1.1 定义 #define maxsize 100 typedef int ElemType; typedef struct term { int col , row; ElemType value; } Term; typedef struct sparsematrix { int m , n , t; Term table[ maxSize ]; } SparseMatrix; &4.1.2 快速转置 for( int j = 0 ; j lchild; } else { Pop( S , p ); p = p -> rchild; } } } &5.3.2.3 后序遍历 void PostOrder2( BiTree T ) { InitStack( S ); BiTree p = T; BiTree r = NULL; while( p || !IsEmpty( S ) ) { if( p ) { Push( S , p ); p = p -> lchild; } else { GetTop( S , p ); //只读不取 if( p - > rchild && p -> rchild != r ) { //右结点没被访问过 p = p -> rchild; } else { Pop( S , p ); visit( p ); r = p; p = NULL; } } } } &5.3.3 层次遍历 void LevelOrder( BiTree T ) { InitQueue( Q ); BiTree p; EnQueue( Q , T ); while( !IsEmpty( Q ) ) { DeQueue( Q , p ); visit( p ); if( p -> lchild != NULL ) { EnQueue( Q , p -> lchild ); } if( P -> rchild != NULL ) { EnQueue( Q , p -> rchild ); } } } &5.4 线索二叉树 &5.4.1 存储结构 typedef struct ThreadNode { ElemType data; struct ThreadNode *lchild , *rchild; int ltag , rtag; } ThreadNode , *ThreadTree; &5.4.2 线索化

中序遍历递归线索化：

void InThread( ThreadTree &p , ThreadTree &pre ) { if( p != NULL ) { InThread( p -> lchild , pre ); if( p -> lchild == NULL ) { p -> lchild = pre; p -> ltag = 1; } if( pre != NULL && pre -> rchild == NULL ) { pre -> rchild = p; pre -> rtag = 1; } pre = p; InThread( p -> rchild , pre ); } } void CreateInThread( ThreadTree T ) { ThreadTree pre = NULL; if( T != NULL ) { InThread( T , pre ); pre -> rchild = NULL; pre -> rtag = 1; } } &5.4.3 遍历

中序序列第一个结点：

ThreadNode *Firstnode( ThreadNode *p ) { while( p -> ltag == 0 ) { p = p -> lchild; return p; } }

结点p在中序序列下的后续：

ThreadNode *Nextnode( ThreadNode *p ) { if( p -> rtag == 0 ) { return Firstnode( p -> rchild ); } else { return p -> rchild; } }

中序序列最后一个结点：

ThreadNode *Lastnode( ThreadNode *p ) { while( p -> rtag == 0 ) { p = p -> rchild; return p; } }

结点p在中序序列下的前驱：

ThreadNode *Prenode( ThreadNode *p ) { if( p -> ltag == 0 ) { return Firstnode( p -> lchild ); } else { return p -> lchild; } } &5.5 树、森林 &5.5.1 树的存储结构 &5.5.1.1 双亲表示法 #define MAX_TREE_SIZE 100 typedef struct { ElemType data; int parent; } PTNode; typedef struct { PTNode nodes[ MAX_TREE_SIZE ]; int n; } PTree; &5.5.1.2 孩子兄弟表示法 typedef struct CSNode { ElemType data; struct CSNode *firstchild , *nextsibling; } CSNode , *CSTree; &5.6 树、二叉树应用 &5.6.1 二叉排序树

二叉排序树非递归查找：

BSTNode *BST_Search( BiTree T , ElemType key ) { while( T != NULL && key != T -> data ) { if( key data) { T = T -> lchild; } else { T = T -> rchild; } } return T; }

插入：

int BST_Insert( BiTree &T , KeyType k ) { if( T == NULL ) { T = ( BiTree ) malloc ( sizeof( BSTNode ) ); T -> key = k; T -> lchild = T -> rchild = NULL; return 1; } else if( k == T -> key ) { return 0; } else if( k key ) { return BST_Insert( T -> lchild , k ); } else { return BST_Insert( T -> rchild , k ); } }

构造：

void Creat_BST( BiTree &T , KeyType str[] , int n ) { T = NULL; int i = 0; while( i nextarc; } visited[ u ] = 0; } &6.3 图的应用 &6.3.1 最小生成树 &6.3.1.1 通用最小生成算法

伪代码：

GENERIC_MST( G ) { T = null; while T 未形成一棵生成树; do 找到一条最小代价边(u,v)并且加入T后不会产生回路; T = T∪(u,v); } &6.3.1.2 Prim算法（普里姆）

简单实现：

void Prim( G , T ) { T = 空集; U = { w }; while( ( V - U ) != 空集) { 设(u,v)是使u属于U与v属于(V-U)，且权值最小的边; T = T ∪ {(u,v)}; //边归入树 U = U ∪ { v }; //顶点归入树 } } &6.3.1.3 Kruskal算法（克鲁斯卡尔）

简单实现：

void Kruskal( V , T ) { T = V; numS = n; while( numS > 1 ) { 从E中取出权值最小的边(u,v); if(v和u属于T的不同的连通分量){ T = T ∪ {(u,v)}; //边归入树 numS--; } } } &6.3.2 拓扑排序

排序算法：

bool TopologicalSort( Graph G ) { InitStack( S ); for( int i = 0 ; i nextarc ) { v = p -> adjvex; if( !( --indegree[ v ] ) ) { //i指向的顶点入度减1，为0的顶点压入栈S Push( S , v ); } } } if( count next; } if( p != NULL && p -> next != NULL ) { return p -> next -> data; } } return -1; } &7 查找 &7.1 顺序查找和折半查找 &7.1.1 一般线性表的顺序查找 typedef struct { ElemType *elem; int TableLen; } SSTable; int Search_Seq( SSTable ST , ElemType key ) { ST.elem[ 0 ] = key; for( i = ST.TableLen ; ST.elem[ i ] != key ; --i ) { return i; } } &7.1.2 折半查找

非递归：

int Binary_Search( SeqList L , ElemType key ) { int low = 0 , high = L.TableLen - 1 , mid; while( low key ) { high = mid - 1; } else { low = mid + 1; } } return -1; }

递归：

typedef struct { ElemType *elem; int length; } SSTable; int BinSearchRec( SSTable ST , ElemType key , int low , int high ) { if( low > high ) { return 0; } mid = ( low + high ) / 2; if( key > ST.elem[ mid ] ) { Search( ST , key , mid + 1 , high ); } else if( key


【本文地址】


今日新闻

推荐新闻

CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3