當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

天勤2022数据结构（一）线性表

發布時間：2023/12/31 编程问答 26 豆豆

生活随笔收集整理的這篇文章主要介紹了天勤2022数据结构（一）线性表小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

天勤2022數據結構（一）線性表

前言
一、基礎題
二、思考題
三、真題精選
總結

前言

提示：全文為作者手打，僅供個人復習使用

#define maxSize 50順序表 typedef struct {int data[maxSize];int length; }Sqlist; 單鏈表 typedef struct LNode{int data;struct LNode *next; }LNode;雙鏈表 typedef struct DNode{int data;struct DNode *prev;struct DNode *next; }DNode;

一、基礎題

線性表可用順序表和鏈表存儲，試問：

如果有n個表同時并存，并且在處理過程中各表的長度會動態發生變化，表的總數也可能自動改變，在此情況下，應選用哪種存儲表示？為什么？

用鏈表。
如果采用順序表，在多個表并存的情況下，一旦發現某個表有存滿并溢出的情況，需要移動其他表來騰出空間為其擴容，導致不斷把大片數據反復移動。時間開銷太大且操作易出錯。
若表的總數還要變化，則會帶來在不影響其他表工作的情況下開辟新表空間或釋放舊表空間的操作上的麻煩。
采用鏈表就沒有這些問題
內存空間足夠情況下，各表的空間分配或釋放不受其他表的影響。
若表的總數基本穩定，且很少進行插入和刪除但要求以最快的速度存取表中的元素，這時用哪種存儲表示？為什么？

用順序表、
順序表插入，刪除操作時間復雜度為O(n)，存取操作時間復雜度為O(1)
充分發揮存取速度塊、存儲利用率高的特點

為什么在單循環鏈表中設置尾指針比設置頭指針更好？

what：尾指針是指向終端結點的指針
why：使得查找鏈表的開始結點和終端結點的時間復雜度為O(1)
而設置頭指針，查找終端結點的時間復雜度仍是O(n)

設計一個算法，將順序表中的所有元素逆置。

void swap(int *a, int *b){int t = *a;*a = *b;*b = t; } void reverse(int *nums, int n){for(int i=0, j=n-1; i<j; i++, j--){myswap(&nums[i], &nums[j]);} }

void reverse(Sqlist &L){int i, j;int temp;for(i=0, j=L.length-1; i<j; ++i, --j){temp=L.data[i];L.data[i]=L.data[j];L.data[j]=temp;} }

設計一個算法，從一給定的順序表L中刪除下標i~j（i≤j，包括i、j）的所有元素，假定i、j都是合法的

void delete(Sqlist &L, int i, int j){int k, delta;delta=j-i+1;for(k=j+1; k<L.length; k++){L.data[k-delta]=L.data[k];}L.length-=delta; }

L.length -= delta;

有一個順序表L，其元素為整型數據，設計一個算法，將L中所有小于表頭元素的整數放在前半部分，大于表頭元素的整數放在后半部分

void move(Sqlist &L){int temp=L.data[i], i=0, j=L.length-1;while(i<j){while(i<j && L.data[j]>temp)j--;if(i<j){L.data[i]=L.data[j];i++;}while(i<j && L.data[i]<temp)i++;if(i<j){L.data[j] = L.data[i];j--;}}L.data[i] = temp; }

有一個遞增非空單鏈表，設計一個算法刪除值域重復的結點。例如，｛1，1，2，3，3，3，4，4，7，7，7，9，9，9｝經過刪除后變成（1，2，3，4，7，9｝

void delete(LNode *L){LNode *p=L->next, *q;while(p->next != NULL){if(p->data == p->next->data){q = p->next;p->next = q->next;free(q);}else{p = p->next; }} }

設計一個算法刪除單鏈表L（有頭結點）中的一個最小值結點

void delete(LNode *L){LNode *pre=L, *p=pre->next, *minp=p, *minpre=pre;while(p != NULL){if(p->data<minp->data){min = p;minpre = pre; }pre = p;p = p->next; }minpre->next = minp->next;free(minp); }

