网站建设合同任,网上推广怎么收费,网站建设php有哪些,常德网站建设常德icoding复习 1 链表 倒数查找
1. 已知一个带有表头结点的单链表, 假设链表只给出了头指针L。在不改变链表的前提下#xff0c;请设计一个尽可能高效的算法#xff0c; 查找链表中倒数第k个位置上的结点#xff08;k为正整数#xff09;。 函数原型为#xff1a;int lnk_s…icoding复习 1 链表 倒数查找
1. 已知一个带有表头结点的单链表, 假设链表只给出了头指针L。在不改变链表的前提下请设计一个尽可能高效的算法 查找链表中倒数第k个位置上的结点k为正整数。 函数原型为int lnk_search(LinkList L, int k, ElemType* p_ele) 若查找成功函数通过指针参数 p_ele 返回该结点 data 域的值此时函数返回 1否则函数返回 0。相关定义如下
struct _lnklist{ ElemType data; struct _lnklist *next; };
typedef struct _lnklist Node; typedef struct _lnklist *LinkList;
#include #include #include list.h // 请不要删除否则检查不通过
int lnk_search(LinkList L, int k, ElemType* p_ele){ int i, length; Node *p; for(i 0, p L; p; i) p p-next; length i; if(length 0 || length k) return 0; for(i 0, p L; i length - k; i)//!!取等,注意边界 p p-next; *p_ele p-data; return 1; } 2. 链表 合并
设线性表A(a1, a2,…,am)B(b1, b2,…,bn)试写一个按下列规则合并A、B为线性表C的算法使得 C (a1, b1,…,am, bm, bm1, …,bn) 当m≤n时 或者 C (a1, b1,…,an, bn, an1, …,am) 当mn时。 线性表A、B、C均以单链表作为存储结构且C表利用A表和B表中的结点空间构成。 注意单链表的长度值m和n均未显式存储。 函数的原型如下 void lnk_merge(LinkList A, LinkList B, LinkList C) 即将A和B合并为C其中 C 已经被初始化为空单链表 相关定义如下 //注意:线性表可以是链表 struct _lnklist{ ElemType data; struct _lnklist *next; };
typedef struct _lnklist Node; typedef struct _lnklist *LinkList; #include #include #include list.h // 请不要删除否则检查不通过
void lnk_merge(LinkList A, LinkList B, LinkList C){ Node *p, *q, *c; bool flag true;//小写!python大写首字母 不用包含bool头文件 c C;//c尾指针 p A-next; q B-next; while(p q){ if(flag){ c-next p; c p; p p-next; flag false; } else{ c-next q; c q; q q-next; flag true; } } if(p) c-next p; else c-next q; free(A); free(B);//!! } 3. 顺序表 删除指定范围 设计一个高效的算法从顺序表L中删除所有值介于x和y之间(包括x和y)的所有元素假设yx 要求时间复杂度为O(n)空间复杂度为O(1)。 函数原型如下 void del_x2y(SeqList *L, ElemType x, ElemType y); 相关定义如下
struct _seqlist{ ElemType elem[MAXSIZE]; int last; }; typedef struct _seqlist SeqList; #include list.h // 请不要删除否则检查不通过 #include #include
void del_x2y(SeqList *L, ElemType x, ElemType y){ int i, j 0; for(i 0; i L-last; i){ if(L-elem[i] x || L-elem[i] y) L-elem[j] L-elem[i]; L-last j - 1;//不用设置delta增量记录删除的数量 } 4. 链表 删除范围内结点
已知线性表中的元素整数以值递增有序排列并以单链表作存储结构。 试写一高效算法删除表中所有大于mink且小于maxk的元素若表中存在这样的元素 分析你的算法的时间复杂度。
链表结点定义如下 struct _lnklist{ ElemType data; struct _lnklist *next; }; typedef struct _lnklist Node;//结构标记 typedef struct _lnklist *LinkList;//!! 函数原型如下 void lnk_del_x2y(LinkList L, ElemType mink, ElemType maxk)
#include list.h // 请不要删除否则检查不通过 #include #include
void lnk_del_x2y(LinkList L, ElemType mink, ElemType maxk){ Node *p, *temp; for(p L-next; p; p p-next){ if(p-data maxk p-data mink){ temp p; p p-next; free(p); } if(p-data maxk) break; } } //解法2为指针跟踪技术 void lnk_del_x2y(LinkList L, ElemType mink, ElemType maxk) { Node *p, *pre; pre L; p L-next; for (; p;) { if (p-data mink p-data maxk) { pre-next p-next; free(p); p pre-next; } else { pre p; p p-next; } } }
5. 顺序表 删除重复
编写算法在一非递减的顺序表L中删除所有值相等的多余元素。 要求时间复杂度为O(n)空间复杂度为O(1)。 函数原型如下 void del_dupnum(SeqList *L)
相关定义如下 struct _seqlist{ ElemType elem[MAXSIZE]; int last; }; typedef struct _seqlist SeqList;
#include list.h // 请不要删除否则检查不通过 #include #include //这里是线性表中的顺序表,不是链表! void del_dupnum(SeqList *L){ int i, j 0, delta 0; //一次遍历达到时间复杂度 for(i 0; i L-last; i){ if(L-elem[i] ! L-elem[i1]) L-elem[j] L-elem[i]; else delta; } L-last - delta; } //解法2 不用设置delta增量 void del_dupnum(SeqList* L) { int i, j 1; for (i 1; i L-last; i) { if (L-elem[i] ! L-elem[i - 1]) { L-elem[j] L-elem[i]; } } L-last j - 1; }
6. 顺序表 数据调整
已知顺序表L中的数据元素类型为int。设计算法将其调整为左右两部分 左边的元素即排在前面的均为奇数右边所有元素即排在后面的均为偶数 并要求算法的时间复杂度为O(n),空间复杂度为O1。
函数原型如下 void odd_even(SeqList *L);
相关定义如下 struct _seqlist{ ElemType elem[MAXSIZE]; int last; }; typedef struct _seqlist SeqList;
#include list.h // 请不要删除否则检查不通过 #include #include
#define N 2 //题目描述不清晰 //偶数内部排序顺序未知 void odd_even(SeqList *L){ int i, j; int x; for(i 0, j 0; i L-last i 1 ! L-last - j; i){ //for的另一种写法for (i 0, j 0; i L-last - j; i) { if(!(L-elem[i] % N)){//偶数 x L-elem[L-last-j]; L-elem[L-last-j] L-elem[i]; L-elem[i] x; i--; j; } } } icoding复习2
1. 栈 后缀表达式计算 (1)如果是操作数直接入栈 (2)如果是操作符op连续出栈两次得到操作数x 和 y,计算 x op y并将结果入栈。 #define Stack_Size 50 typedef struct{ ElemType elem[Stack_Size]; int top; }Stack;
bool push(Stack* S, ElemType x); bool pop(Stack* S, ElemType *x); void init_stack(Stack *S); 其中栈初始化的实现为 void init_stack(Stack *S){ S-top -1; } 需要完成的函数定义为int compute_reverse_polish_notation(char *str); 函数接收一个字符指针该指针指向一个字符串形式的后缀表达式函数返回该表达式的计算结果。
#include #include #include list.h // 请不要删除否则检查不通过
//字符指针!!!!!!!!!!!! //易错 int compute_reverse_polish_notation(char* str)//光秃秃的*str 怎么用要知道 { int i 0; Stack S; //没必要*S init_stack(S); ElemType _push, num1, num2; //str[i]等价于*(stri) while (str[i] ! \0) { // 先判空 再判空格 再判数字和符号 数字判断是几位数 if (str[i] ! ) { if (str[i] 0 str[i] 9) { //!! _push 0; while (str[i] ! ) { _push * 10; _push (str[i] - 0); //一个数字一个数字的压入 , 判断位数 i; } push(S, _push); //每次_push会变, push函数里面top会 //切记 } else { //格外小心弹出来的顺序 //先弹出来的符号对它作用 pop(S, num2); pop(S, num1); switch (str[i]) { case : { num1 num2;//注意两个操作数的顺序 break;//!!!!! } case -: { num1 - num2; break; } case *: { num1 * num2; break; } case /: { if(num2)//判除数 num1 / num2; break; } case %: { if(num2) num1 % num2; break; } } push(S, num1); } } i; } pop(S, num1); //最后的返回值也要弹出来 return num1; } 2. 队列 循环链表表示队列 假设以带头结点的循环链表表示队列并且只设一个指针指向队尾元素结点注意不设头指针请完成下列任务 1: 队列初始化成功返回真否则返回假 bool init_queue(LinkQueue *LQ); 2: 入队列成功返回真否则返回假 bool enter_queue(LinkQueue *LQ, ElemType x); 3: 出队列成功返回真且*x为出队的值否则返回假 bool leave_queue(LinkQueue *LQ, ElemType *x); typedef struct _QueueNode { ElemType data; /*数据域*/ struct _QueueNode *next; /*指针域*/ }LinkQueueNode, *LinkQueue; #include #include #include list.h // 请不要删除否则检查不通过
bool init_queue(LinkQueue *LQ){ //注意这里是给*LQ分配空间,不是LQ; 类比Node *p对于p的空间分配 if(!(*LQ (LinkQueue)malloc(sizeof(LinkQueueNode)))) return false; (*LQ)-next *LQ; return true; } //!!! bool enter_queue(LinkQueue *LQ, ElemType x){ LinkQueueNode *p; if(!(p (LinkQueueNode *)malloc(sizeof(LinkQueueNode)))) return false; p-data x; //LQ为队尾指针 //这一步顺序不要颠倒,循环队列连接到头结点 p-next (*LQ)-next; //尾插入 (*LQ)-next p; *LQ p; return true; } //!!! bool leave_queue(LinkQueue* LQ, ElemType* x) { LinkQueueNode *first, *p; //first为头结点 first (*LQ)-next; if (first *LQ) return false; //注意的是头节点为空, 并且是自然形成的 p first-next; *x p-data; if (p ! *LQ) //这种情况只有一个尾结点可以释放 first-next p-next; else {//!!! *LQ (*LQ)-next;//LQ变为头结点,尾指针指向头结点 (*LQ)-next *LQ; //自己构成空循环 } free(p); return true; }
