DAY1 2025年6月29日 雨轉晴🌧🌤
第二章 線性表
2.2線性表的順序表示
1、從順序表中刪除具有最小值的元素（假設唯一）并由函數返回被刪元素的值。空出的位置由最后一個元素填補，若順序表為空，則顯示出錯信息并推出運行。
【思路】/*首先應該判空，空則顯示出錯，并推出；再遍歷整個順序表，找最小值，并記錄位置，遍歷完成后用最后一個元素補到原來這個最小值元素的位置上。*/
bool Del_min(SqList &L,ElemType &value){ //value 返回值if(L.length==0) return false;value = L.data[0];int index = 0;for(int i =1;i<L.length;i++){if(L.data[i]<value){value = L.data[i];index = i;}L.data[index]=L.data[L.length-1];L.length--;return true;
}2、設計一個高效算法，將順序表L的所有元素逆置，要求算法的空間復雜度為O(1)。
/*題目要求空間復雜度為O(1)，也就是輔助空間為常數級，那數組是不行的了，所以考慮temp變量暫時存放，然后前半和后半對應位置對調即可*/
/*例如1，2，3，4，5 需要逆置，那將前半段和后半段對應位置對調——1，5；2，4；3，就可以得到54321*/void Reverse(SqList &L){ElemType temp;for(int i = 0 ; i<L.length/2 ; i++){temp = L.data[i];L.data[i]=L.data[L.length-i-1];L.data[L.length-i-1]=temp;}
}3、對長度為n的順序表L，編寫一個時間復雜度為O(n)，空間復雜度為O(1)的算法，該算法刪除順序表中所有值為x的數據元素。?
/*【思路】設cnt=0,每次循環如果有x就cnt++,沒有則，讓當前元素往前移動cnt個位置。*/void Del_X(SqList &L,ElemType x){int cnt = 0;i = 0;while(i<L.length){if(L.data[i]==x){cnt++;}else{L.data[i-cnt] = L.data[L];}i++;L.length = L.length-cnt;}
}DAY2 2025年6月30日 晴🌤
1、從順序表中刪除其值在給定值s和t之間（包含s和t，要求s<t）的所有元素，若s或t不合理或順序表為空，則顯示出錯信息并推出運行。
/*【思路】先判空，空則返回false;未異常則遍歷順序表，然后如果遍歷時元素大小在s,t之間，那么cnt++。用以表示要刪除的個數，方便后邊的不在s,t之間的元素前移覆蓋，從而達到刪除的效果*/bool Del_s_t(SqList &L,ElemType s,ElemType t){int i,cnt=0;if(L.length==0||s>=t){ //判空，不能s>=treturn false;}for(i = 0;i<L.length;i++){if(L.data[i]>=s&&L.data[i]<=t){cnt++;}else{L.data[i-cnt]=L.data[i]; //前移k個位置}}L.length-=cnt;return true;
}
2.從有序順序表中刪除所有其值重復的元素，使表中所有元素的值均不同。?
/*【思路】有序順序表，重復的元素一定是在相鄰的位置。所以記錄第一個元素后，然后依次判斷后面的元素是否與前面非重復的有序表的最后一個元素相同。若相同，繼續往后走；不相同就插入到非重復有序表的最后。*/bool Del_Same(SqList &L){if(L.length==0){return false;}int i ,j //i表示第一個不相同的元素，j當作指針遍歷后面的元素for(i = 0,j=1; j<L.length;j++){if(L.data[i]!=L.data[j]) L.data[++i] = L.data[j];}L.length = i+1;return true;
}3.?將兩個有序順序表合并成為一個新的有序順序表，并由函數返回結果順序表。?
/*超級經典！！！【思路】將兩個有序順序表，每次都比較，然后存放較小的那個值。這兩個順序表總有一個先達到length，然后將剩下那個直接搬到總表中*/bool Merge(SqList A,SqList B,SqList &C){if(A.length+B.length>C.maxSize){return false;}int i,j,k=0;while(i<A.length&&j<B.length){ //小的先存if(A.data[i]<=B.data[j]){C.data[k++] = A.data[i++];}else{C.data[k++] = B.data[j++];}}while(i<A.length){ //剩余的一個直接搬過來C.data[k++] = A.data[i++];}while(j<B.length){C.data[k++] = B.data[j++];}C.length = k;return true;
}DAY3 2025年7月1日 晴轉雨?🌤🌧
單鏈表上基本操作的實現
1、單鏈表初始化
/*帶頭節點*/
bool InitList(LinkList &L){L = (LNode*)malloc(sizeof(LNode));//創建頭節點L->next = NULL;return true;
}/*不帶頭節點*/
bool InitList(LinkList &L){L = NULL;return true;
}2、求表長操作
/*記錄單鏈表表中數據結點的個數*/
//帶頭結點
int Length(LinkList L){int len = 0 ;LNode *p=L;while(p->next!=NULL){p = p->next;len++;
}return len;
}//不帶頭結點
int Length(LinkList L){int len =0;LNode *p =L ;while(p!=NULL){len++;p = p->next;}return len;
}3、按序查找
/*沿著next域找，O(n)*/
LNode *GetElem(LinkList L,int i){LNode *p=L;int j = 0;while(p!=NULL&&j<i){p = p-next;j++;
}return p; //p為第i個結點或者是null
}4、按值查找
/*要用結點的data域和定值e比較。O(n)*/
//帶頭結點
LNode *LocateElem(LinkList L,ElemType e){LNode *p =L->next;while(p!=NULL&&p->data!=e){p = p->next;
}return p;
}5、插入結點操作
/*插入到第i個位置，就需要在第i-1個后面進行插入*/
/*s->next = p->next; p-next = s*/
bool ListInsert(LinkList &L,int i ,ElemType e){LNode *p = L;int j = 0;while(p!=NULL&&j<i-1){ //找到第i-1個位置，準備在其后面插入新結點成為第i個。p = p->next;j++;}if(p==NULL) return false;LNode *s = (LNode*)malloc(sizeof(LNode));//新插入結點建立s->data = e;s->next = p->next;p->next =s;return true;
}/*還可以用交換數據域，將前插變為后插*/
s->next = p->next;
p->next = s;
tmp = p->data;
p->data = s->data;
s->data = tmp;6、刪除結點操作
/*刪除要記得釋放空間*/
/*p是被刪結點的前驅，q是被刪的結點*/
bool ListDelete(LinkList &L,int i,ElemType &e){LNode *p = L;int j = 0;while(p->next!=NULL&&j<i-1){p = p->next;j++;}if(p->next ==NULL||j>i-1){return false;
}LNode *q = p->next;e = q->data;p->next = q->next;free(q);return true;
}7.?頭插法建立單鏈表（鏈表逆置）
/*讀入數據的順序和生成的鏈表中元素的順序是相反的，每個結點插入為O(1)，設單鏈表長為n，則總時間復雜度為O(n)*/
LinkList List_HeadInsert(LinkList &L){LNode *s;int x;L = (LNode*)malloc(sizeof(LNode));L->next = NULL;scanf("%d",&x);while(x!=11408){s = (LNode*)malloc(sizeof(LNode));s->data = x;s->next = L->next;L->next = s;scanf("%d",&x);}return L;
}8.尾插法建立單鏈表?
LinkList List_TailInsert(LinkList &L){int x;L = (LNode*)malloc(sizeof(LNode));LNode *s ,*r = L;scanf("%d",&x);while(x!=11408){s = (LNode*)malloc(sizeof(LNode));s->data =x;r->next =s;r = s;scanf("%d",&x);}r->next = NULL;return L;
}
?
測試)