有一個線性表，采用帶頭結點的單鏈表L來存儲。設計一個算法將其逆置。要求不能建立新結點，只能通過表中已有結點的重新組合來完成。

void reverse(LNode *L){LNode *p=L->next , *q;L->next=NULL;while(p != NULL){q = p->next;p->next = L->next;L->next = p;p = q;} }

設計一個算法，將一個頭結點為A的單鏈表（數據域為整數）分解成兩個單鏈表A和B，得A鏈表只含有原來鏈表中data域為奇數的結點，而B鏈表只含有原鏈表中data域為偶數的結點，且保持原來的相對順序。

void divide(LNode *A, LNode *&B){LNode *p = A, *q;B = (LNode*)malloc(sizeof(LNode));B->next = NULL;q = B;while(p->next!=NULL){if(p->next->data % 2 == 0){q->next = p->next;q = q->next;p->next = p->next->next;}elsep = p->next;}q->next = NULL; }

二、思考題

有N個個位正整數存放在int型數組A［0，…，N－1］中，N為已定義的常量且N≤9，數組A[]的長度為N，另給一個int型變量i，要求只用上述變量（A[0]~A[N－1]與i，這N+1個整型變量)寫一個算法，找出這N個整數中的最小者，并且要求不能破壞數組A[]中的數據。

void getMin(int[] nums, N){int i = nums[0];for(int j = 1; j<N; j++){if(nums[j]<i) i = nums[j];} }

寫一個函數，逆序打印單鏈表中的數據，假設指針L指向了單鏈表的開始結點

dfs(L); void dfs(LNode *node){if(node == NULL)return;dfs(node->next);printf(node->data); }

設有兩個用有序鏈表表示的集合A和B，設計一個算法，判斷它們是否相等

int equal(Sqlist &A, Sqlist &B){if(A.length != B.length) return -1;for(int i = 0; i<A.length; i++){if(A.data[i]!=B.data[i])return -1;}return 1; }

設A=（a₁，a₂，…，a_m）和B=（b₁，b₂，…，b_n）均為順序表，A^’和B^’分別是除去最大公共前綴后的子表。例如，A=（b，e，i，j，i，n，g），B=（b，e，i，f，a，n，g），則兩者的最大公共前綴為b、e、i，在兩個順序表中除去最大公共前綴后的子表分別為A^’=（j，i，n，g），B^’=（f，a，n，g）若A^’=B^’=空表，則A=B。若A^’=空表且B^’≠空表，或兩者均不為空且A^’的第一個元素值小于B^’的第一個元素值，則A<B，否則A>B。所有表中元素均為 float型，試編寫一個函數，根據上述方法比較A和B的大小。

void compare(){}

鍵盤輸入n個英文字母，輸入格式為n、cl、c2、…、cn，其中n表示字母的個數。請編程用這些輸入數據建立一個單鏈表，并要求將字母不重復地存入鏈表。

LNode *insert(int n){char dic[26] = {0};LNode *L = (LNode*)malloc(sizeof(LNode));L->next = NULL;LNode *p = L, *q;for(int i = 0; i<n; i++){char cur;scanf("%c", &cur);if(dic[cur-'0']==0){dic[cur-'0']=1;q = (LNode*)malloc(sizeof(LNode));q->data = cur;p->next = q;p = p->next;}}return L; }

三、真題精選

已知一個帶有表頭結點的單鏈表，結點結構為：

datanext

假設該鏈表只給出了頭指針head。在不改變鏈表的前提下，請設計一個盡可能高效的算法，查找鏈表中倒數第k（k為正整數）個位置上的結點。若查找成功，算法輸出該結點的data值，并返回1；否則，只返回0.
要求：
（1）描述算法的基本設計思想。
（2）描述算法的詳細實現步驟。
（3）根據設計思想和實現步驟，采用程序設計語言描述算法（使用C或C++語言實現），關鍵之處請給出簡要注釋。

基本設計思想：

從頭至尾遍歷單鏈表，并用指針pre指向當前結點的前k個結點。
當遍歷到鏈表的最后一個結點時，指針pre所指向的結點即為所查找的結點

詳細實現步驟:

