四、雙向鏈表復(fù)制

文章目錄

• 四、雙向鏈表復(fù)制
• • 題目描述
  • 解題思路
  • 上機(jī)代碼

題目描述

設(shè)一帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表表示的線性表：L =（a1, a2, …… , an）
請(qǐng)寫出一個(gè)時(shí)間復(fù)雜度為O(n)的算法，將L改造為：L =（a1, a2, ……, an-1, an, an-1, ……, a2, a1）

預(yù)設(shè)代碼：

/* PRESET CODE BEGIN - NEVER TOUCH CODE BELOW *//* 設(shè)一帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表表示的線性表： L =（a1, a2, …… , an） 請(qǐng)寫出一個(gè)時(shí)間復(fù)雜度為O(n)的算法，將L改造為： L =（a1, a2, ……, an-1, an, an-1, ……, a2, a1） */#include <stdio.h> #include <stdlib.h> typedef int ElemType; typedef struct DuLNode {ElemType data; // 數(shù)據(jù)域struct DuLNode *prior; // 指向前驅(qū)的指針域struct DuLNode *next; // 指向后繼的指針域 } DuLNode, * DuLinkList;// 函數(shù)原型 void out_next(DuLinkList); void out_prior(DuLinkList); void rcopy(DuLinkList); //這是你要編寫的函數(shù) // 函數(shù)定義 void out_next(DuLinkList DHead) { DuLinkList p = DHead->next; while ( p != DHead ){ printf("%d,", p->data);p = p->next;}printf("\n"); } void out_prior(DuLinkList DHead) { DuLinkList p = DHead->prior; while ( p != DHead ){ printf("%d,", p->data);p = p->prior;}printf("\n"); }int main() { DuLinkList DHead, p;int num;DHead = (DuLNode*)malloc( sizeof(DuLNode));DHead->data = -1;DHead->prior = DHead->next = DHead; // 生成表頭scanf("%d", &num);while ( num != -1 ){ p = (DuLNode*)malloc( sizeof(DuLNode));p->data = num;p->next = DHead->next; // 1.鏈接p的next鏈 DHead->next = p; // 2.鏈接DHead的next鏈p->next->prior = p; // 3.鏈接p的next的prior鏈p->prior = DHead; // 4.鏈接p的prior鏈scanf("%d", &num);}printf("Link next:"); out_next( DHead );printf("Link prior:"); out_prior( DHead );rcopy( DHead );printf("NewL next:"); out_next( DHead );printf("NewL prior:"); out_prior( DHead );return 0; } /************************************** void rcopy(DuLinkList DHead) {This function is wating for you. } ***************************************//* PRESET CODE END - NEVER TOUCH CODE ABOVE */ 測(cè)試輸入期待的輸出時(shí)間限制內(nèi)存限制額外進(jìn)程

測(cè)試用例 1	1 2 3 4 5 -1	Link next:5,4,3,2,1, Link prior:1,2,3,4,5, NewL next:5,4,3,2,1,2,3,4,5, NewL prior:5,4,3,2,1,2,3,4,5,	1秒	64M	0
測(cè)試用例 2	10 20 -1	Link next:20,10, Link prior:10,20, NewL next:20,10,20, NewL prior:20,10,20,	1秒	64M	0
測(cè)試用例 3	1 2 3 4 5 6 7 8 9 10 11 12 -1	Link next:12,11,10,9,8,7,6,5,4,3,2,1, Link prior:1,2,3,4,5,6,7,8,9,10,11,12, NewL next:12,11,10,9,8,7,6,5,4,3,2,1,2,3,4,5,6,7,8,9,10,11,12, NewL prior:12,11,10,9,8,7,6,5,4,3,2,1,2,3,4,5,6,7,8,9,10,11,12,	1秒	64M	0

解題思路

函數(shù)參數(shù)傳入的是頭結(jié)點(diǎn)Dhead的位置，Dhead->prior 即找到an結(jié)點(diǎn)。使用兩個(gè)指針p、q，其中p指向an結(jié)點(diǎn)。

p指針向左掃描一個(gè)位置，就利用q指針向右建立一個(gè)結(jié)點(diǎn)，仿照main函數(shù)中的操作建立雙向循環(huán)鏈表即可。

上機(jī)代碼

void rcopy(DuLinkList DHead) {//找到an結(jié)點(diǎn)DuLinkList p = DHead->prior, q=NULL;//建立雙向循環(huán)鏈表while(p->prior != DHead){p = p->prior;q = (DuLNode*)malloc(sizeof(DuLNode));q->data = p->data;q->prior = DHead->prior;q->prior->next = q;q->next = DHead;q->next->prior = q;} }

總結(jié)

以上是生活随笔為你收集整理的四、双向链表复制的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。