icoding复习1,2
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, bm+1, …,bn) 當m≤n時；
或者
C= (a1, b1,…,an, bn, an+1, …,am) 當m>n時。
線性表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)的所有元素（假設y>=x），
要求時間復雜度為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[i+1])
?? ??? ??? ?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),空間復雜度為O（1）。
函數原型如下：
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]等價于*(str+i)?
? ? 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;
}
總結
以上是生活随笔為你收集整理的icoding复习1,2的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 单反相机什么牌子好？单反相机哪款好？
- 下一篇： icoding复习6 图