聲明2個指針變量cur，pre，1個整型變量cnt
從鏈表頭向后遍歷，指針cur指向當前遍歷的結點，結點pre指向cur所指結點的前k個結點，如果cur之前沒有k個結點，那么pre指向表頭結點。
用整型變量cnt表示當前遍歷了多少個結點，當cnt>k時，指針pre隨著每次遍歷也向后移動一個結點。
當遍歷完成時，pre要么指向表頭指針，要么指向鏈表中倒數第k個位置上的結點

程序設計語言描述:

int find(LNode *L, int k){LNode cur = L, pre = L;int cnt = 0;while(cur != NULL){cur = cur->next;cnt++;/*if判斷不能放前面*/if(cnt > k){pre = pre->next;}}if(cur == L ){return 0;}else{printf("%d", pre->data);return 1;} }

設將n（n>1）個整數存放到一維數組R中。設計一個在時間和空間兩方面盡可能高效的算法。將R中保存的序列循環左移P（0<P<n）個位置，即將R中的數據由（X₀，X₁，…，X_n-1）變換為（X_p，X_p+1，…，X_n-1，X₀，X₁，…，X_p-1）。要求

（1）給出算法的基本設計思想。
（2）根據設計思想，采用C或C++語言描述算法關鍵之處給出注釋。
（3）說明你所設計的算法的時間復雜度和空間復雜度。

基本設計思想:

將R中前P個元素逆置

將剩下的元素逆置

將R中所有的元素整體逆置

void swap(int[] R, int i, int j){R[i] = R[i]^R[j];R[j] = R[i]^R[j];R[i] = R[i]^R[j]; }void reverse(int[] R, int i, int j){for(; i<j; i++, j--){swap(R, i, j);} }void solution(int[] R, int n, int p){reverse(0, p-1);reverse(p, n-1);reverse(0, n-1); }

時間復雜度:O(n)
空間復雜度:O(1)

3. 已知一個整數序列A=（a₀，a₁，…，a_n-1），其中0≤a_i<n（0≤i<n）若存在a_p1=a_p2=…=a_pm=x且m>n/2（0≤p_k≤n, 1≤k≤m），則稱x為A的主元素，例如，A=（0，5，5，3，5，7，5, 5), 則5為主元素；又如，A=（0，5，5，3，5，1，5，7），則A中沒有主元素。假設A中的n個元素保存在一個一維數組中，請設計一個盡可能高效的算法，找出A的主元素。若存在主元素，則輸出該元素;否則輸出-1。要求：

（1）給出算法的基本設計思想
（2）根據設計思想，采用C、C++或Java語言描述算法，關鍵之處給出注釋
（3）說明你所設計算法的時間復雜度和空間復雜度

基本設計思想:
從前往后掃描數組元素,標記出一個可能成為主元素的元素num, 然后重新計數,確認num是否是主元素

選取候選的主元素，依次掃描所給數組中的每個整數，用cnt記錄num的出現次數，將第一個遇到的整數num保存到ans中，cnt=1

若遇到的下一個整數仍等于num，則cnt+=1，否則cnt-=1

當cnt減到0時，將遇到的下一個整數保存到ans中，cnt重新賦值1，開啟新一輪計數，即從當前位置開始重復上述過程，直至掃描完全部數組元素

判斷ans中元素是否時真正的主元素。再次掃描該數組，統計ans中元素出現的次數，若大于n/2，則為主元素；否則，序列中不存在主元素

算法實現：

int majority(int A[], int n){int ans, cnt;ans = A[0];for(int i=1; i<n; i++){if(A[i] == ans){cnt++;}else{if(cnt > 0){cnt--;}else{ans = A[i];cnt = 1;}}}if(cnt > 0){for(i = cnt = 0; i<n; i++){if(A[i] == ans)cnt++;}}return cnt>n/2? ans: -1; }

時間復雜度：O(n)
空間復雜度：O(1)

總結

😄
😢

總結

以上是生活随笔為你收集整理的天勤2022数据结构（一）线性表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

上一篇：《Adobe Flash CS4中文版经
下一篇：在word中如何设置稿纸和字帖？学会帮你